2012-12-02

GoF in OCaml for Advent Calendar 2012 #2

OCaml Advent Calendar二日目です。
Adapterパターンの次はBridgeパターンですが、これは継承と委譲を組み合わせる話なので前回のAdapterパターンと記述的には同じです。省略。という事で、今回はCompositeパターンをOCamlで記述してみます。

Compositeパターン(wikipedia)

Compositeパターンは木構造を作る時に使えるらしい。共通インターフェイスを定義して枝と葉を抽象的に扱います。

module FileSystem = struct
  (* FileInterfaceに相当する型. Folderが子供としてtのlistを持っている. *)
  type t = File of string| Folder of string * t list

  (* 空白を出力する補助関数 *)
  let printDepthSpace n = for i = 0 to n - 1 do print_string " " done

  (* コンストラクタ *)
  let file name = File name
  let folder name = Folder (name, [])

  (* なんか深さを指定するprinter *)
  let rec defaultMethod depth t =
     printDepthSpace depth;
     match t with
       | File name -> 
          print_string name;
       | Folder (name, children) ->
          print_string name;
          List.iter (defaultMethod (depth + 1)) children

   (* 子供を返す関数. 部分関数なのでoption型を返す *)
   let getChildren = function
      | File _ -> None
      | Folder (_, children) -> Some children

   (* 子供を追加する関数.  *)
   let addComponent child = function
      | File _ -> None
      | Folder (name, children) -> Some (Folder (name, child :: children))

   (* 子供を削除する関数. *)
   let removeComponent child = function
      | File _ -> None
      | Folder (name, children) -> Some (Folder (name, List.filter ((=) child) children))
end

直訳するとこのような感じでしょうか。getChildren, addComponent, removeComponetをFileに適用する事はできないのでNoneが返ります。

次回へ続く！ -> http://d.hatena.ne.jp/osiire/20121203

2012-12-01

GoF in OCaml for Advent Calendar 2012 #1

年末で忙しいのにやってしまった感があります。OCaml Advent Calendar作ってしまいました。
　OCaml Advent Calendar
作ったからには三日坊主は目指して参ります。参加したい方は上のページで参加表明お願いします。編集権限お渡しします。

問題のネタですが正直考えるのが大変です。そこで、私の勉強がてら、所謂GoFのデザインパターンをOCamlで書いて紹介してみることにします。これなら20個くらい機械的にいけるでしょう。ただ、私はデザインパターンについて詳しくないので、設計ガーとかオブジェクト指向的にワーとか知りません。とりあえず表面的な書き換えだけ目指します。
なお、GoFをOCamlでっていうネタは下記の論文にあります。日めくりなんてかったるい人はどうぞ。なお、この論文ではGoFパターンをOCamlのオブジェクト機能を使って再現しています。対して本エントリーではモジュールを主に使っていこうと思います。省力化という意味もありますし、うちの会社ではJavascriptを生成するとかの目的以外ではオブジェクト中心のコードは書かないので、モジュールのテクニックをまとめておきたいからです。
　http://people.csail.mit.edu/dnj/teaching/6898/projects/vicente-wagner.pdf
あと、昔yoriyukiさんも同じ事やってらっしゃいます。さすがに内容素晴らしいのですが、数が少ないようなので私は数で攻めます（いや、あくまで希望的観測）。

さて、最初のパターンは何にしよう。とりえあず構造系からいきましょう。Adapterパターンです。Adapterパターンは既存のクラスをラップして自分たちが使いやすいようにメソッド名や引数を変更しちゃおうというものですね。
　http://ja.wikipedia.org/wiki/Adapter_%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3
上のwikipediaの例をOCaml化してみます。

(* 既存の商品モジュール. *)
module Product = struct 
  type t = { cost : int }
  let getCost p = p.cost
end

(* getCostをgetPriceに変更したい. *)
(* 継承によるアダプター *)
module ProductAdapter = struct
  include Product
  let getPrice p = getCost p
end

(* 委譲によるアダプター *)
module ProductAdapter = struct
  type t = Product.t
  let getPrice p = Product.getCost p
end

