80

在这个网站上，他们说有 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）

4

6 回答 6

58

基本谓词/F 函数

McCarthy的基本 S 函数和谓词是：

  1. atom

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

  2. eq

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

  3. car

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

  4. cdr

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

  5. cons

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

将其捆绑在一起：S-Functions

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

  1. quote

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

  2. cond

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

  3. lambda

    表示一个函数。

  4. label

    虽然他不需要这个来进行递归，但他可能不知道Y-Combinator（根据 Paul Graham的说法），他添加这个是为了方便并实现简单的递归。

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

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

atomcar如果您将原子上的操作定义为 return ，则可能会被丢弃NIL。

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

于 2010-08-14T16:39:12.367 回答
15

真正了解这一点的最好方法是实现它。我用了 3 个夏天创建了 Zozotez ，这是一个在Brainfuck上运行的 McCarty 式 LISP 。

我试图找出我需要什么，在一个论坛上你会发现一个帖子说你只需要 lambda。因此，你可以在我想要的 lambda 演算中制作一个完整的 LISP。我觉得它很有趣，但如果你想要一些最终会产生副作用并在现实世界中起作用的东西，这几乎不是一条路。

对于图灵完备的 LISP，我使用了Paul Grahams 对 McCarthy 论文的解释，而您真正需要的是：

  • 符号评估
  • 特殊形式报价
  • 特殊形式 if (或 cond)
  • 特殊形式 lambda（类似于引用）
  • 功能当量
  • 功能原子
  • 功能缺点
  • 功能车
  • 函数 cdr
  • 函数调度 (list-lambda)

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

  • 函数读取
  • 函数写入

就是12。在我的Zozotez 中，我也实现了 set 和 flambda（匿名宏，如 lambda）。我可以为它提供一个实现任何动态绑定 lisp（Elisp、picoLisp）的库，文件 I/O 除外（因为除了 stdin/stdout 之外，底层 BF 不支持它）。

我建议任何人在 LISP 和（不是 LISP）中都实现 LISP1 解释器，以完全理解一种语言是如何实现的。LISP 的语法非常简单，因此它是解析器的一个很好的起点。我目前正在研究一个用不同目标的方案编写的方案编译器（比如斯大林是针对目标C的），希望BF是其中之一。

于 2013-02-28T22:13:14.717 回答
10

McCarthy 使用七个运算符来定义原始 Lisp：quote、atom、eq、car、cdr和。这篇文章追溯了他的脚步。conscond

于 2010-08-14T10:21:24.233 回答
8

此常见问题解答指出：

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

这来自卡内基梅隆大学计算机科学学院的网站。

于 2010-08-14T07:48:53.160 回答
3

您只需要一条 x86MOV指令。

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

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

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

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

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

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

于 2017-08-06T15:05:13.030 回答
2

Paul Graham 使用7实现 eval 。

在 McCarthy 的 LISP 微型手册中，他使用 eval 实现了 ten。

于 2010-09-10T08:51:31.190 回答