Non-Procedural Programming (NPRG005), Spring 2020

Instructor: Adam Dingle

In this course we will study the logic programming and functional programming paradigms 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 9:00 - 10:30 in room S11.
The accompanying tutorial happens every Tuesday from 12:20 - 13:50 in room S11.

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, May 3rd. A first working version of your project is due by Sunday June 14th. The final version of your project is due by Sunday, June 21st.
Take an exam at the end of the semester.

extra help

My office hours this semester are every Friday from 10:30 – 12:00 in room 405. Feel free to stop by if you'd like to discuss any material from this class.

textbooks

Ivan Bratko, Prolog Programming for Artificial Intelligence, Fourth Edition (Pearson, 2011)
Marcus Triska, The Power of Prolog (online, 2020)
Miran Lipovača, Learn You a Haskell for Great Good: A Beginner's Guide (No Starch Press, 2011; freely available online)
Allen and Moronuki, Haskell Programming from First Principles (Lorepub, 2020)

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 18 (notes) (exercises): Course overview. Introduction to Prolog. Atoms. Facts. Conjunction and disjunction. Rules. Recursive rules. How Prolog answers questions.
Feb 25 (notes) (exercises): Primitive types: atoms, integers, floating-point numbers, strings. Lists. Functors and structures. Terms. Unification. Recursive predicates on lists.
Mar 3 (notes) (exercises): Operator syntax. Arithmetic. Integer constraints. Real constraints. The standard library. Mode indicators.
Mar 10 (notes) (exercises): Accumulators. Higher-order predicates: maplist, foldl, call. Matrices with nested lists. Graphs. Depth-first search. Iterative deepening.
Mar 17 (notes) (exercises): Binary trees. findall. Breadth-first search. Searching in state spaces. The cut. Negation. Problems with cut and negation.
Mar 24 (notes) (exercises): Introduction to Haskell. Integer and boolean operators. Lists. Tuples. if/then/else. let. Defining functions. Type declarations. Type variables. Type classes. Pattern matching.
Mar 31 (notes) (exercises): Ranges. List comprehensions. Guards. 'where'. 'case' expressions.
Apr 7 (notes) (exercises): Higher-order functions. Curried functions. Lambda expressions.
Apr 14 (notes) (exercises): Folds. The '$' operator. Function composition. Modules. Maybe.
Apr 21 (notes) (exercises): Datatypes. Records. Derived instances. Type synonyms. Recursive data structures.
Apr 28 (notes) (exercises): Defining type classes. Functors. Kinds. Functional data structures.
May 5 (notes): Input and output. I/O actions. Files and streams.
May 12 (notes): Random values. Bytestrings. Exceptions.
May 19 (notes) (exercises): Infinite lists. Graph representations. Depth-first and breadth-first search. Combinatorial search. Searching in state spaces.