This is the main text for the course. It is a revision (in progress) of Sam Kamin's 1990 textbook. Kamin did an excellent job of cramming a lot of good ideas into a few chapters. To make it possible, he extracted the essence of many different programming languages, and he has expressed those essences in a uniform, LISP-like syntax. Ramsey has updated the text with material on abstract syntax and operational semantics, and he has modernized the software associated with the book. Source code and examples from the book are available in a git repository at linux.cs.tufts.edu:/comp/105/book-code.Because the book is a work in progress, it is not available at the bookstore. Instead, you will need to buy a copy from the instructor. The cost, which covers only the cost of reproduction, is $35.
The best introduction to Standard ML for C programmers.
David Schmidt,
Denotational
Semantics: A Methodology for Language Development, Allyn and
Bacon, 1986.
It's hard to find good books on denotational semantics.
The advantage of this book is that a free PDF is available on Creative
Commons license.
I haven't used it before, but
I hope it will prove useful.
Supplemental Readings
Particular Languages
C
The best language manual ever written? You be the judge. In any case, if you own only one book on C, this should be it.
If you want a ``reference,'' this is it.
A quirky, lighthearted explanation of some of C's dark corners. Although it is a bit biased toward explaining ANSI C (which is now old hat), it's an excellent book for a C programmer with medium experience to deepen his or her understanding of how to write good C programs. If you only own two books on C, this is a good one.
A good overview of the ML language. Lecture 2 has many nice examples of use of the modules system, and lecture 3 is the best explanation I have seen of the static semantics of modules (signature matching and constraints).
Actually ``extended quick-reference card'' is a better description. Runs about 20 pages. Highly recommended to have with you when hacking. .
This tutorial is highly recommended by a trusted colleague.
The classic book on Prolog. Easy to read and digestible.
I haven't read this, but it may be useful.
An excellent short-short introduction to formal methods for imperative programs, as applied by practicing programmers.
This book presents Liskov's and Guttag's work on data abstraction and algebraic specification, which drove the design of CLU, and which later influenced Ada, Modula-3, and other languages. It is, regrettably, out of print, but I'll try to get it on reserve.
A fine, if long-winded, presentation of basic formal methods for imperative programs, especially programming with loops and arrays. Very heavy on the formalism. Includes substantial introductory material on the propositional calculus. Chapters 13--18 are probably most relevant for the basics of developing correct imperative programs.
Although the notation is cumbersome and the material is now more than 20 years old, Knuth's is a remarkable summary of the problems of dynamic memory allocation and garbage collection. This material is still relevant today. Today's survey would cover much the same topics, but would also discuss more recent work in copying and conservative collection.
Not comprehensive, but very lucid on the topics covered.
A good, simple introduction to generational collection.
A good, simple introduction to conservative collection. The collector and some related papers are available.
Describes tools and techniques for improving the memory performance of functional programs.
This is a concise, accessible treatement of the topic by one of the world's experts.
A thorough and clear treatment of semantics for the undergraduate. Good source for operational semantics.
If you don't have the Allison text, these brief notes provide a readable introduction to the basics of the lambda-calculus.
The classic paper in the proofs of abstract types.
Good survey of axiomatic semantics.
A mathematically precise characterization of ``abstract syntax.''
Some remarks on programming-language design from a master. These are rendered more often as ``how not to'' than ``how to.''
The famous ``little book.''
Nice short paper on writing. Especially good on word order.
An excellent book focusing on algorithms for writing good prose and improving existing prose. Also explains how when and why to use such deprecated constructs as passive voice.
A classic. If you own one book on writing, this should be it.
A discussion of literate programming with noweb.
The classic guide to Unix hacking.
This classic guide shows good programming style by example --- often by bad example! If the instructor or grader has cited you for poor programming style, you should read this book.
A nice paper on a string package for C. Good job covering the reasons we want strings to be immutable.
An entertaining account of a simple mechanical learning engine
Describes the tcl language, a bit about how users use it, and a bit about how applications embed it. The important part is at the end where he proposes remote evaluation with tcl as a way of making different tools interact. There's probably a copy online in the tcl sources.
This paper is a nice, lucid explanation of the continuation-passing style, which may be covered in class.