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