Non-Procedural Programming (NPRG005), Spring 2019

Instructor: Adam Dingle

In this course we will study the logic programming and functional programming paradigms by learning the languages Prolog and Haskell. We will emphasize writing working code, and will use these languages to solve a wide variety of practical problems.

lectures and other meetings

requirements

To successfully complete this class, you must:

  1. Complete a number of programming exercises through the semester, which I will assign weekly. You will need to earn at least 70% of the possible points for these exercises.

  2. Write a program in Prolog or Haskell as a semester project. Here are some project ideas. Please send me a one-paragraph project proposal by Sunday May 5th. Send me a first working version of your project by Sunday June 16th. The final version of your project is due by Wednesday June 26th.

  3. Take an exam at the end of the semester.

textbooks

other resources

Prolog

Haskell

syllabus

This will evolve as the semester proceeds, but here is a rough plan for topics we will cover:

Feb 18 (notes) (exercises)
Introduction to Prolog. Atoms, relations, facts. Conjunction and disjunction. Rules. Recursive rules. How Prolog answers questions. (Bratko, ch. 1)
Feb 25 (notes) (exercises)
Functors and structures. Unification. Declarative and procedural meaning of programs. Lists. Arithmetic. Mode notation for predicate parameters. (Bratko, ch. 2-3)
Mar 4 (notes) (exercises)
Simple output. More list predicates. Accumulators. Higher-order predicates: call, maplist. Nested lists. Searching in a graph. (Bratko, ch. 3, 4.1, 8.5)
Mar 11 (notes) (exercises)
Operator syntax. Matrices with nested lists. foldl. Hierarchical structures. Representing arithmetic expressions. Defining lists and integers. (Bratko, ch. 3.3)
Mar 18 (notes) (exercises)
The cut. Negation. If/then/else. Problems with cut and negation. Logical purity. Testing the type of terms. Integer constraints. Searching in state spaces. (Bratko, ch. 4.2, 5, 7)
Mar 25 (exercises)
Sorting. Difference lists. Binary trees. (Bratko, ch. 8.5, 9.1-9.3)
Apr 1 (notes) (exercises)
Introduction to Haskell. The factorial function. Basic types. Arithmetic and boolean operators. Lists and tuples. Arithmetic sequences. if. Defining functions. Pattern matching. Recursion on lists. (Hutton, ch. 1-4, 6; Lipovača, ch. 1-4)
Apr 8 (notes) (exercises)
Function types. Polymorphic types. Type classes. Overloaded types. Let...in. Where. List comprehensions. Guards in comprehensions. Let in comprehensions. (Hutton, ch. 3-5; Lipovača, ch. 1-4)
Apr 15 (notes) (exercises)
Type defaulting. Guards in equations. Case expressions. As patterns. Recursively defined lists. Higher-order functions. Lambda expressions. Maps and filters. foldl, foldr. Curried functions. (Hutton, ch. 4, 7; Lipovača, ch. 3, 5)
Apr 22 (exercises)
No lecture (Easter Monday)
Apr 29 (exercises)
Operator sections. Function composition. Function application with $. Type declarations. Data declarations. Maybe. Recursive types. Trees. (Hutton, ch. 4, 7, 8; Lipovača, ch. 5, 6, 7)
May 6 (notes) (exercises)
Modules. Newtype declarations. Records. More derivable type classes. Class and instance declarations. Functional queues. Graphs. (Hutton, ch. 8; Lipovača, ch. 6, 7)
May 13 (exercises)
Kinds. More on records: pattern matching, field updates. Compiling programs. Input and output. Command-line arguments. File I/O. Random numbers. Functional deques.
May 20 (notes) (exercises)
Introduction to lambda calculus. Strict and lazy evaluation.