[ Posted by Urban Hafner
Sat, 17 Sep 2005 14:37:12 GMT ]
The problem
Limitations of difference lists. What goes wrong when trying to append the same difference list more than once?
My solution
Assume you have the two difference lists (a|b|c|X)#X and (d|e|f|Y)#Y. To append them you bind X to (d|e|f|Y). Using the Append function from 3.4.4 what you get is (a|b|c|d|e|f|Y)#Y. But this changes the first difference list into (a|b|c|d|e|f|Y)#(d|e|f|Y).
If you then try to use the first difference list in another append with, say (x|y|Z)#Z you will get a unification error because what you try to do in the Append function is unify (d|e|f|Y) with (x|y|Z). This will of course fail. But in the first append of the difference list the unification was X=(d|e|f|Y) which of course succeeds always as X is an unbound variable.
Tags book, CTM, difference, exercise, list, mozart, oz
[ Posted by Urban Hafner
Thu, 15 Sep 2005 18:55:59 GMT ]
The problem
Checking if something is a list. Section 3.4.3 defines a function LengthL that calculates the number of elements in a nested list. To see whether X is a list or not, LengthL uses the function Leaf defined this way:
fun {Leaf X} case X of _|_ then false else true end end
What happens if we replace this by the following definition?:
fun {Leaf X} X\=(_|_) end
What goes wrong if we use this version of Leaf?
My solution
What happens is that when you call the second definition of Leaf with a non-nil value the computation suspends. I’m also not entirely sure on this one. But what probably happens is this. The two _ create two new unbound variables in the store. This then means that the disentailment check can’t decide and blocks.
Tags book, CTM, exercise, list, mozart, oz
[ Posted by Urban Hafner
Thu, 15 Sep 2005 18:55:46 GMT ]
The problem
Iterative computations and dataflow variables. The previous exercise shows that using dataflow variables sometimes makes it simpler to write iterative list operations. This leads to the following question. For any iterative operation defined with dataflow variables, is it possible to give another iterative definition of the same operation that does not use dataflow variables?
My solution
I’m really unsure about this one. If anyone can explain it in a nice and convincing way I’d happily replace my hand waving with it.
If we assume that iterative computation means the function Iterate from section 3.2.4 then it seems possible to replace any use of dataflow variables. Just translate your function into one similar to Iterate and you have removed any dataflow variables.
Tags book, CTM, dataflow, exercise, iterative, mozart, oz
[ Posted by Urban Hafner
Thu, 15 Sep 2005 18:55:23 GMT ]
The problem
An iterative append. This exercise explores the expressive power of dataflow variables. In the declarative model, the following definition if append is iterative:
fun {Append Xs Ys}
case Xs
of nil then Ys
[] X|Xr then X|{Append Xr Ys}
end
end
We can see this by looking at the expansion:
proc {Append Xs Ys ?Zs}
case Xs
of nil then Zs=Ys
[] X|Xr then Zr in
Zs=X|Zr
{Append Xr Ys Zr}
end
end
This can do a last call optimization because the unbound variable Zr ca be put in the list Zs and bound later. Now let us restrict the computation model to calculate with values only. How can we write an iterative append? One approach is to define two functions: (1) an iterative list reversal and (2) an iterative function that appends the reverse of a list to another list. Write an iterative append using this approach.
My solution
The iterative list reversal is already defined in the book in section 3.4.2.4. Taking this Append can be defined as follows:
local
fun {IterAppend RevXs Ys}
case RevXs
of nil then Ys
[] X|Xr then {IterAppend Xr X|Ys}
end
end
in
fun {Append Xs Ys}
{IterAppend {Reverse Xs} Ys}
end
end
Tags book, CTM, exercise, iterative, mozart, oz
[ Posted by Urban Hafner
Wed, 14 Sep 2005 19:26:04 GMT ]
The problem
Another append function. Section 3.4.2 defines the Append function by doing recursion on the first argument. What happens if we try to do recursion on the second argument? Here is a possible solution:
fun {Append Ls Ms}
case Ms
of nil then Ls
[] X|Mr then {Append {Append Ls [X]} Mr}
end
end
Is this program correct? Does it terminate? Why or why not?
My solution
On first sight this definition seems to be correct. But of course it isn’t. This is an exercise from a CS textbook, so when a question like “Is this correct?” is asked is clear that the answer has to be “No!” :)
Anyway, here’s why this definition of Append is wrong: The problem is the inner call to Append. In this call Ms is bound to [X] which is the same as X|nil. But this means that it will always go into the second branch of the case statement. It will take apart the list and create the very same list for the inner call to Append again! So the inner Append actually never returns!
Apart from that the two lists can’t be appended together as nowhere in this Append function two lists are actually appended together using the | operator. So it’s doubly wrong.
Tags book, CTM, exercise, mozart, oz, termination
[ Posted by Urban Hafner
Wed, 14 Sep 2005 19:25:26 GMT ]
The problem
State invariants. Write down a state invariant for the IterReverse function.
My solution
Define the state invariant P as follows:
P((Rs,Ys)) = (reverse(Xs) = reverse(Ys)|Rs)
- The proof for P_(_S0~) follows from S0~ = (
nil,Xs).
- Assuming P_(_Si~) and S_i~ is not the final state, prove _P(S_i+1). This follows from the semantics of the case statement and the function call. Write _Si~ = (
Rs,Ys). We are not in the final state, so Ys is of nonzero length. From the semantics, Y|Rs adds one element to Rs and the case statement removes this element from Ys. Therefore P_(_Si+1~) holds.
As you might have noticed I’ve used the proof for IterLength and just changed the bits concerning the state invariant. This is OK because the two functions are nearly the same.
Tags book, CTM, exercise, invariant, mozart, oz, state
[ Posted by Urban Hafner
Wed, 14 Sep 2005 19:24:24 GMT ]
The problem
An iterative SumList. Rewrite the function SumList of section 3.4.2 to be iterative using the techniques developed for Length.
My solution
local
fun {IterSumList S Es}
case Es
of nil then S
[] E|Er then {IterSumList S+E Er}
end
end
in
fun {SumList L}
{IterSumList 0 L}
end
end
Tags book, computation, CTM, exercise, iterative, mozart, oz
[ Posted by Urban Hafner
Sun, 11 Sep 2005 17:34:59 GMT ]
The problem
Iterative factorial. This chapter gives a definition of factorial whose maximum stack depth is proportional to the input argument. Give another definition of factorial which results in an iterative computation. Use the techniques of state transformations from an initial state, as shown in the IterLength example.
My solution
fun {IterFact N}
fun {IterFact2 N S}
if N==0 then S
elseif N>0 then {IterFact2 N-1 S*N}
else raise domainError(N) end
end
end
in
{IterFact2 N 1}
end
Tags book, CTM, exercise, mozart, oz
[ Posted by Urban Hafner
Sun, 11 Sep 2005 17:34:45 GMT ]
The problem
The half-interval method. The half-interval method is a simple but powerful technique for finding roots of the equation f(x) = 0, where f_ is a continuous real function. The idea is that, if we are given real numbers _a and b_ such that f(a) < 0 < f(b), then _f must have a least one root between a_ and _b. To locate a root, let x = (a + b)/2 and compute f(x). If f(x) > 0, then f_ must have a root between _a and x_. If f(x) < 0 then _f must have a root between x_ and _b. Repeating this process will define smaller and smaller intervals that converge on a root. Write a declarative program to solve this problem using the techniques of iterative computation.
My solution
local
fun {GoodEnough A B} {Abs A-B} < 0.00001 end
in
fun {HalfInterval A B F}
Mean=(A+B)/2.0 in
if {GoodEnough A B} then
Mean
elseif {F Mean} > 0.0 then
{HalfInterval A Mean F}
else
{HalfInterval Mean B F}
end
end
end
Tags book, CTM, exercise, mozart, oz
[ Posted by Urban Hafner
Fri, 02 Sep 2005 13:26:27 GMT ]
The problem
Cube roots. This chapter uses Newton’s method to calculate square roots. The method can be extended to calculate roots of any degree. For example, the following method calculates cube roots. Given a guess g_ for the cube root of _x, an improved guess is given by (x/g2 + 2g)/3. Write a declarative program to calculate cube roots using Newton’s method.
My solution
Taking the solution from Table 3.8 on page 123 the only thing that has to change is the Improve function. It has to be defined like this:
fun {Improve Guess}
(X/(Guess*Guess) + 2.0*Guess)/3.0
end
Tags book, CTM, exercise, mozart, oz
