6 ms·

Little Lisp interpreter

187 points by maryrosecook 13y ago

TempleOS 13y ago
I wrote a HolyC compiler. Why don't you put your Lisp into God's temple. God says... C:\TAD\Text\QUIX.TXT f the dark shadows of ignorance that my unhappy constant study of those detestable books of chivalry cast over it. Now I see through their absurdities and deceptions, and it only grieves me that this destruction of my illusions has come so late that it leaves me no time to make some amends by reading other books that might be a light to my soul. Niece, I feel myself at the point of death, and I would fain meet it in such a way as to show that my life has not been so ill that I should leave behind me
groovy2shoes 13y ago
I've written a toy Lisp interpreter that eventually evolved into a toy Lisp compiler. It's a gratifying exercise that I'd recommend for every programmer.
- dominicrodger 13y ago
  Likewise - I did this as part of a hackathon earlier this year - thoroughly enjoyed seeing how all the pieces fitted together.
- cninja 13y ago
  I couldn't agree more. Writing my own interpreter https://github.com/cninja/pEigthP https://github.com/cninja/pEigthP provided many challenges but I think it was one of the most enjoyable "toy projects" that I have done. Also seeing the look on someones face when I say I wrote something to allow me to embed lisp into PHP is priceless.
emeraldd 13y ago
If you find that interesting, you should probably take a look at this: http://michaux.ca/articles/scheme-from-scratch-introduction http://michaux.ca/articles/scheme-from-scratch-introduction I had fun following along with him. Now, if he (or I can get my shot at it finished) can ever finish working on the byte-code based version!
- yfefyf 13y ago
  Thank you for this link.
- pdelgallego 13y ago
  You might enjoy Lisp in Small Pieces. Is one of my favorite books The book is in two parts. The first starts from a simple evaluation function and enriches it with multiple name spaces, continuations and side-effects with commented variants, while at the same time the language used to define these features is reduced to a simple lambda-calculus. The second part focuses more on implementation techniques and discusses precompilation for fast interpretation: threaded code or bytecode; compilation towards C. Some extensions are also described such as dynamic evaluation, reflection, macros and objects. http://www.amazon.com/books/dp/0521545668 http://www.amazon.com/books/dp/0521545668
  - mnemonik 13y ago
    Great book, although I found it hard parse sometimes (compared to say the later chapters of SICP) which I suspect is because it is translated from french. Either way, it puts so much information in one place, it is incredibly valuable.
  - Nzen 13y ago
    If anyone's considering it, now is the time. I've watched it for the last five months. The used price almost always hovers at 80 dollars. It is currently 54 dollars. I'd buy it myself if it weren't just going to sit on my shelf, unopened, the next five months.
- fabriceleal 13y ago
  Looks very interesting; I already had a shot at implementing a subset of scheme using F# (https://github.com/fabriceleal/Pang https://github.com/fabriceleal/Pang), it would be very interesting to follow this series and check the differences between my and his implementations. I would also find very interesting to see a step-by-step series on compiling scheme (with macros included) using llvm. I never tried really hard to look for one, though.
- 13y ago
klrr 13y ago
This is the best beginner project.
- kybernetikos 13y ago
  Which is why there's so many of them out there. (For example my own: http://kybernetikos.github.io/Javathcript/ http://kybernetikos.github.io/Javathcript/ )
  - weavie 13y ago
    Yours wins on the name.
fabriceleal 13y ago
Already down? Google-cached: http://webcache.googleusercontent.com/search?q=cache:https://www.hackerschool.com/blog/21-little-lisp-interpreter http://webcache.googleusercontent.com/search?q=cache:https:/...
- emeraldd 13y ago
  Looks up to me.
- matt_ 13y ago
  Was down for me, thanks for the link.
inginist 13y ago
why write toy, when you can write a real one in python, check http://hylang.org http://hylang.org
cabalamat 13y ago
Is there some reason why every code segment inside not one but two scrolling frames? And does anyone else dislike web design that (1) limits the text to a column a third of the page wide, and then (2) because this is too small, requires a horizontal scrollbar on code segments? For an explanation of a small Lisp interpreter (in Python) that uses sane web design, one might consider Norvig's http://norvig.com/lispy.html http://norvig.com/lispy.html
- nicholasjbs 13y ago
  Thanks for pointing that out. The double-scrollbar was a CSS bug which was only showing up in some browsers. It should be fixed now. I agree this page should be wider for posts like this.
  - weavie 13y ago
    At first I thought it was some play on recursion and though "neat", but then I realised it was probably just an error...
