I discovered you can get eval to recognize natural numbers without introducing more primitives if you take the number in binary, enter it into a list, reverse it, and replace the 1's with t's and the 0's with nil's.
If you do it that way, you can binary right shift a number by consing a nil at the front, or binary left shift by taking the cdr. You can increment, decrement, add and subtract efficiently, too. Even take logarithms.
I had to use this to replace Lisp's namesake linked lists with another data structure that allowed many of the same niceties, but required some math, and therefore naturals, to find elements in the data structure. It was an interesting project. If you made it through the whole article, you might want to look:
> AM worked by generating and modifying short Lisp programs which were then interpreted as defining various mathematical concepts; for example, a program that tested equality between the length of two lists was considered to represent the concept of numerical equality, while a program that produced a list whose length was the product of the lengths of two other lists was interpreted as representing the concept of multiplication.
This is the old representation of numbers in raw Lisp, which uses lists of length n to represent the number n. Incrementing and decrementing are easy, you simply cons or cdr. Subtraction and addition are slower, though, and multiplication, division, left- and right-shifting are really slow.
Beyond that, I'm talking about creating natural numbers for internal use; no outside interpretation happens, as it does in Automated Mathematician. At no point does the computer output these natural numbers; it just uses them to navigate a data structure so it can run a REPL.
If you do it that way, you can binary right shift a number by consing a nil at the front, or binary left shift by taking the cdr. You can increment, decrement, add and subtract efficiently, too. Even take logarithms.
I had to use this to replace Lisp's namesake linked lists with another data structure that allowed many of the same niceties, but required some math, and therefore naturals, to find elements in the data structure. It was an interesting project. If you made it through the whole article, you might want to look:
http://dcussen.posterous.com/lisp-in-lisp-without-linked-lis...