本站声明如下: 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
),你真的能做到这一点吗?在编写更高级别的函数时,肯定有一点需要执行数字操作——上面的原语不允许这样做。
最佳答案
有些数字可以只用这些基元表示,只是在您第一次看到它时很难概念化。
类似于自然数用大小增加的集合表示的方式,它们可以在 Lisp 中模拟为嵌套的 cons 单元。
零将是空列表,或 ()
。一个是单例 cons 单元格,或 (() . ())
。二是一加一,或者说是一的后继,这里我们定义x的后继是(cons () x)
,当然是 (() . (() . ()))
。如果您接受无穷大公理(还有一些,但到目前为止我们的目的主要是无穷大公理),并且忽略真实计算机的内存限制,这可以准确地表示所有自然数。
将其扩展为表示所有整数然后表示有理数 [1] 很容易,但是(我认为)用这种表示法表示实数是不可能的。幸运的是,这并没有影响我们的乐趣,因为无论如何我们都无法在计算机上表示所有实数;我们将就着花车和 double 。所以我们的代表同样强大。
在某种程度上,1
只是(() . ())
的语法糖。
集合论万岁!为 Lisp 欢呼吧!
编辑 啊,为了进一步说明,让我来解决你的类型谓词问题,尽管此时它可能很清楚。由于您的数字具有不同的形式,因此您可以使用您自己创建的测试此特定结构的函数来测试这些链表。我的 Scheme 已经不够好,无法用 Scheme 编写,但我可以尝试在 Clojure 中编写。
无论如何,您可能会说它可能会给您带来误报:也许您只是想表示集合,但最终却与该系统中的数字具有相同的结构。对此我的回答是:好吧,在那种情况下,您确实实际上有一个数字。
所以你可以看到,除了它们占用多少内存(不是我们关心的)以及它们在 REPL 上打印时看起来有多难看(同样,这不是我们关心的),我们在这里有一个相当不错的数字表示以及对它们进行操作的效率有多低(例如,我们必须根据列表操作来定义我们的加法等:缓慢且有点复杂。)但这些都不是问题:速度确实应该并且可能取决于实现细节,而不是你在用这种语言做什么。
所以在这里,在 Clojure 中(但只使用我们在简单的 Lisp 中基本上可以访问的东西,是 numberp
。(我希望;随时纠正我,我昏昏沉沉的 hell 等. 借口等)
(defn numberp
[x]
(cond
(nil? x) true
(and (coll? x) (nil? (first x))) (numberp (second x))
:else false))
[1] 对于整数,将它们表示为自然数的cons cells。让 cons 单元格中的第一个元素是整数的“负”部分,第二个元素是整数的“正”部分。这样,-2 可以表示为 (2, 0) 或 (4, 2) 或 (5, 3) 等。对于有理数,让它们表示为整数的 cons 单元格:例如(-2, 3) 等。这确实让我们有可能使用相同的数据结构来表示相同的数字:但是,这可以通过编写测试两个数字的函数来解决,看看它们是否相等:我们定义这些函数根据已经存在的等价关系集合论为我们提供。有趣的东西:)
关于function - 你能用十个原语实现任何纯 LISP 函数吗? (即没有类型谓词),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3467317/