LetS -- a new loop notation

[Dick@MC.LCS.MIT.EDU]

  This message advertises a Common Lisp macro package called LetS (rhymes with
process) which it is hoped will become a standard iteration facility in Common
Lisp.  LetS makes it possible to write a wide class of algorithms which are
typically written as loops in a functional style which is similar to
expressions written with the Common Lisp sequence functions.  LetS supports a
number of features which make LetS expressions more expressive than sequence
expressions.  However, the key feature of LetS is that every LetS expression is
automatically transformed into an efficient iterative loop.  As a result,
unlike sequence expressions, LetS expressions are just as efficient as the
traditional loop expressions they replace.
  An experimental version of LetS currently exists on the MIT-AI machine in the
file "DICK;LETS BIN".  Although LetS is written in Common Lisp, it has not yet
been tested on anything other than a Symbolics Lisp Machine.   For various
detailed reasons it is unlikely to run on any other machine.  Everyone who
wants to is invited to borrow this file and try LetS out.  I am very
interested to hear any and all comments on LetS.
  Extensive documentation of LetS is in the file "DICK;LETSD >" also on the
MIT-AI machine.  Even people who do not have a Lisp Machine or are not able
to access the code are invited to read this documentation and make comments on
it.  I am interested in getting as wide a feedback as possible.  If you cannot
access the documentation file directly, send me your US mail address and I will
mail you a copy.  The documentation is much too long to reliably send via
computer mail.
  After an initial testing and feedback period, a final version of LetS which
runs under all Common Lisps will be created along with formal documentation.
This should happen within a couple of months.
  A very brief summary of lets is included at the end of this message.

						Dick Waters

!
  The advantages (with respect to conciseness, readability, verifiability and
maintainability) of programs written in a functional style are well known.  A
simple example of the clarity of the functional style is provided by the
Common Lisp program below.  This function computes the sum of the positive
elements of a vector.

