All the control flow you'll ever need

 

(b?f:g)(x)

 Tongue in cheek, of course. Control flow corresponds to determining what (part of a) program you will run next and, of course, you can always compile down to lambda calculus in an abstract sense.

 

Why compiling with continuations is wrong(-ish)

There are two axes to plot programming languages, eager/lazy and strict/permissive. Eager/lazy are two evaluation models, strict/permissive determines how much a language sticks to the chosen model.

Most languages are very eager, usually except for short-circuited boolean operators, and reasonably strict, the order of evaluation is mostly known. Non-strictness is often exploited by compiler writers to reorder expressions for performance; i.e., one might not know precisely in what order '2*x+3*y' is evaluated but it will be fast.

Lazy languages like Haskell and Clean, are mostly lazy and permissive, entire program fragments might be reordered or made eager due to purity. All for performance reasons.

Order of evaluation is of course important, all programmers need to deal with it - albeit less in pure languages. Compiler writers need to deal with it too, a popular manner of writing a Scheme compiler is to transform to continuation passing style since that will make the order of evaluation explicit but also allows for control flow operators.

Let's dive into that a bit with a small snippet of code.

pyth x y = sqrt (add (pow2 x) (pow2 y))

After transformation to continuation passing style, one ends up with:

pyth' x y cont = pow2' x (\x2 -> pow2' y (\y2 -> add' x2 y2 

                                 (\anb -> sqrt' anb cont)))

This transformation is of course global, all functions get a continuation object as an extra argument, and all functions are defined as complex expressions that pass along continuations. It's also a pretty bad manner of writing a program if it weren't for that this style serves well as an intermediate representation for compilation to a backend since it makes order of evaluation and temporary values explicit. Fantastic, done!

The Egel interpreter internally also uses an intermediate representation prior to outputting to bytecode. Let's look at that.

pyth x y =

    let y2 = pow2 y in

    let x2 = pow2 x in

    let anb = add x2 y2 in sqrt anb

The intermediate representation hoists reducible expressions, redexes, and reducible expressions only, out of the term and binds the results, often called reduxes. And similar to the continuation passing style or administrative normal form, makes the order of evaluation and use of temporary values explicit.

But only redexes -i.e. work- are hoisted out. And control flow is nice, but it was, and it will always be, mostly about communicating clearly to your backend what work needs to be done - in what order is the detail.

And that's where I think continuation passing style, or administrative normal form, went wrong-ish as a backend solution for rewriters; they are answers that will function but also the almost correct but strangely wrong answers to a trivial question: what work needs to be done. And instead of answering that they concentrated on the order or got the work statement wrong. No wonder that naive continuation passing style will state too much to be done. Meanwhile, this intermediate representation also gives a precise answer to what functions consume constant stack space and can be optimized further, i.e., those are the functions that rewrite to exactly one redex.

TL;DR: When developing a rewriter it becomes important what work needs to be done in what order. And hoisting out redexes makes that clear, whereas continuation passing style and administrative normal form give almost correct but wonkish answers.

Are All Algol-like Calling Conventions Wrong?

Those who have watched the critically acclaimed "Egel - The Movie" (8 upvotes on lobste.rs) know that I've been dabbling with a small rewriter with a trivialized semantics. The observant viewer might have noticed an off-the-cuff remark in that movie that Egel, since it rewrites, has less need for tail-call optimization, some stuff comes for free.

Let's revisit a small recursive function, factorial: fac 1 = 1 | fac n = n * fac (n-1).

Those who know some compiler theory will know the runtime behaviour of that function if implemented according to the Algol convention for stack machines: for every invocation, a stack frame is created with a dynamic and static link and some space for local variables. The program will subsequently perform its operations within the context of that frame, and for each recursive call, a new stackframe is pushed to the stack.

Egel in contrast, will rewrite a redex to another number of redexes. For a stack machine that corresponds to removing the callee's stack frame entirely and pushing several stack frames with work to be done to the stack. Hence my remark that there's less need for tail-call optimization, for simple recursive functions that consume constant stack space you get that for free. Also noteworthy, tail-call optimization module cons comes for free too.

And that begs the question of whether other calling conventions are wrong, at least for ML-like languages.

Egel - The Movie

 

Modelling Effects

A brief experiment involving 'effects.' Presented below is the translation of a program 'tick + tick' with 'tick' serving as an effect.

The key approach involves isolating the effects through a continuation and utilizing try/catch as a handler or control flow mechanism.

I acknowledge that the final outcome may seem convoluted; however, its purpose is to demonstrate the semantic model's capacity to accommodate such constructs.

using System

data tick

def do_tick = [K -> throw (tick K)]

def handle_tick = [N (tick K) -> try K N catch handle_tick (N+1)]

def main = try do_tick [N -> do_tick ((+) N)] catch handle_tick 1

Random Thoughts On the New Release

I published a new performance release of the Egel interpreter named "v.0.1.10: Egel, let's go." I am now at a fork in my thoughts.

Egel successfully shows that an operational semantics where the root of a directed acyclic graph is repeatedly rewritten can serve as the back-end of a small functional scripting language. However, Egel is notably slow, approximately eight times slower than Python according to various benchmarks.

Egel is also rather rudimentary as a scripting language, sufficient for solving Advent of Code puzzles but lacking essential features, presenting an overall unpolished experience. What I want to do is minimally add date/time objects as primitives and incorporate support for applicatives and lenses.

Despite these potential improvements, it's challenging to justify investing significant effort into a tool that will not find widespread use.

On Trivialization

Sometimes I post about Egel, but more often than not I am confronted with people who -rightfully so- wonder what the point of it all is.

Egel, the language, is a minimal front-end to an alternative operational model that showcases that term rewriting can be achieved by repeatedly rewriting the top of a directed acyclic graph. An alternative to SECD, CACM, or graph rewriting machinery like GHC's spinless tagless G-machine. I estimate that confuses people since that kind of work on operational semantics hasn't really been done for the last twenty years and this is a trivialization effort. Whereas most of the field has moved on to studying elaborate type systems that provide ever more complex static guarantees.

The keyword here is 'trivialization' and let me share my thoughts on that. I like to compare this effort to work on the Pythagorean theorem, which started off with a proof of more than twenty pages, and through insights during the last two millennia has been reduced to a one-liner.

Trivialization is important. At every step, the Pythagorean theorem didn't change, it was still true, no noteworthy things changed; similarly, Egel doesn't really show anything new, everything can already be done with other machinery, and no real unexpected exciting things are happening. Through trivialization you only get something smaller, maybe clearer. But the importance of such an effort becomes clear when one asks oneself where we would be if we were still stuck with a proof of twenty pages.

We live in an era of informatics where baroque abstraction castles are built atop of ever more complex machinery, and at the same time, there's always a need for going back to the fundamentals to see whether something is there that is less complex one can build upon to create new -maybe better- castles.

Emitting a Graph

I've been examining a new emitter that involves rewriting directed acyclic graphs (DAGs). Specifically, when Egel rewrites a combinator, the bytecode of the combinator needs to produce another segment of the DAG.

In light of this, I've been sketching out an algorithm to address this requirement. Below is an example of a new graph that could be the outcome of rewriting a combinator node.

In the representation, solid lines indicate constants, and dotted lines point to redexes that must be rewritten in a particular sequence. Exception handlers are omitted for clarity.

As the rewritten graph node serves as the apex of a DAG, it seems likely that I'll need some form of stack to systematically process AST nodes in a specific order. This processing order is crucial for generating bytecode that effectively constructs the desired graph.

It's a neat puzzle.