Saturday, March 24, 2012

Lazp: an untyped, lazy, functional language with support for runtime metaprogramming

So far, the only untyped, lazy language I've found that's being maintained is Lazy Racket.  I've been interested in Lambda Calculus for a while, though, and LISP/Scheme aren't quite what I want (and they're quite a bit larger, too), so I decided to extend the Lambda Calculator into a standalone language.  Here's the repository.  The goal is to make it native, but for now, it's still in JavaScript, although it will run "standalone" in node.js (and also in browsers).  Here are the language features I'm interested in:
  • lazy, so no side effects, because they can really mess up a lazy language
  • untyped; Haskell is already there for typed, lazy languages
  • metaprogramming; the eval function uses ASTs that are LC functions
    • We'll rewrite Lazp's parser and code generators in Lazp, so it's self-hosting
    • I "hand assembled" the AST functions, so they're in Lazp, already
    • This means metaprogramming in Lazp can happen at parse time and also at runtime (hey, just like in FORTH!)
Want to see how to make a Lazp AST?  Good, I thought you would!  Here are the functions you use to construct them (love me some bullet lists):
  • _lit v -- literal value
  • _ref v -- variable reference: v should be a string
  • _lambda var body -- lambda binding: var should be a string or number, body is an AST
  • _apply func arg -- function application: func can be any AST function except a _prim
  • _prim arg rest -- primitive call: rest is either a _lit, a _ref, or another _prim (which allows more args)
  • _name name ast -- name a type
Here how they are defined in Lambda Calculus.  These are just "standard" LC data structures; you call the function with some data and it returns you a function representing the data structure.  When you want to access a part of the data structure, you pass in a function that takes all the pieces are arguments and do what you want with them.  I'm putting arguments on the left of the '=', which will hopefully make it easier to read (and I'm adding that change to Lazp's syntax) -- you can use \ instead of λ, of course, if you can't find your λ key...
  • _lit x = λf . f x
  • _ref x = λf . f x
  • _lambda v f = λg . g v f
  • _apply func arg = λf . f func arg
  • _prim arg rest = λf . f arg rest
  • _name nm ast = λf . f nm ast
So, say you want to make an AST for the "true" function, λa b . a -- here's how it would look: _lambda a (_lambda b (_ref a)).  Looks almost like LISP, doesn't it (no coincidence, there).

So, what's already working?  I had a big advantage, here, because I could use the Lambda Calculator as a prototype.  So, right now, this returns "hello":
    eval (_apply (_lambda x (_ref x)) (_lit hello))
     This calls eval with an AST that applies the identity function to "hello".

    The code's in Coffeescript and the parser and code generator is all in one file with no dependencies, called Lazp.cs (about 375 lines of code).

    I'm looking for help on this, so feel free to leave a comment if you're interested and feel free to fork it in Github; it's licensed with Zlib.