构建一台 LISP 机器需要多少个原语？十个、七个还是五个？
在这个网站上，他们说有 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 和 apply 生活）
On this site they say there are 10 LISP primitives.
The primitives are: atom, quote, eq, car, cdr, cons, cond, lambda, label, apply.
http://hyperpolyglot.wikidot.com/lisp#ten-primitives
Stevey reckons there are seven (or five):
Its part of the purity of the idea of LISP: you only need the seven (or is
it five?) primitives to build the full machine.
http://steve-yegge.blogspot.com/2006/04/lisp-is-not-acceptable-lisp.html
What is the minimum number of primitives to build a LISP machine (ie something that can run an eval/value function on LISP code)? (And which ones are they?)
(I can understand you could live without atom, label and apply)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
基本谓词/F 函数
McCarthy 的基本 S 函数和谓词为：
atom这是必要的，因为 car 和 cdr 仅为列表定义，这意味着如果您给
car一个原子，您就不能指望任何类型的答案来指示发生了什么。eq用于测试原子之间的相等性。
汽车用于返回 cons 单元的前半部分（地址）。 （地址寄存器的内容）。
cdr用于返回 cons 单元的后半部分（递减）。 （减量寄存器的内容）。
缺点用于创建一个新的 cons 单元，地址一半包含 cons 的第一个参数，减量一半包含第二个参数。
将其结合在一起：S-Functions
然后他继续添加到他的基本符号中，以便能够编写他所谓的 S-functions：
quote表示一个表达式而不求值。
条件与前面描述的谓词一起使用的基本条件。
lambda表示一个函数。
标签虽然他不需要递归，但他可能不知道 Y -Combinator（根据 Paul Graham），他补充道这是为了方便并能够轻松递归。
所以你可以看到他实际上为他的 Lisp 机器定义了 9 个基本“操作符”。在之前对另一个问题的回答中，我解释了如何使用此系统表示数字并对其进行操作。
但这个问题的答案实际上取决于你想从你的 Lisp 机器中得到什么。您可以在没有
label函数的情况下实现一个函数，因为您可以简单地在功能上组合所有内容，并通过应用 Y-Combinator 获得递归。如果您在原子上定义了
car操作以返回NIL，则atom可能会被丢弃。您本质上可以拥有包含这 9 个已定义原语中的 7 个的 McCarthy 的 LISP 机器，但您表面上可以定义一个更简洁的版本，具体取决于您希望给自己带来多少不便。我非常喜欢他的机器，或者像 Clojure 这样的新语言中的许多原语。
Basic Predicates/F-functions
McCarthy's Elementary S-functions and Predicates were:
atomWhich was necessary because car and cdr are defined for lists only, which means you cannot count on any sort of answer to indicate what was happening if you gave
caran atom.eqFor testing equality between atoms.
carFor returning the first half (address) of the cons cell. (Contents of address register).
cdrFor returning the second half (decrement) of the cons cell. (Contents of decrement register).
consFor making a new cons cell, with the address half containing the first argument to cons, and the decrement half containing the second argument.
Tying it together: S-Functions
He then went on to add to his basic notation, to enable writing what he called S-functions:
quoteTo represent an expression without evaluating it.
condThe basic conditional to be used with the previously described predicates.
lambdaTo denote a function.
labelThough he didn't need this for recursion, he might not have known about the Y-Combinator (according to Paul Graham), he added this for convenience and to enable easy recursion.
So you can see he actually defined 9 basic "operators" for his Lisp machine. In a previous answer to another one of your questions, I explained how you could represent and operate on numbers with this system.
But the answer to this question really depends on what you want out of your Lisp machine. You could implement one without the
labelfunction, as you could simply functionally compose everything, and obtain recursion through applying the Y-Combinator.atomcould be discarded if you defined thecaroperation on atoms to returnNIL.You could essentially have McCarthy's LISP machine with 7 of these 9 defined primitives, but you could ostensibly define a more concise version depending on how much inconvenience you'd want to inflict on yourself. I like his machine quite fine, or the many primitives in the newer languages like Clojure.
真正了解这一点的最佳方法是实施它。我用了 3 个夏天的时间创建了 Zozotez，它是一个运行在 Brainfuck。
我试图找出我需要的东西，在论坛上你会发现一个线程，上面写着 你只需要 lambda。 因此，你可以用 lambda 演算创建一个完整的 LISP。我发现它很有趣，但如果你想要一些最终会产生副作用并且在现实世界中有效的东西，那么这几乎不是一个可行的方法。
对于图灵完备的 LISP，我使用了 Paul Grahams 对 McCarthy 论文的解释，你真正需要的是：
Thats 10. 除此之外，还有一个实现您可以测试而不仅仅是在绘图板上：
那就是 12。在我的 Zozotez 中，我实现了set 和 flambda（匿名宏，如 lambda）也是如此。我可以给它提供一个实现任何动态绑定 Lisp（Elisp、picoLisp）的库，但文件 I/O 除外（因为底层 BF 除了 stdin/stdout 之外不支持它）。
我建议任何人都在 LISP 和（不是 LISP）中实现 LISP1 解释器，以充分理解语言是如何实现的。 LISP 具有非常简单的语法，因此它是解析器的良好起点。我目前正在开发一个以具有不同目标的方案编写的方案编译器（例如斯大林针对目标 C），希望 BF 能够成为其中之一。
The best way to actually know this for sure is if you implement it. I used 3 summers to create Zozotez which is a McCarty-ish LISP running on Brainfuck.
I tried to find out what I needed and on a forum you'll find a thread that says You only need lambda. Thus, you can make a whole LISP in lambda calculus I you'd like. I found it interesting, but it's hardly the way to go if you want something that eventually has side effects and works in the real world.
For a Turing complete LISP I used Paul Grahams explanation of McCarthy's paper and all you really need is:
Thats 10. In addition to this, to have a implementation that you can test and not just on a drawing board:
Thats 12. In my Zozotez I implemeted set and flambda (anonymous macroes, like lambda) as well. I could feed it a library implementing any dynamic bound lisp (Elisp, picoLisp) with the exception of file I/O (because the underlying BF does not support it other than stdin/stdout).
I recommend anyone to implement a LISP1-interpreter in both LISP and (not LISP) to fully understand how a language is implemented. LISP has a very simple syntax so it's a good starting point for a parser. I'm currently working on a scheme compiler written in scheme with different targets (like Stalin is for target C), hopefully BF as one of them.
McCarthy 使用七个运算符来定义原始 Lisp：
quote、atom、eq、car、cdr、cons和cond。 这篇文章回顾了他的足迹。McCarthy used seven operators to define the original Lisp:
quote,atom,eq,car,cdr,consandcond. This article retraces his steps.此常见问题解答指出：
这来自卡内基梅隆大学计算机科学学院网站。
This faq states:
That comes from the School of Computer Science, Carnegie Melon website.
您只需要一条 x86
MOV指令。但说真的，这些原语不会实现 Lisp 机器。机器需要 I/O 和垃圾收集等设施。更不用说函数调用机制了！好的，您有七个原语，它们是函数。机器如何调用函数？
对这些原语的正确理解是，它们公开通用图灵机的指令集。因为这些指令是“Lisp”，所以由于口误（用 Lisp 说话），我们偷偷地称其为“Lisp 机器”。 “通用”意味着机器是可编程的：通过一些应用于通用图灵机的组合指令，我们可以实例化任何图灵机。但到目前为止，所有这些都纯粹是数学构造。
为了实际模拟这个 UTM——以物理方式实现它，以便在计算机上探索它，我们需要一台机器，它为我们提供一种方法来实际输入那些形式，这些形式根据这七个 Lisp 指令的组合创建图灵机。我们还需要某种形式的输出；机器至少能够告诉我们“是”、“否”或“等等，我还在运行”。
换句话说，这七个指令实际上可以工作的唯一方法是将它们托管在提供环境的更大的机器中。
另请注意，格雷厄姆的七个基元没有对数字的明确支持，因此您必须用函数构建它们（“教堂数字”技术）。没有哪个 Lisp 生产实现会做出如此疯狂的事情。
You just need an x86
MOVinstruction.Seriously though, these primitives will not implement a Lisp Machine. A machine needs facilities like I/O, and garbage collection. Not to mention a function calling mechanism! Okay, you have seven primitives which are functions. How does the machine call a function?
The proper understanding of what these primitives make possible is that they expose the instruction set of a Universal Turing Machine. Because those instructions are "Lispy", by a slip of the tongue (speaking with a Lisp) we sneakily call this a "Lisp Machine". "Universal" means that the machine is programmable: with some combination instructions applied to the Universal Turing Machine, we can instantiate any Turing Machine. But so far, all of that is purely a mathematical construct.
To actually simulate this UTM—realize it physically in order to explore it on a computer, we need a machine which provides for a way to us to actually input those forms which create Turing Machines from combinations of those seven Lisp instructions. And we also need some form of output; the machine as to at least be able to tell us "yes", "no", or "Wait, I'm still running".
In other words, the only way those seven instructions can practically work is if they are hosted in a larger machine which provides the environment.
Also note that Graham's seven primitives have no explicit support for numbers, so you would have to build them out of functions ("Church numerals" technique). No production Lisp implementation does such a crazy thing.
Paul Graham 使用 7 实现 eval。
在 McCarthy's Micro Manual for LISP 中，他使用 ten 实现了 eval。
Paul Graham implements eval using seven.
In McCarthy's Micro Manual for LISP he implements eval using ten.