CSCE 330 (Fall 2002): Lecture Log

August 23 (Fri), 2002 Introduction to the Course: Goals and Topics to Be Covered. Questionnaire. Why study PLs? What are PLs? (Statements of algorithms, plan to get things done.) (Ghezzi and Jazayeri, parts of Ch.1)

August 26 (Mon), 2002 Software tools, software development environments. Influences on PL design: computer architecture; programming methodologies. (G&J, Ch.1)

August 28 (Wed), 2002 Quiz 1. HW1 assigned, and due Wednesday, September 4. Programming methodologies: waterfall, RUDE, spiral, with brief examples of how they affect PL design. Computer architecture: von Neumann. The von Neumann bottleneck. Imperative (or procedural) languages and their three characteristics: variables, (destructive) assignment statement, and preference for iteration over recursion. Mention names of the three main families of PLs: imperative, functional, logic. Mention that FP and ML are functional, Prolog is logic. We will write programs in these three languages.

August 30 (Fri), 2002 Features of imperative, functional, and logic families of PLs. Very good questions, which I answer.

September 4 (Wed), 2002 HW1 collected. History.

September 6 (Fri), 2002 HW2 assigned. Families, architectures, models of computation. Information hiding, separation of concerns, divide and conquer, abstraction. Interpretation, compilation, hybrid compilation.

September 9 (Mon), 2002 Quiz 5. Syntax and semantics: introduction. Lexical vs. syntactic analysis. BNF: introductory example.

September 11 (Wed), 2002 Quiz 6. HW2 collected. HW3 assigned. BNF: definition of production rules. Derivations. Sentential forms and sentences. Examples.

September 13 (Fri), 2002 Quiz 7. More examples of BNF grammars and derivations. Q&A.

September 16 (Mon), 2002 Quiz 8. More examples of BNF grammars and derivations. Parse trees. Ambiguous grammars. Recursive descent parsing (sketch). Syntax diagrams. Niklaus Wirth's syntax diagrams for Pascal-S, in the original German.

September 18 (Wed), 2002 HW3 collected. No quiz today. Three kinds of PL statements: commands, expressions, and declarations. Static semantics (misnomer; deal with type and scope issues; BNF not appropriate). Dynamic semantics (or, just: semantics) of PLs. Three techniques: axiomatic, denotational, and operational semantics. Denotational semantics handout. State, expressions, assignment.

September 20 (Fri), 2002 Quiz 9. Denotational semantics, continued.

September 23 (Mon), 2002 Quiz 10. Denotation semantics, completed. Introduction to axiomatic semantics.

September 25 (Wed), 2002 HW3 returned. Quiz 11. Discussion of midterm. Q&A on HW3 questions. Blocks in Pascal-S. Loop invariants, with sum program example.

September 27 (Fri), 2002 Midterm 1 (MT1).

September 30 (Mon), 2002 MT1 returned. No quiz. Correction of MT1. Loop invariant example, in full detail.

October 2 (Wed), 2002 Quiz 12. HW4 assigned, due Monday, October 7: exercises 11, 13, 15, and 16 in Ch.2 of the textbook. Abstract syntax, concrete syntax, pragmatics. The concept of binding. Variables.

October 4 (Fri), 2002 No quiz. More on variables. Scope, etc.

