Lisp in Small Pieces of Clojure - part 3

L.I.S.P. cover

This continues a translation of various parts of Lisp in Small Pieces into Clojure. For earlier chapters, see:

This time round I won’t say much about the contents of the chapter. The translation is an accompaniment to the book and the blog post is in no way a substitute. Buy the book if you don’t already have it!

Chapter 3

Chapter three of LiSP begins by reviewing a range of control structures, historical and modern, that incorporate the notion of an escape - a transfer of control that is non-local but nevertheless less powerful than arbitrary ‘goto’. Unlike ‘goto’, you can only escape back to places you’ve already been.

These can be used for optimisation, for instance, for shortcutting out of a deeply nested search procedure or for error handling as per the near-ubiquitous try / catch constructs in popular OO languages.

Each pair provides a means of marking a continuation at which control will resume and a means of transferring control to that continuation.

In addition the book covers unwind-protect, a form that interacts with the various other escapes to provide an analogue of the familiar finally construct, ensuring that a body of code is run when control escapes a block regardless of how the control escapes.

The notion of continuation that is gestured at by these control structures is famously provided as a first class object in Scheme. call-with-current-continuation, a.k.a. call-cc, enables a continuation to be identified, named and stored (with indefinite extent) for later use.

Using call/cc, any of the other control flow primitives can be simulated.

Furthermore, by reifying this notion of continuation in our interpreter, using either the facilities in the underlying lisp (call/cc) or via a translation to continuation passing style (“CPS”), any of these control structures can be provided as primitives in our daughter lisp.

Chapter three describes both these methods although most of it is devoted to the strategy we need in Clojure - CPS.

The Translation

My translation is here.

It sticks closely to the strategy in the book with a few renamings here and there. It’s pretty generously commented so inspect the source for more detail.

Instead of directly mirroring the object orientation approach in the book, I’ve eradicated the few non-essential uses of implementation inheritance in the book (e.g. full-environment inheriting null-environment…) in favour of a more idiomatic protocol / record representation in Clojure. Further discussion of this below.

I’ve implemented call/cc, block / return-from and catch / throw. I’ve left out unwind-protect for now at least, despite its obvious utility. As our evaluator still lacks even such creature-comforts as an extensible global namespace, it’s hardly an pressing issue.

A Note on Object Modelling

Over years of dealing with Java and C++ and some pretty large codebases, I’ve become extremely wary of implementation inheritance. Not dogmatically - any language feature is fair game to developers striving for the simplest and cleanest expression of their intentions - but enough to acquire a firm conviction that inheritance is heavily overused in both ecosystems.

While deep inheritance hierarchies may seem like a great way of modelling your concepts when you have a blank slate, it’s a recipe for some extremely tight and non-obvious coupling that can deadlock refactoring attempts in later phases once those concepts have shifted and the original model is no longer a good fit. The problems can be particularly acute when the inheritance hierarchy has spread across several semi-autonomous modules or (worse) long-lived code branches.

Dynamic languages and languages with superior type inference can alleviate some of these difficulties - you can mitigate coupling by leaving things unsaid or allowing some flexibility in the meaning of what you have said. And various approaches to mixins and traits have been conceived in an attempt to reconcile the fidelity of modelling with evolvability.

Nevertheless, part of the problem is simply inherent. It seems that the more intricate a representation of a conceptual hierarchy, the harder it is to change. The issue is compounded by the scant effort that developers normally take to control the API they present to subclasses (the protected methods) and to take care of method visibility in general.

So in Java, I would generally start with a flat duality of interface and implementation these days, using composition and other approaches where possible and only indulging in implementation inheritance in cases that seem particularly benign.

Happily, this is the basic paradigm that Clojure’s protocols encourage too. However, in translating chapter three’s evaluator into Clojure I don’t think it’s appropriate to go to protocols / records in all cases.

The lisp implementation presented arranges matters like this:

(define-class continuation Object (k))
(define-generic resume (k continuation) v)

