「コンピュータプログラミングの概念・技法・モデル」の続き
第2章を読み終えた!
練習問題をやってみたけど,4 を終えたところでタイムアップです.
自信はないです.
続きは,また後日.
2008/03/29 とりあえず 9までやってみた.それはそうと,問 4に対する自分の回答は間違っていると思う.考え直します.
2.9
1.
P = proc {$ X} T=(X>0) if T then {P X-1} end end
P は宣言されていないので自由.
2.
とりあえず核言語化
local MulByN in local N in N=3 MulByN = proc {$ X Y} Y=N*X end end end
別スコープに同名の識別子(N)があると,その N の写像(例えば {N → 5} とか)が適用されてしまうから.
呼び出し時の環境内に {N → 3} があったとしても,それは上記コード中の N=3 によるものである保証がないから(別スコープの N の写像である可能性があるから).
呼び出し時の環境にNが存在しない例:
declare MulByN in proc {MulByN X ?Y} Y=N*X end
ということか?
呼び出し時の環境にNは存在するが,3以外の値に束縛されている例:
local MulByN N in N=3 proc {MulByN X ?Y} Y=N*X end local N R in N=5 {MulByN 2 R} ← 呼び出し時の環境は {N → 5} になっている.procをスタックから取り出して実行するときに,環境へ{N → 3} が追加される end end
3.
関数は,本体の終了が式でなければならないため.
手続きは文の集合だから問題ない.
4.
case を使った if の定義:
if <x> then <s>1 else <s>2 end
↓
case <x> of true then <s>1 else <s>2 end
if を使った case の定義:
case <x> of <pattern> then <s>1 else <s>2 end
↓
if {Label <x>}=={Label <pattern>} then if {Arity <x>}=={Arity <pattern>} then <x>=<pattern> <s>1 else <s>2 end else <s>2 end
ちなみに,
{Label true}==true {Arity true}==nil {Label H|T}=='|' {Arity H|T}==[1 2]
です.
5.
○{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(1):リストとタプルを間違えた...orz → 正解は case(6)
ちなみに,
{Label [a b c]}='|' {Arity [a b c]}=[1 2] → a|[b c] → a|(b|(c|nil) {Label '|'(a b c)}='|' {Arity '|'(a b c)}=[1 2 3]
です.
6.
declare Test Y proc {Test X} case X of f(a Y c) then {Browse 'case'(1)} else {Browse 'case'(2)} end end declare X Y {Test f(X b Y)}
- {Test f(X b Y)} は case(2)
X, Y に値を束縛しないと評価されない.
a -> X,Y -> b,c -> Y だから,判断不可.
X=a, Y=c を投入すると case(1) が,それ以外は全て case(2) となる.
proc 内の Y と,投入する Y とが指す参照は別である.
X=a, Y=c を評価後,proc 内の Y は b を,投入した Y は c を指す.
- {Test f(a Y d)} は case(2)
(投入した Y を Y' とする)
a -> a,Y = Y' -> y(未束縛),c \= d により,即座に case(2) とを出力する.
- {Test f(X Y d)} は case(2)
X を束縛しないことには評価されない.
a -> X,Y = Y' -> y,c \= d(← X が束縛されないことには,ここは評価されないようだ)
declare X Y if f(X Y d)==f(a Y c) then {Browse 'case'(1)} else {Browse 'case'(2)} end
X==a,Y==Y,d\=c より,X の束縛を待つことなく false と評価されるため,case(2) となる.
7.
環境(Valueの写像)は捕捉され,結果は [4 5] になる.
8.
(a)
fun は式の値を返す.AndThen 内部の呼び出しは,
if <expression>1の評価値 then <expression>2の評価値 else false end
となる.
この文の評価結果は
ただし,
(b)
if <expressin>1 then true else <expression>2 end
なので
fun {OrThen BP1 BP2} if {BP1} then true else {BP2} end end
となる.
9.
(a)
Sum1= {$ N ?R} T=(N==0) if T then R=0 else R1 in R1={Sum1 N-1} R=N+R1 end end
Sum2= {$ N S ?R} T=(N==0) if T then R=S else R1 in R={Sum2 N-1 N+S} end end
(b)
- {Sum1 10}
再帰呼び出し1回目の直前:
([({Sum1 N-1},{N->n0})], {n0->10})
再帰呼び出し2回目の直前:
([({Sum1 N-1},{N->n1}), ({Sum1 N-1},{N->n0})], {n0->10, n1->9})
...
再帰呼び出し10回目の直前:
([({Sum1 N-1},{N->n9}), ..., ({Sum1 N-1},{N->n1}), ({Sum1 N-1},{N->n0})], {n0->10, n1->9, ..., n9->1})
呼び出すと,
([(N+$,{N->n9}), ..., ({Sum1 N-1},{N->n1}), ({Sum1 N-1},{N->n0})], {n0->10, n1->9, ..., n9->1, $->0})
([(N+$,{N->n8}), ..., ({Sum1 N-1},{N->n1}), ({Sum1 N-1},{N->n0})], {n0->10, n1->9, ..., n8->2, n9->1, $->1})
...
([(N+$,{N->n0})], {n0->10, n1->9, ..., n8->2, n9->1, $->45})
- {Sum2 10 0}
再帰呼び出し1回目の直前:
([({Sum2 N-1 N+S},{N->n0, S->s0})], {n0->10, s0->0})
再帰呼び出し2回目の直前:
([({Sum2 N-1 N+S},{N->n1, S->s1})], {n1->9, s1->10})
...
再帰呼び出し10回目の直前:
([({Sum2 N-1 N+S},{N->n9, S->s9})], {n9->1, s0->54})
このあと,{Sum2 N-1 N+S}=55 となる.
(c)
{Sum1 100000000} → メモリ馬鹿食い
※1000000 ぐらいで ozengine がハングする.
{Sum2 100000000 0} → 問題なく結果が返ってくる
※大まかな指標としてメモリ使用量をみると,一定量以上増えないことが確認できる.