代码之家 › 专栏 › 技术社区 › hawkeye

你能用这十个原语实现任何纯LISP函数吗((无类型谓词)

predicate types lisp clojure function

hawkeye · 技术社区 · 14 年前

本网站声明如下: 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

1 回复 | 直到 14 年前

Isaac 14 年前

一些数字可以仅仅用这些原语来表示,当你第一次看到它的时候,概念化是相当不方便和困难的。

与自然数在集合大小增加时的表示方式类似,它们可以在Lisp中模拟为嵌套的cons单元。

() . 一个是独生子细胞,或者 (() . ()) 十成为 (cons () x) (() . (() . ())) . 如果你接受无限公理(还有一些,但目前为止我们的目的主要是无限公理),而忽略真实计算机的内存限制,这就可以准确地表示所有的自然数。

在某种程度上, 1 (() . ()) .

集合论万岁!口齿不清万岁!

编辑

不管怎样,你可能会说它可能会给你带来误报:也许你只是简单地试图表示集合,结果你在这个系统中拥有与数字相同的结构。对此,我回答说:既然如此,你事实上,我有一个数字。

所以你可以看到,我们这里有一个相当不错的数字表示,除了它们占用了多少内存(不是我们关心的)和它们在REPL上打印时看起来有多难看(还有,不是我们的问题)以及对它们进行操作的效率有多低(例如,我们必须用列表操作来定义加法等:速度慢而且有点复杂。)但这些都不是我们关心的问题:速度确实应该而且可能取决于实现细节,而不是语言的实现方式。

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

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