Название: Programming Languages: Build, Prove, and Compare
Автор: Norman Ramsey
Издательство: Cambridge University Press
Год: 2023
Страниц: 800
Язык: английский
Формат: pdf (true)
Размер: 10.1 MB

Computer scientists often need to learn new programming languages quickly. The best way to prepare for this is to understand the foundational principles that underlie even the most complicated industrial languages.

This text for an undergraduate programming languages course distills great languages and their design principles down to easy-to-learn 'bridge' languages implemented by interpreters whose key parts are explained in the text. The book goes deep into the roots of both functional and object-oriented programming, and it shows how types and modules, including generics/polymorphism, contribute to effective programming.

The book is not just about programming languages; it is also about programming. Through concepts, examples, and more than 300 practice exercises that exploit the interpreter, students learn not only what programming-language features are but also how to do things with them. Substantial implementation projects include Milner's type inference, both copying and mark-and-sweep garbage collection, and arithmetic on arbitrary-precision integers.

The ideas, descriptive techniques, and examples are conveyed by means of bridge languages. A bridge language models a real programming language, but it is small enough to describe formally and to learn in a week or two, yet big enough to write interesting programs in. The bridge languages in this book model Algol, Scheme, ML, CLU, and Smalltalk, and they are related to many modern descendants, including C, C++, OCaml, Haskell, Java, jаvascript, Python, Ruby, and Rust.

Each bridge language is supported by an interpreter, which runs all the examples and supports programming exercises. The interpreters, which are presented in depth in an online Supplement, are carefully crafted and documented. They can be used not only for exercises but also to implement students’ own language‐design ideas.

The book develops these concepts:
• Abstract syntax and operational semantics
• Definitional interpreters
• Algebraic laws and equational reasoning
• Garbage collection
• Symbolic computing and functional programming
• Parametric polymorphism
• Monomorphic and polymorphic type systems
• Type inference
• Algebraic data types and pattern matching
• Data abstraction using abstract types and modules
• Data abstraction using objects and classes

The book calls for skills in both programming and proof:
• As prerequisites, learners should have the first‐year, two‐semester programming sequence, including data structures, plus discrete mathematics.
• To extend and modify the implementations in Chapters 1 to 4, a learner needs to be able to read and modify C code; the necessary skills have to be learned elsewhere. C is used because it is the simplest way to express programs that work extensively with pointers and memory, which is the topic of Chapter 4.
• To extend and modify the implementations in Chapters 5 to 10, a learner needs to be able to read and modify Standard ML code; the necessary skills are developed in Chapters 2, 5, and 8. Standard ML is used because it is a simple, powerful language that is ideally suited to writing interpreters.
• To prove the simpler theorems, a learner needs to be able to substitute equals for equals and to fill in templates of logical reasoning. To prove the more interesting theorems, a learner needs to be able to write a proof by induction.

Programming Languages: Build, Prove, and Compare gives you interesting, powerful programming languages that share a common syntax, a common theoretical framework, and a common implementation framework. These frameworks support programming practice in the bridge languages, implementation and extension of the bridge languages, and formal reasoning about the bridge languages. The design of your course will depend on how you wish to balance these elements.