References

1

Abdali, S. Kamal. ``An abstraction algorithm for combinator logic.'' Journal of Symbolic Logic, volume 41, number 1, March 1976, pages 222-224.

2

Abelson, Harold, and Gerald Jay Sussman. Structure and Interpretation of Computer Programs. MIT Press, Cambridge, Massachusetts, 1985.

3

Aho, Alfred Vaino, Ravi Sethi, and Jeffrey David Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, Massachusetts, 1986.

A comprehesive text about the theory and practice of building compilers.

4

Apt, Krzysztof R. ``Ten years of Hoare's logic: A survey--Part I.'' ACM Transactions on Programming Languages and Systems, volume 3, number 4, October 1981, pages 431-483.

5

Babbage, Charles. ``On the influence of signs in mathematical reasoning.'' Transactions of the Cambridge Philosophical Society, volume 2, 1827, pages 325-377.

6

Backus, John. ``Can programming be liberated from the von Neumann style? A functional style and its algebra of programs.'' Communications of the ACM, volume 21, number 8, 1978, pages 613-641. Reprinted in [95, pages 174-202].

The 1977 Turing Lecture.

7

Backus, John. ``The history of FORTRAN I, II, and III.'' In History of Programming Languages, edited by Richard L. Wexelblat, Academic Press, New York, 1981, pages 25-45.

8

Baker, T. P. ``One pass algorithm for overload resolution in Ada.'' ACM Transactions on Programming Languages and Systems, volume 4, number 4, October 1982, pages 601-614.

9

Barendregt, Hendrik Pieter. The Lambda Calculus: Its Syntax and Semantics, revised edition. Studies in logic and the foundations of mathematics, volume 103. North-Holland, Amsterdam, 1984.

10

Barnes, John Gilbert Presslie. Programming in Ada, second edition. International computer science series. Addison-Wesley, London, England, 1984.

11

Barnes, John Gilbert Presslie. Programming in Ada: Plus an Overview of Ada 9X, fourth edition. International computer science series. Addison-Wesley, London, 1994.

12

Barron, David William. Comparative Programming Languages. American Elsevier, New York, 1968.

13

Barwise, Jon. ``Mathematical proofs of computer system correctness.'' Notices of the American Mathematical Society, September 1989, pages 844-851.

14

Baxter, Nancy H., Ed Dubinsky, and Gary Marc Levin. Learning Discrete Mathematics with ISETL. Springer-Verlag, New York, 1989.

15

Beeson, Michael J. ``Problematic principles in constructive mathematics.'' In Logic Colloquium '80, edited by Dirk van Dalen, D. Lascar, and J. Smiley, North-Holland, Amsterdam, 1982, pages 11-55.

16

Borland Interantional, Inc. Turbo PROLOG owner's handbook, 1986.

17

Bratko, Ivan. Prolog Programming for Artificial Intelligence, second edition. Addison-Wesley, Wokingham, England, 1990.

18

Cajori, Florian. A History of Mathematical Notations. 2 volumes. Open Court, Chicago, Illinois, 1928-29.

19

Cardelli, Luca. ``A semantics of multiple inheritance.'' In Semantics of data types, edited by Gilles Kahn, David B. MacQueen, and Gordon Plotkin, Springer-Verlag, Berlin, 1984, pages 51-67.

The paper introduces the record-based model of object-oriented programming.

20

Cardelli, Luca. ``Amber.'' In Combinators and Functional Programming Languages, edited by Guy Cousineau, Pierre-Louis Curien, and Bernard Robinet, Springer-Verlag, Berlin, 1986, pages 21-47.

21

Cardelli, Luca. ``Basic polymorphic typechecking.'' Science of Computer Programming, volume 8, number 2, April 1987, pages 147-172.

22

Cardelli, Luca, and Peter Wegner. ``On understanding types, data abstraction, and polymorphism.'' ACM Computing Surveys, volume 17, number 4, 1985, pages 471-522.

23

Ceruzze, Paul E. Beyond the Limits: Flight Enters the Computer Age. MIT Press, Cambridge, MA, 1989.

In chapter 9 the myth is debunked that a FORTRAN punctuation error caused the destruction of Mariner I, a U.S. spaceprobe to Venus in 1962. Actually, a handwriting error was involved, and FORTRAN was not being used in the flight guidance software at all.

24

Chang, Chin-Liang, and Richard Char-Tung Lee. Symbolic Logic and Mechanical Theorem Proving. Academic Press, New York, 1973.

25

Chomsky, Noam. Aspects of the Theory of Syntax. MIT Press, Cambridge, Massachusetts, 1965.

An analysis of the structure of natural language.

26

Church, Alonzo. The Calculi of Lambda-Conversion. Annals of Mathematical Studies, number 6. Princeton University Press, Princeton, New Jersey, 1941.

27

Church, Alonzo, and J. Barkley Rosser. ``Some properties of conversion.'' Transactions of the American Mathematical Society, volume 39, 1936, pages 472-482.

28

Clark, R. Lawrence. ``A linguistic contribution to GOTO-less programming.'' Datamation, volume 19, number 12, 1973, pages 62-63. Reprinted in Communications of the ACM, volume 27, number 4, April 1984, pages 349-350.

This tongue-in-cheek article advocates the COME FROM control construct to replace the GO TO construct.

29

Cleaveland, J. Craig. An Introduction to Data Types. Addison-Wesley, Reading, Massachusetts, 1986.

A book devoted to data types of programming languages, mostly Ada or Ada-like. Contains a little about universal polymorphism, and a little about algebraic specification.