こんなんでいいのかしら？比較的そのまま適用できますね。
次回に続く！-> http://d.hatena.ne.jp/osiire/20121202

2012-10-08

祖父のコレクション

先月祖父が他界した。享年97歳。数年前まで自転車に乗り庭弄りをしていた元気なおじいちゃんだった。その祖父が集めていた切手やコインがあるとの事で整理してみた。

ダンボールに入ったコレクション。

大半は記念切手や記念コイン。地方自治法施行六十周年記念コインとか1976年から82年までの特殊切手帳など。どれも興味深いのだけど、金庫に納められた古いコインやお札が面白かった。

懐かしの1000円札、500円札、100円札。

古い一円札もあった。年号がなかったのでどれくらい古いものか分からなかったけど、Wikipediaによると「改造一円券」というものらしい。以下全部Wikipedia調べ。http://ja.wikipedia.org/wiki/%E4%B8%80%E5%86%86%E7%B4%99%E5%B9%A3

上のが50銭札。これは「小額政府紙幣 (富士桜) 」。「紀元二千五百九十八年」と書いてあって不思議だったが「皇紀による年号」とのこと。他にも五銭札とか十銭札とか通し番号1番の塔が描かれた十銭札とかあった。

http://ja.wikipedia.org/wiki/%E5%B0%8F%E9%A1%8D%E6%94%BF%E5%BA%9C%E7%B4%99%E5%B9%A3

コインは新しいのから古いのまで色々混ざってたので、年代別に整理。昭和20年以前のもをピックアップ。真ん中の昭和十一年のは一銭。下の昭和3年のは十銭。

大正のは全部でこれだけ。銅のは一銭。銀のが五十銭。大正九年のきれいなやつは十銭。大正のお金なんて初めて見た。

明治と書かれた一銭も。この頃のコインは少し大きめ。

さらに寛永通宝、文久永宝、天保通寳といった江戸時代のお金もあった。さすがに祖父といえど使ってなかったはずで、どっから集めてきたのか。特に天保通寳は上に通し穴みたいのがあって、本物かどうか怪しい。

寛永通宝：　http://ja.wikipedia.org/wiki/%E5%AF%9B%E6%B0%B8%E9%80%9A%E5%AE%9D
文久永宝：　http://ja.wikipedia.org/wiki/%E6%96%87%E4%B9%85%E6%B0%B8%E5%AE%9D
天保通寳：　http://ja.wikipedia.org/wiki/%E5%A4%A9%E4%BF%9D%E9%80%9A%E5%AE%9D

あと日本のものではないと思われる硬貨もあった。

1888年と書かれているのはドイツの硬貨みたいだけど詳細不明。大朝鮮開国後百四年と書かれた銅貨：　http://item.rakuten.co.jp/doragon-coin/gcd006/

調べた限りどれも希少というものではなさそうなので、安心して祖父の思い出として保管しておこうと思う。

[追記]
コレクションの中から息子が持っててた分。こっちの天保通寳は本物っぽい。政和通宝というのが古いやつのようだ。大満州国のコインとかあって戦時中を思わせる。

2012-06-13

emacs+omakeなocamler向けのflymake設定

下記の設定を.emacsに入れてocaml-flymake.shを適当な場所に置くだけ。色はお好みにどうぞ。