ncarroll 13y ago
Who needs a toy lisp? Can't we just lisp for real? Edit: Ok, ok. Now that the title of submission has been changed from "Toy Lisp Interpreter" to "Little Lisp Interpreter" my quip, having lost context doesn't make me smile anymore either.
- pmelendez 13y ago
  As a learning experience is excellent. Lisp family languages are great for this since they are turing complete and with a pretty simple syntax.
  - brudgers 13y ago
    Under the aesthetics of logic, I find Lisp's syntax pretty as well.
mrottenkolber 13y ago
How to write a toy Lisp to C compiler: http://mr.gy/software/microlisp/ http://mr.gy/software/microlisp/
jws 13y ago
I think more useful for me would be "How to build a complex system and not accidentally write a toy Lisp interpreter".
- hga 13y ago
  "Write it in a Lisp" or "Use a Lisp as an extension language" don't work? (Last time I tried the latter the more vocal members of the user base complained so much the entire effort died. That was in 2000.)
  - patrickmay 13y ago
    Details, please? (If you're so inclined.)
    - hga 13y ago
      The existing product was a C code base that had been hacked upon for 16 years (!), with several distinct breaks in continuity. Sufficiently bad that it took hours of investigation to make the slightest change safely, and its performance was increasingly unacceptable, plus it was buggy. I've done a lot of "code archaeology" before and some since, and this is the first time I decided a code base was a total loss with no insurance. So the deadly total rewrite was planned. The business model was "gated open source", as in paying customers got source, the users were almost without exception system administrators, not programmers, and with one exception who was something of a programmer (at least he did more with the awful code base than any other user) and willing to give it a try, they demanded the "extension" language (actually the complicated business logic) be in Perl ... despite to our knowledge at there were no successful examples of this, whereas Lisp has many, with EMACS and AutoCAD being famous wild successes. (The whole thing couldn't be in Perl because of performance requirements.) Despite being the only programmer working on it and not seriously experienced with Perl, I got overruled. The CEO, the only manager, was the sort who during this time of decreasing revenue felt compelled to move from Class B to Class A office space (https://en.wikipedia.org/wiki/Office#Grading https://en.wikipedia.org/wiki/Office#Grading), and more of it---yet somehow the 3 technical people supporting almost all revenue got allocated only one office, which was tight for 2 people, and I'm one of those who needs quiet for maximum productivity (the other two were sysadmins and technical support, and had to do a lot of the latter over the phone. Whine, whine.) Basically, only with maximum productivity on my part was this possible to pull off (and I've done this sort of thing before), as the users were years overdue for real technical fixes and progress (long before I arrived). The board got really upset, the executive director blamed me and they believed her (I after all had been there for less than 2 years and had been able to do only one month of programming in my first year due to Y2K and other sysadmin and tech support demands) ... I had to bail. It was partly my fault, I was not very productive for several months after my major architectural decision was vetoed and that work was dumped, which happened roughly the time the office move made the company's financials likely terminal, and I should have outright refused the CEO when she demanded I drop everything to help try to sell more of the old (which her fantasy budget demanded) and pre-sell versions of the new (then again I have to wonder if that would have made any difference). The company died an ugly death, but not before firing in revenge a close friend I'd hired to do system administration and tech support. Bleah. Bottom lines: avoid recruiting your friends because the company may later go to hell, if you observe the former then don't stay at places that don't respect programmers, can't keep them, and who don't have their eye on the ball of what brings in the cash. None of this was apparent when I accepted their offer, but I'm sure most of us know that story.
dugmartin 13y ago
The tokenizer breaks on strings with parens in them. You should be able to split on each character and implement a simple variant on the shunting yard algorithm in only a few more lines of code and get a robust tokenizer.
mathattack 13y ago
Wouldn't it be more fun to write it in LISP itself?
- emeraldd 13y ago
  You could, I think it would be more interesting to start with a bootstrap system, written in something native, that get's you the minimum you need to run lisp and then rebuild the system in lisp on top of that. Of course, that requires delving into some much more interesting topics like foreign funcitons, compilation, etc.
erik14th 13y ago
https://github.com/JeffBezanson/femtolisp https://github.com/JeffBezanson/femtolisp Lisp implementation from one of the julialang devs
stiff 13y ago
Writing a Lisp interpreter is an opportunity to write a really beautiful program, do not waste it by stopping at a first version that sort of works. A nice implementation should read almost like a spec of the language, except maybe for the more prosaic parsing part. Look at the Norvig article, or at the implementation of Ian Piumarta for inspiration: http://piumarta.com/software/lysp/lysp-1.1/lysp.c http://piumarta.com/software/lysp/lysp-1.1/lysp.c
- magal 13y ago
  Or Chaitin's http://www.umcs.maine.edu/~chaitin/lisp.c http://www.umcs.maine.edu/~chaitin/lisp.c
- kaoD 13y ago
  Yeah but... which spec? (pun intended)
breckinloggins 13y ago
I wrote one in erlang that works pretty well and is even designed to be able to call into erlang functions (if I took it that far). https://github.com/breckinloggins/erlisp https://github.com/breckinloggins/erlisp I'm currently working on writing one in Haskell using the Scheme48 tutorial [1], though I'd eventually like to replace the evaluator with an F-Algebra[2] so I can learn about that. https://github.com/breckinloggins/scheme48 https://github.com/breckinloggins/scheme48 As a side note, would any Haskellers be willing to look at the abstraction I did for parsing #-forms? I created an adhoc data structure: hashLiteralInfo = [ ('f', (Nothing, \_ -> Bool False)), ('t', (Nothing, \_ -> Bool True)), ('b', (Just $ many $ oneOf "01", Number . toInteger . fromBase 2)), ('o', (Just $ many $ oneOf "01234567", Number . toInteger . fromBase 8)), ('d', (Just $ many $ oneOf "0123456789", Number . toInteger . fromBase 10)), ('h', (Just $ many $ oneOf "0123456789abcdefABCDEF", Number . toInteger . fromBase 16)) ] And then the parser consumes that: parseHashLiteral :: Parser LispVal parseHashLiteral = do char '#' c <- oneOf $ map fst hashLiteralInfo let literalInfo = lookup c hashLiteralInfo case literalInfo of Nothing -> fail "Internal parse error: unregistered literal info" Just (Nothing, f) -> return $ f "unneeded" -- I know there's a more idiomatic way to do that Just (Just literalParser, f) -> do digits <- literalParser return $ f digits This works and is "abstracted", but doesn't feel idiomatic. Thoughts? [1] http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_H... [2] http://bartoszmilewski.com/2013/06/10/understanding-f-algebras/ http://bartoszmilewski.com/2013/06/10/understanding-f-algebr...
- tmhedberg 13y ago
  Personally, my approach would be to change the association list so that the values, rather than being pairs of type `(Maybe (Parser String), String -> LispVal)`, are instead just values of type `Parser LispVal`, something like this: hashLiteralInfo = [ ('f', pure $ Bool False) , ('t', pure $ Bool True) , ('b', fmap (Number . toInteger . fromBase 2) (many $ oneOf "01")) -- ... and so on ] The Boolean literal cases are then just parsers which consume no input and always return the same LispVal, instead of being separate, special cases that need to be handled by awkwardly passing a dummy string to a function which ignores its argument.
daemonfire300 13y ago
What is it with you and writting an interpreter for the language in the language?
ktg 13y ago
Parenjs: Lisp-to-JavaScript compiler https://bitbucket.org/ktg/parenjs https://bitbucket.org/ktg/parenjs
dschiptsov 13y ago
Any environments, list-aware reader, closures or just parenthesized prefix notation translated to JS or Haskell?) btw, not related to OP, those guys who think it is so clever to translate some primitive subset of Scheme into Haskell should appreciate that writing Scheme interpreter in Scheme is a part of CS61A course and it takes one page of much more readable code. If, for some reason, you wish to write something other than toys, look at Mark Freeley, to realize that serious Scheme system is hard.

