5 ms·

Lisp interpreter in 90 lines of C++

92 points by fogus 16y ago

spacemanaki 16y ago
> Nevertheless, I get a little thrill out of having made something that allows me to type (define cube (lambda (n) (* n n n))) and then (cube 3). It's like magic. This is great, and it's really true. I've just finished the Metacircular chapter of SICP and felt the same way after reading their code and doing some of the exercises. I think "90 lines of C++" is kind of a silly goal (just because LOC is silly) but it's still a great learning experience. I'd love to try a non-metacircular evaluator after I've read more SICP. The author might be interested in http://michaux.ca/articles/scheme-from-scratch-introduction http://michaux.ca/articles/scheme-from-scratch-introduction I think I found that on HN somewhere, it's been in my TOREAD for a while.
- samstokes 16y ago
  +1 for Scheme From Scratch - very illuminating and inspiring series of articles.
- hvs 16y ago
  If you're interested in getting into the details of implementing a Lisp/Scheme interpreter and compiler, I highly recommend Lisp in Small Pieces: http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/dp/0521545668 http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/d...
  - sedachv 16y ago
    mahmud turned me onto Abdulaziz Ghuloum's An Incremental Approach to Compiler Construction: http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf ; I can't stop raving about it.
dtf 16y ago
I have to say I'm a huge fan of these "X in 100 lines of C++" adventures. They're a great starting point for people like me wanting to learn about a subject in a programmatic way. This global illumination ray-tracer was posted a while back: http://kevinbeason.com/smallpt/ http://kevinbeason.com/smallpt/
- silentbicycle 16y ago
  Here's one of the most interesting "X in Y lines of Z" programs I've seen, a prototype interpreter for the basics of an APL-like language in one page of (rather funky, Arthur Whitney-style) C: http://nsl.com/papers/origins.htm http://nsl.com/papers/origins.htm It segfaults due to nonportable assumptions about pointer sizes in the allocator, and is far from complete as APLs go, but I spent a couple hours picking it apart and came away quite impressed. There's a similar raytracer (http://nsl.com/k/ray/rayq.k http://nsl.com/k/ray/rayq.k) in 17 lines of Q, but I haven't figured that one out yet.
- hxa7241 16y ago
  . . . or MiniLight: http://www.hxa.name/minilight/ http://www.hxa.name/minilight/ is an alternative: it is larger -- averaging 650 lines -- but it is available in 9 different languages -- and is a more complete renderer that you can put your own scenes into. (I am working on the Scheme translation at the moment)
olalonde 16y ago
> // Scheme Interpreter in 90 lines of C++ (not counting lines after the first 90). It's actually 333 lines.
- kleiba 16y ago
  Wait, did you count the lines after the first 90?
  - mooism2 16y ago
    Yeah, I didn't count the words after the first C++.
  - alextgordon 16y ago
    I bet I can get it down to one line.
- stuhacking 16y ago
  Even after removing comments, whitespace and brace lines it weighs in around 190 LLOC.
- astine 16y ago
  It's based on Peter Norvig's article of a similar name. I think that the '90 lines' was a reference to that former article rather than a literal description of this one.
shin_lao 16y ago
I'm both a Lisp and a C++ fan and I really like the idea, but I'd like to make a couple of suggestions. - Use the STL algorithms more. There are way too many "for" loops in this code which are trivial std::accumulate or std::transform calls. - When I see the eval and tokenize functions I ask myself, why not use Boost.Spirit.Qi? - I'm not sure working on a list of strings is efficient, why not work on a list of pairs of pointers instead? - Use smart pointers to avoid leaks. Just a small contribution, I really like the idea.
- paufernandez 16y ago
  "When I see the eval and tokenize functions I ask myself, why not use Qi?" You mean to use Qi's eval? I don't know Qi, so I don't understand what that would entail.
- mahmud 16y ago
  Note to confused Lispers: When I see the eval and tokenize functions I ask myself, why not use Qi? Pull down your eye-brows folks, he means boost::spirit::qi, not http://en.wikipedia.org/wiki/Qi_(programming_language) http://en.wikipedia.org/wiki/Qi_(programming_language) I had a whole minute of flabbergasted awe, then decided to double check with the Google :-)
  - shin_lao 16y ago
    You're right, I edited my remark.
- scott_s 16y ago
  - Use the STL algorithms more. There are way too many "for" loops in this code which are trivial std::accumulate or std::transform calls. Pre-C++0x, that's not a clear tradeoff. Since pre-C++0x does not have lambdas, you would have to write one-off functions or function objects. In this case, I think that would increase the number of lines of code. I do a lot of work in C++, and I prefer using the STL algorithms to explicit for loops. But I have often written code that uses the STL algorithms, then reverted it back to a for loop because I had to introduce more code at another level of scope for a marginal gain in clarity - a voice in the back of my head tells me I'm being too cute. Now that C++0x has lambdas, this should cease to become an issue as I can assume compilers support them.
agazso 16y ago
I'm nitpicking, but actually any C or C++ program can be written in one line, but otherwise it's a great experiment.
- mihaifx 16y ago
  The point is to write a read-able instruction per line. He follows this with a few exceptions.
