Return Paths

It struck me today, sitting in a grammar school auditorium surrounded by anxious parents that I was returning. I knew several people at the school from having lived in the neighborhood a decade ago; and it struck me that I was returning. It feels strange to find a return path much by accident, to come back to a place you left with no clear path of return. 

My brain, being what it is, turned to thinking about return paths in programming languages.  Flow control is the art of the return path, learning how to go back from whence you came without knowing what lies ahead.   It is also an art of bundling the future so that you have a future to return to once the present moment is over.  Structured programming is the art of structuring a program as a sequence of moments, it is in the spaces between those moments that the rest of the world happens. 

Most languages limit every return path to a well defined continuation. A future state neatly bundled in a stack frame or activation context chain or simply a explocit continuation. Anyone familiar with callcc can tell you, return is just a short hand for calling current continuation with a single argument.  For most programming languages, this is sufficient. 

Forth is probably the notable exception. The continuation is the content of the return stack, something the program is free to rewrite at any point. Like Dr Who, the Forth programmer rewrites the future to implement flow control by altering the past.  And like the Doctor, it can be difficult to keep straight what came before and what comes after, and only gets more confused when two time travelers play leap frog. 

But in essence, what Forth does is more honest that what C++ and Java do with exceptions.   The implicit long jumps of try/catch programming violate every reasonable expectation of the future, like quantum goto statements, where all futures are unequally probable, but equally unknowable until you've ended up there.  The reason for this is an exception is a non-local exit to a point determined at runtime.  Fundamentally it violates the tacit assumption that:

  A() ; B() ; C()

will evaluate A then B then C.  With exceptions in the mix we can get:

   () -> nothing, exception thrown at start of A
  A'() -> partial of A(), exception thrown 
  A() -> all of A, excecption short circuiting current continuation
  A();B'() -> partial B
  A();B() -> a b no c
  A();B();C'() -> a b partial c
  A();B();C() -> a b c 

Effectively an indeterminable amount of work will be done, and the code path you expect to execute may or may not be taken depending entirely upon the definitions in the code.  Languages like Java go to great lengths to make the programmer specify which exceptions are thrown or rethrown, however, as many language primitives also throw exceptions not all exceptions are caught this way. In fact, the burden is so great that Java exempts all of those exceptions as it would require nearly every function in the language to declare it throws class Exception, as even trivial code can throw runtime exceptions due to system issues, like insufficient memory in your JVM. 

Probably my favorite idea for flow control and return paths involves a variation of Firth I did many years back. 

;         a binary operator a;b do meant do a, empty stack, then do b

?       a binary operator a?b meant if a do b

meant make a the current continuation, and continue

.        a unary operator a . meaning call the current continuation with the value of a

This gives you the ability to control the flow of a program in a regular fashion without need of special forms and other mystical invocations. (cf. try/catch/throw/final). 

The problem of reducing the continuation of a program to a mere function is that it becomes impossible to efficiently talk about partial applications of some subset of that function.  You can't represent the continuation of a program as C(x) and effectively manage what is really a composition of C(x) = f(g(h(i(x)))), and then produce a function that transform C(x) into C(x) = f(j(g(h(x))).  By manipulating the return stack in Forth, or in C using setjump/ longjump , or in Java using exceptions as a form of flow control, you can achieve this effect, but it is an emergent property of the implementation of the system, and not an explicit design idiom. 

Schemers get the closest to capturing this using callcc to implement backtracking and allowing a programmer a limited ability to pass around compiled continuations, and even modify them by wrapping.  Still there is no good programmatic way of unraveling and patching  a continuation at runtime.

Now for many, not having the ability to explicitly manipulate the future state of a program may not seem terribly useful. With dynamic module loading, we can always load new code at run time, or with a scripting engine generate a new statemachine and evaluate that.  Both are techniques that are widely used in popular software like web browsers and video games.  But what is lacking in both approaches is the capacity for universal applicability. 

The alteration of program state is manipulable though only certain key points where control transfer is simulated or delegates to an external process (in the case of dynamically loading code).  In Erlang, for example, I can load a new module. All methods invoked with a spawn(M,F,A) will run the old code for their allotted course, and new instances will transfer to the new version of the module when a key transfer of control occurs. This insures you don't have partial application of a method during an upgrade resulting in unpredictable behavior. Once the function call finishes, its next invocation will occur in the new module's context.  There is little opportunity for error.  This is also in part why Erlang favors static assignment over dynamic assignment, in that the language avoids aliasing that can render data structures unsafe for preemption or concurrent access.  Since each slot is assigned to a new free region, and all assigned slots are tagged, Erlang can perform sanity checks at run time for misbehaving software.  

