Independent Study: Early LISP History

(This is one in a series of posts about papers I'm reading for an independent study with Prof. Evan Chang at the University of Colorado, Boulder. I'll try to follow the same format in each post — a general discussion, followed by specific points of interest, and finally questions.)

Discussion

Herbert Stoyan's version of the early history of LISP faces hagiographic challenges. Some of the source material from which he works is undated, giving him the task of having to deduce its significance in the conception and development of LISP. The second of the AI Memos that John McCarthy, Nathaniel Rochester, and perhaps others wrote at the MIT AI Lab in the late 1950's is undated. In another case, a graduate student enrolled in one of Minsky's courses wrote the following during a guest lecture by McCarthy:

FORTRAN plus variable functions, composite functions (Church lambda), multiple functions, several valued functions of several variables, direct sum of functions, label portion of program with facility to make symbolic substitutions therein ...

This rather sketchy note, however, contains information of use to one of Stoyan's opening arguments. Citing this note, Stoyan mentions that this guest lecture is the first time that the lambda calculus appears in relation to the language that was to become LISP, reinforcing the point he makes at the beginning of his history — to wit, that LISP was not, as some believe, originally 'a clean "pure" language design in the functional direction which was comprised by AI-programmers in search of efficiency.' The original goal was simply a language to serve the ends of the Artificial Intelligence Laboratory at MIT. Indeed, Stoyan's history of the language shows that McCarthy arrived as the design of early LISP in a somewhat ad hoc manner. The language's built-in functions car (first element of list) and cdr (rest of list) were first implemented on top of an imperative FORTRAN. Furthermore, a language that inspired LISP was imperative, not functional. Quoting Stoyan,

It is one of the most important events in the history of programming that McCarthy, who was looking for a mathematical-logical programming language, found interesting elements of it in FORTRAN. He was fascinated by the idea of writing programs with "algebraic" means, i.e. mathematical expressions.

(The expressions McCarthy eventually settled on were symbolic expressions, or S-expressions, the subject of next week's paper.)

LISP as a Functional Language

While McCarthy didn't conceive LISP simply as an implementation of the lambda calculus, it is a mixed-paradigm language, containing both functional and non-functional features. A brief examination of the functional features of early LISP follows:

• Higher-order functions: early LISP has a built-in functions maplist, which takes a function as an argument, so clearly it has higher-order functions.
  
• Pure functions: I can't tell from the history whether invoking a function in early LISP could have side effects.
  
• Recursion: definitely.
  
• Strict vs. non-strict (lazy) evaluation: the implementation of LISP discussed by Stoyan used lazy evaluation, judging by the following sentence: "If we imagine a correct substitution function and accept the necessity for quoting all constants then there remains the well-known problem of free variables moved to wrong environments because of the lazy evaluation."
• Type systems and pattern matching: it's hard to determine based on the contents of the history, but my impression is that early LISP was untyped.
  

LISP as a Dynamic Language

Dynamic programming languages are loosely defined, more like one of Wittgenstein's family resemblances than one of Aristotle's essences. What follows are some characteristics of dynamic programming languages, and whether and/or how they exist in LISP:

• Eval: the ability to take a string representation of a program and execute (or evaluate) it. This concept originated with LISP. The fact that eval converts data (a string) into code (an execution) seems to be essential to dynamic programming languages in one respect — to wit, that what is executed does not exist at the beginning of a program's execution in a form that is directly executable by the underlying hardware. This is a characteristic of any language that executes in a virtual machine.
  
• Higher-order functions: Yes (covered above).
  
• Object runtime alteration: Objects do not exist in LISP, so this item does not apply.
  
• Closures: In contemporary usage, a "closure" requires lexical (i.e. static) scope. Scoping in early LISP was dynamic, a wildly different beast, so these don't exist.
  
• Continuations: Early LISP isn't purely functional, and the first paper on continuations was delivered in 1964 (a few years before the first implementation of LISP), so continuations were likely not part of early LISP. Further evidence for this is the fact that it had labels and iteration constructs: "Besides the `arithmentical (sic.) or replacement statement' the following kinds of statements were thought to be available.: A GO-statements (sic. -- likely "GOTO statement"), compound statements, statements for iteration, declarative statements (describing property lists) and statements for the definition of subprograms (and functions)."
• Reflection: it's not clear from the history whether early LISP had anything like Common Lisp's find-symbol.

Points of Interest

• One of the features of early LISP was symbolic differentiation and integration of functions? This might become clearer with next week's reading.
  
• Dynamic scoping — not carried over to Common LISP or Scheme.
  
• Parentheses determined by external constraint: "Therefore, the reason for selecting parentheses ... instead of brackets or braces was only a matter of chance because in 1958 the usual devices had only parentheses and nothing else."
• "It turned out that the realization of recursive function was the most complicate (sic) problem in translating the LISP-programs into SAP-routines." The question was how to implement the runtime stack. McCarthy considered following the example of IPL and — as implied by the history — implementing the stack as lists. He also considered implementing the stack as something private to each function. He finally settled on using a "public push-down list" for the runtime stack.
  

Questions

• The difference between maplist and apply is not obvious from Stoyan's discussion. I know that maplist takes a list L and a function F as arguments, applies F to each element of L, and returns a list L' containing of the return value of each invocation of F. In more recent languages (e.g. Python), maplist is called map. The meaning of apply is likely found in recent languages as well. Python has a (deprecated) apply function, which takes two arguments — a function F and a list A containing arguments to be passed as separate actual parameters to F. JavaScript's apply method (which is a callable property of a Function object, not a function properly speaking) with essentially the same signature. (JavaScript's Function object also has a call method, but unlike JavaScript's apply it takes a variable number of actual parameters instead of a single actual parameter. (I answered this question for myself before writing the discussion.)