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 Runnable''''''Return implements Runnable
 { public Runnable''''''Return(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 Runnable''''''Apply implements Runnable
 { public Runnable''''''Apply(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 Final''''''Runnable''''''Step implements Runnable
   { private Final''''''Runnable''''''Step() {};

     public static final Final''''''Runnable''''''Step INSTANCE = new Final''''''Runnable''''''Step();

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

   private static Object retval;

   private static class Final''''''Continuation implements Continuation
   { private Final''''''Continuation() {};

     public static final Final''''''Continuation INSTANCE = new Final''''''Continuation();

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

   public static Object apply(Function f, Object[] args)
   { innerDo(new Runnable''''''Apply(f, args, Final''''''Continuation.INSTANCE));
     return retval;
   }

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

A typical function will look like this '''Typical''''''Function''':

 public final class Typical''''''Function implements Function
 { private Typical''''''Function() {};

   public static final Typical''''''Function INSTANCE = new Typical''''''Function();

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

   private static final class Some''''''Continuation''''''Inner''''''Class implements Continuation
   // (only some functions need this)
   { public Some''''''Continuation''''''Inner''''''Class(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 Runnable''''''Return(k, new Object[] { result });
       // or else tail-call or call another function, etc.
     }
   }
 }

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

-- EdwardKiser

----
See also IoLanguage.

CategoryScheme CategoryCodingConventions