Lectures 19 and 20

2022-11-28 and 2022-11-30 | Week 9 | by Ashwin Ranade

Concurrency
Prolog and Logic Programming

Concurrency

Concurrency is when we decompose a program into simultaneously executing tasks.

The tasks can:

run in parallel on multiple cores, OR run multiplexed on a single core
operate on independent data, OR operate on shared mutable data/systems
be launched deterministcally through program flow, OR be lanuched to due external event (button click in UI)

Concurrency can make our programs more efficient!

Question: If a concurrent program only runs on a single core, why would it be any faster than a program that runs serially? Answer: Some tasks involve lots of waiting, not a lot of CPU. During that waiting time, a concurrent program can use the CPU for other useful tasks!

example: downloading a photo

Concurrency With Shared Mutable State

Race Conditions

Question: What will the value of karma be if I run both functions concurrently until completion? Why?

int karma = 0;

void do_good_deeds() {
  for (int i=0;i<100000;++i)
    karma++;
}

void be_naughty() {
  for (int i=0;i<100000;++i)
    karma--;
}

Answer: Answer: Given that each “thread” of execution can be interrupted at any time to run the other, it’s impossible to know!

The undefined behavior is due to both threads using a shared mutable state; karma is a mutable variable that’s shared between multiple threads. (Race Condition)

a key goal of concurrency is determinism; code should produce the same result every time, regardless of how its tasks are scheduled.

Safe Concurrency With Shared Mutable State

Most modern languages now have built-in language features to make it safer to use shared mutable state.

For example, Java’s synchronized keyword can be used to limit access to a mutable variable to a single thread at a time.

Models for Concurrency

Two approaches for implementing concurrency:

Multi-threading model: A program creates multiple “threads” of execution that run concurrently (potentially in parallel).

The programmer explicitly “launches” one or more functions in their own threads, and the OS schedules their execution across available CPU cores.

// Multi-threaded program (pseudocode)
void handle_user_purchase(User u, Item i) {
  if (bill_credit_card(u) == SUCCESS) {
    create_thread(schedule_shipping(u, i));
    create_thread(send_confirm_email(u, i));
  }
}

Event Driven Model: A program consists of a queue of functions to run, and an infinite loop that dequeues and runs each function from the queue, one after the other.

When an event occurs (e.g., user clicks a button) the event results in a new function f() being added to the queue which eventually runs and handles the event.

// Event-driven program (pseudocode)
function process_payment() { ... }

void setup_event_associations() {
 button = create_new_button("Pay Now!");
 button.set_func(ON_CLICK, process_payment);
}

Fork-Join: A Common Pattern for Multi-Threading

The “fork-join” pattern is basically a concurrent version of divide and conquer.

First, we “fork” one or more tasks so they execute concurrently…

Second, we wait for all those tasks to complete (aka “join”) and then proceed.

Example: A parallel sort would be a good example of a problem suitable for fork-join.

