- Author
- John McCarthy, Massachusetts Institute of Technology
- Published
- April 1960
- Kind
- Foundational research paper describing the LISP system
- Original
- www-formal.stanford.edu/jmc/recursive/recursive.html
- Subject
- Compilers and interpreters
- Themes
- Rules that generate, Saying it exactly
What it is
John McCarthy, then at MIT, describes a recursive way to define functions. McCarthy also describes a programming system built on it. The paper covers the notation, the symbolic data, a universal evaluator and the machine implementation. It ends with a linear variant and a link between flowcharts and recursion.
What it says
- McCarthy says LISP was built on the IBM 704. It served experiments with the Advice Taker.
- McCarthy presents conditional expressions as believed new. They allow a convenient recursive way to define functions.
- The paper says five elementary functions, with conditionals and recursion, can express all computable functions.
- The paper describes a universal function that is both a theoretical model and an interpreter.
- Programmers need not return freed storage. Reclamation runs automatically when free storage runs out.
- As of February 1960, compiled functions ran about 60 times as fast as interpreted ones.
- It says lambda notation cannot name recursive functions, so the paper adds a label notation.
What evidence it gives
The paper gives formal definitions and worked examples. These include substitution, differentiation and a step-by-step trace of the evaluator. It describes the working IBM 704 system. Its performance figures are the compiled speed ratio and a reclamation time of several seconds. Neither comes with a benchmark.
Interests and limits
The author was in the group that built the system. The paper is the designer's own account. It is Part I only. The prose was read in full. The formulas and figures were images and were not read.