Concurrency

Mid-Term Discussion
Remaining Classes

Thread of control: the von Neumann model

Race conditions

Language Mechanisms

Mid-Term: Some Fun, Eh?

Encapsulation in Java, Eiffel, and Haskell

Self Objects in Java

Categories of languages

Multi-methods

Encapsulation in Java, Eiffel, and Haskell

Java: Package; Class/Interface with public, protected, private; nested classes

Eiffel: Class with more versatile publicity; nested classes

Haskell: Module system with controlled import/export; Class/instance types; anonymous functions, let expressions

Functional equivalence

Eiffel: Relatively minimal set of features
Java: Additional package mechanism; Weaker export/import control
Haskell: Orthogonality

Self Objects in Java

See code example

Categories of languages

Distinctions are primarily historical; poorly defined

An "object-oriented" language can be used in a functional style and vice-versa

May capture "flavor" of typical idioms

Not useful as a way to formally taxonomize languages

Multi-methods

See code example

Add a method to a list in the message

On invoke, sort list by (reverse) total distance to root

Find furthest method that works

Cache result

Hash table of exact class pairs prevents possible linear time search of methods
Figuring out which exact pairs are invalid after adding a method is tricky

Add another method, then resort and invalidate cache

Remaining Classes

Today: Concurrency; Homework

July 23: Case studies of Perl, Python, Ruby, and AppleScript; Homework

July 30: Case studies of Java, C#, Ada, Dylan; Final goes out

August 6: Final due; Last class summarizes

 

First: blast through flow of control remaining....

Selection: A or B?

Canonical if-then-else

Cascading series of conditions

Careful of "dangling else"

Haskell: guards for general conditionals

getWord [] = []

getWord a:x

| elem a whitespace = []

| otherwise = a : getWord x

Selection: One of Many

Choose one control path from many

C, C++, Objective-C, Java: switch is glorified goto

Switch on value is jump to point labeled by "case" and continue on
break or return before next "case" (usually)

Haskell: case uses pattern matching

count Leaf = 0

count Node _ t1 t2 = 1 + count t1 + count t2

 

count' t = case t of

Leaf = 0

Node _ t1 t2 = 1 + count t1 + count t2

Iteration and Recursion

Equivalent constructs

Easiest transformation of recursion to iteration is in case of tail recursion: No computation follows recursive call

getWord [] = []

getWord a:x

| elem a whitespace = []

| otherwise = a : getWord x

Compiler recognizes that stack frame can be re-used in place

No need to allocate new parameters and local variables -- the old ones will never be re-used
More complex transformations possible
Some languages required to support tail recursion optimization (e.g., Scheme)

Monads

Explicit specification of order of operations

class Monad m where

return :: a -> m a

(>>=) :: m a -> (a -> m b) -> m b

Satisfying

return a >>= f = f a

m >>= return = m

m >>= (\a -> ((f a) >>= g)) = (m >>= f) >>= g

Return is identity for >>=

>>= is associative

Lambda analogous to naming intermediate results

Compare

Haskell

sumT' Leaf = 0

sumT' (Node n t1 t2) =

return n >>= \num ->

sumT' t1 >>= \s1 ->

sumT' t2 >>= \s2 ->

return (num + s1 + s2)

Java

class Node extends Tree {

int sumT() {

int num = number();

int s1 = left.sumT();

int s2 = right.sumT();

return num + s1 + s2; }; //....

Monads Can Model Parallelism vs Serialization

Monad makes serial steps explicit

Unspecified order is default

E.g., server and client pair

instance Monad t (Message t)

 

server:: Message t -> IO t

server order = log order >>= show order

 

client:: IO t -> Message t

client input = log input >>= send input

Thread of control: the von Neumann model

Random-access memory

State machine/CPU

One state for the machine, one thread of control

Multiple states or multiple machines, multiple threads of control

Shared memory model of concurrent computing

Race conditions

Consider:

public class Racer extends Thread {

public static int a;

protected class R1 extends Thread {

public void run() { a = 1; } };

protected class R2 extends Thread {

public void run() { a = 2; } };

public void run() {

R1 r1 = new R1; R2 r2 = new R2;

r1.start(); r2.start(); yield();

r1.join(); r2.join();

java.io.System.out.println(a); }; };

What happens when we start Racer?

Alternate Model: Actors

Self-like, but intrinsically parallel and asynchronous

An actor has a mailbox and a script

After a message is received, the script is performed

Script can send messages to other actors
Or perform primitive operations

No guarantee of order anywhere except along consistent route

If a sends two messages to b , they will arrive in the same order they were sent, but that's it
Analogy: TCP/IP, UDP/IP

Linda, or Tuple-Space

Feel of a mix of Actors and Shared Memory

A tuple has a collection of slots

Each slot has a name and a queue of objects

Tuples are shared by threads

Anyone can enqueue

Anyone can dequeue

java.util.Hashtable of java.util.LinkedList

Language Mechanisms

Nested threads

Modula, Ada

Fork/Join

Library calls in C, C++
Base class in Java

Implicit

Semantics of Haskell enable parallelism
Cf. Monads

Reading for next week

Perl, Python, Ruby, and AppleScript

"In a Nutshell" available for each

Or web sites:

perl.org

python.org

ruby-lang.org

apple.com/applescript