真正最小的口齿不清
要使一种语言成为图灵完备且是 lisp 变体，所需的最小原语集是什么？
看起来像 car、cdr 和一些流量控制以及 REPL 的东西就足够了。如果有这样的清单就好了。
假设只有 3 种数据类型：整数、符号和列表。（就像 picolisp 中一样）
What is the minimum set of primitives required such that a language is Turing complete and a lisp variant?
Seems like car, cdr and some flow control and something for REPL is enough. It be nice if there is such list.
Assume there are only 3 types of data, integers, symbols and lists.(like in picolisp)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
lambda 演算是图灵完备的。它有一个原语 - lambda。将其转换为 Lisp 语法非常简单。
The lambda calculus is turing complete. It has one primitive - the lambda. Translating that to a lisp syntax is pretty trivial.
Lisp FAQ 对此进行了很好的讨论。这取决于您对基元的选择。 McCarthy原来的《LISP 1.5程序员手册》做到了，用了五个函数：CAR、CDR、CONS、EQ和ATOM。
There's a good discussion of this in the Lisp FAQ. It depends on your choice of primitives. McCarthy's original "LISP 1.5 Programmer's Manual" did it with five functions: CAR, CDR, CONS, EQ, and ATOM.
我相信最小集是约翰·麦卡锡在原始论文中发表的内容。
Lisp 的根源。
代码。
I believe the minimum set is what John McCarthy published in the original paper.
The Roots of Lisp.
The code.
真正了解这一点的最佳方法是实施它。我用了 3 个夏天的时间创建了 Zozotez，它是一个运行在 Brainfuck。
我试图找出我需要的东西，在论坛上你会发现一个线程，上面写着 你只需要 lambda。因此，如果你愿意的话，你可以用 lambda 演算创建一个完整的 LISP。我发现它很有趣，但如果你想要一些最终会产生副作用并且在现实世界中有效的东西，那么这几乎不是一个可行的方法。
对于图灵完备的 LISP，我使用了 Paul Grahams 对 McCarthy 论文的解释，你真正需要的是：
那就是 10。除此之外，要拥有一个可以测试的实现，而不仅仅是在绘图板上：
那就是 12。在我的 Zozotez 我还实现了
set和flambda（匿名宏，如 lambda）。我可以给它提供一个实现任何动态绑定 Lisp（Elisp、picoLisp）的库，但文件 I/O 除外（因为底层 BF 除了 stdin/stdout 之外不支持它）。我建议任何人都用
LISP和（不是 LISP）实现 LISP1 解释器，以充分理解语言是如何实现的。 LISP 的语法非常简单，因此它是一个很好的起点。对于所有其他编程语言，实现解释器的方式非常相似。例如。在 SICP 视频中，向导为一种逻辑语言，但其结构和实现方式与 Lisp 解释器非常相似，尽管这种语言与 Lisp 完全不同。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 if 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
setandflambda(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
LISPand(not LISP), to fully understand how a language is implemented. LISP has a very simple syntax so it's a good starting point. For all other programming languages how you implement an interpreter is very similar. Eg. in the SICP videos the wizards make an interpreter for a logical language, but the structure and how to implement it is very similar to a lisp interpreter even though this language is completely different than Lisp.