Skip to main content
main-content
Top

About this book

This book uses a functional programming language (F#) as a metalanguage 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, garbage collection, and real machine code. Also included are 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.

This second edition includes two new chapters. One describes compilation and type checking of a full functional language, tying together the previous chapters. The other describes how to compile a C subset to real (x86) hardware, as a smooth extension of the previously presented compilers.The examples present several interpreters and compilers for toy languages, including compilers for a small but usable subset of C, abstract machines, a garbage collector, and ML-style polymorphic type inference. Each chapter has exercises.

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

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.
Peter Sestoft

Chapter 3. From Concrete Syntax to Abstract Syntax

Abstract
Until now, we have written programs in abstract syntax, which is convenient when handling programs as data.
Peter Sestoft

Chapter 4. A First-Order Functional Language

Abstract
This chapter presents a functional language micro-ML, a small subset of ML or F#.
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 6. Polymorphic Types

Abstract
This chapter discusses polymorphic types and type inference in F# and other ML-family languages, as well parametric polymorphism in Java and C#, often called generic types and methods.
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.
Peter Sestoft

Chapter 9. Real-World Abstract Machines

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

Chapter 10. Garbage Collection

Abstract
Heap-allocation and garbage collection are not specific to abstract machines, but has finally become accepted in the mainstream thanks to the Java Virtual Machine and the Common Language Infrastructure/.NET.
Peter Sestoft

Chapter 11. Continuations

Abstract
This chapter introduces the concept of continuation.
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.
Peter Sestoft

Chapter 13. Compiling Micro-SML

By Niels Hallenberg
Abstract
In Chaps. 4 and 5 we presented a small functional language, micro-ML, and implemented an interpreter for its dynamic semantics as defined in Fig. 4.​3. The static semantics for the first-order language was defined in Fig. 4.​7 and the higher-order static semantics in Fig. 6.​1. Based on this a type checker and a type inference algorithm were implemented in Sect. 6.​4. Here we round out the topic of functional languages by presenting an extended version of micro-ML called micro-SML.
Peter Sestoft

Chapter 14. Real Machine Code

Abstract
In Chap. 8 we presented a compiler from micro-C to code for an abstract stack machine. In this chapter we describe real machine code in the form of assembly code for the x86 architecture, and show how to compile micro-C programs to such code. Executing micro-C programs translated into real machine code will be much faster, both because it avoids the interpretive overhead incurred by the abstract machine, and because it uses machine registers instead of the stack for expression evaluation.
Peter Sestoft
Additional information