Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Advanced Programming

Welcome to the webpage for the Logic Programming module, part of the Advanced Topics in Programming Languages Theory (ATPLT) course at Aarhus University.

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

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 is 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 Theory course.

See that course description for details.

Lecturer

LecturerEmailOfficeOffice Hours
Magnus Madsenmagnusm@cs.au.dkTuring-215Any time

Syllabus

Week 1: Introduction to Logic Programming and Datalog

Week 2: Programming with Datalog in Flix

Week 3: Programming with Prolog

PhD Level Variant: Extra Material

The following extra material is required reading for the PhD level version of the course:

Logic Programming

Week 1

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 are its Herbrand Universe and Herbrand Base?

Hint: The Herbrand Base will be large. You may want to write it 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 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 route 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 frequent some bar that serves a beer they like.
  • (b) All persons that frequent some bar that serves some beer they don’t like.
  • (c) All persons that frequent some bar that serves 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

Extra Reading (PhD Level)

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 plus one.
  • If we ever 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(S2.DateReceived)
        FROM Salaries S2
        WHERE E.EmployeeID = S2.EmployeeID AND S2.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: Consider the Datalog program:

    Edge(1, 2). Edge(2, 4). Edge(1, 3). Edge(3, 5). Edge(5, 4).
R1: Path(x, y) :- Edge(x, y).
R2: Path(x, z) :- Path(x, y), Edge(y, z).
  • Draw two distinct provenance trees for the fact Path(1, 4). Label each internal node with the rule (R1 or R2) used to derive it, and mark the EDB facts.
  • For each of your two trees, write down the provenance path w.r.t. {Edge}.
  • Flix guarantees that pquery computes a provenance tree of minimal height. Which of your two trees can pquery pr select Path(1, 4) with {Edge} return?

Exercise 02.08: You are a financial crime investigator tracing laundered money. Money moves between accounts in three ways:

  • Wire("acme-holdings", "Cayman National Bank", "shellcorp-7", 100) states that money was wired from account acme-holdings to account shellcorp-7 through the bank Cayman National Bank at time 100.
  • Cash("alpine-invest", "offshore-trust-x", 550) states that cash was handed over from alpine-invest to offshore-trust-x at time 550.
  • Crypto("shellcorp-7", "Binance", "shellcorp-12", 250) states that money was swapped from shellcorp-7 to shellcorp-12 on the crypto exchange Binance at time 250.

The last component of each fact is a timestamp (a Unix-style integer). You are given the following transaction log:

Wire("acme-holdings", "Cayman National Bank", "shellcorp-7", 100).
Wire("shellcorp-7", "Banco General", "tropical-imports", 110).
Cash("tropical-imports", "shellcorp-7", 120).
Wire("nordic-ventures", "LGT Bank", "offshore-trust-x", 150).
Wire("pelican-trading", "Banco General", "shellcorp-12", 210).
Crypto("shellcorp-7", "Binance", "shellcorp-12", 250).
Wire("acme-holdings", "Danske Bank", "nordic-ventures", 300).
Crypto("shellcorp-12", "Kraken", "riviera-estates", 320).
Wire("nordic-ventures", "Danske Bank", "acme-holdings", 350).
Wire("riviera-estates", "HSBC", "luxe-yachts", 380).
Wire("shellcorp-12", "Julius Baer", "alpine-invest", 400).
Cash("alpine-invest", "offshore-trust-x", 550).

Write a Flix function:

def followTheMoney(src: String, dst: String): Vector[String]

which documents how money flowed from account src to account dst, as a vector of human-readable strings, e.g. "acme-holdings wired money to shellcorp-7 via Cayman National Bank", "tropical-imports handed cash to shellcorp-7", or "shellcorp-7 swapped crypto to shellcorp-12 on Binance".

Your evidence must hold up in court: the transfers must form an unbroken chain from src to dst, and money cannot leave an account before it has arrived, i.e., the timestamps along the chain must be strictly increasing.

Test your function by tracing the money from acme-holdings to offshore-trust-x.

Hint: Use pquery.

Exercise 02.09: You are given a database of currency exchange rates, where a fact Rate("DKK", "EUR", 0.134) states that 1 DKK buys 0.134 EUR:

Rate("DKK", "EUR", 0.134).
Rate("DKK", "SEK", 1.55).
Rate("SEK", "NOK", 0.98).
Rate("EUR", "USD", 1.08).
Rate("EUR", "GBP", 0.85).
Rate("GBP", "USD", 1.27).
Rate("USD", "JPY", 155.0).
Rate("USD", "CHF", 0.88).
Rate("CHF", "EUR", 1.06).
Rate("KRW", "USD", 0.00072).

Write a Flix function:

def convert(amount: Float64, src: String, dst: String): Option[Float64]

which converts amount from currency src to currency dst, possibly through a chain of intermediate currencies, or returns None if no conversion chain exists. The effective rate of a conversion chain is the product of the rates along it.

Test your function by converting 1,000 DKK to USD and 1,000 DKK to KRW.

Hint: Use pquery.

(Hard, Optional): There are two ways to convert DKK to USD (via EUR, or via EUR and GBP) with slightly effective rates. Which one does your function compute? How could you change the Datalog program such that the provenance path is guaranteed to be the chain with the best effective rate?

Exercise 02.10: 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.11: Reflect on Exercise 02.10:

  • 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.12: Benchmark Exercise 02.10:

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

Week 3

Reading

Extra Reading (PhD Level)

Slides

Download Slides

Exercises

Exercise 03.01: Open the Ciao playground and enter the family program:

parent(emma, magnus).
parent(emma, daniela).
parent(magnus, oscar).
parent(daniela, freja).
  • Define grandparent(X, Y) and ask ?- grandparent(emma, X).
  • Then ask ?- grandparent(X, freja). — note that you can query in both directions.

Exercise 03.02: Enter the graph program:

edge(a, b).
edge(b, c).

path(X, Y) :- edge(X, Y).
path(X, Z) :- edge(X, Y), path(Y, Z).
  • Ask ?- path(a, X). and collect all solutions.
  • Replace the second rule with path(X, Z) :- path(X, Y), edge(Y, Z). What happens, and why?

Exercise 03.03: Predict the answer to each query, then check it in Ciao:

?- X = 1 + 2.
?- X is 1 + 2.
?- 3 = 1 + 2.
?- f(X, b) = f(a, Y).
?- [H | T] = [1, 2, 3].
?- X = f(X).

What is the difference between = and is?

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.

In the following exercises, use the representation of the natural numbers and the relations defined above.

Exercise 03.06: Use Prolog to determine whether each of the following equations and inequalities has a solution:

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

where x and y are natural numbers, and the numerals abbreviate their Peano form (e.g. 2 abbreviates s(s(z))).

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

Exercise 03.08: Implement the Fibonacci function.

A list can be defined as:

list([]).
list([_ | Xs]) :- list(Xs).

For example, [1, 2, 3] is shorthand for [1 | [2 | [3 | []]]].

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

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

Exercise 03.11: Implement memberOf in terms of append.

Exercise 03.12: 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.13: 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.14: A binary tree of natural numbers can be defined as:

tree(leaf).
tree(node(X, N, Y)) :- nat(N), tree(X), tree(Y).
  • Define a predicate containsUnsorted(T, N) which determines whether the unsorted tree T contains the number N.
  • Define a predicate containsSorted(T, N) which does the same for a sorted tree, visiting at most one subtree per node.
  • Define predicates minHeight(T, N) and maxHeight(T, N) which relate T to the length of its shortest and longest path from the root to a leaf.
  • Define a predicate sum(T, N) which relates T to the sum of its elements.
  • Define predicates preOrder(T, Xs), inOrder(T, Xs), and postOrder(T, Xs) which relate T to the list Xs of its elements in that traversal order.

