你能用十个原语实现任何纯LISP函数吗？(即没有类型谓词)

Question

本网站提出以下声明: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吗？当然,编写更高级别的函数时需要进行数值运算 - 上面的原语不允许这样做.

Answer 1

有些数字只能用那些原语来表示,第一次看到它时,概念化是相当不方便和困难的.

类似于自然数用大小增加的集合来表示,它们可以在Lisp中作为嵌套的cons单元进行模拟.

零将是空列表,或().一个是单身的cons单元格,或者(() . ()).二是一加一,或一,我们定义的继任者的继任者X是(cons () x) ,这是当然的(() . (() . ())).如果您接受Infinity Axiom(以及目前为止我们的目的主要是Infinity Axiom),并忽略了真实计算机的内存限制,这可以准确地表示所有自然数.

很容易扩展它来表示所有整数然后是有理数[1],但用这种表示法表示实数将是(我认为)不可能.幸运的是,这并没有削弱我们的乐趣,因为我们无论如何也无法代表我们计算机上的所有实物; 我们用浮子和双打做.所以我们的表现同样强大.

在某种程度上,1只是语法糖(() . ()).

为理论而欢呼!为Lisp欢呼!

编辑啊,为了进一步说明,让我解决你的类型谓词的问题,虽然在这一点上它可以很清楚.由于您的数字具有不同的形式,因此您可以使用您自己的创建功能测试这些链接列表,以测试此特定结构.我的方案已不再适合在Scheme中编写,但我可以尝试在Clojure中.

无论如何,你可能会说它可能会给你误报:也许你只是试图表示集合,并且你最终拥有与这个系统中的数字相同的结构.对此我回答:嗯,在这种情况下,你确实有一个数字.

所以你可以看到,我们在这里有一个相当不错的数字表示,除了它们占用多少内存(不是我们的关注)以及它们在REPL上打印时看起来多么丑陋(也不是我们的关注)以及效率如何低它将对它们进行操作(例如,我们必须在列表操作方面定义我们的添加等:缓慢而且有点复杂.)但这些都不是关注的:速度真的应该并且可能取决于实现细节,不是你在做什么语言.

所以在这里,在Clojure中(但只使用我们在简单的Lisp中基本上可以访问的东西,是numberp.(我希望;随意纠正我,我是昏昏欲睡的等等等借口等)

(defn numberp 
    [x]
      (cond 
        (nil? x) true
        (and (coll? x) (nil? (first x))) (numberp (second x))
        :else false))

[1]对于整数,将它们表示为自然的利弊细胞.令cons单元中的第一个元素是整数的"负"部分,第二个元素是整数的"正"部分.这样,-2可以表示为(2,0)或(4,2)或(5,3)等.对于有理数,让它们表示为整数的cons单元格:例如(-2,3)这确实使我们可以使用相同的数据结构来表示相同的数字:但是,这可以通过编写测试两个数字的函数来解决,看看它们是否等价:我们根据这些函数来定义这些函数.已经存在的等价关系集理论为我们提供了.好玩的东西 :)