Advanced Programming

Welcome to the webpage for the Advanced Programming module at Aarhus University.

This course is taught by Magnus Madsen (magnusm@cs.au.dk).

The course currently consists of one module: Logic Programming which is taught as part of the Advanced Topics in Programming Languages course.

All material in this course is freely available under the Apache 2.0 license.

You can edit this course! The source for the book and slides are available on GitHub!

Thanks to everyone who has helped improve the material:

Formalities

This module is taught as part of the Advanced Topics in Programming Language course.

See that course description for details.

Lecturer

LecturerEmailOfficeOffice Hours
Magnus Madsenmagnusm@cs.au.dkTuring-215TBD

Syllabus

Week 1: Introduction to Logic Programming and Datalog

Week 2: Programming with Datalog in Flix

Week 3: Programming with Prolog

Paper Presentation

In addition, all presented papers are part of the syllabus!

Logic Programming

Week 1 (Reading | Slides | Exercises)

Reading

Slides

Download Slides

Exercises

Exercise 01.00: Follow the Get Started with Flix tutorial.

Exercise 01.01: Given the Datalog program:

Father(child, dad) :- Parent(child, dad), Male(dad).
Mother(child, mum) :- Parent(child, mum), Female(mum).
  • (a) Describe, in your own words, what the program computes.
  • (b) Add some Parent, Male, and Female facts to the program.
  • (c) Extend the program to compute brothers and sisters.
  • (d) Extend the program to compute uncles and aunts.

Hint: You may use your own family tree or The Simpsons family tree.

Hint: The Brother and Sister relations should have two arguments.

Exercise 01.02: Describe the difference between the two Datalog programs:

Happy(person) :- Rich(person), Famous(person).

and

Happy(person) :- Rich(person).
Happy(person) :- Famous(person).

Exercise 01.03: Identify the syntactic categories of the Datalog program:

Rich("Tom Hanks").
Famous("Tom Hanks").
Happy(person) :- Rich(person), Famous(person).

Hint: The syntactic categories are programs, constraints, facts, rules, head/body atoms, predicate symbols, terms, variables, and constants. Here is a template to get you started:

  • "Tom Hanks" is a ... which is a ...
  • Rich is a ...
  • Rich("Tom Hanks") is a ...
  • Rich("Tom Hanks"). is a ... which is a ...
  • ...

Exercise 01.04: Given the following facts about roads, bridges, and flights:

Road("Aarhus", "Vejle").
Road("Aarhus", "Aalborg").
Road("Aalborg", "Skagen").
Road("Billund", "Vejle").
Road("Odense", "Vejle").
Road("Odense", "Nyborg").
Road("Helsingør", "København").
Road("Helsingborg", "Malmø").
Road("Korsør", "Nyborg").
Road("Korsør", "Roskilde").
Road("København", "Roskilde").
Road("Rønne", "Nexø").

Bridge("Storebælt", "Korsør", "Nyborg").
Bridge("Øresund", "København", "Malmø").
Bridge("Nivå", "Helsingborg", "Helsingør").

Flight("Aalborg", "København").
Flight("Aarhus", "København").
Flight("Billund", "København").
Flight("København", "Rønne").

Assume all roads, bridges, and flights are bi-directional. For example, if there is a flight from Aalborg to København then there is also a flight from København to Aalborg.

  • (a) Compute a relation Drivable(src, dst) which captures every city where one can drive from src and reach dst using only roads (i.e. without using bridges or taking flights).
  • (b) Use Drivable to determine every city one can drive to from Odense.
  • (c) Compute a relation DrivableWithBridges(src, dst) which allows using roads and bridges.
  • (d) Use DrivableWithBridges to compute every city one can drive to from Skagen.
  • (e) Compute a relation Reachable(src, dst) which captures every city which one can reach by driving (via roads and bridges) and then taking a flight. But importantly, after taking a flight, one cannot drive further (since a car will not fit in the overhead bin).
  • (f) Use Reachable to determine if it is possible to travel from Nexø to Aalborg? And what about the other direction, from Aalborg to Nexø?

Hint: Lillebælt is beneath our notice.

Hint: You must ensure that roads, bridges, and flights are bi-directional.

Exercise 01.05: For each constraint, determine whether it is ground:

Father("Luke Skywalker", "Darth Vader").
Fruit("Apple", color).
Fruit("Apple", "Red").
Tasty(food) :- Flavor(food, "sweet").

Exercise 01.06: For each constraint, determine whether it is safe or unsafe:

Vegetable("Potato", color).
Sage(person) :- Wise(person), Old(person).
Imperium(person) :- Consul(person, year).
Manager(boss, employee) :- Worker(employee).

Exercise 01.07: Given the Datalog program:

Fruit("Apple", "Green").
Fruit("Banana", "Yellow").
Fruit("Strawberry", "Red").
Vegetable("Tomato", "Red").

What is its Herbrand Universe and the Herbrand Base?

Hint: The Herbrand Base will be large. You may want to write them up in a table.

Note: You do not have to submit the complete table. An excerpt is sufficient.

Exercise 01.08: Given the Datalog program:

Loves("Rose", "Jack").
Loves("Jack", "Rose").
Loves("Caledon", "Rose").
Happy(x) :- Loves(x, y), Loves(y, x).

What are all the possible the interpretations?

Hint: There are many. You may want to write them up in a table.

Note: You do not have to submit the complete table. An excerpt is sufficient.

Exercise 01.09: Given the Datalog program above with the interpretation:

I = { Loves("Rose", "Jack"), Loves("Caledon", "Caledon"), Happy("Rose") }

which of the following ground atoms and ground rules are true under the interpretation:

Happy("Rose")?
Happy("Jack")?
Happy("Caledon")?
Loves("Rose", "Jack")?
Loves("Jack", "Caledon")?
Happy("Rose") :- Loves("Rose", "Jack"), Loves("Jack", "Rose")?
Happy("Jack") :- Loves("Rose", "Jack"), Loves("Caledon", "Caledon")?
Happy("Caledon") :- Loves("Caledon", "Caledon"), Loves("Caledon", "Caledon")?

Exercise 01.10: Given the Datalog program above which of these interpretations are models?

I1 = { Loves("Rose", "Jack") }

I2 = { Loves("Rose", "Jack"), Loves("Jack", "Rose"), Loves("Caledon", "Rose") }

I3 = { Loves("Rose", "Jack"), Loves("Jack", "Rose"), Loves("Caledon", "Rose"),
       Happy("Rose")}

I4 = { Loves("Rose", "Jack"), Loves("Jack", "Rose"), Loves("Caledon", "Rose"),
       Happy("Rose"), Happy("Jack") }

I5 = { Loves("Rose", "Jack"), Loves("Jack", "Rose"), Loves("Caledon", "Rose"),
       Happy("Rose"), Happy("Jack"), Happy("Caledon") }

and which model is minimal?

Exercise 01.11: Given the Datalog program:

God("Odin").
Son("Odin", "Thor").
Son("Odin", "Baldr").
Son("Thor", "Mothi").
Son("Thor", "Magni").
DemiGod(x) :- Son(y, x), God(y).
Mortal(x) :- Son(y, x), DemiGod(y).
  • Compute its minimal model using the immediate consequence operator Tp.
  • Show the facts inferred in each iteration.

Exercise 01.12: It is said that all roads lead to Rome. But what about roads on islands?

Given the following road facts (which should again be understood as bi-directional):

Road("Brundisium", "Capua").
Road("Brundisium", "Tarentum").
Road("Capua", "Tarentum").
Road("Capua", "Rome").
Road("Genua", "Massilia").
Road("Genua", "Pisae").
Road("Genua", "Parma").
Road("Messana", "Syracuse").
Road("Ostia", "Rome").
Road("Parma", "Ravenna").
Road("Pisae", "Ravenna").
Road("Pisae", "Rome").

Compute all pairs of cities (s, t) which are connected by a road that passes through Rome.

Hint: If your solution includes Messana or Syracuse it is wrong!

Exercise 01.13: Given the following facts about compilers and interpreters:

/// Available hardware.
Machine("x86").
Machine("x64").

// Available interpreters (JITs).
Interpreter("JavaScript", "C++").  // A JavaScript interpreter written in C++.
Interpreter("JVM", "C++").
Interpreter("WASM", "C++").

// Modern compilers.
Compiler("C", "x86", "C").
Compiler("C", "x64", "C").
Compiler("C++", "x86", "C").       // A compiler from C++ to x86 written in C.
Compiler("C++", "x64", "C").
Compiler("Flix", "JVM", "Scala").
Compiler("Java", "JVM", "Java").
Compiler("Rust", "x64", "Rust").
Compiler("Rust", "x86", "Rust").
Compiler("Rust", "WASM", "Rust").
Compiler("Scala", "JVM", "Scala").
Compiler("Scala", "JavaScript", "Scala").

// Bootstrap compilers.
Compiler("C", "x86", "x86").
Compiler("OCaml", "x86", "C").
Compiler("Java", "JVM", "C").
Compiler("Scala", "JVM", "Pizza").
Compiler("Pizza", "JVM", "Java").
Compiler("Rust", "x86", "OCaml").
  • (a) What languages can we run (i.e. using any combination of compilers and interpreters)?
  • (b) What source language(s) can compile to what target language(s)?
  • (c) Can we run the Flix compiler on the web (i.e. on JavaScript or WASM)?
  • (d) Can we run Flix programs on the web (i.e. on JavaScript or WASM)?

Hint: Remember that you can compile compilers!

Exercise 01.14 A student was asked to write a Datalog program to compute orphans and wrote: 

Orphan(c) :- Person(c), Person(p), not Parent(c, p).

Initially, the program seemed to work fine, but later, when the student added additional facts the program started to give wrong answers.

  • (a) Give a collection of facts that show the program is broken.
  • (b) Describe why the program is incorrect.
  • (c) Fix the program such that it correctly computes orphans.

Exercise 01.15: Determine if the Datalog program:

Undead(x)  :- Ghost(x).
Undead(x)  :- Vampire(x).
Alive(x)   :- Human(x), not Undead(x).
Mortal(x)  :- Human(x), Alive(x).
Ghost(x)   :- Human(x), not Alive(x), not Vampire(x).
Vampire(x) :- Human(x), Bitten(x, y), Vampire(y), not Ghost(x).

is stratified. If so, compute its stratification.

Exercise 01.16: Determine if the Datalog program:

A(x) :- B(x), C(x), D(x), E(x).
B(x) :- C(x).
C(x) :- A(x), E(x).
E(x) :- D(x), not D(x).
D(x) :- A(x).

is stratified. If so, compute its stratification.

Exercise 01.17: Given the movie facts:

Movie("Reservoir Dogs", "Action").
Movie("Pulp Fiction", "Action").
Movie("Apocalypse Now", "War").
Movie("The Godfather", "Crime").

StarringIn("Reservoir Dogs", "Steve Buscemi").
StarringIn("Reservoir Dogs", "Michael Madsen").
StarringIn("Reservoir Dogs", "Harvey Keitel").
StarringIn("Reservoir Dogs", "Quentin Tarantino").

StarringIn("Pulp Fiction", "John Travolta").
StarringIn("Pulp Fiction", "Samuel L. Jackson").
StarringIn("Pulp Fiction", "Uma Thurman").
StarringIn("Pulp Fiction", "Bruce Willis").
StarringIn("Pulp Fiction", "Quentin Tarantino").

StarringIn("Apocalypse Now", "Martin Sheen").
StarringIn("Apocalypse Now", "Marlon Brando").
StarringIn("Apocalypse Now", "Francis Ford Coppola").

StarringIn("The Godfather", "Al Pacino").
StarringIn("The Godfather", "Marlon Brando").
StarringIn("The Godfather", "Robert de Niro").

DirectedBy("Reservoir Dogs", "Quentin Tarantino").
DirectedBy("Pulp Fiction", "Quentin Tarantino").
DirectedBy("Apocalypse Now", "Francis Ford Coppola").
DirectedBy("The Godfather", "Francis Ford Coppola").

Write Datalog programs to compute:

  • (a) All movies where the director appears in the movie.
  • (b) All movies where the director does not appear in the movie.
  • (c) All directors that appear in every movie they have made.

Hint: Use negation.

Hint: For (c), find directors that have directed movies in which they do not appear.

Exercise 01.18 (The Drinkers Problem): Given the relations:

Drinks(person, beer).
Frequents(person, bar).
Serves(bar, beer).

Write Datalog programs to compute:

  • (a) All persons that frequents some bar that serve a beer they like.
  • (b) All persons that frequents some bar that serve some beer they don’t like.
  • (c) All persons that frequents some bar that serve only beer they don’t like.
  • (d) Add some facts about your favorite bars and beverages to test your programs.

Hint: Use negation.

Hint: Use more negation.

Week 2 (Reading | Slides | Exercises)

Reading

Slides

Download Slides

Exercises

Exercise 02.01: Rewrite the following SQL query:

SELECT 
    C.CustomerName, O.OrderDate, P.ProductName 
FROM 
    Customers C 
JOIN 
    Orders O ON C.CustomerID = O.CustomerID 
JOIN 
    Products P ON O.OrderID = P.OrderID
WHERE 
    P.ProductPrice > '10'.

as a Flix function that uses Datalog.

  • The function should use inject and query.
  • The function should take the relevant tables as lists of tuples.
  • The function should return a list of tuples.

Exercise 02.02: Rewrite the following SQL query as a Flix function:

SELECT
    S.StudentName,
    C.CourseName,
    MAX(G.Grade) AS HighestGrade
FROM
    Students S
JOIN
    Grades G ON S.StudentID = G.StudentID
JOIN
    Courses C ON G.CourseID = C.CourseID
GROUP BY
    S.StudentID, S.StudentName, C.CourseName
ORDER BY
    S.StudentName;
  • Define a data type Grade which is one of: -3, 00, 02, 4, 7, 10, 12.
  • Introduce a lattice on Grade with -3 as the smallest element.

Exercise 02.03: The Bacon number of an actor or actress is the number of degrees of separation they have from the actor Kevin Bacon. Per Wikipedia:

  • Kevin Bacon himself has a Bacon number of 0.
  • Actors who have worked directly with Kevin Bacon have a Bacon number of 1.
  • If the lowest Bacon number of any actor with whom X has appeared in any movie is N, X's Bacon number is N + 1.

Assume we have a relation StarsWith(Actor, Actor):

  • Write a Flix function to compute the Bacon number of every actor.

Exercise 02.04: Given the Flix expressions:

let p1 = #{ A(x, y) :- B(x, x), C(y). };
let p2 = #{ C(x) :- F(x, y), G(y, x) }.;
  • What are the row types of p1 and p2?

Exercise 02.05: Implement Ullman's Algorithm with a Flix function that has the signature: 

def ullman(g: List[(String, Bool, String)]): Map[String, Int32]

where g is the precedence graph represented as a list of edges and where the Boolean indicates whether an edge is positive (true) or negative (false). The function should return a map from each predicate symbol (String) to its stratum. If the precedence graph cannot be stratified, the returned map should map every predicate symbol to -1.

Ullman's Algorithm can be used to determine if a Datalog program is stratified, and if so, to compute the stratum of each predicate symbol. The algorithm can be described as follows:

  • If there is a positive edge A <- B then the stratum of A must be at least the stratum of B.
  • If there is a negative edge A <- not B then the stratum of A must be at least the stratum of B + 1.
  • If we every encounter a stratum number higher than the number of predicate symbols in the program then the program cannot be stratified.

Hint: Use lattice semantics.

Exercise 02.06: Rewrite the following SQL query as a Flix function:

SELECT
    E.EmployeeName,
    D.DepartmentName,
    S.Amount AS LatestSalary,
    S.DateReceived
FROM
    Employees E
JOIN
    Salaries S ON E.EmployeeID = S.EmployeeID
JOIN
    Departments D ON S.DepartmentID = D.DepartmentID
WHERE
    S.DateReceived = (
        SELECT MAX(S.DateReceived)
        FROM Salaries S
        WHERE E.EmployeeID = S.EmployeeID AND S.DepartmentID = D.DepartmentID
    );

Hint: Use lattice semantics.

Hint: Use fix to find the most recent salary per employee.

Hint: You will need more than one relation/lattice.

Exercise 02.07: Given the Flix function signature:

def reachable(g: Set[(Int32, Int32)], src: Int32, dst: Int32): Bool

which takes a graph, represented as a set of edges, and returns true if there is a path from src to dst in the graph, write three implementations:

  • An implementation that uses first-class Datalog constraints.
  • An implementation that uses functional programming.
  • An implementation that uses imperative programming.

You must test your functions on a non-trivial graph that contains cycles.

Hint: You will need to use recursion.

Hint: You may want to use MutSet or MutMap for the imperative version.

Exercise 02.08: Reflect on (Exercise 02.07):

  • Which implementation was the fastest to write?
  • Which implementation do you find the most elegant?
  • How would you extend the functional and imperative versions with parallelism?

Exercise 02.09: Benchmark (Exercise 02.07):

  • Write a simple benchmark to compare the performance of the three implementations.

Exercise 02.10: Compute shortest paths using the rules from the slides (Attempt III), and the following lattice (which does not cause performance issues): 

enum P {
    case Path(Int32, List[Int32])
    case Bot
}

Exercise 02.11: Extend your solution in (Exercise 02.10) to support graphs with negative edges (and hence potentially negative cycles).

Exercise 02.12: The way we compute shortest paths using lattice semantics (Attempt II + Attempt III) is technically wrong. What's the problem?

Hint: Does the declarative semantics still coincide with what we want to compute? What happened?

Week 3 (Reading | Slides | Exercises)

Reading

Slides

Download Slides

Exercises

Exercise 03.01: Get the Wolf, Goat, and Cabbage program to run.

Exercise 03.02: Extend the Wolf, Goat, and Cabbage program with an Island (I) where the farmer, wolf, goat, and cabbage can move to. Add relevant rules for move and safe. Does it change the possible solutions to the problem?

Exercise 03.03: Write a Prolog program that does not terminate.

Exercise 03.04: Write a Datalog program that does not terminate when run with Prolog.

From now on, the Prolog programs you write should always terminate.

Exercise 03.05: The natural numbers are defined as:

nat(z).
nat(s(X)) :- nat(X).

Implement the following relations on natural numbers: +, -, *, <= and min.

Exercise 03.06: In a functional programming language, we cannot define subtraction in terms of addition. Describe how Prolog allows such a definition and implement it.

Exercise 03.07: Use Prolog to determine if the following equations have a solution:

  • x = 1 + 2
  • x + 2 = 3
  • x * x + 1 = 5
  • x <= min(x, y)

where x and y are natural numbers.

Exercise 03.08: Implement odd(X) and even(X) to determine if a number is odd or even.

Exercise 03.09: Implement the Fibonacci function.

Exercise 03.10: Implement prefix(Xs, Ys) and suffix(Xs, Ys) to determine whether the list Xs is a prefix or suffix of Ys.

Exercise 03.11: Implement prefix and suffix in terms of append.

Exercise 03.12: Implement memberOf in terms of append.

Exericse 03.13: Implement two versions of reverse, one using append and one using an accumulator. Draw the proof trees produced by each on a small list.

Exercise 03.14: Implement substitute(A, B, Xs, Ys) which relates Xs to Ys such that every occurrence of A in Xs is replaced by B in Ys.

Exercise 03.15: A binary tree of natural numbers can be defined as:

tree(leaf).
tree(node(X, N, Y)) :- nat(N), tree(X), tree(Y).
  • Assume the tree is unsorted, compute if it contains a given number.
  • Assume the tree is sorted, compute if it contains a given number.
  • Compute the minimum and maximum height of a tree.
  • Compute the sum of the elements of a tree.
  • Translate a tree to a list using a pre-, in-, and post-order traversal.

Exercise 03.16: The following definition of remove for lists is incorrect. Fix it:

remove(x, [], []).
remove(x, [x | ys], rs) :- remove(x, ys, rs). 
remove(x, [y | ys], rs) :- remove(x, ys, rs).

Exercise 03.17: For each pair of terms, manually compute a unifying substitution, or report if unification is impossible.

  • unify(42, 42)
  • unify(21, 42)
  • unify(X, 42)
  • unify(42, X)
  • unify(X, Y)
  • unify(X, X)
  • unify(leaf, leaf)
  • unify(X, node(X, 21, X))
  • unify(X, node(Y, 21, Z))
  • unify(node(leaf, X, leaf), node(leaf, 42, leaf))
  • unify(node(X, Y, leaf), node(leaf, Z, leaf))
  • unify(node(X, Y, X), node(node(leaf, 42, leaf), 21, leaf))
  • unify(node(X, Y, Z), node(node(leaf, 42, leaf), 21, Z))
  • unify([X], [1, 2, 3])
  • unify([X, Y, Z], [Z, X, Y])
  • unify([[X], Y], [Y, [2, 3]])
  • unify([X, Y], [1, [2, 3]])
  • unify([X, Y], [1, [X, 3]])
  • unify([X, [Y]], [1, [X, [Y]]])

Exercise 03.18: Describe why the occurs check is is necessary in the unification algorithm.

Exercise 03.19: When would you use Datalog to solve a programming problem? And Prolog?

Logic Programming Project

The following ideas may be used for inspiration:

Implement a Complex Domain (e.g. rules for a board game, card game, or tax code)

  • As a logic program using Datalog
  • As a logic program using Flix
  • As a logic program using Prolog

Implement a Logic Programming Language

  • Implement a Datalog engine (e.g. using semi-naive evaluation)
  • Implement a Prolog engine (e.g. using SLD resolution)
  • Implement a third logic programming language (e.g. ASP)

Learn Another Logic Programming Language

  • Explore CodeQL and use it for some program analysis.
  • Explore Datafun and use it solve some programming problems
  • Explore FormuLog and use it solve some programming problems
  • Explore Mercury and use it solve some programming problems
  • Explore miniKanren and use it solve some programming problems

Extend the Datalog Solver in Flix

  • Enrich its semantics with new features
  • Improve its performance and/or scalability
  • Improve its ergonomics (e.g. VSCode support)

Paper Presentations