はてなブックマーク

I wrote previously about different slices of life in the various implementations of the Scrapscript programming language. Until two weeks ago, the most interesting implementation was a so-called “baseline compiler” directly from the AST to C. Now we have an intermediate representation—an IR. Why add an IR? The AST is fine. It’s a very abstract representation of the progam text and it is easy to ge

C-Reduce is a tool by Regehr and friends for minimizing C compiler bug reproducers. Imagine if you had a 10,000 line long C file that triggered a Clang bug. You don’t want to send a massive blob to the compiler developers because that’s unhelpful, but you also don’t want to cut it down to size by hand. The good news is that C-Reduce can do that for you. The bad news is that everyone thinks it only

Intro to HM Damas-Hindley-Milner (HM) is a type system for Standard ML and the ML-family languages. River and I wrote about it earlier this month. Check out that post if you would like an introduction or refresher. In this post, we’ll add row polymorphism to it. We’ll do it in the context of scrapscript’s implementation of Algorithm J, but the core ideas should be language and algorithm-independen

CF Bolz-Tereick wrote some excellent posts in which they introduce a small IR and optimizer and extend it with allocation removal. We also did a live stream together in which we did some more heap optimizations. In this blog post, I’m going to write a small abtract interpreter for the Toy IR and then show how we can use it to do some simple optimizations. It assumes that you are familiar with the

Scrapscript is a small, pure, functional, content-addressable, network-first programming language. My previous post introduced the language a bit and then talked about the interpreter that Chris and I built. This post is about the compiler that Chris and I built. In the beginning, there was an interpreter Writing a simple tree-walking interpreter is a great way to prototype a language implementati

It’s been nine whole years since PEP 484 landed and brought us types from on high. This has made a lot of people very angry and been widely regarded as a bad move1. Since then, people on the internet have been clamoring to find out: does this mean we can now compile Python to native code for more speed? It’s a totally reasonable question. It was one of my first questions when I first started worki

This page is a collection of my favorite resources for people getting started writing programming languages. I hope to keep it updated as long as I continue to find great stuff. I made a fun compilers t-shirt and also a fun JIT compilers t-shirt Compilers Tufts compilers course COMP/CS 181 (2006, but it’s been taught more recently. I should probably ping Sam.) Cornell compilers course CS 6120 and

Tiger got to hunt, Bird got to fly; Lisper got to sit and wonder, (Y (Y Y))? Tiger got to sleep, Bird got to land; Lisper got to tell himself he understand. -- Kurt Vonnegut, modified by Darius Bacon

Many thanks to Kartik Agaram and Leonard Schütz for proofreading these posts. In my last series, I wrote about building a Lisp interpreter. This time, we’re going to write a Lisp compiler. This series is an adaptation of Abdulaziz Ghuloum’s excellent paper An Incremental Approach to Compiler Construction, with several key differences: Our implementation is in C, instead of Scheme Our implementatio

Two fun things happened recently and the proximity of the two made something go click in my head and now I think I understand how bytecode interpreters work. I went to a class at work called “Interpreters 101” or something of the sort. In it, the presenter walked through creating a dead-simple tree-walking Lisp interpreter. Then he ended by suggesting we go out and re-implement it as a bytecode in