August 18 (Thu), 2016 HW1 assigned: Do the exercise at the end of Chapter 1 [L], due 2016-08-25 (Thursday). Turn in a paper. Try to keep your work on a single page. Please note that a copy of Chapter 1 [L] is available on the blackboard site for this course; 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 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-47, 48-79.
August 23 (Tue), 2016 Q1. Review of slides 41-47; after quiz, 31-32 (Von Neumann architecture). Ch.1 [L] ("Thinking and Computation") almost completed. Emphasis on the concept of (logical) entailment. Some Q&A on HW1.
August 25 (Thu), 2015 HW1 collected. Ch.1 [L] ("Thinking and Computation") completed. Ch.2 [L] ("A Procedure for Thinking") almost completed.
August 30 (Tue), 2015 HW1 returned. Ch.2 [L] ("A Procedure for Thinking") completed. Discussion of the subway example (exercise at the end of ch.2 [L] in detail.) Beginning of Ch3 [L] ("The Prolog Language"). The instructor shows how to install SWI-Prolog on a PC, how to invoke on the departmental linux machines (swipl) and where instructions for installation on a Mac are located on the course website (link in the Prolog Information section of the course website). The subway example as a Prolog program. The trace command.
September 3 (Thu), 2015 Q2. HW2 assigned: exercise at the end of Ch.3 [L], due on Thursday, September 8, 2016. Details of submission will be discussed next time. Variants of the "poodle" example from Q2. The importance of rule ordering and body element ordering. The subway example, continued. Some issues concerning entailment and the incompleteness of backchaining. Ch.3 [L] ("The Prolog Language") through Section 3.2.5.
September 6 (Tue), 2016 Discussion of HW2, with Q&A. HW2 must be submitted via the departmental dropbox (https://dropbox.cse.sc.edu). Discussion of menu-based driver, etc., as presented at https://cse.sc.edu/~ahein/330/example.html, a detailed example prepared by Aaron Hein. Ch.3 [L] completed.
September 8 (Thu), 2016 HW2 was due today on the departmental dropbox. Ch.3 [L]: unification with examples; 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.4 [L] ("Writing Prolog Programs") started: 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 they two of them are not mutually exhaustive. 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.
September 13 (Tue), 2016 HW3 assigned: exercises at the end of Ch.4 [L], due on Tuesday, 2015-09-20. Submission details will be announced next Thursday; please start working on this problem and bring questions on Thursday. How changing the order of atoms in the body of above/2 leads to an infinite loop. Using time/1 in WWI-Prolog to obtain some statistics about a query. More efficient (linear time) left/2. Ch.5 ("Case Study: Satisfying Constraints") through section 5.1.3.
September 17 (Thu), 2016 HW3 (PR2) discussed further. See dropbox for details. Q3. Ch.5 ("Case Study: Satisfying Constraints") through section 5.3.1.
September 20 (Tue), 2016 PR3 (HW4) assigned: exercises 2,3,and 4 at the end of Ch.5[L], due on Tuesday, September 27, 2016; you do not need to explain the choice of ordering of constraints in exercise 3. PR2 (HW3) collected. Ch.5 [L] ("Case Study: Satisfying Constraints") through Section 5.6[L]. Tail-recursive factorial, with an accumulator.
September 22 (Thu), 2016 Q4. Ch.5 [L] ("Case Study: Satisfying Constraints") completed. Discussion of tail recursion.
September 27 (Tue), 2016 HW5 (PR4) assigned: exercise 6 Ch.7 [L], due on Tuesday, October 4, 2015 HW3 (PR2; family) discussed. The midterm will be either on Tuesday, October 4, or Thursday, October 6. Three versions of the Fibonacci numbers program: naive, computing with pairs, tail=recursive. Time and space complexity, using the SWI-Prolog predicates time/1 and statistics/2 (e.g., statistics(local, L1), fibA(10000,F), statistics(local,L2)). Ch.6 [L]: Case Study: Interpreting Visual Scenes (Sections 6.1 and 6.2 only). Ch.7 [L]: Lists in Prolog through Section 7.1. Attendance is sparse, likely because of S.E.T. career fair.
September 29 (Thu), 2016 Midterm will be on Thursday, October 6, 2016. It will be closed book and notes. Ch.7 [L]: Lists in Prolog: all except 7.3.1.
October 4 (Tue), 2016 Midterm will be on Thursday, October 6, 2016. It will be closed book and notes. Several examples of programs on lists: length (with and without accumulator), sum (with and without accumulator), inner product (with and without accumulator). Correctness and termination proofs. Naive reverse and reverse with an accumulator. Other small programs with lists. Discussion of the problems in the midterm of fall 2012 (as posted on the website).
October 6 (Tue), 2016 Class was canceled due to inclement weather (Hurricane Matthew).
October 11 (Tue), 2016 Midterm (MT1). There will be a make-up class from 1630-1745 on Thursday, October 13; attendance is not mandatory, but the material covered in class must be studied. Here is the body of the email sent out to the class today: It was good to see a full class today for the midterm exam, despite Hurricane Matthew. I am going to teach a makeup lecture on Thursday, October 13. The class will take place in 3A31 (our usual classroom) from 1630-1745. Attendance is not required, but you will be responsible for the material covered in class; if you do not attend the lecture, you will need to study it carefully on your own. My plan is to cover Ch.8 [L] and some extra material on grammars.
October 13 (Thu), 2016 Optional make-up class on grammars from 1630-1745, open to both section 1 and section 2. Syntax. We used the slides (up to slide 54) that are under "Lecture Notes" on the course website.
October 18 (Tue), 2016 Class was canceled because of technical problems.
October 20 (Thu), 2016 MT1 returned. Brief review of syntax (see make-up class of October 13). Ch.8 [L]: "Case Study: Understanding Natural Language" through section 8.2.
October 25 (Tue), 2016 HW6 assigned, due 2016-11-01; it requires viewing John Backus's 1987 video "Function Level Programming and the FL Language." Haskell: Ch.1 [H], Ch.2 [H] through section 2.2. Students are strongly encouraged to install the Haskell platform, which includes the GHCi interactive compiler. (https://www.haskell.org/platform/windows.html has links for Windows, Mac OS X, and Linux.) The ghci interactive compiler is also installed on the departmental Linux machines.
October 27 (Thu), 2016 HW7 assigned, due on Tuesday, November 1. Do the exercises at the end of Ch.1 [H]. ([H] stands for a reference to Hutton's textbook on Haskell.) This is a paper-and-pencil assignment; please do not run any code. For exercise 2, use the equational reasoning format of the example on p.7 [H]. For exercise 2.4, provide two definitions of last. HW8 (PR5) assigned, due on the departmental dropbox on Thursday, November 3. Do the exercises from Ch.2 [H] and exercise 3 in Ch.3 [H]. 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 2 in chapter 2, run only the examples that are typed at the interactive prompt (">"); for exercise 3 in chapter 2, also copy and paste from your Haskell .hs file. Solutions 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. Ch.1 [H]: Introduction. Ch.2 [H]: First Steps, completed. Ch.3 [H]: Types and Classes, through Currying (section 3.6).
November 1 (Tue), 2016 Q6 (note: Q5 will be assigned later). HW6 and HW7 collected. Ch.3 [H]: Types and Classes completed.. Ch.4 [H]: Defining Functions, through Pattern Matching.
November 3 (Thu), 2016 HW9 (PR6) assigned, due on Thursday, November 10, 2016: exercises 1,2 Ch.4 [H]; 3,4,7 Ch.5 [H]. This assignment must be turned as a single .hs file using the departmental dropbox. The students are asked to form teams of three for presentations; the format of presentations is described elsewhere on the course website. Ch.4 [H]: Defining Functions, completed. Ch.5 [H]: List Comprehensions through section 5.4.
November 10 (Thu), 2016 HW10 (PR7) assigned, due on Thursday, November 17, 2016: exercises 3,4,5 Ch.6 [H]. HW11 (PR8) assigned, due on Tuesday, November 22, 2016: exercises 8,9 Ch.7 [H]. Q5 (note: Q6 was assigned earlier). The students are again asked to form teams of three for presentations; the format of presentations is described elsewhere on the course website. The Caesar Cypher example (Section 5.5 [H]). Chapter 6 ("Recursive Functions") completed. Mutual recursion: take and skip on lists.
November 15 (Tue), 2016 Q7. Review of homework exercises. Cube triples example, solved using list comprehensions. Chapter 7 [H] ("Higher-order Functions") through 7.3; most of 7.4 also done. The students are again asked to form teams of three for presentations; the format of presentations is described elsewhere on the course website.
November 17 (Tue), 2016 Final exam study guide handed out; students are encouraged to do the exercise, ignoring exercise 19, which uses the $ (evaluation) operator. The guide is linked to the course website under "Tests." Chapter 7 [H] ("Higher-order functions") completed, including the transmit program. Variants of fold (foldr1, foldl1, foldl). Two voting algorithms (first-past the post and instant runoff) in Haskell. Inner product (FP/FL style) in Haskell. (These programs are now available in the Haskell section of the course website.) Chapter 10 ("Declaring Types and Classes") started.
November 22 (Tue), 2016 Student presentation teams assignments completed. The final will not be cumulative; it will include syntax and Haskell. Student will be allowed one hand-written 3x5 index card. Video viewing assignment: the Countdown Problem (ch.11 [H]); link on website. The function application operator $; ($ n) as a section. Chapter 10 ("Declaring Types and Classes") completed.
November 29 (Tue), 2016 Q9. Discussion of the dangling else ambiguity. Five student presentations.
December 1 (Thu), 2016 Student presentations completed. End of course survey. An optional review session took place from 1430-1605 in 3D05.