Undergraduate Topics in Computer Science Peter Sestoft Programming Language Concepts Second Edition Undergraduate Topics in Computer Science Series editor Ian Mackie Advisory Board SamsonAbramsky, University ofOxford, Oxford,UK KarinBreitman, PontificalCatholic University of RiodeJaneiro,RiodeJaneiro, Brazil Chris Hankin,Imperial CollegeLondon,London,UK Dexter C.Kozen, Cornell University, Ithaca,USA AndrewPitts, University ofCambridge, Cambridge, UK Hanne Riis Nielson,Technical University of Denmark,Kongens Lyngby,Denmark StevenS. Skiena, StonyBrookUniversity, StonyBrook, USA Iain Stewart, University of Durham, Durham, UK UndergraduateTopics inComputerScience (UTiCS) delivers high-qualityinstruc- tionalcontentforundergraduatesstudyinginallareasofcomputingandinformation science. From core foundational and theoretical material to final-year topics and applications,UTiCSbookstakeafresh,concise,andmodernapproachandareideal for self-study or for a one- or two-semester course. The texts are all authored by establishedexpertsintheirfields,reviewedbyaninternationaladvisoryboard,and containnumerousexamplesandproblems.Manyincludefullyworkedsolutions. More information about this series at http://www.springer.com/series/7592 Peter Sestoft Programming Language Concepts Second Edition With a chapter by Niels Hallenberg 123 PeterSestoft ITUniversity ofCopenhagen, Computer ScienceDepartment Copenhagen Denmark ISSN 1863-7310 ISSN 2197-1781 (electronic) Undergraduate Topics inComputer Science ISBN978-3-319-60788-7 ISBN978-3-319-60789-4 (eBook) DOI 10.1007/978-3-319-60789-4 LibraryofCongressControlNumber:2017949164 1stedition:©Springer-VerlagLondon2012 2ndedition:©SpringerInternationalPublishingAG2017 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpart of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission orinformationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodologynowknownorhereafterdeveloped. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfrom therelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authorsortheeditorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinor for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictionalclaimsinpublishedmapsandinstitutionalaffiliations. Printedonacid-freepaper ThisSpringerimprintispublishedbySpringerNature TheregisteredcompanyisSpringerInternationalPublishingAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Preface This book takes an operational approach to programming language concepts, studying those concepts in interpreters and compilers for some toy languages, and pointing out their relations to real-world programming languages. What is Covered Topics covered include abstract and concrete syntax; functional and imperative programming languages; interpretation, type checking, and compilation; peep-hole optimizations; abstract machines, automatic memory management and garbage collection; the Java Virtual Machine and Microsoft’s .NET Common Language Runtime; and real machine code for the x86 architecture. Someeffortismadethroughouttoputprogramminglanguageconceptsintotheir historical context, and to show how the concepts surface in languages that the students are assumed to know already; primarily Java or C#. Wedonotcoverregularexpressionsandparserconstructioninmuchdetail.For thispurpose,werefertoTorbenMogensen’stextbook;seeChap.3anditsreferences. Apart from various updates, this second edition adds a synthesis chapter, con- tributed by Niels Hallenberg, that presents a compiler from a small functional language called micro-SML to an abstract machine; and a chapter that presents a compiler from a C subset called micro-C to real x86 machine code. Why Virtual Machines? Thebook’semphasisisonvirtualstackmachinesandtheirintermediatelanguages, often known as bytecode. Virtual machines are machine-like enough to make the centralpurposeandconceptsofcompilationandcodegenerationclear,yettheyare much simpler than present-day microprocessors such as Intel i7 and similar. v vi Preface Full understanding of performance issues in real microprocessors, with deep pipelines, register renaming, out-of-order execution, branch prediction, translation lookaside buffers and so on, requires a very detailed study of their architecture, usually not conveyed by compiler textbooks anyway. Certainly, a mere under- standing of the instruction set, such as x86, conveys little information about whether code will be fast or not. The widely used object-oriented languages Java and C# are rather far removed from the real hardware, and are most conveniently explained in terms of their virtual machines: the Java Virtual Machine and Microsoft’s Common Language Infrastructure. Understanding the workings and implementation of these virtual machinesshedslightonefficiencyissues,designdecisions,andinherentlimitations in Java and C#. To understand memory organization of classic imperative lan- guages, we also study a small subset of C with arrays, pointer arithmetics, and recursive functions. We present a compiler from micro-C to an abstract machine, and this smoothly leads to a simple compiler for real x86 hardware. Why F#? WeusethefunctionallanguageF#aspresentationlanguagethroughout,toillustrate programming language concepts, by implementing interpreters and compilers for toy languages. The idea behind this is twofold. First, F# belongs to the ML family of languages and is ideal for implementing interpreters and compilers because it has datatypes and pattern matching and is strongly typed. This leads to a brevity and clarity of examples that cannot be matched by languages without these features. Secondly, the active use of a functional language is an attempt to add a new dimension to students’ world view, to broaden their imagination. The prevalent single-inheritance class-based object-oriented programming languages (namely, Java and C#) are very useful and versatile languages. But they have come to dominate computer science education to a degree where students may become unabletoimagineotherprogrammingtools,especiallytouseacompletelydifferent paradigm. Knowledge of a functional language will make the student a better designerandprogrammer,whetherinJava,C#orC,andwillpreparehimorherto adapt to the programming languages of the future. Forinstance,theso-calledgenerictypesandmethodsappearedinJavaandC#in 2004, but have been part of other languages, most notably ML, since 1978. Similarly, garbage collection has been used in functional languages since Lisp in 1960, but entered mainstream use more than 30 years later, with Java. Finally, functional programming features were added to C# in 2010 and to Java in 2014. Appendix A gives a brief introduction to those parts of F# used in this book. Studentswhodo notknowF#shouldlearn those partsduringthefirst-thirdofthis course,usingtheappendixoratextbooksuchasHansenandRischelorareference such as Syme et al.; see Appendix A and its references. Preface vii Supporting Material There are practical exercises at the end of each chapter. Moreover, the book is accompaniedbycompleteimplementationsinF#oflexerandparserspecifications, abstract syntaxes, interpreters, compilers, and runtime systems (abstract machines, inJavaandC)forarangeoftoylanguages.Thismaterial,andlectureslidesinPDF, are available separately from the book’s homepage: http://www.itu.dk/people/ sestoft/plc/. Acknowledgements This book originated as lecture notes for courses held at the IT University of Copenhagen,Denmark.IwouldliketothankAndrzejWasowski,KenFriisLarsen, Hannes Mehnert, David Raymond Christiansen and past students, in particular NielsKokholm,MikkelBundgaard,andAhmadSalim Al-Sibahi,whopointedout mistakesandmadesuggestionsonexamplesandpresentationinearlierdrafts.Niels Kokholmwroteanearlyversionofthemachinecodegeneratingmicro-Ccompiler presented in Chap. 14. Thanks to Luca Boasso, Mikkel Riise Lund, and Paul Jurczakforpointingoutmisprintsandunclaritiesinthefirstedition.Iowealasting debt to Neil D. Jones and Mads Tofte who influenced my own view of program- ming languages and the presentation of programming language concepts. NielsHallenbergdeservesaspecialthanksforcontributingallofChap.13tothis second edition. Copenhagen, Denmark Peter Sestoft Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Files for This Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Meta Language and Object Language. . . . . . . . . . . . . . . . . . . 1 1.3 A Simple Language of Expressions . . . . . . . . . . . . . . . . . . . . 2 1.3.1 Expressions Without Variables . . . . . . . . . . . . . . . . . 2 1.3.2 Expressions with Variables . . . . . . . . . . . . . . . . . . . . 3 1.4 Syntax and Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.5 Representing Expressions by Objects . . . . . . . . . . . . . . . . . . . 6 1.6 The History of Programming Languages. . . . . . . . . . . . . . . . . 8 1.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2 Interpreters and Compilers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1 Files for This Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Interpreters and Compilers. . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 Scope and Bound and Free Variables. . . . . . . . . . . . . . . . . . . 14 2.3.1 Expressions with Let-Bindings and Static Scope. . . . . 15 2.3.2 Closed Expressions. . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3.3 The Set of Free Variables . . . . . . . . . . . . . . . . . . . . . 17 2.3.4 Substitution: Replacing Variables by Expressions. . . . 17 2.4 Integer Addresses Instead of Names. . . . . . . . . . . . . . . . . . . . 20 2.5 Stack Machines for Expression Evaluation . . . . . . . . . . . . . . . 22 2.6 Postscript, a Stack-Based Language . . . . . . . . . . . . . . . . . . . . 23 2.7 Compiling Expressions to Stack Machine Code . . . . . . . . . . . 25 2.8 Implementing an Abstract Machine in Java. . . . . . . . . . . . . . . 26 2.9 History and Literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3 From Concrete Syntax to Abstract Syntax . . . . . . . . . . . . . . . . . . . 31 3.1 Preparatory Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2 Lexers, Parsers, and Generators . . . . . . . . . . . . . . . . . . . . . . . 32 ix x Contents 3.3 Regular Expressions in Lexer Specifications. . . . . . . . . . . . . . 33 3.4 Grammars in Parser Specifications . . . . . . . . . . . . . . . . . . . . . 34 3.5 Working with F# Modules. . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.6 Using fslex and fsyacc. . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.6.1 Installing and Using fslex and fsyacc . . . . . . . . . 37 3.6.2 Parser Specification for Expressions. . . . . . . . . . . . . . 37 3.6.3 Lexer Specification for Expressions . . . . . . . . . . . . . . 38 3.6.4 The ExprPar.fsyacc.output File Generated by fsyacc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.6.5 Exercising the Parser Automaton. . . . . . . . . . . . . . . . 44 3.6.6 Shift/Reduce Conflicts . . . . . . . . . . . . . . . . . . . . . . . 45 3.7 Lexer and Parser Specification Examples . . . . . . . . . . . . . . . . 47 3.7.1 A Small Functional Language . . . . . . . . . . . . . . . . . . 47 3.7.2 Lexer and Parser Specifications for Micro-SQL . . . . . 48 3.8 A Handwritten Recursive Descent Parser . . . . . . . . . . . . . . . . 48 3.9 JavaCC: Lexer-, Parser-, and Tree Generator . . . . . . . . . . . . . 50 3.10 History and Literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4 A First-Order Functional Language . . . . . . . . . . . . . . . . . . . . . . . . 59 4.1 Files for This Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2 Examples and Abstract Syntax. . . . . . . . . . . . . . . . . . . . . . . . 60 4.3 Run-Time Values: Integers and Closures . . . . . . . . . . . . . . . . 61 4.4 A Simple Environment Implementation . . . . . . . . . . . . . . . . . 62 4.5 Evaluating the Functional Language. . . . . . . . . . . . . . . . . . . . 62 4.6 Evaluation Rules for Micro-ML. . . . . . . . . . . . . . . . . . . . . . . 64 4.7 Static Scope and Dynamic Scope. . . . . . . . . . . . . . . . . . . . . . 66 4.8 Type-Checking an Explicitly Typed Language . . . . . . . . . . . . 68 4.9 Type Rules for Monomorphic Types . . . . . . . . . . . . . . . . . . . 70 4.10 Static Typing and Dynamic Typing . . . . . . . . . . . . . . . . . . . . 72 4.10.1 Dynamic Typing in Java and C# Array Assignment. . . . . . . . . . . . . . . . . . . . . 73 4.10.2 Dynamic Typing in Non-generic Collection Classes . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.11 History and Literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5 Higher-Order Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.1 Files for This Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.2 Higher-Order Functions in F# . . . . . . . . . . . . . . . . . . . . . . . . 81 5.3 Higher-Order Functions in the Mainstream . . . . . . . . . . . . . . . 82 5.3.1 Higher-Order Functions in Java 5 . . . . . . . . . . . . . . . 82 5.3.2 Higher-Order Functions in Java 8 . . . . . . . . . . . . . . . 84