Little Lisp interpreter

Little Lisp interpreter(hackerschool.com)

187 points by maryrosecook 12 years ago | 46 comments

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

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

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_H...

[2] http://bartoszmilewski.com/2013/06/10/understanding-f-algebr...

tmhedberg 12 years 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.

breckinloggins 12 years ago | | |

This worked beautifully, thank you! Check it out:

https://github.com/breckinloggins/scheme48/commit/60d7930b4c...

In particular, with hashLiteralInfo setup as [(Char, Parser LispVal)], the parseHashLiteral function became as simple as:

    parseHashLiteral :: Parser LispVal
    parseHashLiteral = do
        char '#'
        c <- oneOf $ map fst hashLiteralInfo
        case lookup c hashLiteralInfo of
            Just x -> x
            Nothing -> fail "Internal parse error: unregistered literal info"

tel 12 years ago | |

I'm writing up a tutorial on F-algebras and compositional data types. I'd love if you read along and helped me to make it better.

https://www.fpcomplete.com/user/tel/from-zero-to-comp-data

breckinloggins 12 years ago | | |

Bookmarked! And I loved that you snuck in the zygohistoprepromorphism thing.

nimish 12 years ago | |

You might as well make a datatype for "HashLiterals":

    data HashLiteral a = HashLiteral { _character :: Char, _trailingChars :: [Char], _representation :: [Char] -> a}

(Underscores for lenses) And then ``hashLiteralInfo :: [HashLiteral a]`` rather than an ad-hoc thing.

Then you could do something like

    binHashLiteral = HashLiteral { _char = 'b', _parser = Just . many . oneOf "01", _representation = Number . toInteger . fromBase 2 }

which has a nicer type (HashLiteral Number) than some weird nested tuple.

breckinloggins 12 years ago | | |

I gave this a try but ended up going with tmhedberg's suggestion because it (as he said) allowed me to stay with lookup. I would use a richer data structure except for the parseHashLiteral function just needs to return a Parser LispVal anyway, so there's nothing "richer" just yet.

However, if I decide to go forward with some of the more advanced things in the tutorial like threading good error messages and such, I'm pretty sure some new data types are in my future.

Also, when you say "underscore for lenses", did you mean that your example would be pretty clean with the Lenses library? I've been looking for an excuse to learn that so if so I'd love to learn more!

tmhedberg 12 years ago | | |

This simplifies the type signature, but doesn't avoid the need for `return $ f "unneeded"`, which seems to be the ugly part he was really hoping to eliminate.

Also, now you have to write your own lookup function instead of just using Prelude.lookup.

stiff 12 years 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

magal 12 years ago | |

Or Chaitin's http://www.umcs.maine.edu/~chaitin/lisp.c

kaoD 12 years ago | |

Yeah but... which spec?

(pun intended)

dugmartin 12 years 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.

emeraldd 12 years ago |

If you find that interesting, you should probably take a look at this:

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!

pdelgallego 12 years 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

mnemonik 12 years 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 12 years 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 12 years ago | |

Looks very interesting; I already had a shot at implementing a subset of scheme using F# (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.

mnemonik 12 years ago | |

Really loved the sense of community that sprouted up around those articles :) I remember everyone following each other's projects on github, and the discussions in the comments on the blog posts. Good memories :)

I should finish my Ada version sometime... Or just start a new project haha

yfefyf 12 years ago | |

Thank you for this link.

groovy2shoes 12 years 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.

cninja 12 years ago | |

I couldn't agree more. Writing my own interpreter 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.

dominicrodger 12 years ago | |

Likewise - I did this as part of a hackathon earlier this year - thoroughly enjoyed seeing how all the pieces fitted together.

jws 12 years ago |

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

hga 12 years 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 12 years ago | | |

Details, please? (If you're so inclined.)

mrottenkolber 12 years ago |

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

erik14th 12 years ago |

https://github.com/JeffBezanson/femtolisp

Lisp implementation from one of the julialang devs

dschiptsov 12 years 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.

klrr 12 years ago |

This is the best beginner project.

kybernetikos 12 years ago | |

Which is why there's so many of them out there. (For example my own: http://kybernetikos.github.io/Javathcript/ )

weavie 12 years ago | | |

Yours wins on the name.

fabriceleal 12 years ago |

Already down? Google-cached: http://webcache.googleusercontent.com/search?q=cache:https:/...

matt_ 12 years ago | |

Was down for me, thanks for the link.

emeraldd 12 years ago | |

Looks up to me.

ktg 12 years ago |

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

mathattack 12 years ago |

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

emeraldd 12 years 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.

inginist 12 years ago |

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

cabalamat 12 years 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

nicholasjbs 12 years 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 12 years 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 12 years 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 12 years 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 12 years ago | | |

Under the aesthetics of logic, I find Lisp's syntax pretty as well.

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)) ]

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

hashLiteralInfo = [ ('f', pure $ Bool False) , ('t', pure $ Bool True) , ('b', fmap (Number . toInteger . fromBase 2) (many $ oneOf "01")) -- ... and so on ]

parseHashLiteral :: Parser LispVal parseHashLiteral = do char '#' c <- oneOf $ map fst hashLiteralInfo case lookup c hashLiteralInfo of Just x -> x Nothing -> fail "Internal parse error: unregistered literal info"