Ch3, Ex17 (todo)

todo

Ch3, Ex16

% Using name Convolute1 as Convolute is already
% there in mozart system

declare Append Convolute1 Reverse

%copied from exercise-9
local IterReverse MyAppend in
   fun {MyAppend L1 L2}
      case L1 of nil then L2
      [] X|Y then {MyAppend Y X|L2}
      end
   end
   fun {IterReverse X Y}
      case X of nil then Y
      [] X1|X2 then {IterReverse X2 X1|Y}
      end
   end
   fun{Append Xs Ys}
      {MyAppend {IterReverse Xs nil} Ys}
   end
   fun {Reverse Xs}
      {IterReverse Xs nil}
   end   
end

% Notice the use of dataflow variable Y to make it
% tail-recursive
local
   proc {Convolute2 L1 L2 ?L3}
      case L1 of nil then L3 = nil
      [] XL1|YL1 then XL2 YL2 Y in
         L2 = XL2|YL2
         L3 = {Append [XL1#XL2] Y}
         {Convolute2 YL1 YL2 Y}
      end
   end
in
   fun {Convolute1 L1 L2}
      X in
      {Convolute2 L1 {Reverse L2} X}
      X
   end
end


{Browse {Convolute1 [1 2 3] [1 2 3]}}


/* Another iterative convolute without dataflow
   variable, notice the use of accumulator
   programming. In each recursive call we
   keep on modifying state variable S1, when base
   case is reached, we say its the final state
   by making Sn = S1 */
local
   proc {Convolute2 L1 L2 ?S1 ?Sn}
      case L1 of nil then Sn = S1
      [] XL1|YL1 then XL2 YL2 in
         L2 = XL2|YL2
         {Convolute2 YL1 YL2 {Append [XL1#XL2] S1} Sn}
      end
   end
in
   fun {Convolute1 L1 L2}
      X in
      {Convolute2 L1 {Reverse L2} nil X}
      X
   end
end

Ch3, Ex15

declare Partition QuickSort

% Puts all elems<Pivot in L1 and others in L2 
proc {Partition Pivot L ?L1 ?L2}
   case L of nil then
      L1 = nil
      L2 = nil
   [] X|Y then Y1 in
      if X < Pivot then
         L1 = X|Y1
         {Partition Pivot Y Y1 L2}
      else
         L2 = X|Y1
         {Partition Pivot Y L1 Y1}
      end
   end
end  

local
   fun {QuickSortD L}
      case L of nil then E in E#E
      [] X|nil then E in (X|E)#E
      [] X|Y then L1 L2 S1 S2 E1 E2 E3 in
         {Partition X Y L1 L2}
         %Sort L1 and L2 and then return L1+X+L2
         S1#(X|E1) = {QuickSortD L1}
         S2#E2 = {QuickSortD L2}
         E1 = S2
         S1#E2
      end
   end
in
   fun {QuickSort L}
      S#nil = {QuickSortD L}
   in
      S
   end
end


% Test Partition 
local D1 D2 E in
   {Partition 5 [5 2 7 3 4] D1 D2}
   {Browse D1}
   {Browse D2}
end

% Test QuickSort
{Browse {QuickSort nil}}
{Browse {QuickSort [1]}}
{Browse {QuickSort [2 1]}}
{Browse {QuickSort [5 2 7]}}
{Browse {QuickSort [5 2 7 3 4]}}

%=====================================
% Partition that takes difference list and
% returns difference lists
% not used in our program though
proc {Partition N D ?D1 ?D2}
   case D of nil then E1 E2 in
      D1 = E1#E1
      D2 = E2#E2
   [] X|Y then Y1 Y2 in
      if X < N then
         D1 = (X|Y1)#Y2
         {Partition N Y Y1#Y2 D2}
      else
          D2 = (X|Y1)#Y2
          {Partition N Y D1 Y1#Y2}
      end
   end
end

Ch3, Ex14

a) It works because of the dataflow behavior. If you delete one element from an empty queue. Returned queue is q(~1 _ _|_) and returned element is unbound. As soon as we do one insert, these entities are bound.

b)For empty queues it returns the right results. But for non empty queues it blocks as its trying to compare something like 1|2|E == E where E is unbound. The entailment blocks because the answer depends upon the binding of E. If E is bound to anything except 1|2|E then the answer is false. But it can not decide before that binding happens.

Ch3, Ex13

First I'm going to define my representation of Matrix and then Transpose, Multiply operation code.

Matrix data type:
Matrix := {List |}nil
with the constraint that {Length List} > 0 and same for all the lists in the sequence.
for example:

_         _ 
| x1 x2 x3 |
| y1 y2 y3 |  ===>> [[x1 x2 x3] [y1 y2 y3] [z1 z2 z3]]
| z1 z2 z3 |
-          -

======================================================================
Transpose Operation:
Thinking recursively and state transition, this is how the transpose code works..

STEP1: Input: [[1 2 3] [4 5 6]]    Sn: nil
STEP2: Input: [[2 3] [5 6]]        Sn: [[1 4]]
STEP3: Input: [[3] [6]]            Sn: [[1 4] [2 5]]
STEP4: Input: [nil nil]            Sn: [[1 4] [2 5] [3 6]]
When termination condition is reached that is when  input
is [nil nil ...] then we have answer in Sn.

declare Transpose
local Iter IterTranspose in
   proc {Iter M ?Mn ?Sn}
      case M of nil then
         Sn = nil
         Mn = nil
      [] X|Xs then
         case X of X1|Xs1 then Ss Ms in
            Sn = X1|Ss
            Mn = Xs1|Ms
            {Iter Xs Ms Ss}
         end
      end
   end

   /*Test Iter
   {Iter [[1 2 3] [4 5 6]] P Q}
   {Browse P} %[[2 3] [5 6]] 
   {Browse Q} % [1 4] */
   proc {IterTranspose M ?S}
      case M of nil then S = nil
      [] nil|Z then S = nil
      else Mi Si Y in
         {Iter M Mi Si}
  S = Si|Y
            {IterTranspose Mi Y} 
      end
   end

   fun {Transpose M}
      S
   in
      {IterTranspose M S}
      S
   end   
end

% Test Transpose
{Browse {Transpose [[1]]}} % [[1]]
{Browse {Transpose [[1 2]]}} % [[1] [2]]
{Browse {Transpose [[1] [2]]}} % [[1 2]]
{Browse {Transpose [[1 2 3] [4 5 6]]}} %[[1 4] [2 5] [3 6]]
{Browse {Transpose
  [[1 2 3] [4 5 6] [7 8 9]]}} %[[1 4 7] [2 5 8] [3 6 9]]

==========================================================================
Multiplication Operation:
Basically multipication of m1 X n and n X m2 can be thought of as

{Append
 { Multiply [1st row of Matrix-1] Matrix-2}
 { Multiply [2nd row of Matrix-1] Matrix-2}
 ......
 ......
 { Multiply [m1th row of Matrix-1] Matrix-2}}

So we write an operation SingleRowMultiply that multiply a matrix(of order 1Xn) with any matrix(of order nXm), then use it and do the append.

declare Multiply
local SingleRowMultiply IterSRM  MultiplyLists SumList
   MultiplyAndSumLists in
   
   fun {MultiplyLists L1 L2}
      proc {Iter L1 L2 ?S}
         case L1 of nil then S = nil
         [] X1|Y1 then
            case L2 of X2|Y2 then Z in
               S = (X1*X2)|Z
               {Iter Y1 Y2 Z}
            end
          end
      end
      S
   in
      {Iter L1 L2 S}
      S
   end
   %{Browse 'MultiplyLists Test, Result = [4 10 18]'}
   %{Browse {MultiplyLists [1 2 3] [4 5 6]}}

   fun {SumList L}
      fun {IterSumList X Y}
         case X of nil then Y
         [] Xs|L2 then {IterSumList L2 Y+Xs}
         end
      end
   in
      {IterSumList L 0}
   end
   %{Browse 'SumList Test, Result = 14'}
   %{Browse {SumList [2 3 4 5]}} %14

   fun {MultiplyAndSumLists L1 L2}
      {SumList {MultiplyLists L1 L2}}
   end
   %{Browse 'MultiplyAndSumLists Test, Result = 32'}
   %{Browse {MultiplyAndSumLists [1 2 3] [4 5 6]}}

   proc {IterSRM L M ?S}
      case M of nil then S = nil
      [] X|Y then Z in
         S = {MultiplyAndSumLists L X}|Z
         {IterSRM L Y Z}
      end
   end
 
   fun {SingleRowMultiply L M} S in
      {IterSRM L {Transpose M} S}
      [S]
   end

   fun {Multiply M1 M2}
      case M1 of nil then nil
      [] X|Y then
         {Append {SingleRowMultiply X M2} {Multiply Y M2}}
      end
   end
end
%Tests Multiply (with identity matrix)
{Browse {Multiply [[1 2] [3 4]] [[1 0] [0 1]]}}

Ch3, Ex12

Worst case happens when all n elements are nested with depth k. For example let say k=2 and n=3 then list of 1,2,3 would look like [[[1]] [[2]] [[3]]]

Complexity of the version that works with simple versions of list is O(n*k) because for each element there are k "unnestings" to be done. Or may be understand as follow
T(n,k) = T(1,k-1) + T(n-1,k)+ A(1,n-1) + c where A(m,n) denotes time taken to append a list of n elems on a list of m elems. T(n,k) = nT(1,0)+(n*k-n-1)T(0,0)+constant which is O(n*k)

Complexity of the version that works with difference lists is also O(n*k) with same reasoning as above but the constant value is relatively too small because cost of append operations is saved completely.

Ch3, Ex11

%Run this
declare Append
fun {Append D1 D2}
   S1#E1=D1
   S2#E2=D2
   E1=S2
in   
   S1#E2
end
local E1 E2 D1 D2 in
   D1 = (1|2|3|E1)#E1
   D2 = (4|5|6|E2)#E2
   {Browse {Append {Append D1 D2} D2}}
end

%and then, this
local E in
   E = 1|2|3|E
   {Browse E}
end

You realize that you create a cyclic structure when you append the same list again as {Append D1 D2} results in (1|2|3|4|5|6|E2)#E2 and then you're appending (4|5|6|E2)#E2 to it.

Ch3, Ex10 (to be revisited)

I guess, Yes. We can maintain state with accumulators. Not sure though. Can we find an example where its not possible to keep the function iterative without dataflow variables.

Ch3, Ex9

declare Append
local IterReverse MyAppend in
   fun {MyAppend L1 L2}
      case L1 of nil then L2
      [] X|Y then {MyAppend Y X|L2}
      end
   end
   fun {IterReverse X Y}
      case X of nil then Y
      [] X1|X2 then {IterReverse X2 X1|Y}
      end
   end
   fun{Append Xs Ys}
      %{Browse {IterReverse Xs nil}}
      {MyAppend {IterReverse Xs nil} Ys}
   end
end
%Test
{Browse {Append [1 2 5 6 7] [3 4]}}

Ch3, Ex8

This program does not terminate, when Append is called on a list(with just one element) as the second argument and it always happens eventually, for example calling {Append [1 2] [3]} will match [3] to 3|nil then call {Append {Append [1 2] [3]} nil} and this keeps on happening forever.

Ch3, Ex7 (to be revisited)

'\=' tries to do the entailment which is implemented as doing the unification and returning false if unification completes successfully, so X\=_|_ just hangs as underscore is just an anonymous variable and can't be bound and hence unification algorithm gets stuck.

Note: Please give a better answer as I'm not really very convinced with mine :).

Ch3, Ex6

{Append {Reverse Rs} Ys} is always the original list.

Ch3, Ex5

declare SumList
fun {SumList L}
   fun {IterSumList X Y}
      case X of nil then Y
      [] Xs|L2 then {IterSumList L2 Y+Xs}
      end
   end
in
   {IterSumList L 0}
end
{Browse {SumList [2 3 4 5]}}

Ch3, Ex4

declare Factorial
fun {Factorial N}
   fun {IterFactorial X Y}
      if X<1 then Y
      else
         {IterFactorial X-1 Y*X}
      end
   end
in
   {IterFactorial N 1}
end
{Browse {Factorial 5}}

Ch3, EX3

declare FindRootWithHalfInterwal
fun {FindRootWithHalfInterwal F A B}
   Av = (A+B)/2.0
   Temp = {F Av}
in
   % Print things for debugging
   %{Browse average}
   %{Browse Av}
   %{Browse temp}
   %{Browse Temp}
   if Temp<0.0 then {FindRootWithHalfInterwal F Av B}
   elseif Temp>0.0 then {FindRootWithHalfInterwal F A Av}
   else Av
   end
end
%Test
{Browse {FindRootWithHalfInterwal
         fun{$ X} 3.0*X-15.0 end 4.5 6.0}}

Ch3, Ex2

declare CubeRoot
fun {CubeRoot N}
   %can come from outside to make it more modular
   Precision = 0.00001
   InitialGuess = 1.0
   %convert N to float
   X = if {Int.is N} then {Int.toFloat N} else N end
   fun {GoodEnough Guess}
      {Number.abs (Guess*Guess*Guess-X)} < Precision
   end
   fun {Improve Guess}
      (X/(Guess*Guess)+2.0*Guess)/3.0
   end
   fun {NewtonCubeRoot Guess}
      %{Browse Guess} %Print the Guesses made, just to debug
      if {GoodEnough Guess} then Guess
      else {NewtonCubeRoot {Improve Guess}}
      end
   end
   in
   {NewtonCubeRoot InitialGuess}
end
%Tests
{Browse {CubeRoot 0.008}}
{Browse {CubeRoot 27}} 

Ch3, Ex1

Its wrong because there is no implicit type casting(that implicitly converts a float to int) in oz and given program will only work for integers. Correct Abs should check whether the input is an int or float and then do the appropriate check.

declare
fun {Abs X}
   case {Int.is X} of
      true andthen X<0 then ~X
   []true then X
   []false andthen X<0.0 then ~X
   []false then X
   end
end 

Ch2, Ex13

From the algorithm given in the book its clear that unification is a symmetric operation, so whatever order we follow; following is the resulting set of bindings:
X = Y = [a b]
W = a
Z = b

it can also be confirmed from mozart system by executing following

local X Y W Z in
   % try different order of unifications
   X = [a Z]
   Y = [W b]
   X = Y
   % No matter what the above sequence is, following sequence
   % always prints
   % true
   % [a b]
   % a
   % b
   {Browse X==Y}
   {Browse X}
   {Browse W}
   {Browse Z}
end 

Ch2, Ex12

Another version of (different from that in book)

try <s1> finally <s2> end

=================>
local T E in
   try
      <s1>
      T = false
   catch X then
      E = X
      T = true
   end
   <s2>
   if T then raise E end end
end 

Note: This exercise is missing from pdf version of the book online and 13th(unification problem) problem given in the book is the 12th one in pdf version.

Ch2, Ex11

Kernel transform of IsEven:

proc {IsEven X ?R}
   local T in
      T = X==0
      if T then true else S=X-1 in {IsOdd S R} end
   end
end 

this is clearly tail recursive, similarly we can see IsOdd is also tail recursive, hence calls {IsOdd N} and {IsEven N} will execute with constant stack size.

Ch2, Ex10

declare
proc {SMerge Xs Ys ?R}
   local T in
      T = Xs#Ys
      case T
      of nil#Ys then R = Ys
      else
         case T of Xs#nil then R = Xs
         else
            case T of
               (X|Xr)#(Y|Yr) then
               local K in
                  K = X=<Y
                  if K then S in
                     R = X|S
                     {SMerge Xr Ys S}
                  else S in
                     R = Y|S
                     {SMerge Xr Ys S}
                  end
               end
            end
         end
      end      
   end
end

Notice the usage of dataflow variable S to keep recursive call to be last so as to make it tail-recursive, this trick is used when a function call is made inside a data-structure(for reference read the section "Function calls in data structures" in the book).

Ch2, Ex9

(a)Sum1 in kernel language:

proc {Sum1 N ?R}
   local T in
      T = N==0
      if T then R=0
      else
  local L in
     L = {Sum1 N-1}
     R = N + L
  end
      end
   end
end 

As recursive call is not the last call, hence its not tail-recursive.

Sum2 in kernel language:

proc {Sum2 N S ?R}
   local T in
      T = N==0
      if T then R=S
      else
  {sum2 N-1 N+S}
      end
   end
end 

As there is just one recursive call and its the last, hence its tail-recursive.

(b)
In case of Sum1 stack size will grow linearly while in case of Sum2 it remains constant. Store size grows linearly in both the cases but several variables in the store are unreachable when Sum2 is executing.
TODO: hand execute the calls

(c)On my system {Sum2 100000000 0} was successfully able to calculate the result(5000000050000000) and {Sum1 100000000} just hanged (probably due to unavailability of enough memory as Sum1 is not tail recursive)

Ch2, Ex8

(a) Yes, same result and it avoids evaluation of <expression2> when <expression1> returns false.

(b)

fun {OrElse BP1 BP2}
   if {BP1} then true else {BP2} end
end

Ch2, Ex7

Translating given program to closer to kernel code

declare Max3 Max5
proc {SpecialMax Value ?SMax}
   proc {SMax X ?R}
      if X>Value then R=X else R=Value end
   end
end
% *value = 3* in contextual environment of this
% resulting proc
{SpecialMax 3 Max3}
% *value = 5* in contextual environment of this
% resulting proc
{SpecialMax 5 Max5}

Ans: [4 5] will be printed, its trivial to figure out now why (Hint: lexical scoping)

Ch2, Ex6

declare X Y {Test f(X b Y)}
It waits for x1, y1 to bind and then depending upon the bindings it'll print 'case'(1) if we bind X->a and Y->b else 'case'(2)


declare X Y {Test f(a Y d)}
It fails immediately because a=a, Y=Y (no matter what the binding is) and d is never equal to c.

declare X Y {Test f(X Y d)}
It waits for X to bind and then eventually will fail as c is not equal to d.and will print 'case'(2)

Note: I cheated in giving the above answers, I ran the code and then tried to come up with these answers. I am still not sure what is the exact pattern matching algorithm used by the case statement. I hope someone will provide better explainations.

declare X Y
if f(X Y d)==f(a Y c) then {Browse 'case '(1)}
else {Browse 'case'(2)} end
It fails immediately, because "==" uses entailment algorithm which is smart enough to find out that this matching is gonna fail no matter what X binds to.

Ch2, Ex5

Only thing to remember is that clauses are tested sequentially starting with the first clause. Execution passes to next clause only if all the clauses before it failed to match with input pattern. With this its fairly trivial to think the answers, but I'm giving them here anyway..

{Test [b c a]} % 'case'(4)
{Test f(b(3))} % 'case'(5)
{Test f(a)} % 'case'(2)
{Test f(a(3))} % 'case'(5)
{Test f(d)} % 'case'(5)
{Test [a b c]} % 'case'(1)
{Test [c a b]} % 'case'(4)
{Test a|a} % 'case' (1)

Ch2, Ex4

(a)

if <x> then <s1> else <s2> end
 ========> 
case <x> of true then <s1> else <s2> end

(b)

case <x> of <pattern> then <s1> else <s2> end
=============>
local T in
   T = {Label <x>} == {Label <pattern>}
   if T then
      local T in
         T = {Arity <x>} == {Arity <pattern>}
         if T then 
            <x> = <pattern>
            <s1>
         else <s2> end
      end
   else
      <s2>
   end
end

Ch2, Ex3

Functions are always supposed to return a value. If predicate is false and there is no else statement then no value is returned which is not the intended behavior of functions. On the other hand procedures are entities which just cause side effects and return no value, so in their case the mentioned situation is not an error.

Ch2, Ex2

Its a necessary step because N is Free variable identifier and it may or may not exist in the environment of the caller. Hence to make sure of the presence of N, N-> 3 (in general mapping for all Free identifiers) is added to contextual environment.This is in terms with Lexical scoping or else it'll become dynamic scoping.

An example where N does not exist at time of call:

declare MulByN in
local N in
   N = 3
   proc {MulByN X ?Y}
      Y = N*X
   end
end
{Browse {MulByN 5 $}}

An exmple where N is not bound to 3 at the time of the call

declare MulByN N in
local N in
   N = 3
   proc {MulByN X ?Y}
      Y = N*X
   end
end
N = 6
{Browse {MulByN 5 $}}

Ch2, Ex1

Kernel language transform of given program:

P = proc { $ X }
       local T in
      T = X>0
      if T then {P X-1} end
       end
    end

proc statement creates a value of procedure type and binds it to the identifier P. Second occurence of P is Free with respect to the proc statement as declaration of P is not inside it (from defn of free variable on page #64).

Ch1, Ex10

%(a)
We almost never see 1 because chances of happening thread interleaving are very low.

% (b)

declare
C={NewCell 0}
thread I in
  I=@C
  {Delay 5000}
  C:=I+1
end
thread J in
  J=@C
  C:=J+1
  {Delay 5000}
end

Above code almost always results in C being 1 and reason is pretty trivial to figure out.

% (c) -
Since there is a lock, so other thread can't enter the locked block unless the first thread releases it so interleaving is not possible and hence we never see 1 even if we add delay.

Ch1, Ex9

(a)On a high level Memory Store is kind of a hashtable where we can store key-value pairs with the restriction that key can only be a natural number (i.e. 1,2,3,4.....)

One thing to note is that Size returns the total number of pairs added to the store so far and not the highest numbered cell used, this is evident from following code

declare
S={NewStore}
{Put S 10 [22 33]}
{Browse {Size S}} %prints 1 not 10

(b)

declare
GenericPascal OpList ShiftLeft ShiftRight
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
fun {Add X Y} X+Y end

declare
fun {FastPascal N}
 {GenericPascal Add N}
end

declare
local S = {NewStore} in
 fun {FasterPascal N}
    if N > {Size S} then
  for I in ({Size S}+1)..N
  do
     {Put S I {FastPascal I}}
  end
    end
    {Get S N}
 end
end

{Browse {FasterPascal 10}}
{Browse {FasterPascal 5}}

(c) I'm storing contents in the cell as [N1#X1 ..... Nn#Xn]

declare MyNewStore MyPut MyGet MySize
local
 fun {GetPair Xs Key}
    case Xs of
  K#V|Xr andthen Key==K then K#V
  [] K#V|Xr then {GetPair Xr Key}
  [] nil then nil
    end
 end
 fun {RemovePair Xs Key}
    proc {Iter Xs A}
  case Xs of
     K#V|Xr andthen Key==K then A = Xr
  [] K#V|Xr then Y in
     A = K#V|Y
     {Iter Xr Y}
  [] nil then A=nil
  end
    end
    X
 in
    {Iter Xs X}
    X
 end
 fun {Length Xs}
    fun {Iter Xs A}
  case Xs of
     X|Xr then {Iter Xr A+1}
     [] nil then A
  end
    end
 in
    {Iter Xs 0}
 end
in
 fun {MyNewStore}
    {NewCell nil}
 end
 proc {MyPut S Key Val}
    S := (Key#Val)|{RemovePair @S Key}
 end
 fun {MyGet S Key}
    X = {GetPair @S Key}
 in
    if X==nil then '*not-found*' %ideally we should throw error here
    else
  X.2
    end
 end
 fun {MySize S}
    {Length @S}
 end 
end

(d)

%Slightly modified counter code
declare
fun {NewCounter}
 C = {NewCell 0}
 proc {Bump}
    C := @C+1
 end
 fun {Read}
    @C
 end
in
 counter(bump:Bump read:Read)
end

%How to use the counter
%getting a counter
local C1 C2 in
 C1 = {NewCounter}
 C2 = {NewCounter}
 % Bump C1 once and C2 twice
 {C1.bump}
 {C2.bump}
 {C2.bump}
 % Read and print
 {Browse {C1.read}} % should be 1
 {Browse {C2.read}} % should be 2
end



% Modified my store impl to keep track of size using counters
declare MyNewStore MyPut MyGet MySize
local
 fun {GetPair Xs Key}
    case Xs of
  K#V|Xr andthen Key==K then K#V
  [] K#V|Xr then {GetPair Xr Key}
  [] nil then nil
    end
 end
 fun {RemovePair Xs Key}
    proc {Iter Xs A}
  case Xs of
     K#V|Xr andthen Key==K then A = Xr
  [] K#V|Xr then Y in
     A = K#V|Y
     {Iter Xr Y}
  [] nil then A=nil
  end
    end
    X
 in
    {Iter Xs X}
    X
 end
in
 fun {MyNewStore}
    {NewCell nil}|{NewCounter}
 end
 proc {MyPut S Key Val}
    case S of
  Store|Counter andthen {GetPair @Store Key} == nil
    then
  Store := (Key#Val)|@Store
  {Counter.bump}
    [] Store|Counter then
  Store := (Key#Val)|{RemovePair @Store Key}
    end
 end
 fun {MyGet S Key}
    case S of Store|Counter
    then X in
  X = {GetPair @Store Key}
  if X==nil then '*not-found*' %ideally we should throw error here
  else
     X.2
  end
    end
 end
 fun {MySize S}
    case S of Store|Counter then {Counter.read} end
 end
end

Ch1, Ex8

Acc is creating new cell with content 0 in each Accumulate call and losing the previous accumulated values. Here is the correct version:

declare
local Acc = {NewCell 0} in
   fun {Accumulate N}
      Acc:=@Acc+N
      @Acc
   end
end

Ch1, Ex7

In first code 23 is displayed because X=44 was assigned to the identifier that
was local in the block.

In 2nd code 44 is displayed as contents of the cell are changed and same is
displayed.

Ch1, Ex6

(a) For Mul, All are zero because for the 2nd row elements would be [0*1 1*0] and subsequently all the rows will become zero.
Unfortunately I have no way to copy from oz buffer yet, so couldn't show 10th
row for Mul1. But it can be seen by running following program...

declare
GenericPascal OpList ShiftLeft ShiftRight
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
fun {Mul X Y} X*Y end

declare
fun {Mul1 X Y} (X+1)*(Y+1) end

{Browse {GenericPascal Mul 10}}
{Browse {GenericPascal Mul1 10}}

Ch1, Ex5

What happens: Its stuck trying to calculate sum of an infinite list.

Good Idea? Definitely No.

Ch1, Ex4

I guess, Low order polynomial order of time complexity is practical only.

Ch1, Ex3

Proof By Induction:
We see {Pascal 1} = [1] is correct and so is {Pascal 2} = [1 1].
Assume {Pascal N-1} is correct. Then
{Pascal N} = {AddList {ShiftLeft {Pascal N-1}} {ShiftRight {Pascal N-1}}}
is nth row of pascal's triangle. Hence {Pascal N} is correct.

Note: Actually we should also prove that all three auxiliary functions are
also correct, which will be similar arguments.

Ch1, Ex2

%(a)

declare
fun {Fact N}
   if N == 0 then 1 else N*{Fact N-1} end
end

declare
fun {PartialFact N R} % N > R > 0
   % local variables to be used must be declared
   % in the start
   F in
   fun {F K}
      if K==(N-R+1) then K else K*{F K-1} end
   end
   {F N}
end

declare
fun {FastComb N R}
 if R > 0 then {PartialFact N R} div {Fact R}
   else N end
end

%(b)
declare
fun {FasterComb N R}
   if R > (N div 2) then {FastComb N (N-R)} else {FastComb N R} end
end

{Browse {FasterComb 5 3}} %10
{Browse {FasterComb 5 0}} %5

Ch1, Ex1

(a)
declare
A=2 %2^1
B=A*A
C=B*B
D=C*C
E=D*D
F=E*E %2^32
G=F*F %2^64
{Browse G*F*C} %result = 2^(64+32+4)

(b) Couldn't find a shortcut