CMPU-245-51: Declarative Programming Models

Spring 2008

This document will be updated during the course of the semester.

Instructor Luke Hunsberger
Lectures Mon/Wed, 10:30 - 11:45 a.m., OLB 105

Contents

Overview:

Declarative programming languages are an important alternative to languages (such as C, C++, and Java) that use the more familiar imperative programming paradigm. This course introduces the declarative programming paradigm in depth through the programming languages Scheme, Lisp, Haskell and Prolog. These programming languages are based on models of computation that are fundamentally different from the state-machine model underlying imperative programming languages. Scheme, Lisp and Haskell are functional programming languages based on the Lambda Calculus, an elegant theory of computation invented by Alonzo Church in the 1930s. Prolog is based on inference in first-order logic, made computationally practical after important theoretical contributions in the 1960s and 1970s. Exposure to these models will broaden your computing horizons whether or not you use these programming languages again. As you will see during the course of the semester, it is often possible to devise simple and elegant declarative solutions to problems that would otherwise result in complex and awkward imperative programs.

This course will cover the following topics:

Scheme

A functional model of computation, lists, recursion, mapping, non-destructive vs. destructive programming, functional abstraction.

The Lambda Calculus

Reduction, church numerals, basic programming constructs, recursion.

Lisp

Optional and keyword arguments, garbage collection, macros, object-oriented programming, hash tables.

Haskell

Automatic type-checking, list comprehensions, reasoning about programs, types and classes, monads, lazy evaluation.

Prolog

Inference in first-order logic, constructing knowledge bases and querying them.

Technical Stuff:

All programming will be done on the computers in the Sun Lab. Students must work on assignments individually. Any cases of inappropriate collaboration (cheating) have to be reported to the department chair, and will be dealt with promptly. Any sharing of code---even if it's just pointing out something on the screen that you've written---will be considered cheating.

The assignments play a crucial part in understanding the course material, and you are expected to do all of them. Homework for this class will be submitted electronically---in addition to turning in paper copies. Homework must be turned in on time to receive full credit. Late homework will be accepted up to two days after the due date, but will be subject to a penalty of 20% per day.

There will be two in-class exams and one final exam. All exams will be open-book, open-notes. However, no electronic devices may be used during the exams.

This course builds progressively on previously covered material. Therefore it is essential to attend all classes and keep up with the reading and the assignments.

Academic accommodations are available for students with disabilities who are registered with the Office of Disability and Support Services. Please schedule an appointment with the instructor early in the semester to discuss any accommodations for this course which have been approved by the Director of Disability and Support Services as indicated in your accommodation letter.

Resources:

SCHEME The Scheme portion of the course will be covered by in-depth lecture notes which will be provided as handouts (which will also be available on this web site). The DrScheme software is available for free at drscheme.org. In addition, DrScheme is installed on all of the lab computers.
LISP ANSI Common Lisp by Paul Graham is a required text for this course. We'll be using the ACL 7.0 version of Lisp by Franz Inc., which is accessible from the lab computers. NOTE: This software is NOT available for free download!!
HASKELL Programming in Haskell by Graham Hutton is a required text for this course. We'll be using the Hugs98 implementation of Haskell which is available for free at haskell.org/hugs. In addition, it is installed on the lab machines. There are actually two "Prelude.hs" files: one that is loaded automatically when the Hugs interpreter first starts up, and another that is imported by the first Prelude.hs file. Here they are: Prelude.hs (#1) and Prelude.hs (#2). The haskell.org site has a ton of useful links re: all things Haskell. For example, the Haskell language definition, an online tutorial and an online reference for Haskell.
PROLOG We'll be using the SWI Prolog implementation of Prolog, which is installed on the lab computers and is also available for free at swi-prolog.org. Handouts and lecture notes will be provided in class for the Prolog portion of this course.

Grading:

Grading for this course is based on regular programming assignments, two in-class exams, and a final exam, as follows:
  • 60%: Programming Assignments
  • 10%: First In-class Exam
  • 15%: Second In-class Exam
  • 15%: Final Exam (regularly scheduled)
    • The first in-class exam will cover the first third of the course; the second in-class exam will emphasize the second third of the course; and the final exam will emphasize the last third of the course.

    Calendar:

    Week Topic Reading, Code Assignment
    Jan. 23 Course overview, administrative details, introduction to Scheme and DrScheme. Introduction to Scheme and DrScheme.
    Jan. 30 DrScheme, evaluation, default rule for evaluating non-empty lists, special forms: DEFINE, QUOTE, LAMBDA, LET. Scheme For 245 - part 2 and handout-lib.scm. Asmt 1 SOLUTIONS!
    Feb. 4 More special forms: IF, COND, AND, OR
    Lists: CONS, (), FIRST (CAR), REST (CDR), NULL?, PAIR?, LIST?     		Asmt 2 SOLUTIONS!
    Feb. 11 Recursion over lists; hierarchical (i.e., nested) lists, deep recursion, LET vs. LET* vs. LETREC, using function abstraction on different kinds of recursion (numerical, flat and deep). schemeFor245-part3.txt and handout-lib2.scm Asmt 3 SOLUTIONS!!
    Feb. 18 Wrapping up Functional Abstraction in Scheme
    Starting Lambda Calculus: Beta reduction, normal form, different reduction orders, church numerals, arithmetic, booleans and conditionals.     		Lambda Calculus Handout available in hardcopy only
    Abstracting Flat Recursion (Summary)
    Feb. 25 Lambda Calculus continued: Church numerals & recursion code from feb. 25 class Asmt 4 SOLUTIONS!!
    March 3 EXAM 1 and wrap-up of Recursion in the Lambda Calculus Asmt 5 SOLUTIONS!!
    Mar. 7-23

    SPRING

    BREAK

    March 24 Introduction to Haskell dayOne.hs, dayTwo.hs, Induction on NatNums.
    Read first four chapters of Haskell textbook.
    March 31 Induction over natural numbers and lists (ctd.) Induction over Lists, Reverse & Shunt, Code from class
    Read: 10.1 - 10.3, 7.1 - 7.3, and 13.1 - 13.6 in the Haskell textbook. (Also, have a look at the Appendix. Also, chapter 6 should be an easy review of Recursion.)    		 Asmt 6 SOLUTIONS!!
    April 7 The MONADS are coming! The MONADS are coming! Hide behind rock walls! Alert the troops! monads.hs , more-fun-with-monads.hs , monads-for-state.hs Asmt 7 SOLUTIONS!!
    April 14 Lazy evaluation, computing with infinite data structures
    Introduction to Lisp: symbol-value vs. symbol-function, #', lambda, defun, defvar, defparameter, let/let* vs. flet/labels.     		Asmt. 8 SOLUTIONS!!
    April 21 EXAM 2 SOLUTIONS!!
    Recursion in the Lambda Calculus & All Things Haskell!    		 Further intro to Lisp: mapcar, do, do*, merge-sort implementation.
    Code used in class     		Asmt. 9 SOLUTIONS!
    April 28 Keyword args, Rest args, Apply/Funcall, Push/Pop, Maphash, Special Operators and Macros! Code (and info) from Apr28 Class
    Code from Apr30 Class    		 Asmt. 10 (Due Tuesday, May 13)
    May 5 LAST DAY OF CLASS: May 5