3 ms·

> There are lots of standard functions still missing, but rather than implement them as built-ins, they can be implemented from the primitives already available

> There are lots of standard functions still missing, but rather than implement them as built-ins, they can be implemented from the primitives already available. I'd be interested in reading more about this. For example, how was that set of primitives chosen? How does the author know that the set of primitives is sufficient? A couple relevant (and interesting) links: What is the "minimal" set of primitives needed for a Lisp interpreter? https://www.cs.cmu.edu/Groups/AI/html/faqs/lang/lisp/part1/faq-doc-6.html https://www.cs.cmu.edu/Groups/AI/html/faqs/lang/lisp/part1/f... What is the smallest definition of Lisp? https://www.reddit.com/r/lisp/comments/aklz0x/what_is_the_smallest_definition_of_lisp/ https://www.reddit.com/r/lisp/comments/aklz0x/what_is_the_sm...

pjmlp 5y ago
I would consider Lisp 1.5 manual as the minimal set.
- metagame 5y ago
  Consider alternatively: https://github.com/jart/sectorlisp/blob/main/sectorlisp.S https://github.com/jart/sectorlisp/blob/main/sectorlisp.S https://github.com/jart/sectorlisp/blob/main/lisp.lisp https://github.com/jart/sectorlisp/blob/main/lisp.lisp This does give me an idea to do it in even less, though. I'll have to spend a weekend on it. It's also worth noting that the 1.5 metacircular interpreter is incomplete: https://github.com/kragen/stoneknifeforth#why--to-know-what-im-doing https://github.com/kragen/stoneknifeforth#why--to-know-what-...
  - abecedarius 5y ago
    An old go of mine at filling in that incompleteness in a minimal way: https://github.com/darius/ichbins https://github.com/darius/ichbins It went a little too minimal in having no comments.
fsloth 5y ago
"Structure and interpretation of computer programs" (SICP) by Sussman and Abelson contains a recipe for scheme interpreter that can be implemented in any language and answers this as well (well, for scheme).
juliangamble 5y ago
This site reckons there are 10: http://hyperpolyglot.wikidot.com/lisp#ten-primitives http://hyperpolyglot.wikidot.com/lisp#ten-primitives Steve Yegge said there were seven (or five): McCarthy had five. On an x86 architecture - you can do it with one. https://stackoverflow.com/questions/3482389/how-many-primitives-does-it-take-to-build-a-lisp-machine-ten-seven-or-five/ https://stackoverflow.com/questions/3482389/how-many-primiti...
- lioeters 5y ago
  I had imagined this was merely theoretical, but learned that there are computers implemented with a single instruction. https://en.wikipedia.org/wiki/One-instruction_set_computer#Machine_architecture https://en.wikipedia.org/wiki/One-instruction_set_computer#M... https://esolangs.org/wiki/OISC https://esolangs.org/wiki/OISC
- eatonphil 5y ago
  I don't think movfuscator proves you only need one lisp primitive. Just that any language can be evaluated using mov's many variant forms.
- tromp 5y ago
  In the functional realm which LISP inhabits, two combinators suffice: S and K. https://en.wikipedia.org/wiki/SKI_combinator_calculus https://en.wikipedia.org/wiki/SKI_combinator_calculus
  - afiori 5y ago
    in the context of S and K, lisp is not functional
DonaldFisk 5y ago
You'll need car, cdr, cons, atom, and eq. You'll also need ratom and patom for input and output. That's 7 primitive functions. To be able to define recursive functions, you'll also need cond, lambda, setq (or define), quote, and function. That's five special forms. Then you have to write read, eval, apply, and print in your implementation language. That gives you a minimal interpreter. These four functions aren't primitives, but you have to write them and you might as well expose them to the user. Eval and apply call a few other functions which are generally useful, such as assoc, evlis and pairlis. This excludes arithmetic functions and a whole lot of other stuff you'd need for your interpreter to be useful.
- brundolf 5y ago
  Technically I think you could implement arithmetic as recursive functions operating on lists of different lengths.....
  - mpfundstein 5y ago
    you just inspired me to re-read GEB part 1 :-)
  - DonaldFisk 5y ago
    Interestingly, this was more or less the way that Lenat's program AM discovered numbers, and later arithmetic.
    - brundolf 5y ago
      Hah, I actually used to work for Lenat but I didn't know this :)

