News for hackers. Stuff that matters.
Re:What is the “minimal” set of primitives needed for a Lisp... by throwaway823472 on Monday December 08, 2014 @01:24AM (#8715213)
Wouldn't the minimal number be 1: NAND?
Re:What is the “minimal” set of primitives needed for a Lisp... by arethuza on Monday December 08, 2014 @04:14AM (#8715599)
Or if you want to build things on a purely functional basis all you need is S and K:

http://en.wikipedia.org/wiki/SKI_combinator_calculus

It's straightforward to convert lambda calculus expressions to to SK(I) combinators - the fact that you can get recursion using the Y combinator from SK is trivial to demonstrate but still surprises me!

Re:What is the “minimal” set of primitives needed for a Lisp... by ingenter on Monday December 08, 2014 @04:46AM (#8715683)
Then again, you could use a single universal combinator, http://en.wikipedia.org/wiki/Iota_and_Jot .

I find it weird that one can express all of combinator calculus using one function.

Re:What is the “minimal” set of primitives needed for a Lisp... by arethuza on Monday December 08, 2014 @08:33AM (#8716304)
Cool - I had heard that there was as a single combinator scheme but hadn't seen a definition of it before.

I had some fun as an undergraduate "compiling" proper code down to, in the worst cast, SK combinators and that was entertainingly inefficient (resulting in a need to become acquainted with implementing garbage collection). I suspect that U might be even more fun...

NB I did my SK stuff on a multi-user Unix minicomputer in '87/'88 so modern machines probably makes this a bit more realistic to play with.

Re:What is the “minimal” set of primitives needed for a Lisp... by rdc12 on Monday December 08, 2014 @03:00AM (#8715440)
Yes and No.

You could build the lisp primitives out of NAND, but you still need those primitives to build the lisp implementation, which is what the orignial question is. You could also write the lisp primitives without direct reference to NAND (excluding NAND inside of the CPU).