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
The lecture happens every Monday from 12:20 - 13:50
in room S4.
The accompanying lab/tutorial happens every Thursday
from 12:20 - 13:50 in room SW1 (note the change
from SW2 where it was previously scheduled).
requirements
To successfully complete this class, you must:
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.
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.
Take an exam at the end of the semester.
textbooks
Ivan Bratko, Prolog
Programming for Artificial Intelligence, Fourth Edition
(Pearson, 2011)
Graham Hutton, Programming
in Haskell, Second Edition (Cambridge, 2016)
Miran Lipovača, Learn
You a Haskell for Great Good: A Beginner's Guide (No Starch
Press, 2011; freely available online)
Greg Michaelson, An
Introduction to Functional Programming Through Lambda Calculus
(Dover, 2011)
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.