你能用十个原语实现任何纯LISP函数吗？ （即没有类型谓词） [英] Can you implement any pure LISP function using the ten primitives? (ie no type predicates)

问题描述

此网站提出以下声明：
http：//hyperpolyglot.wikidot。 com / lisp＃ten-primitives

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.

我的问题是 - 你真的可以这样做没有类型谓词，如 numberp ？当然，有一个点，当写一个更高级的函数，你需要做一个数字操作 - 上面的原语不允许。

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.

推荐答案

一些数字可以只用这些原语表示，它只是相当不方便，第一次看到它。

Some numbers can be represented with just those primitives, it's just rather inconvenient and difficult the conceptualize the first time you see it.

类似于自然数用大小增加的集合表示，它们可以在Lisp中模拟为嵌套cons单元格。

Similar to how the natural numbers are represented with sets increasing in size, they can be simulated in Lisp as nested cons cells.

零将是空列表，或（）。一个是单例cons单元格，或（（）。（））。两个是一个加一，或者一个的继承者，其中我们定义 x 的后继是（cons（）x）当然（（）。（）。（）））。如果你接受无限公理（以及更多，但主要是无限公理为我们的目的为止），并忽略真实的计算机的内存限制，这可以准确地表示所有的自然数。

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.

这很容易扩展到代表所有的整数，然后理性[1]，但代表在这个符号的reals将是（我认为）是不可能的。幸运的是，这不会削弱我们的乐趣，因为我们不能代表我们的计算机上的所有reals;我们做浮法和双打。

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.

在某种程度上， 1 只是语法糖（（）。（））。

In a way, 1 is just syntactic sugar for (() . ()).

集合理论的Hurray！ Hurray for Lisp！

Hurray for set theory! Hurray for Lisp!

EDIT 为了进一步澄清，让我解决你的类型谓词问题， 。因为你的数字有一个不同的形式，你可以测试这些链接列表与你自己的创造测试这个特定的结构的功能。我的计划不够好，不再写在Scheme，但我可以尝试在Clojure。

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.

所以你可以看到，我们有一个相当体面的数字表示，除了它们占用了多少内存（不是我们的关注）和他们看起来丑陋当打印在REPL（也不是我们的关注），以及如何无效地操作它们（例如，我们必须定义我们的添加等列表操作：慢和有点复杂。）但这些都不是关注：速度真的应该和可以依赖于实现细节，而不是你在做这个语言。

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.

在这里，在Clojure我们基本上可以访问在我们简单的Lisp， numberp （我希望;随时纠正我，我呻吟为地狱等借口等） p>

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.)

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

[1]对于整数，将它们表示为自然数的cons单元格。令cons单元中的第一个元素是整数的负部分，第二个元素是整数的正部分。以这种方式，-2可以表示为（2,0）或（4,2）或（5,3）等。对于有理数，让它们表示为整数的cons单元。 （-2，3）等。这使我们有可能具有相同的数据结构表示相同的数字：然而，这可以通过编写测试两个数字的函数来补救，看看它们是否是等价的：我们定义这些功能就已经存在的等价关系集理论提供给我们。有趣的东西：）

[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 :)

这篇关于你能用十个原语实现任何纯LISP函数吗？ （即没有类型谓词）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！