9

LISP is generally considered an interpreted language, but compilers have been made for it. What was the first compiler?

To be clear, this is about compilers that compile LISP code stored for interpretation (whether as S-expressions, ASTs or some other internal form) to machine code, such that it then runs faster than the interpreted form did. It's not about "dumpers" that simply remove a parsing step or other such mechanisms.

  • 3
    "LISP is generally considered an interpreted language" – I would hope that at least the people who use Lisp would know that there is no such thing as an "interpreted language" and that this term is so non-sensical that it is Not Even Wrong. – Jörg W Mittag Sep 9 at 13:52
  • 17
    @JörgWMittag Don't be disingenuous, please. "An interpreted language" means exactly what it intuitively seems like it means: a language where the primary intended use case is as an interpreted language. Saying "there's no such thing because it's theoretically possible to compile anything that can be interpreted and vice versa" is pedantic and obnoxious, and serves no purpose other than to derail conversations and annoy people. – Mason Wheeler Sep 9 at 17:52
  • 2
    <troll>There's never been a LISP compiler. LISP "compilers" just dump memory. See the Emacs "nonportable dumper" catastrophe that was only fixed in the last couple years. – R.. Sep 9 at 17:59
  • 1
    @SolomonSlow: It's not proof that one hasn't. It's an example of the mechanism that's usually used in place of compilers for lisp. – R.. Sep 9 at 23:46
  • 1
    @R.. No, it's an example of a mechanism that's used in addition to compilers for lisp. – npostavs Sep 10 at 3:41
20

The first LISP compiler was implemented very early in the life of the first LISP, LISP I for the IBM 704.


The LISP I Compiler

From the LISP I Programmer's Manual (March 1, 1960) section 4.2, "Definitions of Functions in LISP"

In Chapter 2 functions are connected to their names only through the use of the form LABEL. In the current LISP system, there are two further ways a function can be defined:

The first of these relates to functions defined in the system by machine-language subroutines. Such a subroutine for a function may be already available as part of the LISP system itself, in which case it appears among the functions given in Section 9, or it may have been produced by the LISP compiler.

Section 4.6, "The Compiler," describes its operation in detail:

The LISP compiler is itself a pseudo-funciton which is available to the APPLY operator. The compiler is called in by the LISP function,

                      comdef[x],

where x is a list of names of the functions to be compiled. Each function on the list will be compiled into a binary machine program....

The compiler runs in several stages: producing a (LISP) list of assembly instructions, a two-pass assembly of this list to binary code, and then binding the name in the system so it calls the machine-language code rather than the original S-expression. The assembly code list looks like:

(( ,LXD,0,4),( ,TXI,G0007,4,-1),( ,TRA,*+5),(G0008,BSS,0),...)

This appears also to be the first use of something like gensym: "In this example, the objects beginning with G are atomic symbols generated for use within the compiler."

"Linking" was done at compile time, so one had to be careful of order when compiling functions in separate comdefs, though circular references were fine if done within a single compile run:

If a function f uses a function g as a subfuction, then g should be included in a comdef which comes before the comdef involving f except in the following special case: if a closed circle of function usage occurs, e.g.

                      f₁ uses f₂
                      f₂ uses f₃
                      .
                      .
                      .
                      fₙ uses f₁,

then all of the functions in this circle must be compiled in the same comdef. thus the functions listed in a given comdef should be unrelated or related in this circular sense.


The LISP 1.5 Compiler

The compiler was actively maintained and extended for at least several years. AIM-039, "Artificial Intelligence Project--RLE and MIT Computation Center Memo 39--The New Compiler," by T. Hart and M. Levin has no date, but from its sequence in the AIM list it appears to have been written sometime between January 1962 (AIM-31) and October 1962 (AIM-46). By this point the compiler had become self-hosting:

This memo introduces the brand new LISP 1.5 Compiler designed and programmed by Tim Hart and Mike Leven. It is written entirely in LISP and is the first compiler that has ever compiled itself by being executed interpretively.

The purpose of the LISP Compiler is to replace S-expression definitions of functions with efficient machine language subroutines. A subroutine can be expected to run about 40 times as fast as the interpreter can execute the same function from its S-expression definition. Subroutines typically take 70-80 per cent of the storage required by their corresponding S-expressions.

The compiler as it exists on the standard compiler tape is a machine language program that was obtained by having the S-expression definition of the compiler work on itself through the interpreter.

The compiler is designed so that compiled functions and interpretal [sic] functions can be intermixed freely. Suitable declarations allow free variables to be transmitted between the compiled functions and the interpreter.

There were some interesting limitations to the compiler, perhaps for performance reasons. For example, checks for the existence of free variables used by the compiled functions seem to have been left out. From section "Free Variables":

When a variable is used free, it must have been bound by a higher level function. If a program is being run interpretively, and a free variable is used without having been bound on a higher level, error diagnostic *A 8* will occur.

If the program is being run compiled, the diagnostic may not occur, and the variable may have value NIL.

All free variables in compiled programs must be declared SPECIAL or COMMON.

 

  • 2
    Re, "interesting limitations to the compiler." IIRC, One of the innovations of Common Lisp was the explicit requirement that compiling a function should not change its behavior in any way. Prior to that, programmers using certain LISP systems had to be aware of subtle behavioral differences between compiled code and interpreted code. (e.g., meaning of "local" variables in MacLisp.) – Solomon Slow Sep 10 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.