Non-Procedural Programming (NPRG005), Summer 2021

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 practical problems.

lectures and other meetings

The lecture happens every Tuesday from 10:40 - 12:10.
The accompanying tutorial happens every Tuesday from 14:00 – 15:30.

All lectures and tutorials will occur over Zoom for at least the beginning of the semester.

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 Thursday, May 6th. A first working version of your project is due by Sunday, June 20th. The final version of your project is due by Sunday, June 27th.
Take an exam at the end of the semester.
Regularly attend the lectures and tutorials.

textbooks

Clocksin and Mellish, Programming in Prolog, Fifth Edition (Springer, 2003)
Ivan Bratko, Prolog Programming for Artificial Intelligence, Fourth Edition (Pearson, 2012)
Marcus Triska, The Power of Prolog (online, 2021)
Miran Lipovača, Learn You a Haskell for Great Good: A Beginner's Guide (No Starch Press, 2011; freely available online)
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.

To access any of the videos below, use our Zoom meeting ID and passcode (not your CAS login) as the username/password.

Mar 2 (lecture video) (tutorial video) (notes) (exercises): Course overview. Introduction to Prolog. Atoms. Facts. Conjunction and disjunction. Rules. Recursive rules. How Prolog answers questions.
Mar 9 (lecture video) (tutorial video) (notes) (exercises): Declarative and procedural meanings of programs. Primitive types: atoms, integers, floating-point numbers, strings. Lists. Unification. Nested lists. Recursive predicates on lists.
Mar 16 (lecture video) (tutorial video) (notes) (exercises): Functors and structures. Operator syntax. Arithmetic. Mode indicators. Integer and real constraints.
Mar 23 (lecture video) (tutorial video) (notes) (exercises): Accumulators. Higher-order predicates: maplist, foldl, call. Matrices with nested lists.
Mar 30 (lecture video) (tutorial video) (notes) (exercises): Searching with integer constraints. Functional data structures. Binary trees. The cut. Negation. Problems with cut and negation.
Apr 6 (lecture video) (tutorial video) (notes) (exercises): Introduction to Haskell. Integer and boolean operators. if/then/else. Defining functions. Type declarations. Pattern matching. Lists. Type variables. The Eq type class. Ranges.
Apr 13 (lecture video) (tutorial video) (notes) (exercises): Tuples. 'let'. Guards. 'where'. Standard type classes. Numeric type classes. Type conversions. List comprehensions. The undefined value.
Apr 20 (lecture video) (tutorial video) (notes) (exercises): Maybe. 'case' expressions. As patterns. Higher-order functions. Lambda expressions. Sections. Function composition. Curried functions. List functions in the standard library. Debugging.
Apr 27 (lecture video) (tutorial video) (notes) (exercises): Searching on Hoogle. Type synonyms. Folds. Datatypes. Derived instances. Recursive data structures.
May 4 (lecture video) (tutorial video) (notes) (exercises): Recursive value definitions. Records. Instance declarations. Kinds.
May 11 (lecture video) (tutorial video) (notes) (exercises): The '$' operator. Defining type classes. Functors. 'do'. Input and output. I/O actions. Files and streams.
May 18 (lecture video) (tutorial video) (notes) (exercises): Modules. Exhaustive search. Graph representations. Depth-first and breadth-first search. Searching in state spaces.
May 25 (lecture video) (tutorial video) (notes) (exercises): Amortized running times. Symmetric lists. Monads revisited. 'sequence' and 'mapM'. The Reader, Writer, and State monads.
June 1 (lecture video) (tutorial video) (notes) (exercises): Newtype declarations. Immutable arrays. Applicative functors. Monadic parsing.