3 ms·

Wouldn't the minimal number be 1: NAND?

• rdc12 12y ago
  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).
• arethuza 12y ago
  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 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!
  • ingenter 12y ago
    Then again, you could use a single universal combinator, http://en.wikipedia.org/wiki/Iota_and_Jot http://en.wikipedia.org/wiki/Iota_and_Jot . I find it weird that one can express all of combinator calculus using one function.
    • arethuza 12y ago
      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.