- pmiller2 16y ago
  I threatened to do this in an introductory undergrad systems programming course I had to take to satisfy a degree requirement in spite of it being way below my level of proficiency. Fortunately for my grade and the grader's sanity, I chose not to do it.
  - scott_s 16y ago
    If your grader was aware of the indent program, it wouldn't be an issue.
    - swolchok 16y ago
      Graders at the University of Michigan are willfully unaware of it because we want students to have some coding style. You'd be surprised how many have to be repeatedly slapped around until they get a real programmer's editor instead of trying to use gedit without configuring it.
fogus 16y ago
I am also a sucker for "X in Y lines of Z code" posts. I would love to see a comprehensive list arranged by language/topic.
zitterbewegung 16y ago
Why do people keep on calling lisp-1's scheme? This doesn't even have call/cc ... its basically scheme in name only.
lisper 16y ago
A similar thing, but with better integration with C++. Includes exceptions and a full numerical tower: https://github.com/rongarret/Ciel https://github.com/rongarret/Ciel Note: not quite ready for prime time. Just a proof of concept for now.
deadsy 16y ago
I looked at the Norvig lis.py code and took the time to understand every line. It's a clever program and taught me a few new Python tricks. The main reason he can get it down to so few lines of code is that he leans back on the capabilities of Python. E.g. garbage collection, arbitrary objects stored in hierarchical lists, lambdas, use of dictionaries for the environment/symbol table. If you try the same thing with a language like C you either need library support or more lines of original code.
eschulte 16y ago
Lisp interpreter in 4 lines of Clojure! https://gist.github.com/720413 https://gist.github.com/720413 Sorry I know this is rude, but I'm tired of seeing so many posts about lisp interpreters in high level languages, the vast majority of which don't mention macros -- the only plausible reason that such an interpreter would really be useful (mine does support macros :)).
wrs 16y ago
I know this is a curmudgeonly thing to say, but I'm happy to see one of these "implementing Lisp" articles where someone started with a lower-level language than Lisp. It just seems like you miss out on a lot of interesting learning if you start with something like Ruby or Python that is so close to Lisp already. For example, implementing lambda with a Python lambda...really? You are missing a giant a-ha moment there, as you can see from this article. Note: implementing a metacircular interpreter for Lisp in Lisp is a beautiful special case exception to my curmudgeonliness.
johnohara 16y ago
Tried to compile this using Borland's C++ 5.5 (free). The only function not supported was 'isdigit()'. Wrote a simple version just for fun and it compiled. I was able to run the first example completely. Not bad for an out-of-date but free compiler with a 1993,2000 copyright.

92 points by fogus 16y ago

> Nevertheless, I get a little thrill out of having made something that allows me to type (define cube (lambda (n) (* n n n))) and then (cube 3). It's like magic. This is great, and it's really true. I've just finished the Metacircular chapter of SICP and felt the same way after reading their code and doing some of the exercises. I think "90 lines of C++" is kind of a silly goal (just because LOC is silly) but it's still a great learning experience. I'd love to try a non-metacircular evaluator after I've read more SICP. The author might be interested in http://michaux.ca/articles/scheme-from-scratch-introduction http://michaux.ca/articles/scheme-from-scratch-introduction I think I found that on HN somewhere, it's been in my TOREAD for a while.

samstokes 16y ago
+1 for Scheme From Scratch - very illuminating and inspiring series of articles.
hvs 16y ago
If you're interested in getting into the details of implementing a Lisp/Scheme interpreter and compiler, I highly recommend Lisp in Small Pieces: http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/dp/0521545668 http://www.amazon.com/Lisp-Small-Pieces-Christian-Queinnec/d...
- sedachv 16y ago
  mahmud turned me onto Abdulaziz Ghuloum's An Incremental Approach to Compiler Construction: http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf ; I can't stop raving about it.

dtf 16y ago

I have to say I'm a huge fan of these "X in 100 lines of C++" adventures. They're a great starting point for people like me wanting to learn about a subject in a programmatic way. This global illumination ray-tracer was posted a while back: http://kevinbeason.com/smallpt/ http://kevinbeason.com/smallpt/

silentbicycle 16y ago
Here's one of the most interesting "X in Y lines of Z" programs I've seen, a prototype interpreter for the basics of an APL-like language in one page of (rather funky, Arthur Whitney-style) C: http://nsl.com/papers/origins.htm http://nsl.com/papers/origins.htm It segfaults due to nonportable assumptions about pointer sizes in the allocator, and is far from complete as APLs go, but I spent a couple hours picking it apart and came away quite impressed. There's a similar raytracer (http://nsl.com/k/ray/rayq.k http://nsl.com/k/ray/rayq.k) in 17 lines of Q, but I haven't figured that one out yet.
hxa7241 16y ago
. . . or MiniLight: http://www.hxa.name/minilight/ http://www.hxa.name/minilight/ is an alternative: it is larger -- averaging 650 lines -- but it is available in 9 different languages -- and is a more complete renderer that you can put your own scenes into. (I am working on the Scheme translation at the moment)

olalonde 16y ago

