Implementing functional languages を頑張って読む.21日目

21日目

20日目は全訳して無駄に長かったので躓いたところとExerciseだけ書く

2.7 Mark 5: Structured data

今の実装じゃ構造型はきつい

Exercise 2.18

なぜcase式は今のマシンで取り扱うのが難しいか?(case式でinstantiate関数がどう動くか見よ)
→ わからん.

2.7.1 Building structured data

実装するべきものを2.7.3で書いていてくれてるので,すぐ実装せずに2.7.3を参考にする.

一般的なcase式を実装するのは難しいので簡単なBooleanから実装する.

2.7.2 Conditionals

BooleanはMirandaではこのように書かれる.
boolean ::= False | True
2つのコンストラクタ,True,Falseがある.それぞれアリティは0で,私たちは任意に1をFalseに,2をTrueに当てはめられる.
よってCore Languageでは以下の定義を得る:

False = Pack{1,0}
True = Pack{2,0}

Exercise 2.19

条件式の状態遷移ルールを完成させよ.3つのルールが必要である: 2つは既にifの条件式が評価されている場合; 1つはまだ評価されていない場合である(Rule 2.9を参考にせよ).最初の2つの場合は間接参照ノードを用いるのが良い.
さらなるルールが1つ欠落している.なんだろうか?(ヒント: 条件式の評価が終了した時,条件式はどのように再試行されるだろうか?)

h
a	NPrim If
ac	NAp a b
t	NData 2 []
f	NData 1 []
at	NAp ac bt
af	NAp at bf

a : ac : at : af : []	d	h[ac: NAp a t ]	f
a : []	d	h[af: NInd bt]	f

a : ac : at : af : []	d	h[ac: NAp a f ]	f
a : []	d	h[af: NInd bf]	f

a : ac : at : af : []	d	h[ac: NAp a b]	f
b : []	(ac : at : af : []) : d	h	f

a : []	s : d	h[a: NData _ _]	f
s	d	h	f

Exercise 2.20

Core Languageでのor,xor,notの定義を与えよ.全てextraPreludeDefsに追加せよ.

and x y = if x y False
or x y = if x True y
not x = if x False True
xor x y = or (and x (not y)) (and (not x) y)

2.7.3 Implementing structured data

構造体,条件分岐,比較を実装するのに必要な変更一覧がある.

• NData コンストラクタをnode データ型に追加せよ.showNodeをNDataを表示できるように拡張せよ.
• PrimConstr, If, Greater, GreaterEq, Less, LessEq, Eq, NotEqをprimitiveに追加せよ.instantiateVarで適切に実体化できるように適切なペアをprimitivesに追加せよ.
• instantiateConstr(Update)の定義を与えよ.
• isDataNode関数をNDataノードも認識するようにせよ.
• step関数の中のdispatchが補助関数のdataStepを呼ぶことによりNDataを扱えるようにせよ.
• dataStepを定義せよ.これはnumStepと非常によく似ている.
• primStepをPrimConstrやその他新しいプリミティブを対処できるように拡張せよ.PrimConstrやIfは補助関数を呼ぶと良い.比較は大体primArithが使える.

primConstrはprimitivesには入らない.型が違う.
primDyadicに条件分岐をぶん投げてるのが大丈夫かわからない.
自明にgreaterとeqさえあれば自明その他の演算子は構成可能なので後で減らせるかも.
そもそも遅延評価なのでifをプリミティブにする必要すらない.
K x y = xとF x y = y でOKだし,and/orもコンビネータで書ける.

Exercise 2.21

全ての変更を実装せよ.全て実装できていれば以下の関数が実行可能.

fac n = if (n == 0) 1 (n * fac (n-1)) ; main = fac 3

出力(fact 6)

Stack [ (top)
  34: NNum 720
]
heap size 106


Total number of steps = 176
Total number of reductions = 34
Total number of supercombinator reductions = 8
Total number of primitive reductions = 26
Maximum of stack depth = 4

2.7.3が終わり.5時間で3ページ.ひどい.

diffはもう一回一回が長いので貼らない.そのうちgitに上げるのでlogでも見て