第二章 練習問題

oz CTMCP

核言語が初登場。書き直せという問題が多い。

1 自由変数と束縛変数

核言語へ変換すると以下のようになる。なので、第二のPの出現ではPは自由ではない。

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

2 文脈的環境

問題の意図がよく掴めない。

とりあえず、呼び出し時に環境にNがない例。

local MulByN N in
 ...
end

{MulByN X Y}

次に3以外に束縛されている例。

local MulByN N in
 ...
end

local N in
  N = 42
  {MulByN X Y}
end

つまりこういう場合が存在するので、常にN->3を環境に追加する必要がある。

3 関数と手続き

次の関数Fは、返り値として何を持てばいいのが明かではないため、例外が発生する。

fun {F X}
  if false then
    X
  end
end

しかし、手続きの場合返り値を持つ必要がないので、例外は発生しない。

4 if文とcase文

(a)
if <cond> then
  <then-c>
else
  <else-c>
end

は次のように書くことができる。

case <cond> of
   true then <then-c>
   else <else-c>
end
(b)
case [0 1 2] of
  H|T then <s>
end

を変換すると

declare
local L H T in
   proc {Each F L}
      if L \= nil then H|T = L in
	 {F H}
	 {Each F T}
      end
   end

   L = [0 1 2]
   P = H|T
   
   if {Label L} == {Label P} andthen {Arity L} == {Arity P} then
      {Each proc {$ X} P.X=L.X end {Arity L}}
      {Show P}
   end
end

となる。

核言語においてパターンは、lit(fet1:x1 ... fetN:xN)の形をしている?BNF的には違うが、意味はこれによって規定されている。

5 case文

せっかく書いたので貼っておく。コピペ用?

declare
proc {Test X}
   case X
   of a|Z  then {Show 'case'(1)}
   [] f(a) then {Show 'case'(2)}
   [] Y|Z  andthen Y==Z then {Show 'case'(3)}
   [] Y|Z  then {Show 'case'(4)}
   [] f(Y) then {Show 'case'(5)}
   else {Show 'case'(6)}
   end
end

{Test [b c a]}
{Test f(b(3))}
{Test f(a)}
{Test f(a(3))}
{Test f(d)}
{Test [a b c]}
{Test [c a b]}
{Test a|a}
{Test '|'(a b c)}
{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)
{Test '|'(a b c)}
case(6)

6 case文再訪

すべてcase of ... endのXが決定状態にないため待機に入る。

しかし、if文の場合f(X Y d) == f(a Y c)はfalseであることが分かるため、case(2)が出力される。

if f(X Y d) == f(a Y c) then
   {Show 'case'(1)}
else
   {Show 'case'(2)}
end

7 字句的スコープ閉包

つまりValueの値が字句的に決まるってことを理解してるかのチェックだろう。Max3はValue=3、Max5はValue=5であることを考慮にいれると、

[4 5]

8 制御抽象

ありがちな問題。andalsoが短絡するか否か。

(a)

同じ結果になる。{AndAlso fun {$} true end fun{$} end}なら、を計算しないで済む。

(b)
fun {OrElse BP1 BP2}
   if {BP1} then
      true
   else
      {BP2}
   end
end

9 末尾再帰

(a)

核言語へ展開する上で以下の2つの手続きを仮定する。

proc {Add X Y ?R} R=X+Y end
proc {Eq X Y ?R} R=X==Y end
local Sum1 in
   local Sum2 in
      Sum1 = proc {$ N ?R}
		local EqR in
		   {Eq N 0 EqR}
		   if EqR then 
		      R=0 
		   else
		      local SumR in
			 local AddR in
			    {Add N ~1 AddR}
			    {Sum1 AddR SumR}
			    {Add N SumR R}
			 end
		      end
		   end 
		end
	     end

      Sum2 = proc {$ N S ?R} 
		local EqR in
		   {Eq N 0 EqR}
		   if EqR then 
		      R=S 
		   else
		      local AddR1 in
			 local AddR2 in
			    {Add N ~1 AddR1}
			    {Add N S AddR2}
			    {Sum2 AddR1 AddR2 R} 
			 end
		      end
		   end
		end
	     end
   end
end
(b) Sum1

再帰呼び出し時のときの環境のみを追いかける。

N=10のとき

{Sum1 AddR SumR} N:n0 R:r AddR:a0 SumR:s0
{Add N SumR R} N:n0 R:r AddR:a0 SumR:s0

格納域:n0=10 a0=9 r s0

N=9のとき