pjmlp 5y ago

I would consider Lisp 1.5 manual as the minimal set.

metagame 5y ago
Consider alternatively: https://github.com/jart/sectorlisp/blob/main/sectorlisp.S https://github.com/jart/sectorlisp/blob/main/sectorlisp.S https://github.com/jart/sectorlisp/blob/main/lisp.lisp https://github.com/jart/sectorlisp/blob/main/lisp.lisp This does give me an idea to do it in even less, though. I'll have to spend a weekend on it. It's also worth noting that the 1.5 metacircular interpreter is incomplete: https://github.com/kragen/stoneknifeforth#why--to-know-what-im-doing https://github.com/kragen/stoneknifeforth#why--to-know-what-...
- abecedarius 5y ago
  An old go of mine at filling in that incompleteness in a minimal way: https://github.com/darius/ichbins https://github.com/darius/ichbins It went a little too minimal in having no comments.

fsloth 5y ago

"Structure and interpretation of computer programs" (SICP) by Sussman and Abelson contains a recipe for scheme interpreter that can be implemented in any language and answers this as well (well, for scheme).

juliangamble 5y ago

This site reckons there are 10: http://hyperpolyglot.wikidot.com/lisp#ten-primitives http://hyperpolyglot.wikidot.com/lisp#ten-primitives Steve Yegge said there were seven (or five): McCarthy had five. On an x86 architecture - you can do it with one. https://stackoverflow.com/questions/3482389/how-many-primitives-does-it-take-to-build-a-lisp-machine-ten-seven-or-five/ https://stackoverflow.com/questions/3482389/how-many-primiti...

lioeters 5y ago
I had imagined this was merely theoretical, but learned that there are computers implemented with a single instruction. https://en.wikipedia.org/wiki/One-instruction_set_computer#Machine_architecture https://en.wikipedia.org/wiki/One-instruction_set_computer#M... https://esolangs.org/wiki/OISC https://esolangs.org/wiki/OISC
eatonphil 5y ago
I don't think movfuscator proves you only need one lisp primitive. Just that any language can be evaluated using mov's many variant forms.
tromp 5y ago
In the functional realm which LISP inhabits, two combinators suffice: S and K. https://en.wikipedia.org/wiki/SKI_combinator_calculus https://en.wikipedia.org/wiki/SKI_combinator_calculus
- afiori 5y ago
  in the context of S and K, lisp is not functional

DonaldFisk 5y ago

You'll need car, cdr, cons, atom, and eq. You'll also need ratom and patom for input and output. That's 7 primitive functions. To be able to define recursive functions, you'll also need cond, lambda, setq (or define), quote, and function. That's five special forms. Then you have to write read, eval, apply, and print in your implementation language. That gives you a minimal interpreter. These four functions aren't primitives, but you have to write them and you might as well expose them to the user. Eval and apply call a few other functions which are generally useful, such as assoc, evlis and pairlis. This excludes arithmetic functions and a whole lot of other stuff you'd need for your interpreter to be useful.

brundolf 5y ago
Technically I think you could implement arithmetic as recursive functions operating on lists of different lengths.....
- mpfundstein 5y ago
  you just inspired me to re-read GEB part 1 :-)
- DonaldFisk 5y ago
  Interestingly, this was more or less the way that Lenat's program AM discovered numbers, and later arithmetic.
  - brundolf 5y ago
    Hah, I actually used to work for Lenat but I didn't know this :)