CSCE 330 (Fall 2022): Lecture Log

August 18 (Thu), 2022 Syllabus, grading policy handouts (also on the web site). Textbooks. Why study principles of PLs?

August 23 (Tue), 2022 More introduction and history, using the introductory slides on the course website.

August 25 (Thu), 2022 HW1 assigned: Do the exercise at the end of Chapter 1 [L], due 2022-09-01 (Tuesday). Turn in your work (a single pdf file) using the departmental dropbox. (As always, see "Grading per assignment" link on the main course website for a brief rubric; see the entry in the departmental dropbox for sumbission details.) Keep your work to a single page. The Von Neumann computer architecture. Other computer architectures. The three major language families. Euclid's algorithm in C, Scheme, OCaml, and Prolog. Brief history of programming languages (based on an article by Brian Hayes, linked to the web site for the course) and using Eric Leveneuz's genealogy of programming language ("Computer Languages Timeline") linked to the course website in the "Some Useful Links" section. Tiobe, PYPL, and IEEE Spectrum indices of popularity of Programming Languages. Presentation based on slides (330Ch1.pptx) in the main course website,

August 30 (Tue), 2022 Q1. Review of slides on PL families (with the Haskell example added and discussed). Ch.1 [L] ("Thinking and Computation") almost completed. Some Q&A on HW1.