(defun sum-pos-vect (v)
  (reduce #'+ (remove-if-not #'plusp v)))

  A key feature of sum-pos-vect is that it makes use of an intermediate
aggregate data structure (a sequence) to represent the selected set of vector
elements.  The use of sequences as intermediate quantities in computations
makes it possible to use functional composition to express a wide variety of
computations which are usually represented as loops.  Unfortunately, as
typically implemented, sequence expressions are extremely inefficient.
  The problem is that straightforward evaluation of a sequence expression
requires the actual creation of the intermediate sequence objects.  Since
alternate algorithms using loops can often compute the same result without
creating any intermediate sequences, the overhead engendered by using sequence
expressions is quite reasonably regarded as unacceptable in many situations.
  A solution to the problem of the inefficiency of sequence expressions is to
transform them into iterative loops which do not actually create any
intermediate sequences before executing them.  For example, sum-pos-vect might
be transformed as shown below.

(defun sum-pos-vect-transformed (v)
  (prog (index last sum element)
	(setq index 0)
	(setq last (length v))
	(setq sum 0)
      L (if (not (< index last)) (return sum))
	(setq element (aref v index))
	(if (plusp element) (setq sum (+ element sum)))
	(setq index (1+ index))
	(go L)))

  Several researchers have investigated the automatic transformation of
sequence expressions into loops.  For example, APL compilers transform many
kinds of sequence expressions into loops.
  Unfortunately, there is a fundamental problem with the transformation of
sequence expressions into loops.  Although many sequence expressions can be
transformed, many cannot.  For example, Common Lisp provides a sequence
function (reverse) which reverses the elements in a sequence.  Suppose that a
sequence expression enumerates a sequence, reverses it, and then reduces it to
some value.  This sequence expression cannot be computed without using
intermediate storage for the enumerated sequence because the first element of
the reversed sequence is taken from the last element of the enumerated
sequence.  There is no way to transform the sequence expression into an
efficient loop without eliminating the reverse operation.
  A solution to the problems caused by the presence of non-transformable
sequence operations is to restrict the kinds of sequence operations which
are allowed so that every sequence expression is guaranteed to be
transformable.  For example, one could start by outlawing the operation
reverse.
!
                                     LETS

  LetS supports a wide class of sequence expressions that are all guaranteed
to be transformable into efficient loops.  In order to avoid confusion with
the standard Common Lisp data type sequence, the data type supported by LetS
is called a series.
  Using LetS the program sum-pos-vect would be rendered as shown below.  The
function Evector converts the vector v into a series which contains the same
elements in the same order.  The function Tplusp is analogous to
(remove-if-not #'plusp ...) except that it operates on a series.  The function
Rsum corresponds to (reduce #'+ ... :initial-value 0) except that it takes in
a series as its argument.

(defun sum-pos-vect-lets (v)
  (Rsum (Tplusp (Evector v))))

  LetS automatically transforms the body of this program as shown below.  The
readability of the transformed code is reduced by the fact that it contains a
large number of gensymed variables.  However, the code is quite efficient.
The only significant problem is that too many variables are used.  (For
example, the variable #:vector5 is unnecessary.)  However, this problem need
not lead to inefficiency during execution as long as a compiler which is
capable of simple optimizations is available.

(defun sum-pos-vect-lets-transformed (v)
  (let (#:index12 #:last4 #:sum21 #:element11 #:vector5)
    (tagbody (setq #:vector5 v)
	     (setq #:index12 0)
	     (setq #:last4 (length #:vector5))
	     (setq #:sum21 0)
	#:p0 (if (not (< #:index12 #:last4)) (go #:e9))
	     (setq #:index12 (1+ #:index12))
	     (setq #:element11 (aref #:vector5 #:index12))
	     (if (not (plusp #:element11)) (go #:p0))
	     (setq #:sum21 (+ #:element11 #:sum21))
	     (go #:p0)
        #:e9)
    #:sum21))

                        RESTRICTIONS ENFORCED BY LETS

  The key aspect of LetS is that it enforces a palatable (and not overly
strict) set of easily understandable restrictions which guarantee that every
series expression can be transformed into a highly efficient loop.  This
allows programmers to write series expressions which are much easier to work
with than the loops they might otherwise write, without suffering a decrease
in efficiency.
  There are two central restrictions which are enforced by LetS.  First, every
series must be statically identifiable so that transformation can occur at
compile time rather than at run time.  Second every series function is
required to be "in-order".  A series function is said to be in-order if it
reads each input series in order, one element at a time, starting from the
first one, and if it creates the output series (if any) in order, one element
at a time, starting from the first one.  In addition, the function must do
this without using internal storage for more than one element at a time for
each of the input and output series.  For example, the series functions
Evector, Tplusp, and Rsum are all in-order.  In contrast, the function reverse
is not in-order.  (Reverse either has to read the input in reverse order, or
save up the elements until the last one is read in.)
!
                          OTHER FEATURES OF LETS

  Although efficiency is the main goal of LetS, LetS supports a number of
features which are not directly related to efficiency per se.  Most notable of
these is implicit mapping of functions over series.  Whenever an ordinary Lisp
function is syntactically applied to a series, it is automatically mapped over
the elements of the series.
  The following example illustrates implicit mapping.  In the function below,
the computation "(lambda (x) (expt (abs x) 3))" is implicitly mapped over the
series of numbers generated by Evector.  Implicit mapping of this sort is a
commonly used feature of APL and is extremely convenient.

(defun sum-cube-abs-vect (v)
  (Rsum (expt (abs (Evector v)) 3)))

(sum-cube-abs-vect #(1 -2 3)) => (+ 1 8 27) => 36

  New series functions can be defined by using the form defunS.  The following
example shows how the function Rsum could be defined.  More complex forms can
be defined by using the ordinary Common Lisp macro definition facilities to
define macros which create appropriate series expressions.

(defunS Rsum (numbers)
    (declare (series numbers))
  (reduceS #'+ 0 numbers))

  LetS provides two forms (LetS and LetS*) which are analogous to let and
let*.  As shown in the example below, These forms can be used to bind both
ordinary variables (e.g., num-obs, mean, and deviation) and series variables
(e.g., ob).  Whether or not a variable is a series is determined
by looking at the type of value produced by the expression which computes
the value bound to it.

(defun mean-and-deviation (observations)
  (letS* ((ob (Elist observations))
          (num-obs (Rlength ob))
	  (mean (/ (Rsum ob) num-obs))
	  (deviation (- (/ (Rsum (expt ob 2)) num-obs) (expt mean 2))))
    (list mean deviation)))

  The complete documentation of LetS compares LetS with the Common Lisp
sequence functions and with the Zeta Lisp Loop macro.  LetS supports
essentially all of the functionality of the Loop macro in a style which looks
like sequence functions and which is exactly as efficient as the loop macro.

                           THE ANCESTRY OF LETS

  The LetS package described here is descended from an earlier package of the
same name (See MIT/AIM-680a and "Expressional Loops", Proc. Eleventh ACM
SIGACT-SIGPLAN Symposium on the Principles of Programming Languages, January
1984).  The current system differs from the earlier system in a number of
ways.  In particular, the new system supports a much wider set of features.