tiger book読書記録 chapter 1

2018年8月7日 15:27

最新コンパイラ構成技法(Modern Commpiler Implementaion in ML new edition)　通称tiger bookを読むことにした。このnoteはその記録用である。

Chapter 1

august 4, 2018:
一章本文を読む。流石に最初の章は簡単であるがMLを知らない。しょうがないので,手元の環境にstandard mlをinstallして簡単なMLのtutorialをすることにした。

August 5, 2018:
Ubuntu環境にstandard ML new jerseyを入れた。deb package化されているので簡単。以下のpackageを入れた。emacsを使っているのでsml-modeも入れておく。

sudo apt-get install sml-mode smlnj smlnj-doc smlnj-runtime elpa-sml-mode

emacsのsml-modeで思った様にindentしてくれない。面倒なので、当面このままにしておく。MLに慣れてきた頃に見直そう。

August 6, 2018:
MLの超基本を適当なsiteで学ぶ。学んだのは
- コメントの書き方 (* *)
- identifier, reserved keyword
- basic types: bool, int, word, real, char, string, unit
- complex type: tuple, list, record
- operators:　- + * abs / div mod: divとmodもinfix notationだった
- not, andalso, orelse
- how to define function
- type variable: 'a ''aと equality type, non-equality type
- pattern matching and wild card matching _
- higher order function and fn, rec
- partial application
- list walking operators: null, hd, tl, length, map, rev, @, foldr, foldl, last, nth
- algebraic data type/type constructor/value constructor
- reference type, !, :=
- module system: structure, signature, functor
むぅ、whereのsyntaxがよく理解出来ていないがまぁ、良しとする。解説も簡単なものだったし。必要になったらまた何か解説を読むことにする。
処理系の実行を理解して、簡単なコードは理解出来るようになったか。明日からはtiger bookに戻って１章の演習問題に取り組むことにする。

Aug 8, 2018:
本文中の課題1 引数の最大値を求める関数maxargsを書け

type id = string;

datatype binop = Plus | Minus | Times | Div;

datatype stm = CompoundStm of stm * stm
             | AssignStm of id * exp
             | PrintStm of exp list
     and exp = IdExp of id
             | NumExp of int
             | OpExp of exp * binop * exp
             | EseqExp of stm * exp;

fun maxval x y = if x > y then x else y;
fun maxargs (CompoundStm (stm0, stm1)) = maxval (maxargs stm0) (maxargs stm1)
  | maxargs (AssignStm (id0, exp0)) = maxargs_exp exp0
  | maxargs (PrintStm xs) = maxval (length xs) (maxargs_exp_list xs)
and maxargs_exp_list [] = 0
  | maxargs_exp_list (x::xs) = maxval (maxargs_exp x) (maxargs_exp_list xs)
and maxargs_exp (IdExp id0) = 0
  | maxargs_exp (NumExp x) = 0
  | maxargs_exp (OpExp (e0, b, e1)) = maxval (maxargs_exp e0) (maxargs_exp e1)
  | maxargs_exp (EseqExp (stm0, exp0)) = maxval (maxargs stm0) (maxargs_exp exp0);

なんかmaxvalを使っているのが気に入らない。foldrを使うとうまく出来るのだろうか。まだ、MLに慣れてないのでerrorをfixのに苦労する。ml of new jerseyはcompilerと書いてあるけれど、interpreterなのか。どうやらこれをcompileして実行fileを作成するのは出来ないことは無いが面倒そうだ。moltonとか使えとかある。それならcompilerと名乗らずinterpreterと名乗って欲しい。明日は課題その2をやろう。

August 9, 2018:
課題2と演習問題1.1 a, b, cをやった。dは明日にする。

課題2

type id = string;

datatype binop = Plus | Minus | Times | Div;

datatype stm = CompoundStm of stm * stm
             | AssignStm of id * exp
             | PrintStm of exp list
     and exp = IdExp of id
             | NumExp of int
             | OpExp of exp * binop * exp
             | EseqExp of stm * exp;

structure Table =
struct
  exception LookupFailure;

  type tkey = id;
  type tval = int;
  type elem = (id * tval);
  type table = (id * tval) list;

  fun new () = nil : table;
  fun update key (num, t) = (key, num)::t;
  fun lookup key [] = raise LookupFailure
    | lookup key ((k, v)::xs) = if key = k then v else lookup key xs;
end;

