Skip to main content
main-content
Top

About this book

Programming Language Concepts uses a functional programming language (F#) as the metalanguage in which to present all concepts and examples, and thus has an operational flavour, enabling practical experiments and exercises. It includes basic concepts such as abstract syntax, interpretation, stack machines, compilation, type checking, and garbage collection techniques, as well as the more advanced topics on polymorphic types, type inference using unification, co- and contravariant types, continuations, and backwards code generation with on-the-fly peephole optimization.

Programming Language Concepts covers practical construction of lexers and parsers, but not regular expressions, automata and grammars, which are well covered elsewhere. It throws light on the design and technology of Java and C# to strengthen students’ understanding of these widely used languages.

The examples present several interpreters and compilers for toy languages, including a compiler for a small but usable subset of C, several abstract machines, a garbage collector, and ML-style polymorphic type inference. Each chapter has exercises based on such examples.

Table of Contents

Chapter 1. Introduction

Abstract
This chapter introduces the approach taken and the plan followed in this book. We show how to represent arithmetic expressions and other program fragments as data structures in F# as well as Java, and how to compute with such program fragments. We also introduce various basic concepts of programming languages.
Peter Sestoft

Chapter 2. Interpreters and Compilers

Abstract
This chapter introduces the distinction between interpreters and compilers, and demonstrates some concepts of compilation, using the simple expression language as an example. Some concepts of interpretation are illustrated also, using a stack machine as an example.
Peter Sestoft

Chapter 5. Higher-Order Functions

Abstract
A higher-order functional language is one in which a function may be used as a value, just like an integer or a boolean. That is, the value of a variable may be a function, and a function may take a function as argument and may return a function as a result.
Peter Sestoft

Chapter 7. Imperative Languages

Abstract
This chapter discusses imperative programming languages, in which the value of a variable may be modified by assignment. We first present a naive imperative language where a variable denotes an updatable store cell, and then present the environment/store model used in real imperative programming languages. Then we show how to evaluate micro-C, a C-style imperative language, using an interpreter, and present the concepts of expression, variable declaration, assignment, loop, output, variable scope, lvalue and rvalue, parameter passing mechanisms, pointer, array, and pointer arithmetics.
Peter Sestoft

Chapter 8. Compiling Micro-C

Abstract
In Chap. 2 we considered a simple stack-based abstract machine for the evaluation of expressions with variables and variable bindings. Here we continue that work, and extend the abstract machine so that it can execute programs compiled from an imperative language (micro-C). We also write a compiler from the imperative programming language micro-C to this abstract machine.
Peter Sestoft

Chapter 9. Real-World Abstract Machines

Abstract
This chapter discusses some widely used real-world abstract machines.
Peter Sestoft

Chapter 11. Continuations

Abstract
This chapter introduces the concept of continuation, which helps understand such notions as tail call, exceptions and exception handling, execution stack, and backtracking.
Peter Sestoft

Chapter 12. A Locally Optimizing Compiler

Abstract
In this chapter we shall see that thinking in continuations is beneficial also when compiling micro-C to stack machine code. Generating stack machine code backwards may seem silly, but it enables the compiler to inspect the code that will consume the result of the code being generated. This permits the compiler to perform many optimizations (code improvement) easily.
Peter Sestoft
Additional information