CSCE 330 (Fall 2000): Lecture Log

August 25 (Fri), 2000 Introduction to the Course: Goals and Topics to Be Covered. Questionnaire. (Sebesta, parts of Ch.1.)

August 28 (Mon), 2000 More preliminaries: reasons to study principles of PLs, etc. (parts of ch.1 [S]).

August 30 (Wed), 2000 Quiz 1 More preliminaries: Waterfall, RUDE, and Spiral program development methodologies. The three main PL families: imperative (or procedural), functional (or applicative), and logic (or rule-based). Influence of the Von-Neumann computer architecture. (parts of ch.1 [S]).

September 1 (Fri), 2000 Quiz 2 Information hiding as a program development concept that affected PL constructs. PL design influence on architecture. Pseudo-families of PLs: Object-oriented, scripting, constraint. (parts of ch.1 [S]). HW #1 assigned, due Wed September 6: problems 1,8,10,13,14,17 Ch.1 and all review questions for Ch.2.

September 6 (Wed), 2000 (Note: Monday was Labor Day--a holiday.) Quiz 3. HW 1 collected. Answer to question on HW: semicolon as statement terminator (Pascal) vs. separator (C). Optimizability and program transformation. Syntax and semantics of PLs: intro. Denotational semantics: intro.

September 8 (Fri), 2000 Quiz 4. More on denotational semantics: expressions and assignments.

September 11 (Mon), 2000 Quiz 5. First four-minute questionnaire. More on denotational semantics: assignments and statement lists.

September 13 (Wed), 2000 Quiz 6. Summary of first four-minute questionnaire. More on denotational semantics. Notes handed out (and later placed on the web).

September 15 (Fri), 2000 Quiz 7. More on denotational semantics--completed.

September 18 (Mon), 2000 Quiz 8. Example of the denotational semantics of a complete program. HW2 assigned: complete the example. (Note: this assignment was recorded as HW3, with grades of 0 for not received and 1 for received, only.)

September 20 (Wed), 2000 Quiz 9. HW2 collected. HW3 assigned (handout): thirteen short problems in denotational semantics. (Note: This assignment was recorded as HW2, with possible maximum grade of 36.) Handout: Example of the denotational semantics of a complete program (elaboration from Ghezzi, Carlo and Mehdi Jazayeri. _Programming Language Concepts, 2nd ed. New York: John Wiley and Sons, 1987). (This is also the solution of HW2.) Final comments on denotational semantics.

September 22 (Fri), 2000 Quiz 10. HW3 collected. Lexical analysis: lexemes and tokens. Syntax. Grammars and machines. BNF.

September 25 (Mon), 2000 Quiz 11. HW4 assigned: one problem in denotational semantics: while loop (handout); also, exercises 3 and 4 on p.152 [Sebesta]. More on BNF. Parse trees. Top-down and bottom-up parsing.

September 27 (Wed), 2000 No quiz today. HW4 collected. BNF completed.

September 29 (Fri), 2000 Midterm Exam.

October 2 (Mon), 2000 No quiz today. Review of Midterm (returned). lex, with a brief introduction to Unix.

October 4 (Wed), 2000 Quiz 12. HW5 assigned: exploration of basic Unix commands and lex (handout). Other handouts: brief intro to vi, vi commands, lex preprocessor diagram. Backus video on FL and FP--first 15 minutes with discussion of some major points.

October 6 (Fri), 2000 Quiz 13. HW5 collected. Continuation of Backus tape, with discussion of some major points.

October 9 (Mon), 2000 Quiz 14. Program 1 assigned (two functions in FP); due Friday, 00/10/13. Continuation of Backus tape, with discussion of some major points (esp. I/O).

October 11 (Wed), 2000 Quiz 15. Continuation of Backus tape, with discussion of some major points (esp. I/O). Review of some primitive functions of FP. Review of main functional forms of FP: composition, construction, insert, apply to all. Example: factorial.

