August 19 (Fri), 2005 Syllabus, grading policy handouts (also on the web site). Presentation of course objectives. Questionnaire, with discussion (not completed) (Ghezzi and Jazayeri, parts of Ch.1)
August 22 (Mon), 2005 HW1 assigned, due on Monday, August 29. Discussion of questionnaire. Influences on PL design. (Ghezzi and Jazayeri, parts of Ch.1, online slides)
August 24 (Wed), 2005 Programming methodologies, programming environments, data and control abstraction. (Ghezzi and Jazayeri, parts of Ch.1, online slides)
August 26 (Fri), 2005 Quiz 1. The von Neumann computer organization ("architecture") and its effect on PLs. Other architectures. Symbolics, Japanese fifth generation. Language translation: compilation, interpretation, hybrid.
August 29 (Mon), 2005 Quiz 2. HW1 collected. HW2 assigned, due on Wednesday, September 7. Genealogy of PLs. Features of three main families of PLs: imperative (or procedural or assignment-based), functional or applicative, logic or declarative. Some examples.
August 31 (Wed), 2005 Syntax and Semantics: Introduction. Lexical analysis and syntactic analysis.
September 2 (Fri), 2005 Quiz 3. BNF. Definitions and examples: sentence, sentential form, derivation, ambiguous grammar, with examples.
September 7 (Wed), 2005 Quiz 4. HW2 collected. HW3 assigned: exercise 3 ch.1, exercises 1,2 ch.2, due Sept. 14. EBNF, with examples. Dangling else problem in the original Algol 60 specifications.
September 9 (Fri), 2005 Quiz 5. Type and scope rules (static semantics), attribute grammars, with an example. Binding and binding times. Variables.
September 12 (Mon), 2005 Quiz 6. Examples of context free grammars: Pascal-S (Syntax diagrams), SML-97, Moscow ML Module systems. Declarations, expressions, and commands. Introduction to axiomatic, denotational, and operational semantics. Axiomatic semantics, up to and not including loop invariants.
September 14 (Wed), 2005 No quiz. HW3 collected. Midterm 1 will be Friday, September 16. Review of a sample midterm, posted on line. Static and dynamic scope rules. Review of HW1 and HW2 solutions.
September 16 (Fri), 2005 MT1.
September 19 (Mon), 2005 Quiz 7. HW2 returned. Axiomatic semantics: loop invariants, with an example.
September 21 (Wed), 2005 Quiz 8. HW3 returned. HW4 assigned. See hw4.ps, linked to the homework page. Detailed explanation of Q8 (on loop invariants) takes the whole period.
September 23 (Fri), 2005 MT1 returned and discussed. Quiz 9. HW4 printout handed out. Denotational semantics of a simple imperative language: up to conditionals.
September 26 (Mon), 2005 Quiz 10. Denotational semantics: review, while loops, programs. The factorial example: introduction, proof of partial correctness using axiomatic semantics.
September 28 (Wed), 2005 Quiz 11. HW4 collected. Denotational semantics: example of a program with a while loop.
September 30 (Fri), 2005 Quiz 12. HW5 collected. See hw5.ps, linked to the homework page. Introduction to operational semantics. Introduction to Simplesem. Categorization of PLs by data memory use: static, stack-based, dynamic.
October 03 (Mon), 2005 Quiz 13. C1 language, with Euclid's algorithm example. C2 language, with example.
October 05 (Wed), 2005 No quiz. Review of denotational semantics, with Q&A.
October 07 (Fri), 2005 Q14. PR1 assigned. C2' language, with example. Introduction to C3 language. Simply recursive and mutually recursive functions (examples: comb; take and skip).
October 10 (Mon), 2005 Quiz 15. HW5 collected. Operational semantics of call and return of the C3 language. Stack management of data memory.
October 12 (Wed), 2005 Q16. HW4 returned. Old Fortran program example for C2. C3 in detail.
October 17 (Mon), 2005 Q17. PR1 collected. Stepping through C3 example program (recursive factorial) in simplesem. Introduction to block structure. C4': compound statements, with example.
October 19 (Wed), 2005 No quiz. C4' and C4". Intro to dynamic features in C5: dynamic arrays.
October 21 (Fri), 2005 No quiz. HW6 assigned: exercise 22 on p.108 of [G&J], due Friday, October 28. Dynamic arrays (C5'). Pointers (C5''). The heap. Heap management, coalescing, compaction. Explicit storage deallocation. Garbace collection. The mark and sweep algorithm.
October 24 (Mon), 2005 No quiz. Dynamic typing. Parameter passing methods. Function parameters (assigned). Introduction to ML.
October 26 (Wed), 2005 Q18. HW7 assigned: 2.1.2, 2.2.2, 2.4.1, 2.4.3, 2.4.4, 2.4.5, 2.4.6 [U]. PR2 assigned: 2.1.1, 3.1.1, 3.1.2, 3.2.1 [U]. Both are due on Wednesday, November 2. Simple functions in ML.
October 28 (Fri), 2005 No quiz. HW 6 collected. More on functions in ML. Lists. Patterns. Simple recursive functions: factorial, list membership, (naive) list reversal.
October 31 (Mon), 2005 No quiz. Review of lists in ML. More functions in ML. nth. Short-circuit evaluation: orelse, andalso. Mutual recursion: and, take and skip. Non-tail recursive version of fact, tail recursive (iterative) version of fact (facti), with an accumulator. Tail-recursive version of fact does not require the pushing of one activation records on the stack for each recursive call; this is demonstrated by the different behavior of the ML run-time support for fact with a negative argument: in the case of fact, the stack keeps growing, as shown by statistics displayed by the garbage collector, while for facti an overflowed is reached almost immediately.
November 2 (Wed), 2005 Q19. HW 8 and PR2 collected. Lazy vs. eager (strict) evaluation, with if vs. cond example. Decrease and conquer exponentiation. Simulation of imperative programs by their denotational semantics: the goto program example.
November 4 (Fri), 2005 No Quiz. PR3 assigned: exercises 3.3.1, 3.3.2, 3.3.3, 3.3.8, 3.3.11, 3.4.1, 3.4.5, due November 11. PR4 assigned: exercises 5.4.5, 5.4.6, 5.4.7 [U], due November 14. Local declarations in ML (let), powerset function, minmax function as an example of exception handling and returning a tuple, insertion sort without and with comparison operator as an argument.
November 7 (Mon), 2005 No quiz. Split, merge, and mergesort. List concatenation and its efficiency. Naive reverse and fast reverse with an accumulator.
November 9 (Wed), 2005 Q20. Midterm 2 (MT2) will be on Monday, November 14. Quicksort in ML. Higher level functions: map.
November 11 (Fri), 2005 No quiz. PR3 collected. MT2's date has been changed. It will be on Wednesday, November 16. Simpler quicksort, with sketch of correctness proof. Curried version of map. Q&A in preparation of MT2.
November 14 (Mon), 2005 No quiz. PR4 collected. HW7, HW8, PR2, PR3 returned. Q&A.
November 16 (Wed), 2005 Midterm 2.
November 18 (Fri), 2005 No quiz. Haskell, including list comprehensions and lazy evaluation, with examples. LISP: beginning of presentation based on Paul Graham's paper on the history of McCarthy's original LISP interpreter.
November 21 (Mon), 2005 No quiz. Student presentation handouts distributed. Students are requested to form 3-person teams and submit by email the names of members of the team and three languages that they would be willing to present. I will choose one language for them to present. LISP completed. Introduction to Prolog.