prog+ass.md

Two Lisp History Stories

prog

Lisp, thanks to Scheme, is often associated with functional programming. However, as David Turner points out,

McCarthy (1978) records that LISP had assignment and goto before it had conditional expressions and recursion—it started as a version of FORTRAN I to which these latter were added.

LISP was not based on the lambda calculus, despite using the word “LAMBDA” to denote functions. At the time he invented LISP, McCarthy was aware of (Church 1941) but had not studied it. The theoretical model behind LISP was Kleene's theory of first order recursive functions [according a talk McCarthy gave, heard by Turner].

If you've only worked with Scheme, you may not have seen a traditional goto in a Lisp before. Here is some vintage LISP 1.5 code:

(LENGTH(LAMBDA (M) (PROG (N) (SETQ N 0)
A (COND ((NULL M) (RETURN N)) ) (SETQ N (ADD1 N)) (SETQ M (CDR M))
(GO A) )))

Reformatted:

(LENGTH
  (LAMBDA (M)
    (PROG (N)
          (SETQ N 0)
        A (COND ((NULL M)
                 (RETURN N)))
          (SETQ N (ADD1 N))
          (SETQ M (CDR M))
          (GO A))))

This code, changed only slightly, is acceptable to Common Lisp:

(defun LENGTH. (M)
  (PROG (N)
        (SETQ N 0)
      A (COND ((NULL M)
               (RETURN N)))
        (SETQ N (1+ N))
        (SETQ M (CDR M))
        (GO A)))

The prog macro is not a common sight in modern Common Lisp and was inherited for backwards compatibility. But the string “prog” appears in several Common Lisp operators. To wit:

• prog
• prog*
• prog1
• prog2
• progn
• progv
• multiple-value-prog1

In the beginning, there was PROG. However, apparently code like

(PROG ()
      (DO-SOMETHING)
      (RETURN (DO-SOMETHING-ELSE)))

happened frequently enough to warrant a PROG2 function, so that you could write

(PROG2 (DO-SOMETHING)
       (DO-SOMETHING-ELSE))

(When I say “function”, I mean it.)

At some point in the development of BBN-Lisp (to become Interlisp), prog1 and progn were added, though prog1 and prog2 both took only two arguments. The Interlisp lineage also had what Common Lisp calls “implicit progns”, where certain forms allow any number of expressions. For example, instead of

(COND ((TEST X)
       (PROGN (A)
              (B)
              (C)))
      …)

you can write

(COND ((TEST X)
       (A)
       (B)
       (C))
      …)

BBN-Lisp would generalize prog1 to any number of arguments (prog2 taking only two). By 1972, prog2 was gone, presumably because a two-argument prog2 can be replaced with progn.

Independently, Maclisp had implicit progns in cond, without actually having a progn operator at first; it was added later, perhaps borrowed from Interlisp. Maclisp generalized prog2 to any number of expressions, resulting in an idiom to achieve the effect of prog1: (prog2 nil (important-result) (side-effect) …). For example, Vaughan Pratt's CGOL (an alternative front-end syntax for Maclisp, which was also the first implementation of Pratt parsing) rewrote a&b into (PROG2 NIL a b).

One of the more obscure progs, progv, was added to Maclisp in 1975. But prog1 had to wait until 1979:

4) PROG1 -- Like PROG2 but return first argument instead of second.
   (PROG1 e1 e2 ... en) is like (PROG2 () e1 e2 ... en)
   So if you had this defined as macro in your files, you can relax now.

Turning to Lisp Machine Lisp, we find that prog* was introduced by 1981, by analogy with let*. While Lisp Machine Lisp supported multiple value returns, it seems that multiple-value-prog1 was a Common Lisp innovation.

After all of this, the ANSI Common Lisp standard contains an error in the description of prog2, claiming it acts like prog1.

ass

Let me regale you with the tale of ass (and sequence functions) in Common Lisp. LISP 1.5 introduced “association lists”, lists of pairs of keys and values. To search for a key in such a list, you could use the assoc function.

If `a` is an association list such as the one formed by `pairlis` in the above example, then `assoc` will produce the first pair whose first term is `x`. Thus it is a table searching function. We have

assoc[x;a] = [equal[caar[a];x]→car[a];T→assoc[x;cdr[a]]]

The most common use of association lists is for mapping symbols to values, for which the equal test is overkill. Interlisp used eq in assoc instead. Maclisp initially did the same, but by 1970 introduced an additional function called assq. Why the name was not asseq I cannot say. The member function also gained a companion memq.

Apparently the longer names were reanalyzed, and the first three letters extracted as a morpheme; ass carries the force of association, and mem the force of membership testing. Thus in Lisp Machine Lisp we find mem and assfunctions, taking a test as an argument. By analogy, a similar process was carried out on remove and delete to obtain remq, delq, rem, and del (plus rem-if, rem-if-not, del-if, del-if-not).

In an early draft of Common Lisp: The Language (regarded as the definition of Common Lisp in the days before the standard), the systematization of ass et al. is taken to its logical extreme.

That is, functions operating on association lists are essentially mechanically generated by combining an optional prefix (mem, pos, del), an optional infix r, and one of assoc, assq, ass, ass-if, ass-if-not. You can predict the behavior of the function from its name.

Why “Again, too many functions”? There is even more combinatorial explosion in the generic “sequence” operations in an earlier chapter. Many of the sequence functions in the manual made it into ANSI Common Lisp, such as reverse, every (and the other predicates), fill, and subseq. However, every sequence function had type specific variants for lists, bit vectors, strings, general vectors, and vectors with an element type indicated by an additional argument.

Even more (neologistic) reanalysis takes place, resulting in a dazzling array of functions (asterisks mark those eventually discarded):

• position (= pos…), posq, pos-if, pos-if-not, position-from-end, posq-from-end, pos-from-end, pos-from-end-if, pos-from-end-if-not
• remove (= rem…), remq, rem, rem-if, rem-if-not, remove-from-end, remq-from-end, rem-from-end, rem-from-end-if, rem-from-end-if-not
• *scan-over (= scan…), scanq, scan, scan-if, scan-if-not, scan-over-from-end, scanq-from-end, scan-from-end, scan-from-end-if, scan-from-end-if-not
• count (root cnt for some reason), cntq, cnt-if, cnt-if-not
• mismatch (= mismat…), mismatq, mismat, mismatch-from-end, mismatq-from-end, mismat-from-end
• *maxprefix (= maxpref…), maxprefq, maxpref
• *maxsuffix (= maxsuff…), maxsuffq, maxsuff
• search (root srch), srchq, srch, search-from-end, srchq-from-end, srch-from-end

Each of these is, of course, multiplied by the five type-specific variants. Opposition to Steele's sequence design was fierce:

The next version of the manual has three sequence function proposals: “Cross-product” (as described above), “Functional” (which seems to be missing some funcall or apply calls), and “Keyword” (close to what we end up in ANSI Common Lisp). Obviously, the absurd number of functions was silly, but it's too bad we lost ass. According to a later iteration of the Lisp Machine Lisp manual, from after the first edition of Common Lisp: The Language,

[ass] is part of The mem, rem, del series, whose names were chosed partly because they created a situation in which this function simply had to be called ass. It's too bad that [Common Lisp's assoc] is so general and subsumes ass …