Erlang does not provide an explicit mechanism for modifying a future state of a program, the OTP platform provides all of the structure necessary to implement it. As the gen_fsm and gen_server both provide models for application state, they do so with a view towards future versions of themselves. Both modules provide an upgrade hook to allow the programmer to transform old state representations to new ones. This is incredibly valuable for long running programs, as it ensures that upon upgrade the translation from one model to the next is performed in conjunction with the upgrade.  If the code is primarily driven by gen_fsm modules, the migration from one collection of state machines can be carefully modeled and executed, though the representation of this change involves no fundamental structure of the language. 

The limitation that Erlang over comes through application design revolves around a typical design pattern of event drive systems. To paraphrase Mcluhan, the Program is the Message.   In an event driven program, flow control is the routing of messages between components of the program.  The recipients of the messages have a limited model of state in that they have know endpoints to which they send messages.  The effect of these messages is more messages being sent,  until all terminal node are reached.   If a loop in the message graph is encountered, the program may or may not terminate depending on the behavior of the nodes that compose the loop. 

If you think of an Erlang program not as the functions, but the flow of messages between the processes (read objects) you have the same model as Smalltalk, in which a program is an expression of message flows between objects.  As more parallel systems are developed, modeling message flow between involatile objects becomes the preferred method of computation.  The objects themselves are viewed as static, whereas the state they encapsulate may be dynamic and ever changing. Like a Mouse or Keyboard object, they may not map to a fixed known value, but may change as a function of time.  To reason about them from the standpoint of the program is to reason about the messages they can send and the cascades that may result.  Being able to alter this cascade at run time becomes increasingly important, as there is no single linear flow through the "program". 

REST attempts to solve this problem by embedding state transforms into the message flow. Links in the document are pointers to potential future states.  The problem here is not the modeling of state, but the nature of linking. Ultimately the definition of the continuation of a program lies in the interplay between the link and the system or systems that interpret it. As anyone who has used hypertext for any period of time knows, dead links, where the representative entity for a state ceases to be, result in a loss of the continuation.   This problem exists in any long lived system which attempts to model continuations outside of the medium of the message. 

Programmers familiar with ESB will immediately see a solution, where in the state machine which describes the flow of a message through a system is embedded in the message itself.  The message passed between services also contains a small program that describes how the artifacts produced will be used in the future state of the system.   This is a particularly powerful technique as the description of this flow is a description of the programs future states which exists independent of any single state store. 

In a poker simulator, ca 2005, I wrote just such an engine in Python. The problem I was facing was how to score and play an effectively infinite variations of poker, where in home game style rules could be tied to any event.  For example, all Queens are wild when a one-eyed jack is showing, unless the Queen of clubs is in the river.  The rules of the game consist of a finite state machine, which radically alters the meaning of a few cards based on the state of the game.  Now when you can consider this expression as:

  All X are Y when Z unless Q

And realize that you can chain apply any number of rules on top of this with additional conditions, you quickly have a hard time generating a scoring algorithm let alone a strategy algorithm for each variation.  The final approach was a self-modifying state machine which injected rules into a continuation array which was modifyable by any operation. A method could scan and inject one or more methods anywhere into the continuation as well as remove an arbitrary number.  Since copies of the array could also be attached to any method, branches could be represented as possible futures attached to conditional evaluators.   In this way all possible combinations could be modeled in that any operation could reinvent the future at any point by altering the continuation. 

In this secanario, a loop could be constructed by injecting a call back to the current module at the appropriate point.  Much like an Erlang module that calls itself using a MFA spawn, each thread of execution would determine its own fate, and in sequence all futures would contend.  This allowed the AI to adapt its strategy by rewriting its plan on the fly, and allow the scoring engine to modify its scoring strategy based on events in the game. Rather than programming for each possibility, small sections of the program new how to assemble themselves into useful aggregates. This scheme ultimately only worked because of the concatenative nature of each individual method. In effect I had an object oriented forth in python that used an event driven architecture to self-modify its execution path. 

I am working on a new system in JavaScript now that works roughly the same way. And it is funny because once again I find myself on a return path I did not expect to find.