187 points by maryrosecook 13y ago

I wrote a HolyC compiler. Why don't you put your Lisp into God's temple. God says... C:\TAD\Text\QUIX.TXT f the dark shadows of ignorance that my unhappy constant study of those detestable books of chivalry cast over it. Now I see through their absurdities and deceptions, and it only grieves me that this destruction of my illusions has come so late that it leaves me no time to make some amends by reading other books that might be a light to my soul. Niece, I feel myself at the point of death, and I would fain meet it in such a way as to show that my life has not been so ill that I should leave behind me

groovy2shoes 13y ago

I've written a toy Lisp interpreter that eventually evolved into a toy Lisp compiler. It's a gratifying exercise that I'd recommend for every programmer.

dominicrodger 13y ago
Likewise - I did this as part of a hackathon earlier this year - thoroughly enjoyed seeing how all the pieces fitted together.
cninja 13y ago
I couldn't agree more. Writing my own interpreter https://github.com/cninja/pEigthP https://github.com/cninja/pEigthP provided many challenges but I think it was one of the most enjoyable "toy projects" that I have done. Also seeing the look on someones face when I say I wrote something to allow me to embed lisp into PHP is priceless.

emeraldd 13y ago

If you find that interesting, you should probably take a look at this: http://michaux.ca/articles/scheme-from-scratch-introduction http://michaux.ca/articles/scheme-from-scratch-introduction I had fun following along with him. Now, if he (or I can get my shot at it finished) can ever finish working on the byte-code based version!

