198:314 Principles of Programming Languages
Fall 2007

Ryder's Lecture Notes

Required readings in our textbook Michael L. Scott, Programming Language Pragmatics, Second Edition, 2006, are indicated by Scott below. Note a list of errors in the textbook is available here. Supplemental readings may also be listed during the term; they will be found in the SERC Reading Room on reserve.

Please print out these lecture notes (which are in PDF 2-up) as double-sided output to save trees.

• September 4, 2007, Lecture 1: Introduction 2-up for printing
  Why study programming languages, history of PLs
  Reading: Scott Ch 1
  Slides covered: Intro #1-25
  
  
• September 6, 2007, Lecture 2: Formal Languges 2-up for printing
  Syntax, Regular expressions and regular grammars, Backus Naur Form (BNF), Grammars
  Reading: Scott pp 37-43, 46-54.
  Additional References: Aho, Sethi, Ullman, Compilers: Principles, Techniques and Tools, first edition, Section 3.3 (regular expressions), 3.6, 3.7 (finite state machines, both deterministic and nondeterministic)
  Slides covered: Formal #1-12
  
  
• September 11, 2007, Lecture 3: Formal Languges-2 2-up for printing
  Context-free grammars, derivation, parse, precedence and ambiguity,
  parse trees
  Reading: Scott pp. 43-46.
  Slides covered: Formal #13-20; Formal-2 #1-13
  
  
• September 13, 2007, Lecture 4: Formal Languges-3 2-up for printing
  ambiguity in PLs, if-then-else constructs,
  Reading: Scott pp 61-70, 94-96
  Slides covered: Formal-2 #14-17; Formal-3 #1-12
  Slides corrected: Formal-3 #14
  
  
• September 18, 2007, Lecture 5: Formal Languages-3, cont.
  parsing techniques, Chomsky hierarchy for formal languages
  Example of recusive descent parsing
  Slides covered: Formal-3 #13-24.
  
  
• September 20, 2007, Lecture 6: Prolog 2-up for printing
  constructs: facts, rules, queries through examples
  Prolog vs logic programming, Horn clauses,
  Reading: Scott pp 559-571 (Ch 11)
  Slides covered: Prolog #1-26
  Slides corrected: Prolog #20,26
  
  
• September 25, 2007, Lecture 7: Prolog-2 2-up for printing
  Lists in Prolog, recursive functions, search trees for debugging,
  tracing in Prolog, example of recursive descent parser
  Reading: Scott pp 571-583 (Ch 11)
  Slides covered: Prolog # 26-28; Prolog-2 #1-12
  
  
• September 27, 2007, Lecture 8: Prolog-2, cont.
  More functions on lists, search trees for debugging,
  tracing in Prolog, more discussion on recursive descent parsing
  Reading: same as lectures 6.7
  Slides covered: Prolog-2 #12-21
  
  
• October 2, 2007, Lecture 9: Prolog-3 2-up for printing
  Notes changed for slides 8,11,14 at 10am Oct 2nd
  List append function, generate and test example: n-Queens,
  unification - informally (matching) and formally (substitution)
  Reading: same as lectures 6,7; (bring to lecture) nqueens.pl
  Note: nqueens.pl program changed; new tar file available as of 10am Oct 2nd
  Programs: A tar file containing Prolog programs including examples
  from lecture are available for download here.
  Slides covered: Prolog-3 #1-20
  
  
• October 4, 2007, Lecture 10: Names-Bindings-Scope 2-up for printing
  Names and binding times, kinds of storage: static, stack, heap; Lexical scoping
  Reading: Scott pp. 102-124, 407-413
  Slides covered: Names-Bindings-Scope #1-15;
  
  
  
• October 9, 2007, Lecture 11: Names-Bindings-Scope, cont
  More on lexical scoping, how to implement using the static chain
  Slides covered: Semantics-Names-Bindings #15-37
  Slides corrected: Names-Bindings-Scope #17-21
  Slides changed Names-Bindings-Scope #20
  
  
  
• October 11, 2007, Lecture 12: Names-Bindings-Scope2 2-up for printing
  Algol60 display implementation, How to handle recursion in scoping?
  Dynamic scoping, central reference table
  Reading: Scott pp. 407-413+CD on displays(107-110), on dynamic scope (131-135)
  Slides covered: Names-Bindings-Scope2 #1-19
  
  
• October 16, 2007, Lecture 13: Semantics-Memory-Management 2-up for printing
  More on bindings, aliasing, heap problems: garbage, dangling pointers
  Reading: Scott pp. 142-143(aliasing), 238-241 (value/reference models),
  369-389 (especially 379-389) (garbage collection)
  Slides covered: Memory-Manage #1-20
  
  
