One of my own old blog posts. Incrementally refactors normal Enumerator and Observer interfaces (in the object-oriented sense) using algebraic reasoning, gradually bringing them closer and closer to realistic networking protocols, and quite quickly arriving at a place where the networking concepts of “acknowledgement of messages” and “flow control to avoid overwhelming a receiver” fall out for free.

A short tutorial on algebraic data types, useful tools for reasoning about and refactoring data structures:

In what sense are data types algebraic? […] Isn’t this all just a bunch of general abstract nonsense? We’ll investigate these questions, and perhaps demystify this important concept of functional languages.

An example of how these ideas can help can be seen in my old blog post on The Origins of Flow Control and Acknowledgements.

(Aside: this post’s link seems to be to a rescued copy of the text, which was originally at http://blog.lab49.com/archives/3011.)

A cool recent Smalltalk VM based directly on Smalltalk-80 and closely following the classic “Blue Book” design, but somewhat modernized and implemented in Rust. Straighforward and understandable.

An interactive tool for seeing how various compilers (GCC, Clang, MSVC, rustc, etc.) produce machine code for various architectures at various optimisation levels.

Squeak is a direct descendant of the Smalltalk-80 system. Lots to criticise, lots to be inspired by. One of my favourite operating systems, one of my favourite programming languages! Not that it couldn’t be better, of course…

A recent ML-family language design:

1SubML is an experimental ML-like programming language with a unified module and value language, structural subtyping, global type inference, higher rank polymorphic types, existential types, higher kinded types (no partial application), recursive types, worst-case polynomial time type checking and much more.

A slightly rambly but rich discussion of Pratt parsing, a parsing technique that is very simple, on the one hand, but surprisingly powerful and subtle, on the other.

Laurence Tratt explains a relatively simple new meta-tracing-based technique for adding a JIT compiler to an existing C-based interpreter:

What might surprise you is that we only added about 400LoC to PUC Lua, and changed under 50LoC. This hopefully makes the trade-off yk offers clear: yklua does not reach the performance peaks of the wonderful, carefully hand-written, LuaJIT; but LuaJIT is stuck in the 13 year old past of Lua 5.15, whereas yklua trivially tracks updates to PUC Lua. The point of this post isn’t to tell you that one side or the other of this trade-off is best. Rather, it’s to show that the trade-off exists, and that yk fills in a part of the design space that was largely out of bounds before.

Many programming languages have some kind of representation of a stream, a sequence of bytes (or objects) that can be processed a chunk at a time, filtered, transformed, composed, pipelined, split, merged and so on. JavaScript is no exception, but historical peculiarities of the language have left it in kind of a bad place for the ergonomics of using streams. So this article discusses improvements that could be made. PL students take note: we’ve moved on from mere syntax and semantics to the squishy yet ultimately valuable worlds of ergonomics and pragmatics!

Musings on the topic of “input shapes” in context of fuzz testing (a powerful automated software testing technique), and why they are important:

I propose that there are two types of inputs: instruction-like and data-like. Of course, there is some overlap where, for example, an instruction contains data, or data contains instructions, but fundamentally, this is what inputs are consumed as by the program. For both of these types, you have three shapes: linear, tree, and directed graph.

The importance of (and tricks for) doing proofs about code you’re writing as you write it:

This is a brief write-up of a trick I learned that helps me write code faster and more accurately. I say “trick”, but it’s really something I started to do without noticing as I moved further into my career.

When you’re working on something difficult, sketch a proof in your head as you go that your code will actually do what you want it to do. A simple idea, but easier said than done: doing this “online” without interrupting your flow takes a lot of practice. But once you get really good at it, you’ll find that a surprising amount of the time your code will work on the first or second try. It feels a little magical.

(via John Regehr)

An interactive web tool that simulates various garbage collection algorithms running over a user-specified concrete heap. Also illustrates a simple tagging/object-header scheme. (Note that the “About” page is hidden away in a hamburger menu at the top right.)

An elegant example of FP for the FP portion of my PL course:

A simple, useful, plain-text variant of Donald Knuth’s paragraph-filling algorithm can be expressed as a fold. This algorithm runs in time linear to the length of its input and usually produces better results than the classic greedy text-flow algorithm.

Makes explicit the connection between the Visitor design pattern and sum types (a.k.a. tagged unions / algebraic data types).

An excellent paper that skewers the common cultural understanding of the C programming language as being a “low-level” or “portable assembly” language. Modern CPUs have diverged so far from the C abstract machine that C no longer provides predictable “close-to-the-metal” guarantees.

A concrete and formal definition of memory safety from (inter alia) Benjamin C. Pierce.

We give a rigorous characterization of what it means for a programming language to be memory safe, capturing the intuition that memory safety supports local reasoning about state.

Paper in the proceedings of the Principles of Security and Trust conference 2018.

Development of incremental improvements to a pure-functional quicksort implementation, eliminating multiple passes over the input and unnecessary append operations by introducing accumulators.

Neel Krishnaswami remembers John Reynolds. One particular quote that struck me (highlighted by Lindsey Kuper) is this:

So this was John [Reynolds]’s definition of a successful language design: if you have a user who has used it to write a program you couldn’t have, your language has succeeded, since it has helped a fellow human being solve one of their own particular problems.

I’ve always liked his definition, since it manages to avoid an obsession with nose-counting popularity metrics, while still remembering the essentially social purpose of language design.”

Programming languages are about people!

The OOPSLA 1997 paper that introduced Squeak, a Smalltalk implementation “written in itself”:

Squeak is an open, highly-portable Smalltalk implementation whose virtual machine is written entirely in Smalltalk, making it easy to debug, analyze, and change. To achieve practical performance, a translator produces an equivalent C program whose performance is comparable to commercial Smalltalks.

The paper discusses the bootstrapping process, the VM’s object format and garbage collector, the Smalltalk-subset-to-C translation process, the implementations’ approach to the BitBlt graphics primitive, performance, and the fledgling Squeak community. The latter is still going strong thirty-some years later.