CISC 260: Programming Paradigms Schedule Winter 2006

The dates for each topic are approximate.  I'm often slightly ahead or behind schedule. The "overflow" days are there to allow me to catch up if necessary. If we get ahead, I'll add examples, review activities, or possibly a short new topic. The dates for assignments and quizzes are not likely to change.

We will be spending the first half of the course on Haskell and the second half on Prolog. I haven't created a detailed schedule for the Prolog topics yet, but I'll do that over Reading Week if not before. I expect that we'll cover Chapters 1-8 of the Prolog portion of the text, and possibly Chapter 9 as well.

Each topic in the schedule grid is linked to a short description of the topic, as well as the required readings, slides, examples, and suggested sample problems. I will try to have the slides posted before the lectures, but when the semester gets busy I may not manage it!

week	Monday Date	Monday	Tuesday	Thursday
1	Jan. 9	Introduction	Haskell Start-Up	Haskell Start-Up
2	Jan. 16	Haskell Start-Up	Recursion	Lists and Tuples assn1 due
3	Jan. 23	More About Lists	More About Lists	Proofs
4	Jan. 30	Proofs & review	Quiz 1	I/O assn2 due
5	Feb. 6	Algebraic Types	Algebraic Types	Generalization
6	Feb. 13	Functions as Values	Type Classes & Type Checking	Type Classes & Type Checking
READING WEEK!
7	Feb. 27	Haskell Review	Quiz 2	Lazy Programming
8	March 6	take up Quiz 2 assn3 due	Prolog Intro	Prolog Intro
9	March 13	Prolog Intro	Prolog Intro	Lists assn4 due Friday
10	March 20	Review	Quiz 3	Arithmetic
11	March 27	Cuts & Negation	Depth-First Search assn5 due	I/O
12	April 3	Tic Tac Toe	Tic Tac Toe	Tic Tac Toe assn6 due Friday

Topics, Readings and Slides:

Haskell Start-up: Basic Haskell: types, functions, and the Hugs tool. These lectures will include demonstrations of different ways to use Hugs from Windows and Linux.
Required Reading: Chapters 1-3 of the Haskell portion of the text. Chapter 1 is an overview of what to expect. Read it but don't stress out over details; they will be explained more fully later. Chapters 2 and 3 get you started using Hugs, writing simple Haskell functions, and using predefined modules.
Slides: full size    4-up
(slides updated 11 Jan: a few extra slides added at the end)
(slides updated again 12 Jan: small typo fixed on slide 11, as noted in class)
Example From Class: FirstScript.hs (updated with additional function from 12 Jan lecture)
Practice Problems:
    Page 37: 3.6, 3.7 and 3.8
    Page 41: 3.11
    Page 43: 3.12, 3.13
    Pages 45-46: 3.14, 3.17

Recursion: Haskell has no loops; you use recursion instead!
Required Reading: Chapter 4 of the Haskell portion of the text.
Slides: full size    4-up
Example From Class: Recursion.hs
Practice Problems:
    Page 64: 4.8
    Page 67: 4.13
    Page 69: 4.15
    problem 1 from last year's Assignment 1

Lists and Tuples Two ways to build more complicated data structures out of primitive values.
Required Reading: Chapter 5 of the Haskell portion of the text.
Slides: full size    4-up
(slides updated 19 Jan: change to slides 12&13)
(slides updated again 21 Jan: fixed two small typos)
Exercises From Slides: ListExamples.hs
    We didn't finish the above in class. Try the exercises from slide 21 before you peek!
Practice Problems:
    Page 76: 5.1, 5.2
    Page 79: 5.6, 5.7
    Page 82: 5.8, 5.10, 5.11
    problem 2a from last year's Assignment 1

More About Lists More about how to write Haskell functions for lists.
Required Reading: Chapter 7 of the Haskell portion of the text. We will also cover a short topic (local definitions) from Section 6.3 of the Thompson Haskell text, which is not in the custom text. A scan of this section is posted in the WebCT area.
Slides: full size    4-up
Exercises From Slides: ListExamples2.hs
    updated with functions written in class on Tuesday, 24 Jan