function sort_in_parallel(array, n) {
  t1 = run_background(sort(array[0:n/3])); 
  t2 = run_background(sort(array[n/3:n*2/3)); 
  t3 = run_background(sort(array[n*2/3:n]));

  wait_for_all_tasks_to_finish(t1, t2, t3);
  merge_sorted_subarrays(array);
}

function task1(param) { ... }
function task2(param) { ... }
function task3(param1, param2) { ... }

function launch_in_parallel() {
  t1 = run_background(task1(42)); 
  t2 = run_background(task2("suss")); 
  t3 = run_background(task3(3.14, 2.71));

  wait_for_all_tasks_to_finish(t1, t2, t3);
  print("All tasks completed, proceeding...");
}

Fork-Join is Often Used Recursively.

Fork-Join In Different Languages

// C++
#include <thread>          
 
void task1(int n)  { ... }
void task2(int n)  { ... }
void task3(int n)  { ... }

int main() {
  std::cout << "Forking threads!\n";
  //To launch a function in the background, we simply create a new thread object.

  std::thread t1(task1, 10);
  std::thread t2(task2, 20);
  std::thread t3(task3, 30);

  // do other processing here...

  t1.join(); //To join, we simple call the thread.join() method. This blocks the caller until the thread finishes.

  t2.join();
  t3.join();
  std::cout << "All threads joined!\n";
}

# Python
import threading

def task(n):
  while n > 0:   # do some computation
    n = n - 1

print("Forking threads!")

#In Python, we must create a thread object, and then do thread.start() before it runs.

t1 = threading.Thread(target=task, args=(100000000,))
t2 = threading.Thread(target=task, args=(100000000,))
t3 = threading.Thread(target=task, args=(100000000,))
t1.start()
t2.start()
t3.start()

# do other processing here...

t1.join()
t2.join()
t3.join()
print("All threads joined!")

Multi-threading in Python

Question for the Python program: Assuming looping 100 million times takes 5s, how long will this program take to run on a multicore PC?

Answer: 15s We’d expect all three tasks to run in parallel… taking 5s total. But it takes 15s! Why? Because when each Python thread runs, it claims exclusive access to Python’s memory/objects.

So only one thread generally does computation at a time!

Why? Python’s garbage collection system was never designed to be thread-safe!

Python has something called a “Global Interpreter Lock” or GIL.

The GIL is like a hot potato – it can only have one owner at a time.

Once a thread takes ownership of the GIL it’s allowed to read/write to Python objects.

After a thread runs for a while, it releases the GIL (tosses the potato) to another thread and gives it ownership.

If a thread is waiting for the GIL, it simply falls asleep until it gets its turn.

Question: So why even support multiple threads? Are there any cases where multithreading speeds things up?

Answer: Answer: I/O operations like downloading data from the web or saving a file to disk DON’T need the GIL to run! So these kinds of operations can still make progress if launched in the background!

Prolog and Logic Programming

Overview of Logic Programming

Logic programming is a paradigm where we express programs as a set of facts (relationships which are held to be true), and a set of rules (i.e. if A is true, then B is true).

A program/user then issues queries against this these facts and axioms:

Logic programming is declarative – programs specify “what” they want to compute, not “how” to do so.

Examples:

Facts:

Martha is Andrea’s parent
Andrea is Carey’s parent

Rules: If X is the parent of Q, and Q is the parent of Y, then X is the grandparent of Y

Queries:

Is Martha the grandparent of Carey?
Who is the grandparent of Carey?

Introduction to Prolog

Prolog is used for theorem-proving (type checking is one such use case) and has also been used to implement natural language processing and expert systems.

Prolog is primarily declarative but also has some imperative features.

Other logic programming languages: Datalog, Flix, Fril, Alf

When given a query, Prolog tries to find a chain of connections between the query and the specified facts and rules that lead to an answer.

Prolog Programs

Every Prolog program is comprised of facts about the world, and a bunch of rules that can be used to discover new facts.

Prolog Facts

A “fact” is a predicate expression that declares either…

An attribute about some thing (aka atom)
- outgoing(ren)
A relationship between two or more atoms or numbers:
- parent(alice, bob)
- age(ren, 80)

Facts look like function calls, but they’re really just static assertions of different relationships.

In Prolog, the functor and all atoms must be lower case.
If a fact is not explicitly stated, then it is assumed to be false.

Prolog Rules

A rule lets us define a new fact in terms of one or more existing facts or rules.

Each rule has two parts…

A “head” which defines what the rule is trying to determine
A “body” which specifies the conditions (aka subgoals) that allow us to conclude the head is true

Rules are defined in terms of Variables as well as atoms and numbers.

Variables like X and Y are placeholders, which Prolog will try to fill in as it tries to answer user queries. [must always be capitalized]

% Facts:
outgoing(ren).
silly(ren).
parent(alice, bob).			 
age(ren, 80).
parent(bob, carol). 			 

% Rules:
comedian(P) :- silly(P), outgoing(P).
grandparent(X, Y) :- parent(X,Q), parent(Q,Y). 
old_comedian(C) :- comedian(C),                                         age(C, A), A > 60.

Recursive Rules

Rules can also be recursive and can have multiple parts!

Just as with recursion, always put the base-case first, since when answering queries, Prolog processes rules from top-to-bottom.

% Recursive rules:
ancestor(X, Z) :- parent(X,Z).
ancestor(X, Z) :- parent(X,Y), ancestor(Y,Z).

Explanation of the above code block: X is the ancestor of Z if:

X is Z’s parent
OR if X is some person Y’s parent AND Y is an ancestor of person Z

Negation in Rules

Rules can also use negation – but be careful!

In Prolog, not() works as follows:

Prolog tries to prove is true using all of the program's facts and rules
If can't be proven as true, then not() is found to be true.

% Rules with negation:
serious(X) :- not(silly(X)).

For example, the following query would be found to be true:

serious(alice)

Closed World Assumption (CWA)

Prolog operates according to the Closed World Assumption.

The CWA states that only those things can be proven to be true by the program’s facts/rules are true. And thus, anything that cannot be proven to be true with the facts/rules, must, by definition, be false.

For instance, the CWA would conclude that alice is NOT silly because otherwise the facts/rules would have shown this.

The world is “closed,” and a condition is true IFF it is provable via the facts/rules; everything else is assumed to be false.

Prolog Queries

We can create queries to answer true/false questions:

A query can match a simple fact…

Or it can execute a rule.

?- outgoing(alice)
true
?- grandparent(brenda, ned)
true

We can also create queries to fill-in-the-blanks:

The query will find ALL possible matches.
The query can specify multiple unknowns.
And Prolog will find ALL consistent combinations of answers!

?- parent(alice , Who)
Who = bob
Who = brenda
?- grandparent(A, B)

%answers to queries below
A = alice, B = caitlin
A = brenda, B = ned

Resolution: How Prolog Answers Queries

Example facts/rules:

parent (nel, ted).
parent (ann, bob).
parent (ann, bri).
parent (bri, cas). 
gparent( X ,  Y )  :- 
  parent(X,Q), parent(Q,Y). 

Example query:

gparent(ann, W)

Algorithm:

Add our query to a goal stack
Pop the top goal in our goal stack and match it with each item in our database, from top to bottom
If we find a match, extract the variable mappings, and create a new map with the old+new mappings
Create a new goal stack, copying over existing, unprocessed goals and adding new subgoals
Recursively repeat the process on the new goal stack and the new mappings

So initially, our goal stack is simply gparent(ann,W), and our mappings are {}. Then, after matching the last rule, our goal stack becomes:

parent(X,Q)
parent(Q,Y)

And our mappings are {X->ann,W<->Y}

Then, pop the top rule off our goal stack. We have a potential match with parent (nel, ted). So our goal stack becomes:

parent(Q,Y)

With the mappings: {X->ann,W<->Y, Q->bob}

We pop the top rule off the stack again. There’s no rule that matches parent(bob,Y), which means the set of mappings we discovered were not valid.

So we’ll back-track one level up and continue searching for alternative mappings.

If our goal stack is empty, we output variables from our mapping that were explicitly queried; in this case, our final mapping is: { X ->ann, W <-> Y <-> cas, Q ->bri }

So we return cas, since W=cas.

Unification

As we saw, during the Resolution process, Prolog repeatedly Compares the current goal with each fact/rule to see if they are a match.

If a goal and a fact/rule match, Prolog extracts mappings between variables and atoms (e.g., X->bob).

Together, these two steps (comparison + mapping) between a single goal and a single fact/rule are called unification.

Unification pseudocode:

def unify(goal, fact_or_rule, existing_mappings):
   if the goal with the existing mappings matches the current fact/rule:
      mappings = extract variable mappings between goal and fact/rule
      return (True, mappings)	 # We did unify! Return discovered mappings
   otherwise:
      return (False, {})   	# We couldn't unify! So no mappings found

The unification algorithm runs on one goal at a time.
Unification runs on a single fact or rule at a time.

Matching a Goal and a Fact/Rule

So how do we determine if a goal with the current mappings matches a specific fact/rule?

apply all current mappings to the goal
treat both the mapped goal and head of the fact/rule as trees
Compare each node of the goal tree with the corresponding node in the fact/rule tree

Use the following comparison rules:

If both nodes are functors, then make sure the functors are the same and have the same number of children.
If both nodes hold atoms, make sure the atoms are the same.
If a goal node holds an unmapped variable it will match ANY item in the corresponding node of the fact/rule.
If a fact/rule node holds an unmapped variable it will match ANY item in the corresponding node of the goal.

Note: The animations do a really good job of explaining this – they are slides 20-21 of the Prolog lecture. I’ll do my best, but it’s hard to transcribe into text.

Unification: Do They Match

Follow the rules above. Many examples are on ~slides 20-30 of the Prolog presentation; they’re hard to transcribe into text.

Here’s one example:

Assuming we have the mapping {What->ucla}, and we are trying to match (1) likes(gene, What) with (2) likes(Y,X). These DO MATCH.

we replace What with ucla, so the children of the likes node for (1) becomes gene and ucla.
This matches the children nodes for (2), since they both hold unmapped variables [Y and X respectively]

Unification: Extracting Variable Mappings

Once we know that a goal matches a fact/rule, we need to extract the variable mappings.

Approach:

Iterate through each corresponding pair of nodes in both trees.
Any time you find an unmapped Variable in either tree that maps to an atom/number in the other tree, create a mapping between the variable and the atom.
Any time you find an unmapped Variable in either tree that maps to an unmapped Variable in the other tree, create a bidirectional mapping between the variables.

Unification: Summary

Unification is the process of:

comparing a single goal with a single fact/rule, given the current set of mappings
determining if the goal and the fact/rule match
If so, extracting all new mappings between variables and atoms on either side.

Unification is used within the broader Resolution algorithm that we traced through.

Resolution Continued

Here’s a simplified version of the Resolution algorithm, showing where Unification fits in.

def resolution(database, goals, cur_mappings):
  if there are no goals left:
    tell the user we found a solution and output our discovered mappings!
    return
  for each fact/rule z in the database:
    success, new_mappings = unify(goals[0], fact_or_rule, cur_mappings)
    if success:
      tmp_mappings = cur_mappings + new_mappings
      tmp_goals = sub_goals(z) + goals[1:]
      resolution(database, tmp_goals, tmp_mappings)    # recursion
  # if we get here, we didn't find a match... BACKTRACK and keep trying!

The Resolution algorithm is initially called with the user’s query as its only goal, and with no initial mappings.

# Determine if ann the grandparent of cas?
resolution(database, "gparent(ann, cas)", { })

Prolog Lists

Lists in Prolog are just like lists in Haskell or Python.

Lists can contain numbers, atoms, or other lists.

[ ]
[silly, goofy, gleeful]
[1, 2, [dog, cat], 3.5]

Prolog uses a combination of pattern matching (like Haskell) and unification to process lists.
List processing is also done with facts and rules, just like other inference tasks.

Firstly, here’s a Prolog fact with variables inside of atoms.

is_the_same(X,X)

is_the_same(lit,lit) --> returns true
is_the_same(ucla,usc) --> returns false

Now, time for some Prolog lists!

Example 1

is_head_item(X,[X | XS]).

This [X | XS] syntax is Prolog’s equivalent of pattern matching, just like (x:xs) in Haskell.

X matches the first item of the list. XS matches the rest of the list.

is_head_item(lit, [lit, dank, snack]) --> returns true
is_head_item(drip, [lit,dank,snack]) --> returns false

Explanation: Prolog is unifying from left-to-right and mapping each variable.

Once it extracts a mapping, it only “unifies” the query if later uses of the mapping are consistent with the first.

We can also do:

Example 2

is_second_item(Y, [X, Y | XS]).

[X, Y | XS] equivalent of (x:y:xs) in Haskell.

X matches the first item of the list. Y matches the second item of the list. XS matches the rest of the list.

is_head_item(dank, [lit, dank, snack]) --> returns true
is_head_item(lit, [lit,dank,snack]) --> returns false

Example 3: Checking if a list contains a value

is_member(X,[X|Tail]). 
is_member(Y,[Head|Tail]) :- is_member(Y,Tail). 

If we query is_member(dank,[lit,dank,snack]):

we first try and match the first fact, but it’s false
so we match on the second rule, which turns out to unify, so we return True!

Example 4: Deleting an atom from a list

The general form will be: delete(ItemToDelete, ListToDeleteFrom, ResultingList)

A query could look like this: delete(carey, [paul, carey, david], X) –> X = [paul, david]

delete(Item, [Item | Tail], Tail).  
delete(Item_, [Head_ | Tail_], [Head_ | FinalTail])  :-  delete(Item_, Tail_, FinalTail).

The first line is like we saw earlier – it handles the base case.

The base case handles the situation where the first item in the list is the one we want to delete, e.g.: delete(carey, [carey, david, paul], X)

The second line handles the case where the item we want to delete ISN’T the first item, e.g.: delete(david, [carey, david, paul], X)

Our rule uses pattern matching to break up the input list into the Head item and all Tail items.
the subgoal: “Use delete to remove the Item from amongst the Tail items; FinalTail refers to the resulting tail”
In this case, we construct our output list by concatenating the Head item from our original list with the tail of the list with the Item removed from it.

Prolog List Processing: Built-in Facts and Rules

append(X,Y,Z)

Determines if list X concatenated with list Y is equal to list Z
append([1,2],[3,4],[1,2,3,4]) yields True
append([1,2],X,[1,2,3,4]) yields X -> [3,4]

sort(X,Y)

Determines if the elements in Y are the same elements of X, but in sorted order
sort([4,3,1], [1,3,4]) yields True
sort([4,3,1],X) yields X -> [1,3,4]

permutation(X,Y)

Determines if the elements in Y are the same elements of X, but in a different ordering

permutation([4,3,1], [3,1,4]) yields True

reverse(X,Y)

Determines if list X is the reverse of list Y

reverse([1,2,3],[3,2,1]) yields True
reverse([1,2,3],X) yields X -> [3,2,1]

member(X,Y)

Determines if X is a member of the list Y

member(6, [1,6,4]) yields True
member(X,[1,6,4]) yields X -> 1, X -> 6, and X -> 4

sum_list(X,Y)

Determines if the sum of all elements in X add up to Y
sum_list([4,3,1], 8) yields True
sum_list([4,3,1], Q) yields Q -> 8

Prolog List Syntax is Syntactic Sugar For Functors and Atoms!

Notice that when you remove the syntactic sugar, list processing is implemented just like any other Prolog fact or rule!

And while we didn’t see an example in the slides, the empty list [ ] can similarly be written as the atom nil.

The	operator (as in [X	Tail]) can be replaced with a fact named “cons” that takes two arguments.
- [X	Tail] –> cons(X,Tail)

original facts/rules:

is_member(X, [X | Tail]).
is_member(Y, [Head | Tail]) :- is_member(Y, Tail).

rewritten:

is_member(X, cons(X,  Tail)).
is_member(Y, cons(Head, Tail)) :- is_member(Y, Tail).