yfefyf 13y ago
Thank you for this link.
pdelgallego 13y ago
You might enjoy Lisp in Small Pieces. Is one of my favorite books The book is in two parts. The first starts from a simple evaluation function and enriches it with multiple name spaces, continuations and side-effects with commented variants, while at the same time the language used to define these features is reduced to a simple lambda-calculus. The second part focuses more on implementation techniques and discusses precompilation for fast interpretation: threaded code or bytecode; compilation towards C. Some extensions are also described such as dynamic evaluation, reflection, macros and objects. http://www.amazon.com/books/dp/0521545668 http://www.amazon.com/books/dp/0521545668
- mnemonik 13y ago
  Great book, although I found it hard parse sometimes (compared to say the later chapters of SICP) which I suspect is because it is translated from french. Either way, it puts so much information in one place, it is incredibly valuable.
- Nzen 13y ago
  If anyone's considering it, now is the time. I've watched it for the last five months. The used price almost always hovers at 80 dollars. It is currently 54 dollars. I'd buy it myself if it weren't just going to sit on my shelf, unopened, the next five months.
fabriceleal 13y ago
Looks very interesting; I already had a shot at implementing a subset of scheme using F# (https://github.com/fabriceleal/Pang https://github.com/fabriceleal/Pang), it would be very interesting to follow this series and check the differences between my and his implementations. I would also find very interesting to see a step-by-step series on compiling scheme (with macros included) using llvm. I never tried really hard to look for one, though.
13y ago

klrr 13y ago

This is the best beginner project.

kybernetikos 13y ago
Which is why there's so many of them out there. (For example my own: http://kybernetikos.github.io/Javathcript/ http://kybernetikos.github.io/Javathcript/ )
- weavie 13y ago
  Yours wins on the name.

fabriceleal 13y ago

Already down? Google-cached: http://webcache.googleusercontent.com/search?q=cache:https://www.hackerschool.com/blog/21-little-lisp-interpreter http://webcache.googleusercontent.com/search?q=cache:https:/...

emeraldd 13y ago
Looks up to me.
matt_ 13y ago
Was down for me, thanks for the link.

inginist 13y ago

why write toy, when you can write a real one in python, check http://hylang.org http://hylang.org

cabalamat 13y ago

Is there some reason why every code segment inside not one but two scrolling frames? And does anyone else dislike web design that (1) limits the text to a column a third of the page wide, and then (2) because this is too small, requires a horizontal scrollbar on code segments? For an explanation of a small Lisp interpreter (in Python) that uses sane web design, one might consider Norvig's http://norvig.com/lispy.html http://norvig.com/lispy.html

