构建LISP机器需要多少原语？十,七,五？

Question

在这个网站上,他们说有10个LISP原语.原语是:atom, quote, eq, car, cdr, cons, cond, lambda, label, apply.

http://hyperpolyglot.wikidot.com/lisp#ten-primitives

Stevey估计有七个(或五个):

它是LISP概念纯度的一部分:你只需要七个(或五个？)原语来构建整个机器. http://steve-yegge.blogspot.com/2006/04/lisp-is-not-acceptable-lisp.html

构建LISP机器的最小基元数是多少(即可以在LISP代码上运行eval/value函数的东西)？(他们是哪一个？)

(我明白你可以没有生活atom, label and apply)

Answer 1

基本谓词/ F函数

麦卡锡的基本S函数和谓词是:

1. atom

   这是必要的,因为汽车和cdr仅为列表定义,这意味着如果你给了car一个原子,你不能指望任何类型的答案来表明发生了什么.

2. eq

   用于测试原子之间的相等性

3. car

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

4. cdr

   用于返回cons单元的后半部分(减量).(减量登记的内容).

5. cons

   为了创建一个新的cons单元格,地址一半包含cons的第一个参数,而一半包含第二个参数.

把它绑在一起:S-Functions

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

1. quote

   表示表达式而不进行评估.

2. cond

   与先前描述的谓词一起使用的基本条件.

3. lambda

   表示功能.

4. label

   虽然他不需要这个用于递归,但他可能不知道Y-Combinator(根据Paul Graham的说法),他为方便起见添加了这个并且能够轻松递归.

所以你可以看到他实际上为他的Lisp机器定义了9个基本的"操作符".在之前对另一个问题的回答中,我解释了如何用这个系统表示和操作数字.

但这个问题的答案实际上取决于你想从Lisp机器中得到什么.你可以在没有label函数的情况下实现一个,因为你可以简单地在功能上组合所有东西,并通过应用Y-Combinator获得递归.

atom如果定义了car要返回的原子上的操作,则可以将其丢弃NIL.

你基本上可以拥有McCarthy的LISP机器,其中包含这9个定义的原语中的7个,但你可以表面上定义一个更简洁的版本,具体取决于你想给你自己造成多大的不便.我非常喜欢他的机器,或者像Clojure这样的新语言中的许多原语.

Answer 2

实际了解这一点的最好方法是实现它.我用3个夏天创造了Zozotez,这是一个在Brainfuck上运行的McCarty-ish LISP .

我试图找出我需要的东西,在论坛上你会发现一个帖子说你只需要lambda.因此,你可以在lambda演算中制作一个完整的LISP.我发现它很有趣,但如果你想要一些最终会产生副作用并且在现实世界中工作的东西,那么这种方法几乎不可能实现.

对于图灵完整的LISP,我使用了Paul Grahams对McCarthy论文的解释,你真正需要的是:

• 符号评价
• 特殊形式报价
• 特殊形式if(或cond)
• 特殊形式lambda(类似于引用)
• 功能方程
• 功能原子
• 功能缺点
• 功能车
• 功能cdr
• function-dispatch(list-lambda)

那就是10.除此之外,还有一个可以测试的实现,而不仅仅是在绘图板上:

• 功能阅读
• 功能写

多数民众赞成12.在我的Zozotez中,我也实现了set和flambda(匿名macroes,如lambda).我可以为它提供一个实现任何动态绑定lisp(Elisp,picoLisp)的库,但文件I/O除外(因为除了stdin/stdout之外,底层BF不支持它).

我建议任何人在LISP和(而不是LISP)中实现LISP1解释器,以完全理解语言的实现方式.LISP语法非常简单,因此它是解析器的一个很好的起点.我目前正在研究一个用不同目标编写的方案编译器(比如Stalin用于目标C),希望BF作为其中之一.

Answer 3

麦卡锡用七个运营商定义原始的Lisp: ,quote,atom,eq,,car 和.这篇文章回顾了他的步骤.cdrconscond

Answer 4

这个 faq说明:

没有单一的"最佳"基本原语集; 这一切都取决于实施.例如,即使像数字这样基本的东西也不必是原始的,并且可以表示为列表.一组可能的原语可能包括用于操纵S表达式的CAR,CDR和CONS,用于S表达式的输入/输出的READ和PRINT以及用于解释器的内容的APPLY和EVAL.但是,您可能希望为函数添加LAMBDA,为等式添加EQ,为条件添加COND,为赋值添加SET,为定义添加DEFUN.QUOTE也可以派上用场.

那来自计算机科学学院,Carnegie Melon网站.

Answer 5

请参阅另一个问题,从Paul Graham的7个原语集构造宏.

Answer 6

您只需要一条 x86MOV指令。

“M/o/Vfuscator（短‘o’，听起来像“mobfuscator”）将程序编译成“mov”指令，而且只有“mov”指令。算术、比较、跳转、函数调用以及程序所需的所有其他内容都是全部通过 mov 操作执行；没有自修改代码，没有传输触发的计算，也没有其他形式的非 mov 作弊。”

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

对这些原语的正确理解是它们公开了通用图灵机的指令集。因为这些指令是“Lisp”，所以由于口误（用 Lisp 说话），我们偷偷地称其为“Lisp 机器”。“通用”意味着机器是可编程的：通过一些应用于通用图灵机的组合指令，我们可以实例化任何图灵机。但到目前为止，所有这些都纯粹是数学构造。

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

换句话说，这七个指令实际上可以工作的唯一方法是将它们托管在提供环境的更大的机器中。

另请注意，格雷厄姆的七个基元没有对数字的明确支持，因此您必须用函数构建它们（“教堂数字”技术）。没有哪个 Lisp 生产实现能做出如此疯狂的事情。