{Sum1 AddR SumR} N:n1 R:r AddR:a1 SumR:s1
{Add N SumR R} N:n1 R:r AddR:a1 SumR:s1
{Add N SumR R} N:n0 R:r AddR:a0 SumR:s0

格納域:n0=10 n1=9 a0=9 a1=8 r s[0-1]

N=8のとき

{Sum1 AddR SumR} N:n2 R:r AddR:a2 SumR:s2
{Add N SumR R} N:n2 R:r AddR:a2 SumR:s2
{Add N SumR R} N:n1 R:r AddR:a1 SumR:s1
{Add N SumR R} N:n0 R:r AddR:a0 SumR:s0

格納域:n0=10 n1=9 n2=8 a0=9 a1=8 a2=7 r s[0-2]

N=7のとき

{Sum1 AddR SumR} N:n3 R:r AddR:a3 SumR:s3
{Add N SumR R} N:n3 R:r AddR:a3 SumR:s3
{Add N SumR R} N:n2 R:r AddR:a2 SumR:s2
{Add N SumR R} N:n1 R:r AddR:a1 SumR:s1
{Add N SumR R} N:n0 R:r AddR:a0 SumR:s0

格納域: n0=10 n1=9 n2=8 n3=7 a0=9 a1=8 a2=7 a3=6 r s[0-3]

N=6のとき

{Sum1 AddR SumR} N:n4 R:r AddR:a4 SumR:s4
{Add N SumR R} N:n4 R:r AddR:a4 SumR:s4
{Add N SumR R} N:n3 R:r AddR:a3 SumR:s3
{Add N SumR R} N:n2 R:r AddR:a2 SumR:s2
{Add N SumR R} N:n1 R:r AddR:a1 SumR:s1
{Add N SumR R} N:n0 R:r AddR:a0 SumR:s0

格納域:n0=10 n1=9 n2=8 n3=7 n4=6 a0=9 a1=8 a2=7 a3=6 a4=5 r s[0-4]

N=5のとき

{Sum1 AddR SumR} N:n5 R:r AddR:a5 SumR:s5
{Add N SumR R} N:n5 R:r AddR:a5 SumR:s5
{Add N SumR R} N:n4 R:r AddR:a4 SumR:s4
{Add N SumR R} N:n3 R:r AddR:a3 SumR:s3
{Add N SumR R} N:n2 R:r AddR:a2 SumR:s2
{Add N SumR R} N:n1 R:r AddR:a1 SumR:s1
{Add N SumR R} N:n0 R:r AddR:a0 SumR:s0

格納域: n0=10 n1=9 n2=8 n3=7 n4=6 n5=5 a0=9 a1=8 a2=7 a3=6 a4=5 a5=4 r s[0-5]

N=4のとき

{Sum1 AddR SumR} N:n6 R:r AddR:a6 SumR:s6
{Add N SumR R} N:n6 R:r AddR:a6 SumR:s6
{Add N SumR R} N:n5 R:r AddR:a5 SumR:s5
{Add N SumR R} N:n4 R:r AddR:a4 SumR:s4
{Add N SumR R} N:n3 R:r AddR:a3 SumR:s3
{Add N SumR R} N:n2 R:r AddR:a2 SumR:s2
{Add N SumR R} N:n1 R:r AddR:a1 SumR:s1
{Add N SumR R} N:n0 R:r AddR:a0 SumR:s0

格納域: n0=10 n1=9 n2=8 n3=7 n4=6 n5=5 n6=4 a0=9 a1=8 a2=7 a3=6 a4=5 a5=4 a6=3 r s[0-6]

N=3のとき

{Sum1 AddR SumR} N:n7 R:r AddR:a7 SumR:s7
{Add N SumR R} N:n7 R:r AddR:a7 SumR:s7
{Add N SumR R} N:n6 R:r AddR:a6 SumR:s6
{Add N SumR R} N:n5 R:r AddR:a5 SumR:s5
{Add N SumR R} N:n4 R:r AddR:a4 SumR:s4
{Add N SumR R} N:n3 R:r AddR:a3 SumR:s3
{Add N SumR R} N:n2 R:r AddR:a2 SumR:s2
{Add N SumR R} N:n1 R:r AddR:a1 SumR:s1
{Add N SumR R} N:n0 R:r AddR:a0 SumR:s0

格納域: n0=10 n1=9 n2=8 n3=7 n4=6 n5=5 n6=4 n7=3 a0=9 a1=8 a2=7 a3=6 a4=5 a5=4 a6=3 a7=2 r s[0-7]

N=2のとき

