Friday, 4 May 2012

Emulating "goto" in F#


A label and its following instruction block can be translated into a function and its body. Then each goto becomes a function call. You must pass all local variables as arguments because separate functions have separate scopes and you must add fall-through calls from one instruction block to the next when necessary. However, tail calls are a more general concept.
For example:
let rec start () =  // .start
  start()           // goto start
Note that a decent compiler will actually compile this equivalent high-level code back down tojump/branch between instruction blocks in assembler. The main difference is that the stack frames must be reorganised because you can tail call between completely dissimilar environments.
Interestingly, you cannot pass labels around in other languages but you can pass functions around in F#, both as arguments in function calls and as return values from functions. Other languages, like Fortran, do offer computed goto as a half-way house.
Note that asynchronous programming is an important practical application of this technique. When you call an asynchronous function you tell it where it is to branch to when it completes. For example, when you make a call to start an web page downloading asynchronously you pass it a function that it will invoke once the data is available (essentially, the hardware interrupt received when the last of your data comes in ends up firing off your high-level managed code to operate on the fresh data, which is pretty cool). Modern languages give you the tools to write high-level reusable asynchronous code by combining these goto-like techniques with extra code generation during compilation. In other languages like C# you are screwed because you want to wrap multiple asynchronous calls in a single try..catch but you cannot because they are actually spread across many different functions.

No comments: