Non-Procedural Programming (NPRG005), Summer 2022

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

requirements

To successfully complete this class, you must:

  1. 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.

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

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

  4. Regularly attend the lectures and tutorials.

textbooks

other resources

Prolog

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.

Feb 16 (lecture video) (tutorial video) (exercises) (notes)
Course overview. Introduction to Prolog. Atoms. Equality. Conjunction and disjunction. Predicates. Facts. Rules. Recursive rules.
Feb 23 (lecture video) (tutorial video) (exercises) (notes)
Anonymous variables. Integers. Arithmetic expressions. Comparisons. Old-style arithmetic: 'is'. Integer constraints. Floating-point numbers. Real constraints. Lists. Recursive predicates on lists.
Mar 2 (lecture video) (tutorial video) (exercises) (notes)
More list predicates. Nested lists. Functors and structures. Operator syntax. Graphs. Iterative deepening.
Mar 9 (lecture video) (tutorial video) (exercises) (notes)
Defining integers and lists using structures. Higher-order predicates: maplist, call. Matrices with nested lists. Accumulators. Folds. Searching in state spaces.
Mar 16 (lecture video) (tutorial video) (exercises) (notes)
Functional data structures. Queues. Binary trees. The cut. Logical purity. Negation. If / then / else. More state space searching. Breadth-first search. Findall.
Mar 23 (lecture video) (tutorial video) (exercises) (Learn You a Haskell, ch. 1-4; notes)
Introduction to Haskell. Integer and boolean operators. if/then/else. Defining functions. Type declarations. Pattern matching. Lists. Type variables. Ranges. Tuples. Guards. 'let'.
Mar 30 (lecture video) (tutorial video) (exercises) (LYaH, ch. 2-4)
'where'. Standard type classes. Numeric type classes. Type conversions. List comprehensions.
Apr 6 (lecture video) (tutorial video) (exercises) (LYaH, ch. 3, 5, 6)
Maybe. 'case' expressions. As patterns. Higher-order functions. Lambda expressions. Operator sections. Function composition. Curried functions. List functions in the standard library.
Apr 13 (lecture video) (tutorial video) (exercises) (LYaH, ch. 6, 8)
Searching on Hoogle. Recursive value definitions. Type synonyms. Folds. Datatypes. Derived instances. Recursive data structures.
Apr 20 (lecture video) (tutorial video) (exercises) (LYaH, ch. 8; notes)
Records. Immutable arrays. Instance declarations. Kinds.
Apr 27 (lecture video) (tutorial video) (exercises) (LYaH, ch. 8, 9)
The '$' operator. Defining type classes. Functors. 'do'. Input and output. I/O actions. Files and streams.
May 5 (lecture video) (tutorial video) (exercises) (LYaH, ch. 7, 9)
Foldables. Higher-order functions for I/O. Modules. Packages. Random numbers.
May 11 (tutorial video - partial) (exercises) (notes)
(No lecture.) Graph representations. Depth-first and breadth-first search. Searching in state spaces.
May 18 (lecture video) (tutorial video) (exercises) (LYaH, ch. 11, 12)
Functions as functors. IO as a functor. Applicative functors. Monads.