Programming Languages: An Active Learning Approach

✍ Scribed by Kent Lee

• Year: 2008
• Tongue: English
• Leaves: 289
• Edition: 1
• Category: Library

✦ Synopsis

Programming Languages: An Active Learning Approach introduces students to three programming paradigms: object-oriented/imperative languages using C++ and Ruby, functional languages using Standard ML, and logic programming using Prolog. This interactive textbook is intended to be used in and outside of class. Each chapter follows a pattern of presenting a topic followed by a practice exercise or exercises that encourage students to try what they have just read. This textbook is best-suited for students with a 2-3 course introduction to imperative programming. Key Features: (1) Accessible structure guides the student through various programming languages. (2) Seamlessly integrated practice exercises. (3) Classroom-tested. (4) Online support materials. Advance praise: “The Programming Languages book market is overflowing with books, but none like this. In many ways, it is precisely the book I have been searching for to use in my own programming languages course. One of the main challenges I perpetually face is how to teach students to program in functional and logical languages, but also how to teach them about compilers. This book melds the two approaches very well.” -- David Musicant, Carleton College

✦ Table of Contents

Contents......Page 9
Preface......Page 6
1. Introduction......Page 13
1.1 Historical Perspective......Page 14
1.2 Models of Computation......Page 16
1.3 The Origins of a Few Programming Languages......Page 19
1.4 Language Implementation......Page 24
1.5 Where do we go from here?......Page 29
1.6 Exercises......Page 30
1.7 Solutions to Practice Problems......Page 31
1.8 Additional Reading......Page 32
2.1 Terminology......Page 33
2.2 Backus Naur Form (BNF)......Page 35
2.3 The EWE Language......Page 36
2.4 Context-Free Grammars......Page 40
2.5 Derivations......Page 41
2.6 Parse Trees......Page 42
2.7 Parsing......Page 43
2.8 Parser Generators......Page 44
2.11 Other Forms of Grammars......Page 45
2.12 Abstract Syntax Trees......Page 49
2.14 Limitations of Syntactic Definitions......Page 50
2.15 Exercises......Page 52
2.16 Solutions to Practice Problems......Page 53
2.17 Additional Reading......Page 58
3. Object-Oriented Programming with C++......Page 59
3.1 Application Development......Page 60
3.2 The Token Class......Page 67
3.3 Implementing a Class......Page 69
3.4 Inheritance and Polymorphism......Page 71
3.5 A Historical Look at Parameter Passing......Page 74
3.6 Const in C++......Page 79
3.7 The AST Classes......Page 82
3.8 The Scanner......Page 85
3.9 The Parser......Page 87
3.10 Putting It All Together......Page 93
3.11 Exercises......Page 96
3.12 Solutions to Practice Problems......Page 99
3.13 Additional Reading......Page 102
4. Object-Oriented Programming with Ruby......Page 103
4.1 Designing Calc......Page 105
4.2 The Token Class......Page 106
4.3 Parameter Passing in Ruby vs C++......Page 107
4.4 Accessor and Mutator methods in Ruby......Page 108
4.6 The AST Classes......Page 109
4.7 Polymorphism in Ruby......Page 112
4.8 The Scanner......Page 114
4.9 The Parser......Page 115
4.10 Putting It All Together......Page 119
4.11 Static vs Dynamic Type Checking......Page 121
4.12 Exercises......Page 124
4.13 Solutions to Practice Problems......Page 126
4.14 Additional Reading......Page 128
5. Functional Programming in Standard ML......Page 129
5.1 Imperative vs Functional Programming......Page 130
5.2 The Lambda Calculus......Page 131
5.3 Getting Started with Standard ML......Page 134
5.4 Expressions, Types, Structures, and Functions......Page 135
5.5 Recursive Functions......Page 137
5.6 Characters, Strings, and Lists......Page 139
5.7 Pattern Matching......Page 141
5.8 Tuples......Page 142
5.9 Let Expressions and Scope......Page 143
5.10 Datatypes......Page 145
5.12 Efficiency of Recursion......Page 148
5.13 Tail Recursion......Page 150
5.14 Currying......Page 152
5.15 Anonymous Functions......Page 153
5.16 Higher-Order Functions......Page 154
5.17 Continuation Passing Style......Page 160
5.18 Input and Output......Page 161
5.19 Programming with Side-effects......Page 162
5.20 Exception Handling......Page 164
5.21 Encapsulation in ML......Page 165
5.22 Type Inference......Page 167
5.23 Exercises......Page 170
5.24 Solutions to Practice Problems......Page 173
5.25 Additional Reading......Page 180
6. Language Implementation in Standard ML......Page 181
6.1 Using ML-lex......Page 182
6.2 The Calculator Abstract Syntax Definition......Page 184
6.3 Using ML-yacc......Page 185
6.4 Code Generation......Page 187
6.5 Compiling in Standard ML......Page 191
6.6 Extending the Language......Page 193
6.7 Let Expressions......Page 194
6.8 Defining Scope in Block Structured Languages......Page 197
6.9 If-Then-Else Expressions......Page 198
6.10 Functions in a Block-Structured Language......Page 200
6.11 Sequential Execution......Page 207
6.12 Exercises......Page 209
6.13 Solutions to Practice Problems......Page 211
6.14 Additional Reading......Page 214
7. Logic Programming......Page 215
7.1 Getting Started with Prolog......Page 217
7.2 Fundamentals......Page 218
7.3 Lists......Page 220
7.5 Unification and Arithmetic......Page 223
7.6 Input and Output......Page 224
7.7 Structures......Page 225
7.8 Parsing in Prolog......Page 227
7.9 Prolog Grammar Rules......Page 232
7.10 Exercises......Page 234
7.11 Solutions to Practice Problems......Page 235
7.12 Additional Reading......Page 237
8. Formal Semantics......Page 238
8.1 Attribute Grammars......Page 240
8.2 Axiomatic Semantics......Page 243
8.3 Action Semantics......Page 245
8.4 Exercises......Page 256
8.6 Additional Reading......Page 257
Appendix A: The C++ Scanner Class Implementation......Page 258
Appendix B: The Ruby Scanner Class Implementation......Page 262
C.2 The Int Structure......Page 265
C.3 The Real Structure......Page 266
C.4 The Char Structure......Page 268
C.6 The List Structure......Page 269
C.7 The TextIO Structure......Page 270
Appendix D: SML Calculator Compiler......Page 272
Appendix E: The Factorial Program's Code......Page 275
Appendix F: Small Action Semantic Description......Page 278
References......Page 284
C......Page 286
L......Page 287
R......Page 288
Y......Page 289