你能使用这十个原语实现任何纯 LISP 函数吗？ （即没有类型谓词）
本网站做出以下声明： http://hyperpolyglot.wikidot.com/lisp#ten-primitives
McCarthy introduced the ten primitives of lisp in 1960. All other pure lisp functions (i.e. all functions which don't do I/O or interact with the environment) can be implemented with these primitives. Thus, when implementing or porting lisp, these are the only functions which need to be implemented in a lower language. The way the non-primitives of lisp can be constructed from primitives is analogous to the way theorems can be proven from axioms in mathematics. The primitives are: atom, quote, eq, car, cdr, cons, cond, lambda, label, apply.
我的问题是 -如果没有诸如 numberp 这样的类型谓词，你真的能做到这一点吗？当然，在编写更高级别的函数时，您需要执行数字运算 - 上面的原语不允许这样做。
This site makes the following claim:
http://hyperpolyglot.wikidot.com/lisp#ten-primitives
McCarthy introduced the ten primitives of lisp in 1960. All other pure lisp functions (i.e. all functions which don't do I/O or interact with the environment) can be implemented with these primitives. Thus, when implementing or porting lisp, these are the only functions which need to be implemented in a lower language. The way the non-primitives of lisp can be constructed from primitives is analogous to the way theorems can be proven from axioms in mathematics. The primitives are: atom, quote, eq, car, cdr, cons, cond, lambda, label, apply.
My question is - can you really do this without type predicates such as numberp? Surely there is a point when writing a higher level function that you need to do a numeric operation - which the primitives above don't allow for.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
有些数字可以只用这些基元来表示，只是在您第一次看到它时很难概念化。
与自然数如何用大小增加的集合表示类似，它们可以在 Lisp 中模拟为嵌套 cons 单元。
零表示空列表，或
()。其中之一是单例 cons 单元，或(() . ())。二是一加一，或者一的后继，我们将 x 的后继定义为(cons () x)，这当然是(() . (() . ()))。如果您接受无穷大公理（以及其他一些，但到目前为止主要是用于我们目的的无穷大公理），并忽略真实计算机的内存限制，这可以准确地表示所有自然数。很容易扩展它来表示所有整数，然后表示有理数 [1]，但用这种表示法表示实数是（我认为）不可能的。幸运的是，这并没有影响我们的乐趣，因为无论如何我们都无法在计算机上表示所有实数；我们用花车和双打凑合。所以我们的代表权同样强大。
在某种程度上，
1只是(() . ())的语法糖。集合论万岁！ Lisp 万岁！
编辑 啊，为了进一步澄清，让我解决你的类型谓词问题，尽管此时它可能很清楚。由于您的数字具有不同的形式，因此您可以使用您自己创建的测试此特定结构的函数来测试这些链接列表。我的Scheme 还不够好，无法用Scheme 编写，但我可以尝试用Clojure 编写。
无论如何，您可能会说它可能会给您带来误报：也许您只是试图表示集合，但最终会得到与系统中的数字相同的结构。对此我的回答是：好吧，在这种情况下，你确实有一个号码。
所以你可以看到，我们在这里得到了相当不错的数字表示，除了它们占用了多少内存（不是我们关心的）以及它们在 REPL 上打印时看起来有多难看（也不是我们关心的）以及效率有多低之外它将对它们进行操作（例如，我们必须根据列表操作来定义我们的加法等：缓慢且有点复杂。）但这些都不是问题：速度确实应该并且可能取决于实现细节，不是你正在做的事情，而是语言。
所以在这里，在 Clojure 中（但只使用我们在简单的 Lisp 中基本上可以访问的东西，是
numberp。（我希望；请随意纠正我，我昏昏沉沉的，等等。借口等等.)[1] 对于整数，将它们表示为自然数的 cons 单元。令 cons 单元中的第一个元素为整数的“负”部分，第二个元素为整数的“正”部分。这样，-2 可以表示为 (2, 0) 或 (4, 2) 或 (5, 3) 等。对于有理数，让它们表示为整数的 cons 单元：例如 (-2, 3)这确实使我们有可能使用相同的数据结构来表示相同的数字：但是，这可以通过编写测试两个数字以查看它们是否相等的函数来解决：我们根据已经存在的等价关系集合论为我们提供了有趣的东西:)
Some numbers can be represented with just those primitives, it's just rather inconvenient and difficult the conceptualize the first time you see it.
Similar to how the natural numbers are represented with sets increasing in size, they can be simulated in Lisp as nested cons cells.
Zero would be the empty list, or
(). One would be the singleton cons cell, or(() . ()). Two would be one plus one, or the successor of one, where we define the successor of x to be(cons () x), which is of course(() . (() . ())). If you accept the Infinity Axiom (and a few more, but mostly the Infinity Axiom for our purposes so far), and ignore the memory limitations of real computers, this can accurately represent all the natural numbers.It's easy enough to extend this to represent all the integers and then the rationals [1], but representing the reals in this notation would be (I think) impossible. Fortunately, this doesn't dampen our fun, as we can't represent the all the reals on our computers anyway; we make do with floats and doubles. So our representation is just as powerful.
In a way,
1is just syntactic sugar for(() . ()).Hurray for set theory! Hurray for Lisp!
EDIT Ah, for further clarification, let me address your question of type predicates, though at this point it could be clear. Since your numbers have a distinct form, you can test these linked lists with a function of your own creation that tests for this particular structure. My Scheme isn't good enough anymore to write it in Scheme, but I can attempt to in Clojure.
Regardless, you may be saying that it could give you false positives: perhaps you're simply trying to represent sets and you end up having the same structure as a number in this system. To that I reply: well, in that case, you do in fact have a number.
So you can see, we've got a pretty decent representation of numbers here, aside from how much memory they take up (not our concern) and how ugly they look when printed at the REPL (also, not our concern) and how inefficient it will be to operate on them (e.g. we have to define our addition etc. in terms of list operations: slow and a bit complicated.) But none of these are out concern: the speed really should and could depend on the implementation details, not what you're doing this the language.
So here, in Clojure (but using only things we basically have access to in our simple Lisp, is
numberp. (I hope; feel free to correct me, I'm groggy as hell etc. excuses etc.)[1] For integers, represent them as cons cells of the naturals. Let the first element in the cons cell be the "negative" portion of the integer, and the second element be the "positive" portion of the integer. In this way, -2 can be represented as (2, 0) or (4, 2) or (5, 3) etc. For the rationals, let them be represented as cons cells of the integers: e.g. (-2, 3) etc. This does give us the possibility of having the same data structure representing the same number: however, this can be remedied by writing functions that test two numbers to see if they're equivalent: we'd define these functions in terms of the already-existing equivalence relations set theory offers us. Fun stuff :)