nicholasjbs 13y ago
Thanks for pointing that out. The double-scrollbar was a CSS bug which was only showing up in some browsers. It should be fixed now. I agree this page should be wider for posts like this.
- weavie 13y ago
  At first I thought it was some play on recursion and though "neat", but then I realised it was probably just an error...

ncarroll 13y ago

Who needs a toy lisp? Can't we just lisp for real? Edit: Ok, ok. Now that the title of submission has been changed from "Toy Lisp Interpreter" to "Little Lisp Interpreter" my quip, having lost context doesn't make me smile anymore either.

pmelendez 13y ago
As a learning experience is excellent. Lisp family languages are great for this since they are turing complete and with a pretty simple syntax.
- brudgers 13y ago
  Under the aesthetics of logic, I find Lisp's syntax pretty as well.

mrottenkolber 13y ago

How to write a toy Lisp to C compiler: http://mr.gy/software/microlisp/ http://mr.gy/software/microlisp/

jws 13y ago

I think more useful for me would be "How to build a complex system and not accidentally write a toy Lisp interpreter".

hga 13y ago
"Write it in a Lisp" or "Use a Lisp as an extension language" don't work? (Last time I tried the latter the more vocal members of the user base complained so much the entire effort died. That was in 2000.)
- patrickmay 13y ago
  Details, please? (If you're so inclined.)
  - hga 13y ago
    The existing product was a C code base that had been hacked upon for 16 years (!), with several distinct breaks in continuity. Sufficiently bad that it took hours of investigation to make the slightest change safely, and its performance was increasingly unacceptable, plus it was buggy. I've done a lot of "code archaeology" before and some since, and this is the first time I decided a code base was a total loss with no insurance. So the deadly total rewrite was planned. The business model was "gated open source", as in paying customers got source, the users were almost without exception system administrators, not programmers, and with one exception who was something of a programmer (at least he did more with the awful code base than any other user) and willing to give it a try, they demanded the "extension" language (actually the complicated business logic) be in Perl ... despite to our knowledge at there were no successful examples of this, whereas Lisp has many, with EMACS and AutoCAD being famous wild successes. (The whole thing couldn't be in Perl because of performance requirements.) Despite being the only programmer working on it and not seriously experienced with Perl, I got overruled. The CEO, the only manager, was the sort who during this time of decreasing revenue felt compelled to move from Class B to Class A office space (https://en.wikipedia.org/wiki/Office#Grading https://en.wikipedia.org/wiki/Office#Grading), and more of it---yet somehow the 3 technical people supporting almost all revenue got allocated only one office, which was tight for 2 people, and I'm one of those who needs quiet for maximum productivity (the other two were sysadmins and technical support, and had to do a lot of the latter over the phone. Whine, whine.) Basically, only with maximum productivity on my part was this possible to pull off (and I've done this sort of thing before), as the users were years overdue for real technical fixes and progress (long before I arrived). The board got really upset, the executive director blamed me and they believed her (I after all had been there for less than 2 years and had been able to do only one month of programming in my first year due to Y2K and other sysadmin and tech support demands) ... I had to bail. It was partly my fault, I was not very productive for several months after my major architectural decision was vetoed and that work was dumped, which happened roughly the time the office move made the company's financials likely terminal, and I should have outright refused the CEO when she demanded I drop everything to help try to sell more of the old (which her fantasy budget demanded) and pre-sell versions of the new (then again I have to wonder if that would have made any difference). The company died an ugly death, but not before firing in revenge a close friend I'd hired to do system administration and tech support. Bleah. Bottom lines: avoid recruiting your friends because the company may later go to hell, if you observe the former then don't stay at places that don't respect programmers, can't keep them, and who don't have their eye on the ball of what brings in the cash. None of this was apparent when I accepted their offer, but I'm sure most of us know that story.

dugmartin 13y ago

The tokenizer breaks on strings with parens in them. You should be able to split on each character and implement a simple variant on the shunting yard algorithm in only a few more lines of code and get a robust tokenizer.

mathattack 13y ago

Wouldn't it be more fun to write it in LISP itself?

emeraldd 13y ago
You could, I think it would be more interesting to start with a bootstrap system, written in something native, that get's you the minimum you need to run lisp and then rebuild the system in lisp on top of that. Of course, that requires delving into some much more interesting topics like foreign funcitons, compilation, etc.

erik14th 13y ago

https://github.com/JeffBezanson/femtolisp https://github.com/JeffBezanson/femtolisp Lisp implementation from one of the julialang devs

stiff 13y ago

Writing a Lisp interpreter is an opportunity to write a really beautiful program, do not waste it by stopping at a first version that sort of works. A nice implementation should read almost like a spec of the language, except maybe for the more prosaic parsing part. Look at the Norvig article, or at the implementation of Ian Piumarta for inspiration: http://piumarta.com/software/lysp/lysp-1.1/lysp.c http://piumarta.com/software/lysp/lysp-1.1/lysp.c

magal 13y ago
Or Chaitin's http://www.umcs.maine.edu/~chaitin/lisp.c http://www.umcs.maine.edu/~chaitin/lisp.c
kaoD 13y ago
Yeah but... which spec? (pun intended)

breckinloggins 13y ago

I wrote one in erlang that works pretty well and is even designed to be able to call into erlang functions (if I took it that far). https://github.com/breckinloggins/erlisp https://github.com/breckinloggins/erlisp I'm currently working on writing one in Haskell using the Scheme48 tutorial [1], though I'd eventually like to replace the evaluator with an F-Algebra[2] so I can learn about that. https://github.com/breckinloggins/scheme48 https://github.com/breckinloggins/scheme48 As a side note, would any Haskellers be willing to look at the abstraction I did for parsing #-forms? I created an adhoc data structure: hashLiteralInfo = [ ('f', (Nothing, \_ -> Bool False)), ('t', (Nothing, \_ -> Bool True)), ('b', (Just $ many $ oneOf "01", Number . toInteger . fromBase 2)), ('o', (Just $ many $ oneOf "01234567", Number . toInteger . fromBase 8)), ('d', (Just $ many $ oneOf "0123456789", Number . toInteger . fromBase 10)), ('h', (Just $ many $ oneOf "0123456789abcdefABCDEF", Number . toInteger . fromBase 16)) ] And then the parser consumes that: parseHashLiteral :: Parser LispVal parseHashLiteral = do char '#' c <- oneOf $ map fst hashLiteralInfo let literalInfo = lookup c hashLiteralInfo case literalInfo of Nothing -> fail "Internal parse error: unregistered literal info" Just (Nothing, f) -> return $ f "unneeded" -- I know there's a more idiomatic way to do that Just (Just literalParser, f) -> do digits <- literalParser return $ f digits This works and is "abstracted", but doesn't feel idiomatic. Thoughts? [1] http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_H... [2] http://bartoszmilewski.com/2013/06/10/understanding-f-algebras/ http://bartoszmilewski.com/2013/06/10/understanding-f-algebr...

tmhedberg 13y ago
Personally, my approach would be to change the association list so that the values, rather than being pairs of type `(Maybe (Parser String), String -> LispVal)`, are instead just values of type `Parser LispVal`, something like this: hashLiteralInfo = [ ('f', pure $ Bool False) , ('t', pure $ Bool True) , ('b', fmap (Number . toInteger . fromBase 2) (many $ oneOf "01")) -- ... and so on ] The Boolean literal cases are then just parsers which consume no input and always return the same LispVal, instead of being separate, special cases that need to be handled by awkwardly passing a dummy string to a function which ignores its argument.

daemonfire300 13y ago

What is it with you and writting an interpreter for the language in the language?

ktg 13y ago

Parenjs: Lisp-to-JavaScript compiler https://bitbucket.org/ktg/parenjs https://bitbucket.org/ktg/parenjs

dschiptsov 13y ago

Any environments, list-aware reader, closures or just parenthesized prefix notation translated to JS or Haskell?) btw, not related to OP, those guys who think it is so clever to translate some primitive subset of Scheme into Haskell should appreciate that writing Scheme interpreter in Scheme is a part of CS61A course and it takes one page of much more readable code. If, for some reason, you wish to write something other than toys, look at Mark Freeley, to realize that serious Scheme system is hard.