軟體工程師手冊/語言詞典/Qi

Qi 是一種由 Mark Tarver 博士開發的功能性程式語言，於 2005 年 4 月推出。一個新版本在 2008 年 11 月重新實現併發布為 Qi II。第一個版本是免費軟體，根據 GPL 許可。但是，由於 GPL 被認為對商業使用不友好，^[1] Qi II 可透過兩種專有許可獲得：一種用於個人和教育用途，另一種用於生產封閉原始碼軟體。

Qi是用Lisp編寫的。它包含了現代函數語言程式設計語言中的大多數常用功能，如模式匹配、柯里化、部分應用、守衛和（可選）靜態型別檢查。

L21 專案

Qi 是作為 L21 專案的一部分開發的，該專案旨在使 Lisp 現代化，以應對 21 世紀計算的挑戰。在他的講座中，^[2] Tarver 博士概述了一系列當前對 Lisp 的挑戰，他認為這些挑戰損害了該語言的更廣泛使用。他特別指出了 Common Lisp 缺乏模式匹配、與 lambda 演算理論的不一致性（部分應用缺失）、過程性汙染和缺乏靜態型別。Tarver 認為，這些缺陷導致 Lisp 在大學水平上普遍被放棄作為教學工具，隨之而來的是 Lisp 程式設計師畢業生的缺乏。Tarver 將這種對大學裡教 Lisp 的缺乏支援描述為導致了一個“典型的惡性迴圈”，即少量精通 Lisp 的畢業生鼓勵從使用 Lisp 程式設計師過渡，這反過來又助長了 Lisp 是一種正在消亡的語言的看法，並助長了 Lisp 教學的衰落。

在同一個講座中，Tarver 建議，這個問題可以從行業端或大學端解決，但從行業端解決這個問題需要一個擁有大量資金投資 Lisp 的冠軍。Tarver 反而建議從大學端解決這個問題，透過使 Common Lisp 現代化，使其在至少 25 年內“未來證明”。他描述的 Lisp 的充分現代化總結在十項要求中，Qi 是為了滿足這些要求而設計的。解決方案應