(require 'flymake)
(push '("File \"\\(.*\\)\", line \\([0-9]+\\), characters \\([0-9]+\\)--?\\([0-9]+\\):\\(.*\\)" 1 2 3 5) flymake-err-line-patterns)
(push '("\\.ml\\'" flymake-ocaml-init) flymake-allowed-file-name-masks)
(defun flymake-ocaml-init ()
  (list "~/.emacs.d/ocaml-flymake.sh"))
(custom-set-faces
 '(flymake-errline ((((class color)) (:background "LightYellow" :underline "OrangeRed"))))
 '(flymake-warnline ((((class color)) (:background "LightBlue2" :underline "Yellow")))))

ocaml-flymake.sh(/opt/ocaml/binはocamlのバイナリがインストールしてあるパス)

#!/bin/sh
env PATH=${PATH}:/opt/ocaml/bin omake -s 2>&1 | tr -d "\n" | sed -e 's/\t//g'

2012-04-07

イベントドリブンな状態遷移をFRPで記述してみる

例題の仕様は次の通り。

b1,b2というボタンがあり、これらはON,OFFがあるトグルボタン。
modeというトグルボタンがある。
modeがOFFの時、b1とb2は排他的な動きをする(ラジオボタンのような動き)。
modeがONの時、b1とb2は独立なトグルボタンとして動作する。
clearボタンがあり、これが押されるとb1,b2はOFFになる。

これを普通(?)のイベントハンドラ風に記述するとこんな感じ。

type on_off = ON | OFF
let flip = function ON -> OFF | OFF -> ON

(* 状態を保存する変数. 初期値は全部OFF *)
let mode = ref OFF
let b1 = ref OFF
let b2 = ref OFF

(* getter, setterの定義. ここにUIへの反映処理なども記述できる. *)
let mode_getter () = !mode
let mode_setter b = mode := b
let b1_getter () = !b1
let b1_setter b = b1 := b
let b2_getter () = !b2
let b2_setter b = b2 := b

(* modeボタンが押された場合。トグルのみ. *)
let on_mode_clicked () =
  mode_setter (flip (mode_getter ()))

(* 
 * トグルボタンが押された時の処理.
 * (getter, setter)はb1もしくはb2のgetter,setter. othersは第一引数のボタン以外のボタンのsetterのリスト.
 *)
let on_b_clicked (getter, setter) others () =
  (* やや複雑な場合分け. *)
  if getter () = ON then
    if mode_getter () = ON then
      setter OFF
    else
      ()
  else begin
    setter ON;
    if mode_getter () = ON then
      ()
    else
      List.iter (fun setter -> setter OFF) others
  end

(* b1クリック時のイベントハンドラ *)
let on_b1_clicked = on_b_clicked (b1_getter, b1_setter) [b2_setter]
(* b2クリック時のイベントハンドラ *)
let on_b2_clicked = on_b_clicked (b2_getter, b2_setter)  [b1_setter]

(* クリアボタンの機能. *)
let on_clear_clicked () =
  b1_setter OFF;
  b2_setter OFF

さて、これと同じ事をFRP(PEC)で記述してみる。

(* おまじない *)
module E = Pec.Event.Make (Pec.EventQueue.DefaultQueueM) (Pec.EventQueue.DefaultQueueI)
module S = Pec.Signal.Make (E)
open S.OP
open Pec.Event

(* イベントの準備 *)
let b1_click, send_b1_click = E.make ()
let b2_click, send_b2_click = E.make ()
let mode_click, send_mode_click = E.make ()
let clear_click, send_clear_click = E.make ()

(* modeはOFFが初期値でクリックされる度にON/OFFが切り替わる *)
let mode = S.fold (fun b () -> flip b) OFF mode_click

let when_on b e = E.filter (fun _ -> S.read b = ON) e
let when_off b e = E.filter (fun _ -> S.read b = OFF) e

(*
 * ON/OFF状態のシグナルを作成する関数.
 *)
let button_state self_clicked others_clicked =
  let state = S.return OFF in
  (* ONに遷移する条件 *)
  let to_on =
    when_off state self_clicked 
    +> E.map (fun _ -> ON)
  in
  (* OFFに遷移する条件 *)
  let to_off = 
    E.choose [
      when_on mode self_clicked;
      when_off mode others_clicked;
      clear_click
    ]
    +> when_on state
    +> E.map (fun _ -> OFF)
  in
  (* ON条件とOFF条件の重ね合わせがボタンの挙動. *)
  state <=< S.fold (fun _ b -> b) OFF (E.choose [to_on; to_off]);
  state

(* b1シグナル *)
let b1 = button_state b1_click (E.choose [b2_click])
(* b2シグナル *)
let b2 = button_state b2_click (E.choose [b1_click])

どちらも記述量は大して変わらない。FRPの方が宣言的で状態遷移図を直接的に実装している感じ。
b1, b2シグナルを使えば後からUIに対する見た目の効果も加えられるので、setter, getterにそれらを埋め込まなければならないスタイルより独立性が高そう。

2012-03-25

既存モジュールを使って幽霊型を作る

幽霊型は型で特定のお約束を強制的に守るために役に立ちます。しかし、大抵は既存のモジュールの型の意味を後から使い分けたくなるのでそのためのテクニックも追加で必要になります。例えば次のような10進モジュールDecimalがあったとします。

module Decimal = struct
  type t = float (* ホントはNum.numを使った実装にするんだけど、ここでは省略 *)
  let of_float x = x
  let add a b = a +. b
  let sub a b = a -. b
  let compare a b = compare a b
end

このDecimal型を使って、アプリケーション内で消費税を扱いたいとします。そうすると、同じDecimal型でも税込金額とお約束している値とまだ未課税の金額とお約束している値とをaddしてしまうとまずいわけです。こういう時こそ幽霊な訳ですが、Decimalの演算をいちいち全部ラッピングしたくはない。そこで次のような魔術を使うと労力を削減できます。

module TaxedMoney : sig
  type 'a t constraint 'a = [< `Taxed | `NotTaxed ]
  val of_float : float -> [ `NotTaxed ] t
  val add : 'a t -> 'a t -> 'a t
  val sub : 'a t -> 'a t -> 'a t
  val compare : 'a t -> 'a t -> int
  val tax : [ `NotTaxed ] t -> [ `Taxed ] t
end = struct
  type 'a t = Decimal.t constraint 'a = [< `Taxed | `NotTaxed ]
  include (Decimal : (module type of Decimal) with type t := Decimal.t)
  let tax x = x *. 1.05
end

シグネチャーだけは再定義しなければなりませんが、少なくとも実装をラップする作業は避けられます。

2012-02-11

Algorithm W入門を攻略してきた

先日@pi8027さん著の「Algorithm　W入門」を攻略してきました。

http://partake.in/events/22da1e72-032d-49ae-847f-a56606308320

@Mega80bさんに同書をお渡しするついでに読書会です。@t6sさん、@mzpさん、つきあってくれてありがとう。設定したクリア条件は三つ。

練習問題を全部解くこと
実装をコンパイル/実行してみること
C{let}とWの違いを説明できること

結局2.は達成できませんでしたが、1.と3.はクリア。せっかくなので3.の説明を書き留めておきます。
まず単純型付けλ計算における型推論は次のステップで実行されます。(この本の方針では)

項を受け取り、その項の部分項に型付け規則を適用しながら（型と型との）等式の集合を作る。連立方程式みたいなもの。証明木が導出できたらおしまい。
等式の集合から、その解となる型の割り当てを導く（ユニフィケーション）
得られた型の割り当てを元の項に適用して、おしまい。

このアルゴリズムにlet多相を入れると次のようになります。（C{let}）

項を受け取り、その項の部分項に型付け規則を適用しながら（型と型との）等式の集合を作る。
1. ただしlet項の時だけ変数の型が場合によって変わる。let項の型変数のうちlet項の外側の型環境にない型変数は多相にできる。let項の外側の型環境を求めるには、等式の集合をユニフィケーションする。
2. 多相の変数を型環境から取り出す時にはフレッシュな型変数を割り当てる。
等式の集合から、その解となる型の割り当てを導く（さらにユニフィケーション）
得られた型の割り当てを元の項に適用して、おしまい。

これでも目的のlet多相は達成できますが、等式の集合作成時と等式の集合の解を求める時との両方でユニフィケーションが現れます。どうせ等式の集合作成時にユニフィケーションが必要になるなら、もう等式の集合とか作らずに等式が得られるたびに（必要なら）ユニフィケーションしちゃえば、等式の集合を持ちまわって最後にユニフィケーションする必要ないです。

項を受け取り、その項の部分項に型付け規則を適用して（型と型との）等式を作る。
等式から（場合によってユニフィケーションを実行して）型の割り当てを導く。証明木が導出できたらおしまい。
1. let項を多相にするとか、多相な型を環境から取り出す時はフレッシュな型変数を割り当てるとかは前と一緒。
得られた型の割り当てを元の項に適用して、おしまい。

だいぶすっきりしました。これがアルゴリズムW。

osiire’s blog

ふしぎなそふとやさん