• October 18, 2007, Lecture 13: Semantics-Memory-Management2 2-up for printing
  Garbage collection, reachability, Algorithms: mark and sweep,
  copy collection, generational collection, conservative collection
  Reading: Scott pp 369-389 (especially 379-389) (garbage collection)
  Slides covered: Memory-Manage-2 #1-38
  
  
• October 23, 2007: MIDTERM IN-CLASS EXAM
  
  
• October 25, 2007: Lecture 14 (Dr. Alex Borgida): Intro to Scheme 2-up for printing
  pure functional programming languages, S-expressions, cons, car, cdr,
  defining functions, read-eval-print loop of Lisp interpreter,
  recursive functions, equality testing
  Reading: Scott pp 523-539
  Slides covered:
  
  
• October 30, 2007: Lecture 15: Scheme, cont
  S-expressions, defining functions
  Scheme functions from lecture including atom?, len, atomcount, app, eql?
  Slides covered: Scheme #1-15
  
  
• November 1, 2007: Lecture 16: Scheme, cont
  deep versus shallow recursive functions, equality testing
  Higher-order functions 2-up for printing
  (These were previously posted under Lecture 15)
  Examples: Map, Foldr, using Apply and Eval
  atomcnt2
  atomcnt3
  map and mapp examples
  foldr
  Reading: Scott pp 545-549
  Slides covered: Scheme #15-31; Scheme-2 #1-14
  
  
• November 6, 2007: Lecture 17: Scheme-2: higher order functions
  Higher-order functions, foldl, lexical scoping with let's
  Examples: foldr, foldl, map, filter
  map functions
  filters
  more on foldr and foldl
  more on foldl
  Slides covered: Scheme-2 #14-17
  
  
• November 8, 2007: Lecture 18, Scheme-2, cont
  Let expressions
  Functional languages-3 2-up for printing
  Tail recursion, closures, streams, lambda calculus
  Examples: streams, closures
  curried fcns
  examples of streams
  even more on foldl, foldr
  Slides covered: Scheme-2 #18-21, Functional3 #1-15
  
  
• November 13, 2007: Lecture 19, Functional-3, cont
  lambda calculus
  Parameter Passing mechanisms 2-up for printing
  pass by value, by name, by reference, by value-result, by result
  Readings: Scott pp 407-413, 417-433, CD:107-110, CD:122-124
  Slides covered: Functl-3 #16-19, ParamPassing #1-12
  Google map-reduce website
  
  
• November 15, 2007: Lecture 20: Parameter Passing, cont
  pass by name, aliasing, function arguments
  Types 2-up for printing
  What is a type? type checking, conversion and coercion
  Readings: Scott pp 143-148, 308-319, 321-336
  Slides covered: ParamPassing #13-20, Types #1-16
  
  
• November 20, 2007: Lecture 21:Types, cont
  Type conversion, aggregate types: strings, arrays
  Scripting Languages 2-up for printing
  Properties of scripting PLs, Python: lexical scoping,
  common errors, datatypes: numbers, sequences - strings
  Simple programs: strings.py scope1.py, scope2.py, scope3.py,
  Readings: Scott, types: pp 336-366, scripting: 671-677,
  677-701(skim, look for Python refs),723-725
  Slides covered: Types: #16-28, Scripting #1-12
  Slides changed: Scripting #14,20
  
  
• November 27, 2007: Lecture 22: Scripting Languages, cont
  Python: sequences: strings, lists, tuples, mappings (dictionaries), files
  Python 2-up for printing
  basic statements
  More simple programs: file.py,, lists.py, dictionaries.py
  OverloadedOperators.py, intersect.y,
  Readings:
  Slides covered: Scripting #13-22, Python #1-6
  Slides changed: Python #3,5,6
  
  
• November 29, 2007: Lecture 23: Python, cont.
  Defining functions, parameter passing, exceptions
  Python-2 2-up for printing
  regular expressions in Python, defining and using patterns,
  Using the os and re modules
  More simple programs: except.py, gener.py,
  iter.py, os-walk.py, os-walk.out
  addrs.py, addr, addrs.out
  patt.py, patt.out
  Slides covered: Python #7-15, Python2 #1-11
  
  
• December 4, 2007: Lecture 24: Python, cont
  iterators and generators,co-routines
  Types-2 2-up for printing
  strings, enumerated types, structures, user defined types, type unions
  References: Andrew S. Tanenbaum, "A Tutorial on Algol 68", ACM Computing Surveys, June 1976, pp 155-190
  Slides covered: Python #16-30, Types2 #1-10
  
  
• December 6, 2007: Lecture 25: Types2 cont
  unions, type checking, structural and name type equivalence,
  dereferencing as type conversion
  Slices covered: Types2 #11-34
  
  
• December 11, 2007: Lecture 26: Keynote from HOPL-III: 50 in 50
  Guy Steele and Richard Gabriel
  Overview of history of programming languages over past 50 years, up until early 1990s
  
  

Last update 9:32pm on December 4, 2007 by BG Ryder.