PFPL 1

Preface

Types are the central organizing principle of the theory of programming languages. Language fea- tures are manifestations of type structure. The syntax of a language is governed by the constructs that define its types, and its semantics is determined by the interactions among those constructs. The soundness of a language design—the absence of ill-defined programs—follows naturally.

• A-priori thoughts? Is that true? Are there alternate, valid views of the universe?

Chapter 1

Programming languages are languages, a means of expressing computations in a form compre- hensible to both people and machines.

• Slightly weaker echo of the Abelson quote.

We will not concern ourselves in this book with concrete syntax, but will instead consider pieces of syntax to be finite trees augmented with a means of expressing the binding and scope of identifiers within a syntax tree.

1.1 Abstract Syntax Trees

An abstract syntax tree, or ast for short, is an ordered tree whose leaves are variables, and whose interior nodes are operators whose arguments are its children. Ast’s are classified into a variety of sorts corresponding to different forms of syntax.

• Why "sort"? As opposed to, say, "type". Does it imply an ordering?

Answer in paragraph 3:

Abstract syntax trees are classified by sorts that divide ast’s into syntactic categories. For exam- ple, familiar programming languages often have a syntactic distinction between expressions and commands; these are two sorts of abstract syntax trees.