September 1 (Thu), 2022 HW2 assigned: exercise at the end of Ch.3 [L]. HW2 must be submitted via the departmental dropbox (https://dropbox.cse.sc.edu). One .pl file musy be provided; it must include the Prolog program and commented examples of use; one example per part of the exercise. To save the examples of use, I recommend using protocol/1 and noprotocol/0. You may check the current working directory using working_directory(CWD,CWD) and change it with working_directory(_,NEWWD). The instructor shows how to access SWI-Prolog (swipl at the Linux prompt) on the departmental Linux machines. The instructor shows how to install SWI-Prolog in Windows. Ch.2 [L] ("A Procedure for Thinking") through section 2.4.

September 6 (Tue), 2022 HW2 is due in one week. Ch.2 [L] ("A Procedure for Thinking") completed. Ch.3 [L] ("The Prolog Language") through 3.2.3.

September 8 (Thu), 2022 Ch.3 [L] completed. Negation as failure, with a sidebar on its definition in Prolog using the cut and fail. (To students: do not use cuts in your programs for this course!) Unification with examples, including the "pointer" algorithm as described by Loveland.

September 13 (Tue), 2022 HW3 assigned: exercises at the end of Ch.4 [L], due on Thursday, 2022-09-22. Discussion of the subway example (exercise at the end of ch.2 [L]) in detail with a Prolog implementation. Observations related to the subway problem in prolog: monotonicity of definite clause logic (the logic of facts and rules), impossibility of conflicts in definite clause logic KBs, soundness and completeness of forward chaining for definite clause logic. Ch.4 [L] ("Writing Prolog Programs") completed: the blocks world example. Mathematical induction. Size of a predicate. Proof of partial correctness of above/2 and left/2. Correctness by diminishing size of a predicate. Mathematical induction, with a detailed example of proof by induction. Recursive programs and induction. Induction can be used to prove that a recursive program is correct. Induction can also be used as a guide to writing Prolog programs. The base case is usually a clause. The induction step is usually a collection of one or more clauses, which are determined by case analysis. We will see that a similar technique can be used in Haskell for functional programs.

September 15 (Thu), 2022 The board was used, because the projector did not work properly. Induction with examples: sum of powers of 2 and the "above" predicate for the blocks world.

September 20 (Tue), 2022 Q2. HW4 assigned: exercises 2, 3, and 4 at the end of Ch.5[L], due on Tuesday, 2022-10-04. Recursive programs and induction. Induction can be used to prove that a recursive program is correct. Induction can also be used as a guide to writing Prolog programs. The base case is usually a clause. The induction step is usually a collection of one or more clauses, which are determined by case analysis. We will see that a similar technique can be used in Haskell for functional programs. Simple example: above/2. Complicated example: left/2 (first approach, with four clauses.) Note that the clauses for left/2 are exhaustive, but two of them are not mutually exclusive. This leads to exponential blowup, because the number of cases to be considered doubles up as size changes by one. Proof of termination using the size method. Detailed example using left/2. More efficient (linear time) left/2. Ch.5 ("Case Study: Satisfying Constraints") through section 5.1.2.

September 22 (Thu), 2022 Ch.5 [L] continued through Section 5.2. Tail-recursive vs. non-tail recursive programs, with factorial examples. Tail-recursive factorial using an accumulator.

September 27 (Tue), 2022 Naive powers of two without (non tail-recursive) and with (tail-recursive) and accumulator. Ch.5 [L] completed.

September 29 (Thu), 2022 The midterm exam will be on Thursday, October 6. (A delay is possible, partly depending on weather events.) Students are asked to read all of Ch.7 [L] before the next class (Tuesday, 2022-10-04). Ch.6 [L] ("Case Study: Interpreting Visual Scenes:): Section 6.2 only. Ch.7 [L] ("Lists in Prolog") through Example 3 in section 7.2.1.

October 4 (Tue), 2022 Q3. HW5 assigned, due 2022-10-11: Exercise 6 Ch.7 [L]. MT1 will be on Tuesday, October 11. Students are encouraged to do HW5 early, in preparation for MT1. Ch.7 [L] ("Lists in Prolog") completed.

October 6 (Thu), 2022 Q4. We go over some exercises with lists, solving problems with and without an accumulator. Interactive lecture with much Q&A.

October 11 (Tue), 2022 Midterm exam (MT1).

October 18 (Tue), 2022 HW6 is posted on the main course website. It will be assigned next class. Correction of MT1. Syntax started.

October 20 (Thu), 2022 Q5. HW6 assigned, due 2022-10-27. Syntax, continued.

October 25 (Tue), 2022 Syntax, continued; up to a description of the CLITE grammar. Good Q&A.

October 27 (Thu), 2022 Syntax, completed. Good Q&A. Axiomatic semantics, with an example.

November 1 (Tue), 2022 Q6. HW7 assigned, due 2022-11-10. Note that this requires watching a video. Denotational semantics, with an example.

November 3 (Thu), 2022 John Backus Video: "Function Level Programming and the FL Language" completed; played from start; see the entry under "Some Useful Links."

November 10 (Thu), 2022 HW8 assigned, due on Tuesday, November 15: exercises 1-5 ch.1[H]. See departmental dropbox for details. Ch.1 [L].

November 15 (Tue), 2022 HW9 assigned, due on Thursday, November 17: Exercises 3-5 Ch.2 [H] and Exercises 1-4 Ch.3 [H]; see departmental dropbox for details. Student presentation due on Monday, November 28 at 23:55; details in the "Student Presentation" area of the main course website. How to install Haskell using GHCup. Some code from ch.1 [H], including the "sequencing of actions" example using monads. Ch.2 [H]: "First steps." Ch.3 [H]: "Types and Classes."

November 17 (Thu), 2022 HW10 assigned: Exercise 8 Ch.4[H]. There will be no penalty for late HW9 submissions until the beginning of class on Tuesday, November 22. Teams for presentations set up in class; some still need to be completed. Ch.4 [H]: "Defining Functions."

November 22 (Tue), 2022 HW11 assigned: exercises 5 and 6 Ch.5[H], due on Tuesday, November 29. List comprehensions. Some examples of functions, including a couple that use higher-order functions (composition, map, const).

November 29 (Tue), 2022 (Class after Thanksgiving) Student presentations. The following seven teams present: Alex Hutton and Daniel Anderson: SQL. Sophia Riley, Vivian D'Souza, and Alex Lay-Calvert: Lua. Ana Boccanfuso, Christina Desmangles, and Dreyson Clark: R. Anavami Isa and Donovan Price: PHP. Anna Michelitch, Patrick Burroughs, and Daniel Miller: JavaScript. Aubrey Addy, Manish Chaudhary, and Danielle Higgins: Erlang. Kyler Spell and Benjamin Goodman: Perl. Thomas Lloyd and Ben Tidwell: Arduino. Brief comments on final exam.

November 29 (Tue), 2022 Second day of student presentations canceled because of projection equipment failure. Exercises on the board: a little FP, but mainly Haskell. To prepare for the exam, I suggest reviewing the following materials under "Homework, Test, and Programs" in the fall 2016 CSCE 330 main course website (https://cse.sc.edu/~mgv/csce330f16/index.html): study guide for the fall 2016 final exam (up to question 16) and the final exam from 2013.