4 ms·

Parsing the untyped λ-calculus with Parsec

28 points by wetmore 11y ago

PieSquared 11y ago
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/ http://learnyouahaskell.com/
- wetmore 11y ago
  Glad the explanation helped, especially since I sort of skimped on the details and just pointed to wikipedia :P
optimusclimb 11y ago
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 https://gist.github.com/shermany/ad41ccf93fc969c5d759
platz 11y ago
> λx.x can be written as λ.0 Reading the wikipedia entry, I thought it would be written as λ.1
- wetmore 11y ago
  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.
TheLoneWolfling 11y ago
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)

28 points by wetmore 11y ago

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/ http://learnyouahaskell.com/

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

optimusclimb 11y ago

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 https://gist.github.com/shermany/ad41ccf93fc969c5d759

platz 11y ago

> λx.x can be written as λ.0 Reading the wikipedia entry, I thought it would be written as λ.1

wetmore 11y ago
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.

TheLoneWolfling 11y ago

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)