{Sum1 AddR SumR} N:n8 R:r AddR:a8 SumR:s8
{Add N SumR R} N:n8 R:r AddR:a8 SumR:s8
{Add N SumR R} N:n7 R:r AddR:a7 SumR:s7
{Add N SumR R} N:n6 R:r AddR:a6 SumR:s6
{Add N SumR R} N:n5 R:r AddR:a5 SumR:s5
{Add N SumR R} N:n4 R:r AddR:a4 SumR:s4
{Add N SumR R} N:n3 R:r AddR:a3 SumR:s3
{Add N SumR R} N:n2 R:r AddR:a2 SumR:s2
{Add N SumR R} N:n1 R:r AddR:a1 SumR:s1
{Add N SumR R} N:n0 R:r AddR:a0 SumR:s0

格納域: n0=10 n1=9 n2=8 n3=7 n4=6 n5=5 n6=4 n7=3 n8=2 a0=9 a1=8 a2=7 a3=6 a4=5 a5=4 a6=3 a7=2 a8=1 r s[0-8]

N=1のとき

{Sum1 AddR SumR} N:n9 R:r AddR:a9 SumR:s9
{Add N SumR R} N:n9 R:r AddR:a9 SumR:s9
{Add N SumR R} N:n8 R:r AddR:a8 SumR:s8
{Add N SumR R} N:n7 R:r AddR:a7 SumR:s7
{Add N SumR R} N:n6 R:r AddR:a6 SumR:s6
{Add N SumR R} N:n5 R:r AddR:a5 SumR:s5
{Add N SumR R} N:n4 R:r AddR:a4 SumR:s4
{Add N SumR R} N:n3 R:r AddR:a3 SumR:s3
{Add N SumR R} N:n2 R:r AddR:a2 SumR:s2
{Add N SumR R} N:n1 R:r AddR:a1 SumR:s1
{Add N SumR R} N:n0 R:r AddR:a0 SumR:s0

格納域: n0=10 n1=9 n2=8 n3=7 n4=6 n5=5 n6=4 n7=3 n8=2 n9=1 a0=9 a1=8 a2=7 a3=6 a4=5 a5=4 a6=3 a7=2 a8=1 a9=0 r s[0-8]

(b) Sum2

N=10のとき

{Sum2 AddR1 AddR2 R} AddR1:a0 AddR2:b0 R:r

格納域: a0:9 b0:10 r

N=9のとき

{Sum2 AddR1 AddR2 R} AddR1:a1 AddR2:b1 R:r

格納域: a0:9 a1:8 b0:10 b1:19 r

N=8のとき

{Sum2 AddR1 AddR2 R} AddR1:a2 AddR2:b2 R:r

格納域: a0:9 a1:8 a2:7 b0:10 b1:19 b2:27 r

N=7のとき

{Sum2 AddR1 AddR2 R} AddR1:a3 AddR2:b3 R:r

格納域: a0:9 a1:8 a2:7 a3:6 b0:10 b1:19 b2:27 b3:34 r

N=6のとき

{Sum2 AddR1 AddR2 R} AddR1:a4 AddR2:b4 R:r

格納域: a0:9 a1:8 a2:7 a3:6 a4:5 b0:10 b1:19 b2:27 b3:34 b4:40 r

N=5のとき

{Sum2 AddR1 AddR2 R} AddR1:a5 AddR2:b5 R:r

格納域: a0:9 a1:8 a2:7 a3:6 a4:5 a5:4 b0:10 b1:19 b2:27 b3:34 b4:40 b5:45 r

N=4のとき

{Sum2 AddR1 AddR2 R} AddR1:a6 AddR2:b6 R:r

格納域: a0:9 a1:8 a2:7 a3:6 a4:5 a5:3 a6:2 b0:10 b1:19 b2:27 b3:34 b4:40 b5:45 b6:49 r

N=3のとき

{Sum2 AddR1 AddR2 R} AddR1:a7 AddR2:b7 R:r

格納域: a0:9 a1:8 a2:7 a3:6 a4:5 a5:4 a6:3 a7:2 b0:10 b1:19 b2:27 b3:34 b4:40 b5:45 b6:49 b7:52 r

N=2のとき

{Sum2 AddR1 AddR2 R} AddR1:a8 AddR2:b8 R:r

格納域: a0:9 a1:8 a2:7 a3:6 a4:5 a5:4 a6:3 a7:2 a8:1 b0:10 b1:19 b2:27 b3:34 b4:40 b5:45 b6:49 b7:52 b8:54 r

N=1のとき

{Sum2 AddR1 AddR2 R} AddR1:a9 AddR2:b9 R:r

格納域: a0:9 a1:8 a2:7 a3:6 a4:5 a5:4 a6:3 a7:2 a8:1 a9:0 b0:10 b1:19 b2:27 b3:34 b4:40 b5:45 b6:49 b7:52 b8:54 b9:55 r

