Run And Return Successor

The book DesignPatterns has a pattern called StatePattern. RunAndReturnSuccessor is a variation of that pattern where each state, when run, returns its successor state. A state must return itself, if no state change is intended; it can instead construct and return some other state, or return an existing state it found out about through its parameters.

But an object implemented with a StatePattern stays in a given state until it is "bumped" by having one of its member functions called. You can do that with RunAndReturnSuccessor, but it is more common to just take the first state, run it, run its successor, run that object's successor, and so on, in a loop, until you run out of successors. So you don't wait for any member function to be called. You carry out a whole chain of computations, which was identified only by its initial state.

Funny, this sounds exactly like the inner interpreter of a threaded language (such as ForthLanguage). Every word ends with NEXT, which jumps to the next word in the sequence. One could consider a Forth program as a very fine-grained spec of state changes.

You can have a state that acts like a subroutine if you allow it to take, as a constructor parameter, the state it should return to. If you are a state that wishes to "call" that subroutine-state, then you construct it with yourself as the "return-to" parameter and return it as your successor. When it is done, it returns its "continuation" object, which is you, as its successor.

Ideally, every state has a "continuation" state when you (the programmer) use this model. Since usually you want your program to terminate eventually, you start by constructing a "final state" which can be recognized by its address. (You can pass NULL, no constructing needed, unless you want to be able to prevent state objects from constructing it -- you might want them to have to receive it as an official parameter.) You construct the start state, passing the final state as its continuation. Then you keep running successors until the current state object, whatever it is, returns the "final state" as its successor. You can recognize it with =. Then you quit.

(It is even more fun to have a queue of current states, and, instead of having every state return its successor, give every state the ability to insert zero or more successors into the queue. This amounts to a MessageQueue.)

A state can "tail-call" another state by giving its successor its own continuation, instead of itself as continuation.

A state can pass parameters to another state, apart from the continuation. CallWithCurrentContinuation becomes possible to implement, when a state passes its continuation twice. (Once as continuation, once as parameter.)

It should be possible to write a Scheme compiler that outputs code using this model. It should be possible to hand-write a Scheme interpreter that uses it.

In practice it begins to resemble ContinuationPassingStyle.

-- EdwardKiser

In what ways does it differ from ContinuationPassingStyle?

It differs syntactically. Ordinary stack-based function calls still exist in the language. If you want to do a tail-call you have to emulate it; you actually do something like

  return new Call(func, params, k);

Later I figured out how to use this to write a full-blown Scheme implementation with call/cc and the works. Here's a part of it.

In Java, you start with an interface Runnable (not to be confused with java.lang.Runnable):

 public interface Runnable
 { Runnable run(); // and return successor
 }

Then you have Continuation and Function interfaces:

 public interface Continuation
 { Runnable doReturn(Object[] retvals);
 }

 public interface Function
 { Runnable apply(Object[] args, Continuation k);
 }

Then you have some useful Runnable objects to return every now and then to keep the Java stack from overflowing:

 public final class RunnableReturn implements Runnable
 { public RunnableReturn(Continuation k, Object[] retvals)
   { this.k = k; this.retvals = retvals;
   }
   private Continuation k;
   private Object[] retvals;
   public Runnable run()
   { return k.doReturn(retvals);
   }
 }

 public final class RunnableApply implements Runnable
 { public RunnableApply(Function f, Object[] args, Continuation k)
   { ... similar to preceding ...
   }
   ...
 }

Then you have a master class called a Doer:

 public final class Doer
 {
   private Doer() {};

   private static class FinalRunnableStep implements Runnable
   { private FinalRunnableStep() {};

     public static final FinalRunnableStep INSTANCE = new FinalRunnableStep();

     public Runnable run()
     { throw new RuntimeException("Ran amok past final runnable step");
     }
   }

   private static Object retval;

   private static class FinalContinuation implements Continuation
   { private FinalContinuation() {};

     public static final FinalContinuation INSTANCE = new FinalContinuation();

     public Runnable doReturn(Object[] retvals)
     { if (retvals.length != 1) throw new RuntimeException("Returned wrong number of values");
       retval = retvals[0];
       return FinalRunnableStep.INSTANCE;
     }
   }

   public static Object apply(Function f, Object[] args)
   { innerDo(new RunnableApply(f, args, FinalContinuation.INSTANCE));
     return retval;
   }

   private static void innerDo(Runnable r)
   { while (r != FinalRunnableStep.INSTANCE)
     { r = r.run();
     }
   }
 }

A typical function will look like this TypicalFunction:

 public final class TypicalFunction implements Function
 { private TypicalFunction() {};

   public static final TypicalFunction INSTANCE = new TypicalFunction();

   public Runnable apply(Object[] args, Continuation k)
   { if (tail-calling another function)
     { Function f = (Function)args[0] or whatever;
       return new RunnableApply(f, new Object[] { args[1], args[2], whatever }, k);
     }
     else if (not calling another function)
     { Object result = ... ;
       return new RunnableReturn(k, new Object[] { result });
     }
     else if (calling another function and expecting a return)
     { Function f = (Function)args[0] or whatever;
       Continuation k2 = new SomeContinuationInnerClass(k, args[1], etc);
       return new RunnableApply(f, new Object[] { args[2], whatever }, k2);
     }
   }

   private static final class SomeContinuationInnerClass implements Continuation
   // (only some functions need this)
   { public SomeContinuationInnerClass(Continuation k, Object param, etc)
     { // assign constructor parameters to private data members
     }
     // private data members
     public Runnable doReturn(Object[] retvals)
     { // receive return values and use with private data members
       return new RunnableReturn(k, new Object[] { result });
       // or else tail-call or call another function, etc.
     }
   }
 }

From a design standpoint, it seems to work...

-- EdwardKiser