第一章 練習問題

oz CTMCP

第一章の問題。Mozart/OZの紹介が多い。

1 計算機

(a)
declare X Y Z
X = 2 * 2 * 2 * 2 * 2 % 2 ** 5
Y = X * X * X * X * X % (2**5)**5
Z = Y * Y * Y * Y % ((2**5)**5)**4
{Show Z}
(b)
delcare X
X = 100 * 99 * .. * 1
{Show X}

簡単にやる方法はない。

2 組み合わせの計算

(a)
declare
fun {Product From To}
   if From == To then
      From
   else
      From * {Product From+1 To}
   end
end

fun {Comb N K}
   {Product N-K+1 N} div {Product 1 K}
end
(b)

Combは先ほどの物と同じ。

fun {CombSmart N K}
   if K > (N div 2) then
      {Comb N N-K}
   else
      {Comb N K}
   end
end

3 プログラムの正しさ

ちゃんと証明しきれていない気がする。

面倒なので、補助関数ShiftLeft、ShiftRight、AddListが正しいものとする。

  • {Pascal 1}は正しい答、すなわち[1]を返す。
  • {Pascal N-1}が正しいと仮定する。そのあと、{Pascal N}は{AddList {ShiftLeft {Pascal N-1}} {ShiftRight {Pascal N-1}}}を計算する。よって、AddList、ShiftLeft、ShiftRightが正しければ、Pascalは正しい結果を返す。

4 プログラムの計算量

O(n**100)のプログラムが実用的か否か、という問題。

1.7節では特に述べられていない。
しかし計算量が高次の多項式であったとしても、増加率は指数の計算量には及ばないので、十分実用的であると考える。

5 遅延計算

停止しない。そのため、良い考えではない。

6 高階プログラミング

(a)

2行目(N=2)のとき{OpList Mul [0 1] [1 0]}を計算する。そのため、すべて0になる。
Mullを使うと、次のようになる。

[10 
 6235300 
 160344312228246705825060 
 49116946500844767398714340184254871599279813644844 
 505756353132539355991535788904396967700352784465846135098293311191732044 
 505756353132539355991535788904396967700352784465846135098293311191732044 
 49116946500844767398714340184254871599279813644844 
 160344312228246705825060 
 6235300 
 10]
(b)
proc {ShowPascal Op}
   for I in 1..10 do
      {Show {GenericPascal Op I}}
   end
end

7 明示的状態

前者は23を、後者は44を表示する。

8 明示的状態と関数

間違っている理由は、毎回セルを作り初期化してしまっているから。

declare
local Acc
   Acc = {NewCell 0}
in
   fun {Accumulate N} 
      Acc := @Acc + N
      @Acc
   end
end

{Show {Accumulate 5}}
{Show {Accumulate 100}}
{Show {Accumulate 45}}

9 記憶域(memory store)

(a)

Supplements for "Concepts, Techniques, and Models of Computer Programming"にウェブサイトの補充ファイルがおいてある。ファイル: booksuppl.oz。
この分量だっらコピペが楽。

declare
fun {NewStore}
   D={NewDictionary}
   C={NewCell 0}
   proc {Put K X}
      if {Not {Dictionary.member D K}} then
         C:=@C+1
      end
      D.K:=X
   end
   fun {Get K} D.K end
   fun {Size} @C end
in
   storeobject(put:Put get:Get size:Size)
end

proc {Put S K X} {S.put K X} end
fun {Get S K} {S.get K} end
fun {Size S} {S.size} end

S ={NewStore}
{Put S 2 [22 33]}
{Show {Get S 2}}
{Show {Size S}}
(b)
local 
   S = {NewStore} 
in
   fun {FasterPascal N}
      if N > {Size S} then L = {FasterPascal N-1} in
	 {Put S N L}
	 L
      else 
	 {Get S N}
      end
   end
end
(c)
fun {MyNewStore}
   {NewCell nil}
end

proc {MyPut S Key Value}
   S := (Key|Value)|@S
end

fun {MyGet S Key}
   fun {Assoc L}
      case L of (K1|Value)|T then
	 if K1 == Key then Value
	 else {Assoc T} end
      else nil end
   end
in
   {Assoc @S}
end
(d)
proc {MyPut S Key Value}
   if {MyGet S Key} == nil then _ = {Bump} in
      S := (Key|Value)|@S
   else 
      S := (Key|Value)|@S
   end
end

fun {MySize}
   {Read}
end

MyPutが汚ないな。ノットイコールの書き方が分らない。
あと、この問題は1.13と1.3と間違えている。

10 明示的状態と並列性

(a)

1になることもあるはずだけれども、常に2が得られた。1の代入のほうが上に書いてあるからかな?

(b)
declare
C={NewCell 0}
thread {Delay 10} C:=1 end
thread C:=2 end
(c)

ここで言う「遅延技法」はlazyなやつではなく、Delayを挿入する技法のことだろう。
Delayを挿入しても結果は代らない。結果が得られるのが遅くなるだけ。