构建一台 LISP 机器需要多少原语？十个、七个还是五个？

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

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

Stevey 认为有七个（或五个）：

这是 LISP 思想的纯粹性的一部分：你只需要七个（或者是 它有五个？）构建完整机器的原语。http://steve-yegge.blogspot.com/2006/04/lisp-is-not-acceptable-lisp.html http://steve-yegge.blogspot.com/2006/04/lisp-is-not-acceptable-lisp.html

构建 LISP 机器（即可以在 LISP 代码上运行 eval/value 函数的机器）的最小原语数量是多少？ （它们是哪些？）

（我可以理解你可以没有atom, label and apply)

基本谓词/F 函数

McCarthy http://www-formal.stanford.edu/jmc/recursive.pdf's 基本 S 函数和谓词 were:

1. atom

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

2. eq

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

3. car

   用于返回 cons 单元的前半部分（地址）。 （地址寄存器的内容）。

4. cdr

   用于返回 cons 单元的后半部分（递减）。 （减量寄存器的内容）。

5. cons

   用于创建新的 cons 单元，地址一半包含 cons 的第一个参数，减量一半包含第二个参数。

将其结合在一起：S-Functions

然后他继续添加他的基本符号，以便能够编写他所谓的 S-Functions：

1. quote

   表示一个表达式而不对其求值。

2. cond

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

3. lambda

   来表示一个函数。

4. label

   虽然他不需要这个来进行递归，但他可能不知道Y-组合器 https://en.wikipedia.org/wiki/Fixed-point_combinator#Fixed_point_combinators_in_lambda_calculus (根据保罗·格雷厄姆的说法 http://lib.store.yahoo.net/lib/paulgraham/jmc.ps），他添加这个是为了方便并且能够轻松递归。

所以你可以看到他实际上为他的 Lisp 机器定义了 9 个基本“操作符”。在之前对您另一个问题的回答中，我解释了如何数字的表示和运算 https://stackoverflow.com/questions/3467317/can-you-implement-any-pure-lisp-function-using-the-ten-primitives-ie-no-type-pr/3468060#3468060有了这个系统。

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

atom如果您定义了car对原子进行操作返回NIL.

您本质上可以拥有包含这 9 个已定义原语中的 7 个的 McCarthy 的 LISP 机器，但您表面上可以定义一个更简洁的版本，具体取决于您希望给自己带来多少不便。我非常喜欢他的机器，或者像 Clojure 这样的新语言中的许多原语。