January 14 (Mon), 2008 Administrative information: textbook, syllabus, grading policy. Beginning of course questionnaire, with discussion.
January 16 (Wed), 2008 Q1. HW1 assigned, due 1-23: exercises 1.2, 1.4-1.6 textbook. More preliminaries: families of languages (imperative, functional, logic); PLs as algorithm description languages. Computer architectures. Von Neumann vs. Harvard architectures. Direct hardware or architectural support for non-von-Neumann machines: Symbolics, Lambda, PIM-1, Mago's machine. Reasons for failure of this approach.
January 18 (Fri), 2008 Overview of operational semantics. Axiomatic semantics. Loop invariants: technique and example, with a lot of Q&A.
No class on January 21 (MLK Holiday). Class for Wednesday, January 23, is canceled. It will be made up at a time to be announced.
January 25 (Fri), 2008 Q3, with discussion. Assembly language: historical definition. Expressions vs. commands. The example of Heron's formula in (register-memory) assembly language vs. a block structured language such as ML (or Triangle!). Facilities that are present in HLLs but not (or barely) in machine or assembly languages: expressions, data types, control structures, declarations, abstraction, encapsulation (or data abstraction). More preliminaries: Languages; various computer architectures. Load-store (register-register), accumulator (single-register), memory-memory, stack instruction sets. The TAM as a Harvard stack machine.
January 28 (Mon), 2008 No quiz. Commands, expressions, and declarations. Denotational semantics. Handout.
January 30 (Wed), 2008 No quiz. HW2 assigned: exercises 2.2 through 2.6, 2.8, 2.9, due Wednesday, February 6. Make up class (to make up for the Wednesday, January 24, class, which was canceled) will be on Friday, Febraury 1, at 1025, in room 2A15. Denotational semantics, completed (example, handouts).
February 1 (Fri), 2008 No quiz. Missed class of January 23 made up before regular class meeting time. Chapter 2 (Language processors, including tombstone diagrams, bootstrapping, etc.) completed.
February 4 (Mon), 2008 No quiz. Chapter 3 ([Overview of] Compilation) started. The phases of compilation: textbook flowchart and examples from [Gries, 1971], [Aho, Sethi, and Ullman, 1986], [Appel, 1998], [Grune, Bal, Jacobs, and Langendoes, 2000]. Definitions of phases are contrasted. Example of Several authors' presentation of the phases of compilation. Chomski's language hierarchy. Terminal symbols, non-terminal symbols, start symbol, production rules. The lexicon of Triangle.
February 6 (Wed), 2008 No quiz. HW2 collected. Syntax of Triangle, with emphasis on block ("let") commands, let expressions, and functions. Review of derivations in context-free grammars. Attribute grammars and decorated (abstract) syntax trees, with example.
February 8 (Fri), 2008 Q4. HW3 assigned, due Wednesday, February 13: Exercises 3.1, 3.2, 3.3, 3.5, 3.6. Brief discussion of code generation (section 3.1.3). Students are encouraged to read the "brief guide to the Triangle language processor" linked to the course web site and try out the example program.
February 11 (Mon), 2008 No quiz. Appel handout: ch. 2 on lexical analysis. Chapter 3 ([Overview of] Compilation) completed.
February 13 (Wed), 2008 No quiz. Discussion of HW2. Lexical analysis. Regular expressions.
February 15 (Fri), 2008 No quiz. HW4 assigned, due Wednesday, February 20: Exercises 4.1 and 4.2. Test will be on Wednesday, February 20. [Changed to Friday!] Appel Ch.2: deterministic finite state automata as recognizers, with several examples. Transition tables. Recognizing the longest match. NFAs. Translation of regular expressions to NFAs.
February 18 (Mon), 2008 No quiz. Test will be on Friday, February 22. NFAs. Translation of regular expressions to NFAs. JLex.
February 20 (Wed), 2008 No quiz. HW3 returned. Test will be on Friday, February 22. JLex. Extended BNF and extended REs (textbook, through p.82) Grammar transformations. Starters sets (4.2.4). Introduction to parsing.
February 22 (Fri), 2008 PR1 (due Wednesday, February 27) and PR2 (due Wednesday, February 29) assigned. Midterm 1 (MT1).
February 25 (Mon), 2008 Review of MT1. Top-down and bottom-up parsing.
February 27 (Wed), 2008 No quiz. Recursive descent parsers. LL(1) grammars and parsers. Developing an LL(1) parser for Mini-Triangle.
February 29 (Fri), 2008 No quiz. HW5 assigned: exercises 4.13-4.16, due Wednesday, March 5. PR3 assigned: exercise 4.10. Write a Java program. Design a small test case and capture the interaction in a file. Turn in a single file with the code and the example of interaction. Due Friday, March 7. AST construction. Chapter 4 completed.
March 3 (Mon), 2008 No quiz. Contextual analysis (Ch.5): preliminaries, including review of attribute grammars.
March 5 (Wed), 2008 No quiz. PR4 assigned: exercise 4.20, due Wednesday, March 19. Ch 5 continued. Visitor design pattern.
March 7 (Fri), 2008 No quiz. The Monty Hall puzzle (and an influence diagram representing it). Ch.5 completed. Several questions on assignments. PR3 due date extended to March 10 at 11:15 (am).
March 17 (Mon), 2008 No quiz. Ch 6 (Run-time organization) started: TAM architecture (appendix C), expression evaluation (6.2), data representation (6.1) started
March 19 (Wed), 2008 No quiz. HW6 assigned: exercises 5.5, 5.6, 5.7 due Wed 3/26. Presentation on Object-Oriented Programming by Mr. Jarrell Waggoner, with emphasis on how to visit an AST. Discussion.
March 21 (Fri), 2008 No quiz. Data representation, including a brief discussion of two's complement representation of integers and of the insecurity of variant records in Pascal. Static storage allocation (6.3). Stack storage allocation (6.4) started.
March 24 (Mon), 2008 No quiz. Discussion of exercises 5.5 and 5.6. Stack storage allocation (6.4) almost completed.
March 26 (Wed), 2008 No quiz. Static links. Routine protocols (6.5.1).
March 28 (Fri), 2008 No quiz. HW7 assigned, due Wednesday, April 2: exercises 6.15, 6.18, 6.24 Routine protocols. Value-return and reference parameters. Recursion. Simplesem example of the factorial problem.
March 31 (Mon), 2008 Q5. HW7 delayed to Friday. More on recursion: tail recursion. Heap and heap management begun.
April 2 (Wed), 2008 No quiz. HW7 delayed to Monday. Heap management completed.
April 4 (Fri), 2008 No quiz. Run-time organization for object-oriented languages. Chapter 6 completed.
April 7 (Mon), 2008 No quiz. Code generation (Chapter 7): Code selection, with mini-Triangle example, through p.262 (approx.) Midterm 2 will be on Friday (April 21). Old midterm is on line.
April 9 (Wed), 2008 Q6 and Q7. MT2 will be on Friday (April 11) and will be open book. Code generation (Cahpter 7): code selection completed, code generation (7.2) completed, storage allocation started (7.3).
April 11 (Fri), 2008 MT2.
April 14 (Mon), 2008 No quiz. MT2 will not count. HW8 assigned: exercise 7.6 due Monday, April 11. Storage allocation. Chapter 7 almost completed.
April 16 (Wed), 2008 No quiz. User defined procedures and functions; parameter passing. Chapter 7 (code generation) completed. Chapter 8 (Interpretation) started.
April 18 (Fri), 2008 Q8. HW9 assigned: exercise 8.1 and 8.2 due Friday, April 25 (notes: (1) you do not need to show that your Java code runs; (2) due date changed from April 23). See the triangle bugs entry---there is an update. Iterative interpretation completed. Recursive interpretation: most of the Mini_Triangle recursive interpreter done.
April 21 (Mon), 2008 No quiz. Good Q&A on undefined values in Triangle and other issues concerning the final project. Interpretation chapter completed. LISP interpreter started.
April 23 (Wed), 2008 Q9. LISP interpreter continued (using Paul Graham's reconstriction of John McCarthy's 1960 paper; see web site for links).
April 25 (Fri), 2008 No quiz. Presentation of McCarthy's eval completed. The presentation is based on the paper by Paul Graham, at www.paulgraham.com/rootsoflisp.html I also use the original paper: John McCarthy. "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I." _Communications of the ACM_, 3, 4 (April 1960), pp.184-195. Additional test cases added to "Grading policy and test cases for the term project." Students who complete the test cases (including a script of their running) will obtain some extra credit.
April 28 (Mon), 2008 Q10. Concluding lecture: programming lifecycle, efficiency (Ch. 9). Code transformation (or "code optimization") (handout). January 24 (Wed), 2007 HW1 is due on Monday, January 29. Q2, with much discussion. More on preliminaries: computer architectures. Von Neumann vs. Harvard architectures. Direct hardware or architectural support for non-von-Neumann machines: Symbolics, Lambda, PIM-1, Mago's machine. Reasons for failure of this approach.
January 26 (Fri), 2007 HW1 due date postponed to Wednesday, January 31. Assembly language: historical definition. Expressions vs. commands. The example of Heron's formula in (register-memory) assembly language vs. a block structured language such as ML (or Triangle!). Facilities that are present in HLLs but not (or barely) in machine or assembly languages: expressions, data types, control structures, declarations, abstraction, encapsulation (or data abstraction). More preliminaries: Languages; various computer architectures. Load-store (register-register), accumulator (single-register), memory-memory, stack instruction sets. The TAM as a Harvard stack machine. Binding and applied occurrences. Scope and type, with examples.
January 29 (Mon), 2007 Context-free grammars. BNF. EBNF grammar of Mini-Triangle, with examples and comments on Triangle.
January 31 (Wed), 2007 HW1 collected. Language Processors: through section 2.3. Some good questions.
February 2 (Fri), 2007 HW2 assigned: exercises 2.2-2.4. Bootstrapping, with many examples. Good questions. Chapter 2 completed.
February 5 (Mon), 2007 HW2 collected. Compilation: Chapter 3. The phases of compilation: textbook flowchart and examples from [Aho, Sethi, and Ullman, 1986], [Appel, 1998], [Grune, Bal, Jacobs, and Langendoes, 2000]. Definitions of phases are contrasted. Example of Compiler design issues. Multi-pass vs. one-pass compilers. Discussion of the operation of a one-pass compiler on a simple example. Trade-offs (speed, space, modularity, flexibility, potential for optimization). Impossibility of one-pass compilation for Java, which allows variables to be declared after they are used. The (531) Triangle compiler is multi-pass. Top-level driver of the Triangle compiler.
February 7 (Wed), 2007 HW3 assigned: exercises 3.1, 3.2, 3.3, 3.5, due Monday, February 12. Static vs. dynamic scope rules. Compilation (Ch.3) completed. Syntactic analysis: Ch.4. Tokens for mini-Triangle and their Java representation (Section 4.1.1). Regular expressions.
February 9 (Fri), 2007 HW1 returned. Chomski's hierarchy of languages, grammars, and recognizers. Appel Ch.2: regular expressions with examples of tokens, FSAs: definitions, first examples (the keyword if, Pascal identifiers).
February 12 (Mon), 2007 HW3 collected. MT1 will be on Wednesday, February 21. Appel Ch.2: deterministic finite state automata as recognizers, with several examples. Transition tables. Recognizing the longest match. NFAs. Translation of regular expressions to NFAs.
February 14 (Wed), 2007 HW2 returned. HW4 assigned: exercises 2.1, 2.3-2.5 (Appel handout); 4.1, 4.2 (textbook), due Monday, February 19. MT1 will be on Wednesday, February 21. Review of translation of REs to NFAs. Simulation of NFAs. Translation of NFAs to DFAs.
February 16 (Fri), 2007 MT1 will be on Wednesday, February 21. NFAs and DFAs completed. JLex. Extended BNF and extended REs (textbook, through p.82) Starters sets (4.2.4).
February 19 (Mon), 2007 HW3 returned. HW4 collected. MT1's date has been changed to Friday, February 23. Sample MT1 is with answers is posted on the web site. Students are encouraged to study the sample test and the two quizzes carefully. MT1 will be open-book, Students must bring their textbook, (Section 4.2 completed) Conceptual introduction to parsing. Parts of section 4.3: bottom-up and top-down parsing, using micro-English as an example. Recursive descent parsing: micro-English (started).
February 21 (Wed), 2007 Review session led by Mr. Sen Xu.
February 23 (Fri), 2007 MT1.
February 26 (Mon), 2007 MT1 returned. Recursive descent parsers.
February 28 (Wed), 2007 Parsing: Section 4.3 completed, with examples. Section 4.4 (Construction of Abstract Syntax Trees). Remainder of Ch.4 assigned.
March 2 (Fri), 2007 HW5 assigned: Exercise 4.9 due Wednesday, March 7 HW6 assigned: Exercises 4.13 through 4.16 due Wednesday, March 7 PR1 assigned: Exercise 4.20 (and, for graduate students only: 4.22, for Mini-Triangle), due Friday, March 9. Contextual Analysis (ch. 5), started.
March 5 (Mon), 2007 Contextual analysis (ch.5), through justification of visitor pattern.
March 7 (Wed), 2007 HW5 and HW6 collected. PR1 due data changed to midnight on Saturday, March 10. Contextual analysis (ch.5) completed. Run-time organization (ch.6) started.
March 9 (Fri), 2007 PR2 and PR3 assigned, due Wednesday, March 21, 2007, and Friday, March 23, 2007, respectively. Note: PR1 will be due at a later date, as explained in the following email of March 8, 2007: *******email begins*********** Dear CSCE 531 students, I have come to realize that programming assignment 1 is unsuitable as a first assignment. Please keep the work you have done on it. It will come useful later, when it is reassigned. On Friday, I will give you a new, gentler, first programming assignment. This new assignment will be due after the break. There are three submissions of the current programming assignment in the dropbox now. The students who have sent in those submissions should withdraw them, if possible, and keep their work for later submission. I apologize for the inconvenience. Best regards, *******email ends************** Run-time organization continued through stack memory management. (Static links are next.)
March 19 (Mon), 2007 Short lesson, to allow students to attend colloquium at 1400. Review of run-time organization.
March 21 (Wed), 2007 PR2 collected (35/37 placed it in dropbox by start of class!). Run-time organization: static links, routines.
March 23 (Fri), 2007 PR4 (due Wednesday, March 28) and PR5 (due Friday, March 30) assigned. Run-time organization: recursion and heap allocation.
March 26 (Mon), 2007 Heap allocation: garbage collection. Support for object-oriented programming in the heap. Ch. 6 (run-time organization) completed.
March 28 (Wed), 2007 HW5 and HW6 returned. PR4 and PR5 due date changed: Monday, April 2 for PR4, Wednesday, April 4 for PR5. Ch 7 (code generation) started, through code templates for the whole of mini-Triangle.
March 30 (Fri), 2007 HW7 assigned: exercises 7.1, 7.2, 7.3, due Friday, April 6. Code generation: code selection (7.1) completed; code generation algorithm using the visitor pattern (7.2) completed, including backpatching (7.2.3). Storage allocation started.
April 2 (Mon), 2007 Quiz 4. Storage allocation, continued.
April 4 (Wed), 2007 Quiz 5. Program 1 (PR1) reassigned, due Wednesday, April 11: see entries for March 2 and March 9. Chapter 7 (code generation) completed.
April 6 (Fri), 2007 Quiz 6. PR6 assigned, due Monday, April 16: Exercises 7.4 and 7.5 (building on exercises 7.1, 7.2, and 7.3; numbers to be verified!). HW8 assigned, due Friday, April 13: Exercise 7.6 in Ch. 7 on entity descriptors (known value and known address; unknown value and known address; etc.) in various programming languages. Reading assignment: Students are encouraged to read Paul Graham's paper on McCarthy's LISP interpreter, linked to the web site for the course. Interpretation (ch. 8): general comments, difference between iterative and recursive interpreters. Examples of iterative interpreters: the emulator for Hypo (an accumulator machine), the mini-Shell interpreter, initial part of the mini-Basic interpreter.
April 9 (Mon), 2007 Q7. The mini-Basic interpreter, in full detail.
April 11 (Wed), 2007 Q8. How to specify semantics formally: an overview of denotational semantics (handout, based on Ghezzi and Jazayeri, 2nd ed.): the denotational semantics of a simple language with integers, conditionals and pretest (while) loops. Recursive interpretation is similar to denotational semantics.
April 13 (Fri), 2007 Q9. This quiz followed a review of parameter passing, prompted by questions related to HW8. HW8 is now due at midnight. LISP interpreter: (S)-expressions, the first 2 of the 7 primitive functions: quote and atom, in great detail.
April 16 (Mon), 2007 Q10. Extension for PR6 until next class time. It is made clear that code needs to be written only for this exercise. Code that is demonstrated to compile and run (by providing adequate scaffolding for the visitor/encoder) will lead to extra credit. LISP interpreter: all primitive functions, lambda, label, and defun.
April 18 (Wed), 2007 Q11. PR6 due date extended for the extra credit part. Term project assigned. LISP interpreter: examples of functions.
April 20 (Fri), 2007 Q12. LISP interpreter: more examples of functions, beginning of the eval program.
April 23 (Mon), 2007 Q13. LISP eval almost completed.
April 25 (Wed), 2007 Q14. Term project changes and decisions: Exercise 9.12 (first option) replaces 9.9; teams of two (2) students are allowed, individual projects are allowed as well. Students are required to email the composition of each pair. LISP eval completed.
April 27 (Fri), 2007 Q15. Chapter on interpreters completed.