Exercise 03.15: 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.16: For each pair of terms, manually compute a unifying substitution, or report if unification is impossible.

  1. unify(42, 42)
  2. unify(21, 42)
  3. unify(X, 42)
  4. unify(42, X)
  5. unify(X, Y)
  6. unify(X, X)
  7. unify(leaf, leaf)
  8. unify(X, node(X, 21, X))
  9. unify(X, node(Y, 21, Z))
  10. unify(node(leaf, X, leaf), node(leaf, 42, leaf))
  11. unify(node(X, Y, leaf), node(leaf, Z, leaf))
  12. unify(node(X, Y, X), node(node(leaf, 42, leaf), 21, leaf))
  13. unify(node(X, Y, Z), node(node(leaf, 42, leaf), 21, Z))
  14. unify([X], [1, 2, 3])
  15. unify([X, Y, Z], [Z, X, Y])
  16. unify([[X], Y], [Y, [2, 3]])
  17. unify([X, Y], [1, [2, 3]])
  18. unify([X, Y], [1, [X, 3]])
  19. unify([X, [Y]], [1, [X, [Y]]])

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

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

Week 4

Reading

Extra Reading (PhD Level)

Slides

Download Slides

Exercises

For the following exercises, you can play around on repl.futhark-lang.org, but you will have a better experience if you install Futhark on your own system. You do not have to run any of your code on a GPU, and it is discouraged unless it works immediately, as configuring a GPU development environment is in many cases nontrivial. If you can compile C programs, it is possible that --backend=multicore will also work.

However, you can just stick to using futhark repl and ignore the questions that ask you to perform benchmarking.

If you use Windows, use WSL. To run compiled code, you must have a C compiler available in your shell environment.

Exercise 04.01:

Create a Futhark function process : []i32 -> []i32 -> i32 that takes as arguments two one-dimensional i32 arrays (signals) of the same length and computes the maximum absolute difference (pointwise) between the signals (you should not use Futhark’s loop construct). The function should return the value 0 if two empty signals are passed to the function.

Consider the following two signals:

def s1 = [23,45,-23,44,23,54,23,12,34,54,7,2, 4,67]
def s2 = [-2, 3,  4,57,34, 2, 5,56,56, 3,3,5,77,89]
  • What is the result of calling your function on s1 and s2?

Exercise 04.02:

We can use futhark bench to benchmark Futhark programs. Change the definition of your process function to use entry instead of def and add the following stanza to your program:

-- ==
-- entry: process
-- random input { [1000000]i32 [1000000]i32 }

Then use futhark bench process.fut to benchmark your program. You can have multiple random input lines.

  • How does your program scale for different inputs? Does it scale as predicted by the work-span cost model, even for very small or very large inputs?

Exercise 04.03:

Create a version of process, called process_idx : []i32 -> []i32 -> (i32,i64), that also returns the index of the source signals for which the largest absolute difference is found.

  • What is the result of calling your function on s1 and s2?

Hint: you wil need to construct a new reduce operator.

Exercise 04.04:

Inspired by the implementation of filter shown in the slides, finish this implementation of partition:

def partition [n] 'a (p: a -> bool) (as: [n]a) : ([]a, []a) =
  ???

The intent is that partition separates those elements that satisfy a predicate from those that do not. Example:

> partition (\x -> x%2==0) [0,1,2,3,4,5,6,7]
([0, 2, 4, 6],
 [1, 3, 5, 7])

While you can implement this as two filters, it can also be done more efficiently, by being clever about the indexes.

  • What is the work and span of your implementation? Is it work-efficient?

Exercise 04.05:

The slides describe how to implement a segmented scan. A similar operation is a segmented reduction. Finish the following implementation of segmented reduction:

def segreduce [n] 't (op: t -> t -> t) (ne: t)
                     (fs: [n]bool) (vs: [n]t): []t =
  ???
  • What is the work and span of your implementation? Is it work-efficient?

Hint: this is best done by performing a segmented scan, then extracting the last element of every segment.

Exercise 04.06:

Implement a function for computing histograms:

def histogram [n] (k: i64) (xs: [n]u32) : [k]i64 =
  ???

If H = histogram k xs, then H[i] counts how many occurrences of i are present in xs. Any number x in xs that is not in the range [0,k-1] is ignored.

Hint: use a sort followed by a segmented reduction - you will also need to compute an appropriate flag vector.

Hint: use i64.u32 to convert a u32 number to i64.

Hint: Remember that not all buckets of the histogram may be occupied.

  • What is the work and span of your implementation? Is is work-efficient?