> // Scheme Interpreter in 90 lines of C++ (not counting lines after the first 90). It's actually 333 lines.

kleiba 16y ago
Wait, did you count the lines after the first 90?
- mooism2 16y ago
  Yeah, I didn't count the words after the first C++.
- alextgordon 16y ago
  I bet I can get it down to one line.
stuhacking 16y ago
Even after removing comments, whitespace and brace lines it weighs in around 190 LLOC.
astine 16y ago
It's based on Peter Norvig's article of a similar name. I think that the '90 lines' was a reference to that former article rather than a literal description of this one.

shin_lao 16y ago

I'm both a Lisp and a C++ fan and I really like the idea, but I'd like to make a couple of suggestions. - Use the STL algorithms more. There are way too many "for" loops in this code which are trivial std::accumulate or std::transform calls. - When I see the eval and tokenize functions I ask myself, why not use Boost.Spirit.Qi? - I'm not sure working on a list of strings is efficient, why not work on a list of pairs of pointers instead? - Use smart pointers to avoid leaks. Just a small contribution, I really like the idea.

paufernandez 16y ago
"When I see the eval and tokenize functions I ask myself, why not use Qi?" You mean to use Qi's eval? I don't know Qi, so I don't understand what that would entail.
mahmud 16y ago
Note to confused Lispers: When I see the eval and tokenize functions I ask myself, why not use Qi? Pull down your eye-brows folks, he means boost::spirit::qi, not http://en.wikipedia.org/wiki/Qi_(programming_language) http://en.wikipedia.org/wiki/Qi_(programming_language) I had a whole minute of flabbergasted awe, then decided to double check with the Google :-)
- shin_lao 16y ago
  You're right, I edited my remark.
scott_s 16y ago
- Use the STL algorithms more. There are way too many "for" loops in this code which are trivial std::accumulate or std::transform calls. Pre-C++0x, that's not a clear tradeoff. Since pre-C++0x does not have lambdas, you would have to write one-off functions or function objects. In this case, I think that would increase the number of lines of code. I do a lot of work in C++, and I prefer using the STL algorithms to explicit for loops. But I have often written code that uses the STL algorithms, then reverted it back to a for loop because I had to introduce more code at another level of scope for a marginal gain in clarity - a voice in the back of my head tells me I'm being too cute. Now that C++0x has lambdas, this should cease to become an issue as I can assume compilers support them.

agazso 16y ago

I'm nitpicking, but actually any C or C++ program can be written in one line, but otherwise it's a great experiment.

mihaifx 16y ago
The point is to write a read-able instruction per line. He follows this with a few exceptions.
pmiller2 16y ago
I threatened to do this in an introductory undergrad systems programming course I had to take to satisfy a degree requirement in spite of it being way below my level of proficiency. Fortunately for my grade and the grader's sanity, I chose not to do it.
- scott_s 16y ago
  If your grader was aware of the indent program, it wouldn't be an issue.
  - swolchok 16y ago
    Graders at the University of Michigan are willfully unaware of it because we want students to have some coding style. You'd be surprised how many have to be repeatedly slapped around until they get a real programmer's editor instead of trying to use gedit without configuring it.

fogus 16y ago

I am also a sucker for "X in Y lines of Z code" posts. I would love to see a comprehensive list arranged by language/topic.

zitterbewegung 16y ago

Why do people keep on calling lisp-1's scheme? This doesn't even have call/cc ... its basically scheme in name only.

lisper 16y ago

A similar thing, but with better integration with C++. Includes exceptions and a full numerical tower: https://github.com/rongarret/Ciel https://github.com/rongarret/Ciel Note: not quite ready for prime time. Just a proof of concept for now.

deadsy 16y ago

I looked at the Norvig lis.py code and took the time to understand every line. It's a clever program and taught me a few new Python tricks. The main reason he can get it down to so few lines of code is that he leans back on the capabilities of Python. E.g. garbage collection, arbitrary objects stored in hierarchical lists, lambdas, use of dictionaries for the environment/symbol table. If you try the same thing with a language like C you either need library support or more lines of original code.

eschulte 16y ago

Lisp interpreter in 4 lines of Clojure! https://gist.github.com/720413 https://gist.github.com/720413 Sorry I know this is rude, but I'm tired of seeing so many posts about lisp interpreters in high level languages, the vast majority of which don't mention macros -- the only plausible reason that such an interpreter would really be useful (mine does support macros :)).

wrs 16y ago

I know this is a curmudgeonly thing to say, but I'm happy to see one of these "implementing Lisp" articles where someone started with a lower-level language than Lisp. It just seems like you miss out on a lot of interesting learning if you start with something like Ruby or Python that is so close to Lisp already. For example, implementing lambda with a Python lambda...really? You are missing a giant a-ha moment there, as you can see from this article. Note: implementing a metacircular interpreter for Lisp in Lisp is a beautiful special case exception to my curmudgeonliness.

johnohara 16y ago

Tried to compile this using Borland's C++ 5.5 (free). The only function not supported was 'isdigit()'. Wrote a simple version just for fun and it compiled. I was able to run the first example completely. Not bad for an out-of-date but free compiler with a 1993,2000 copyright.