Lexical block return: The language crux

Tagged:

I have been thinking about my favorite programming languages: Smalltalk, Common Lisp, and Scheme. These languages have much in common, and share many features, all the way down to syntax extension. I tend to be working in or studying any of these three when I am not pushing PHP for money.

These languages have an amazing pedigree, and many of their features have been ever so slowly moving into the mainstream. So what keeps this little club so exclusive? Is it my affinity for Lisp macrology? Is it the necessarily corresponding dearth of built-in funny characters? Perhaps, but I also realized they shared lexical, non-local block return in common, an interesting feature that others seem to overlook.

All three languages encourage you to define new control structures procedurally, using higher-order functions. This is especially true of Smalltalk where even retrieving array and dictionary elements has useful¹ associated control structures:

anArray at: 42 ifAbsent: [self defaultAt: 42].
anArray at: 42 ifPresent: [:newElt |
    self defaultAt: 42 put: newElt].

So you like this and in lieu of Javascript 1.6’s Array.forEach, which at this point can only be relied on in new Mozilla browsers, you try to raise the spirit of #do: from Smalltalk:

function values_do (coll, proc) {
  var len = coll.length;
  for (var idx = 0; idx < len; ++idx)
    if (idx in coll)
      proc (coll[idx]);
}

Great, now we can define #detect:

function find_if (coll, pred) {
  values_do (coll, function (elt) {
      if (pred (elt))
        return elt;
    });
}

…oops. return will return from the function we pass to values_do, not find_if. That’s okay, I guess, it’s an easy fix.

function find_if (coll, pred) {
  var dummy = {};
  var ans;
  try
    {
      values_do (coll, function (elt) {
          if (pred (elt))
            {
              ans = elt;
              throw dummy;
            }
        });
    }
  catch (ex) {if (dummy===ex) return ans; else throw ex;}
  return null;
}

Okay, not so much an easy fix. What Javascript got right was including closures, so that this was even possible to implement usefully in the first place. What it missed was a convenient way to turn naïve higher-order functions into even more powerful control structures, through lexical rather than context-dynamic means requiring you to jump through hoops on every use to avoid collision with other dynamic unwind handlers.

All three of my favorite languages have this mechanism. Smalltalk’s is the least flexible, as it can only escape from the containing method, but the most convenient. All three non-locally escape the current continuation, passing a value to one lexically containing the escape expression.

"Smalltalk"
detect: predicate ifNone: otherwiseBlock
    self do: [:each | (predicate value: each) ifTrue: [^each]].
    ^otherwiseBlock value

;;; Common Lisp
(defun detect (list pred)
  (dolist (elt list)
    (if (funcall pred elt)
      (return-from detect elt))))

;;; Scheme (even R5RS with a little convenience define)
(define (detect lst pred)
  (call/cc (lambda (escape)
             (for-each (lambda (elt)
                         (if (pred elt) (escape elt)))
                       lst))))

I don’t know how related this is, but the combination of lexical block return and lexical closures is all you need to create a powerful exceptions framework, one much more powerful than those in most mainstream languages. Smalltalk, Common Lisp, and R6RS Scheme seem to take advantage of this implication by defining such frameworks.

Is this, perhaps, the missing link that turns what might otherwise be sanity sinks into languages that fit into my head? Maybe it is not so much that implementing higher-order processes is easier than that with these languages, I am always aware that I can wipe out a whole well-defined range of continuations at the drop of a ^.


¹Useful in that I would have used them hundreds of times by now in my otherwise-PHP development. I’m looking at you array_key_exists and isset. The former has the dubious honor of being my only php-mode abbrev, bound to ake.

I had never put my fingers on it, but now that you wrote about it I couldn't agree more.

Hi,

this post is very interesting. As a smalltalker, I would have loved to know more about call/cc and return-from but I guess I can search by myself.

You may want to fix the dolist call in the detect defun, which probably takes a list as second parameter :-).

now I see what you mean. Fixing.

About return-from. defun implicitly establishes a block named as the function.

call/cc is a sophisticated and truly fascinating mechanism, and would require a whole separate post to explain. Its functionality is available to GNU Smalltalk via the class Continuation in the kernel classes. Another #detect:

detect: predicate ifNone: otherwiseBlock
    ^Continuation escapeDo: [:escape |
        self do: [:each | (predicate value: each) ifTrue:
                              [escape oneShotValue: each].
        escape oneShotValue: otherwiseBlock value]

As for the other, dolist is a macro in Common Lisp. As with Presource macros, the normal evaluation rules don't apply. An incomplete example in Scheme:

(define-syntax dolist
  (syntax-rules ()
    ((_ (?each ?list) . ?body)
     (for-each (lambda (?each) . ?body) ?list))))

User login