My Literature Recommendations
The following is my opinion of the best published books and
papers in various areas of computing.
The literature recommendations are organized by the
ACM Computing Reviews Classification System
(see a January issue of Computing Reviews for details).
Table of Contents
Although there are place-holders here for all of the top-level areas
in the ACM Computing Reviews Classification System,
the focus in is the areas D.1,
D.3,
and F.3.
If you're new to programming languages, you might start in
area D.3, perhaps in D.3.3.
- Undergraduate
- See Gary T. Leavens,
``Aiding Self-motivation with Readings
in Introductory Computing,''
Department of Computer Science, Iowa State University,
TR #94-08, May 1994.
- Undergraduate
- Backus's Turing award lecture sparked much of the research
in functional programming.
- John Backus,
Can Programming Be Liberated from the von Neumann Style?
A Functional Style and Its Algebra of Programs.
Communications of the ACM, 21(8):613-641,
August 1978.
- Harold Abelson and Gerald Jay Sussman with Julie Sussman.
Structure and Interpretation of Computer Programs.
MIT Press, second edition, 1996.
- George Springer and Daniel P. Friedman.
Scheme and the Art of Programming.
McGraw-Hill, 1989.
- Graduate
-
- Paul Hudak, Conception, Evolution, and Application
of Functional Programming Languages,
ACM Computing Surveys,
21(3):359-411, September 1989.
- Philip Wadler. The Essence of Functional Programming.
In Conference Record of the Nineteenth Annual
ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages,
pages 1-14. ACM, Janunary 1992.
- Martin C. Henson.
Elements of Functional Languages.
Blackwell Scientific Publications, Oxford, England, 1987.
- Graduate
-
- Gregory R. Andrews.
Concurrent Programming: Principles and Practice.
The Benjamin/Cummings Publishing Company, 1991.
- S. Mullender. Distributed Systems.
ACM Press, 1989.
- Undergraduate
- The following are good introductions to OOP.
- Brad J. Cox.
Object Oriented Programming: an Evolutionary Approach.
Addison-Wesley, 1986.
- Adele Goldberg and David Robson.
Smalltalk-80, The Language and its Implementation.
Addison-Wesley, 1983.
- E. Gamma and R. Helm and R. E. Johnson and J. Vlissides.
Design Patterns: Elements of Reusable Object-Oriented Software.
Addison-Wesley, 1995.
- Graduate
- The following introductions are suitable for graduate students.
- Bertrand Meyer.
Object-oriented Software Construction.
Prentice Hall, 1988.
- Bordon Blair, John Gallagher, David Hutchison, and Doug Shepherd.
Object-Oriented Languages, Systems and Applications.
Pitman Publishing, London, 1991.
- Undergraduate
-
- Leon Sterling and Ehud Shapiro.
The Art of Prolog.
The MIT Press, Cambridge, Mass., 1986.
- Undergraduate
-
- Barbara Liskov and John Guttag.
Abstraction and Specification in Program Development,
chapter 10.
The MIT Press, 1986.
- Graduate
-
- J. Guttag and J. J. Horning,
The Algebraic Specification of Abstract Data Types.
Acta Informatica, 10(1):27-52, 1978.
- John V. Guttag and James J. Horning, with S.J. Garland,
K.D. Jones, A. Modet, and J.M. Wing.
Larch: Languages and Tools for Formal Specification.
Springer-Verlag, NY, 1993.
- R. M. Burstall and J. A. Goguen,
Algebras, Theories and Freeness:
An Introduction for Computer Scientists.
In Manfred Broy and Gunther Schmidt, editors,
Theoretical Foundations of Programming Methodology:
Lecture Notes of an International Summer School
directed by F. L. Bauer, E. W. Dijkstra and C. A. R. Hoare,
volume 91 of series C,
pages 329-348.
D. Ridel, Dordrecht, Holland, 1982.
- Advanced Graduate/Researcher
- The last is a recent survey.
- Hartmut Ehrig and Bernd Mahr.
Fundamentals of Algebraic Specification 1:
Equations and Initial Semantics.
EATCS Monographs on Theoretical Computer Science.
Springer-Verlag, NY, 1985.
- Martin Wirsing, Peter Pepper, Helmut Partsch, Walter Dosch,
and Manfred Broy, On Hierarchies of Abstract Data Types.
Acta Informatica, 20(1):1-33, October 1983.
- Martin Wirsing.
Algebraic Specfication.
In J. van Leewen, editor,
Handbook of Theoretical Computer Science,
volume B: Formal Models and Semantics,
chapter 13, pages 675-788.
The MIT Press, New York, N.Y., 1990.
The following are about program verification from the software engineering
point of view.
For a view towards using verification techniques for programming
language semantics,
see underF.3.2 Algebraic approaches to semantics
about predicate transformer semantics.
- Undergraduate
-
The following are good introductions.
- Barbara Liskov and John Guttag.
Abstraction and Specification in Program Development,
chapter 11.
The MIT Press, 1986.
- David Gries.
The Science of Programming.
Springer-Verlag, New York, N.Y., 1981.
- Edsger W. Dijkstra.
A Discipline of Programming.
Prentice-Hall, Inc., Englewood Cliffs, N.J., 1976.
- Graduate
-
- Edward Cohen.
Programming in the 1990s: An Introduction
to the Calculation of Programs.
Springer-Verlag, New York, N.Y., 1990.
- Carroll Morgan.
Programming from Specifications.
Prentice Hall International, Hempstead, UK, 1990.
- Advanced Graduate/Researcher
-
- Patrick Cousot.
Methods and Logics for Proving Programs.
In J. van Leewen, editor,
Handbook of Theoretical Computer Science,
volume B: Formal Models and Semantics,
chapter 15, pages 841-993.
The MIT Press, New York, N.Y., 1990.
- Undergraduate
- The following books treat the semantics of several different languages.
- Daniel P. Friedman and Mitchell Wand and Christopher T. Haynes.
Essentials of Programming Languages.
McGraw-Hill, 1992.
- Samuel N. Kamin.
Programming Languages: An Interpreter-Based Approach.
Addison-Wesley, 1990.
- Graduate
- The following are modern book-length introductions.
- David A. Schmidt,
The Structure of Typed Programming Languages.
MIT Press, 1994.
- Glynn Winskel.
The Formal Semantics of Programming Languages.
MIT Pres, 1993.
- Advanced Graduate/Researcher
- The following uses category theory and is mathematically sophisticated.
- Carl A. Gunter.
Semantics of Programming Languages:
Structures and Techniques.
MIT Press, 1992.
- Underraduate
-
- Harold Abelson and Gerald Jay Sussman with Julie Sussman.
Structure and Interpretation of Computer Programs.
MIT Press, 1985.
- George Springer and Daniel P. Friedman.
Scheme and the Art of Programming.
McGraw-Hill, 1989.
- Graduate
-
- LaurenceC. Paulson.
ML for the Working Programmer.
Cambridge University Press, New York, N.Y., 1991.
- Graduate
-
- Barbara Liskov and Robert Scheifler.
Guardians and Actions: Linguistic Support for Robust,
Distributed Programs.
ACM Transactions on Programming Languages and Systems,
5(3):381-404, July 1983.
- Gregory R. Andrews and Ronald A. Olsson.
The SR Programming Language: Concurrency in Practice.
The Benjamin/Cummings Publishing Company,
Redwood City, CA, 1993.
- Undergraduate
-
- Bertrand Meyer.
Object-oriented Software Construction.
Prentice Hall, 1988.
- Adele Goldberg and David Robson.
Smalltalk-80, The Language and its Implementation.
Addison-Wesley, 1983.
- Graduate
-
- Bertrand Meyer. Eiffel: The Language.
Object-Oriented Series.
Prentice Hall, New York, N.Y., 1992.
- Gregor Kiczales, Jim des Rivieres, and Daniel G. Bobrow.
The Art of the Metaobject Protocol.
The MIT Press, Cambridge, Mass., 1991.
- Craig Schaffert, Topher Cooper, Bruce Bullis, Mike Kilian,
and Carrie Wilpolt.
An Introduction to Trellis/Owl.
ACM SIGPLAN Notices, 21(11):9--16, November 1986.
OOPSLA '86 Conference Proceedings, Norman Meyrowitz (editor),
September 1986, Portland, Oregon.
- Undergraduate
- The following are good general references in this area.
- Daniel P. Friedman and Mitchell Wand and Christopher T. Haynes.
Essentials of Programming Languages.
McGraw-Hill, 1992.
- Samuel N. Kamin.
Programming Languages: An Interpreter-Based Approach.
Addison-Wesley, 1990.
- Graduate
- The following are collections of good original papers.
- Anthony I. Wasserman.
TUTORIAL Programming Language Design.
IEEE Computer Society Press, Los Alamitos, Calif., 1980.
(Initally presented at Compsac80,
The IEEE Computer Society's Fourth International
Computer Software & Applications Conference, October 27-31,
1980.
The IEEE catalog number is EHO 164-4.)
- Ellis Horowitz.
Programming Languages: A Grand Tour (Third Edition).
Computer Science Press, Rockville, Maryland, 1987.
- Undergraduate
- The following gets the idea of data abstraction across clearly.
- Barbara Liskov and John Guttag.
Abstraction and Specification in Program Development.
The MIT Press, 1986.
- Graduate
-
- B. Liskov.
On Linguistic Support for Distributed Programs.
In Proceedings Symposium on Reliability in
Distributed Software and Database Systems, Pittsburgh,
pages 53-60.
July, 1981.
- Barbara Liskov, Maurice Herlihy, and Lucy Gilbert.
Limitations of Synchronous Communication with Static
Process Structure in Languages for Distributed Computation.
In Conference Record of the Thirteenth Annual ACM
Symposium on Principles of Programming Languages,
St. Petersburg Beach, Florida, pages 150-159.
ACM, January, 1986.
- Undergraduate
-
- George Springer and Daniel P. Friedman.
Scheme and the Art of Programming,
chapters 16-17.
McGraw-Hill, 1989.
- Undergraduate
-
- Daniel P. Friedman and Matthias Felleisen.
The Little LISPer.
Trade edition.
The MIT Press, 1987.
- Harold Abelson and Gerald Jay Sussman with Julie Sussman.
Structure and Interpretation of Computer Programs.
MIT Press, 1985.
- George Springer and Daniel P. Friedman.
Scheme and the Art of Programming.
McGraw-Hill, 1989.
There are really two different approaches to semantics
that fall in this category: techniques using classical techniques of algebra,
and those using predicate transformers.
A good paper on the algebraic approach is the following.
- Graduate
-
- Manfred Broy, Martin Wirsing, and Petter Pepper.
On the Algebraic Definition of Programming Languages.
ACM Transactions on Programming Languages and Systems,
9(1):54--99, January 1987.
My recommendations for literature on predicate transformer semantics
are the following.
- Graduate
-
- Edsger W. Dijkstra and Carel S. Scholten.
Predicate Calculus and program semantics.
Springer-Verlag, NY, 1990.
- Advanced Graduate/Researcher
-
- Wim H. Hesselink.
Programs, Recursion, and Unbounded Choice,
volume 27 of
Cambridge Tracts in Theoretical Computer Science.
Cambridge University Press, New York, N.Y., 1992.
- Undergraduate
-
- R. D. Tennent,
The Denotational Semantics of Programming Languages.
Communications of the ACM,
19(8):437-453,
August 1976.
- Lloyd Allison.
A Practical Introduction to Denotational Semantics.
Cambridge University Press, 1986.
- Graduate
- The following are modern book-length introductions, although somewhat
dated by now.
- David A. Schmidt.
Denotational Semantics:
A Methodology for Language Development.
Allyn and Bacon, Inc., 1986.
- J. Stoy.
Denotational Semantics: The Scott-Strachey Approach
to Programming Language Theory.
MIT Press, 1977.
- Advanced Graduate/Researcher
- The articles are good references for the researcher.
- Peter D. Mosses. Denotational Semantics.
In J. van Leewen, editor,
Handbook of Theoretical Computer Science,
volume B: Formal Models and Semantics,
chapter 11,
pages 577-631.
The MIT Press, 1990.
- C. A. Gunter and D. S. Scott. Semantic Domains.
In J. van Leewen, editor,
Handbook of Theoretical Computer Science,
volume B: Formal Models and Semantics,
chapter 12,
pages 789-840.
The MIT Press, 1990.
- Undergraduate
- An excellent introduction to structural operational semantics is the
following book.
- Matthew Hennessy.
The Semantics of Programming Languages: an Elementary
Introduction using Structural Operational Semantics.
Wiley, 1990.
- Graduate
-
- Edigio Astesiano,
Inductive and Operational Semantics.
In E. J. Neuhold and M. Paul, editors,
Formal Description of Programming Concepts,
pages 51-136.
Springer-Verlag, 1991.
- Advanced Graduate/Researcher
- Landin's SECD machine is defined in his paper below.
- P. J. Landin, The Mechanical Evaluation of Expressions.
Computer Journal,
6:308-320, 1964.
- G. D. Plotkin,
LCF Considered as a Programming Language.
Theoretical Computer Science,
5:223-255, 1977.
- Undergraduate
- The following are some good introductions to type systems, although
perhaps more appropriate at the graduate level.
- James H. Morris, Jr., Protection in Programming Languages.
Communications of the ACM, 16(1):15-21,
January 1973.
- Luca Cardelli. Typeful Programming.
In E. J. Neuhold and M. Paul, editors,
Formal Description of Programming Concepts,
pages 431-507.
Springer-Verlag, 1991,
- Bengt Nordström and Kent Peterson.
Types and Specifications.
In R. E. A. Mason, editor,
Information Processing 83,
pages 915-920.
Elsevier Science Publishers B.V. (North-Holland),
September, 1983.
- Graduate
-
- Robin Milner, A Theory of Type Polymorphism in Programming.
Journal of Computer and System Sciences,
17(3):348-375,
December 1978.
- Robert Harper and John C. Mitchell,
On the Type Structure of Standard ML.
ACM Transactions on Programming Languages and Systems,
15(2):211-252, April 1993.
- Luca Cardelli, A Semantics of Multiple Inheritance.
Information and Computation,
76(2/3):138-164, Feb./March 1988.
- Advanced Graduate/Researcher
-
- Jean-Yves Girard and Yves Lafont and Paul Taylor.
Proofs and Types.
Cambridge University Press, 1989.
- John C. Mitchell. Type systems for programming languages.
In J. van Leewen, editor,
Handbook of Theoretical Computer Science,
volume B: Formal Models and Semantics,
chapter 8,
pages 365-458.
The MIT Press, 1990.
- Roland Backhouse, Paul Chisholm, Grant Malcolm, and Erik Saaman,
Do-it-Yourself Type Theory.
Formal Aspects of Computing,
1(1):19-84, January - March 1989.
- Advanced Graduate/Researcher
- The following is an encyclopedic reference.
- H. P. Barendregt.
The Lambda Calculus: Its Syntax and Semantics.
North-Holland, 1984.
- Graduate
-
- Hartmut Ehrig and Bernd Mahr.
Fundamentals of Algebraic Specification 1:
Equations and Initial Semantics,
chapter 3.
EATCS Monographs on Theoretical Computer Science.
Springer-Verlag, NY, 1985.
- Donald Sannella and Andrzej Tarlecki,
On Observational Equivalence and Algebraic Specification.
Journal of Computer and System Sciences,
34(2/3):150-178, April/June 1987.
- J. A. Goguen and R. M. Burstall.
Introducing Institutions.
In Edmund Clarke and Dexter Kozen, (editors),
Logics of Programs: Workshop, Carnegie Mellon University,
June 1983,
volume 164 of
Lecture Notes in Computer Science,
pages 221-256,
Springer-Verlag,
New York, N.Y., 1984.
Category theory figures prominently in much work on semantics
at advanced levels.
- Graduate
- The following are good texts for learning category theory.
- Benjamin C. Pierce.
Basic Category Theory for Computer Scientists.
The MIT Press, 1991.
- R. Goldblatt.
Topoi: The Categorial Analysis of Logic
(Revised Edition).
North-Holland, 1984.
- Michael Barr and Charles Wells.
Category Theory for Computing Science.
Prentice-Hall International Series in Computer Science.
Prentice-Hall, 1990.
- Advanced Graduate/Researcher
- The MacLane book cited is the category theory ``bible''.
- Saunders Mac Lane.
Categories for the Working Mathematician,
volume 5 of Graduate Texts in Mathematics.
Springer-Verlag, 1971.
Last update $Date: 1997/09/10 21:59:11 $
Gary T. Leavens