(* interpStm : stm -> table -> table *)
fun interpStm (CompoundStm (stm0, stm1)) t =
    let
        val t0 = interpStm stm0 t;
    in
        interpStm stm1 t0
    end
  | interpStm (AssignStm (id0, exp0)) t = Table.update id0 (interpExp exp0 t)
  | interpStm (PrintStm (xs)) t = printExp xs t
(* interpExp : exp -> table -> int * table *)
and interpExp (IdExp id0) t = (Table.lookup id0 t, t)
  | interpExp (NumExp num) t = (num, t)
  | interpExp (OpExp (e0, op0, e1)) t =
    let
        val (num0, t0) = interpExp e0 t;
        val (num1, t1) = interpExp e1 t0;
    in
        case op0 of
            Plus => (num0 + num1, t1)
          | Minus => (num0 - num1, t1)
          | Times => (num0 * num1, t1)
          | Div => (num0 div num1, t1)
    end
  | interpExp (EseqExp (stm0, exp0)) t0 =
    let
        val t1 = interpStm stm0 t0;
    in
        interpExp exp0 t1
    end
(* printExp : exp list -> table -> table *)
and printExp nil t = (print("\n"); t)
  | printExp [(IdExp id0)] t = (print (id0 ^ " = " ^ Int.toString (Table.lookup id0 t) ^ ";\n"); t)
  (* | printExp [(IdExp id0)] t = (print id0; t) *)
  | printExp [(NumExp num)] t = (print ((Int.toString num) ^ ";\n"); t)
  | printExp [exp0] t =
    let
        val (num, t_new) = interpExp exp0 t;
        val _ = print (Int.toString num ^ ";\n");
    in
        t_new
    end
  | printExp (x::xs) t =
    let
        val t0 = printExp [x] t;
    in
        printExp xs t0
    end;

val prog =
    CompoundStm(AssignStm("a", OpExp(NumExp 5, Plus, NumExp 3)),
                CompoundStm(AssignStm("b",
                                      EseqExp(PrintStm [IdExp "a", OpExp(IdExp "a", Minus, NumExp 1)],
                                              OpExp(NumExp 10, Times, IdExp "a"))),
                            PrintStm [IdExp "b"]));

(*
a = 5 + 3
b = [print(a), a -1, 10 * a]
print(b)
*)

val t = Table.new ();
interpStm prog t;

let文とcase of構文を知らなくてハマる。始めのうちlocal scopeなvariableを定義出来るとは知らず時間を無駄にした。もうちょっとMLを学ぶか。結果を見ると構文定義をそのままナゾルだけで構文木評価が出来るのは楽だな。Cで書くとなるとnode定義を準備してvisitor patternで真面目にtree traverseをすることになりそうだ。PrintStmの評価のためにprintExpを導入したが無しでもPrintStmのpattern matchで頑張ればなんとかなりそう。ま、どっちても同じだから気分の問題か。

演習問題1.1a

type key = string;
datatype tree = LEAF | TREE of tree * key * tree;

val empty = LEAF;

fun insert (key, LEAF) = TREE(LEAF, key, LEAF)
  | insert (key, TREE(l, k, r)) =
    if key < k then
        TREE(insert (key, l), key, LEAF)
    else if key > k then
        TREE(l, k, insert (key, r))
    else
        TREE(l, key, r);

fun member (key, LEAF) = false
  | member (key, TREE(l, k, r)) =
    if key < k then
        member (key, l)
    else if key > k then
        member (key, r)
    else
        true;

val t = insert("a", empty);
val t = insert("b", t);
member ("a", t);
member ("b", t);
member ("c", t);

演習問題1.1b, c

type key = string;
datatype 'a tree = LEAF | TREE of 'a tree * key * 'a * 'a tree;

val empty = LEAF;

fun insert (key, value, LEAF) = TREE(LEAF, key, value, LEAF)
  | insert (key, value, TREE(l, k, v, r)) =
    if key < k then
        TREE(insert (key, value, l), key, v, LEAF)
    else if key > k then
        TREE(l, k, v, insert (key, value, r))
    else
        TREE(l, key, value, r); (* overwrite the existing binding*)

fun member (LEAF, key) = false
  | member (TREE(l, k, v, r), key) =
    if key < k then
        member (l, key)
    else if key > k then
        member (r, key)
    else
        true;

exception NOT_FOUND;
fun lookup (key, LEAF) = raise NOT_FOUND
  | lookup (key, TREE(l, k, v, r)) =
    if key < k then
        lookup (key, l)
    else if key > k then
        lookup (key, r)
    else
        v;

