Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Little Lisp interpreter

hackerschool.com

Post reply on HN
Print view View original

31–40 of 49 posts

Re: Little Lisp interpreter

#32

Post by tmhedberg »

breckinloggins wrote: post #30

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 a…

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.

Re: Little Lisp interpreter

#33

Post by magal »

stiff wrote: post #29

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

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

Re: Little Lisp interpreter

#34

Post by emeraldd »

mathattack wrote: post #26

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

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.

Re: Little Lisp interpreter

#35

Post by nimish »

breckinloggins wrote: post #30

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 a…

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.

Re: Little Lisp interpreter

#36

Post by tmhedberg »

nimish wrote: post #35
breckinloggins wrote: post #30

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 a…

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

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.

Re: Little Lisp interpreter

#37

Post by breckinloggins »

tmhedberg wrote: post #32
breckinloggins wrote: post #30

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 a…

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…

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  x
            Nothing -> fail "Internal parse error: unregistered literal info"

Re: Little Lisp interpreter

#38

Post by breckinloggins »

nimish wrote: post #35
breckinloggins wrote: post #30

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 a…

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

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!

Re: Little Lisp interpreter

#39

Post by patrickmay »

hga wrote: post #28
jws wrote: post #18

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

"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.)

Details, please? (If you're so inclined.)
Post reply on HN