198:314 Principles of Programming Languages
Spring 2004

Ryder's Lecture Notes

Required reading in our Louden textboook (indicated by L) are indicated below. Also listed are supplemental readings in Aho, Sethi, Ullman, Compilers: Principles, Practices and Techniques, Addison-Wesley, 1986 (indicated by ASU) which can be found in the SERC Reading Room on reserve. Additional supplemental readings are given in Sethi, Programming Languages, Concepts and Constructs which can 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.

• January 21, 2004, Lecture 1: Introduction 2-up for printing
  Why study programming languages, history of PLs
  Reading: L Chs 1-2
  Slides covered: Intro #1-32
  Slides corrected: Intro #14
  
  
• January 23, 2004, Lecture 2: Formal Languages-1 2-up for printing
  syntax, regular expressions
  Reading: L Ch 4 (4.1-4.5,4.7); ASU Ch 2.2, 3.3, 3.4
  Slides covered: Formal #1-13
  
  
• January 28, 2004, Lecture 3: Formal Languages-2 2-up for printing
  BNF (Backus Naur form), grammars, context-free grammars,
  derivation, parse, precedence, operator associativity,
  parse trees, ambiguity
  Reading: L Ch 4 (4.1-4.5,4.7)
  Slides covered: Formal #14-20; Formal-2 #1-17
  
  
• January 30, 2004, Lecture 4: Formal Languages-3 2-up for printing
  more on ambiguity,formal languages: Chomsky hierarchy, context-sensitive languages,
  Type 0 languages and Turing machines
  Reading: L Ch 4 (4.1-4.5,4.7)
  Slides covered: Formal-3 #1-19
  Slides corrected: Formal-3 #9-10
  
  
• February 4, 2004, Lecture 5: Functional Programming 2-up for printing
  pure fucntional programming, S-expressions, cons, car, cdr,
  defining functions, quoting arguments
  Reading: L Ch 11.1-11.3
  Slides covered: FunPgmg #1-12
  
  
• February 6, 2004, Lecture 6: More Functional Programming
  read-print-eval loop, recursive functions,
  equality testing
  Functional Programming-2 2-up for printing
  higher order functions: map; Slides covered: FunPgmg #13-21; FunPgmg-2 #1-4
  
  
• February 11, 2004, Lecture 7: Functional Programming-2 cont.
  higher order functions: map, foldr; using apply and eval; lexical scoping with let,
  Traces of versions of atomcount function
  Slides covered: FunPgmg-2 #4-14
  Slides corrected: FunPgmg-2 #3,14 (see lecture 6 for updated slides)
  
  
• February 13, 2004, Lecture 8: Functional Programming-2 cont.
  closures, curried functions
  Functional Programming-3 2 up for printing
  fold left, tail recursive functions, streams
  Supplemental Reading: Sethi, Ch 10
  Slides covered: FunPgmg-2 #14-19, FunPgmg-3 #1-10
  
  
• February 18, 2004, Lecture 9: Functional Programming-3 cont.
  Lambda calculus
  Semantics-Memory 2-up for printing
  identifiers, binding times, declarations, lexical and dynamic scope, symbol table
  Readings: L, Ch 5.1-5.5,8.4
  Slides covered: FunPgmng-3 #11-15; Semantics #1-15
  Slides changed: Semantics #7
  curried Scheme example from class
  to be discuseed in Lecture 10
  
  
• February 20, 2004, Lecture 10: Semantics-Memory, cont.
  kinds of storage: stack, heap, lifetimes
  Semantics-Memory-2 2-up for printing
  Scoping, run-time stack, lexical scope, dynamic scope
  Slides covered: Semantics #15-23, Semantics2 #1-19,31-35.
  
  
• February 25, 2004, Lecture 11: Semantics-Memory-2, cont.
  implementations of static and dynamic scoping, display, central reference table,
  lexical scoping with recursion, procedure activation tree, closures and their bindings
  C 2-up for printing
  comparison to Java, control-flow statements, Hello World program
  Readings: L, Ch 7.1-7.4, 8.5; Sethi, pp 196-198(displays)
  Slides covered: Semantics2 #20-30, 35-41; C #1-9
  
  
• February 27, 2004, Lecture 12: C, cont
  pointers, datatypes, arrays
  C-2 2-up for printing
  examples using multiple level pointers and structs
  Slides covered: C #10-19, C-2 #1-7
  
  
