5.17 Notes and Further Reading
John McCarthy, the original designer of Lisp, received the ACM A. M. Turing Award in 1971 for contributions to artificial intelligence, including the creation of Lisp. For a detailed account of the history of Lisp we refer readers to McCarthy (1981). For a concise introduction to Lisp, we refer readers to Sussman, Steele, and Gabriel (1993).
In his 1978 Turing Award paper, John Backus described how the style of functional programming embraced by a language called FP is different from languages based on the λ-calculus:
An FP system is based on the use of a fixed set of combining forms called functional forms. These, plus simple definitions, are the only means of building new functions from existing ones; they use no variables or substitutions rules, and they become the operations of an associated algebra of programs. All the functions of an FP system are of one type: they map objects onto objects and always take a single argument. (Backus 1978, p. 619)
While FP was never fully embraced in the industrial programming community, it galvanized debate and interest in functional programming and subsequently influenced multiple languages supporting a functional style of programming (Interview with Simon Peyton-Jones 2017).
Design Guidelines 2–8 in Table 5.7 correspond to the First, Second, Fifteenth, Thirteenth, Twelfth, Eleventh, and Sixth Commandments, respectively, from Friedman and Felleisen (1996a, 1996b). The function mystery from Programming Exercise 5.6.9 is the function scramble from Friedman and Felleisen (1996b, pp. 11–15, 35, and 76). The functions remove_first, remove_all, remove_all* in Section 5.10.1 are from Friedman and Felleisen (1996a, Chapters 3 and 5), where they are called rember, multirember, and rember*, respectively.
For a derivation of the Y combinator, we refer readers to Gabriel (2001). For more information on bottom-up programming, we refer readers to Graham (1993, 1996) and Krishnamurthi (2003).
Scheme was the first Lisp dialect to use lexical scoping, which is discussed in Chapter 6. The language also required implementations of it to perform tail-call optimization, which is discussed in Chapter 13. Scheme was also the first language to support first-class continuations, which are an important ingredient for the creation of user-defined control structures and are also discussed Chapter 13.