Declarative Programming Models

CMPU-245 Section 01
Vassar College, Fall 2018
Syllabus / Course Wiki

Welcome to our course wiki. It will be updated throughout the semester with important course information, so check here regularly.

Professor: Marc Smith
Office: SP 104.5
Office Hours: Mon/Wed 10:30am-12:00pm;
Tue/Thu 9:00-10:00am;
and by appointment
Phone: 845 437 7497
Email: mlsmith (best way to contact me!)
Time Tue/Thu 12-1:15pm
Space SP 105

Programming in Haskell, Second Edition, by Graham Hutton. Required
(available in the Bookstore and from Amazon)

Learn Prolog Now, by Patrick Blackburn, Johan Bos, and Kristina Striegnitz. (available online)

Declarative programming languages are important alternatives to the imperative languages used in most software systems. This course covers two kinds of declarative programming: functional programming and logic programming. Topics include the semantics of declarative languages, techniques for programming in declarative languages, and the use of mathematical logic as a tool for reasoning about programs.

CMPU-102 Data Structures and Algorithms
CMPU-145 Foundations of Computer Science

Declarative programming languages (e.g., Scheme, Lisp, ML, Haskell, Prolog) provide important alternatives to languages such as C, C++, Java and Python 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. Among its many other useful features, Haskell's 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. Definite clause grammars and parsing.

All programming will be done on the computers in the SP 307 or 309 Labs. Students must work on assignments individually. Any cases of inappropriate collaboration (cheating) must be reported to the Academic Panel and will be dealt with promptly (see Academic Integrity below). Any sharing of code—even if it's just pointing out something on the screen that you've written—will be considered cheating. Also, you are strictly prohibited from using any materials (e.g., problem solutions) from any prior version of this class unless they are presented during this class.

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 one midterm exam and one final exam. For each exam, you will be allowed to bring one 8.5“-by-11” sheet of paper with whatever notes you deem appropriate. No other resources of any kind (notes, books, calculators, computers, etc.) will be allowed.

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.

Haskell
In addition to the required text for this course, there are two other Haskell books available online that you may wish to refer to:

  • Real World Haskell by Bryan O'Sullivan, Don Stewart, and John Goerzen;
  • Learn You a Haskell for Great Good! by Miran Lipovača

We'll be using the GHC version of Haskell which is freely available for download at https://www.haskell.org/downloads, and is installed on the lab machines. The https://www.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 freely downloadable. Our main reference will be Learn Prolog Now, which is available online. Additional handouts and lecture notes will be provided in class.

We are a community of learners, but we must be present to help one another. You provide a unique and valuable contribution to every class. The questions you ask help everyone understand the course material. Missing class deprives the entire class of your insights and understanding. So, please notify me before any classes or labs you know you will miss. I worry about you when you're not present. More practically, part of your grade (5%) is based on participation, and you must be present to participate (visits during office hours also count toward class participation). Excessive absences tend to hurt one's overall performance in this class.

Grading for this course is based on regular programming & hand-written assignments and the two exams, as follows:

  • 50%: Programming & Hand-Written Assignments
  • 20%: Midterm Exam
  • 30%: Final Exam


The final exam is comprehensive; however, it will emphasize the second half of the course a bit more than the first half.

Please don't cheat. Read Going to the Source. Since this course is concerned with composing code, the guidelines that apply to writing in general apply equally to the writing of computer programs. Copying someone else's code without attribution amounts to plagiarism. So give proper attribution for the help you receive. Quoting from chapter X of Going to the Source, “In suspected cases of plagiarism, the instructor prepares a written statement of complaint to the Academic Panel.” Please don't put yourself or your professor in that position. When in doubt, ask me before seeking any help from another source.

Academic accommodations are available for students registered with the Office for Accessibility and Educational Opportunity (AEO). Students in need of disability (ADA/504) accommodations should schedule an appointment with me early in the semester to discuss any accommodations for this course that have been approved by the Office for Accessibility and Educational Opportunity, as indicated in your AEO accommodation letter.

Vassar College is committed to providing a safe learning environment for all students that is free of all forms of discrimination and sexual harassment, including sexual assault, relationship abuse, and stalking. If you (or someone you know) has experienced or experiences any of these incidents, know that you are not alone. Vassar College has staff members trained to support you in navigating campus life, accessing health and counseling services, providing academic and housing accommodations, helping with legal protective orders, and more.

Please be aware all Vassar faculty members are “responsible employees,” which means that if you tell me about a situation involving sexual harassment, sexual assault, relationship abuse, or stalking, I must share that information with the Title IX Coordinator. Although I have to make that notification, the Title IX office will only provide outreach by email. You will control how your case will be handled — you don’t have to read or respond to the email, and it is completely up to you whether to pursue a formal complaint. Our goal is to make sure you are aware of the range of options available to you and have access to the resources you need.

If you wish to speak to someone privately, you can contact any of the following on-campus resources:

The SAVP website (https://savp.vassar.edu) and the Title IX section of the EOAA website (https://eoaa.vassar.edu/title-ix/) have more information, as well as links to both on- and off-campus resources.

I would like to acknowledge Professor Luke Hunsberger, who developed this course at Vassar and usually teaches it. He has been generous in meeting with me and providing his course course materials to me as I teach it this semester while he is on sabbatical.