Contents

• Overview
• Technical Stuff
• Resources
• Grading
• Course Calendar

Overview:

Declarative programming languages (e.g., Scheme, Lisp, ML, Haskell, Prolog) provide important alternatives to languages such as C, C++ and Java that follow the perhaps-more-familiar imperative programming paradigm. This course explores the power and elegance of the declarative programming paradigm in depth through the programming languages 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. Haskell, like Scheme, is a functional programming language based on the Lambda Calculus, an elegant theory of computation invented by Alonzo Church in the 1930s. However, unlike Scheme, it makes extensive use of pattern matching, which encourages a new, and extremely useful way of programming. In addition, the Haskell compiler automatically infers the type of each expression, thereby enabling it to catch type errors without the programmer having to explicitly specify types for each datum. Prolog is based on inference in first-order logic, made computationally practical after important theoretical contributions in the 1960s and 1970s. A Prolog program consists of a database of facts and rules which can be used to answer queries posed by a user. 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:

The Lambda Calculus

Basic syntax, reduction rules, Church numerals, basic programming constructs, recursion.

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:

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:

55%: Programming Assignments

15%: First In-class Exam

15%: Second In-class Exam

15%: Final Exam (regularly scheduled)

Calendar: