Perugini Saverio / Perugini Saverio - Programming Languages: Concepts and Implementation / Programming Languages: Concepts and Implementation [2023, PDF, ENG] torrent

Книги и журналы » Компьютерная литература » Программирование (книги)

Programming Languages: Concepts and Implementation / Языки программирования: концепции и реализация

Год издания: 2023
Автор: Perugini Saverio / Перуджини Саверио

Издательство: Jones & Bartlett Learning
ISBN: 978-1-2842-2272-2
Язык: Английский

Формат: PDF
Качество: Издательский макет или текст (eBook)
Количество страниц: 889

Описание: Programming Languages: Concepts and Implementation is a textbook on the fundamental principles of programming languages through a combination of concept-based and interpreter-based approaches. The book has an implementation-oriented focus and features conceptual and programming exercises that give students practical experience applying language theory and concepts. The book also showcases the construction of a progressive series of language interpreters in Python that cover the implementation of a host of core language concepts such as scope, first-class functions, and parameter passing. Other programming styles, including logic/declarative programming, and compelling language features, such as first-class continuations, are also discussed. Concepts are presented in Python, Scheme, JavaScript, Ruby, ML, Haskell, Prolog, and various other programming languages. This book is intended as a general-purpose textbook for a course on programming languages. Each new print textbook includes Navigate eBook Access, a digital-only e-book with 365-day access.

Языки программирования: концепции и реализация - это учебное пособие по фундаментальным принципам языков программирования с использованием сочетания подходов, основанных на концепциях и интерпретаторах. Книга ориентирована на реализацию и содержит концептуальные упражнения и упражнения по программированию, которые дают студентам практический опыт применения теории языка и концепций. В книге также демонстрируется создание прогрессивной серии языковых интерпретаторов на Python, которые охватывают реализацию множества основных языковых концепций, таких как область видимости, первоклассные функции и передача параметров. Также обсуждаются другие стили программирования, включая логическое/декларативное программирование, и привлекательные языковые возможности, такие как первоклассные продолжения. Концепции представлены в Python, Scheme, JavaScript, Ruby, ML, Haskell, Prolog и различных других языках программирования. Эта книга задумана как учебное пособие общего назначения для курса по языкам программирования.
[spoiler="Примеры страниц"]