30

Clocksin, William F., and Christopher S. Mellish. Programming in PROLOG, second edition. Springer-Verlag, Berlin, 1984.

31

Clocksin, William F., and Christopher S. Mellish. Programming in PROLOG, third revised and extended edition. Springer-Verlag, Berlin, 1987.

32

Cohen, Jacques. ``Describing PROLOG by its interpretation and compilation.'' Communications of the ACM, volume 28, number 12, December 1985, pages 1311-1324.

33

Cohen, Norman H. Ada As a Second Language. McGraw-Hill, New York, 1986.

34

Constable, Robert L., Stuart F. Allen, H. M. Bromley, W. Rance Cleaveland, J. F. Cremer, Robert William Harper, Jr., D. J. Howe, T. B. Knoblock, N. P. Mendler, P. Panangaden, James T. Sasaki, and S. F. Smith. Implementing Mathematics with the NUPRL Proof Development System. Prentice Hall, Englewood Cliffs, New Jersey, 1986.

35

Cook, Steven A. ``Soundness and completeness of an axiom system for program verification.'' SIAM Journal on Computing, volume 7, number 1, February 1978, pages 70-90.

Proof of soundness and relative completeness of Hoare logic for a simple imperative language. A proof rule for procedures with global variables is given.

36

Cousineau, Guy, Pierre-Louis Curien, and M. Mauny. ``The categorical abstract machine.'' In Functional programming languages and computer architecture, edited by Jean-Pierre Jouannaud, Springer-Verlag, Berlin, 1985, pages 50-64.

37

Curien, Pierre-Louis. Categorical Combinators, Sequential Algorithms and Functional Programming. Research notes in theoretical computer science. Pitman, London, 1986.

38

Curry, Haskell Brooks, and Robert Feys. Combinatory Logic. Studies in logic and the foundations of mathematics. North-Holland, Amsterdam, 1958.

39

Dahl, Ole-Johan, and Kristen Nygaard. ``The development of the SIMULA languages.'' In History of Programming Languages, edited by Richard L. Wexelblat, Academic Press, New York, 1981, pages 439-480.

40

Damas, Luis Manuel Martins, and Robin Milner. ``Principal type-schemes for functional programs.'' In Conference Record of the Ninth Annual ACM Symposium on Principles of Programming Languages, 1982, pages 207-212.

41

Darlington, John, Peter Henderson, and David A. Turner, editors. Functional Programming and Its Applications: An Advanced Course. Cambridge University Press, Cambridge, 1982.

42

Davis, Ruth E. ``Logic programming and Prolog: A tutorial.'' IEEE Software, volume 2, number 5, September 1985, pages 53-62. Reprinted in [95, pages 493-502].

43

de Bakker, Jacobus Willem. Mathematical Theory of Program Correctness. Prentice-Hall International series in computer science. Prentice-Hall International, London, 1980.

44

Demers, Alan J. ``A simplified type structure for Ada.'' In Jornadas En Computacion, June 1982, pages 86-104.

A case is made for a uniform treatment of objects, packages, generics and types under the principle of type-completeness. Compile-time type checking can be preserved by ``manifestly'' safe expressions (constants).

45

Demers, Alan J., and James E. Donahue. ``Data types, parameters and type checking.'' In Conference Record of the Seventh Annual ACM Symposium on Principles of Programming Languages, 1980, pages 12-23.

46