val t = insert("a", 1, empty);
val t = insert("b", 2, t);
lookup ("a", t);
lookup ("b", t);
lookup ("c", t) handle NOT_FOUND => ~1;

(* 1.1 c *)

(* t s p i p f b s t *)
val t = insert("t", 1, empty);
val t = insert("s", 2, t);
val t = insert("p", 3, t);
val t = insert("i", 4, t);
val t = insert("p", 5, t);
val t = insert("f", 6, t);
val t = insert("b", 7, t);
val t = insert("s", 8, t);
val t = insert("t", 9, t);

(* a b c d e f g h i *)
val t = insert("a", 1, empty);
val t = insert("b", 2, t);
val t = insert("c", 3, t);
val t = insert("d", 4, t);
val t = insert("e", 5, t);
val t = insert("f", 6, t);
val t = insert("g", 7, t);
val t = insert("h", 8, t);
val t = insert("i", 9, t);

1.1cの評価結果は次の通り

val t = TREE (LEAF,"t",1,LEAF) : int tree
val t = TREE (TREE (LEAF,"s",2,LEAF),"s",1,LEAF) : int tree
val t = TREE (TREE (TREE #,"p",2,LEAF),"p",1,LEAF) : int tree
val t = TREE (TREE (TREE #,"i",2,LEAF),"i",1,LEAF) : int tree
val t = TREE (TREE (TREE #,"i",2,LEAF),"i",1,TREE (LEAF,"p",5,LEAF))
  : int tree
val t = TREE (TREE (TREE #,"f",2,LEAF),"f",1,LEAF) : int tree
val t = TREE (TREE (TREE #,"b",2,LEAF),"b",1,LEAF) : int tree
val t = TREE (TREE (TREE #,"b",2,LEAF),"b",1,TREE (LEAF,"s",8,LEAF))
  : int tree
val t = TREE (TREE (TREE #,"b",2,LEAF),"b",1,TREE (LEAF,"s",8,TREE #))
  : int tree
val t = TREE (LEAF,"a",1,LEAF) : int tree
val t = TREE (LEAF,"a",1,TREE (LEAF,"b",2,LEAF)) : int tree
val t = TREE (LEAF,"a",1,TREE (LEAF,"b",2,TREE #)) : int tree
val t = TREE (LEAF,"a",1,TREE (LEAF,"b",2,TREE #)) : int tree
val t = TREE (LEAF,"a",1,TREE (LEAF,"b",2,TREE #)) : int tree
val t = TREE (LEAF,"a",1,TREE (LEAF,"b",2,TREE #)) : int tree
val t = TREE (LEAF,"a",1,TREE (LEAF,"b",2,TREE #)) : int tree
val t = TREE (LEAF,"a",1,TREE (LEAF,"b",2,TREE #)) : int tree
val t = TREE (LEAF,"a",1,TREE (LEAF,"b",2,TREE #)) : int tree

listが長くなると全部表示してくれないのね。何かoptionがあるのかな。まぁ、いいことにする。

August 10 ,2018:
演習問題1.1d 関数型記号表の為のbalanced tree data structureを提案せよ。
要件を考えると
- ヒントの通り、lookupではtreeを変更してはいけない。
- operationの頻度としてはlookup > insert > delete. 関数型であることを考えるとdelete operationは無いとしても良いか。値の上書きは必要か？insertで入れ替えるとしても良い。頻度としてはinsertと同程度。
単純に考えるとbalanced binary treeになるが、avl treeとかred-back treeだとkeyがstringでnode毎にstringのcompareを行うことになるなぁ。そうするとtrieかternary search treeか。でももうbalanced treeでは無くなってしまう。問題の意図としてはred black treeを実装しろというところか。意図から外れてしまうがtrieを実装してみよう。
そこで少しMLの調べる。String.explodeを知った。option, NONE, SOMEを知った。これでなんとか実装できそうだ。実装は明日。

August 12, 2018:
Trieを実装してみた。functional programmingに慣れてないので昨日実装仕掛けたものは動作せず諦めてdatatypeを別のものに変えてやっと動くものが出来た。出来たcodeを眺めてみるとまぁ、当たり前のことをやっているだけだな。Cかpythonならすぐ実装できる自信があったのだが、思ったよりも時間がかかった。特にstringとcharの変換が意外と面倒だ。なのでstringをexplodeでchar listに変換してから処理することにしたらうまくいった。

datatype id = string;

structure Trie =
struct
  exception InvalidKey;
  exception NotFound;

  type tkey = id;
  type nodeKey = char;
  type tval = int;

  datatype trie_node = NODE of nodeKey * tval option * trie_node list;
  type trie = trie_node list;
  fun new () = [] : trie;

  (* datatype 'a trie_node = NODE of nodeKey * 'a option * 'a trie_node list; *)
  (* type 'a trie = 'a trie_node list; *)

  (* fun new () = [] : 'a trie; *)

  fun insert key value root =
      insert_node (explode key) value root
  and insert_node [] value ns = raise InvalidKey
    | insert_node [c] value [] = [NODE(c, SOME value, [])]
    | insert_node [c] value (NODE(nkey, nval, children)::ns) =
      if c = nkey then
          NODE(nkey, SOME value, children)::ns
      else
          NODE(nkey, nval, children)::insert_node [c] value ns
    | insert_node (c::cs) value [] =
      [NODE(c, NONE, insert_node cs value [])]
    | insert_node (c::cs) value (NODE(nkey, nval, children)::ns) =
      if c = nkey then
          NODE(nkey, nval, insert_node cs value children)::ns
      else
          NODE(nkey, nval, children)::insert_node (c::cs) value ns;

  fun lookup key root =
      lookup_node (explode key) root
  and lookup_node [] ns = raise InvalidKey
    | lookup_node cs [] = raise NotFound
    | lookup_node [c] (NODE(nkey, value, children)::ns) =
      if c = nkey then
          valOf value handle Option => raise NotFound
      else
          lookup_node [c] ns
    | lookup_node (c::cs) (NODE(nkey, value, children)::ns) =
      if c = nkey then
          lookup_node cs children
      else
          lookup_node (c::cs) ns;

  fun delete key root =
      delete_node (explode key) root
  and delete_node [] ns = raise InvalidKey
    | delete_node cs [] = raise NotFound
    | delete_node [c] (NODE(nkey, value, children)::ns) =
      if c = nkey then
          if null children then
              ns
          else
              NODE(nkey, NONE, children)::ns
      else
          NODE(nkey, value, children)::delete_node [c] ns
    | delete_node (c::cs) (NODE(nkey, nval, children)::ns)=
      if c = nkey then
          let
              val children_new = delete_node cs children
          in
              if nval = NONE andalso null children_new then
                  ns
              else
                  NODE(nkey, nval, children_new)::ns
          end
      else
          NODE(nkey, nval, children) :: delete_node (c::cs) ns
end;

val t = Trie.new ();
val t = Trie.insert "a" 1 t;
val t = Trie.insert "ab" 2 t;
val t = Trie.insert "abc" 3 t;
Trie.lookup "a" t;
Trie.lookup "ab" t;
Trie.lookup "abc" t;
val t = Trie.insert "aaa" 4 t;
Trie.lookup "aaa" t;
val t = Trie.insert "aaa" 5 t;
Trie.lookup "aaa" t;
val t = Trie.delete "ab" t;
val t = Trie.delete "aaa" t;
Trie.lookup "ab" t;

テストコードの実行結果は次の通り

val t = [] : Trie.trie
val t = [NODE (#"a",SOME 1,[])] : Trie.trie_node list
val t = [NODE (#"a",SOME 1,[NODE #])] : Trie.trie_node list
val t = [NODE (#"a",SOME 1,[NODE #])] : Trie.trie_node list
val it = 1 : Trie.tval
val it = 2 : Trie.tval
val it = 3 : Trie.tval
val t = [NODE (#"a",SOME 1,[NODE #,NODE #])] : Trie.trie_node list
val it = 4 : Trie.tval
val t = [NODE (#"a",SOME 1,[NODE #,NODE #])] : Trie.trie_node list
val it = 5 : Trie.tval
val t = [NODE (#"a",SOME 1,[NODE #,NODE #])] : Trie.trie_node list
val t = [NODE (#"a",SOME 1,[NODE #])] : Trie.trie_node list

uncaught exception NotFound
  raised at: trie1.sml:44.46-44.54
/usr/lib/smlnj/bin/sml: Fatal error -- Uncaught exception NotFound with 0
 raised at trie1.sml:44.46-44.54

node = []だとwarningが出るのね。型が問題か。だからnull operatorがあるのか。
data typeを一般化してfunctorにするのは気力がなかった。chapter 1で止まっていてもしょうがないのでこれで良いことにする。明日からはchapter 2にうつる。noteも新しいものに移る。

この記事が気に入ったらサポートをしてみませんか？