• March 2, 2004, Lecture 13: C-2, cont.
  more on multiple-level pointers, casting, pointer arithmetic
  Prof Borgida's lecture C-3 (2-up for printing)
  
  
  
• March 5, 2004, MIDTERM EXAM
  
  
• March 10, 2004, Lecture 14: C-3, review
  Prof Ryder's C-3 slides (2-up for printing)
  (Note: there is overlap between these notes and Prof Borgida's;
  we will review from both of them so please print both out.)
  Semantics-Memory-3 (2-up for printing)
  Control of the heap, problems with the heap and pointers,
  environments, different storage models in PLs
  Readings: L, Ch 5.5-5.7
  Slides covered: reviewed C-2, C-3 slides; SemMem-3 #1-10
  Slides corrected: C-3 #25
  
  
• March 12, 2004, Lecture 15: Semantics-Memory-3, cont
  how the heap is managed, garbage collection, algorithms
  C-4 (2 up for printing)
  More details on C, especially as pertain to our C project
  Suggested Reference: K. Reek, Pointers on C, Addison Wesley, 1998
  Ch 6: Pointers, Ch 8: Arrays
  Slides covered:SemMem-3 #11-19; C-4 #1-9
  Slides corrected:C-4 #7
  
  
• March 24, 2004, Lecture 16: Abstract Datatypes 2 up for printing
  What is a data abstraction? Stack ADT, generics,
  object-orientation, encapsulation and code sharing, object-oriented design
  Readings: L, Ch 9.1-9.3, 10.7-10.8
  Slides covered: ADT #1-16
  Slides corrected: ADT #6,25
  
  
  
• March 26, 2004, Lecture 17: ADT, cont
  C++ 2 up for printing
  Language basics - comparison to Java, operator overloading, pointers versus references
  Stack example in C
  Stacks in C++
  Readings: L, Ch 10.1-10.5
  Slides covered: ADT#17-26, C++ #1-8
  Slides changed: C++ #6
  
  
• March 31, 2004, Lecture 18: C++, cont
  subclasses, object creation, dynamic dispatch, visibility
  C++-2 2 up for printing
  Slides covered: C++ #8-28, C++-2 #1-13
  Slides changed: C++ #9-11
  
  
• April 2, 2004, Lecture 19: C++-2, cont
  Multiple inheritance of various sorts, iterators
  fixed vector example in C++
  Slides covered: C++-2 #13-34
  
  
• April 7, 2004, Lecture 20: Parameter Passing 2 up for printing
  call by value, call by reference, call by result, call by name
  Readings: L Ch 8.1-8.3
  Slides covered: Param #1-20
  
  
• April 9, 2004, Lecture 21: Prolog 2 up for printing
  Language constructs, Horn clauses, how to compute in logic?
  comparison to logic programming, examples
  Readings: L Ch 12.1-12.5
  Slides covered: #1-22
  Slides changed: Prolog #14,16,19
  
  
• April 14, 2004, Lecture 22: Prolog-2 2 up for printing
  Lists in Prolog, Recursive functions on lists (e.g., member_of),
  Prolog search trees, Tracing execution
  Slides covered: Prolog #23-25; Prolog-2 #1-21
  
  
• April 16, 2004, Lecture 23: Prolog-3 2 up for printing
  Functions on lists (e.g., append), N-Queens as example of generate and test,
  nqueens.pl
  Slides covered: Prolog-3 #1-14;
  
  
• April 21, 2004, Lecture 24: Prolog-3
  Unification revisited, an example of safe invertabiliy
  with the 'is' predicate; add.pl, more on nqueens.pl
  Download these notes again; they changed as of April 22nd 11:15am.
  Types 2 up for printing
  What is a type?
  Readings: L Ch 6
  Slides covered: Prolog-3 #15-20; Types #1-4
  
  
• April 23, 2004, Lecture 25 (DOUBLE PERIOD): Types, cont Type system, Type checking,
  Type safety, Type conversion, Primitive types, Aggregate types: arrays
  Types-2 2up for printing
  Aggregate types: strings, structures; Enumerations, Subtyping, Type equivalence
  Slides covered: Types #1-28; Types-2 #1-9, 18-21
  Slides corrected: Types #2,22; Types-2 #6
  
  
• April 28, 2004: Lecture 27: Types, cont
  Unions, more on type equivalence, Consideration of Ref types,
  More examples
  Slides covered:
  
  
• April 30, 2004: Lecture cancelled (makeup lecture was April 23rd)
  
  
• May 10, 2004: FINAL EXAM