构建一台Lisp机器需要多少个原语?十、七或五?

见 this other question 从PaulGraham的7个原语集构造宏。

基本谓词/f-函数

McCarthy 的 初等S-函数和谓词 是:

1. atom

   这是必要的,因为car和cdr只是为列表定义的,这意味着如果你给出了 car 原子

2. eq

   用于测试原子间的均等性。

3. 汽车

   返回cons单元的前半部分(地址)。(地址寄存器的内容)。

4. cdr

   返回cons单元的后半部分(减量)。(减量登记册的内容)。

5. cons

   用于生成一个新的cons单元格,其中地址的一半包含cons的第一个参数,而递减的一半包含第二个参数。

将其捆绑在一起:S-功能

然后,他继续添加到他的基本符号中,以便能够编写他所称的S函数:

1. quote

   表示一个表达式而不计算它。

2. cond

   与前面描述的谓词一起使用的基本条件。

3. lambda

   表示一个函数。

4. label

   虽然他不需要这个来递归,但他可能不知道 Y-Combinator ( according to Paul Graham ,为了方便起见,他添加了这个函数,并启用了简单的递归。

所以你可以看到他实际上为他的Lisp机器定义了9个基本的“操作符”。在之前对另一个问题的回答中,我解释了你如何 represent and operate on numbers 有了这个系统。

但这个问题的答案实际上取决于你想从Lisp机器中得到什么。你可以实现一个没有 标签 函数,因为您可以简单地在功能上组合所有内容,并通过应用Y组合器获得递归。

原子 如果定义了 汽车 原子返回操作 NIL .

你基本上可以使用麦卡锡的Lisp机器,其中有7个定义了原语,但是你可以表面上定义一个更简洁的版本,这取决于你想给自己造成多大的不便。我很喜欢他的机器,或者像Clojure这样的新语言中的许多原语。

要真正了解这一点,最好的方法就是实现它。我用3个夏天创造 Zozotez 这是麦卡蒂式的口齿不清 Brainfuck .

我试着找出我需要什么,在一个论坛上,你会找到一条线索,上面写着 You only need lambda. 因此,你可以在lambda微积分中做一个完整的Lisp。我觉得这很有趣,但如果你想要一些最终会产生副作用并在现实世界中发挥作用的东西,这很难做到。

对于图灵完整的Lisp,我使用 Paul Grahams explanation of McCarthy's paper 你真正需要的是:

• 符号评估
• 特殊格式报价
• 特殊形式if(或cond)
• 特殊形式lambda(类似于引号)
• 函数方程
• 功能原子
• 函数不等式
• 功能车
• 函数CDR
• 功能调度(列表lambda)

这是10。除此之外,要有一个可以测试的实现,而不仅仅是在绘图板上:

• 函数读取
• 函数写入

这是12。在我的 佐佐特兹 我也暗示了set和flambda(匿名宏,比如lambda)。我可以给它一个实现任何动态绑定lisp(elisp,picolisp)的库,但文件I/O除外(因为底层bf除了stdin/stdout之外不支持它)。

我建议任何人在lisp和(而不是lisp)中实现lisp1解释器,以完全理解语言是如何实现的。Lisp有一个非常简单的语法,因此它是解析器的良好起点。我目前正在开发一个用不同目标编写的方案编译器(就像斯大林是针对目标C的),希望BF是其中之一。

McCarthy使用了七个运算符来定义原始Lisp: quote , atom , eq , car , cdr , cons 和 cond . This article 回过头来。

This 常见问题解答:

没有单一的“最佳”最小基元集;这一切都取决于 实施。例如,即使是像数字这样基本的东西 不需要是原始的,并且可以表示为列表。一种可能 一组原语可能包括car、cdr和cons,用于操作 s-表达式,读取并打印s-表达式的输入/输出 申请和评估口译员的胆量。但你可能会 要为函数添加lambda,为相等添加eq,为 条件,设置为赋值,定义为defun。引用 可能也能派上用场。

来自卡内基甜瓜网站计算机科学学院。

Paul Graham使用 seven .

在麦卡锡的Lisp微手册中,他使用 ten .

你 just need an x86 MOV instruction .

“m/o/vfuscator(简称“o”,听起来像“mobfuscator”)将程序编译成“mov”指令,而只编译“mov”指令。算术、比较、跳转、函数调用以及程序所需的所有其他操作都是通过mov操作执行的;没有自修改代码、没有传输触发计算,也没有其他形式的非mov欺骗。”

不过,说真的,这些原语不会实现Lisp机器。机器需要I/O和垃圾收集等设施。更不用说函数调用机制了!好的,您有七个基本体,它们是函数。机器如何调用函数?

对这些原语的正确理解是 暴露 指令集 通用图灵机 . 因为这些指令是“口齿不清”,我们偷偷地称之为“口齿不清机器”。“通用”是指机器是可编程的:在通用图灵机上应用一些组合指令,我们可以实例化任何图灵机。但到目前为止,所有这些都是纯粹的数学构造。

为了实际地模拟这个utm实现它的物理特性,以便在计算机上进行探索,我们需要一台机器,它为我们提供了一种方法来实际地输入那些从这七个lisp指令组合中创建图灵机的形式。我们还需要某种形式的输出;机器至少能够告诉我们“是”、“否”或“等等,我还在运行”。

换言之,这七条指令实际工作的唯一方法是将它们托管在提供环境的大型机器中。

还要注意,Graham的七个原语对数字没有明确的支持,因此您必须用函数构建它们(“教堂数字”技术)。没有生产Lisp实现能做这样一件疯狂的事情。