Non-Procedural Programming (NPRG005), Summer 2024

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 Monday from 9:00 – 10:30 in room S4.

• There are two tutorial sessions:

  • every Wednesday from 10:40 – 12:10 in room S11 (teacher: Adam Dingle)

  • every Wednesday from 12:10 – 13:40 in room SW1 (teacher: Tomáš Bílý)

• Adam Dingle will hold office hours every Friday from 13:00 - 14:00 in room S10.

requirements

To successfully complete this class, you must:

1. 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. Any points that you earn over 90% (up to a maximum of 10%) will be applied as bonus points to your exam score.

2. 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 5th. A first working version of your project is due by Sunday, June 9th. The final version of your project is due by Sunday, June 16th.

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

4. 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, 2024)

• 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

• Haskell Library Quick Reference

• Glasgow Haskell Compiler

syllabus

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

Feb 19 (notes) (exercises)

Course overview. Introduction to Prolog. Atoms. Equality. Conjunction and disjunction. Predicates. Facts. Rules. Recursive rules.

Feb 26 (notes) (exercises)

Declarative and procedural interpretations of Prolog programs. Anonymous variables. Integers. Old-style arithmetic: 'is'. Arithmetic expressions. Comparisons. New-style arithmetic: integer constraints. Lists. Recursive predicates on lists.

Mar 4 (notes) (exercises)

Floating-point numbers and constraints. Standard library predicates. Mode indicators. Nested lists. Combinatorial recursion. Structures. Operator syntax. Dictionaries.

Mar 11 (notes) (exercises)

Defining natural numbers and lists. Higher-order predicates: maplist, call. Accumulators. Matrices with nested lists.

Mar 18 (notes) (exercises)

Folds. Sorting. Functional data structures. Queues. Binary trees.

Mar 25 (notes) (exercises)

The cut. Negation. If / then / else. Graphs. Iterative deepening. Searching with a visited set. Breadth-first search.

Apr 1

No lecture (Easter Monday)

Apr 8 (notes) (exercises)

Introduction to Haskell. Integer and boolean operators. if/then/else. Defining functions. Type declarations. Pattern matching. Lists. Type variables. Guards.

Apr 15 (notes) (exercises)

Characters. Strings. Tuples. 'let'. 'where'. Ranges. Infinite lists. Standard type classes. Numeric type classes. Type defaulting. Type conversions. List comprehensions.

Apr 22 (notes) (exercises)

Combinatorial recursion. Maybe. 'case' expressions. Higher-order functions. Lambda expressions. Operator sections. Function composition.

Apr 29

As patterns. Curried functions. Folds. Type synonyms. Algebraic datatypes. Recursive data structures. Derived instances. Kinds. Instance declarations. Recursive value definitions. The '$' operator. Records. Searching on Hoogle.

May 6

Defining type classes. Functors. Exhaustive search. Foldables. Arrays. 'do'. Input and output. I/O actions. Files and streams.

May 13

Debugging. Modules. Packages. Random numbers. Applicative functors. Random-access lists. Sets and dictionaries.

May 20

Graph representations. Depth-first and breadth-first search. Searching in state spaces. Priority queues. Leftist heaps. Monads. Writing monads. State with monads. Parser combinators.