Back to Ada concurrency.

Communication in Ada threads

There are two ways of doing communication: synchronous and asynchronous.

Synchronous communication means that the communication ends when both the sender is at the point of sending and the receiver is at the point of receiving. I.e., whoever gets to that point first has to stop and wait for the other one. Neither the sender nor the receiver can proceed until the communication has completed.

This imposes an order on tasks in concurrent threads. Everything before the communication point has to execute, in both threads, before the things after the communication point.

In asynchronous communication, the sender continues executing after sending the message without waiting for the recipient to receive the message. In this case, there’s nothing that synchronizes the sender and receiver.

Ada provides synchronous communication through entries. They sort of look like procedures, where the sender makes what looks like a procedure call, but is (sort of) executed by the other thread.

Here’s roughly what it looks like. Note that this is taken off prof’s blackboard notes, so syntax might be wonky.

task one is
    entry foo; -- This is the declaration of which entries this task has.
end one;

task body one is
    while true loop
        put("Hello");
        accept foo; -- This is the synchronization point
    end loop;       -- in the thread. When they meet,
end one;            --  it's called a rendezvous.

task two; -- This task has no entries.

task body two is
    while true loop
        one.foo;      -- This is the synchronization point
        put("World"); -- in the second thread. It waits
    end loop          -- for the accept in the first 
end two;              -- thread before continuing.
                      

This program would print “HelloWorldHelloWorld” infinitely, but always in the right order.

Er, actually, because it’s an infinite loop, there’s a possibility that the second “Hello” would print before the “World”, depending on the execution order of the threads. So this would actually print something like “HelloWorldWorldHelloWorldHelloHelloWorld”. But it would always print them in pairs, at least.

You can also add parameters. In Ada, remember that you have input parameters, output parameters, and inout parameters. If you don’t specify, it’s assumed to be in.

task one is
    entry foo(X:integer); -- This is the declaration of which entries this task has.
end one;

task body one is
    while true loop
        put("Hello");
        accept foo(X: integer) do -- Take the parameter
            put(X+1); -- And do something with it in this
        end foo;      -- "accept block".
    end loop;
end one;

task two; -- This task has no entries.

task body two is
    while true loop
        one.foo(6);
        put("World");
    end loop
end two;

This program would print out an infinite “Hello6WorldHello6HelloWorld6Hello”. Where the 6 goes between the two but the order might mess up.

This is why concurrency is hard.

There are two very important points with an accept block that are important for the homework.

1. The rendezvous doesn’t complete until the end of the accept block. Which means the task/thread that called the entry waits for the accept block to finish executing in the other task/thread before continuing.

2. The scope of any parameter to an entry is only within the accept block for that entry. E.g. in our example above, X can’t be accessed outside the accept block.

   If you want to access values outside the accept block, you have to save the value to a local variable.

Some notes about our assignment

We have to implement Quicksort. Quicksort has a partition step, where you split the array, and then the recursive step, where you call it recursively on the left and right sides. In our assignment, the recursive calls need to be done concurrently.

In short:

QS
|
partition
|   \
QS   QS

In Ada, the recursive calls need to be inside tasks. But how do you get the partition to finish before the two tasks start running?

One way to do it is to have an entry call saying “the partition is done”. But that entry call is pretty expensive. A better way of doing this is to not create the task until it’s needed.

Tasks are created when declared in a procedure. When that procedure starts, the task also starts.

For example (in pseudocode), this would be bad:

procedure QS
    task one
        Call QS recursively
    end one;
    
    task two
        Call QS recursively
    end two;
end

But this would cause task one and two to run right away when the procedure is called. But a better way would be put tasks one and two in a nested procedure so they don’t start running until the nested procedure is called. More like:

procedure QS
    procedure GO
        task one
            Call QS recursively
        end one;
        
        task two
            Call QS recursively
        end two;
    end
begin
    partition();
    GO();
end

Tasks would be created at the call of GO. Note that GO will not return until all its tasks are done. So GO’s body could be totally empty:

procedure GO is
begin
    null;
end;

Another option would be to declare a nested block where the tasks are declared in the block. Either would work fine.

And with that, we’re moving back off Ada to more general topics.

Parameter passing in programming languages

