primlisp

https://github.com/Munksgaard/primlisp

Well, it turns out that my initial plan was too ambitious. What a surprise. The plan was to implement an interpreter for a very simple lisp. Unfortunately, I had stuff to do, so I only got as far as the parser.

The parser is implemented using rust-peg, a Rust library for parsing expression grammers. As such, the entire parsing is as simple as

read -> super::AST
    = cons / integer / nil / symbol

cons -> super::AST
    = "(" space car:read space "." space cdr:read space ")"
    { super::AST::Cons(Box::new(car),
      Box::new(cdr)) }

nil -> super::AST
    = "()" { super::AST::Nil }

integer -> super::AST
    = sign:"-"? n:num
    { super::AST::Integer(if sign.is_some() { - n } else { n }) }

symbol -> super::AST
    = [a-zA-Z][a-zA-Z0-9\-]* { super::AST::Symbol(match_str.to_string()) }

num -> isize
    = [0-9]+ { match_str.parse().unwrap() }

space -> ()
    = [ \n\t]*

which I think is quite elegant. Of course, primlisp can only handle integers, cons-cells, nil and symbols, so that explains the extremely simple grammar, but still.

I was going to make primlisp a Lisp-1 for simplicity, but I've run into a roadblock when trying to define a symbol-table. With lispski it was easy: Lisp is untyped, so I could just stuff closures into the table, but what is the type of a symbol-table?

Right now, I'm going for a vector of (String, Something), where the String is the symbol name, and the Something is… something else. What are possible values for Something? Symbols should be bindable to integers, nil, conses, functions (both primitive and compound). So an enum like

enum Something {
    Integer(AST::Integer),
    Nil,
    Cons(AST::Cons),
    PrimFun(SomeType),
    CompoundFun(SomeType2),
}

So far so good, but what is SomeType? Primitive functions include cons and car, but they have different types: cons: Fn(AST, AST) -> AST and car: Fn(AST) -> AST. I could curry them, like in lispski, but then cons would just be cons: Fn(AST) -> Fn(AST) -> AST, and that's no good either.

I'm rambling, and now I'll go to bed. Perhaps tomorrow I'll think of something.