[ Posted by Urban Hafner
Wed, 02 Nov 2005 16:13:30 GMT ]
The problem
Order-determining concurrency. Explain what happens when executing the following:
declare A B C D in
thread B=C+1 end
thread C=B+1 end
thread A=1 end
thread B=A+1 end
{Browse D}
In what order are the threads created? In what order are the additions done? What is the final result? Compare with the following:
declare A B C D in
A=1
B=A+1
C=B+1
D=C+1
{Browse D}
Here there is only one thread. In what order are the additions done? What is the final result? What do you conclude?
My solution
Of course both code snippets produce the same result, namely 4. And of course the threads in the first code example are executed in the same way as in the second. That’s because the threads have to wait for the variables they are using in the additions to become bound.
An what do I conclude? Well, that this kind of concurrency is declarative. At least that’s what I think I was supposed to answer :)
Tags book, concurrency, CTM, dataflow, exercise, mozart, oz, variable
[ Posted by Urban Hafner
Wed, 02 Nov 2005 16:13:16 GMT ]
The problem
Concurrent Fibonacci. Consider the following sequential definition of the Fibonacci function:
fun {Fib X}
if X=<2 then 1
else {Fib X-1}+{Fib X-2} end
end
and compare it with the concurrent definition given in section 4.2.3. Run both on the Mozart system and compare their performance. How much faster is the sequential definition? How many threads are created by the concurrent call {Fib N} as a function if N?
My solution
For timing I used the following function. Even though it can only count in seconds, it’s enough for this purpose.
fun {Timer Fun Arg}
Before
in
Before={Time.time}
{Fun Arg _}
{Time.time}-Before
end
For N=30 the normal Fibonacci function took 1 second, the concurrent one 19. For N=40 the normal one took 289 seconds and the concurrent one made my computer swap so I stopped it.
The number of thread created should be in the same order as the number of function calls done, because every other function call is done in its own thread. As the number of function calls is exponential so is the number of threads. Of course this is quite a lame answer, but neither did I have skills nor the motivation to find an exact solution. Maybe Wikipedia can help?
Tags book, concurrency, CTM, exercise, fibonacci, mozart, oz
[ Posted by Urban Hafner
Wed, 02 Nov 2005 16:12:33 GMT ]
The problem
Threads and garbage collection. This exercise examines how garbage collection behaves with threads and dataflow variables. Consider the following program:
proc {B _}
{Wait _}
end
proc {A}
Collectible={NewDictionary}
in
{B Collectible}
end
After the call {A} is done, will Collectible become garbage? That is, will the memory occupied by Collectible be recovered? Give an answer by thinking about the semantics. Verify that the Mozart system behaves in this way.
My solution
At first I was a bit confused by what is meant with after the call is done and how _ behaves. But then I understood. Wait waits until its argument becomes determined. But when you use _ as an argument that can never happen because it creates a new unbound variable.
This I why I think Collectible can’t be garbage collected. It can’t be done because the call to A isn’t finished yet, because the call to B isn’t finished.
Tags book, collection, CTM, exercise, garbage, mozart, oz, thread
[ Posted by Urban Hafner
Wed, 02 Nov 2005 16:10:56 GMT ]
The problem
Thread semantics. Consider the following variation of the statement used in section 4.1.3 to illustrate thread semantics:
1
2
3
4
5
| local B in
thread B=true end
thread B=false end
if B then {Browse yes} end
end
|
For this exercise, do the following:
(a) Enumerate all possible executions of this statement.
(b) Some of these executions cause the program to terminate abnormally. Make a small change to the program to avoid these abnormal terminations.
My solution
(a) Line 4 has to wait until B becomes bound, so either line 2 or 3 has to execute first. The following combinations are possible:
(b) Actually all executions terminate abnormally because all of the eventually try to unify true and false. So what we have to check in the thread in line 2 and 3 is if B is already bound. This leads to the following program:
local B in
thread if {IsDet B} then skip else B=true end end
thread if {IsDet B} then skip else B=false end end
if B then {Browse yes} end
end
Tags book, CTM, exercise, mozart, oz, semantics, thread
[ Posted by Urban Hafner
Thu, 20 Oct 2005 09:53:05 GMT ]
Some fellow students from my faculty started a bioinformatics wiki. Even though there is some information on bioinformatics in Wikipedia, I think it is a good idea to have a specialized wiki for bioinformatics. Not only to get all the definitions, but also to get information on all the tools available.
Tags bioinformatics, wiki
[ Posted by Urban Hafner
Sun, 16 Oct 2005 11:52:25 GMT ]
The first time I heard of the Genographic Project was in the podcast of the talk by Kris Lichter on IT Conversations. It’s a cooperation of IBM and National Geographic. What they are trying is to find out how the human race migrated from Africa across the world. For that they are using genetic markers from indigenous people around the world.
But what makes it interesting is that everybody can participate. You just buy a kit from national geographic, send back your DNA and they analyze it. When the analysis is finished you can find your results on their website. Of course totally anonymous, or so they say. With the money for the kit you payed for the genetic analysis of your DNA and also support some projects to help indigenous people. Maybe that’s why the kit costs $100 (plus $26.50 shipping outside of America) or if the analyses are just that expensive.
After carefully reading the website I finally couldn’t manage to resist any longer. So I ordered the kit and I’m really looking forward to receiving it and to find out what haplogroup I am. And apart from that the project is just cool :)
Tags bioinformatics, evolution, genetic, genographic, human, marker, migration
[ Posted by Urban Hafner
Mon, 26 Sep 2005 15:34:17 GMT ]
The problem
Quicksort. The following is a possible algorithm for sorting lists. Its inventor C.A.R. Hoare, called it quicksort, because it was the fastest known general-purpose sorting algorithm at the time it was invented. It uses a divide and conquer strategy to give an average time complexity of O(n_ log _n). Here is an informal description of the algorithm for the declarative model. Given an input list L, then do the following operations:
- Pick
L’s first element, X, to use as a pivot.
- Partition
L into two lists, L1 and L2, such that all elements in L1 are less than X and all elements in L2 are greater than or equal to X.
- Use quicksort to sort
L1 giving S1 and to sort L2 giving S2.
- Append the lists
S1 and S2 to get the answer.
Write this program with difference lists to avoid the linear cost of append.
My solution
I must admit that I didn’t really understand difference lists and what I did here is mostly based on modifying a version of QuickSort with appends into a version with difference lists. But what I did is mostly a copy the idea from the Flatten example in section 3.4.4 and is not based on a deep understanding of difference lists. Anyway, here it is:
fun {QuickSort L}
fun {Partition Li E Acc1 Acc2}
case Li
of nil then
Acc1#(Acc2)
[] Li1|Lir then
if Li1 < E then
{Partition Lir E Li1|Acc1 Acc2}
else
{Partition Lir E Acc1 Li1|Acc2}
end
end
end
proc {QuickSortD L ?Ds}
case L
of nil then Y in Ds=Y#Y
[] E1|E2|nil then Y in
if E1 < E2 then
Ds=(E1|E2|Y)#Y
else
Ds=(E2|E1|Y)#Y
end
[] E|nil then Y in Ds=(E|Y)#Y
[] X|_ then L1 L2 Y1 Y2 Y4 in
L1#L2={Partition L X nil nil}
Ds=Y1#Y4
{QuickSortD L1 Y1#Y2}
{QuickSortD L2 Y2#Y4}
end
end
Ys
in
{QuickSortD L Ys#nil} Ys
end
Tags book, conquer, CTM, difference, divide, exercise, list, mozart, oz, quicksort, sorting
[ Posted by Urban Hafner
Mon, 19 Sep 2005 10:40:09 GMT ]
The problem
FIFO queues. Consider the FIFO queue defined in section 3.4.4. Answer the following two questions:
(a) What happens if you delete an element from an empty queue?
(b) Why is it wrong to define IsEmpty as follows?
fun {IsEmpty q(N S E)} S==E end
My solution
There is no queue definition in 3.4.4, so I used the worst-case constant-time ephemeral queue because it is represented as a tuple q(N S E).
Consider adding a to the empty queue q(0 X X) using {Insert Q X}. What we get is the new queue q(1 a|E1 E1). Using the definition of IsEmpty from above blocks because the entailment check can’t decide. Deleting an element from the queue returns the queue q(0 E1 E1). Here our IsEmpty works. But it’s of course quite bad when we can use IsEmpty only when we already know that the queue is empty :)
Tags book, CTM, exercise, FIFO, mozart, oz, queue
[ Posted by Urban Hafner
Mon, 19 Sep 2005 10:39:50 GMT ]
The problem
Matrix operations. Assume that we represent a matrix as a list of lists of integers, where each internal list gives one row of the matrix. Define functions to do standard matrix operations such as matrix transposition and matrix multiplication.
My solution
Transposition
fun {Transpose Matrix}
{List.foldR Matrix
fun {$ R1 R2} {List.zip R1 R2 fun {$ E1 E2} E1|E2 end} end
for E in Matrix.1 collect:C do {C nil} end}
end
Multiplication
fun {Multiply Matrix1 Matrix2}
if {ColumnCount Matrix1}=={RowCount Matrix2} then
TM2={Transpose Matrix2} in
for Row1 in Matrix1 collect:R do
{R for Row2 in TM2 collect:S do
{S {List.foldL {List.zip Row1 Row2 fun {$ X Y} X*Y end}
fun {$ X Y} X+Y end 0}}
end}
end
else
raise domainError end
end
end
Addition
% Add any combination of matrices and numbers
fun {Add MN1 MN2}
fun {AddMatrices Matrix1 Matrix2}
{List.zip Matrix1 Matrix2
fun {$ R1 R2} {List.zip R1 R2 fun {$ E1 E2} E1+E2 end} end}
end
fun {AddNumberToMatrix Matrix Number}
for Row in Matrix collect:R do
{R {List.map Row fun {$ E} E+Number end}}
end
end
in
case MN1
of _|_ then
case MN2 of _|_ then
if {RowCount MN1}=={RowCount MN2} andthen
{ColumnCount MN1}=={ColumnCount MN2} then
{AddMatrices MN1 MN2}
else
raise differentSizes end
end
else {AddNumberToMatrix MN1 MN2} end
else
case MN2 of _|_ then {AddNumberToMatrix MN2 MN1}
else MN1 + MN2 end
end
end
Auxiliary functions
fun {RowCount Matrix} {List.length Matrix} end
fun {ColumnCount Matrix} {List.length Matrix.1} end
Tags book, CTM, exercise, list, matrix, mozart, oz
[ Posted by Urban Hafner
Mon, 19 Sep 2005 10:16:32 GMT ]
The problem
Complexity of list flattening. Calculate the number of operations needed by the two versions of the Flatten function given in section 3.4.4. With n_ elements and maximal nesting depth _k, what is the worst-case complexity of each version?
My solution
First of all, I’d like to make clear that I’ve never been good at complexity analyses. Secondly, I first forgot to incorporate the k_. So I will first present my solution without the _k and then try to incorporate it. But there I got stuck. So if you have a correct solution please help me out!
- For the
Flatten using lists the worst-case is a list of n_ Elements which are nested into each other. Then the second branch of Flatten will be selected _n times, and there will be 2n calls to Flatten and n_ calls to Append. While the calls to Flatten are of O(_1) the runtime of the Append calls depend on the length of the first argument to Append. In this case the first call takes n steps, the second call (n – 1), and so on. All the Appends together take n * (n – 1) / 2 time. Together the runtime is of O(2n + n * (n – 1) / 2) which is the same as O(n2^).
- Incorporating k_ into this analysis the worst case is a list of _n/k Elements which are lists nested to depth k_. Then there are in the order of _n calls to
Flatten and all the Append calls together take n/k x (2k 4(k-1) 8(k-2) + ...) time. This should be of O(n2^), but I don’t know how to prove it. And I don’t even see it :(
- The analysis of
Flatten with difference lists is much easier. As we have learnt in chapter 3 the append of two difference lists is of O(1_). So the only thing we have to look at are the number of calls to Flatten. As we have seen before in worst-case there are _n calls to Flatten, incorporating k_ there are even less. So it’s clear that this version of Flatten is of O(_n).
Tags book, CTM, difference, execution, list, mozart, oz, time
