G_del語(yǔ)言編譯系統(tǒng)中推理機(jī)的設(shè)計(jì)與實(shí)現(xiàn).pdf

1、邏輯程序設(shè)計(jì)語(yǔ)言提供了一種說(shuō)明性的編程方法，與基于算法的過(guò)程性程序設(shè)計(jì)語(yǔ)言如Pascal、Ada和C等相比，邏輯程序設(shè)計(jì)語(yǔ)言具有諸多優(yōu)點(diǎn)。首先，邏輯程序豐富的表達(dá)能力和不確定性語(yǔ)言機(jī)制，使其非常適合于表達(dá)人工智能和知識(shí)工程中的問(wèn)題；其次，邏輯程序建立在一階謂詞邏輯的基礎(chǔ)之上，具有嚴(yán)格的數(shù)學(xué)理論基礎(chǔ)，易于進(jìn)行程序的正確性證明和驗(yàn)證；第三，邏輯程序開(kāi)發(fā)者不需要考慮程序“如何計(jì)算”，而只需要說(shuō)明要“做什么”，從而有利于其將精力集中到問(wèn)題的求解

2、上，從計(jì)算模型的層面探索問(wèn)題的求解。由于Prolog語(yǔ)言取得的成功，一直以來(lái)Prolog都是邏輯程序設(shè)計(jì)的代稱。但是，Prolog基于一階邏輯的Horn子集，作為一種無(wú)類型邏輯程序設(shè)計(jì)語(yǔ)言，缺乏足夠的可表達(dá)性，而且，由于Prolog中引入了較多的過(guò)程性謂詞如cut和retract等，使其缺乏清晰、明確的說(shuō)明性語(yǔ)義。 鑒于此，邏輯程序設(shè)計(jì)的研究者們提出了新型邏輯程序設(shè)計(jì)語(yǔ)言G(o)del，它繼承并發(fā)展了Prolog，試圖解決Pro

3、log中存在的諸多語(yǔ)義問(wèn)題，增強(qiáng)其可表達(dá)性能力，縮小理想的邏輯程序與邏輯程序的具體實(shí)現(xiàn)之間的巨大鴻溝。據(jù)此，它引入了參數(shù)型多態(tài)多類類型系統(tǒng)，增加了延遲計(jì)算等新的語(yǔ)言成分，支持模塊化程序設(shè)計(jì)和元程序設(shè)計(jì)，具有靈活的計(jì)算規(guī)則和剪枝操作，并以系統(tǒng)模塊形式提供豐富的抽象數(shù)據(jù)類型以支持通用程序設(shè)計(jì)，對(duì)其適當(dāng)擴(kuò)展可支持面向?qū)ο蟪绦蛟O(shè)計(jì)。但是，作為一種新型的邏輯程序設(shè)計(jì)語(yǔ)言，G(o)del語(yǔ)言能否真正走向成功，還取決于是否有一個(gè)高效率的編譯或解釋實(shí)現(xiàn)

4、系統(tǒng)。迄今為止，就是語(yǔ)言的設(shè)計(jì)者們，也僅實(shí)現(xiàn)了一個(gè)旨在驗(yàn)證語(yǔ)言功能的原型系統(tǒng)。本文圍繞Godel語(yǔ)言的實(shí)現(xiàn)，提出并沿著一條全新的技術(shù)路線，初步實(shí)現(xiàn)了一個(gè)G(o)del編譯程序的實(shí)驗(yàn)室系統(tǒng)，通過(guò)了一組典型的程序?qū)嵗疫\(yùn)行效率很高。本文重點(diǎn)介紹這個(gè)實(shí)驗(yàn)室系統(tǒng)中核心部分推理機(jī)的設(shè)計(jì)與實(shí)現(xiàn)。 本文首先對(duì)推理機(jī)所要實(shí)現(xiàn)的G(o)del語(yǔ)言的主要機(jī)制：類型系統(tǒng)、延遲計(jì)算、剪枝操作等進(jìn)行了分析，討論這些新機(jī)制對(duì)G(o)del語(yǔ)言程序設(shè)計(jì)和SL

5、D反駁一消解過(guò)程的影響。進(jìn)一步，借鑒Warren虛擬機(jī)的設(shè)計(jì)思想，提出了將Godel源程序通過(guò)詞法、語(yǔ)法和語(yǔ)義分析把源程序翻譯成帶說(shuō)明性語(yǔ)義信息的一種高度結(jié)構(gòu)化的中間代碼，然后在中間代碼之上進(jìn)行程序的推理求解的編譯實(shí)現(xiàn)技術(shù)路線?；谠撍枷?，我們具體討論了G(o)del語(yǔ)言編譯系統(tǒng)的總體設(shè)計(jì)結(jié)構(gòu)，闡述了G(o)del語(yǔ)言推理機(jī)實(shí)現(xiàn)的基本原理，重點(diǎn)描述了中間代碼結(jié)構(gòu)和基于該中間代碼的推理機(jī)實(shí)現(xiàn)。最后，通過(guò)性能分析驗(yàn)證了本文實(shí)現(xiàn)的推理機(jī)具有較