Anyone know of any "toy" optimizing compilers for ...
# of-functional-programmings
S.M Mukarram Nainar
05/20/2020, 2:11 AMAnyone know of any "toy" optimizing compilers for a functional programming language that are small enough to study and fit in head? Looking for learning resources.
Tangentially, are there any nanopass compilers that are used outaide of education?
w
wtaysom
05/20/2020, 3:50 AMMentioning "nanopass" suggests that I wouldn't have much to add. 😉
e
eyal
05/20/2020, 9:16 AMFor a small Hindley Milner (Algorithm W) type checker check out this introductory paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65.7733&rep=rep1&type=pdf
and Lennart Augustusson has a few toy compilers for various small languages in his blog, e.g:
http://augustss.blogspot.com/2007/06/simple-compiler-in-my-last-post-i.html
d
Doug Moen
05/20/2020, 12:25 PM"A nanopass framework for commercial compiler development" (for Chez Scheme) by Andy Keep. http://andykeep.com/pubs/dissertation.pdf
Doug Moen
05/20/2020, 12:28 PMThis project is open source and active. http://nanopass.org/ and https://github.com/nanopass
Doug Moen
05/20/2020, 12:31 PMThis is something I want to learn more about myself. I'm not happy with the compiler I wrote for my own functional language.
Doug Moen
05/20/2020, 12:34 PMThis blog post compares the nanopass approach to building a parser using parser combinators. <https://blog.sigplan.org/2019/07/09/my-first-fifteen-compilers/> I hope the analogy is correct, because building a compiler by composing simple generic functional building blocks sounds like just the approach I need.
❤️ 1
Doug Moen
05/20/2020, 12:46 PMDigging more into the idea of constructing a compiler by composing combinators. Here's a one page compiler written this way in Haskell that "accepts a Turing-complete language and produces WebAssembly". It's not an optimizing compiler, though. https://crypto.stanford.edu/~blynn/lambda/sk.html
Doug Moen
05/20/2020, 12:59 PMAccording to somebody on Hacker News <https://news.ycombinator.com/item?id=15153956>,
Chez Scheme [0] is written using the nanopass framework, and it's regarded as one of the fastest Scheme compilers in existence [1]. Before it was rewritten to use the nanopass system, Chez's compiler was known for its performance in terms of lines of code compiled per second; the rewrite slowed it down a bit, but the quality and performance of generated machine code improved. Andy Keep and Kent Dybvig wrote a paper about the project [2]. I haven't browsed the Chez source, but it's a good way to answer your question.
[0] https://github.com/cisco/ChezScheme
[1] http://ecraven.github.io/r7rs-benchmarks/benchmark.html
[2] https://www.cs.indiana.edu/~dyb/pubs/commercial-nanopass.pdf
Doug Moen
05/20/2020, 1:03 PMLooking at the ChezScheme repository on github, it uses the nanopass framework on github (that I linked to earlier) as a dependency.
d
Dan Cook
05/20/2020, 6:53 PMI really liked this programming language walkthrough for compiling a "regular looking" (looks imperative) language to continuation passing style (behaves like scheme + CPS):
http://lisperator.net/pltut/
s
S.M Mukarram Nainar
05/21/2020, 6:01 PMThanks everyone!
I didn't know chez was rewritten in nanopass, that's neat.
b
Boarders
06/18/2020, 5:41 PMI think Lisp in Small Pieces or Appel's Compiling with Continuations might have some good basic optimisation techniques but I would also love to know a good resource for this!
4 Views