4 ms·

Compiling to λ-calculus

114 points by sindoc 15y ago

russellallen 15y ago
This is more of a meta-comment, but it is always interesting seeing links like this (here on Hacker News and elsewhere) which attract a fair number of upvotes, but no comments. Perhaps we're all afraid of looking stupid... easier to discuss Job's retirement or something less scary :) Anyway, to drop down a metalevel, this is fabulous but also interesting for what the lambda calculus doesn't talk about - concurrency and more broadly time. I'd like to see more pages like this but which come from an actor model of computation or some other process calculus.
- mattmight 15y ago
  Would you like a "Compiling over to the pi-calculus" article?
  - russellallen 15y ago
    Definitely. If done in the same general style as your lambda calculus one I think it would be a great resource.
  - jsherman 15y ago
    Registered for HN just to say I'd love to see this
  - hughmanatee 15y ago
    Matt, I've read several articles on your site and wanted to say thanks for writing them. I'd be very interested in reading an article about compiling to the pi-calculus.
  - maaku 15y ago
    Somebody please write this.
  - mahmud 15y ago
    Yes please :-)
- lukesandberg 15y ago
  the lambda calculus doesn't talk about concurrency but it does discuss time. like turing machines there is a concept of time inasmuch as a particular algorithm will take so long to complete (complexity). The reason it doesnt talk about concurrency is because concurrency doesn't bring anything to the table in terms of deciding complexity or computability. to be a little more blunt :) Talking about concurrency in the lambda calculus is like talking about concurrent math or paralelizing the concept of addition (not an implementation).
- 5hoom 15y ago
  I often find that I want to comment on stories like this to express my enthusiasm for an interesting topic, but yeah I know that by doing so there is the risk that I'll expose myself as being pretty naive & unsophisticated in an advanced subject. And I'd be doing this in front of a large audience of very intelligent yet potentially ruthless peers ;)
rpearl 15y ago
It is interesting that your compilers class targets the lambda calculus. While we have a thorough curriculum on functional programming at CMU (and for one class I did write several compilers which took more complex languages and translated them to the lambda calculus and even more minimalistic languages like the SK (optionally I) combinator calculus, that class wasn't on compilers, it was "Principles of Programming Languages". It also covered type theory, implementing type inference, and so on. Whereas our compilers class covers the sort of topics you would expect in a compiler targeting a real architecture: parsing/lexing, choosing intermediate languages, SSA form, optimizations, register allocation, code generation, and so on. We have a separate class which covers compiling higher order typed languages (SML in particular). Our compilers class is also unusual (in ones I have seen) in that, instead of building a lexer, building a parser, doing translation, and so on for each stage, as separate projects, rather students build a whole compiler for each assignment. The language compiled gains more and more features: first control flow, then function calls, then memory operations (structs, arrays, heap-allocation). Might I ask your thinking when choosing the lambda calculus as the basis for your compilers class?
- dill_day 15y ago
  FWIW, if you follow the link to his compilers class page, you can see that the projects do in fact deal with traditional topics: Lexical analyzer Parser High-level translator Normalizer & CPS converter Low-level translator Register allocator & Assembly code emitter Anyway, when I took compilers it was similar to yours -- each week we compiled larger subsets of Python to x86.
- mattmight 15y ago
  It was a normal compilers class. We compiled Python. This was just an exercise for week one.
- mahmud 15y ago
  CMU has the most rigorous CS corriculum, specially fo PL research, FP & compilers.
DanielRibeiro 15y ago
Very nice. It would be nice to see it compiling down to the typed lamba calculus as well[1] [1] http://math.ucr.edu/home/baez/rosetta.pdf http://math.ucr.edu/home/baez/rosetta.pdf , pg55
- lemming 15y ago
  And while we're taking requests, one in a similar style on type inference would be great too.
  - motxilo 15y ago
    You can examine Chapter 4 of Essentials of Programming Languages for the basics of type inference ;)

114 points by sindoc 15y ago

This is more of a meta-comment, but it is always interesting seeing links like this (here on Hacker News and elsewhere) which attract a fair number of upvotes, but no comments. Perhaps we're all afraid of looking stupid... easier to discuss Job's retirement or something less scary :) Anyway, to drop down a metalevel, this is fabulous but also interesting for what the lambda calculus doesn't talk about - concurrency and more broadly time. I'd like to see more pages like this but which come from an actor model of computation or some other process calculus.

mattmight 15y ago
Would you like a "Compiling over to the pi-calculus" article?
- russellallen 15y ago
  Definitely. If done in the same general style as your lambda calculus one I think it would be a great resource.
- jsherman 15y ago
  Registered for HN just to say I'd love to see this
- hughmanatee 15y ago
  Matt, I've read several articles on your site and wanted to say thanks for writing them. I'd be very interested in reading an article about compiling to the pi-calculus.
- maaku 15y ago
  Somebody please write this.
- mahmud 15y ago
  Yes please :-)
lukesandberg 15y ago
the lambda calculus doesn't talk about concurrency but it does discuss time. like turing machines there is a concept of time inasmuch as a particular algorithm will take so long to complete (complexity). The reason it doesnt talk about concurrency is because concurrency doesn't bring anything to the table in terms of deciding complexity or computability. to be a little more blunt :) Talking about concurrency in the lambda calculus is like talking about concurrent math or paralelizing the concept of addition (not an implementation).
5hoom 15y ago
I often find that I want to comment on stories like this to express my enthusiasm for an interesting topic, but yeah I know that by doing so there is the risk that I'll expose myself as being pretty naive & unsophisticated in an advanced subject. And I'd be doing this in front of a large audience of very intelligent yet potentially ruthless peers ;)

rpearl 15y ago

It is interesting that your compilers class targets the lambda calculus. While we have a thorough curriculum on functional programming at CMU (and for one class I did write several compilers which took more complex languages and translated them to the lambda calculus and even more minimalistic languages like the SK (optionally I) combinator calculus, that class wasn't on compilers, it was "Principles of Programming Languages". It also covered type theory, implementing type inference, and so on. Whereas our compilers class covers the sort of topics you would expect in a compiler targeting a real architecture: parsing/lexing, choosing intermediate languages, SSA form, optimizations, register allocation, code generation, and so on. We have a separate class which covers compiling higher order typed languages (SML in particular). Our compilers class is also unusual (in ones I have seen) in that, instead of building a lexer, building a parser, doing translation, and so on for each stage, as separate projects, rather students build a whole compiler for each assignment. The language compiled gains more and more features: first control flow, then function calls, then memory operations (structs, arrays, heap-allocation). Might I ask your thinking when choosing the lambda calculus as the basis for your compilers class?

dill_day 15y ago
FWIW, if you follow the link to his compilers class page, you can see that the projects do in fact deal with traditional topics: Lexical analyzer Parser High-level translator Normalizer & CPS converter Low-level translator Register allocator & Assembly code emitter Anyway, when I took compilers it was similar to yours -- each week we compiled larger subsets of Python to x86.
mattmight 15y ago
It was a normal compilers class. We compiled Python. This was just an exercise for week one.
mahmud 15y ago
CMU has the most rigorous CS corriculum, specially fo PL research, FP & compilers.

DanielRibeiro 15y ago

Very nice. It would be nice to see it compiling down to the typed lamba calculus as well[1] [1] http://math.ucr.edu/home/baez/rosetta.pdf http://math.ucr.edu/home/baez/rosetta.pdf , pg55

lemming 15y ago
And while we're taking requests, one in a similar style on type inference would be great too.
- motxilo 15y ago
  You can examine Chapter 4 of Essentials of Programming Languages for the basics of type inference ;)