Non-Procedural Programming (NPRG005), Summer 2025

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 Thursday from 9:00 – 10:30 in room S5.
There are two tutorial sessions:
- every Wednesday from 9:00 – 10:30 in room SW2 (teacher: Jan Liam Verter)
- every Thursday from 10:40 – 12:10 in room S11 (teacher: Adam Dingle)
Adam Dingle will hold office hours every Friday from 14:00 - 15:00 in room S10.

requirements

To successfully complete this class, you must:

Complete a number of programming exercises through the semester, which your tutorial teacher 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 your tutorial teacher a one-paragraph project proposal by Sunday, May 4th. A first working version of your project is due by Sunday, June 8th. The final version of your project is due by Sunday, June 15th.
Take an exam at the end of the semester.
Regularly attend the lectures and tutorials.

You may not use GPT, Copilot or other AI tools to generate code that you submit in any homework assignment or semester project in this course. Any use of such tools is considered cheating and may disqualify you from passing the class.

textbooks

Ivan Bratko, Prolog Programming for Artificial Intelligence, Fourth Edition (Pearson, 2012)
Marcus Triska, The Power of Prolog (online, 2025)
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 20 (notes) (exercises): Course overview. Introduction to Prolog. Atoms. Equality. Conjunction and disjunction. Predicates. Facts. Rules. Recursive rules.
Feb 27 (notes) (exercises): Anonymous variables. Integers. Old-style arithmetic: 'is'. Arithmetic expressions. Comparisons. New-style arithmetic: integer constraints. Searching with integer constraints. Lists. Recursive predicates on lists.
Mar 6 (notes) (exercises): Standard library predicates. Mode indicators. Pure code. Floating-point numbers and constraints. List predicates, continued. Nested lists. Combinatorial recursion. Structures. Dictionaries.
Mar 13 (notes) (exercises): Operator syntax. Defining natural numbers and lists. Higher-order predicates: maplist, call. Accumulators. Matrices with nested lists.
Mar 20 (notes) (exercises): Folds. Sorting. Functional data structures. Queues. Binary trees. The cut. Negation. If / then / else. Graphs. Iterative deepening. Searching in a state space.
Mar 27 (notes) (exercises): Introduction to Haskell. Integer and boolean operators. if/then/else. Defining functions. Type declarations. Pattern matching. Lists. Type variables. Ranges. Characters. Strings. Guards. 'let'.
Apr 3 (notes) (exercises): Tuples. 'where'. Infinite lists. Standard type classes. Numeric type classes. Type defaulting. Type conversions. List comprehensions.
Apr 10 (notes) (exercises): Maybe. 'case' expressions. Higher-order functions. Lambda expressions. Curried functions. Operator sections. Function composition.
Apr 17 (exercises): The '$' operator. As patterns. Combinatorial recursion. Folds. Type synonyms. Algebraic datatypes. Recursive data structures. Derived instances.
Apr 24: Recursive value definitions. Kinds. Instance declarations. Defining type classes. Functors.
May 1: No lecture (Labor Day)
May 8: No lecture (Victory Day)
May 15: Records. Foldables. 'do'. Input and output. I/O actions.
May 22: Files and streams. Command-line programs. Modules. Packages. Random numbers. Recursive value definitions. Dynamic programming. Arrays. Random-access lists. Sets and dictionaries. Graph representations. Depth-first and breadth-first search. Monads.