Practice Problems:
    Page 119: 7.2,7.3
    Page 120: 7.4,7.5 (The functions in this set are defined in the Prelude, so you'll have to "hide" them if you want to test your solutions)
    Page 125: 7.6, 7.7, 7.8, 7.13
    Page 128: 7.14, 7.15, 7.16, 7.17
    Page 132-133: 7.20, 7.24, 7.25, 7.26
    problem 2b from last year's Assignment 1
    last year's Assignment 2

Proofs How to prove properties of Haskell functions.
Required Reading: None. I'll show you in class how to do simple proofs.
Slides: full size    4-up
(slides updated 30 Jan: fixed typos on slides 16 & 18)

Practice Problems:
1. Prove the three lemmas left undone in the rev1/rev2 proof (listed on the last slide)
2. Given the recursive definitions of length and ++ given earlier in this course, prove that length (xs ++ ys) = length xs + length ys, for all finite lists xs and ys.
3. Prove sum (rev1 xs) = sum xs.
4. Prove length (rev1 xs) = length xs.
5. Try 3 and/or 4 with rev2 instead of rev1.
6. The elem function is a Prelude function which asks if an element occurs in a list. Here's a simple recursive definition of elem:

elem :: Eq a => a -> [a] -> Bool
elem _ [] = False
elem x (y:ys) = x == y || elem x ys

I/O A quick look at I/O in Haskell. I will not test you on Haskell I/O, but I want you to be able to use it in Assignment 3.
Required Reading: None.
Slides: full size    4-up
Practice Problems: None. You never have to write any I/O code in Haskell for this course!

Algebraic Types Another very powerful way to combine primitive types into more complex values. This is closest Haskell comes to Java-like classes.
Required Reading: Chapter 14 of the Haskell portion of the text, sections 1, 2, 5 and 7. We will come back to section 3 later. We will not discuss sections 4 or 6. I'm scheduling this topic out of the textbook order so that you can use algebraic types in Assignment 3.
Slides: full size    4-up
Code From Class: Algebraic.hs
Practice Problems:
    Page 248: 14.4-6
    Page 255: 14.15-18
    Page 268: 14.44-45

Generalization An introduction to higher-order functions, including some useful higher-order functions.
Required Reading: Chapter 9 of the Haskell portion of the text.
Slides: full size    4-up
Practice Problems:
    Page 159: 9.1-9.3, 9.6, 9.8
    Page 163-4: 9.11, 9.13, 9.14, 9.16
    notes about 9.13:
        unzip is pretty simple
        last is not hard if you use foldr1 instead of foldr.
        init is do-able but messy; the only way I thought of doing it involves using (list, Bool) tuples

Functions as Values More about using functions as values in Haskell.
Required Reading: Chapter 10 of the Haskell portion of the text. You can skip section 10.9.
Slides: full size    4-up
Practice Problems:
    Page 171: 10.2, 10.3
    Page 174: 10.4, 10.5, 10.9
    Page 180: 10.13

Type Classes and Type Checking Type classes are groups of related types. Type checking concerns how Haskell determines the type of a function and how it checks for type errors.
Required Reading: Chapters 12 and 13 of the Haskell portion of the text. You should read through Chapter 12, but I will not ask you to write your own type classes in Haskell; the syntax is too messy! I will summarize what you need to know about type classes in lecture.
Slides: full size    4-up
Practice Problems:
    Page 237: 13.6, 13.8
    Note: 13.8 is messy, but if you can figure it out you'll know you're able to deal with both types and curry/uncurry.
    If you're stuck, remember that you can use :type in Hugs.
    Page 240: 13.10
    Plus practice problems given in slides.

Lazy Programming Lazy Programming concerns some clever ways you can take advantage of the Haskell evaluation rules to write functions. Includes the use of infinite lists.
Required Reading: Chapter 17 of the Haskell portion of the text, skipping section 9.
Slides: full size    4-up
Example Code: lazy.hs. Contains code from the slides plus a practice problem relating to the examples in the slides. (Search for "PRACTICE PROBLEM" to find it.)
More Practice Problems:
    Page 369: 17.22. The first part of this problem was in the slides, but we didn't have time for it in class. Try it out and make sure you understand it. Then try the second part. This one's tough; I'll give hints if you get stuck.
    Page 370: 17.24.

Prolog Intro An introduction to logic programming and the Prolog language.
Required Reading: Chapters 1 and 2 of the Prolog portion of the text.
Slides: full size    4-up
(slides updated 14 March: small typos fixed and more slides added)
Full Code For Examples On Slides:
    first simple example, with two-parameter "taken" facts
    extension with three-parameter "taken" facts
    prerequisite program
    course example with structures
Practice Problems:
    To help with the problems from Chapter 1, download a copy of my version of fig1_8.pl. This is the "family" program from figure 1.8 on page 17 (with fragments shown and discussed earlier in the text). I have made a few changes to avoid SWI-Prolog errors.
    Page 8: 1.1 and 1.2. Try on paper, then check with SWI-Prolog.
    Page 13: 1.3-1.5. Add rules to your copy of figure 1.8, then think of queries to test them.
    Page 22: 1.7. I don't care if you draw diagrams exactly like the ones in the text. It's enough if you find a systematic way to trace through a query and decide if there will be any backtracking.
    Page 38: 2.3-2.5.
    Page 40: 2.6
    Page 44: 2.9. Again, I don't care about the format of your trace, but you should be able to answer the question about which case takes more work.

Lists (Prolog)
How to use lists in Prolog.
Required Reading: Sections 3.1 and 3.2 in Prolog portion of text.
Slides: full size    4-up
Code For Examples On Slides: Lists.pl
Practice Problems:
    Page 67: 3.1 and 3.2.
    Page 73-74: 3.3 - 3.6, 3.8, 3.9, 3.11

Arithmetic in Prolog
Prolog arithmetic, including the different kinds of comparison operators.
Required Reading: Sections 3.3 and 3.4 in Prolog portion of text. The section of 3.3 describing how to define your own infix operators is optional.
Slides: full size    4-up
Code For Examples On Slides: arithmetic.pl
Practice Problems:
    the total predicate described on slide 11 (hint: refer to the flatten predicate we discussed before the quiz.)
    Page 80: 3.14
    Page 85-86: 3.16 - 3.21

Cuts & Negation
Cuts: a mechanism for limiting backtracking; also helps to implement "not".
Required Reading: Chapter 5 in Prolog portion of text.
Slides: full size    4-up
Code For Examples On Slides: cuts.pl
Practice Problems:
    experiment with the "silly example" in cuts.pl: add cuts in different places, try to predict the effect, and check yourself with SWI-Prolog
    Page 123: 5.1 - 5.3
    Page 127: 5.5

Depth-First Search
Graph searching and its applications in Prolog.
Required Reading: none; material is on slides
Slides: full size    4-up
Practice Problems:two practice problems on slides

I/O
How to do I/O in Prolog.
Required Reading: none
Optional Reading: Chapter 6 in the Prolog portion of the text and/or the I/O section of the SWI-Prolog manual
Slides: full size    4-up
Practice Problems: none

Tic Tac Toe
An extended example in Prolog, then in Haskell.
Slides: full size    4-up
This is the final version of these slides now
Prolog code
Haskell code