Commits

camlspotter committed bb37519

update

  • Participants
  • Parent commits 3da4be0

Comments (0)

Files changed (4)

 ^_build/
+.*~$

lazy_split_at.rst

+==============================
+splitAt を OCaml で
+==============================
+
+Haskell の関数::
+
+  splitAt :: Int -> [a] -> ([a], [a])
+
+を OCaml での遅延リストに翻訳することを考える。ちなみに::
+
+  type 'a t = 'a desc Lazy.t
+
+  and 'a desc = 
+    | Null
+    | Cons of 'a * 'a t
+
+  let (!!) = Lazy.force
+
+まずどう翻訳したいのか考える
+=======================================
+
+Haskell の ``[a]`` を単に ``'a t`` に変えればいいだけではないか?
+という単純な考えは一般的に良くない。ちゃんと立ち止まって考える。
+
+``splitAt n xs`` は ``xs`` の prefix ``n``個分と、それ以外の postfix 
+を返す。だから、 prefix は常に有限長になる。有限長であって無限長に
+ならないのであれば、そもそも ``'a t`` を使わず ``'a list`` ではないのか、
+と考えるべきだ。つまり、::
+
+   val split_at : int -> 'a t -> 'a list * 'a t
+
+と考える。そうすると、単に ``[a]`` を ``'a t`` に変えた関数::
+
+   val split_at' : int -> 'a t -> 'a t * 'a t
+
+と型が違う。型が違うと意味が違うはずだ。そう考えると、
+``split_at`` と ``split_at'`` がどう動くべき関数であるか
+それなりに演繹できる。
+
+まず無限入力にも停止するミニマルなものを書く
+============================================================
+
+はじめから欲張って ``split_at'`` を書こうとすると大抵何か
+間違いを犯す。まず取り敢えず、どのような ``'a t`` にも結果を返す
+(force すると止まらない ``undefined`` かも知れないが)関数を実装しよう。
+つまり、この場合、 ``split_at`` になる::
+
+  let rec split_at n t =
+    if n = 0 then [], t
+    else match t with
+    | lazy Null -> [], t
+    | lazy (Cons (x,t)) -> 
+        let xs, t' = split_at (n-1) t in
+  	x::xs, t' 
+
+``Lazy.force`` や上述の ``!!`` ではなくパターン部で ``lazy`` を
+使って force した上でマッチしていることに注意。 ``Lazy.force`` や ``!!``
+を使って書いても良い。
+
+しかしそんな事より、この関数が末尾再帰になっていない事が問題。
+ある程度大きい ``n`` を入れるとスタックを食いつぶしてしまう。
+こう書くべき::
+
+  let split_at n t = 
+    let rec aux rev n t =
+      if n = 0 then rev, t
+      else match t with
+      | lazy Null -> rev, t
+      | lazy (Cons (x,t)) -> aux (x::rev) (n-1) t
+    in
+    let rev, postfix = aux [] n t in
+    List.rev rev, postfix
+
+これで出来上がり。``split_at n t`` は ``t`` の ``n`` 個の prefix 
+をそこまでの lazy cons を force した上で普通のリストにして返す。
+呼び出し時に Lazy cons が force されるのは ``split_at`` の型
+に明示されている。Prefix は force されているのでリーク
+(プログラマがもういらないはずなのに、と期待していても GC されないようなデータ)
+もしない。うん、よろしい。
+
+そして一番重要なことだが、ストリームが無限でも ``split_at`` は停止する。
+停止性のみを満たす物を書くのは、これは Haskell の遅延評価を鍵とする関数を
+eager evaluation の言語に移す時の最低基準だからだ。そして最低基準であるから、
+正しい関数も書きやすい。
+
+それから、できるだけ評価が遅延される物を書く
+============================================================
+
+さて、 ``split_at`` を書けたら、次にやることはより遅延が効いた関数を
+書くことだ。 ``split_at n xs`` は prefix の cons を force してしまう。
+``n`` がいくつで有っても結果にアクセスしない限りできるだけ ``xs`` の
+cons が force されないような物を書こう。 ``split_at'`` だ。
+
+事前に ``split_at`` を書いていることで、 ``split_at'`` は次のような
+関数でないのは明らかだ::
+
+  let split_at'_bad n t = 
+    let prefix, postfix = split_at n t in
+    t_of_list prefix, postfix
+
+これでは単に ``split_at`` の結果の prefix 有限リストをストリームに
+変えただけだ。確かに型は目指すものと同じだが、``split_at'_bad n t``
+を呼び出した時点で先頭の ``n`` 個の cons が force されるのは
+``split_at`` と変わらない。
+
+そんなアホな事はしない!?そうだろうか。
+気をつけていてもそういう物を書いてしまうことはある。
+
+分解する時、は lazy で wrap する
+---------------------------------------------
+
+Haskell でのなんとなく lazy になる環境に慣れていたり、
+不注意で OCaml の普通の list の split_at の様にプログラムを書き出すと
+こんなコードになる::
+
+  let rec split_at'_bad2 n t =
+    if n = 0 then lazy Null, t
+    else match t with
+    | lazy Null -> lazy Null, t
+    | lazy (Cons (x,t)) -> 
+        let pref, post = split_at'_bad2 (n-1) t in
+        lazy (Cons (x,pref)), post
+
+これはダメ。何故ダメか。これはちゃんと考えて欲しい。ポイントは二つ::
+
+* 関数に ``t`` を渡すと即座に lazy pattern で force されてしまう。
+* ``split_at'_bad2`` がそのまますぐに再帰呼び出しされているので、
+  ``split_at'_bad2 n t`` は 即座に ``n``回再帰してしまう。
+
+この二つから、この関数は型こそ目標のものと同じだがやっていることは
+結局上の「そんなアホな事はしない!?」と全く同じ。型を合わせただけ、だ。
+
+遅延データを force したら必ずそのコードを lazy で囲もう。つまり、::
+
+  let rec split_at'_bad3 n t =
+    if n = 0 then lazy Null, t
+    else 
+      lazy (match t with
+        | lazy Null -> lazy Null, t
+        | lazy (Cons (x,t)) -> 
+            let pref, post = split_at'_bad3 (n-1) t in
+            lazy (Cons (x,pref)), post)
+
+こうなる。 ``split_at'_bad3`` の再帰呼び出しも lazy の中にあるので
+上記の2つ目の問題、すぐに再帰呼び出しが行われる問題も解決できている。
+しかし、これは型が合っていない。 lazy で wrap してしまったからだ。
+
+Lazy.t を単に !! で外すのはまず間違い
+---------------------------------------------
+
+ここで初めて型合わせをやることになる。とはいえ、次のような型合わせは間違い::
+
+  let rec split_at'_bad3 n t =
+    if n = 0 then lazy Null, t
+    else 
+      !!( lazy (match t with
+        | lazy Null -> lazy Null, t
+        | lazy (Cons (x,t)) -> 
+            let pref, post = split_at'_bad3 (n-1) t in
+            lazy (Cons (x,pref)), post))
+
+lazy で wrap したのを ``!!`` (force) ですぐさま元に戻している、
+これじゃあ意味がない。 ``!!(lazy e)`` は ``e`` と同じだから。
+ここで我々が欲しい型は確かに ``('a t * 'a t) Lazy.t -> 'a t * 'a t``
+なのだが、一番外側の Lazy.t は force や再帰が勝手に進まないために
+導入したものだから外してはいけない。ではどこを外すのか。その内側、つまり::
+
+  ('a t * 'a t) Lazy.t = ('a desc Lazy.t * 'a desc Lazy.t) Lazy.t
+
+の tuple 要素についている ``Lazy.t`` を外すことになる。
+
+  let detuple tpl = fst !!tpl
+================================
+OCaml の object について
+================================
+
+私は OCaml の オブジェクトシステムそして普通世間一般の オブジェクトシステムについて理解が足りないと
+自覚しているので正直こういう文章を書く自信全く無いのですが…
+
+OCaml のオブジェクトは構造的サブタイピング
+==============================================
+
+OCaml の オブジェクト のサブタイピングは structural subtyping というものです。
+世間一般の nominal なサブタイピングとは常識が異なるので、まずそこから難しいく映るかもしれません。
+
+Nominal なサブタイピングの世界
+----------------------------------------------
+
+Nominal な世界ではオブジェクトはクラスに属します。まあ大雑把に言うと オブジェクトの型はクラス名。
+そしてオブジェクトの型(クラス名)はその *名前* で区別(identify)されます。だから nominal と言う。
+
+クラスはオブジェクトの実装を与えると同時にその型を定義します。
+
+クラスは他のクラスを継承でき、サブクラスになります。
+
+オブジェクトのサブタイピングは、それが属するクラスの継承関係がそのまま使われます。
+クラスの identification は名前で行われますから、オブジェクトのサブタイピングもクラス名で決まります。
+
+OCaml の Structural なサブタイピングの世界
+----------------------------------------------
+
+OCaml の Structural な世界ではオブジェクトはクラスに属しません! 
+オブジェクトの型はクラス名ではありません! 
+まあ大雑把に言うとオブジェクトの型はそのオブジェクトが持っているメソッドの型の集合です。
+そしてオブジェクトの型(メソッドの型集合)はその集合の *構造* で区別されます。だから structural と言う。
+
+クラスはオブジェクトの実装を与えますが、その型を定義するものではありません! 
+オブジェクトの型の別名を与えるだけです。オブジェクトの型はあくまでもそのメソッド型集合の構造です。
+
+クラスは他のクラスを継承でき、サブクラスになります。
+
+オブジェクトのサブタイピングはその *構造によってのみ* 決まります。
+サブタイピングにはオブジェクトを生成するのに使用したクラスの継承関係とは *関係ありません。*
+
+
+クラス抜きで考える OCaml のオブジェクト
+===============================================================
+
+オブジェクト、いやさ、多相レコード
+------------------------------------
+
+OCaml のオブジェクトのサブタイピングは nominal つまり属クラス名主義的なものではなく、
+structural つまり、その型の構造で決まる、と言う事を繰り返し強調しました。
+実際 OCaml のオブジェクトのサブタイピングはそのクラスシステムとは独立したものです。
+それはクラスの無いオブジェクト (immediate object) を定義できることからもわかります。::
+
+    object 
+      method m = 1 
+      method n x = x + 1
+    end  
+    (* 型は < m : int;   n : int -> int > *)
+
+実際のところクラス抜きのオブジェクトは多相レコードにほかなりません。
+多相レコードとは、事前の型宣言のいらない型付きレコードのことです。
+
+多相レコードの多相性の例を見ましょう::
+
+    let get_m o = o#m
+    (* 型は get_m : < m : 'a; .. > -> 'a *)
+
+この関数は ``o`` というオブジェクト、いやさ、多相レコードを引数に取りそのメソッド、いやさ、
+フィールド ``m`` を取ってきて返す関数です。 ``get_m`` の型の引数部分を見てください。
+``< m : 'a; .. >`` という形になっている。これは何でもいいから ``m`` というフィールドを
+持つ多相レコード、を意味する型です。実際、::
+
+    # get_m (object method m = "hello" end);;
+    - : string = "hello"
+    # get_m (object method m = 1  method n x = x + 1 end);;
+    - : int = 1
+
+こんな風に ``get_m`` は ``m`` の型が違ってたり、 ``m`` 以外のフィールドが
+存在する多相レコードであっても取り扱うことができます。
+
+``get_m`` の引数の型  ``< m : 'a; .. >`` には二つの多相性があります:
+
+* m の型は何でも良い事を示す型変数 ``'a``
+* m 以外のフィールドが存在してもよいという事を示す ``..``
+
+実際 ``..`` は型変数のような挙動を示すのですが、ここに深入りすると帰ってこれなくなるので
+これくらいにしましょう。
+
+上の例では ``get_m`` が適用されている二つの多相レコードの型は
+``< m : string >`` と ``< m : int;  n : int -> int >`` ですが、
+これを ``< m : 'a; .. >`` の二つの多相性によって上手く扱っているわけです。
+
+あー、なるほど、これが OCaml の構造的サブタイピングな?と思われますか?
+
+*違います。* 
+
+これは多相レコードの多相型によるもので、サブタイプではないのです。
+例えば、 ``< m : 'a; .. >``  の型変数である
+``'a`` が ``int`` に instantiate され、 ``..`` が ``n : int -> int`` に
+instantiate されたものが ``< m : int;  n : int -> int >`` になります。 
+ちょっと ``..`` の部分が構造に関する多相性で特殊ですが、
+これは単に ML の parametric polymorphism の延長に過ぎません。
+
+まあ上では違いますと言い切りましたが、この ``..`` の多相性は
+OCaml のオブジェクトにおける"サブタイプ感"を醸しだすのに重要な要素であることは確かです。
+
+えっじゃあサブタイピングはどこに?
+------------------------------------
+
+OCaml におけるオブジェクトのサブタイピングとは上の多相レコードにおける 
+parametric polymorphism では抑えられない型の大小を取り扱います。
+例えば、::
+
+    object method m = 1 end                         (* < m : int > *)
+    object method m = 2  method n x = x + 1 end     (* < m : int;  n : int -> int > *)
+
+この二つのオブジェクト、そして、それは型推論されません。常に手で書く必要があります。
+
+
+
+クラスの継承関係はオブジェクトのサブタイピングに引き継がれますが、
+それはクラス継承関係が宣言されたからというより、サブクラスから生成される オブジェクトの型構造が
+親クラスから生成されるオブジェクトの型構造を必ず含む、ような継承しか許されないからです。
+=================================
+なぜ CamlP4 はダメなのか
+=================================
+
+これは Twitter で 「P4 の代わりが欲しいよ」と呟いたら多分 OCamlPro の中の人から
+
+「じゃあどこがイヤなのか教えてよ!代わり作るのに役立つから!」
+
+と言われたので、140文字じゃあ無理だなあと思って英語で書きだそうと思ったけどまあ
+アドベントカレンダーの季節だしまあ日本語で書いてからあとで英語にしてもええかなあと思った。
+
+Revised syntax がダメ
+==================================
+
+CamlP4 には悪名高い Revised syntax というものがある。この名前からして、お、OCaml のオリジナルの
+文法はダメで、この Revised を使うのが通なのかなという幻想を抱かせるがそういう事は全くない。
+Revised syntax は見るべきところはあるが結局 P4 の外では誰も使っていない。
+
+