5 ms·
The struggle to understand what is a primitive has to take into account what the instruction set architecture (ISA) is for the machine that will be running the
by whitten 12y ago
The struggle to understand what is a primitive has to take into account what the instruction set architecture (ISA) is for the machine that will be running the system.
This article doesn't even consider the idea that the LISP may be running on any exotic hardware at all.
It might be instructive to look at the ISA for the Lisp Machine from the 1980s.
- rdc12 12y agoWhich is quite different to the theoretical minimum number which they are presumably looking at
- throwaway823472 12y agoWouldn't the minimal number be 1: NAND?
- rdc12 12y agoYes 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 agoOr 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 agoThen 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 agoCool - 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.
- Someone 12y agoWhy would what is a primitive depend on the ISA? If you need car, cdr and cons, it doesn't matter whether each is a single instruction or then thousand, does it?