Essentials of Programming Languages
Encyclopedia
Essentials of Programming Languages (EOPL) is a textbook on programming language
s by Daniel P. Friedman
, Mitchell Wand
, and Christopher T. Haynes.
EOPL surveys the principles of programming languages from an operational perspective. It starts with an interpreter in Scheme for a simple functional core language similar to the lambda calculus
and then systematically adds constructs. For each addition, for example, variable assignment or thread-like control, the book illustrates an increase in expressive power of the programming language and a demand for new constructs for the formulation of a direct interpreter. The book also demonstrates that systematic transformations, say store-passing style or continuation-passing style
can eliminate certain constructs from the language in which the interpreter is formulated.
The second part of the book is dedicated to a systematic translation of the interpreter(s) into register machine
s. The transformations show how to eliminate higher-order closures; continuation objects; recursive function calls; and more. At the end, the reader is left with an "interpreter" that uses nothing but tail-recursive function calls and assignment statements plus conditionals. It becomes trivial to translate this code into a C program or even an assembly program. As a bonus, the book shows how to pre-compute certain pieces of "meaning" and how to generate a representation of these pre-computations. Since this is the essence of compilation, the book also prepares a course on the principles of compilation and language translation, a related but distinct topic.
Like SICP
, EOPL represents a significant departure from the prevailing textbook approach in the 1980s. At the time, a book on the principles of programming languages presented four to six (or even more) programming languages and discussed their programming idioms and their implementation at a high level. The most successful books typically covered ALGOL 60
(and the so-called Algol family of programming languages), SNOBOL
, Lisp, and Prolog
. Even today a fair number of textbooks on programming languages are just such surveys, though their scope has narrowed.
EOPL was started in 1983 when Indiana was one of the leading departments in programming language research. Eugene Kohlbecker, one of Friedman's PhD students, transcribed and collected his "311 lectures". Other faculty members, including Mitch Wand and Christopher Haynes, started contributing and turned "The Hitchhiker's Guide to the Meta-Universe" -- as Kohlbecker had called it -- into the systematic, interpreter and transformation-based survey that it is now. Over the 25 years of its existence, the book has become a near-classic; it is now in its third edition, including additional topics such as 'types' and 'modules'. Its first part now incorporates ideas on programming from HtDP
, another non-conventional text book, which uses Scheme to teach the principles of program design. The authors as well as Matthew Flatt
have recently provided DrScheme
plug-ins and language levels for teaching with EOPL.
EOPL has spawned at least two other, related texts: Queinnec's Lisp in Small Pieces
and Krishnamurthi's Programming Languages: Applications and Implementations.
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
s by Daniel P. Friedman
Daniel P. Friedman
Daniel Paul Friedman is a professor of Computer Science at Indiana University in Bloomington, Indiana. His research focuses on programming languages, and he is a prominent author in the field....
, Mitchell Wand
Mitchell Wand
Mitchell Wand is a Computer Science professor at Northeastern University. He received his Ph.D. degrees from MIT. His research has centred on programming languages and is a member of the Northeastern Programming Research Lab. He is also the co-author of Essentials of Programming Languages.-External...
, and Christopher T. Haynes.
EOPL surveys the principles of programming languages from an operational perspective. It starts with an interpreter in Scheme for a simple functional core language similar to the lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
and then systematically adds constructs. For each addition, for example, variable assignment or thread-like control, the book illustrates an increase in expressive power of the programming language and a demand for new constructs for the formulation of a direct interpreter. The book also demonstrates that systematic transformations, say store-passing style or continuation-passing style
Continuation-passing style
In functional programming, continuation-passing style is a style of programming in which control is passed explicitly in the form of a continuation. Gerald Jay Sussman and Guy L. Steele, Jr...
can eliminate certain constructs from the language in which the interpreter is formulated.
The second part of the book is dedicated to a systematic translation of the interpreter(s) into register machine
Register machine
In mathematical logic and theoretical computer science a register machine is a generic class of abstract machines used in a manner similar to a Turing machine...
s. The transformations show how to eliminate higher-order closures; continuation objects; recursive function calls; and more. At the end, the reader is left with an "interpreter" that uses nothing but tail-recursive function calls and assignment statements plus conditionals. It becomes trivial to translate this code into a C program or even an assembly program. As a bonus, the book shows how to pre-compute certain pieces of "meaning" and how to generate a representation of these pre-computations. Since this is the essence of compilation, the book also prepares a course on the principles of compilation and language translation, a related but distinct topic.
Like SICP
Structure and Interpretation of Computer Programs
Structure and Interpretation of Computer Programs is a textbook published in 1984 about general computer programming concepts from MIT Press written by Massachusetts Institute of Technology professors Harold Abelson and Gerald Jay Sussman, with Julie Sussman...
, EOPL represents a significant departure from the prevailing textbook approach in the 1980s. At the time, a book on the principles of programming languages presented four to six (or even more) programming languages and discussed their programming idioms and their implementation at a high level. The most successful books typically covered ALGOL 60
ALGOL 60
ALGOL 60 is a member of the ALGOL family of computer programming languages. It gave rise to many other programming languages, including BCPL, B, Pascal, Simula, C, and many others. ALGOL 58 introduced code blocks and the begin and end pairs for delimiting them...
(and the so-called Algol family of programming languages), SNOBOL
SNOBOL
SNOBOL is a generic name for the computer programming languages developed between 1962 and 1967 at AT&T Bell Laboratories by David J. Farber, Ralph E. Griswold and Ivan P. Polonsky, culminating in SNOBOL4...
, Lisp, and Prolog
Prolog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
. Even today a fair number of textbooks on programming languages are just such surveys, though their scope has narrowed.
EOPL was started in 1983 when Indiana was one of the leading departments in programming language research. Eugene Kohlbecker, one of Friedman's PhD students, transcribed and collected his "311 lectures". Other faculty members, including Mitch Wand and Christopher Haynes, started contributing and turned "The Hitchhiker's Guide to the Meta-Universe" -- as Kohlbecker had called it -- into the systematic, interpreter and transformation-based survey that it is now. Over the 25 years of its existence, the book has become a near-classic; it is now in its third edition, including additional topics such as 'types' and 'modules'. Its first part now incorporates ideas on programming from HtDP
How to Design Programs
How to Design Programs is a textbook by Matthias Felleisen, Robert Bruce Findler, Matthew Flatt and Shriram Krishnamurthi on the systematic design of computer programs published in 2001 by MIT Press. The book introduces the concept of a design recipe, a six-step process for creating programs from...
, another non-conventional text book, which uses Scheme to teach the principles of program design. The authors as well as Matthew Flatt
Matthew Flatt
Matthew Flatt is a computer scientist, currently teaching at the University of Utah . He is also a member of the PLT group and, as such, responsible for the creation and maintenance of Racket....
have recently provided DrScheme
DrScheme
DrRacket is an open source integrated development environment for the Racket programming language which has a graphical user interface. It is widely used among introductory Computer Science courses that teach Scheme and is lauded for its simplicity and appeal to beginner programmers...
plug-ins and language levels for teaching with EOPL.
EOPL has spawned at least two other, related texts: Queinnec's Lisp in Small Pieces
Lisp in Small Pieces
Lisp in Small Pieces is a book by Christian Queinnec on Lisp, Scheme and other related dialects, their interpretation, semantics, and compilation and contains code for 11 interpreters and 2 compilers.The English title is a recursive acronym...
and Krishnamurthi's Programming Languages: Applications and Implementations.
See also
- Structure and Interpretation of Computer ProgramsStructure and Interpretation of Computer ProgramsStructure and Interpretation of Computer Programs is a textbook published in 1984 about general computer programming concepts from MIT Press written by Massachusetts Institute of Technology professors Harold Abelson and Gerald Jay Sussman, with Julie Sussman...
- How to Design ProgramsHow to Design ProgramsHow to Design Programs is a textbook by Matthias Felleisen, Robert Bruce Findler, Matthew Flatt and Shriram Krishnamurthi on the systematic design of computer programs published in 2001 by MIT Press. The book introduces the concept of a design recipe, a six-step process for creating programs from...