CSCE 330 (Fall 2017): Lecture Log

August 24 (Thu), 2017 HW1 assigned: Do the exercise at the end of Chapter 1 [L], due 2017-08-31 (Thursday). Turn in your work (a single pdf file) using the departmental dropbox. Try to keep your work on a single page. Please note that a copy of Chapter 1 [L] is available on the departmental dropbox; it is provided so that you can do HW1 while waiting for your textbook to arrive. Syllabus, grading policy handouts (also on the web site). Textbooks. Why study principles of PLs? The Von Neumann computer architecture. The three major language families. Euclid's algorithm in C, Scheme, and Prolog. Brief history of programming language (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. Presentation based on slides (330Ch1.pptx) in the main course website, using slides 1-6, 41-48.

August 29 (Tue), 2017 Q1. Review of slides 41-48 on PL families. Slides on history and popularity of PLs (49-85). Brief history of programming language (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. Presentation based on slides (330Ch1.pptx) in the main course website, using slides 1-6, 41-47, 48-79. Ch.1 [L] ("Thinking and Computation") almost completed. Some Q&A on HW1.

August 31 (Thu), 2017 Photo with Eric Levenez's chart on the wall will be sent to Dr. Levenez for his website compilation. Ch.1 [L] ("Thinking and Computation") completed. Emphasis on the concept of (logical) entailment. Ch.2 [L] ("A Procedure for Thinking") through section 2.3.1.

September 5 (Tue), 2017 Ch.2 [L] ("A Procedure for Thinking") completed. Ch.3 [L] started.

September 7 (Thu), 2017 HW2 assigned: exercise at the end of Ch.3 [L], due on Thursday, September 14, 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. Q2. Discussion of the subway example (exercise at the end of ch.2 [L] in detail.) Beginning of Ch3 [L] ("The Prolog Language"). The subway problem in prolog. The instructor shows how to install SWI-Prolog on a PC.

September 12 (Tue), 2017 More on 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.3 [L] ("The Prolog Language") through Section 3.2. Trace, negation, equality.

September 14 (Thu), 2017 HW2 was due today on the departmental dropbox. Ch.3 [L]: unification with examples, including the "pointer" algorithm as described by Loveland; the backchaining procedure as explained in Figure 3.12, with the family KB of Figure 3.1 and the query female(X), parent(sam,X) as an example, in detail. Ch.3 [L] completed. Ch.4 [L] ("Writing Prolog Programs") through Section 4.3.

September 19 (Tue), 2017 HW3 assigned: exercises at the end of Ch.4 [L], due on Tuesday, 2017-09-26. You are required to use the family KB in dropbox. 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. 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 cases to be considered double 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.3.

September 21 (Thu), 2017 PR3 (HW4) assigned: exercises 2,3,and 4 at the end of Ch.5[L], due on Tuesday, October 3, 2017; you do not need to explain the choice of ordering of constraints in exercise 3. Ch.5 ("Case Study: Satisfying Constraints") through section 5.3. Tail-recursive factorial, with an accumulator.

September 26 (Tue), 2017 Q3. Computing powers using an accumulator. Non-terminating tail-recursive power program runs forever but does not run our of memory; non-terminating non tail-recursive power program runs out of memory. Ch.5 ("Case Study: Satisfying Constraints") completed.

September 28 (Thu), 2017 Q4. Review and discussion of class scheduling program in Ch.5 [H]. Ch.6 [L]: Case Study: Interpreting Visual Scenes (Sections 6.1 and 6.2 in detail, with brief comments on sections 6.3 and 6.4. Ch.7 [L]: Lists in Prolog through Section 7.2,

October 3 (Tue), 2017 HW5 assigned: Exercise 6 from ch.7[L], due on Tuesday, October 10; please see instructions in dropbox. The midterm (MT) will be on Thursday, October 12. Ch.7 [L]: Lists in Prolog completed. Ch.8 [L]: "Case Study: Understanding Natural Language" through section 8.1.2. Slides on syntax through slide 7; these slides are in the Lecture Notes part of the course website, in PowerPoint format (330Syntax.pptx).

October 5 (Thu), 2017 Midterm will be on Thursday, October 12. It will be closed book and notes. Students are encouraged to review Prolog programs on the course websites for this and previous offerings of the course. Reversing a list: naive reverse, and tail-recursive reverse using an accumulator. Syntax. We used the slides on the course website up to slide 48.

October 10 (Tue), 2017 Midterm will be on Thursday, October 12. It will be closed book and notes. Review for the midterm: discussion of the Prolog programs under "Homework, Test, and Programs linked to the website for the 2016 edition of the course: at https://cse.sc.edu/~mgv/csce330f16/index.html. Syntax: slides on the course website up to slide 54. Ch.8 [L]: "Case Study: Understanding Natural Language" continued through section 8.2.2.

October 12 (Thu), 2017 Midterm exam, proctored by Mr. Nathaniel Stone, Teaching Assistant.

October 17 (Tue), 2017 HW6 on syntax assigned due on Thursday, Octover 26. See main course website for details. Review of midterm exam. Ch.8 [L]: "Case Study: Understanding Natural Language" continued through section 8.2.3.

October 24 (Tue), 2017 Ch.8 [L]: "Case Study: Understanding Natural Language" completed. First 20 minutes of John Backus Video: "Function Level Programming and the FL Language;" see the entry under "Some Useful Links."

October 26 (Thu), 2017 HW7 assigned, due on Thursday, November 2, 2017. Q5. John Backus Video: "Function Level Programming and the FL Language" completed; played from start; see the entry under "Some Useful Links."

October 31 (Tue), 2017 HW6 (parse tree) solution on the board. Discussion of Q5 (function composition and insert). Non-recursive length in FP. The Haskell section of the course website; link to the Haskell platform with ghci. Ch.1 [H]: Introduction.

November 2 (Thu), 2017 HW8 assigned, due on Thursday, November 9. Do the exercises at the end of Ch.1 [H]. ([H] stands for a reference to the second edition of Hutton's textbook on Haskell. Some of the exercise have solutions in Appendix A.1 of [H]. If you use those solutions, state so.) This is a paper-and-pencil assignment; please do not run any code. For exercise 1, give a derivation that is different from the ones in appendix A.1 [H] and use the equational reasoning format of the example on pp.5-6 [H]. HW9 assigned, due on the departmental dropbox on Tuesday, November 14 (updated from Tuesday, November 9). Do the exercises from Ch.2 [H] and exercises 3 and 4 in Ch.3 [H]. For exercise 2.4, provide two definitions of last. Use GHCi (or WinGHCi) and show a script, as follows: Please open a .docx or text (if text, please convert to pdf) file and copy and paste from the GHCi or WinGHCi session as needed; for exercise 1 in chapter 2, run only the examples that are typed at the interactive prompt (">"); for exercises 3 and 4 in chapter 3, also copy and paste from your Haskell .hs file. Solutions (boyond in appendix A.1) for the exercises from Hutton's book are easily available. Please, on your honor, do not consult them. Students are asked to install GHCi on their computers. GHCi (ghci) is available on the departmental Linux machines. Review of Ch.1 [H] with examples described on the board and coded in Haskell. Ch.2 [H] ("First Steps").

November 7 (Tue), 2017 Ch.2 [H] ("First Steps") and Ch.3 [H] ("Types and Classes") completed. Brief discussion of the Standard Haskell classes in Figure 6.1 (p.76) of the 2010 Haskell Report, which is linked to the course website in the Haskell Information section.

November 9 (Thu), 2017 Examples concerning types and classes. Ch.4 [H] ("Defining Functions") completed.

November 14 (Tue), 2017 HW10 assigned: Exercise 8 Ch.4 and Exercises 5,6, and 9 Ch.5 [H], due on Tuesday, November 21. Ch.5 [H]: List Comprehensions; the Caesar cypher example.

November 16 (Thu), 2017 Ch.6 [H]: Recursive Functions.

November 21 (Tue), 2017 HW11 assigned: Exercises 4,6,7,8 in Ch.6 [H], due on Thursday, November 30. Student presentation due on Thursday, November 30 (see change below); details in the "Student Presentation" area of the course website. Examples of recursive function development using the scheme in section 6.6[H]. Ch.7[H] ("Higher-Order Functions") through section 7.3 and most of section 7.5.

November 28 (Tue), 2017 Student presentation teams are due on Thursday, November 30. The presentation itself is due on Monday, December 4. Q6 (developing two recursive functions, in great detail). Ch.7[H] ("Higher-Order Functions") completed.

November 30 (Thu), 2017 Assignment: View the video "The Countdown Problem" by Graham Hutton, linked to the Haskell page of the course website and corresponding to chapter 9 of the textbook. Team assignments almost completed. Tail-recursive functions in Haskell: factorial with an accumulator. Higher-level function example: inner product; need to uncurry functions before composing them. Ch.8 [H]: "Declaring Types and Classes." Video: Graham Hutton on Monads, linked to the Haskell page of the course website and corresponding to section 12.3 of the textbook.

December 5 (Tue), 2017 Q7. Student presentations (eight teams: 1,3,6,7,8,13,18, and 20).

December 7 (Tue), 2017 End of course student evaluation. Student presentations (teams 2,9, and 12). End of course.