Programming Languages (Lectures Slides)

1 Introduction......Page 2
Sources......Page 4
Programming Paradigms......Page 5
What is Programming Language......Page 6
Themes addressed in this Course......Page 8
Generations of PLs......Page 9
How do PPs differ......Page 10
Programming Paradigms......Page 11
Compilers & Interpreters......Page 12
Quick Tour of PLs History......Page 13
Brief Chronology......Page 14
Fortran......Page 15
ALGOL 60......Page 18
COBOL......Page 20
PL/1......Page 22
Functional Languages......Page 24
Prolog......Page 26
Object-oriented Languages......Page 28
Interactive Languages......Page 30
Special-Purpose Languages......Page 32
Symbolic Languages .........Page 33
4GLs......Page 34
Scripting Languages......Page 37
Future......Page 39
What you should know!......Page 40
Can you answer these questions?......Page 41
2 Stack-based Programming......Page 42
Refs......Page 43
PostScript Objects, Types & Stacks......Page 44
What is PostScript......Page 45
Postscript variants......Page 46
Syntax......Page 47
Semantics......Page 48
Object Types......Page 50
Arithmetic Operators......Page 51
Operand Stack......Page 52
Stack & Arithmetic Operators......Page 54
Graphics Operators......Page 55
Coordinates......Page 56
Drawing a Box......Page 57
Path Construction Operators......Page 59
“Hello World” in Postscript......Page 60
Encapsulated PostScript......Page 62
Character & Font Operators......Page 63
Procedures & Variables......Page 64
Procedures & Variables......Page 65
Box Procedure......Page 67
Graphics State & Coordinate Operators......Page 69
Fibonacci Graph......Page 71
Numbers & Strings......Page 72
Factorial......Page 73
Boolean, Control & String Operators......Page 75
Simple Formatter......Page 76
Arrays & Dictionaries......Page 78
Array & Dictionary Operators......Page 79
Using Dictionaries - Arrowheads......Page 80
Instantiating Arrows......Page 83
3 Functional Programming......Page 87
Refs......Page 88
Functional vs Imperative Programming......Page 89
Bit of History......Page 90
Programming without State......Page 92
Pure Functional PLs......Page 94
Key Features of Pure FLs......Page 95
What is Haskell......Page 97
“Hello World” in Haskell......Page 100
Pattern Matching......Page 103
Pattern Matching......Page 104
Lists......Page 106
Using Lists......Page 108
List Comprehensions......Page 110
Referential Transparency......Page 112
Referential Transparency......Page 113
Evaluation of Expressions......Page 114
Lazy Evaluation......Page 116
Lazy Evaluation......Page 117
Lazy Lists......Page 119
Programming Lazy Lists......Page 121
Declarative Programming Style......Page 123
Recursion......Page 124
Tail Recursion......Page 125
Multiple Recursion......Page 128
Higher Order & Curried Functions......Page 129
Higher Order Functions......Page 130
Anonymous Functions......Page 132
Curried Functions......Page 133
Understanding Curried Functions......Page 134
Using Curried Functions......Page 136
Currying......Page 137
To be continued …......Page 138
4 Types & Polymorphism......Page 141
Refs......Page 142
Static & Dynamic Types......Page 143
What is a Type......Page 144
Static & Dynamic Types......Page 148
Static Types restrict the Programs you may write!......Page 150
Static & Dynamic Typing......Page 152
Strong, Weak, Static, Dynamic......Page 154
Kinds of Types......Page 155
Type Completeness......Page 156
Types in Haskell......Page 159
Function Types......Page 160
List Types......Page 162
Tuple Types......Page 163
User Data Types......Page 164
Enumeration types......Page 166
Union Types......Page 168
Recursive Data Types......Page 170
Using Recursive Data Types......Page 172
Monomorphic & Polymorphic Types......Page 174
Monomorphism......Page 175
Polymorphism......Page 177
Kinds of Polymorphism......Page 178
Hindley-Milner Type Inference......Page 180
Type Inference......Page 181
Composing Polymorphic Types......Page 183
Polymorphic Type Inference......Page 185
Type Specialization......Page 188
Overloading......Page 189
Coercion vs Overloading......Page 190
Overloading......Page 192
Instantiating overloaded operators......Page 194
Equality for Data Types......Page 195
Equality for Functions......Page 196
5 Intro to the Lambda Calculus......Page 199
Refs......Page 200
Computability - Church Thesis......Page 201
What is Computable......Page 202
Church Thesis......Page 203
Uncomputability......Page 204
What is a Function......Page 205
Lambda Calculus - Operational Semantics......Page 209
What is Lambda Calculus......Page 210
Parsing Lambda Expressions......Page 212
What is Lambda Calculus .........Page 213
Beta Reduction......Page 215
Lambda Expressions in Haskell......Page 217
Lambdas are Anonymous Functions......Page 218
Free & Bound Variables......Page 220
Few Examples......Page 222
“Hello World” in Lambda Calculus......Page 223
Church-Rosser Property......Page 224
Why Macro Expansion is wrong......Page 225
Substitution......Page 226
Alpha Conversion......Page 228
Eta Reduction......Page 229
Normal Forms......Page 231
Few Examples......Page 232
Evaluation Order......Page 233
Church-Rosser Property......Page 234
Modelling basic Programming Constructs......Page 235
Non-Termination......Page 236
Currying......Page 237
Representing Booleans......Page 239
Representing Tuples......Page 241
Tuples as Functions......Page 243
6 Fixed Points......Page 246
Refs......Page 247
Representing Numbers......Page 248
Recall these Encodings …......Page 249
Representing Numbers......Page 250
Working with Numbers......Page 252
Recursion & Fixed-Point Combinator......Page 254
Recursion......Page 255
Recursive Functions as Fixed Points......Page 257
Fixed Points......Page 259
Fixed Point Theorem......Page 260
How does Y work......Page 262
Using the Y Combinator......Page 264
Recursive Functions are Fixed Points......Page 266
Unfolding Recursive Lambda  Expressions......Page 268
Typed Lambda Calculus......Page 270
Polymorphic Lambda Calculus......Page 273
Polymorphic Lambda Calculus......Page 274
Hindley-Milner Polymorphism......Page 276
Polymorphism & Self Application......Page 277
Built-in Recursion with letrec AKA def AKA µ......Page 279
Other Calculi......Page 281
Featherweight Java......Page 282
Other Calculi......Page 284
Quick Look at π Calculus......Page 285
7 Intro to Denotational Semantics......Page 288
Refs......Page 289
Syntax & Semantics......Page 290
Defining Programming Languages......Page 291
Uses of Semantic Specifications......Page 292
Methods for Specifying Semantics......Page 293
Semantics of Expressions......Page 298
Concrete & Abstract Syntax......Page 299
Calculator Language......Page 301
Calculator Semantics......Page 303
Semantic Domains......Page 306
Data Structures for Abstract Syntax......Page 308
Representing Syntax......Page 310
Implementing the Calculator......Page 312
Semantics of Assignment......Page 315
Language with Assignment......Page 316
Representing Abstract Syntax Trees......Page 318
Abstract Syntax Tree......Page 320
Modelling Environments......Page 321
Functional Updates......Page 323
Semantics of Assignments in Haskell......Page 324
Running the Interpreter......Page 326
Other Issues......Page 327
Practical Issues......Page 328
Theoretical Issues......Page 329
8 Objects & Prototypes......Page 332
Refs......Page 334
Class- vs Prototype-based Languages......Page 335
Class-based vs Prototype-based......Page 336
Prototype-based Languages......Page 338
Objects, Properties & Methods......Page 339
What is JavaScript......Page 340
Syntax......Page 341
Object Properties......Page 342
Methods......Page 344
Scripting Web Browser......Page 346
Delegation......Page 348
Delegation......Page 349
Delegation of Messages......Page 351
Constructors......Page 353
Constructor Functions......Page 354
Constructor.prototype......Page 356
Object Model......Page 360
Predefined Objects......Page 362
Extending Predefined Objects......Page 363
The arguments object......Page 365
Closures......Page 367
Variable Scopes......Page 368
Closures......Page 370
Closures & Objects......Page 373
Snakes & Ladders with Prototypes......Page 375
Snakes & Ladders......Page 376
Assertions & Exceptions......Page 378
Closures......Page 380
Asynchrony......Page 382
Delegation vs Inheritance......Page 384
JSON......Page 386
Interpreting JSON......Page 388
“Adam’s rib”......Page 390
The Top Level......Page 392
The Good, the Bad & the Ugly......Page 396
The Good......Page 397
The Bad (globals)......Page 399
The Bad (arrays)......Page 401
The Bad (...)......Page 403
The Ugly......Page 405
What you should know!......Page 407
9 Objects, Types & Classes......Page 409
Literature......Page 413
Principle of Substitutability......Page 415
Subclassing ≠ Subtyping ≠ Is-a......Page 416
Principle of Subtitutability......Page 418
Components & Compatibility......Page 420
Kinds of Compatibility......Page 422
Liskov Substitutability Principle......Page 424
Types & Polymorphism......Page 426
Review - Static & Dynamic Typing......Page 427
Review - Polymorphism......Page 429
OO Polymorphism......Page 431
Review - Kinds of Polymorphism......Page 433
Kinds of Type Compatibility......Page 435
Kinds of Types......Page 437
Type Rules & Type-checking......Page 439
Dimensions of Type-checking......Page 440
Type-checking exact Interfaces......Page 442
Type Rules......Page 444
Applying the Rules......Page 450
Object Encodings & Recursion......Page 452
Object Encodings and Recursion......Page 453
Existential Object Encoding......Page 455
An Existential Point......Page 457
Pros and Cons......Page 459
Functional Object Encoding......Page 461
A Functional Point......Page 463
Objects and Recursion......Page 465
Pros and Cons......Page 467
Abadi and Cardelli’s Object Calculus......Page 469
Literature (II)......Page 472
Subtypes, Covariance & Contravariance......Page 473
Generators & Fixpoints......Page 474
Recursive Types......Page 476
Types as Sets......Page 478
Function Subtyping......Page 480
Covariant Types......Page 482
Covariant Type Errors......Page 484
Contravariant Types......Page 486
Covariance & Contravariance......Page 488
Overloading......Page 490
Example......Page 492
Overloading......Page 494
Checking Subtypes......Page 496
Record Extension......Page 497
Record Overriding......Page 499
Record Subtyping......Page 501
Recursive Subtypes......Page 503
Types in Practice......Page 505
Classes as Families of Types......Page 507
The Problem with Recursive Closure......Page 508
The Problem of Type-Loss......Page 510
Classes as Type Generators......Page 512
F-bounded Quantification......Page 514
Classes as Families of Types......Page 516
Types & Classes......Page 518
Inheritance - Subclassing without Subtyping......Page 520
(Partial) Answers......Page 522
10 Logic Programming......Page 525
Refs......Page 526
Facts & Rules......Page 527
Logic Programming Languages......Page 528
What is Prolog......Page 530
Horn Clauses......Page 532
Resolution & Unification......Page 533
Resolution & Unification......Page 534
Prolog Databases......Page 536
Simple Queries......Page 537
Queries with Variables......Page 539
Unification......Page 541
Evaluation Order......Page 543
Closed World Assumption......Page 545
Searching & Backtracking......Page 546
Backtracking......Page 547
Comparison......Page 549
Sharing Subgoals......Page 551
Disjunctions......Page 552
Recursion, Functions & Arithmetic......Page 553
Recursion......Page 554
Evaluation Order......Page 558
Failure......Page 560
Cuts......Page 562
Red & Green Cuts......Page 564
Negation as Failure......Page 565
Changing the Database......Page 567
Functions & Arithmetic......Page 571
Defining Functions......Page 573
Lists & other Structures......Page 574
Lists......Page 575
Pattern Matching with Lists......Page 577
Inverse relations......Page 581
Exhaustive Searching......Page 583
Limits of Declarative Programming......Page 585
11 Applications of Logic Programming......Page 589
Ref......Page 590
Search Problems......Page 591
Solving a Puzzle......Page 592
Non-Solution......Page 594
1st Solution......Page 598
2nd (Non-)Solution......Page 602
3rd Solution......Page 605
4th Solution......Page 611
Symbolic Interpretation......Page 617
Symbolic Interpretation......Page 618
Goal-directed interpretation......Page 619
Definite Clause Grammars......Page 621
Definite Clause Grammars......Page 622
DCG translation......Page 626
Interpretation as Proof......Page 628
Example......Page 629
How does it work?......Page 632
How to use this?......Page 634
Interpreter for the Calculator Language......Page 636
Lexical Analysis......Page 638
Recognizing Tokens......Page 641
Recognizing Numbers......Page 643
Concrete Grammar......Page 645
Parsing with DCGs......Page 647
Representing Programs as Parse Trees......Page 649
Testing......Page 651
Interpretation as Proof......Page 652
Building simple Interpreter......Page 653
Testing the Interpreter......Page 655
Top-Level Script......Page 656
Lambda Calculus Interpreter......Page 658
Lambda Interpreter (excerpt)......Page 659
Running the Interpreter......Page 661