與 Lisp 相容——作為 Lisp 最廣泛使用的方言，解決方案應該用 Common Lisp 編寫並在 Common Lisp 下執行。
免費用於非商業和教育用途。
緊湊——程式不應比用 Common Lisp 編寫的相同程式更長。
易於學習——語義和語法應該可以被孩子學習。
高效——解決方案應該生成至少與手動編碼的 Lisp 等效程式一樣快的程式。在實踐中，Qi 程式已被證明通常更快。^[3]
具有現代函數語言程式設計語言的特徵。Tarver 博士將這些特徵包括模式驅動的列表處理、靜態型別、柯里化和部分應用。
不只是 Haskell 或 ML 的克隆——這是“未來證明”解決方案的一部分。
在計算上是充分的——這意味著該語言“足以滿足當今程式設計師的需求”。Tarver 博士將“計算充分性”描述為“一個大而模糊的重要概念”，並認為這個概念的擴充套件隨著時間的推移而改變。他認為 Common Lisp 由於缺乏對諸如外部語言介面和圖形等功能的規範，在“計算上不充分”。Tarver 認為，Qi 本身還需要透過開發圖形、Web 介面和外部語言處理的標準庫來實現這個目標。
可[超程式設計和可定製——使用者應該可以自由地對語言的語法進行程式設計。為了實現這一點，Qi 對其所有語法都有 M 表示式和 S 表示式級別的語法，以及一個“eval”函式，將 M 表示式對映到 S 表示式；這使得在 Qi 中進行超程式設計比在 Lisp 中更容易。在定製方面，Qi 有一個顯式的“sugar”關鍵字，允許使用者對 Qi 閱讀器進行程式設計以接受自定義語法。
有充分的文件記錄，在理論上是安全的——Qi 擁有完整的文件記錄，並具有正式的正確性證明，並且有一本規範的教科書也在線上。^[4]

架構

Qi 利用推演演算的邏輯符號來定義型別。在 Qi 的解釋下，這種型別符號實際上本身就是一個圖靈完備語言。這種符號允許 Qi 為 Common Lisp 庫分配可擴充套件的型別系統，被認為是該語言的一個非常強大的功能。

Qi 透過抽象統一機 (AUM) 將推演演算編譯為 Qi Prolog（它被納入 Qi 環境）。AUM 充當函數語言程式設計的類似物，類似於 Warren 抽象機，從本質上是擴充套件的 lambda 演算生成虛擬指令。^[5] Qi 編譯器將 AUM 指令對映到 Common Lisp，然後 Lisp 編譯器根據 Lisp 平臺將其編譯為位元組碼或機器碼。Qi 環境還包括一個編譯器編譯器 Qi-YACC，它用於 Qi 的編碼中，以處理 Qi 程式碼的解析和讀取。因此，Qi 除了幾個 Common Lisp 函式外，基本上是用它自己啟動或編寫的。

開發

截至 2009 年 1 月，Qi 自 2005 年 4 月首次釋出（6.1 版）以來已更新過多次，當前版本為 Qi II 1.07，於 2009 年 7 月釋出，在 CLISP、CMU Common Lisp、Allegro Common Lisp 和 Steel Bank Common Lisp (SBCL) 平臺上的 Windows 和 Linux 下執行。

Qi II 在原始 Qi 的基礎上包含了以下改進（引述自 Lambda Associates 的 Qi II What's New 頁面，並略作修改）

從頭開始對 Qi 進行完全重新實現。
新許可證。
型別安全的按需延遲評估。
改進的可程式設計語法。
利用型別資訊的 4 倍速編譯器。
與 Common Lisp 的整合得到改進。
在 LispWorks 下執行。
常用函式被設定為多引數函式。
與 Prolog 的連線得到改進。
用於將推演推理嵌入 Qi 函式中的規則閉包。
對依賴型別的處理得到改進。
一個型別安全的類系統，位於一個庫中，以及 Qi 中的函數語言程式設計（第二版）。
在 Qi 中的函數語言程式設計（第二版）中進行了完整的文件記錄。

在此之前，一個早期的版本 9.0 結合了一個可選的分解程式碼編譯器 (Turbo-E) 用於最佳化模式匹配。在與多個 Lisp 程式和 Objective Caml 進行的比較測試中，Qi 9.0 的速度與最快的、經過大量手動最佳化的 Lisp 版本相當。一個包含嵌入到 Qi 中的型別安全版本的 Tcl/Tk 的版本（Qi/Tk）於 2009 年 3 月釋出。

2010 年 1 月，宣佈了 Qi II 的繼任版本，旨在實現 Tarver 講座中的許多想法。新版本旨在在 Common Lisp、Clojure 和 Python 下執行，也針對 Dalvik 虛擬機器。貢獻者包括 Mark Tarver 博士、Google 的 Carl Shapiro 和 Stefan Tampe。

或者，Qi 中提出的想法的開發人員和支持者已經為 Qi 想出了一個繼任者，稱為 Shen (Programming Language)^[6]。Shen 是一種比 Qi 更緊湊的語言，儘管它與 Qi 大致相容。因此，Qi 的進一步開發可能會停滯不前 ^[7]，這意味著會投入更多精力在 Shen 上。

核心語言

Qi 核心語言是對 Lisp 語言的簡化。函式以字首形式編寫。符號、變數、布林值、數字、字串和字元在頂層鍵入時都是自評估的。以下是一些示例。

以下是 Qi 中傳統的 Hello world 程式

(output "Hello, world~%")

列表是用 [ .... ] 構建的，用空格分隔列表的元素。

[76 trombones]

使用模式匹配的階乘函式

(define factorial
0 -> 1
N -> (* N (factorial (- N 1))))

Qi 中將輸入乘以 2 的 lambda 函式。

(/. X (* X 2))

使用模式匹配對列表進行操作的成員資格函式。（Qi 在很大程度上遵循愛丁堡 [Prolog] 語法約定進行匹配（即變數以大寫字母開頭），但使用空格而不是逗號來分隔專案。）

(define member
_ [] -> false
X [X | _] -> true
X [_ | Y] -> (member X Y))

使用守衛查詢列表中第一個大於 N 的數字的函式。

(define find_greater
N [] -> (error "no number greater than ~A.~%" N)
N [M | _] -> M where (> M N)
N [_ | Ns] -> (find_greater N Ns))

型別檢查

Qi 中的靜態型別是可選的，可以透過 (tc +) 啟用，透過 (tc -) 停用。型別系統識別符號、變數、字串、布林值、數字和字元作為原始型別。原始型別運算子是 list、* (product)、--> 和 array。以下是一些示例

(3-) (tc +)
true

(4+) hello
hello : symbol

(5+) "hello"
"hello" : string

(6+) 686.8
686.8 : number

(7+) #\z
#\z : character

(8+) true
true : boolean

(9+) (@p 1 a)
(@p 1 a) : (number * symbol)

(10+) [1 2 | [3]]
[1 2 3] : (list number)

(11+) (* 8)
#<CLOSURE :LAMBDA [X4] [* X3 X4]> : (number --> number)

(12+) X
X : variable

函式透過 Hope 顯式型別化。[A] 是型別 (list A) 的可接受縮寫。以下是在 Qi 中 member 的多型別簽名。

(define member
{A --> [A] --> boolean}
_ [] -> false
X [X | _] -> true
X [_ | Y] -> (member X Y))

使用者定義的具體型別在 Qi 推演演算中定義。Qi 推演演算使用單結論形式。推演規則具有以下形式

<side conditions>
S₁;
.
.
.
S_n;
____
S₀;

其中 S₀,...,S_n 是推演模式。請注意，S₁, ...,S_n 可能為空。

Qi 中的邊條件要麼是 (a) 布林測試，要麼是 (b) 區域性賦值。以下是一些示例；第一個使用布林邊條件來定義一個列舉型別 'fruit'，其中 'apples'、'pears' 和 'oranges' 是唯一的成員。

(7+)(datatype fruit

if (element? F [apples pears oranges])
______________________________________
F : fruit;)
fruit : unit

(8+) apples : fruit
apples : fruit

(9+) plums : fruit
error: type error

這裡定義了一個型別 'alphanum'，它是符號和數字型別的並集。

(10+) (datatype alphanum

X : number;
___________
X : alphanum;

X : symbol;
___________
X : alphanum;)
alphanum : unit

(11+) [76 trombones]
[76 trombones] : (list alphanum)

這是一個在型別中使用區域性賦值（相當愚蠢）的示例。

(12+) (datatype ordering

if (number? X)
if (number? Y)
let Z (* X 2)
if (= Y Z)
__________________
[X Y] : ordering;)
ordering : unit

(13+) [2 3] : ordering
error: type failure

(14+) [2 4] : ordering
[2 4] : ordering

最後，一個更有趣的二進位制數字遞迴型別。

(15+) (datatype binary

if (element? X [0 1])
_____________
X : zero-or-one;

X : zero-or-one;
__________________
[X] : binary;

X : zero-or-one; Y : binary;
____________________________
[X | Y] : binary;

X : zero-or-one, [Y | Z] : binary >> P;
___________________________________________
[X Y | Z] : binary >> P;)
binary

(16+) (define complement
\calculates the complement of a binary number\
{binary --> binary}
[0] -> [1]
[1] -> [0]
[1 N | X] -> [0 | (complement [N | X])]
[0 N | X] -> [1 | (complement [N | X])])
complement : (binary --> binary)

(3+) (complement [0 1 0 1])
[1 0 1 0] : binary

Qi Prolog

Qi Prolog 是一個用 Qi 實現的 Prolog 版本，使用標準的 Edinburgh 語法，將 Prolog 程式嵌入到字串中。這是一個 Qi Prolog 的基本示例。

(m-prolog
"dog(snoopy).
man(socrates).
man(plato).
mortal(X) :- man(X).")

這是向 Prolog 資料庫提問的方法。

(prolog? (man plato))
(prolog? (man snoopy))
(prolog? (dog X))
(prolog? (man M))

這是愛因斯坦的謎題在 Qi Prolog 中的實現。在 2.6 GHz Intel 機器上的 CMU Lisp 上，Qi Prolog 在 0.24 秒內解決了 (ask [einsteins_riddle M])（M = 德國）（300 KLIPS）。

(m-prolog

"einsteins_riddle(Fish_Owner) :- einstein(Houses, Fish_Owner).

einstein(Houses, Fish_Owner) :-
=(Houses, house, norwegian, _, [house, _, _, _, milk, _], _, _]),
member([house, brit, _, _, _, red], Houses),
member([house, swede, dog, _, _, _], Houses),
member([house, dane, _, _, tea, _], Houses),
iright([house, _, _, _, _, green], [house, _, _, _, _, white], Houses),
member([house, _, _, _, coffee, green], Houses),
member([house, _, bird, pallmall, _, _], Houses),
member([house, _, _, dunhill, _, yellow], Houses),
next_to([house, _, _, dunhill, _, _], [house, _, horse, _, _, _], Houses),
member([house, _, _, _, milk, _], Houses),
next_to([house, _, _, marlboro, _, _], [house, _, cat, _, _, _], Houses),
next_to([house, _, _, marlboro, _, _], [house, _, _, _, water, _], Houses),
member([house, _, _, winfield, beer, _], Houses),
member([house, German, _, rothmans, _, _], Houses),
next_to([house, norwegian, _, _, _, _], [house, _, _, _, _, blue], Houses),
member([house, Fish_Owner, fish, _, _, _], Houses).

member(X,[X | _]).
member(X,[_ | Z]) :- member(X,Z).

next_to(X, Y, List) :- iright(X, Y, List).
next_to(X, Y, List) :- iright(Y, X, List).

iright(L, R, [L | [R | _]]).
iright(L, R, [_ | Rest]) :- iright(L, R, Rest).")

Qi Prolog 包含一個用於呼叫 Qi 函式的介面，以及類似於 DEC-10 Prolog 的模式宣告可能性。

Qi YACC

Qi YACC 是一個基於自上而下遞迴下降解析策略的無型別編譯器編譯器。它源於 TDPL（自上而下解析語言），是 Qi 中許多內建解析的基礎。Qi YACC 直接將 Backus–Naur 形式程式碼作為虛擬碼。

<sentence> := <assignment> | <goto>
<assignment> := goto <symbol>

變成

(defcc <sentence>
<assignment>;
<goto>;)

(defcc <assignment>
goto <symbol>;)

以下是一個 Qi-YACC 程式，它對 { ... } 中出現的任何輸入進行括號。

(2-) (defcc <paren>
{ <paren> } <paren1> := [<paren> | <paren1>];
<token> <paren> := [<token> | <paren>];
<e> := [];)
<paren>

(3-) (defcc <paren1>
<paren>;)
<paren1>

(4-)(defcc <token>
-*- := (if (element? -*- [{ }]) #\Escape -*-);)
<token>

(5-) (compile <paren> [{ a { b } } c])
[[a [b]] c]

Qi-YACC 在主頁上進行了更詳細的討論（見外部連結）。

參考資料

外部連結

Lambda Associates 的官方網站
Qi 有自己的 Google 論壇
Qi 原始碼也託管在 Google 程式碼專案託管上
程式設計功夫 Qi 教學文章的部落格

[1] 許可證

[2] 所有筆記來自 Mark Tarver 的講座“面向 21 世紀的 Lisp”。

[3] Qi、Lisp 和 Ocaml 比較

[4] Mark Tarver，《Qi 函數語言程式設計》第二版

[5] 另見 Prolog#實現技術

[6] Shen 語言

[7] Shen 在 45 個基本指令下執行，但比 Qi 更強大。

[1]

[2]

[3]

[4]

[5]

[6]

[7]