Wednesday, July 20, 2011

Leaky Shift

Sometimes it helps to bounce ideas against other people, so thanks to LtU/MattM for getting something right. I hacked together a solution once to deal with the translation of exceptions, try/catch and throw blocks. I looked a bit at shift/reset, found it too difficult to implement, and tried to implement something more trivial with two combinators.

  R f = f S (remember the current context in S)

  S x = x   (but also, whenever S evaluates it replaces the original R f term)

An example:

  1 + R (\s -> 1 + s 3) = 1 + (\s -> 1 + s 3) S = 1 + (1 + S 3) = 1 + 3 = 4

The problem, of course, is that you don't want an S combinator to leak outside an R term. I was aware of that, but -rather unconvinced- thought it may go right.
Try/catch blocks are translated to a somewhat difficult lambda term employing R. The general thought -I more hoped than convinced myself- is that either an exception is thrown (and an S is eaten), or a value is produced (and introduced S's are lost). I.e., no leaks.

A post-mortem analysis of what I did:

It works, but it also dawned to me that it may only work at the moment since I only compile straight-forward code in the bootstrap compiler. The problem occurs when translating try/catch blocks which return functions. A contrived example:

  f = try [ x -> x / 0 ] catch [ NaN -> throw "division by zero" ];
  f 3

I didn't try it yet in real code, but I am pretty sure that the result would be that the thunk which holds f would be overwritten with the thrown exception instead that an exception is thrown. Fortunately, it also looks like it is fixable.

One solution would be to remove exception handlers from curried thunks, and reinstall the right ones of the context with employed @ combinators, but it would be difficult to get all invariants right.

Another, better, solution would be a bit different compilation scheme where the curried thunk f is guaranteed not to also contain the exception handler, and  f 3 is translated to f (exception-handler) 3, which would be more straight-forward. I should check whether I didn't translate to that by accident. Ah well, back to the drawing board.

A last, best, solution would be to assign to f not the lambda abstraction, but the whole try-catch block. That should do nicely. And I may even have done that by accident? Again, I should look at the code.