Demers, Alan J., and James E. Donahue. ```Type-completeness' as a language principle.'' In Conference Record of the Seventh Annual ACM Symposium on Principles of Programming Languages, 1980, pages 234-244.

47

Demers, Alan J., James E. Donahue, and Glenn Skinner. ``Data types as values.'' In Conference Record of the Fifth Annual ACM Symposium on Principles of Programming Languages, 1978, pages 23-30.

48

DeMillo, Richard A., Richard J. Lipton, and Alan J. Perlis. ``Social processes and proofs of theorems and programs.'' Communications of the ACM, volume 22, number 5, May 1979, pages 271-280.

49

Dijkstra, Edsger Wybe. ``Defense of ALGOL 60.'' Communications of the ACM, volume 4, number 11, November 1961, pages 502-503.

This letter to the editor points out the advantages of the call-by-name parameter passing in ALGOL 60. The examples used are summations of array elements.

50

Dijkstra, Edsger Wybe. ``Go to statement considered harmful.'' Communications of the ACM, volume 11, number 3, March 1968, pages 147-148. Reprinted in [196, 102-103].

This letter to the editor ignited the GO TO controversy.

51

Dijkstra, Edsger Wybe. ``Guarded commands, nondeterminacy and the formal derivation of programs.'' Communications of the ACM, volume 18, number 8, August 1975, pages 453-457. Reprinted in [196, pages 453-457].

52

Dijkstra, Edsger Wybe. A Discipline of Programming. Prentice Hall, Englewood Cliffs, New Jersey, 1976.

53

Dijkstra, Edsger Wybe. ``On a political pamphlet from the Middle Ages (Commentary on a paper by DeMillo, Lipton, and Perlis).'' Software Engineering Notes, volume 3, number 2, April 1978, pages 14-17.

54

Dijkstra, Edsger Wybe. ``On the cruelty of really teaching computing science.'' Communications of the ACM, volume 32, number 12, December 1989, pages 1398-1404.

55

Downey, Peter J., and Ravi Sethi. ``Correct computation rules for recursive languages.'' SIAM Journal on Computing, volume 5, number 3, September 1976.

56

Driver, Godfrey Rolles. Semitic Writing from Pictograph to Alphabet. Oxford University Press, London, 1976.

57

Dummett, Michael A. E. Elements of Intuitionism. Oxford Logic Series. Oxford University Press, London, 1977.

58

Eisenbach, Susan, editor. Functional programming: Languages, tools and architectures. Ellis Horwood series in computers and their applications. Ellis Horwood, Chichester, England, 1987.

59

Ellis, Margaret A., and Bjarne Stroustrup. The Annotated C++ Reference Manual. Addison Wesley, Reading, Massachusetts, 1990.

A definition of the C++ programming language with commentary and examples of individual features. Included are descriptions of templates and exception handling. This reference manual was chosen by ANSI to serve as the starting point for formal standardization.

60

Falkoff, Adin D., and Kenneth E. Iverson. ``The design of APL.'' IBM Journal of Research and Development, July 1973, pages 324-334. Reprinted in [95, pages 240-250].

61

Falkoff, Adin D., and Kenneth E. Iverson. ``The evolution of APL.'' In History of Programming Languages, edited by Richard L. Wexelblat, Academic Press, New York, 1981, pages 661-674.

62

Fetzer, James H. ``Program verification: The very idea.'' Communications of the ACM, volume 31, number 9, Spetember 1988, pages 1048-1063.

63

Field, Anthony J., and Peter G. Harrison. Functional Programming. International computer science series. Addison Wesley, Wokingham, England, 1988.

64

Fisher, David A. ``DoD's common programming language effort.'' IEEE Computer, volume 11, number 3, March 1978, pages 24-33. Reprinted in [196, page 316-325].

65

Fleck, A. C. ``On the impossibility of content exchange through the by-name parameter transmission mechanism.'' SIGPLAN Notices, volume 11, number 11, November 1976, pages 38-41.

66

Frederick P. Brooks, Jr. The Mythical Man-Month: Essays on Software Engineering. Addison-Wesley, Reading, Massachusetts, 1975. Reprinted with corrections in 1982.

These essays are based on the author's experience as manager of the group that developed OS/360 at IBM in 1964 and 1965

67

Friedman, Daniel Paul, Mitchell Wand, and Christopher T. Haynes. Essentials of Programming Languages. MIT Press, Cambridge, Massachusetts, 1992.

A textbook on programming languages. The programming language Scheme is used as an executable metalanguage.

68

Gallier, Jean H. Logic for Computer Science: Foundations of Automatic Theorem Proving. Harper & Row, New York, 1986.

69

Gannon, John D., and James J. Horning. ``Language design for programming reliability.'' IEEE Transactions on Software Engineering, volume SE-1, number 2, June 1975, pages 179-191.

A study of programming errors.

70

Gehani, Narain, and Andrew D. McGettrick, editors. Software Specification Techniques. International Computer Science Series. Addison-Wesley, Wokingham, England, 1986.

71

Gelernter, David Hillel, and Suresh Jagannathan. Programming Linguistics. MIT Press, Cambridge, Massachusetts, 1990.

72

Genesereth, Michael R., and Nils J. Nilsson. Logical Foundations of Artificial Intelligence. Morgan Kaufmann, Los Altos, California, 1987.

73

Goguen, Joseph A., J. W. Thatcher, and E. G. Wagner. ``An initial algebra approach to the specification, correctness, and implementation of abstract data types.'' In Data structuring, edited by Raymond Tzuu Yeh, Prentice Hall, Englewood Cliff, New Jersey, 1978, pages 80-149.

74

Goldberg, Adele. Smalltalk-80: The Interactive Programming Environment. Addison-Wesley series in computer science. Addison-Weseley, Reading, Massachusetts, 1985.

75

Goldberg, Adele, and David Robson. Smalltalk-80: The Language and Its Implementation. Addison-Wesley series in computer science. Addison-Weseley, Reading, Massachusetts, 1983.

76

Goldberg, Adele, and David Robson. Smalltalk-80: The Language. Addison-Wesley series in computer science. Addison-Weseley, Reading, Massachusetts, 1989.

77

Gordon, Michael J. C. Programming Language Theory and Its Implementation: Applicative and Imperative Paradigms. Prentice-Hall International series in computer science. Prentice Hall, New York, 1988.

Part I is about Hoare logic, part II is about the lambda calculus and combinators, part III about is about LISP and theorem proving.

78

Gries, David. Compiler Construction for Digital Computers. John Wiley & Sons, 1971.

79

Gries, David. The Science of Programming. Texts and monographs in computer science. Springer-Verlag, New York, 1981.

80

Gunter, Carl A. Semantics of Programming Languages: Structures and Techniques. MIT Press, Cambridge, Massachusetts, 1992.

81

Hamming, Richard W. ``The unreasonable effectiveness of mathematics.'' American Mathematical Monthly, volume 82, number 2, February 1980, pages 81-90.

82

Henderson, Peter. Functional Programming. Prentice-Hall International series in computer science. Prentice-Hall International, Englewood Cliffs, New Jersey, 1980.

83

Hennessy, Matthew. The Semantics of Programming Languages: an Elementary Introduction Using Structural Operational Semantics. Wiley, Chichester, England, 1990.

84

Higman, Bryan. A Comparative Study of Programming Languages. American Elsevier, New York, 1967.

85

Hillis, W. Daniel, and Guy L. Steele Jr. ``Data parallel algorithms.'' Communications of the ACM, volume 29, number 12, December 1986, pages 1170-1183.

86

Hoare, Charles Antony Richard. ``An axiomatic basis for computer programming.'' Communications of the ACM, volume 12, number 10, October 1969, pages 576-580, 583.

Paper introducing the axiomatic approach to programming languages semantics.

87

Hoare, Charles Antony Richard. ``Hints on programming language design.'' In SIGACT/SIGPLAN Symposium on principles of programming languages, October 1973. Reprinted in [95, pages 35-40].

The article stresses simplicity, fast translation, efficient object code, readability and abstract types.

88

Hoare, Charles Antony Richard. ``Recursive data structures.'' International Journal of Computer and Information Sciences, volume 4, number 2, June 1975, pages 105-132.

In this article Hoare maintains that pointers are bad and can be replaced by recursive data types.

89

Hoare, Charles Antony Richard, and J. C. Shepherdson, editors. Mathematical logic and programming languages. Prentice-Hall International series in computer science. Prentice-Hall International, 1985.

The papers in this book were first published in the Philosophical Transactions of the Royal Society, Series A, volume 312, 1984.

90

Hoare, Charles Antony Richard, and Niklaus Emil Wirth. ``An axiomatic definition of the programming language Pascal.'' Acta Informatica, volume 2, 1973, pages 335-355. Reprinted in [196, page 506-526].

91

Hofstadter, Douglas R. Gödel, Escher, Bach: An Eternal Golden Braid. Basic Books, New York, 1979.

This book won a Pulitzer prize for general nonfiction in 1980. It discusses recursion, formal systems, and Gödel's incompleteness theorem using examples from Dutch artist Mauritis C. Escher and the composer Johann Sebastian Bach. Short stories about Achilles and the Tortoise inspired by a short story by Lewis Carroll begin each chapter.

92

Holt, Richard C. Design goals for the Turing programming language. Technical Report CSRI-187, Computer Systems Research Institute, University of Toronto, August 1986.

93

Holt, Richard C., and James R. Cordy. ``The Turing programming language.'' Communications of the ACM, volume 31, number 12, December 1988, pages 1410-1421.

94

Horn, Alfred. ``On sentences which are true of direct unions of algebras.'' Journal of Symbolic Logic, volume 16, number 1, March 1951, pages 14-21.

This paper has very little to do with Horn clauses.

95

Horowitz, Ellis, editor. Programming Languages: A Grand Tour, third edition. Computer Science Press, Rockville, Maryland, 1987.

A collection of 30 significant papers concering the field of programming languages, especially Pascal and other ALGOL-like languages. Includes a bibliography and an index.

96

Hudak, Paul, and Benjamin Goldberg. ``Experiments in diffused combinator reduction.'' In Proceedings of the Symposium on LISP and Functional Programming, ACM, 1984, pages 167-176.

97

Huet, Gérard P. ``Confluent reductions: Abstract properties and applications to term rewriting systems.'' Journal of the ACM, volume 27, number 4, October 1980, pages 797-821.

98

Huet, Gérard P., and Derek C. Oppen. ``Equations and rewrite rules.'' In Formal Languages, edited by Ronald V. Book, Academic Press, New York, 1980.

99

Huskey, Vekna R., and Harry D. Huskey. ``Lady Lovelace and Charles Babbage.'' Annals of the History of Computing, volume 2, number 4, October 1980, pages 299-329.

100

Iverson, Kenneth E. A Programming Language. John Wiley & Sons, New York, 1962.

101

James, Carol L., and Duncan E. Morrill. ``The real Ada, Countess of Lovelace.'' ACM SIGSoft Engineering Notes, volume 8, number 1, January 1983, page 30.

Brief account of the naming of the programming language Ada and the life of Augusta Ada Bryon.

102

Jensen, Hans. Sign, Symbol, and Script: An Account of Man's Efforts to Write, third revised and enlarged edition. George Allen and Unwin, London, 1970.

103

Jensen, Kathleen, and Niklaus Wirth. Pascal: User Manual and Report, second edition. Springer-Verlag, New York, 1974.

104

Jensen, Kathleen, and Niklaus Wirth. Pascal: User Manual and Report, second and corrected edition. Springer-Verlag, New York, 1978.

105

Jensen, Kathleen, and Niklaus Wirth. Pascal User Manual and Report, third edition. Springer-Verlag, New York, 1985. Prepared by Andrew B. Mickel and James F. Miner.

106

Jensen, Kathleen, and Niklaus Wirth. Pascal User Manual and Report: ISO Pascal Standard, fourth edition. Springer-Verlag, New York, 1991. Revised by Andrew B. Mickel and James F. Miner.

A Pascal tutorial and the definitive Pascal reference incorporating revisions to the 1983 ISO Standard.

107

Johnston, John B. ``The contour model of block structured processes.'' SIGPLAN Notices, volume 6, number 2, February 1971, pages 55-82.

108

Kamin, Samuel N. Programming Languages: An Interpreter-Based Approach. Addison-Wesley, Reading, Massachusetts, 1990.

109

Kay, Alan C. ``The early history of Smalltalk.'' SIGPLAN Notices, volume 28, number 3, March 1993, pages 69-96.

110

Kernighan, Brian Wilson, and Dennis M. Ritchie. The C Programming Language, second edition. Prentice Hall, Englewood Cliffs, New Jersey, 1988.

The second edition of the classic work defining and explaining C. Although the second edition predates the official ANSI standard the book is a valuable reference to ANSI C. The biggest change over the original ``K&R'' language defined in the first edition is the addition of function prototypes.

111

Knight, Kevin. ``Unification: A multidisciplinary survey.'' Computing Surveys, volume 21, number 1, March 1989, pages 93-124.

The unification algorithm is useful in a large number of fields among which are type checking in programming langauges, resolution theorem proving, and natural language processing.

112

Knuth, Donald Ervin. ``Backus Normal Form vs. Backus Naur Form.'' Communications of the ACM, volume 7, number 12, December 1964, pages 735-736.

In this letter to the editor, Knuth argues that the name ``Backus Naur Form'' honoring Peter Naur is better than ``Backus Normal Form.'' The BNF notation is not a normal form at all.

113

Knuth, Donald Ervin. ``Semantics of context-free languages.'' Mathematical Systems Theory, volume 2, number 2, June 1968, pages 127-145. A corrigendum appears in volume 5, number 1, pages 95-96.

Origin of attribute grammars as a device to give meaning to programs by adding inherited and synthesized attributes to context-free free grammars.

114

Knuth, Donald Ervin. ``An empirical study of FORTRAN programs.'' Software--Practice and Experience, volume 1, 1971, pages 105-133.

115

Knuth, Donald Ervin. ``Ancient Babylonian algorithms.'' Communications of the ACM, volume 15, number 7, July 1972, pages 671-677. An errata appeared in volume 19, number 2, February 1976, page 108.

116

Knuth, Donald Ervin. ``Structured programming with go to statements.'' Computing Surveys, volume 6, December 1974, pages 261-301. Reprinted in [196, pages 104-144].

117

Knuth, Donald Ervin, and Jack N. Merner. ``Algol 60 confidential.'' Communications of the ACM, volume 4, number 6, June 1961, pages 268-272.

118

Knuth, Donald Ervin, and Luis Trabb Pardo. ``The early development of programming languages.'' In Encyclopedia of Computer Science and Technology, Marcel Dekker, New York, 1977, pages 419-96.

Detailed account of all early ``high-level'' programming languages.

119

Kowalski, Robert A. ``Algorithm = logic + control.'' Communications of the ACM, volume 22, number 7, July 1979, pages 424-436. Reprinted in [95, pages 480-492].

120

Krasner, Glenn, editor. Smalltalk-80: Bits of history, words of advice. Addison-Wesley series in computer science. Addison-Weseley, Reading, Massachusetts, 1983.

121

Lampson, Butler W., James J. Horning, Ralph L. London, James G. Mitchell, and G. J. Popek. ``Report on the programming language Euclid.'' SIGPLAN Notices, volume 12, number 3, February 1977.

122

Landin, Peter J. ``A lambda-calculus approach.'' In Advances in Programming and Non-Numerical Computation, edited by Leslie Fox, Pergamon Press, Oxford, 1966, pages 97-141.

123

Lindsey, Charles H. ``A history of ALGOL 68.'' SIGPLAN Notices, volume 28, number 3, March 1993, pages 97-132.

124

Liskov, Barbara H. ``Exception handling in CLU.'' IEEE Transactions on Software Engineering, November 1979, pages 545-558. Reprinted in [196, page 403-415].

125

Liskov, Barbara H., Alan Snyder, Russell Atkinson, and J. Craig Schaffert. ``Abstraction mechanisms in CLU.'' Communications of the ACM, volume 20, number 8, August 1977, pages 564-576.

126

Liskov, Barbara H., and Stephen N. Zilles. ``Programming with abstract data types.'' SIGPLAN Notices, volume 9, number 4, April 1974, pages 50-59. Reprinted in [196, page 189-198].

The language described in this paper is not given a name, but is an early version of the programming language CLU developed at MIT.

127

Lloyd, John Wylie. Foundations of Logic Programming. Springer-Verlag, Berlin, 1984.

128

Loeckx, Jacques J. C., Kurt Mehlhorn, and Reinhard Wilhelm. Grundlagen der Programmiersprachen. Teubner, Stuttgart, 1986.

129

Loeckx, Jacques J. C., Kurt Sieber, and Ryan D. Stansifer. The Foundations of Program Verification, second edition. Teubner, Stuttgart, 1987.

130

McCarthy, John. ``Towards a mathematical science of computation.'' In Information Processing 1962, edited by Cicely M. Popplewell, North-Holland, Amsterdam, 1963, pages 21-28.

131

McGettrick, Andrew D. The Definition of Programming Languages. Cambridge computer science texts, volume 11. Cambridge University Press, Cambridge, 1980.

132

Mackenzie, Charles E. Coded Character Sets, History and Development. Addison-Wesley, Reading, Massachusetts, 1980.

133

MacLennan, Bruce J. Principles of Programming Languages. Holt, Rinehart and Winston, New York, 1983.

134

Madsen, Ole Lehrmann, Birger Møller-Pederson, and Kristen Nygaard. Object-Oriented Programming in the BETA Programming Language. Addison-Wesley, Wokingham, England, 1993.

An introduction to programming in the BETA programming language.

135

Maier, David, and David S. Warren. Computing with Logic: Logic Programming with PROLOG. Benjamin Cummings, Menlo Park, California, 1988.

136

Manna, Zohar, and Adi Shamir. ``A new approach to recursive programs.'' In Perspectives on computer science, edited by Anita K. Jones, Academic Press, 1977, pages 103-124.

137

Marcotty, Michael, and Henry F. Ledgard. The Programming Language Landscape, second edition. Science Research Associates, Chicago, Illinois, 1986.

138

Marcotty, Michael, Henry F. Ledgard, and Gregor V. Bochmann. ``A sampler of formal definitions.'' Computing Surveys, volume 8, number 2, June 1976, pages 191-276.

139

Martelli, Alberto, and Ugo Montanari. ``An efficient unification algorithm.'' ACM Transactions on Programming Languages and Systems, volume 4, number 2, April 1982, pages 258-282.

140

Martin, Alain J. ``A general proof rule for procedures in predicate transformer semantics.'' Acta Informatica, volume 20, December 1983, pages 301-313.

Procedures with input (call-by-value), result, and value/result parameters are given a sound proof rule by considering the subprogram call to be an assignment to local variables from all the input parameters, followed by the body of the subprogram, followed by an assignment to all the output parameters.

141

Martin-Löf, Per. Notes on Constructive Mathematics. Almqvist & Wiksell, Stockholm, 1970.

142

Meyer, Albert R. Puzzles in programming logic. Technical report, MIT, November 1985.

143

Milner, Robin. ``A theory of type polymorphism in programming.'' Journal of Computer and System Sciences, volume 17, number 3, December 1978, pages 348-375.

144

Milner, Robin, Mads Tofte, and Robert William Harper, Jr. The Definition of Standard ML. MIT Press, Cambridge, MA, 1990.

The formal definition of the static and dynamic semantics of the Standard ML programming language.

145

Minsky, Marvin Lee. Computation: Finite and Infinite Machines. Prentice Hall, New York, 1967.

146

Moore, Doris Langley. Ada, Countess of Lovelace: Byron's legitimate daughter. Harper & Row, New York, 1977.

147

Morris, Jr., James H. ``Protection in programming languages.'' Communications of the ACM, volume 16, number 1, January 1973, pages 15-21.

148

Naveh, Joseph. Early History of the Alphabet: An Introduction to West Semitic Epigraphy and Palaeography. Magnes Press, Jerusalem, 1982.

149

Nelson, Greg, editor. Systems Programming with Modula-3. Prentice Hall series in innovative technology. Prentice Hall, Englewood Cliffs, New Jersey, 1991.

This collection contains the 50-page Modula-3 report defining the language. Other parts describe the standard libraries including the thread interface for concurrent programming and the ``pickle'' interface for persistent objects. The last chapter, ``How the Language Got Its Spots,'' is a fictional dialogue featuring Dr. Lambdaman and others that illuminates some aspects of the evolution of Modula-3.

150

Neumann, Peter G. ``Some reflections on a telephone switching problem.'' Communications of the ACM, volume 33, number 7, July 1990, page 154.

151

Nicholls, John E. The Structure and Design of Programming Languages. The Systems programming series. Addison-Wesley, Reading, Massachusetts, 1975.

The section on PL/I in the appendix has a two page summary of the development of the language up to 1974.

152

O'Donnell, Michael J. ``A critique of the foundations of Hoare style programming logics.'' Communications of the ACM, volume 25, number 12, December 1982, pages 927-935.

153

O'Donnell, Michael J. Equational Logic As a Programming Language. MIT Press, Cambridge, Massachusetts, 1985.

154

Pagan, Frank G. Formal Specification of Programming Languages. Prentice Hall, Englewood Cliffs, New Jersey, 1981.

155

Parnas, David Lorge. ``A technique for software module specificaton with examples.'' Communications of the ACM, volume 15, number 5, 1972, pages 330-336.

156

Paterson, M. S., and M. N. Wegman. ``Linear unification.'' In Proceedings of the Eighth Annual Symposium of Theory of Computing, 1976, pages 181-186.

157

Paulson, Lawrence C. ``Compiler generation from denotational semantics.'' In Methods and Tools for Compiler Construction, edited by Bernard Lorho, Cambridge University Press, Cambridge, England, 1984, pages 219-250.

158

Perlis, Alan J., and Klaus Samelson. ``Preliminary report--International Algebraic Language.'' Communications of the ACM, volume 1, number 12, December 1958, pages 8-22.

An early definition of the programming language ALGOL. This report appeared simultaneous in [159].

159

Perlis, Alan J., and Klaus Samelson. ``Report on the algorithmic language ALGOL.'' Numerische Mathematik, volume 1, January 1959, pages 41-60.

An early definition of the programming language ALGOL. This report appeared simultaneous in [158].

160

Popek, G. J., James J. Horning, Butler W. Lampson, James G. Mitchell, and Ralph L. London. ``Notes on the design of Euclid.'' SIGPLAN Notices, volume 12, number 3, March 1977, pages 11-18.

161

Pournelle, Jerry. ``Computing at Chaos Manor: Come to the Faire.'' BYTE, volume 10, number 7, July 1985, pages 309-339.

In this monthly column Purnelle describes meeting Wirth and a celebrated pun attributed to him. Wirth's name is one that is confusing for English speakers to pronounce. When asked how to pronounce his name, he is said to have answered that if you call him by name, it is ``virt'' (the German pronunciation), and if you call him by value, it is ``worth'' (the American pronunciation).

162

Quine, Willard Van Orman. Word and Object. MIT Press, Cambridge, Massachusetts, 1960.

Section 30 is on ``referential opacity.''

163

Rentsch, Tim. ``Object oriented programming.'' SIGPLAN Notices, volume 17, number 9, September 1982, pages 51-57.

164

Richard, Frederic, and Henry F. Ledgard. ``A reminder for language designers.'' SIGPLAN Notices, volume 12, number 12, December 1977, pages 73-82.

165

Robinson, John Alan. ``A machine-oriented logic based on the resolution principle.'' Journal of the ACM, volume 12, number 1, January 1965, pages 34-41.

166

Robinson, John Alan. Logic, Form and Function: The Mechanization of Deductive Reasoning. North-Holland, New York, 1979.

167

Robinson, John Alan. ``Logic programming--past, present, and future.'' New Generation Computing, volume 1, 1983, pages 107-124.

168

Rosen, Barry K. ``Tree manipulation systems and Church-Rosser theorems.'' Journal of the ACM, volume 20, number 1, January 1973, pages 160-187.

169

Schmandt-Besserat, Denise. ``The earliest precursor of writing.'' In Language, Writing, and the Computer, W. H. Freeman, New York, 1986, pages 31-40.

170

Schmidt, David A. Denotational Semantics. Allyn and Bacon, Boston, Massachusetts, 1986.

171

Schönfinkel, Moses. ``On the building blocks of mathematical logic.'' In From Frege to Gödel, edited by Jean van Heijenoort, Harvard University Press, Cambridge, Massachusetts, 1977.

This article was originally published in 1924. In it logic is reduced to a small set of primitive notions including the combinators K ( Konstanzfunktion) and S (Verschmelzungsfunktion). Schönfinkel also introduces the device now know as ``Currying.''

172

Schwartz, Jacob T., Robert B. K. Dewar, Ed Dubinsky, and E. Schonberg. Programming with Sets: An Introduction to SETL. Texts and monographs in computer science. Springer-Verlag, 1986.

173

Scott, Dana S. ``Outline of a mathematical theory of computation.'' In Proceedings of the 4th Annual Princeton Conference on Information Sciences & Systems, Princeton, 1970, pages 169-176.

174

Scott, Dana S. ``Lattice theory, data types and formal semantics.'' In Formal semantics of programming languages, edited by Randall Rustin, Prentice Hall, Englewood Cliffs, New Jersey, 1972, pages 65-106.

175

Scott, Dana S. ``Logic and programming languages.'' Communications of the ACM, volume 20, number 9, September 1977, pages 634-641.

176

Shu, Nan C. Visual Programming. Van Nostrand Reinhold, New York, 1988.

177

Slater, Robert. Portraits in Silicon. MIT Press, Cambridge, Massachusetts, 1987.

Biographies of Charles Babbage (1791-1871), Alan Turing, John von Neumann, Claude Shannon, Konrad Zuse, John V. Atanasoff, John William Mauchly and J. Presper Eckert, Howard Aiken, Jay W. Forrester, Thamas J. Watson, Sr., William Norris, H. Ross Perot, William Shockley, Robert Noyce, Jack Kilby, Marcian E. (Ted) Hoff, Gene Amdahl, Seymour R. Cray, Gordon Bell, Grace Murray Hopper, John Backus, John Kemeny and Thomas Kurtz, William Gates, Dennis Ritchie and Kenneth Thompson, Daniel Bricklin, Nolan Bushnell, Steven Jobs, Adam Osborne, William Nillard, and Donald Knuth.

178

Smullyan, Raymond M. To Mock a Mocking Bird and Other Logic Puzzles: Including an Amazing Adventure in Combinatory Logic. Knopf, New York, 1985.

179

Stansifer, Ryan. ML Primer. Prentice Hall, Englewood Cliffs, New Jersey, 1992.

An introduction to programming in the functional language ML.

180

Stenlund, Sören. Combinators, -terms, and Proof Theory. D. Reidel Publishing Company, Dordrecht, Holland, 1972.

181

Stoy, Joseph E. Denotational Semantics. MIT Press, Cambridge, Massachusetts, 1977.

182

Strachey, Christopher. ``Towards a formal semantics.'' In Formal description of languages for computer programming, edited by Thomas B. Steel, Jr., North-Holland, Amsterdam, 1966, pages 198-220.

This paper was presented at a conference organized by Technical Committee 2 of the International Federation for Information Processsing, and held in Vienna, September 1964. In it the terms l-value and r-value are used to distinguish the value of a programming language variable from its location.

183

Stroustrup, Bjarne. The C++ Programming Language. Addison-Wesley, Reading, Massachusetts, 1986.

184

Stroustrup, Bjarne. ``A history of C++: 1979-1991.'' SIGPLAN Notices, volume 28, number 3, March 1993, pages 271-297.

185

Stroustrup, Bjarne. The Design and Evolution of C++. Addison Wesley, Reading, Massachusetts, 1994.

Extensive commentary about the design, history, philosophy, and development of C++. The chapters are: The Prehistory of C++, C with Classes, The Birth of C++, C++ Language Design Rules, Chronology 1985-1993, Standardization, Interest and Use, Libraries, Looking Ahead, Memory Management, Overloading, Multiple Inheritance, Class Concept Refinements, casting, Templates, Exception handling, Namespaces, and The C Preprocessor.

186

Struik, Dirk Jan, editor. A Source Book in Mathematics, 1200-1800. Harvard University Press, Cambridge, Massachusetts, 1969.

187

Tanenbaum, Andrew S. ``A tutorial on ALGOL 68.'' Computing Surveys, volume 8, number 2, June 1976, pages 155-190. Reprinted in [95, pages 69-104].

An introduction to ALGOL 68 as defined in the revised report of 1975. While ALGOL 60 did not have input or output procedures, ALGOL 68 has a wide assortment of such routines, including ``readf'' and ``printf'' which are complex routines vaguely resembling those of the IO library for the C programming language.

188

Tarnlund, S. A. ``Horn clause computability.'' BIT, volume 17, 1977, pages 215-226.

189

Tennent, R. D. ``Another look at type compatibility in Pascal.'' Software--Practice and Experience, volume 8, 1978, pages 429-437.

190

Tennent, R. D. Principles of Programming Languages. Prentice Hall, Englewood Cliffs, New Jersey, 1981.

191

Thomas, Peter G., Hugh Robinson, and Judy Emms. Abstract Data Types. Oxford University Press, Oxford, England, 1988.

192

Turner, David A. ``A new implementation technique for applicative languages.'' Software--Practice and Experience, volume 9, number 1, 1979, pages 31-49.

This paper argues that translating functional languages to combinators is a practical way of implementing these languages.

193

United States Department of Defense. Reference Manual for the Ada Programming Language. United States Government Printing Office, Washington, D.C., 1983. A hypertext version is available at http://www.itl.saic.com/ada/ada_lrm.html.

194

van Heijenoort, Jan, editor. From Frege to Gödel: A Source Book in Mathematical Logic. Harvard University Press, Cambridge, Massachusetts, 1977.

195

Vuillemin, Jean. ``Correct and optimal implementations of recursion in a simple programming language.'' Journal of Computer and System Sciences, volume 9, number 3, December 1974, pages 332-354.

196

Wasserman, Anthony I., editor. Tutorial, Programming Language Design. IEEE Computer Society Press, Los Alamitos, California, 1980.

A collection of 39 significant papers concerning imperative programming languages.

197

Watt, David Anthony. ``Executable semantic descriptions.'' Software--Practice and Experience, volume 16, number 1, January 1986, pages 13-43.

198

Welsh, Jim, J. Sneeringer, and Charles Antony Richard Hoare. ``Ambiguities and insecurities in Pascal.'' Software--Practice and Experience, volume 7, number 6, 1977, pages 685-696. Reprinted in [196, pages 284-295].

199

Wexelblat, Richard L., editor. History of Programming Languages. ACM monograph series. Academic Press, New York, 1981.

Proceedings of the first SIGPLAN sponsored conference about the history of programming languages. It was held in 1978 and focused on 13 programming languages represented by invited speakers: FORTRAN, John Backus; ALGOL, Alan Perlis, Peter Naur; LISP, John McCarthy; COBOL, Jean Sammett; APT, Douglas Ross; JOVIAL, Jules Schwartz; GPSS, Geoffrey Gordon; SIMULA, Kristen Nygaard and Ole-Johan Dahl; JOSS, Charles Baker; BASIC, Thomas Kurtz; PL/I, George Radin; SNOBOL, Ralph Griswold; APL, Kenneth Iverson.

200

Williams, Michael Roy. A History of Computing Technology. Prentice Hall, Englewood Cliffs, New Jersey, 1985.

201

Winkler, J. F. H. ``Some improvements of ISO Pascal.'' SIGPLAN Notices, volume 19, number 9, September 1984, pages 49-62. Reprinted in [95, pages 123-153].

202

Winograd, Terry A. ``Computer software for working with language.'' In Language, Writing, and the Computer, W. H. Freeman, New York, 1986, pages 61-72.

203

Wirth, Niklaus Emil. ``Program development by stepwise refinement.'' Communications of the ACM, volume 14, number 4, April 1971, pages 221-227.

The method of stepwise refinement is used to solve the eight-Queens problem in chess. This method involves refining the program structure in ever increasing detail until the steps of the algorithm can be implemented directly in the programming language.

204

Wirth, Niklaus Emil. ``The programming language Pascal.'' Acta Informatica, volume 1, number 1, 1971, pages 35-63.

The first implementation of Pascal was written by a single graduate student in FORTRAN in 1969. The second compiler was to be implemented in the language itself using a single-pass system based on recursive-descent parsing. This version of the Pascal language, now containing recursion, appeared as a technical report in 1970 and soon afterward as this paper in Acta Informatica.

205

Wirth, Niklaus Emil. ``On the design of programming languages.'' In Information processing 74, edited by Jack L. Rosenfeld, North-Holland, Amsterdam, 1974, pages 386-393.

206

Wirth, Niklaus Emil. ``An assessment of the programming language Pascal.'' IEEE Transactions on Software Engineering, volume SE-1, number 2, June 1975, pages 192-198. Reprinted in [95, pages 117-122].

207

Wirth, Niklaus Emil. ``From Modula to Oberon.'' Software--Practice and Experience, volume 18, number 7, 1988, pages 661-670.

208

Wirth, Niklaus Emil. ``Recollections about the development of Pascal.'' SIGPLAN Notices, volume 28, number 3, March 1993, pages 333-342.

This is one of papers presented at the History of Programming Languages conference. Wirth explains Pascal's genesis as a successor to ALGOL W.

209

Wirth, Niklaus Emil, and Charles Antony Richard Hoare. ``A contribution to the development of ALGOL.'' Communications of the ACM, volume 9, number 6, June 1966, pages 413-432.

This two-part paper is an introduction and a definition to a programming language designed as a successor to ALGOL 60 and as an alternative to the emerging ALGOL 68 language. It came to be known as ALGOL W and was implemented on the IBM 360 at Stanford University. ALGOL W included types for records and pointers and a case statement.

210

Zemanek, Heinz. ``Al-Khorezmi: His background, his personality, his work and his influence.'' In Algorithms in Modern Mathematics and Computer Science, edited by Andrei Petrovitch Ershov and Donald Ervin Knuth, Springer-Verlag, Berlin, 1981, pages 8-81.