Nearly every programming language that defines procedures or functions allows for the passing of parameters to those functions. To define a few things:

void f(int x){ // x here is called the "formal parameter".
    ...
}

int y = 3;
f(y); // y here is the "actual parameter" or "argument".

In a function call, the formal parameter is associated somehow with the actual parameter. But how?

There are actually four different ways that this association can occur. And it depends on the parameter passing mechanism:

1. Pass by value
2. Pass by reference
3. Pass by value result (aka copy-in-copy-out)
4. Pass by name

What are each of these?

Consider this snippet of code:

void f(int x) {
    x = x + 1;
}

int y = 3;
f(y);
print(y);

Pass by value

The formal parameter corresponds to a memory location (i.e. it’s its own variable). The value of the actual parameter is then copied into that memory location.

In our example, the value of y, 3 gets copied into x. x is then incremented, making it 4, but y is unchanged and is still 3. The program prints “3”.

Pass by reference

In this case, we copy the memory address of the actual parameter into the formal parameter, and every time we access the formal parameter we need to follow that pointer through to the actual’s memory location.

In our example, the value of y would then be changed, and the program prints “4”.

Pass by value result

Pass-by-value-result is like pass-by-value, in that it copies the value of the actual into the formal parameter, but when the function returns, the value is copied back from the formal parameter into the actual parameter.

The main difference between the behaviour of this and pass-by-reference is that the values of the actual parameter and the formal parameter can differ during the execution of the function. For example:

int y = 3;
void f(int x) {
    x = x + 1;
    print(y);
}

f(y);
print(y);

This program will print “3”, then “4”, whereas in a pass-by-reference program you’d get “4” then “4”. In pass-by-value, for that matter, you’d get “3” and “3”.

This is not very commonly used.

One problem, for example, is what if you call a function like this:

f(a[i], i)

What if i changes? Where should it copy the value: to the index of the previous value of i or should it recompute the address of a[i] and place it there? It’s ambiguous.

Pass by name

Conceptually, this means that the formal parameter is replaced by the “name”, or the expression, of the actual parameter.

In our example above, this is like literally replacing the name x with the name y.

And this applies to expressions as well, such that if you called f(y+1), you’d end up with the (nonsense) expression in the function body of y+1=y+1 + 1.

And then the function call is replaced by the function body after the parameters are replaced.

Here’s a better example:

void f(int x, int y) {
    y = y+1;
    x = x+1;
}

int a = 3;
int b = 4;
f(a, b);

This becomes, after substitution:

int a = 3;
int b = 4;
b = b+1;
a = a+1;

If you’re passing variables, there’s no difference between this and pass-by-reference. But when you’re passing expressions, it changes things significantly. For example, consider an array indexing, which is an expression you can assign to, using our above example of f(x,y):

int a[] = {...};
int i = 3;
f(a[i], i);

This becomes:

i = i+1;
a[i] = a[i]+1;

Note that in pass-by-reference, the first argument, x, would still refer to a[3]. Here, though, the value that gets changed is actually a[4].

Note also that this isn’t exactly how macros work in C++: this is slightly more powerful than textual substitution, because you can have recursive functions.

This is also rarely used. But this is actually pretty similar to what Haskell (and other lazy-evaluation langauges) does, which is less of a problem because Haskell doesn’t allow you to assign to variables.

In common programming languages

C

C is all pass-by-value, and reference semantics has to be explicitly written through pointer manipulation.

C++

C++ allows you to choose, using & in argument lists for pass-by-reference.

Java

It’s actually pass-by-value. But it’s a tricky one because the value of a Java Object is its memory address. For example:

class C {...};

public static void f(C z) {
    ...
    z = new C(): // Does not affect w below!
}

...
C w = new C();
f(w);

The key point here is that both z and w are pointing to an object of type C somewhere in memory. It’s not pass-by-reference because z does not point to w directly, they’re both pointers. This is why, when z is set to a new object, w is unchanged. But it looks like pass-by-reference because when you access members of z before the change, you also are accessing the members of w.

Ada

Ada doesn’t let you specify which parameter passing mechanism it feels is most efficient. If you make a program that outputs different results depending on which it chooses, your program is considered erroneous. Thus the distinction between input, output, and inout parameters.

inouts are particularly dangerous, I think.