It ain't that simple: Exceptional Control Flow

Story short: The current scheme for translating try/catch to a set of combinators is (mostly) correct, but leaks since curried combinators might escape a try/catch block with exception handlers still referring that block. Seems I made a bad call here.

So, I need to rethink this. And since I am now provably 'Not that Smart'™, I'll do it in this blog. First, a number of observations:

There is a translation scheme of try/catch to an 'unsugared' term. (I use the term 'unsugared' loosely for a source code to source code translation.)
This is trivial, any calculation can be translated to SK only if need be.

If we can unsugar try/catch, we should.
It greatly simplifies the runtime if I only need to think about combinator applications. There is the possibility that I simply shouldn't try to unsugar this, to keep the operational model clean, but that's unlikely.

The translation of try/catch to an unsugared term is a 'must have.'
I want to do combinatorial rewriting, mostly to see where I'll end up, but also to experiment with what it enables. If anything, if this is to be a simple slow toy, it should enable certain functionality trivially usually not found in other languages. If all computations are simple terms being rewritten we might enable:

1. Trivial low overhead concurrency. Concurrency deflates to interleaving evaluation steps amongst any number of terms.
2. Trivial suspension of computations. A term could, for instance, be stopped, written to disk, and resumed at any given point.
3. Trivial mobile code. Any term can be serialized, send to another place, and be resumed there.

The last one is a must have. I want to see whether I could create a better R, or Python, for data centre applications, and the ability to move code to where the data is is a must have. In Spark, this is achieved by either serializing Java bytecode for Java/Scala, or pickling Python objects, and sending the abstract calculations to their destinations. I want this.

The unsugared term must allow for efficient evaluation.

Okay, here's the real catch. The most trivial source to source translation is simply having any calculation return a value from a disjoint union; i.e., any computation returns either a normal value or an exceptional result and either proceeds normally or passes on the exception. But the extra checks are wasteful, blow up all terms, and are inefficient in that they also need to 'pass up' exceptional results instead of simply 'tearing down a stack'.

The design space with magical combinators is limited.

Since we don't want the above translation, that warrants the idea that we should introduce 'magical' combinators which can modify the control flow.

In a term rewriting system, modifying control flow boils down to being able to rewrite the term in unexpected manners (and continue evaluation somewhere else).

For instance, a 'magical' combinator could have a value pop up somewhere else in the term, or erase and substitute entire terms in a non-normal fashion and then force evaluation elsewhere.

And we have two rough solutions for these 'magical' combinators: either do it more or less 'purely', by the creation of control flow objects which are passed around and hold information about what part of the term to rewrite, or do it 'impurely' with combinators which through side effects manage and query external tables referencing the term.

Of course, I prefer the first solution but fell flat on my face there. In the case of try/catch, since control flow objects might escape the local context through returning curried applications, those control flow object cannot be that 'pure' as I imagined (this is solvable, however, by making them impure; i.e., the control object is an impure shared stack of contexts) Moreover, passing around control flow objects is again wasteful as it usually passes an extra argument around.

So there you have it. I want 'pure' terms but for performance reasons I should give up on that idea and use side-effecting impure combinators; i.e., all terms are evaluated within a term referencing context modified and queried by 'magical' combinators. Which should imply a simple scheme where I introduce combinators for try/catch and throw which impurely modify, or extract information from, some tables. Tada, this bites again with low overhead concurrency or mobile code.

So, now I wrote it down. Unsure what to do. It ain't that simple.