breckinloggins on Little Lisp interpreter

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 13y

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 13y

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 13y

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 13y

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

tel 13y

Excellent!

I'm definitely going to go through Edward Kmett's recursion-schemes library which has the zygohistoprepromorphism in it. While I plan to cover topics to make comprehension of the zhppm easier, I don't know that I'll examine it in particular.

Unless I just do for fun, because it's not actually terrifically complex... just sort of a joke name for a relatively simple, abstract idea.

nimish 13y

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 13y

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 13y

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.

Comments