Can you implement any pure LISP function using the ten primitives? (ie no type predicates)

Question

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.

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.

Surely a numeric operation would 'interact with the environment'? — Lazarus
@Lazarus: They don't need to at all! Numbers can be constructed from those primitives quite elegantly. — Isaac
@Isaac: I'm ignorant of Lisp so thanks for that info and a great answer +1. — Lazarus
@Lazarus: No problem at all! Was fun to answer. I hope I didn't make any mistakes... — Isaac

Isaac Isaac · Accepted Answer · 2010-08-12T13:21:03

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

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

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.

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.

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

Hurray for set theory! Hurray for Lisp!

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.

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.

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

Can you implement any pure LISP function using the ten primitives? (ie no type predicates)

1 Answers