Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2017 | Book

Introduction Read chapter Read first chapter

Programming Language Concepts

Author: Prof. Peter Sestoft

Publisher: Springer International Publishing

Book Series : Undergraduate Topics in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

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

Frontmatter
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
Backmatter
Metadata
Title
Programming Language Concepts
Author
Prof. Peter Sestoft
Copyright Year
2017
Electronic ISBN
978-3-319-60789-4
Print ISBN
978-3-319-60788-7
DOI
https://doi.org/10.1007/978-3-319-60789-4

Premium Partner

    Image Credits