软件工程师手册/语言词典/Qi

Qi 是一种由 Mark Tarver 博士开发的功能性编程语言，于 2005 年 4 月推出。一个新版本在 2008 年 11 月重新实现并发布为 Qi II。第一个版本是免费软件，根据 GPL 许可。但是，由于 GPL 被认为对商业使用不友好， Qi II 可通过两种专有许可获得：一种用于个人和教育用途，另一种用于生产封闭源代码软件。

Qi是用Lisp编写的。它包含了现代函数式编程语言中的大多数常用功能，如模式匹配、柯里化、部分应用、守卫和（可选）静态类型检查。

L21 项目

Qi 是作为 L21 项目的一部分开发的，该项目旨在使 Lisp 现代化，以应对 21 世纪计算的挑战。在他的讲座中， Tarver 博士概述了一系列当前对 Lisp 的挑战，他认为这些挑战损害了该语言的更广泛使用。他特别指出了 Common Lisp 缺乏模式匹配、与 lambda 演算理论的不一致性（部分应用缺失）、过程性污染和缺乏静态类型。Tarver 认为，这些缺陷导致 Lisp 在大学水平上普遍被放弃作为教学工具，随之而来的是 Lisp 程序员毕业生的缺乏。Tarver 将这种对大学里教 Lisp 的缺乏支持描述为导致了一个“典型的恶性循环”，即少量精通 Lisp 的毕业生鼓励从使用 Lisp 程序员过渡，这反过来又助长了 Lisp 是一种正在消亡的语言的看法，并助长了 Lisp 教学的衰落。

在同一个讲座中，Tarver 建议，这个问题可以从行业端或大学端解决，但从行业端解决这个问题需要一个拥有大量资金投资 Lisp 的冠军。Tarver 反而建议从大学端解决这个问题，通过使 Common Lisp 现代化，使其在至少 25 年内“未来证明”。他描述的 Lisp 的充分现代化总结在十项要求中，Qi 是为了满足这些要求而设计的。解决方案应

1. 与 Lisp 兼容——作为 Lisp 最广泛使用的方言，解决方案应该用 Common Lisp 编写并在 Common Lisp 下运行。
2. 免费用于非商业和教育用途。
3. 紧凑——程序不应比用 Common Lisp 编写的相同程序更长。
4. 易于学习——语义和语法应该可以被孩子学习。
5. 高效——解决方案应该生成至少与手动编码的 Lisp 等效程序一样快的程序。在实践中，Qi 程序已被证明通常更快。
6. 具有现代函数式编程语言的特征。Tarver 博士将这些特征包括模式驱动的列表处理、静态类型、柯里化和部分应用。
7. 不只是 Haskell 或 ML 的克隆——这是“未来证明”解决方案的一部分。
8. 在计算上是充分的——这意味着该语言“足以满足当今程序员的需求”。Tarver 博士将“计算充分性”描述为“一个大而模糊的重要概念”，并认为这个概念的扩展随着时间的推移而改变。他认为 Common Lisp 由于缺乏对诸如外部语言接口和图形等功能的规范，在“计算上不充分”。Tarver 认为，Qi 本身还需要通过开发图形、Web 接口和外部语言处理的标准库来实现这个目标。
9. 可[元编程和可定制——用户应该可以自由地对语言的语法进行编程。为了实现这一点，Qi 对其所有语法都有 M 表达式和 S 表达式级别的语法，以及一个“eval”函数，将 M 表达式映射到 S 表达式；这使得在 Qi 中进行元编程比在 Lisp 中更容易。在定制方面，Qi 有一个显式的“sugar”关键字，允许用户对 Qi 阅读器进行编程以接受自定义语法。
10. 有充分的文档记录，在理论上是安全的——Qi 拥有完整的文档记录，并具有正式的正确性证明，并且有一本规范的教科书也在线上。

架构

Qi 利用推演演算的逻辑符号来定义类型。在 Qi 的解释下，这种类型符号实际上本身就是一个图灵完备语言。这种符号允许 Qi 为 Common Lisp 库分配可扩展的类型系统，被认为是该语言的一个非常强大的功能。

Qi 通过抽象统一机 (AUM) 将推演演算编译为 Qi Prolog（它被纳入 Qi 环境）。AUM 充当函数式编程的类似物，类似于 Warren 抽象机，从本质上是扩展的 lambda 演算生成虚拟指令。 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)。Shen 是一种比 Qi 更紧凑的语言，尽管它与 Qi 大致兼容。因此，Qi 的进一步开发可能会停滞不前 ，这意味着会投入更多精力在 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>
S1;
.
.
.
Sn;
____
S0;

其中 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 教学文章的博客