October 13 (Fri), 2000 Quiz 16. Program 1 collected. HW6 assigned: Exercises 2.1.1, 2.1.2, 2.2.2 [Ullman]. Exercise 2.1.1 requires use of the ML interpreter. To get into the Standard ML of New Jersey interpreter, type sml at the Unix prompt on the stones. See "ML Information" in the CSCE 330 web page (http://www.cse.sc.edu/classes/Fall00/csce330/) for places where ML interpreters for Unix and Windows can be found. Standard ML of New Jersey and Moscow ML are recommended. Basics of ML: Roughly, up to and including Section 2.3 of Ullman's book.

October 18 (Wed), 2000 No class on Monday, October 16, because of Spring break. Quiz 17. HW6 collected. HW7 assigned: Exercises 2.3.1, 2.3.2 [Ullman], due Friday, October 20. Basics of ML continued: tuples, lists.

October 20 (Fri), 2000 Quiz 18. HW7 collected. HW8 assigned: Exercises 2.4.1, 2.4.2, 2.4.3, 2.4.4, 2.4.5, 2.4.6 [Ullman]. Chapter 2 [Ullman] completed.

October 23 (Mon), 2000 Quiz 19. HW8 collected. No new homework assigned. Students were asked to read through page 65 [Ullman]. Introduction to functions in ML.

October 25 (Wed), 2000 No Quiz. Program 2 assigned: 3.1.1, 3.1.2 (a,b,d), 3.2.1 (a) [Ullman]. Recursive functions (most of 3.2 [Ullman]).

October 27 (Fri), 2000 Quiz 20. Program 2 collected. Program 3 assigned: 3.2.1 (b-f), 3.3.1 (all), 3.3.13. Patterns. More examples of recursive functions.

October 29 (Mon), 2000 Quiz 21. Program 1 returned. Program 3 will be collected on Wednesday. Local declarations: let. Fast exponentiation. Power sets.

November 1 (Wed), 2000 Quiz 22. Program 2 returned. Program 3 collected. Program 4 assigned: Exercises 3.3.9, 3.3.7. Insertion sort in ML.

November 3 (Fri), 2000 Quiz 23. Program 4 collected. Program 5 assigned: Exercises 3.3.11, 3.3.14, due Wednesday. Mergesort in ML.

November 6 (Mon), 2000 Quiz 24. Quicksort in ML. Naive reverse and reverse with accumulator (difference lists). Complexity of append and cons.

November 8 (Wed), 2000 Quiz 25. Lazy vs. eager (or strict) evaluation. ML uses eager evaluation, except when the if then else expression is used. Example: the cond function vs. if then else. Tail-recursive (iterative) functions. Example: facti(n,p) (where p is an accumulator). Curried functions (beginning): add (x,y) vs. addc x y. Partial evaluation: add3.

November 10 (Fri), 2000 Quiz 26. Program 6 assigned: 5.2.1, 5.2.2 Ullman, due Wednesday. Some howework returned. Exceptions.

November 13 (Mon), 2000 Quiz 27. Exceptions, Currying, Curried version of map.

November 15 (Wed), 2000 Quiz 28. Program 6 collected. Program 7 assigned: 5.4.5, 5.4.6, 5.4.7 [Ullman], due Monday 11/20. Program 8 assigned: 5.4.2 [Ullman], due Monday, 11/27. Curried and non-curried versions of map and reduce.

November 17 (Fri), 2000 Quiz 29. Filter, comb, ML combination (o), ML map. Hiding arguments (for function space programming, in Backus's terminology) in ML combination and ML map using let definitions.

November 20 (Mon), 2000 Second Midterm

Thanksgiving break: no classes on Wednesday and Friday.

November 27 (Mon), 2000 Second Midterm: Correction

November 30 (Wed), 2000 Association lists (as an implementation of dictionaries), (directed) graphs, depth-first search, all in ML, all based on Paulson's presentation.

December 1 (Fri), 2000 More on DFS.

December 4 (Mon), 2000 No quiz today. Corrected version of depth-first search traversal handed out. A message was sent to Paulson highlighting the error in his book's second version. The handout also contains code for topological sort, based on depth-first search traversal. Types and datatypes in ML, through the 'elt Set example (completed).

December 6 (Wed), 2000 Program 9 assigned: problems 3 and 4, p.638 [Sebesta]: extensional and intensional representations of family relations in Prolog. Logical expressions example (solution of exercise 6.28 [Ullman]. Binary search trees (overview). Introduction to Prolog: declarative sorting, extensional and intensional representations, knight's tour example, family relations example.

December 8 (Wed), 2000 Program 9 collected. Discussion of Program 9. Declarative and procedural readings of Prolog programs. Course evaluation.