ctmcp4.11.oz

% ex. 1
local B in
   thread
      B=true        % 1
   end
   thread
      B=false       % 2
   end
   if B then        % 3
      {Browse yes}  % 4
   end
end

% a) この文のあり得る実行を列挙せよ
% 何も出力せずに異常終了:
%   (1, 2), (2, 1)
%   (2, 3, 1)
%   (3, 1, 2)
%   (3, 2, 1)
% yes と表示してから異常終了
%   (1, 3, 4, 2): 
%   (3, 1, 4, 2)

% b) 1 あるいは 2 を削除

% ex. 2

declare
proc {B _}
   {Wait _}  % 永遠にブロックする
end
proc {A}
   Collectible={NewDictionary}
in
   {Browse invoke}
   {B Collectible}
   {Browse done}
end
{A}

% ex. 3

declare
fun {FibC X}  % 並列版
   if X=<2 then 1
   else thread {FibC X-1} end + {FibC X-2} end
end
fun {FibS X}  % 直列版
   if X=<2 then 1
   else {FibS X-1}+{FibS X-2} end
end

local S E in
   S={Time.time}
   {Browse {FibC 30}}
   E={Time.time}
   {Browse elapsed#(E-S)}
end

local S E in
   S={Time.time}
   {Browse {FibS 30}}
   E={Time.time}
   {Browse elapsed#(E-S)}
end

% T(N) を N が与えられた際のスレッド生成量 (≒ 空間計算量) とすると
% T(N) = T(N-1) + T(N-2), T(1) = T(2) = c
% c = O(d^N)
% O(d^(N-1)) + O(d^(N-2)) = O(d^N)
% よって T(N) = O(d^N)

% ex. 4

declare A B C D in
thread D=C+1 end  % 1
thread C=B+1 end  % 2
thread A=1 end    % 3
thread B=A+1 end  % 4
{Browse D}

% スレッドの生成は 1, 2, 3, 4 の順に行われる
% データフロー変数の依存関係によって適宜ブロックするので計算の順序は 3, 4, 2, 1 となる。結果は4

declare A B C D
A=1
B=A+1
C=B+1
D=C+1
{Browse D}

% 結果は同じく4。単一スレッド上では計算は記述順に進行する
% データフロー変数を介することでスレッド間の実行順序が調整される

% ex. 5

% if は条件節が評価できるまで then/else のいずれも実行しない。そのため X に値が束縛されるまでブロックする
% この手続きは X に束縛された値には興味がないので then と else の両方で同じように skip して (i.e., 何もしないで) 終了する
declare
proc {MyWait X}
   if X==unit then skip
   else skip end
end

declare C
thread
   {Delay 3000}
   C=done
end
{MyWait C}
{Browse done}

% ex. 6
% 4.8.3.2 未達のためスキップ

% ex. 7

% よく考えたら iterator じゃない

declare
fun {GenerateIterator N}
   fun {$} N|{GenerateIterator N+1} end
end
fun {DSum Iter Acc Limit}
   case {Iter} of N|Iter2 then
      if Limit>0 then
         {DSum Iter2 Acc+N Limit-1}
      else
         Acc
      end
   end
end

local
   Iter={GenerateIterator 0}
in
   {Browse {DSum Iter 0 15000}}
end

% ex. 8

declare
fun {Filter In F}
   case In
   of X|In2 then
      if {F X} then X|{Filter In2 F}
      else {Filter In2 F} end
   else
      nil
   end
end

{Show {Filter [5 1 2 4 0] fun {$ X} X>2 end }}

% a) 次を実行するとどうなるか

declare A
{Show {Filter [5 1 A 4 0] fun {$ X} X>2 end }}

% 何も出力しない内にブロックする

% b) 次を実行するとどうなるか

declare Out A
thread Out={Filter [5 1 A 4 0] fun {$ X} X>2 end } end
{Show Out}

% {Filter [5 1 A 4 0] F} が再帰的に {Filter [A 4 0] F} が呼ばれた時点でブロックする
% Show の実行時点で Out は _ か 5|_ のいずれか

% c) 次を実行するとどうなるか

declare Out A
thread Out={Filter [5 1 A 4 0] fun {$ X} X>2 end } end
{Delay 1000}
{Show Out}

% メインスレッドが Delay でブロックされている間に Filter を実行するスレッドが走り、b) と同様 {Filter [A 4 0] F} の時点でブロックする。したがって Show の時点で Out はおそらく 5|_ である

% d) 次を実行するとどうなるか

declare Out A
thread Out={Filter [5 1 A 4 0] fun {$ X} X>2 end } end
thread A=6 end
{Delay 1000}
{Show Out}

% [5 6 4] 。メインスレッドがブロックされている間に A が束縛され Filter が全ての要素を舐めるから

% ex. 9

declare
fun {NotLoop Xs}
   case Xs of X|Xr then (1-X)|{NotLoop Xr} end
end
fun {NotG Xs}
   thread {NotLoop Xs} end
end
fun {GateMaker F}
   fun {$ Xs Ys}
      fun {GateLoop Xs Ys}
         case Xs#Ys of (X|Xr)#(Y|Yr) then
            {F X Y}|{GateLoop Xr Yr}
         end
      end
   in
      thread {GateLoop Xs Ys} end
   end
end
AndG={GateMaker fun {$ X Y} X*Y end}
OrG={GateMaker fun {$ X Y} X+Y-X*Y end}
NandG={GateMaker fun {$ X Y} 1-X*Y end}
NorG={GateMaker fun {$ X Y} 1-X+Y-X*Y end}
XorG={GateMaker fun {$ X Y} X+Y-2*X*Y end}
proc {FullAdder X Y Z ?C ?S}
   K L M
in
   K={AndG X Y}
   L={AndG Y Z}
   M={AndG X Z}
   C={OrG K {OrG L M}}
   S={XorG Z {XorG X Y}}
end

% n = 4 
local
   X1s=0|1|0|1|0|1|0|1|0|1|0|1|0|1|0|1|_
   X2s=0|0|1|1|0|0|1|1|0|0|1|1|0|0|1|1|_
   X3s=0|0|0|0|1|1|1|1|0|0|0|0|1|1|1|1|_
   X4s=0|0|0|0|0|0|0|0|1|1|1|1|1|1|1|1|_
   Y1s=1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|_
   Y2s=1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|_
   Y3s=0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|_
   Y4s=0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|_
   C0s=0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|_
   C1s C2s C3s C4s
   S1s S2s S3s S4s
   {FullAdder X1s Y1s C0s C1s S1s} % 1 (LSB)
   {FullAdder X2s Y2s C1s C2s S2s} % 2
   {FullAdder X3s Y3s C2s C3s S3s} % 3
   {FullAdder X4s Y4s C3s C4s S4s} % 4 (MSB)
   proc {BrowseOutBits S1s S2s S3s S4s C4s}
      case S1s#S2s#S3s#S4s#C4s
      of (S1|S1r)#(S2|S2r)#(S3|S3r)#(S4|S4r)#(C4|C4r) then
         {Browse s#[S4 S3 S2 S1]}
         {Browse c#C4}
         {Delay 1000}
         {BrowseOutBits S1r S2r S3r S4r C4r}
      end
   end
in
   {BrowseOutBits S1s S2s S3s S4s C4s}
end