Parsing the untyped λ-calculus with Parsec

[wetmore]

http://mattwetmore.me/posts/parsing-combinators-with-parser-combinators.html

[PieSquared]

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/

[wetmore → PieSquared]

Glad the explanation helped, especially since I sort of skimped on the details and just pointed to wikipedia :P

[TheLoneWolfling]

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)

[optimusclimb]

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

[platz]

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

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

[wetmore → platz]

Oof, that's my mistake, I didn't notice that the indexing system TAPL uses starts at 0, while Wikipedia starts at 1. I'll add a note about that to the post now.