8

语言是图灵完备和 lisp 变体所需的最小原语集是多少？

似乎 car、cdr 和一些流控制以及 REPL 的东西就足够了。如果有这样的清单就好了。

假设只有 3 种类型的数据，整数、符号和列表。（就像在 picolisp 中一样）

4

4 回答 4

12

lambda演算已经完成。它有一个原语——lambda。将其转换为 lisp 语法非常简单。

于 2010-04-28T17:10:32.260 回答
6

在Lisp FAQ中有很好的讨论。这取决于您选择的原语。McCarthy 的原版《LISP 1.5 程序员手册》做到了五个功能：CAR、CDR、CONS、EQ 和 ATOM。

于 2010-04-28T17:17:23.063 回答
5

我相信最小集是约翰麦卡锡在原始论文中发表的。

Lisp 的根源。

代码。

于 2010-04-28T17:17:18.073 回答
2

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

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

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

  • 符号评估
  • 特殊形式报价
  • 特殊形式 if (或 cond)
  • 特殊形式 lambda（类似于引用）
  • 功能当量
  • 功能原子
  • 功能缺点
  • 功能车
  • 函数 cdr
  • function-dispatch（基本上应用但实际上并未暴露给系统，因此它处理第一个元素是函数的列表）

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

  • 函数读取
  • 函数写入

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

LISP我建议任何人在和中都实现 LISP1 解释器，(not LISP)以完全理解一种语言是如何实现的。LISP 的语法非常简单，因此它是一个很好的起点。对于所有其他编程语言，您实现解释器的方式非常相似。例如。在SICP 视频中，向导为逻辑语言制作解释器，但结构和实现方式与 lisp 解释器非常相似，尽管这种语言与 Lisp 完全不同。

于 2016-02-28T17:52:59.230 回答