プログラミングについて勉強する(4)

「コンピュータプログラミングの概念・技法・モデル」の続き


第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

となる.
この文の評価結果は 1 andthen 2 と変わらない.
ただし,2 が常に評価されている,という点は異なる.


(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} → 問題なく結果が返ってくる
※大まかな指標としてメモリ使用量をみると,一定量以上増えないことが確認できる.