Parsing the untyped λ-calculus with Parsec

Parsec is what originally got me interested in Haskell. I had played around with it via LYAH [0] before, but never really got into it. I wanted to write a compiler for a language I was playing with, and seeing Parsec convinced me I should dive in and learn Haskell, as it just lets you write parsers in an incredibly intuitive and quick way; for me at least, parser combinator libraries are much easier to use than parser generators, and are also a lot more modular.

Even if you're familiar with parsec and parsing in Haskell, this post includes a fairly good explanation of De Bruijn indices. I've seen them a few times already but this explanation made it click particularly well.

[0] Learn You a Haskell: http://learnyouahaskell.com/

Interestingly enough, I've been playing around with parsing the same thing lately, albeit in Python with a simple recursive descent parser (with exceptions for control flow, which actually works surprisingly well.)

A lot of the same ideas. And indeed, much of the parser is pretty close to the same:

    def parseAbst(self):
        self.expect('λ')
        varName = self.expect(self.parseVar)
        self.pushVar(varName)
        self.expect('.')
        exprTree = self.expect(self.parseExpr)
        return abst(varName, exprTree)

(I also have self.accept, etc.)

(Of course, much of the complexity is hosted to the class surrounding this)

Woah...this takes me back a long time.

Posting just in case anyone finds it interesting...here's an (admittedly weak) lambda calculus interpreter, in Oz:

https://gist.github.com/shermany/ad41ccf93fc969c5d759

> λx.x can be written as λ.0

Reading the wikipedia entry, I thought it would be written as λ.1