(c)

100,000,000ではどちらも終了しなかったんで、10,000,000でおこなった。
Sum1は終了しなかったが、Sum2は正しく計算した。

10 核言語への展開

declare
local SMerge in
   SMerge = proc{$ Xs Ys R}
	       case '#'(Xs Ys) of
		  '#'(nil Ys) then R=Ys
	       [] '#'(Xs nil) then R=Xs
	       [] '#'(X|Xr Y|Yr) then
		  if X =< Y then
		     local Z Zr in
			R=Z|Zr
			Z=X
			{SMerge Xr Ys Zr}
		     end
		  else
		     local Z Zr in
			R=Z|Zr
			Z=Y
			{SMerge Xs Yr Zr}
		     end
		  end

	       end
	    end
end

11 相互再帰

N=0について、{IsEven 0}、{IsOdd 0}は共に一定の大きさのスタックで実行可能である。

次にN-1について{IsEven N-1}、{IsOdd N-1}が一定の大きさのスタックで実行可能であると仮定する。
すると{IsEven N}、{IsOdd N}は、{IsOdd N-1}、{IsEven N-1}のスタックの大きさで実行可能なので、一定の大きさのスタックで実行可能である。

よって非負の整数に対して{IsEven N}、{IsOdd N}が一定の大きさのスタックで実行可能である。

12 finnaly節を持つ例外

declare B X Y
try
  <s1>   
catch X1 then
   B = true
   X = X1
end

if B then
   <s2>
   raise X end
end

13 単一化

まず、核言語へ変換する。

X = '|'(1:a 2:'|'(1:Z 2:nil)) % (1)
Y = '|'(1:W 2:'|'(1:b 2:nil)) % (2)
X = Y                         % (3)
1,2,3
  1. Xが'|'(1:a 2:'|'(1:Z 2:nil))に束縛される
  2. Yが'|'(1:W 2:'|'(1:b 2:nil))に束縛される
  3. unity(X,Y)
    1. unity(a,W) -> Wがaに束縛される
    2. unity('|'(1:Z 2:nil),'|'(1:b 2:nil))
      1. unity(Z,b) -> Zがbに束縛される
      2. unity(nil,nil) -> なにもない
1,3,2
  1. Xが'|'(1:a 2:'|'(1:Z 2:nil))に束縛される
  2. Yが'|'(1:a 2:'|'(1:Z 2:nil))に束縛される
  3. unity(Y,'|'(1:W 2:'|'(1:b 2:nil)))
    1. unity(a,W) -> Wがaに束縛される
    2. unity('|'(1:Z 2:nil),'|'(1:b 2:nil))
      1. unity(Z,b) -> Zがbに束縛される
      2. unity(nil,nil) -> なにもない
2,1,3
  1. Yが'|'(1:W 2:'|'(1:b 2:nil))に束縛される
  2. Xが'|'(1:a 2:'|'(1:Z 2:nil))に束縛される
  3. unity(X,Y)
    1. unity(a,W) -> Wがaに束縛される
    2. unity('|'(1:Z 2:nil),'|'(1:b 2:nil))
      1. unity(Z,b) -> Zがbに束縛される
      2. unity(nil,nil) -> なにもない
2,3,1
  1. Yが'|'(1:W 2:'|'(1:b 2:nil))に束縛される
  2. Xが'|'(1:W 2:'|'(1:b 2:nil))に束縛される
  3. unity(X,'|'(1:a 2:'|'(1:Z 2:nil)))
    1. unity(a,W) -> Wがaに束縛される
    2. unity('|'(1:Z 2:nil),'|'(1:b 2:nil))
      1. unity(Z,b) -> Zがbに束縛される
3,1,2
  1. XとYが同値集合になる
  2. X、Yが'|'(1:a 2:'|'(1:Z 2:nil))に束縛される
  3. unity(Y,'|'(1:W 2:'|'(1:b 2:nil)))
    1. unity(a,W) -> Wがaに束縛される
    2. unity('|'(1:Z 2:nil),'|'(1:b 2:nil))
      1. unity(Z,b) -> Zがbに束縛される
3,2,1
  1. XとYが同値集合になる
  2. X、Yが'|'(1:W 2:'|'(1:b 2:nil))に束縛される
  3. unity(X,'|'(1:a 2:'|'(1:Z 2:nil)))
    1. unity(a,W) -> Wがaに束縛される
    2. unity('|'(1:Z 2:nil),'|'(1:b 2:nil))
      1. unity(Z,b) -> Zがbに束縛される