Reinventing imperative programming?

Following a reference on Lambda-the-Ultimate, I read Olin Shivers' "The Anatomy of a Loop" (ICFP '05, 2005). This paper discusses the design and implementation of a loop macro for Scheme. Unlike other loop macro systems for Lisp, Shivers' is carefully defined to avoid undefined behavior, and to be extensible. Shivers' approach begins with the control flow within the loop, and uses that control flow to define the scope of identifiers in the loop components.

The motivating example Shivers uses is:

(letrec
 ((loop (lambda (rest result)
  (if (null? rest)
   (reverse result)
   (let ((x (car rest)))
    (if (p? x)
     (let ((y <verbose code using x>))
      (if (q? <verbose code using y>)
       (let ((z <verbose expression>))
        (loop (cdr rest)
         (cons <z expression> result)))
       (loop (cdr rest) result)))
     (loop (cdr rest) result)))))))
(loop l '()))

Which is indeed pretty darn ugly. However, ignoring Shiver's "after" code (using the loop form), directly translating this code into a Python-esque pseudo-code is interesting:

list result = ()
for x in rest:
 if p?(x):
  y = <verbose x>
  if q?(<verbose y>):
   z = <verbose>
   append result, <z expression>
return result

Looking at the difference, I begin to understand those who complain about the parentheses in Lisp syntax. The problem isn't the parentheses, it is the use of plain recursion (as mentioned by Shivers), the binding forms, the sheer amount of syntax, ultimately the expression-oriented nature of the Lisp example. (Yes, it could have been written in a more imperative style. It could also have been broken into smaller functions, say at the let's, or the same task done with higher-order functions.) The alternative is familiar and probably easy to read and understand for anyone who has done any imperative programming.

For comparison, take a look at Shivers' ''after'' code:

(loop (for x in l)
 (when (p? x))
 (bind (y <verbose x>))
 (when (q? <verbose y))
 (bind (z <verbose>))
 (save <z expression>))

This code resembles the imperative pseudo-code amazingly well. Most of that resemblence is undoubtedly due to the desire that the loop macro code be familiar for programmers used to imperative style. However, what Shivers has done is to re-invent an imperative programming style, on a basis of functional Scheme.

(Similarly, Haskell's monads re-invent imperative programming to manage state on a lazy functional base.)

But, before anyone can say that ''all'' Shivers has done is the re-invention, consider the method he uses: building on a basis of a pluggable Control Flow Graph sub-language, allowing additional keywords to be defined for the loop macros, and taking a novel approach that may yield other control structures.

As an example of the latter, consider Haskell's monads. At first glance, monads appear to be a way of reinventing imperative programming for Haskell, which as a lazy functional language has significant difficulties with I/O. However, once the monadic approach is identified, it can be generalized to other situations:

Monad Type of computation Combination strategy for >>=
Identity N/A: Used with monad transformers The bound function is applied to the input value.
Maybe Computations which may not return a result Nothing input gives Nothing output, Just x input uses x as input to the bound function.
Error Computations which can fail or throw exceptions Failure records information describing the failure. Binding passes failure information on without executing the bound function, or uses successful values as input to the bound function.
[] (List) Non-deterministic computations which can return multiple possible results Maps the bound function onto the input list and concatenates the resulting lists to get a list of all possible results from all possible inputs.
IO Computations which perform I/O Sequential execution of I/O actions in the order of binding.
State Computations which maintain state The bound function is applied to the input value to produce a state transition function which is applied to the input state.
Reader Computations which read from a shared environment The bound function is applied to the value of the input using the same environment.
Writer Computations which write data in addition to computing values Written data is maintained separately from values. The bound function is applied to the input value and anything it writes is appended to the write data stream.
Cont Computations which can be interrupted and restarted The bound function is inserted into the continuation chain.

(Table taken from the Catalog of Standard Monads from All About Monads.)

The Maybe monad propagates the Nothing/Just x result through the computation automatically, while the List monad can be used to easily get all of the possible results of a non-deterministic computation.

gloria i ad inferni
faciamus opus

Return to Top | About this site...
Last edited Sat Aug 8 03:29:10 2009.
Copyright © 2005-2016 Tommy M. McGuire