[ Posted by urban
Sat, 02 Apr 2005 11:45:49 GMT ]
The problem
Explicit state. This exercise compares variables and cells. We give two code fragments. The first uses variables:
local X in
X=23
local X in
X=44
end
{Browse X}
end
The second uses a cell:
local X in
X={NewCell 23}
X:=44
{Browse @X}
end
In the first, the identifier X refers to two different variables. In the second, X refers to a cell. What does Browse display in each fragment? Explain.
My solution
In the first example 23 is displayed and in the second one 44.
The reason is that in the first example a second variable named X is created that shadows the first one. But the X whose value is 44 exists only during the inner local block. When Browse is executed the X refers to the first X again.
The second example displays of course 44 as we have only one variable X that refers to a cell whose value can be changed.
Tags book, CTM, oz
[ Posted by urban
Sat, 02 Apr 2005 11:41:00 GMT ]
The problem
Higher order programming. Section 1.9 explains how to use higher-order programming to calculate variations of Pascal’s triangle. The purpose of this exercise is to explore these variations.
(a) Calculate individual rows using subtraction, multiplication, and other operations. Why does using multiplication give a triangle with all zeros? Try the following kind of multiplication instead:
fun {Mul1 X Y} (X+1)*(Y+1) end
What does the 10th row look like when calculated with Mul1?
(b) The following loop instruction will calculate and display 10 rows at a time:
for I in 1..10 do {Browse {GenericPascal Op I}} end
Use this loop instruction to make it easier to explore the variations.
My solution
(a) I’ll just list the code here. Most of it is just copied from the book.
declare GenericPascal OpList ShiftLeft ShiftRight in
fun {GenericPascal Op N}
if N==1 then [1]
else L in
L={GenericPascal Op N-1}
{OpList Op {ShiftLeft L} {ShiftRight L}}
end
end
fun {OpList Op L1 L2}
case L1 of H1|T1 then
case L2 of H2|T2 then
{Op H1 H2}|{OpList Op T1 T2}
end
else nil end
end
fun {ShiftLeft L}
case L of H|T then
H|{ShiftLeft T}
else [0] end
end
fun {ShiftRight L} 0|L end
declare Sub1 Sub2 Mul Mul1 in
fun {Sub1 X Y} X-Y end
fun {Sub2 X Y} Y-X end
fun {Mul X Y} X*Y end
fun {Mul1 X Y} (X+1)*(Y+1) end
(b) You have to be careful not to use fun here. Internally fun is converted into a proc with an additional return argument. But this is not what we want here, as EasyBrowse doesn’t have a meaningful return value.
declare
proc {EasyBrowse Op}
for I in 1..10 do {Browse {GenericPascal Op I}} end
end
Tags book, CTM, oz
[ Posted by urban
Sat, 02 Apr 2005 11:37:00 GMT ]
The problem
Lazy evaluation. Section 1.8 defines a lazy function Ints that lazily calculates an infinite list of integers. Let us define a function that calculates the sum of a list of integers:
fun {SumList L}
case L of X|L1 then X+{SumList L1}
else 0 end
end
What happens if we call {SumList {Ints 0}}? Is this a good idea?
My solution
When calling {{SumList {Ints 0}} we end up with an infinite recursion because we want to add up all numbers in the list {Ints 0}. This is of course not possible as each call to {SumList L1} (in the second line of the SumList function) generates a successive element of the list through X|L1.
Tags book, CTM, oz
[ Posted by urban
Sat, 02 Apr 2005 11:34:00 GMT ]
The problem
Program complexity. What does section 1.7 say about programs whose time complexity is a higher-order polynomial? Are they practical or not? What do you think?
My solution
It of course depends on the program and how high the complexity is. What can be said is that for big input values they are very likely better than programs with exponential complexity.
Tags book, CTM, oz
[ Posted by urban
Sat, 02 Apr 2005 11:32:00 GMT ]
The problem
Program correctness. Section 1.6 explains the basic ideas of program correctness an applies them to show that the factorial function defined in section 1.3 is correct. In this exercise, apply the same ideas to the function Pascal of section 1.5 to show that it is correct.
My solution
I must admit that I have never been very confident when proving things. So take the following prove with a grain of salt and don’t assume that it is good style to be so sloopy.
{Pascal 1} is correct as it returns [1].- Assume that
{Pascal N-1} is correct (and assume that AddList, ShiftLeft and ShiftRight are correct, too).
To calculate the n-th row of Pascal’s triangle you take the (n-1)-th row and prepend 0 on the left and you take the (n-1)-th row (again) and append 0 on the right. Then you just add the two lists (i.e. the corresponding elements of the two rows) and you have the n-th row of Pascal’s triangle. This is just what Pascal does.
q.e.d.
Tags book, CTM, oz
[ Posted by urban
Sat, 02 Apr 2005 11:28:00 GMT ]
The problem
Calculating combinations. Section 1.3 defines the function Comb to calculate combinations. This function is not very efficient because it might require calculating very large factorials. The purpose of this exercise is to write a more efficient version of Comb.
(a) As a first step, use the following alternative definition to write a more efficient function (imagine a nicely formated formula):
(n k) = n*(n-1)*...*(n-k+1)/k*(k-1)*...*1
Calculate the numerator and denominator separately and then divide them. Make
sure the result is 1 when k=0.
(b) As a second step, use the following identity:
(n k) = (n n-k)
to increase efficiency even more. That is, if k > n/2, then do the calculation with n-k instead of with k.
My solution
(a) Fact and AtoB are helper functions.
declare
fun {Fact N}
if N==0 then 1 else N*{Fact N-1} end
end
declare
fun {AtoB A B}
if A < B then
1
else
if A == B then A else A*{AtoB A-1 B} end
end
end
declare
fun {FasterComb N K}
{AtoB N N-K+1} div {Fact K}
end
(b) The function FasterComb is from part (a).
declare
fun {FastComb N K}
if K > (N div 2) then
{FastComb N N-K}
else
{FasterComb N K}
end
end
Tags book, CTM, oz
[ Posted by urban
Sat, 02 Apr 2005 10:43:00 GMT ]
The problem
A calculator. Section 1.1 uses the system as a calculator. Let us explore the
possibilities:
(a) Calculate the exact value of 2100 without using any new functions Try to think of shortcuts to do it without having to type 2*2*2*...*2 with one hundred 2s. Hint: use variables to store intermediate results.
(b) Calculate the exact value of 100! without using any new functions. Are there any possible shortcuts in this case?
My solution
(a) As said in the hint, you have to store intermediate results:
declare
local V W X in
V={NewCell 2}
W = {NewCell 0}
X = {NewCell 0}
V := @V*@V % 2^2
V := @V*@V % 2^4
W := @V
V := @V*@V % 2^8
V := @V*@V % 2^16
V := @V*@V % 2^32
X := @V
V := @V*@V % 2^64
V := (@V*@W*@X) % 2^64 * 2^4 * 2^32 = 2^100
{Browse @V}
end
(b) Right now I can’t see a shortcut for computing 100!.
Tags book, CTM, oz
[ Posted by urban
Sat, 02 Apr 2005 10:40:00 GMT ]
by Peter van Roy and Seif Haridi
This is the thickest computer science book that I ever tried to read. Up to now I didn’t succeed in reading it. That’s why I’m now trying to post all the exercises in my blog to give me the feeling that I have to continue because people might want to read my results.
Wish me luck!
Tags book, CTM, oz
