Principles of Programming Languages Version 1.0

1 Principles of Programming GrantZachary PalmerScott 2002-2020 Scott F. work is licensed under the Creative Commons Attribution-Share Alike UnitedStates License. To view a copy of this license, send a letter to CreativeCommons, 171 Second Street, Suite 300, San Francisco, California, 94105, document was last compiled on April 22, Introduction12 Operational A First Look at Operational Semantics .. BNF grammars and Syntax .. Semantics for Logic Expressions .. Syntax .. Semantics and Interpreters .. TheF[ Programming language .. [Syntax .. Substitution .. Semantics forF[.. Expressiveness ofF[.. s Paradox and Encoding Recursion .. Parameter Passing .. [Abstract Syntax .. Operational Equivalence .. Operational Equivalence .. of Operational Equivalence.]]]]]

2 Of Operational Equivalence .. -Calculus .. 483 Tuples, Records, and Tuples .. Records .. Polymorphism .. [RLanguage .. Variants .. Polymorphism .. [VLanguage .. 544 Side Effects: State and State .. [SLanguage .. Stores .. Normal Kind of State .. Garbage Collection .. Environment-Based Interpreters .. TheF[SRLanguage .. and Factorial .. Sort .. Exceptions and Other Control Operations .. Return .. [XLanguage .. theF[XInterpreter .. 765 Object-Oriented language Encoding Objects inF[SR.. Objects .. Polymorphism .. Hiding .. Dispatch .. Fields and Methods .. TheF[OBLanguage .. Syntax .. Direct Interpreter .. [OBtoF[SR.. 956 Type An Overview of Types.]]]]]]]]]]

3 [: A TypedF[Variation .. Issues .. [ language .. Type Checking .. Types for an Advanced language :TF[SRX.. Subtyping .. [RType System:TF[with Records and Subtyping .. anSTF[RType Checker .. in Other Languages .. Type Inference and Polymorphism .. Inference and Polymorphism .. Equational Type System:EF[.. [:EF[withLetPolymorphism .. Constrained Type Inference .. 1237 Overview .. Java Concurrency Model .. The Actor Model andAF[V.. ofAF[V.. Example .. Semantics of Actors .. Local Rules .. Global Rule .. Atomicity of Actors .. 1328 Compilation by Program Closure Conversion .. Official Closure Conversion .. A-Translation .. Official A-Translation .. Function Hoisting .. Translation to C .. Layout.]]]]]]]]]]]]

4 ToC translation .. to Assembly code .. Summary .. Optimization .. Garbage Collection .. 154 Bibliography155 Index157 chapter 1 IntroductionIn this book, our goal is to study the fundamental concepts in Programming Languages ,as opposed to learning a range of specific Languages . Languages are easy to learn, itis the concepts behind them that are difficult. The basic features we study in turn in-clude higher-order functions, data structures in the form of records and variants, mutablestate, exceptions, objects and classes, and types. We also study language implementa-tions, both through language interpreters and language compilers. Throughout the bookwe write small interpreters for toy Languages , and in chapter 8 we write a principledcompiler. We define type checkers to define which programs are well-typed and whichare not.

5 We also take a more precise, mathematical view of interpreters and type check-ers, via the concepts ofoperational semanticsandtype systems. These last two conceptshave historically evolved from the logician s view of material has evolved from lecture notes used in a Programming Languages coursefor juniors, seniors, and graduate students at Johns Hopkins University [21].While the book uses formal mathematical techniques such as operational semanticsand type systems, it does not emphasize proofs of properties of these systems. We willnonetheless sketch the intuitions of some OCaml LanguageThe OCaml Programming language [15] is used throughout the book, and assignmentsrelated to the book should be written in OCaml. OCaml is a modern dialect of MLwhich has the advantages of being reliable, fast, free, and available on just about anyplatform FbDKComplementing the book is theF[Development Kit, FbDK.]

6 It is a set of OCaml utilitiesand interpreters for designing and experimenting with the toyF[andF[SRlanguagesdefined in the book. It is available from the book homepage 1. INTRODUCTION2 Background NeededThe book assumes familiarity with the basics of OCaml, including the module system(but not the objects, the O in OCaml). Beyond that there is no absolute prerequisite,but knowledge of C, C++, and Java is helpful because many of the topics in this book areimplemented in these Languages . The compiler presented in chapter 8 produces C codeas its target, and so a basic knowledge of C will be needed to implement the nebulously, a certain mathematical maturity greatly helps in understanding theconcepts, some of which are deep. for this reason, previous study of mathematics, for-mal logic and other foundational topics in Computer Science such as automata theory,grammars, and algorithms will be a great , make sure your seat belts are buckled, sit back, relax, and enjoy the ride.]]

7 chapter 2 Operational A First Look at Operational SemanticsThesyntaxof a Programming language is the set of rules governing the formation ofexpressions in the language . Thesemanticsof a Programming language is themeaningof those are several forms of language semantics. Axiomatic semantics is a set of ax-iomatic truths in a Programming language . Denotational semantics involves modelingprograms as static mathematical objects, namely as set-theoretic functions with specificproperties. We, however, will focus on a form of semantics called operational operational semantics is a mathematical model of Programming languageexecu-tion. It is, in essence, an interpreter defined mathematically. However, an operationalsemantics is more precise than an interpreter because it is defined mathematically, andnot based on the meaning of the Programming language in which the interpreter is writ-ten.

8 This might sound sound like a pedantic distinction, but interpreters interpret alanguage sifstatements with theifstatement of the language the interpreter is writtenin. This is in some sense a circular definition ofif. Formally, we can define operationalsemantics as (Operational Semantics).Anoperational semanticsfor a program-ming language is a mathematical definition of its computation relation,e v, whereeis a program in the vis mathematically a 2-place relation between expressions of the language ,e, andvalues of the language ,v. Integers and booleans are values. Functions are also valuesbecause they don t compute to , meaning theydenote an arbitrary expression or value, and should not be confused with the (regular)variables that are part of operational semantics for a Programming language is a means for understanding inprecise detail the meaning of an expression in the language .

9 It is the formal specificationof the language that is used when writing compilers and interpreters, and it allows us torigorously verify things about the 2. OPERATIONAL BNF grammars and SyntaxBefore getting into meaning we need to take a step back and first precisely define languagesyntax. This is done with formal Form(BNF) is a standardgrammar formalism for defining language syntax. You could well be familiar with BNFsince it is often taught in introductory courses, but if not we provide a brief BNF grammars compriseterminals,nonterminals (aka syntactic categories), andproduction rules. Terminals are traditionally identified using lower-case letters; non-terminals are identified using upper-case letters. Production rules describe how non-terminals are defined. The general form of production rules is: nonterminal ::= form 1 | | form n where each form above describes a particular language form that is, a string ofterminals and non-terminals.

10 Atermin the language is a string of terminals whichmatches the description of one of these rules (traditionally the first).For example, consider the language Sheep. Let{S}be the set of nonterminals,{a,b}be the set of terminals, and the grammar definition be:S::=b|SaNote that this is a recursive definition. Examples of terms in Sheep areb,ba,baa,baaa,baaaa,..That is, any string starting with the characterband followed by zero or moreacharactersis a term in Sheep. The following are examples that are not terms in SHEEP: a: Terms in Sheep must start with ab. bbaaa: Sheep does not allow multiplebcharacters in a term. baah:his not a terminal in Sheep. Saaa:Sis a non-terminal in Sheep. Terms may not contain way of expressing a grammar is by the use of asyntax diagram. Syntaxdiagrams describe the grammar visually rather than in a textual form.