[/spoiler]
[spoiler="Оглавление"]
Preface xvii
About the Author xxix
List of Figures xxxi
List of Tables xxxv
Part I Fundamentals 1
1 Introduction 3
1.1 TextObjectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 ChapterObjectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 TheWorldofProgrammingLanguages . . . . . . . . . . . . . . . . . . 4
1.3.1 FundamentalQuestions . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.2 Bindings: Static andDynamic . . . . . . . . . . . . . . . . . . . 6
1.3.3 ProgrammingLanguageConcepts . . . . . . . . . . . . . . . . 7
1.4 StylesofProgramming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4.1 ImperativeProgramming . . . . . . . . . . . . . . . . . . . . . . 8
1.4.2 FunctionalProgramming . . . . . . . . . . . . . . . . . . . . . . 11
1.4.3 Object-OrientedProgramming . . . . . . . . . . . . . . . . . . 12
1.4.4 Logic/DeclarativeProgramming . . . . . . . . . . . . . . . . . 13
1.4.5 Bottom-upProgramming . . . . . . . . . . . . . . . . . . . . . . 15
1.4.6 Synthesis: Beyond Paradigms . . . . . . . . . . . . . . . . . . . 16
1.4.7 LanguageEvaluationCriteria . . . . . . . . . . . . . . . . . . . 19
1.4.8 ThoughtProcess forProblemSolving . . . . . . . . . . . . . . 20
1.5 Factors InfluencingLanguageDevelopment . . . . . . . . . . . . . . . 21
1.6 RecurringThemes inthe Study ofLanguages . . . . . . . . . . . . . . 25
1.7 WhatYouWillLearn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.8 LearningOutcomes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.9 ThematicTakeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.10 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.11 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2 Formal Languages and Grammars 33
2.1 ChapterObjectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2 Introductionto FormalLanguages . . . . . . . . . . . . . . . . . . . . . 34
2.3 Regular Expressions and Regular Languages . . . . . . . . . . . . . . . 35
2.3.1 Regular Expressions . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3.2 Finite-StateAutomata . . . . . . . . . . . . . . . . . . . . . . . . 38
2.3.3 RegularLanguages . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.4 Grammars andBackus–NaurForm . . . . . . . . . . . . . . . . . . . . . 40
2.4.1 RegularGrammars . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.5 Context-FreeLanguages andGrammars . . . . . . . . . . . . . . . . . . 42
2.6 LanguageGeneration: SentenceDerivations . . . . . . . . . . . . . . . 44
2.7 LanguageRecognition:Parsing . . . . . . . . . . . . . . . . . . . . . . . 47
2.8 SyntacticAmbiguity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.8.1 Modeling Some Semantics inSyntax . . . . . . . . . . . . . . . 49
2.8.2 ParseTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.9 GrammarDisambiguation . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.9.1 OperatorPrecedence. . . . . . . . . . . . . . . . . . . . . . . . . 57
2.9.2 Associativity ofOperators . . . . . . . . . . . . . . . . . . . . . 57
2.9.3 The Classical Dangling elseProblem. . . . . . . . . . . . . . 58
2.10 ExtendedBackus–NaurForm . . . . . . . . . . . . . . . . . . . . . . . . 60
2.11 Context-SensitivityandSemantics . . . . . . . . . . . . . . . . . . . . . 64
2.12 ThematicTakeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.13 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
2.14 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3 Scanning and Parsing 71
3.1 ChapterObjectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.2 Scanning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.3 Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.4 Recursive-DescentParsing . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.4.1 ACompleteRecursive-DescentParser . . . . . . . . . . . . . . 76
3.4.2 ALanguageGenerator . . . . . . . . . . . . . . . . . . . . . . . 79
3.5 Bottom-up,Shift-ReduceParsingandParserGenerators . . . . . . . 80
3.5.1 A Complete Example in lex and yacc . . . . . . . . . . . . . 82
3.6 PLY:PythonLex-Yacc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.6.1 ACompleteExample inPLY . . . . . . . . . . . . . . . . . . . . 84
3.6.2 Camille Scanner and Parser Generators in PLY . . . . . . . . 86
3.7 Top-downVis-à-VisBottom-upParsing . . . . . . . . . . . . . . . . . . 89
3.8 ThematicTakeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.9 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.10 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4 Programming Language Implementation 103
4.1 ChapterObjectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.2 InterpretationVis-à-VisCompilation . . . . . . . . . . . . . . . . . . . . 103
4.3 Run-Time Systems:Methods ofExecutions . . . . . . . . . . . . . . . . 109
4.4 Comparisonof InterpretersandCompilers . . . . . . . . . . . . . . . . 114
4.5 InfluenceofLanguageGoals onImplementation . . . . . . . . . . . . 116
4.6 ThematicTakeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.7 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
4.8 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5 Functional Programming in Scheme 125
5.1 ChapterObjectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.2 Introductionto FunctionalProgramming . . . . . . . . . . . . . . . . . 126
5.2.1 Hallmarks of FunctionalProgramming . . . . . . . . . . . . . 126
5.2.2 LambdaCalculus . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5.2.3 Lists inFunctionalProgramming . . . . . . . . . . . . . . . . . 127
5.3 Lisp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.3.2 Lists inLisp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.4 Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5.4.1 An Interactive and Illustrative Session with Scheme . . . . . 129
5.4.2 Homoiconicity: No Distinction Between
ProgramCode andData . . . . . . . . . . . . . . . . . . . . . . 133
5.5 cons Cells: Building Blocks of Dynamic Memory Structures . . . . . 135
5.5.1 ListRepresentation. . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.5.2 List-BoxDiagrams . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5.6 FunctionsonLists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
5.6.1 A List lengthFunction . . . . . . . . . . . . . . . . . . . . . . 141
5.6.2 Run-Time Complexity: append and reverse . . . . . . . . 141
5.6.3 TheDifferenceListsTechnique . . . . . . . . . . . . . . . . . . 144
5.7 ConstructingAdditionalData Structures . . . . . . . . . . . . . . . . . 149
5.7.1 ABinaryTreeAbstraction . . . . . . . . . . . . . . . . . . . . . 150
5.7.2 ABinary SearchTreeAbstraction . . . . . . . . . . . . . . . . . 151
5.8 SchemePredicatesasRecursive-DescentParsers . . . . . . . . . . . . 153
5.8.1 atom?, list-of-atoms?, and list-of-numbers? . . . 153
5.8.2 Factoring out the list-ofPattern. . . . . . . . . . . . . . . . 154
5.9 Local Binding: let, let*, and letrec . . . . . . . . . . . . . . . . . . 156
5.9.1 The let and let* Expressions . . . . . . . . . . . . . . . . . . 156
5.9.2 The letrec Expression . . . . . . . . . . . . . . . . . . . . . . . 158
5.9.3 Using let and letrec toDefine aLocalFunction. . . . . . 158
5.9.4 Other Languages Supporting Functional Programming:
MLandHaskell . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.10 AdvancedTechniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
5.10.1 MoreListFunctions . . . . . . . . . . . . . . . . . . . . . . . . . 166
5.10.2 Eliminating Expression Recomputation . . . . . . . . . . . . . 167
5.10.3 Avoiding Repassing Constant Arguments Across RecursiveCalls
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
5.11 Languages andSoftwareEngineering . . . . . . . . . . . . . . . . . . . 174
5.11.1 BuildingBlocks asAbstractions . . . . . . . . . . . . . . . . . . 174
5.11.2 Language Flexibility Supports Program Modification . . . . 175
5.11.3 MalleableProgramDesign . . . . . . . . . . . . . . . . . . . . . 175
5.11.4 FromPrototype toProduct . . . . . . . . . . . . . . . . . . . . . 175
5.12 Layersof FunctionalProgramming . . . . . . . . . . . . . . . . . . . . . 176
5.13 Concurrency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
5.14 ProgrammingProject forChapter 5 . . . . . . . . . . . . . . . . . . . . . 178
5.15 ThematicTakeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
5.16 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
5.17 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 182
6 Binding and Scope 185
6.1 ChapterObjectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
6.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
6.2.1 What Is aClosure? . . . . . . . . . . . . . . . . . . . . . . . . . . 186
6.2.2 StaticVis-à-VisDynamicProperties . . . . . . . . . . . . . . . 186
6.3 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
6.4 Static Scoping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
6.4.1 Lexical Scoping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
6.5 Lexical Addressing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
6.6 FreeorBoundVariables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
6.7 Dynamic Scoping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
6.8 Comparisonof Static andDynamic Scoping . . . . . . . . . . . . . . . 202
6.9 MixingLexicallyandDynamically ScopedVariables . . . . . . . . . . 207
6.10 TheFUNARGProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
6.10.1 TheDownwardFUNARGProblem . . . . . . . . . . . . . . . 214
6.10.2 TheUpwardFUNARGProblem . . . . . . . . . . . . . . . . . 215
6.10.3 RelationshipBetweenClosures andScope . . . . . . . . . . . 224
6.10.4 Uses ofClosures . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
6.10.5 The Upward and Downward FUNARG Problem in a
Single Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
6.10.6 Addressing the FUNARG Problem . . . . . . . . . . . . . . . . 226
6.11 Deep,Shallow, andAdHocBinding . . . . . . . . . . . . . . . . . . . . 233
6.11.1 DeepBinding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
6.11.2 ShallowBinding . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
6.11.3 AdHocBinding. . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
6.12 ThematicTakeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
6.13 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
6.14 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 242
Part II Types 243
7 Type Systems 245
7.1 ChapterObjectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
7.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
7.3 TypeChecking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
7.4 TypeConversion,Coercion,andCasting . . . . . . . . . . . . . . . . . 249
7.4.1 TypeCoercion: ImplicitConversion . . . . . . . . . . . . . . . 249
7.4.2 TypeCasting:ExplicitConversion . . . . . . . . . . . . . . . . 252
7.4.3 TypeConversionFunctions:ExplicitConversion . . . . . . . 252
7.5 ParametricPolymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . 253
7.6 Operator/FunctionOverloading . . . . . . . . . . . . . . . . . . . . . . 263
7.7 FunctionOverriding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
7.8 Static/DynamicTypingVis-à-VisExplicit/ImplicitTyping . . . . . . 268
7.9 Type Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
7.10 Variable-LengthArgumentLists inScheme . . . . . . . . . . . . . . . . 274
7.11 ThematicTakeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
7.12 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
7.13 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 283
8 Currying and Higher-Order Functions 285
8.1 ChapterObjectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
8.2 Partial FunctionApplication . . . . . . . . . . . . . . . . . . . . . . . . . 285
8.3 Currying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
8.3.1 CurriedForm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
8.3.2 CurryingandUncurrying . . . . . . . . . . . . . . . . . . . . . 294
8.3.3 The curry and uncurryFunctions inHaskell . . . . . . . . 295
8.3.4 Flexibility in Curried Functions . . . . . . . . . . . . . . . . . . 297
8.3.5 AllBuilt-inFunctions inHaskellAreCurried . . . . . . . . . 301
8.3.6 Supporting Curried Form Through First-Class Closures . . 307
8.3.7 MLAnalogs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
8.4 PuttingItAllTogether:Higher-OrderFunctions . . . . . . . . . . . . . 313
8.4.1 FunctionalMapping . . . . . . . . . . . . . . . . . . . . . . . . . 313
8.4.2 FunctionalComposition . . . . . . . . . . . . . . . . . . . . . . 315
8.4.3 Sections inHaskell . . . . . . . . . . . . . . . . . . . . . . . . . . 316
8.4.4 FoldingLists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
8.4.5 Crafting Cleverly Conceived Functions with Curried HOFs 324
8.5 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
8.6 ThematicTakeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
8.7 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
8.8 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 336
9 Data Abstraction 337
9.1 ChapterObjectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
9.2 AggregateDataTypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
9.2.1 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
9.2.2 Records . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
9.2.3 UndiscriminatedUnions . . . . . . . . . . . . . . . . . . . . . . 341
9.2.4 DiscriminatedUnions . . . . . . . . . . . . . . . . . . . . . . . . 343
9.3 InductiveDataTypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
9.4 VariantRecords . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
9.4.1 VariantRecords inHaskell . . . . . . . . . . . . . . . . . . . . . 348
9.4.2 Variant Records in Scheme: (define-datatype ...)
and (cases ...) . . . . . . . . . . . . . . . . . . . . . . . . . . 352
9.5 Abstract Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
9.6 Abstract-Syntax Tree for Camille . . . . . . . . . . . . . . . . . . . . . . 359
9.6.1 Camille Abstract-Syntax Tree Data Type: TreeNode . . . . . 359
9.6.2 Camille Parser Generator with Tree Builder . . . . . . . . . . 360
9.7 DataAbstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
9.8 Case Study:Environments . . . . . . . . . . . . . . . . . . . . . . . . . . 366
9.8.1 ChoicesofRepresentation . . . . . . . . . . . . . . . . . . . . . 367
9.8.2 ClosureRepresentationinScheme . . . . . . . . . . . . . . . . 367
9.8.3 ClosureRepresentationinPython . . . . . . . . . . . . . . . . 371
9.8.4 Abstract-SyntaxRepresentationinPython . . . . . . . . . . . 372
9.9 ML and Haskell: Summaries, Comparison, Applications, and
Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
9.9.1 MLSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
9.9.2 Haskell Summary . . . . . . . . . . . . . . . . . . . . . . . . . . 382
9.9.3 ComparisonofMLandHaskell . . . . . . . . . . . . . . . . . . 383
9.9.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
9.9.5 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
9.10 ThematicTakeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
9.11 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
9.12 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 387
Part III Interpreter Implementation 389
10 Local Binding and Conditional Evaluation 391
10.1 ChapterObjectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
10.2 Checkpoint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
10.3 Overview: Learning Language Concepts Through Interpreters . . . 393
10.4 Preliminaries: InterpreterEssentials . . . . . . . . . . . . . . . . . . . . 394
10.4.1 ExpressedValuesVis-à-VisDenotedValues . . . . . . . . . . 394
10.4.2 DefinedLanguageVis-à-VisDefiningLanguage . . . . . . . 395
10.5 The Camille Grammar and Language . . . . . . . . . . . . . . . . . . . 395
10.6 A First Camille Interpreter . . . . . . . . . . . . . . . . . . . . . . . . . . 396
10.6.1 Front End for Camille . . . . . . . . . . . . . . . . . . . . . . . . 396
10.6.2 Simple Interpreter for Camille . . . . . . . . . . . . . . . . . . . 399
10.6.3 Abstract-SyntaxTrees forArgumentsLists . . . . . . . . . . . 401
10.6.4 REPL:Read-Eval-PrintLoop . . . . . . . . . . . . . . . . . . . . 403
10.6.5 ConnectingtheComponents . . . . . . . . . . . . . . . . . . . . 404
10.6.6 How to Run a Camille Program . . . . . . . . . . . . . . . . . . 404
10.7 LocalBinding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
10.8 ConditionalEvaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
10.9 PuttingItAllTogether . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
10.10 ThematicTakeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
10.11 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
10.12 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 421
11 Functions and Closures 423
11.1 ChapterObjectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
11.2 Non-recursiveFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
11.2.1 Adding Support for User-Defined Functions to Camille . . . 423
11.2.2 Closures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426
11.2.3 Augmenting the evaluate_exprFunction . . . . . . . . . . 427
11.2.4 ASimple StackObject . . . . . . . . . . . . . . . . . . . . . . . . 430
11.3 RecursiveFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440
11.3.1 Adding Support for Recursion in Camille . . . . . . . . . . . 440
11.3.2 RecursiveEnvironment . . . . . . . . . . . . . . . . . . . . . . . 441
11.3.3 Augmenting evaluate_exprwithNewVariants . . . . . . 445
11.4 ThematicTakeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
11.5 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
11.6 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 456
12 Parameter Passing 457
12.1 ChapterObjectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
12.2 Assignment Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
12.2.1 Use of Nested lets to Simulate Sequential Evaluation . . . 458
12.2.2 Illustration of Pass-by-Value in Camille . . . . . . . . . . . . . 459
12.2.3 ReferenceDataType . . . . . . . . . . . . . . . . . . . . . . . . . 460
12.2.4 Environment Revisited . . . . . . . . . . . . . . . . . . . . . . . 462
12.2.5 Stack Object Revisited . . . . . . . . . . . . . . . . . . . . . . . . 463
12.3 Survey of Parameter-PassingMechanisms . . . . . . . . . . . . . . . . 467
12.3.1 Pass-by-Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
12.3.2 Pass-by-Reference . . . . . . . . . . . . . . . . . . . . . . . . . . 472
12.3.3 Pass-by-Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
12.3.4 Pass-by-Value-Result . . . . . . . . . . . . . . . . . . . . . . . . 478
12.3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481
12.4 Implementing Pass-by-Reference in the Camille Interpreter . . . . . 485
12.4.1 RevisedImplementationofReferences . . . . . . . . . . . . . 486
12.4.2 Reimplementation of the evaluate_operand Function . . 487
12.5 LazyEvaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
12.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
12.5.2 β-Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
12.5.3 C Macros to Demonstrate Pass-by-Name: β-Reduction
Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
12.5.4 TwoImplementations ofLazyEvaluation . . . . . . . . . . . 499
12.5.5 ImplementingLazyEvaluation:Thunks . . . . . . . . . . . . 501
12.5.6 LazyEvaluationEnablesListComprehensions . . . . . . . . 506
12.5.7 Applications ofLazyEvaluation . . . . . . . . . . . . . . . . . 511
12.5.8 Analysis ofLazyEvaluation . . . . . . . . . . . . . . . . . . . . 511
12.5.9 Purity and Consistency . . . . . . . . . . . . . . . . . . . . . . . 512
12.6 Implementing Pass-by-Name/Need in Camille: Lazy Camille . . . . 522
12.7 Sequential Execution in Camille . . . . . . . . . . . . . . . . . . . . . . . 527
12.8 Camille Interpreters: A Retrospective . . . . . . . . . . . . . . . . . . . 533
12.9 Metacircular Interpreters . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
12.10 ThematicTakeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542
12.11 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543
12.12 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 544
Part IV Other Styles of Programming 545
13 Control and Exception Handling 547
13.1 ChapterObjectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548
13.2 First-ClassContinuations . . . . . . . . . . . . . . . . . . . . . . . . . . . 548
13.2.1 TheConceptof aContinuation . . . . . . . . . . . . . . . . . . 548
13.2.2 Capturing First-Class Continuations: call/cc . . . . . . . . 550
13.3 GlobalTransferofControlwithContinuations . . . . . . . . . . . . . . 556
13.3.1 NonlocalExits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556
13.3.2 Breakpoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560
13.3.3 First-ClassContinuations inRuby . . . . . . . . . . . . . . . . 562
13.4 OtherMechanisms forGlobalTransferofControl . . . . . . . . . . . . 570
13.4.1 The gotoStatement . . . . . . . . . . . . . . . . . . . . . . . . . 570
13.4.2 Capturing and Restoring Control Context in C: setjmp
and longjmp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571
13.5 Levels of Exception Handling in Programming Languages: A
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
13.5.1 FunctionCalls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 580
13.5.2 Lexically Scoped Exceptions: break and continue . . . . . 581
13.5.3 StackUnwinding/Crawling . . . . . . . . . . . . . . . . . . . . 581
13.5.4 Dynamically Scoped Exceptions:
Exception-HandlingSystems . . . . . . . . . . . . . . . . . . . 582
13.5.5 First-ClassContinuations . . . . . . . . . . . . . . . . . . . . . . 583
13.6 ControlAbstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585
13.6.1 Coroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586
13.6.2 Applications of First-ClassContinuations . . . . . . . . . . . 589
13.6.3 ThePowerof First-ClassContinuations . . . . . . . . . . . . . 590
13.7 TailRecursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594
13.7.1 RecursiveControlBehavior . . . . . . . . . . . . . . . . . . . . 594
13.7.2 IterativeControlBehavior . . . . . . . . . . . . . . . . . . . . . 596
13.7.3 Tail-CallOptimization . . . . . . . . . . . . . . . . . . . . . . . . 598
13.7.4 SpaceComplexityandLazyEvaluation . . . . . . . . . . . . . 601
13.8 Continuation-Passing Style . . . . . . . . . . . . . . . . . . . . . . . . . . 608
13.8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608
13.8.2 AGrowingStack or aGrowingContinuation . . . . . . . . . 610
13.8.3 AnAll-or-NothingProposition . . . . . . . . . . . . . . . . . . 613
13.8.4 Trade-offBetweenTime andSpaceComplexity . . . . . . . . 614
13.8.5 call/ccVis-à-VisCPS . . . . . . . . . . . . . . . . . . . . . . . 617
13.9 Callbacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618
13.10 CPSTransformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 620
13.10.1 Defining call/cc in Continuation-Passing Style . . . . . . 622
13.11 ThematicTakeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635
13.12 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636
13.13 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 640
14 Logic Programming 641
14.1 ChapterObjectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642
14.2 PropositionalCalculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642
14.3 First-OrderPredicateCalculus . . . . . . . . . . . . . . . . . . . . . . . . 644
14.3.1 RepresentingKnowledge asPredicates . . . . . . . . . . . . . 645
14.3.2 ConjunctiveNormal Form . . . . . . . . . . . . . . . . . . . . . 646
14.4 Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648
14.4.1 ResolutioninPropositionalCalculus. . . . . . . . . . . . . . . 648
14.4.2 ResolutioninPredicateCalculus . . . . . . . . . . . . . . . . . 649
14.5 FromPredicateCalculus toLogicProgramming . . . . . . . . . . . . . 651
14.5.1 Clausal Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651
14.5.2 HornClauses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653
14.5.3 ConversionExamples . . . . . . . . . . . . . . . . . . . . . . . . 654
14.5.4 Motif ofLogicProgramming . . . . . . . . . . . . . . . . . . . . 656
14.5.5 ResolutionwithPropositions inClausal Form . . . . . . . . . 657
14.5.6 Formalism Gone Awry . . . . . . . . . . . . . . . . . . . . . . . 660
14.6 ThePrologProgrammingLanguage . . . . . . . . . . . . . . . . . . . . 660
14.6.1 EssentialProlog:AssertingFacts andRules . . . . . . . . . . 662
14.6.2 CastingHornClauses inPrologSyntax . . . . . . . . . . . . . 663
14.6.3 Running andInteractingwithaPrologProgram . . . . . . . 663
14.6.4 Resolution,Unification, andInstantiation . . . . . . . . . . . 665
14.7 Going Further inProlog . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667
14.7.1 ProgramControl inProlog:ABinaryTreeExample . . . . . 667
14.7.2 Lists andPatternMatching inProlog . . . . . . . . . . . . . . 672
14.7.3 ListPredicates inProlog . . . . . . . . . . . . . . . . . . . . . . 674
14.7.4 Primitive Nature of append . . . . . . . . . . . . . . . . . . . . 675
14.7.5 TracingtheResolutionProcess . . . . . . . . . . . . . . . . . . 676
14.7.6 Arithmetic inProlog . . . . . . . . . . . . . . . . . . . . . . . . . 677
14.7.7 Negationas Failure inProlog . . . . . . . . . . . . . . . . . . . 678
14.7.8 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679
14.7.9 Analogs BetweenPrologandanRDBMS . . . . . . . . . . . . 681
14.8 ImpartingMoreControl inProlog:Cut . . . . . . . . . . . . . . . . . . 691
14.9 Analysis ofProlog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 701
14.9.1 PrologVis-à-VisPredicateCalculus . . . . . . . . . . . . . . . 701
14.9.2 ReflectioninProlog . . . . . . . . . . . . . . . . . . . . . . . . . 703
14.9.3 MetacircularPrologInterpreterandWAM . . . . . . . . . . . 704
14.10 TheCLIPSProgrammingLanguage . . . . . . . . . . . . . . . . . . . . 705
14.10.1 Asserting Facts andRules . . . . . . . . . . . . . . . . . . . . . 705
14.10.2 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 706
14.10.3 Templates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707
14.10.4 Conditional Facts inRules . . . . . . . . . . . . . . . . . . . . . 708
14.11 ApplicationsofLogicProgramming . . . . . . . . . . . . . . . . . . . . 709
14.11.1 Natural Language Processing . . . . . . . . . . . . . . . . . . . 709
14.11.2 Decision Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 710
14.12 ThematicTakeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 710
14.13 ChapterSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 710
14.14 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 712
15 Conclusion 713
15.1 Language Themes Revisited . . . . . . . . . . . . . . . . . . . . . . . . . 714
15.2 RelationshipofConcepts . . . . . . . . . . . . . . . . . . . . . . . . . . . 714
15.3 MoreAdvancedConcepts . . . . . . . . . . . . . . . . . . . . . . . . . . 716
15.4 Bottom-upProgramming . . . . . . . . . . . . . . . . . . . . . . . . . . . 716
15.5 FurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719
Appendix A Python Primer 721
A.1 AppendixObjective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 721
A.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 722
A.3 DataTypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 722
A.4 Essential Operators and Expressions . . . . . . . . . . . . . . . . . . . . 725
A.5 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 731
A.6 Tuples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733
A.7 User-DefinedFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734
A.7.1 SimpleUser-DefinedFunctions . . . . . . . . . . . . . . . . . . 734
A.7.2 PositionalVis-à-VisKeywordArguments . . . . . . . . . . . . 735
A.7.3 LambdaFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . 738
A.7.4 LexicalClosures. . . . . . . . . . . . . . . . . . . . . . . . . . . . 739
A.7.5 MoreUser-DefinedFunctions . . . . . . . . . . . . . . . . . . . 740
A.7.6 LocalBindingandNestedFunctions . . . . . . . . . . . . . . . 742
A.7.7 MutualRecursion . . . . . . . . . . . . . . . . . . . . . . . . . . 744
A.7.8 Putting ItAllTogether:Mergesort . . . . . . . . . . . . . . . . 744
A.8 Object-OrientedProgramminginPython . . . . . . . . . . . . . . . . . 748
A.9 ExceptionHandling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 750
A.10 ThematicTakeaway . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 754
A.11 AppendixSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 754
A.12 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 755
Appendix B Introduction toML (Online) 757
B.1 AppendixObjective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 757
B.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 757
B.3 PrimitiveTypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 758
B.4 Essential Operators and Expressions . . . . . . . . . . . . . . . . . . . . 758
B.5 Running anMLProgram . . . . . . . . . . . . . . . . . . . . . . . . . . . 760
B.6 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 762
B.7 Tuples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 763
B.8 User-DefinedFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764
B.8.1 SimpleUser-DefinedFunctions . . . . . . . . . . . . . . . . . . 764
B.8.2 LambdaFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . 764
B.8.3 Pattern-DirectedInvocation . . . . . . . . . . . . . . . . . . . . 765
B.8.4 Local Binding and Nested Functions: let Expressions . . . 768
B.8.5 MutualRecursion . . . . . . . . . . . . . . . . . . . . . . . . . . 770
B.8.6 Putting ItAllTogether:Mergesort . . . . . . . . . . . . . . . . 770
B.9 DeclaringTypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 774
B.9.1 InferredorDeduced . . . . . . . . . . . . . . . . . . . . . . . . . 774
B.9.2 ExplicitlyDeclared . . . . . . . . . . . . . . . . . . . . . . . . . . 774
B.10 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 775
B.11 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 776
B.12 Input andOutput . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 776
B.12.1 Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 776
B.12.2 Parsing anInputFile . . . . . . . . . . . . . . . . . . . . . . . . . 777
B.12.3 Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 778
B.13 ThematicTakeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 781
B.14 AppendixSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 782
B.15 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 782
Appendix C Introduction to Haskell (Online) 783
C.1 AppendixObjective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 783
C.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 783
C.3 PrimitiveTypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 784
C.4 TypeVariables,TypeClasses, andQualifiedTypes . . . . . . . . . . . 785
C.5 Essential Operators and Expressions . . . . . . . . . . . . . . . . . . . . 787
C.6 Running aHaskellProgram . . . . . . . . . . . . . . . . . . . . . . . . . 789
C.7 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 791
C.8 Tuples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 792
C.9 User-DefinedFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793
C.9.1 SimpleUser-DefinedFunctions . . . . . . . . . . . . . . . . . . 793
C.9.2 LambdaFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . 794
C.9.3 Pattern-DirectedInvocation . . . . . . . . . . . . . . . . . . . . 795
C.9.4 Local Binding and Nested Functions: let Expressions . . . 799
C.9.5 MutualRecursion . . . . . . . . . . . . . . . . . . . . . . . . . . 801
C.9.6 Putting ItAllTogether:Mergesort . . . . . . . . . . . . . . . . 802
C.10 DeclaringTypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 806
C.10.1 InferredorDeduced . . . . . . . . . . . . . . . . . . . . . . . . . 806
C.10.2 ExplicitlyDeclared . . . . . . . . . . . . . . . . . . . . . . . . . . 806
C.11 ThematicTakeaways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 810
C.12 AppendixSummary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 810
C.13 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 810
Appendix D Getting Started with the Camille Programming Language
(Online) 811
D.1 AppendixObjective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 811
D.2 Grammar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 811
D.3 Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 813
D.4 GitRepository StructureandSetup . . . . . . . . . . . . . . . . . . . . . 813
D.5 How to Use Camille in a Programming Languages Course . . . . . . 814
D.5.1 Module 0: FrontEnd(Scanner andParser) . . . . . . . . . . . 814
D.5.2 Chapter 10 Module: Introduction (Local Binding and
Conditionals) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 814
D.5.3 Configuring theLanguage . . . . . . . . . . . . . . . . . . . . . 815
D.5.4 Chapter 11 Module: Intermediate (Functions and Closures) 816
D.5.5 Chapter 12 Modules: Advanced (Parameter Passing,
Including Lazy Evaluation) and Imperative (Statements
andSequentialEvaluation) . . . . . . . . . . . . . . . . . . . . . 818
D.6 ExampleUsage:Non-interactivelyandInteractively(CLI) . . . . . . 818
D.7 Solutions toProgrammingExercises inChapters 10–12 . . . . . . . . 819
D.8 Notes andFurtherReading . . . . . . . . . . . . . . . . . . . . . . . . . . 821
Appendix E Camille Grammar and Language (Online) 823
E.1 AppendixObjective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 823
E.2 Camille 0.1: Numbers and Primitives . . . . . . . . . . . . . . . . . . . 823
E.3 Camille 1.:LocalBindingandConditionalEvaluation . . . . . . . . 824
E.4 Camille 2.:Non-recursiveandRecursiveFunctions . . . . . . . . . . 825
E.5 Camille 3.: Variable Assignment and Support for Arrays . . . . . . 826
E.6 Camille 4.: SequentialExecution . . . . . . . . . . . . . . . . . . . . . . 827
Bibliography B-1
Index I-1
[/spoiler]