(define-class if-continuation continuation (et ef r)
(define-class begin-continuation continuation (e* r)

(define-generic invoke (f) v* r k)

define-class sets up a true implementation inheritance relationship here. The definition of continuation contributes a k field to all subclasses and automatically defines accessor methods continuation-k and set-continuation-k! which are available on all subclasses.

This would correspond roughly to the following Java - where the generic functions have become methods defined inline within the class definitions.

/**
 * Unified call interface for functions, primitives and
 * continuations.
 */
public interface Invokable {
  void invoke(Object[] vals, Environment r, Continuation k);
}

public class Continuation implements Invokeable {
  private final Continuation k;

  public Continuation(Continuation k) { this.k = k; }
  public Continuation getK() { return k; }

  // Default, intended to be overridden
  public void resume(Object value) { k.resume(value); }

  // This is a case of API adaptation, *not* to be overridden
  public final void invoke(Object[] vals, Environment r, Continuation k) {
    resume(vals[0])
  }
}

public class IfContinuation extends Continuation {
  private final Form et;
  private final Form ef;
  private final Environment r;

  public Continuation(Form et, Form ef, Environment r) {
    this.et = et; 
    this.ef = ef;
    this.r = r;
  }
  public Form getET() { return et; }
  public Form getEF() { return ef; }
  public Environment getR() { return r; }

  // override resume for custom behaviour
  public void resume(Object value) { ... }
}

public class BeginContinuation extends Continuation { ... }

This illustrates three subtly different uses of implementation inheritance:

It’s tempting perhaps to define a Resumable interface and work where possible at a higher level of abstraction but the parts of the evaluate which work with continuations, the implementations of block and catch for instance, need to follow the chain of wrapped continuations via getK so the going the extra mail with interface segregation doesn’t buy us much in this case.

Both object systems provide for method implementation at the level of an intermediate base class, even if the Java approach is not as open to future extension.

By contrast, Clojure protocols and records do not provide for intermediate base classes at all. So a different approach again is appropriate:

(defprotocol Continuation
  (resume [self v]))

(defrecord IfContinuation [k et ef r]
  Continuation
  (resume [self v] ...))

(defrecord BeginContinuation [k e* r]
  Continuation
  (resume [self v] ...))

(defmulti invoke (fn [f v* r k]))
(defmethod invoke Continuation [f v* r k] ...)

Each continuation is a separate record type and does not share a common implementation base class. Therefore each redefines the wrapped continuation, k.

From other code, access to the wrapped continuation is available via (:k cont) and available only because each and every continuation defines k. A more careful implementation might define a protocol for access to this information but in the spirit of simplicity and a preference for data over code (which we like in the Clojure world) a better implementation still would probably just rename the field to something sensible and leave it accessible to the full range of built in functions. k was chosen merely to stick close to the book’s implementation.

The Continuation protocol is actually the Resumable interface we considered earlier. No default implementation of resume is defined.

Invokeable is replaced by a multimethod which is a) closer to the original implementation and b) allows this sort of adaptation of at the abstraction level quite easily.

Despite protocols “solving the expression problem” for Clojure by allowing extension to arbitrary predefined types, they do not solve in and of themselves solve the further problem of protocol adaptation.

If we had realised Invokeable as a protocol we would then have had to extend Invokeable to each and every implementation of Continuation to effect the adaptation. Or extend the protocol to Object and manage our own type-based method dispatch at that level.

In some circumstances extending protocols to an exhaustive enumeration of implementations might be reasonable (see BlockLookup in the translation for instance) but in the case of protocol adaptation it is clearly not reasonable.

Other approaches exist (see clojure protocol adapters for instance) but the multimethod approach is simple, flexible and powerful.

The fiddly bit though is the interaction if isa? which multimethod use to resolve method dispatch and the protocol extension relationship. If you’re dispatching on #(type %) you need to be very careful that you’re referring to the interface generated by the protocol rather than the protocol itself:

;; Continuation is a var reference the protocol, defined with defprotocol
(isa? (type (BeginContinuation. nil nil nil)) Continuation)
;; => false

;; lispic.chapter3.cont.Continuation is the fully qualified class
;; name of the corresponding interface
(isa? (type (BeginContinuation. nil nil nil)) lispic.chapter3.cont.Continuation)
;; => true

Other Stuff

There’s an extremely rich literature on continuations out there that I couldn’t even begin to cover. The book itself discusses delimited or composable continuations briefly and there are various approaches to these. See David Nolen’s delimc for an exprimental implementation in Clojure and a set of pointers for further reading.

Monadic implementations of continuations are also available in two of the prominent Clojure monad libraries though monads and category theory are in the main orthogonal to the concerns of the book.

Comments