August 20 (Thu), 2015 HW1 assigned: Do the exercise at the end of Chapter 1 [L], due 2015-08-27 (Thursday; early work will be accepted). 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. 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.
August 26 (Tue), 2015 Influences on PL design. The Von Neumann architecture. Translation: compilation, interpretation, interpretive compilation. Euclid's algorithm in C, Scheme, and Prolog, just begun.
August 28 (Thu), 2015 Q1. HW1 collected. Euclid's algorithm in C, Scheme, and Prolog. Ch.1 [L] ("Thinking and Computation") completed.
September 1 (Tue), 2015 Q2. HW1 returned. HW2 assigned: exercise at the end of Ch.3 [L], due on Thursday, September 10. Ch.2 [L] ("A Procedure for Thinking").
September 3 (Thu), 2015 Beginning of Ch.3 [L] ("The Prolog Language") through Section 3.2.3. The instructor installs the latest version of SWI-Prolog for Windows (32-bit; 7.2.3) on his laptop.
September 8 (Tue), 2015 Q3. Prolog (swipl) now available on the departmental Linux machines. Ch.3 [L] completed.
September 10 (Thu), 2015 HW2 (PR1) collected. HW3 assigned: exercises at the end of Ch.4 [L], due on Tuesday, 2015-09-22. SWI-Prolog on the Linux machines demonstrated: swipl at the Linux prompt. Brief demonstration of the SWISH browser-based SWI-Prolog interpreter (http://swish.swi-prolog.org/). This is an interpreter with limited functionality and under development. It should be used as a last resort. Review of Q3: logical entailment and incompleteness of back-chaining on Prolog knowledge bases. Ch.4 [L] ("Writing Prolog Programs") started: the blocks world example.
September 15 (Tue), 2015 Ch.4 [L] continued and completed. 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. More efficient (linear time) left/2.
September 17 (Thu), 2015 HW2 returned. Ch.5 ("Case Study: Satisfying Constraints") through almost all of section 5.3.1.
September 22 (Tue), 2015 PR3 (HW4) assigned: exercises 2,3,and 4 at the end of Ch.5[L], due on Tuesday, September 29, 2015; 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") almost completed.
September 24 (Thu), 2015 Ch.5 [L] ("Case Study: Satisfying Constraints") completed. Ch.6 [L] ("Case Study: Interpreting Visual Scenes") completed; only sections 6.1 and 6.2 are covered in this course. Ch.7 [L] ("Lists in Prolog") started.
September 29 (Tue), 2015 HW5 (PR4) assigned: exercise 6 Ch.7 [L], due on Tuesday, October 6, 2015; on an exceptional basis, late submissions will not be accepted. HW4 (PR3) collected. The midterm will be either on Tuesday, October 6, or Thursday, October 8. Ch.7 [L]: Lists in Prolog.
October 1 (Thu), 2015 Midterm will be on Thursday, October 8. HW3 (PR2) retrurned. Reminder: Late submissions of HW5 (PR4) will not be accepted. Ch.7 [L] completed. Ch.8 [L]: Case Study: Understanding Natural Language, up to most of 8.2.3 (Writing a parser).
October 13 (Tue), 2015 Classes of October 6 and 8 were canceled due to inclement weather. HW5 (PR4) collected and discussed in class. Midterm will be on Thursday, October 15. Emails with information about the test were sent out. Ch.8 [L]: Case Study: Understanding Natural Language almost completed. Naive reverse and reverse with an accumulator.
October 15 (Thu), 2015 Midterm (MT1).
October 20 (Tue), 2015 Midterm post-mortem. Detailed discussion of factorial computation in Prolog, with a simple non tail recursive solution and a tail recursive solution using an accumulator. Detailed discussion of delete/3: version that deletes only one instance of Element; version that deletes all; SWI-Prolog version (p.405 manual for 7.2.3); notation for predicate arguments (p.73 manual), with special discussion of the meaning of + in +List1, @ in @Element, and - in -List2. First 20 minutes of John Backus Video: "Function Level Programming and the FL Language"; see the entry under "Some Useful Links."
October 27 (Tue), 2015 John Backus Video: "Function Level Programming and the FL Language" completed; played from start because of many absences last week; see the entry under "Some Useful Links."
October 29 (Thu), 2015 Q6. HW6 assigned: Exercises 1-4 Ch.1 [H], due on Tuesday, November 5, 2015. HW7 (PR5) assigned: Exercises 1-5 Ch.2 [H], due on Tuesday, November 5, 2015; for exercise 2.4, provide two definitions of last. Solutions for the exercises from Hutton's book are easily available. Please, on your honor, do not consult them. Students are asked to install Hugs on their computers. Ghci (ghci) is available on the departmental Linux machines. Ch.1 [H]: Introduction. Ch.2 [H]: First Steps, section 2.1 only; first use of Hugs.
November 3 (Thu), 2015 Ch.2 [H]: First Steps, completed. Ch.3 [H]: Types and Classes, through Currying (section 3.6).
November 5 (Thu), 2015 HW8 (PR6) assigned: Exercises 1-3 at the end of Ch.3[H], due November 12, 2015. HW6 and HW7 (PR5) collected. Discussion of quicksort program in Haskell. Ch.3 [H]: Types and Classes, completed. Ch.4 [H]: Defining Functions, through most of section 4.4 (Pattern Matching).
November 10 (Tue), 2015 HW9 (PR7) assigned: Exercises 1 and 2 Ch.4 [H], due November 17, 2015. HW10 (PR8) assigned: Exercises 3, 4, and 7 Ch.5 [H], due November 17, 2015. (Even though these two assignments are due on the same day, please turn in two separate papers. Presentations discussed. Details are on the "Student Presentation" page of the course website. Students are welcome to look for team mates. Teams will be assigned next class if teams are not formed spontaneously. Presentation deliverables are due on November 24 (before Thanksgiving) on the departmental dropbox, dropbox.cse.sc.edu; actual presentations will be on December 1 and December 3. Ch.4 [H] (Defining Functions) completed. Discussion of foldr and how it differs from insert (!) in Backus's FP. Ch.5 [H] (List Comprehensions) completed.
November 12 (Thu), 2015 HW11 (PR9) assigned: Exercises 1-6 (all exercises) Ch.6 [H], due November 19, 2015. The Caesar Cypher example (Section 5.5 [H]). Chapter 6 ("Recursive Functions") completed.
November 17 (Tue), 2015 HW12 (PR10) assigned: exercises 8-9 Ch.7 [H], due November 24, 2015. HW9 and HW10 collected. Students are strongly encouraged to set up teams of three students for the required presentations. Details are elsewhere on the course website. Mutual recursion: take and skip on lists. Chapter 7 ("Higher Order Functions") completed. Example of scalar (inner) product written in the higher-order function style, in FP and in Haskell.
November 19 (Thu), 2015 HW13 (PR11) assigned: view Graham Hutton's lecture on Ch.11 of his textbook, which is linked to the course website (under "reference materials"); download the countdown program; do exercise 1 Ch.11 [H] (Hint: "choices" are permutations of subsets.); do the first part of exercise 4 Ch.11 [H] (Hint: use a list comprehension to generate the number of expressions; this will run for a few minutes.); due on Tuesday, December 1. Q6. HW11 (PR9) collected. The string transmitter example from Ch.7[H]. Ch.8 [H] ("Functional Parsers") started.
November 24 (Tue), 2015 HW12 (PR10) collected. HW9 and HW10 returned. Ch.8 [H] ("Functional Parsers") completed. Ch.10[H] ("Types and Classes") completed.
December 1 (Tue), 2015 HW13 (PR11) collected. HW12 (PR10) returned. Student presentations on the following languages: Julia, Python, Groovy, LOLCODE, Go, Perl, Swift, Lua (1), Bash.
December 1 (Tue), 2015 Final exam will be from 1230-1500 on Thursday, December 10, 2015, in the classroom (SWGR 2A31). This is the regularly scheduled time for courses taught from 1315-1430 on Tuesdays and Thursdays. The final exam will be closed book. No notes, calculators, computing devices, and communication devices will be allowed. HW13 returned. Student presentations on the following languages: Lua (2), Bash, Ruby, Pascal, Spin, ASP (Answer Set Programming), Dart, Forth. Student end of course evaluation. End of course.