October 7 (Mon), 2002 No quiz. Nesting trees. Potential call graphs. Run-time structure of PLs. Operational semantics. Simplesem (and Dr. Michael Hilton's Simusem). Static, stack-based, and dynamic memory management.

October 9 (Wed), 2002 Quiz 13. Simplesem instructions. Static languages: C1. Euclid's algorithm example.

October 11 (Fri), 2002 No quiz. HW5 assigned, due Monday, October 21: "Load the Simplesem version of Euclid's algorithm (in the textbook) in Simplesem and test it on several examples. Single step to understand how it works. Write a proof of termination and partial correctness of the algorithm. Be formal and brief. Turn in a document including a snapshot of Simplesem with your program loaded, as well as a well-written proof, using the departmental dropbox." Demonstration of Simplesem using laptop and projector. C2 languages: static, routines without parameters and return values.

October 14 (Mon), 2002 No class: Fall break.

October 16 (Wed), 2002 No quiz. Review of C2; separate compilation and linking: C2'. Some good Q&A. Introduction to stack-based languages: C3.

October 18 (Fri), 2002 Quiz 14. C3, up to the beginning of a detailed discussion of the factorial program example.

October 21 (Mon), 2002 No quiz. C3 completed. Block structure. C4. C4' (nested compound statements) and C4'' (nested subprograms). Nesting trees. Dynamic memory management vs. overlays for C4'.

October 23 (Wed), 2002 Quiz 15. C4' and C4'', with examples.

October 25 (Fri), 2002 Quiz 16. The frame pointer. C5': dynamic arrays, with illustration in Ada and Algol68.

October 28 (Mon), 2002 Quiz 17. Oral presentations: form handed out, with request for 3-student team formation and three preferred languages. C5'': pointers, with illustrations in C++ and Pascal, and a discussion of garbage collection.

October 28 (Mon), 2002 No quiz. Oral presentation preferences collected. Parameter passing mechanisms. Functional languages, just started.

November 1 (Fri), 2002 No quiz. Assignment of languages to teams. (See course web page for list.) Backus tape on functional programming and the FL language (about 35 minutes of it).

November 4 (Mon), 2002 No Quiz. Program 2 assigned (on FP), due Friday, November 8. Backus tape concluded. Carter Bays's handout on FP. Discussion of some features of FP.

November 6 (Wed), 2002 Quiz 18. Introduction to ML.

November 8 (Fri), 2002 Quiz 19. More ML.

November 11 (Mon), 2002 Midterm 2.

November 13 (Wed), 2002 No Quiz. HW6: exercises 2.1.2, 2.2.2, 2.4.1, 2.4.3, 2.4.4., 2.4.5 in [U98] (Ullman's book), due Monday, Nov. 18. PR3: exercises 2.1.1, 3.1.1, 3.1.2, 3.2.1(a), 3.2.1(d) [U98], due Wednesday, Nov. 20. ML: up to the end of chapter 2 in [U98].

November 15 (Fri), 2002 No Quiz. Presentation of C# (Malegos, Al-Mutairi, Hester). A little more ML, up to how do declare a simple function.

November 18 (Mon), 2002 No Quiz. Midterm 2 returned. ML: Simple recursive functions (naive reverse, member).

November 20 (Wed), 2002 PR4 assigned: 3.3.1(all), 3.3.2, 3.3.3, 3.3.8, 3.3.11, due Monday, November 25. No Quiz. ML: more recursive functions: member, comb, with a digression on dynamic programming (in the context of the number of combinations example). Presentation of LISP (McNutt, Dolinger, Gandy): two thirds.

November 22 (Fri), 2002 Quiz 20. Presentation of LISP completed. Presentation of Perl, by Gao, Rubino, and Farrell. Example of mutual recursive functions in ML: take and skip.

November 25 (Mon), 2002 Quiz 21. PR5 assigned: program 3.4.1, due 2-12-4 (Wednesday) PR4 deadline extended to tomorrow (Tuesday, 2-11-26) at 5pm, because patterns had not been explained in class. Presentation of Algol 68 by Brown, Jones, and Scarborough. Patterns; naive reverse with patterns; concatenation operator; linear time complexity of concatenation; naive reverse takes quadratic time; linear time reverse with an accumulator.

December 2 (Mon), 2002 (First class after Thanksgiving break.) PR6 assigned: family relations in Prolog. Introduction to Prolog: extensional and intensional representations; the knight's moves example.

December 4 (Wed), 2002 Presentations: Ada by Wu, Pai, and Duan; Pascal, by Martin, Smith, and Meekins; COBOL, by Marozas, Yancey, Varghese, and Kattler (begun).

December 6 (Fri), 2002 A little more Prolog, with a brief demo of SWI-Prolog under Windows. Presentations: COBOL completed; Goedel by Rodenberger, Linder, and Shaver; FORTRAN by Garcia, Pinkney, and Sumter.