5 ms·

What is the “minimal” set of primitives needed for a Lisp interpreter?

67 points by shawndumas 12y ago

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 ago
  Which is quite different to the theoretical minimum number which they are presumably looking at
  - throwaway823472 12y ago
    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.
- Someone 12y ago
  Why 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?
farva 12y ago
There's been a lot of discussion about the minimal set of primitives to build an interpreter in the Forth community (for instance https://groups.google.com/d/msg/comp.lang.forth/KHw28PKZXUk/JrXcjrYshxAJ https://groups.google.com/d/msg/comp.lang.forth/KHw28PKZXUk/.... ) Particularly interesting is eForth, a Forth made to be easily ported while still having acceptable performance, and Minimal ANS Forth, a heavily-commented ANS compliant Forth written in Forth (both of these use significantly more than the minimum for practical reasons.) The answer, for both Lisp and Forth, is somewhere between 8 and 11. In "real world" usage, the set of primitives largely depends on the hardware you're targeting and how well you need it to perform.
- upofadown 12y ago
  The Forth exercise is interesting because you end up with a super simple instruction set. If someone ever invents a machine that can do operations really fast, but where implementing complex operations is prohibitive, such exercises could have practical value.
5kg 12y ago
Shen[1] is a powerful language built upon Kl, which have only 46 primitives[2]. [1]: http://www.shenlanguage.org/ http://www.shenlanguage.org/ [2]: http://www.shenlanguage.org/learn-shen/shendoc.htm#The http://www.shenlanguage.org/learn-shen/shendoc.htm#The Primitive Functions of K Lambda
jules 12y ago
You only need lambda (and primitives for doing I/O). You can define numbers, lists, and all other data types using only lambda. For example you can define booleans like this: (define true (lambda (a b) a) (define false (lambda (a b) b) (define if (lambda (b a b) (b a b))) Now you can do: (if true 4 9) -> returns 4 You can define logical `and` and `or` like this: (define and (lambda (p q) (if p q false))) (define or (lambda (p q) (if p true q))) To make that work right for (if b (...) (...)) you'd need lazy evaluation though, otherwise both the then and else branch would always be evaluated regardless of whether the condition is true or false. Or you could wrap the then and else branch in a lambda, and then call the lambda that is returned by `if`. - So booleans are the type forall r. r -> r -> r. "To use a boolean, you have to give it a value of type r for the then branch, and a value of type r for the else branch, and then you get a value of type r back". - You can define natural numbers as functions of type forall r. r -> (r -> r) -> r. "To use a natural number, you should give a value of type r for n=0, and a function of type r -> r for n=k+1, then you get a value of type r back". - You can define pairs of type (A,B) as forall r. (A -> B -> r) -> r. "To use a pair of type A,B you have to give a function that takes an A and a B and returns an r, then you get an r back". - You can define sum types A+B (either an A or a B) as forall r. (A -> r) -> (B -> r) -> r. - You can define least fix points (inductive types) of a type constructor F as forall r. (F r -> r) -> r. - You can define greatest fix points (coinductive types) of a type constructor F as exists s. (s, s -> F s). See also http://en.wikipedia.org/wiki/Church_encoding http://en.wikipedia.org/wiki/Church_encoding Church encodings are a general way to define data types in lambda calculus purely based on lambdas. Church encodings are still not fully understood. For example the relation between Church encodings and mathematical induction is not fully understood yet (in type theory terms, the relation between non-dependent elimination / recursion principle and dependent elimination / induction principle). Also it's not yet fully understood how to take a fix point of a contravariant type constructor. Another thing that's as far as I know not fully understood is how to do Church encodings for higher inductive types. This goes to the very foundations of mathematics, and researchers in type theory think that in the coming years we will have breakthroughs that will make type theory a viable replacement for set theory as the basis of mathematics, with the benefit that mathematical proofs will be verified by computers.
- sklogic 12y ago
auvi 12y ago
pg has an implementation of Lisp primitives that was described in McCarthy's 1960 paper. http://ep.yimg.com/ty/cdn/paulgraham/jmc.lisp http://ep.yimg.com/ty/cdn/paulgraham/jmc.lisp
TazeTSchnitzel 12y ago
lambda, quote, cons, car, cdr, atom, cond, eq, label Or with pattern-matching: cons, lambda, label, quote And really, label is just immediately-invoked lambda, so: cons, lambda, quote http://bodil.org/building-lisp/#0 http://bodil.org/building-lisp/#0
juliangamble 12y ago
On this site they say there are 10 LISP primitives. The primitives are: atom quote eq car cdr cons cond lambda label apply http://hyperpolyglot.wikidot.com/lisp#ten-primitives http://hyperpolyglot.wikidot.com/lisp#ten-primitives Steve Yegge reckons there are seven or five: Its part of the purity of the idea of LISP: you only need the seven (or is it five?) primitives to build the full machine. http://steve-yegge.blogspot.com/2006/04/lisp-is-not-acceptable-lisp.html http://steve-yegge.blogspot.com/2006/04/lisp-is-not-acceptab... McCarthy had five: atom eq car cdr cons http://www-formal.stanford.edu/jmc/recursive.pdf http://www-formal.stanford.edu/jmc/recursive.pdf McCarthy then added another four: quote cond lambda label So according to McCarthy - the answer is nine. See here for a more in depth discussion: http://stackoverflow.com/questions/3482389/how-many-primitives-does-it-take-to-build-a-lisp-machine-ten-seven-or-five/ http://stackoverflow.com/questions/3482389/how-many-primitiv...
- sklogic 12y ago
  The answer will vary significantly depending on the degree of interpretation required (i.e., how much of your Lisp you want to lower down to something simpler prior to interpretation). That's why some lists include lambda, while some are only listing primitive functions.

67 points by shawndumas 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 ago
Which is quite different to the theoretical minimum number which they are presumably looking at
- throwaway823472 12y ago
  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.
Someone 12y ago
Why 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?

farva 12y ago

There's been a lot of discussion about the minimal set of primitives to build an interpreter in the Forth community (for instance https://groups.google.com/d/msg/comp.lang.forth/KHw28PKZXUk/JrXcjrYshxAJ https://groups.google.com/d/msg/comp.lang.forth/KHw28PKZXUk/.... ) Particularly interesting is eForth, a Forth made to be easily ported while still having acceptable performance, and Minimal ANS Forth, a heavily-commented ANS compliant Forth written in Forth (both of these use significantly more than the minimum for practical reasons.) The answer, for both Lisp and Forth, is somewhere between 8 and 11. In "real world" usage, the set of primitives largely depends on the hardware you're targeting and how well you need it to perform.

upofadown 12y ago
The Forth exercise is interesting because you end up with a super simple instruction set. If someone ever invents a machine that can do operations really fast, but where implementing complex operations is prohibitive, such exercises could have practical value.

5kg 12y ago

Shen[1] is a powerful language built upon Kl, which have only 46 primitives[2]. [1]: http://www.shenlanguage.org/ http://www.shenlanguage.org/ [2]: http://www.shenlanguage.org/learn-shen/shendoc.htm#The http://www.shenlanguage.org/learn-shen/shendoc.htm#The Primitive Functions of K Lambda

jules 12y ago

You only need lambda (and primitives for doing I/O). You can define numbers, lists, and all other data types using only lambda. For example you can define booleans like this: (define true (lambda (a b) a) (define false (lambda (a b) b) (define if (lambda (b a b) (b a b))) Now you can do: (if true 4 9) -> returns 4 You can define logical `and` and `or` like this: (define and (lambda (p q) (if p q false))) (define or (lambda (p q) (if p true q))) To make that work right for (if b (...) (...)) you'd need lazy evaluation though, otherwise both the then and else branch would always be evaluated regardless of whether the condition is true or false. Or you could wrap the then and else branch in a lambda, and then call the lambda that is returned by `if`. - So booleans are the type forall r. r -> r -> r. "To use a boolean, you have to give it a value of type r for the then branch, and a value of type r for the else branch, and then you get a value of type r back". - You can define natural numbers as functions of type forall r. r -> (r -> r) -> r. "To use a natural number, you should give a value of type r for n=0, and a function of type r -> r for n=k+1, then you get a value of type r back". - You can define pairs of type (A,B) as forall r. (A -> B -> r) -> r. "To use a pair of type A,B you have to give a function that takes an A and a B and returns an r, then you get an r back". - You can define sum types A+B (either an A or a B) as forall r. (A -> r) -> (B -> r) -> r. - You can define least fix points (inductive types) of a type constructor F as forall r. (F r -> r) -> r. - You can define greatest fix points (coinductive types) of a type constructor F as exists s. (s, s -> F s). See also http://en.wikipedia.org/wiki/Church_encoding http://en.wikipedia.org/wiki/Church_encoding Church encodings are a general way to define data types in lambda calculus purely based on lambdas. Church encodings are still not fully understood. For example the relation between Church encodings and mathematical induction is not fully understood yet (in type theory terms, the relation between non-dependent elimination / recursion principle and dependent elimination / induction principle). Also it's not yet fully understood how to take a fix point of a contravariant type constructor. Another thing that's as far as I know not fully understood is how to do Church encodings for higher inductive types. This goes to the very foundations of mathematics, and researchers in type theory think that in the coming years we will have breakthroughs that will make type theory a viable replacement for set theory as the basis of mathematics, with the benefit that mathematical proofs will be verified by computers.

sklogic 12y ago

auvi 12y ago

pg has an implementation of Lisp primitives that was described in McCarthy's 1960 paper. http://ep.yimg.com/ty/cdn/paulgraham/jmc.lisp http://ep.yimg.com/ty/cdn/paulgraham/jmc.lisp

TazeTSchnitzel 12y ago

lambda, quote, cons, car, cdr, atom, cond, eq, label Or with pattern-matching: cons, lambda, label, quote And really, label is just immediately-invoked lambda, so: cons, lambda, quote http://bodil.org/building-lisp/#0 http://bodil.org/building-lisp/#0

juliangamble 12y ago

On this site they say there are 10 LISP primitives. The primitives are: atom quote eq car cdr cons cond lambda label apply http://hyperpolyglot.wikidot.com/lisp#ten-primitives http://hyperpolyglot.wikidot.com/lisp#ten-primitives Steve Yegge reckons there are seven or five: Its part of the purity of the idea of LISP: you only need the seven (or is it five?) primitives to build the full machine. http://steve-yegge.blogspot.com/2006/04/lisp-is-not-acceptable-lisp.html http://steve-yegge.blogspot.com/2006/04/lisp-is-not-acceptab... McCarthy had five: atom eq car cdr cons http://www-formal.stanford.edu/jmc/recursive.pdf http://www-formal.stanford.edu/jmc/recursive.pdf McCarthy then added another four: quote cond lambda label So according to McCarthy - the answer is nine. See here for a more in depth discussion: http://stackoverflow.com/questions/3482389/how-many-primitives-does-it-take-to-build-a-lisp-machine-ten-seven-or-five/ http://stackoverflow.com/questions/3482389/how-many-primitiv...

sklogic 12y ago
The answer will vary significantly depending on the degree of interpretation required (i.e., how much of your Lisp you want to lower down to something simpler prior to interpretation). That's why some lists include lambda, while some are only listing primitive functions.