¿Se puede implementar cualquier función LISP pura usando las diez primitivas? (es decir, no hay predicados tipo)

Question

Este sitio hace la siguiente afirmación: 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.

Mi pregunta es - ¿puede realmente hacer esto sin predicados de tipo tales como numberp? Seguramente hay un punto al escribir una función de nivel superior que necesita para hacer una operación numérica, que las primitivas anteriores no permiten.

Answer 1

Algunos números pueden ser representados con solo esos primitivos, es simplemente incómodo y difícil de conceptualizar la primera vez que lo ves.

De forma similar a cómo se representan los números naturales con conjuntos que aumentan de tamaño, se pueden simular en Lisp como células cons anidadas.

Cero sería la lista vacía, o (). Una sería la celda de cons de singleton, o (() .()). Dos serían uno más uno, o el sucesor de uno, donde definimos el sucesor de x como (cons() x), que es, por supuesto, (() . (() .())). Si acepta el Infinity Axiom (y algunos más, pero principalmente el Infinity Axiom para nuestros propósitos hasta el momento), e ignora las limitaciones de memoria de las computadoras reales, esto puede representar con precisión todos los números naturales.

Es bastante fácil extender esto para representar todos los enteros y luego los racionales [1], pero representar los reales en esta notación sería (creo) imposible. Afortunadamente, esto no amortigua nuestra diversión, ya que no podemos representar todos los reales en nuestras computadoras de todos modos; nos arreglamos con carrozas y dobles. Entonces nuestra representación es igual de poderosa.

En cierto modo, 1 es solo azúcar sintáctica para (() .()).

¡Hurra para la teoría de conjuntos! ¡Hurra por Lisp!

EDITAR Ah, para cualquier aclaración, permítanme hablar a su pregunta de predicados de tipo, aunque en este punto podría ser clara. Como sus números tienen una forma distinta, puede probar estas listas vinculadas con una función de su propia creación que evalúa esta estructura en particular. Mi Scheme ya no es lo suficientemente bueno como para escribirlo en Scheme, pero puedo intentarlo en Clojure.

Independientemente, puede estar diciendo que podría dar falsos positivos: tal vez simplemente está tratando de representar conjuntos y termina teniendo la misma estructura que un número en este sistema. A eso respondo: bueno, en ese caso, usted do de hecho tiene un número.

Así que pueden ver, aquí tenemos una representación bastante decente de los números, aparte de la cantidad de memoria que ocupan (no es nuestra preocupación) y qué tan feos se ven cuando se imprimen en el REPL (también, no es nuestra preocupación) y cuán ineficiente será operar sobre ellos (por ejemplo, tenemos que definir nuestra suma, etc., en términos de operaciones de lista: lenta y un poco complicada.) Pero ninguno de estos es una preocupación: la velocidad realmente debería y podría depender de los detalles de implementación, no lo que estás haciendo es el lenguaje.

Así que aquí, en Clojure (pero usando solo las cosas a las que básicamente tenemos acceso en nuestro sencillo Lisp, es numberp. (Espero, no dudes en corregirme, estoy atontado como el infierno etc. excusas, etc.)

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

[1] En el caso de los números enteros, representélos como las células contra de los productos naturales. Deje que el primer elemento en la celda cons sea la porción "negativa" del entero, y el segundo elemento sea la porción "positiva" del entero. De esta forma, -2 puede representarse como (2, 0) o (4, 2) o (5, 3) etc. Para los racionales, que se los represente como celdas cons de los enteros: p. (-2, 3) etc. Esto nos da la posibilidad de tener la misma estructura de datos representando el mismo número: sin embargo, esto puede remediarse escribiendo funciones que prueben dos números para ver si son equivalentes: nosotros definiríamos estas funciones en términos de las relaciones de equivalencia ya existentes que la teoría de conjuntos nos ofrece. Cosas divertidas :)