Non-Procedural Programming (NPRG005), Summer 2023

Instructor: Adam Dingle

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

lectures and other meetings

The lecture happens every Tuesday from 9:00 – 10:30 in room S1.
The accompanying tutorial happens every Wednesday from 9:00 – 10:30 in room S1.
My office hours are every Friday from 13:00 – 14:00 in room S510.

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. Any points that you earn over 85% (up to a maximum of 15%) will be applied as bonus points to your exam score when you take the exam.
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, April 30th. A first working version of your project is due by Sunday, June 11th. The final version of your project is due by Sunday, June 18th.
Take an exam at the end of the semester.
Regularly attend the lectures and tutorials.

textbooks

Ivan Bratko, Prolog Programming for Artificial Intelligence, Fourth Edition (Pearson, 2012)
Marcus Triska, The Power of Prolog (online, 2023)
Miran Lipovača, Learn You a Haskell for Great Good: A Beginner's Guide (No Starch Press, 2011)
Richard Bird, Thinking Functionally with Haskell (Cambridge University Press, 2014)

other resources

Prolog

Prolog Library Quick Reference
SWI-Prolog (reference manual: HTML / PDF)

Haskell

syllabus

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

Feb 14 (notes) (exercises): Course overview. Introduction to Prolog. Atoms. Equality. Conjunction and disjunction. Predicates. Facts. Rules. Recursive rules.
Feb 21 (notes) (exercises): Anonymous variables. Integers. Arithmetic expressions. Comparisons. Old-style arithmetic: 'is'. Integer constraints. Lists. Recursive predicates on lists.
Feb 28 (notes) (exercises): Searching with integer constraints. Floating-point numbers. Real constraints. More list predicates. Nested lists. Functors and structures. Operator syntax. Defining integers and lists using structures.
Mar 7 (notes) (exercises): Graphs. Depth-first search. Iterative deepening. Searching in state spaces. Higher-order predicates: maplist, call. Accumulators. Matrices with nested lists.
Mar 14 (notes) (exercises): Folds. Functional data structures. Queues. Binary trees. The cut. Negation. If / then / else. Breadth-first search.
Mar 21 (notes) (exercises): Introduction to Haskell. Integer and boolean operators. if/then/else. Defining functions. Type declarations. Pattern matching. Lists. Type variables. Ranges. Guards. Infinite lists. Tuples. 'let'. 'where'.
Mar 28 (notes) (exercises): Standard type classes. Numeric type classes. Type conversions. List comprehensions. Combinatorial recursion with list comprehensions. Maybe. Type defaulting. 'case' expressions.
Apr 4 (notes) (exercises): As patterns. Higher-order functions. Folds. Lambda expressions. Operator sections. Function composition. Curried functions. List functions in the standard library. Searching on Hoogle.
Apr 11 (notes) (exercises): Type synonyms. Algebraic datatypes. Recursive data structures. More infinite lists. Recursive value definitions. Kinds.
Apr 18 (notes) (exercises): The '$' operator. Records. Instance declarations. Defining type classes. Functors. Exhaustive search.
Apr 25 (notes) (exercises): Foldables. Arrays. 'do'. Input and output. I/O actions. Files and streams.
May 2 (notes) (exercises): Debugging. Modules. Packages. Random numbers. Applicative functors. Random-access lists. Sets and dictionaries.
May 9 (notes) (exercises): Graph representations. Depth-first and breadth-first search. Searching in state spaces. Priority queues. Leftist heaps. Monads.
May 16 (notes) (exercises): Writing monads. State with monads. Parser combinators.