5 ms·

Show HN: Compiler Fundamentals – Closure Conversion

70 points by rain1 8y ago

rain1 8y ago
I took the essence of closure conversion and implemented it as a single file racket script with explanation in comments and examples. The idea is that this should help someone if they are a beginner wanting to implement a language that has lambda. Or anybody who is curious how a compiler might implement lambda.
sinistersnare 8y ago
I also made a closure converting pass to my compiler (in racket also!) Here's mine: https://github.com/sinistersnare/SinScheme/blob/master/src/racket/closure-convert.rkt https://github.com/sinistersnare/SinScheme/blob/master/src/r...
- abecedarius 8y ago
  Yet another: this is the whole compiler, but for a simpler language and target. https://github.com/darius/squeam/blob/master/eg/lambdacompiler.scm https://github.com/darius/squeam/blob/master/eg/lambdacompil... It's in my own Scheme variant, I'm afraid. I guess I should translate it to something people know. But, for example ;; Variable reference (to (var-ref<- v) (make ({.free-vars} (set<- v)) ({.compile s k} (cons (s v) k)))) turns a source-code variable access into an AST object with two methods: 1. The free-variable set of this AST has just that one variable. 2. To compile this to bytecode, given a scope s and following code k, ask the scope what instruction to emit for this variable, and prepend that to k. (In general k is passed in for the sake of tail-call optimization, on line 33.)
tinco 8y ago
Lisps look so magical. I wish it were more accepted in the web application industry to pick a lisps for implementing services. I love my Ruby, and my Go, but it would be fun to experiment with a lisp some time.
- blevs 8y ago
  Clojure and Clojurescript are both amazing. If you have the time they are absolutely worth playing around with.
deleted 8y ago
[deleted]
disconcision 8y ago
this is just a tiny nitpick but I'm wondering why you didn't use pattern matching? if you just wanted to stay schemey then disregard but you could skip the entire shapes section and the rest of the code would still be terser, e.g. ((begin? exp) `(begin . ,(mapply cc (cdr exp) sc))) would become [`(begin ,xs ...) `(begin ,@(mapply cc xs sc))] or if you're feeling fancy (define cc-sc (curryr cc sc)) [`(begin ,(app cc-sc xs) ...) `(begin ,@xs)]
rurban 8y ago
A shorter version in C: https://github.com/perl11/potion/blob/master/core/compile.c#L198 https://github.com/perl11/potion/blob/master/core/compile.c#...

70 points by rain1 8y ago

I took the essence of closure conversion and implemented it as a single file racket script with explanation in comments and examples. The idea is that this should help someone if they are a beginner wanting to implement a language that has lambda. Or anybody who is curious how a compiler might implement lambda.

sinistersnare 8y ago

I also made a closure converting pass to my compiler (in racket also!) Here's mine: https://github.com/sinistersnare/SinScheme/blob/master/src/racket/closure-convert.rkt https://github.com/sinistersnare/SinScheme/blob/master/src/r...

abecedarius 8y ago
Yet another: this is the whole compiler, but for a simpler language and target. https://github.com/darius/squeam/blob/master/eg/lambdacompiler.scm https://github.com/darius/squeam/blob/master/eg/lambdacompil... It's in my own Scheme variant, I'm afraid. I guess I should translate it to something people know. But, for example ;; Variable reference (to (var-ref<- v) (make ({.free-vars} (set<- v)) ({.compile s k} (cons (s v) k)))) turns a source-code variable access into an AST object with two methods: 1. The free-variable set of this AST has just that one variable. 2. To compile this to bytecode, given a scope s and following code k, ask the scope what instruction to emit for this variable, and prepend that to k. (In general k is passed in for the sake of tail-call optimization, on line 33.)

tinco 8y ago

Lisps look so magical. I wish it were more accepted in the web application industry to pick a lisps for implementing services. I love my Ruby, and my Go, but it would be fun to experiment with a lisp some time.

blevs 8y ago
Clojure and Clojurescript are both amazing. If you have the time they are absolutely worth playing around with.

deleted 8y ago

[deleted]

disconcision 8y ago

this is just a tiny nitpick but I'm wondering why you didn't use pattern matching? if you just wanted to stay schemey then disregard but you could skip the entire shapes section and the rest of the code would still be terser, e.g. ((begin? exp) `(begin . ,(mapply cc (cdr exp) sc))) would become [`(begin ,xs ...) `(begin ,@(mapply cc xs sc))] or if you're feeling fancy (define cc-sc (curryr cc sc)) [`(begin ,(app cc-sc xs) ...) `(begin ,@xs)]

rurban 8y ago

A shorter version in C: https://github.com/perl11/potion/blob/master/core/compile.c#L198 https://github.com/perl11/potion/blob/master/core/compile.c#...