Hatena::ブログ(Diary)

みずぴー日記

2010-07-09(金)

omake + oUnitでTDD!

| omake + oUnitでTDD! - みずぴー日記 を含むブックマーク

明日は、TDD Bootcamp名古屋です。

というわけで、自分のoUnit + omakeでTDDな環境を晒してみます。もっとクールな方法があったら教えてください><。

ちなみに、構築したサンプルはno titleに置いてあります。

ディレクトリ構造

ディレクトリ構造はこんな感じで、本番コード(./src)とテストコード(./test)が別ディレクトリに分かれています。

.
|-- OMakefile
|-- OMakeroot
|-- src
|   |-- OMakefile
|   |-- fact.ml
|   `-- main.ml
`-- test
    |-- OMakefile
    `-- fact_test.ml

ルートのOMakefile

ルートのOMakefileではサブディレクトリを認識させます。ついでにocamlfindも有効にしておきます。

.PHONY: all clean check

USE_OCAMLFIND = true
OCAML_FLAGS=-w A -warn-error A

if $(not $(OCAMLFIND_EXISTS))
   eprintln(This project requires ocamlfind, but is was not found.)
   eprintln(You need to install ocamlfind and run "omake --configure".)
   exit 1

NATIVE_ENABLED = $(OCAMLOPT_EXISTS)
BYTE_ENABLED = $(not $(OCAMLOPT_EXISTS))

.SUBDIRS: src test

clean:
	rm -f *~ *.opt *.cmi *.cmx *.o *.omc

本番コード側

適当なモジュールを書きます。とりあえず階乗で。

(* src/fact.ml *)
let rec fact n =
  if n = 0 then
    2 (* BUGGGGYYYY *)
  else
    n * (fact (n - 1))

そしてOMakefile。

普通のOCamlプログラムとしてビルドするだけでなく、ライブラリとしてもビルドします。

# src/OMakefile
.PHONY: all clean

FILES[] =
	fact
	main

LIB = target
PROGRAM = main

.DEFAULT: $(OCamlProgram $(PROGRAM), $(FILES))

OCamlLibrary($(LIB), $(FILES))

clean:
	rm -f *~ *.opt *.cmi *.cmx *.o *.omc *.cma *.cmxa $(PROGRAM) *.a

テストコード側

oUnitを使ったテストコードを書きます。

(* test/fact_test.ml *)
open OUnit
open Fact

let _ = run_test_tt_main begin "fact.ml" >::: [
  "fact(3)" >:: begin fun () ->
    assert_equal 6 (fact 3)
  end
] end

そしてテストプログラムビルドします。

このとき先ほど作ったライブラリを使うようにします。

# test/OMakefile
.PHONY: all clean check
OCAMLINCLUDES += ../src

FILES[] =
	fact_test

OCAMLPACKS[] =
	oUnit

PROGRAM = test
OCAML_LIBS += ../src/target

clean:
	rm -f *~ *.opt *.cmi *.cmx *.o *.omc *.cma *.cmxa

.DEFAULT: all

all : $(OCamlProgram $(PROGRAM), $(FILES))

check : all
	./$(PROGRAM)

実行例

$ omake check
*** omake: reading OMakefiles
*** omake: finished reading OMakefiles (0.23 sec)
- build test <check>
+ ./test
F
======================================================================
Failure: 1:0:fact

OUnit: not equal
----------------------------------------------------------------------
Ran: 1 tests in: 0.00 seconds.
FAILED: Cases: 1 Tried: 1 Errors: 0 Failures: 1 Skip:0 Todo:0
*** omake: 38/40 targets are up to date
*** omake: failed (4.16 sec, 0/3 scans, 7/14 rules, 13/130 digests)
*** omake: targets were not rebuilt because of errors:
   <phony <test/check>>

2010-02-01(月)

Practical OCamlを手にいれた!

| Practical OCamlを手にいれた! - みずぴー日記 を含むブックマーク

f:id:mzp:20100201200839j:image

研究室の大掃除のおかげで、かの悪名高きPractical OCamlを手に要れました。

ブログに記事を書くという約束と引き換えに手にいれたので、あとで何かを書きたいと思います。

2010-01-11(月)

型でOCamlの関数を検索できるサービス、OCaml API Searchをリリースしました

| 型でOCamlの関数を検索できるサービス、OCaml API Searchをリリースしました - みずぴー日記 を含むブックマーク

HaskellにはHoogleという型で関数を検索できるグレイトな検索エンジンがあります。関数型言語では、欲しい関数の型がなんとなく分かることが多いので、こいつがものすごく便利です。

でも、Haskellでしか使えないのが悔しい。でも感じちゃう。。

というわけで、OCaml版のno titleを作りました。是非御活用ください。

使い方の例

このあたりから、なんとなく雰囲気を感じとってください。

フィードバックの送り方

  • この日記にコメントをつける。
  • Twitterで@mzpに話しかける。
  • no titleをforkして、パッチを書く。

不具合や不便なところがありましたら、遠慮なく教えてください。

OCamlBrowserとの関係

実は、OCamlBrowserに同様の機能があります。

で、その機能だけを切り出して、CGIとして動かせるようにしたのがno titleです。ガリク先生、ありがとうございます。

その他の検索サービス

GODI Package DocumentationでもOCamlの関数を検索できます。関数名で検索したいときは、こっちのほうが便利だと思います。

没ネタ

f:id:mzp:20100111195236p:image

2009-11-09(月)

OCamlでダイクストラ法

| OCamlでダイクストラ法 - みずぴー日記 を含むブックマーク

30分プログラム、その692。OCamlでダイクストラ法。

"OCaml ダイクストラ法"でググると、昔ボクが書いた不完全な実装がヒットしてしまう。(ダイクストラ法を実装しようとしたら、よくわからないものになった - みずぴー日記)

この不完全な実装を放置するのはよくない気がしたので、ちゃんと実装し直しました。

前回は純粋関数的に書こうとして失敗したので、今回はmutableなフィールドを持っているレコードを使いました。ただし、モジュール内部で隠蔽して、外部からだとまるで副作用が無いかのように扱えるようにしました。

シグネチャ

type 'a graph
type 'a node
type 'a edge

(* グラフの構築 *)
val make_node : 'a -> 'a node
val make_edge : 'a node -> 'a node -> int -> 'a edge
val make_graph : nodes:'a node list -> edges:'a edge list -> 'a graph

(* ノードには任意のデータを持たせれるので、それを取り出す *)
val node_data : 'a node -> 'a

(* 最短距離と経路を求める *)
val shortest : 'a graph -> 'a node -> 'a node -> (int * 'a node list) option

使い方

(* ノードを作る *)
let a = make_node "A"
let b = make_node "B"
let c = make_node "C"
let d = make_node "D"
let e = make_node "E"

(* グラフを構築する *)
let nodes = [
  a; b; c; d; e
]
let edges = [
  make_edge a b 3;
  make_edge b c 1;
  make_edge a c 5;
  make_edge c d 1;
]

let graph = make_graph ~edges ~nodes

(* aからdの最短距離と経路を求める *)
let (distance,path) = shortest a d

実装

(*
compile:

  ocamlfind ocamlc -package extlib -linkpkg dijkstra.mli dijkstra.ml

example:

  let a = make_node "A"
  let b = make_node "B"
  let c = make_node "C"
  let d = make_node "D"
  let e = make_node "E"

  let nodes = [
    a; b; c; d; e
  ]
  let edges = [
    make_edge a b 3;
    make_edge b c 1;
    make_edge a c 5;
    make_edge c d 1;
  ]

  let graph = make_graph ~edges ~nodes

  let (distance,path) = shortest a d
  (* where distance=5 path=[a;b;c;d] *)
*)

open StdLabels

let (@@) f g = f g
let (+>) f g = g f

let sure f =
  function
      Some x ->
	Some (f x)
    | None ->
	None

type 'a node = {
  data: 'a;
  mutable path : int * 'a node list option
}

type 'a edge = {
  from: 'a node;
  to_ : 'a node;
  distance : int
}

type 'a graph = {
  nodes : 'a node list;
  edges : 'a edge list;
  mutable start_node : 'a node option
}

let make_node data = {
  data = data;
  path = (max_int,None)
}

let make_edge from to_ distance = {
  from=from;
  to_=to_;
  distance=distance
}

let node_data {data=data} = data

let make_graph ~nodes ~edges = {
  start_node = None;
  nodes = nodes;
  edges = edges
}

let edges {edges=edges} = edges
let nodes {nodes=nodes} = nodes

let min_node a b =
  if fst a.path < fst b.path then a else b

let minimum_node nodes =
  List.fold_left ~f:min_node ~init:(List.hd nodes) (List.tl nodes)

let connect_edges {edges=edges} node =
  List.filter ~f:(fun {from=from} -> node = from) edges

let cons x xs = x :: xs

let rec update_nodes graph nodes =
  if nodes = [] then
    ()
  else
    let { path=(d, path) } as node =
      minimum_node nodes in
    let edges =
      connect_edges graph node in
      List.iter edges ~f:begin fun {distance=distance; to_=to_} ->
	if distance + d < fst to_.path  then
	  to_.path <-
	    (distance + d, sure (cons node) path)
      end;
      update_nodes graph (ExtList.List.remove nodes node)

let shortest graph first last =
  if graph.start_node <> Some first then begin
    first.path <- (0,Some []);
    update_nodes graph graph.nodes;
    graph.start_node <- Some first
  end;
  match last.path with
      distance,Some path ->
	Some (distance,List.rev (last::path))
    | _,None ->
	None

参考

2009-09-13(日)

pa_field: {foo}を{foo=foo}にするCamlp4拡張

| pa_field: {foo}を{foo=foo}にするCamlp4拡張 - みずぴー日記 を含むブックマーク

将来のOCamlで{foo = foo}のかわりに{foo}と書けるようになるかも、というウワサがあるらしいです。

ステキな機能ですね。

ここ最近、

let f {foo=foo;bar=bar;baz=baz} =
  ...

みたいなコードをずっと書いてて嫌になってきたので、Camlp4で実現してみました。

antiquotationがうまく使えなくて、直接コンストラクタを呼んでますが、とりあえず動きます。

使い方

まず、コンパイルします。

$ ocamlc -pp camlp4oof -I +camlp4 -c pa_field.ml

じゃあ、使ってみましょう。

$ ocaml dynlink.cma camlp4o.cma pa_field.cmo
# type pt = {x:int};;
type pt = { x : int; }
# let x = 42 in {x};;
- : pt = {x = 42}
# let f {x} = x;;
val f : pt -> int = <fun>

あと-ppに渡せば、ocamlcやocamloptでも使えます。

$ ocamlc -pp camlp4oof -I +camlp4 -c pa_field.ml

ソースコード

no titleからダウンロードできます。

一応、ソースコードも貼っておきます。

(*
  pa_field.ml

  To compile:
    ocamlc -pp camlp4oof -I +camlp4 -c pa_field.ml

  To use:
    ocamlc -pp 'camlp4o pa_field.cmo' example.ml
  or
    ocaml dynlink.cma camlp4o.cma pa_field.cmo


  {x; y} == {x=x; y=y}

  Example:
  # type pt = {x:int};;
  type pt = { x : int; }
  # let x = 42 in {x};;
  - : pt = {x = 42}
  # let f {x} = x;;
  val f : pt -> int = <fun>
*)

open Camlp4.PreCast

module Id = struct
  let name = "pa_field"
  let version = "$Id:$"
end

module Field ( Syntax : Camlp4.Sig.Camlp4Syntax) = struct
  include Syntax

  let stream_peek_nth n strm =
    let toks = Stream.npeek n strm in
      try
	Some (fst (List.nth toks (pred n)))
      with Failure _ ->
	None

  let test_no_with =
    let rec test lev strm =
      match stream_peek_nth lev strm with
	| Some (KEYWORD "(" | KEYWORD "with" | KEYWORD "=") ->
	    raise Stream.Failure
	| Some (UIDENT _ | LIDENT _ | KEYWORD ".")  ->
            test (succ lev) strm
	| _ -> () in
      Gram.Entry.of_parser "test_no_with" (test 1)

  EXTEND Gram
    expr: LEVEL "simple" [
      [ "{"; test_no_with; lel = label_expr_list; "}" ->
	  Ast.ExRec (_loc, lel, Ast.ExNil _loc) ]
    ];

    label_expr: [
      [ id = label_longident ->
          Ast.RbEq (_loc, id,Ast.ExId (_loc, id)) ]
    ];

    label_patt: [
      [ id = label_longident ->
          Ast.PaEq (_loc, id, Ast.PaId (_loc, id)) ]
    ];
  END
end

module M = Camlp4.Register.OCamlSyntaxExtension(Id)(Field)

camlspottercamlspotter 2009/09/13 15:23 あ、そーか、パタンマッチもできるのか。便利だけどパッと見キモイ、、、

2009-07-05(日)

正規表現ライブラリ書きました

| 正規表現ライブラリ書きました - みずぴー日記 を含むブックマーク

暑いなー、と思って部屋でごろごろしてたら、いつのまにか正規表現ライブラリを書いてました。なにがおこったか、(ry

まだ、直したいところがいくつかありますが、とりあえず動くようにはなったので公開しときます。

使い方

シグネチャはこんな感じ。

val regexp  : string -> char regexp
val compile : 'a regexp -> 'a list -> ('a list * 'a list) option = <fun>
let f () =
  let r =
    compile @@ regexp "(foo)*" in
  let s =
    explode "foofoo" in
    match r s with
        Some (matched,rest) ->
          Printf.printf "matched = %s\n" @@ implode matched;
          Printf.printf "rest = %s\n" @@ implode  rest
      | None ->
          print_endline "no match"

ソースコード

no title

直したいところ

  • option型を繋げるところが、Maybeモナドっぽい気がする
  • gsubとかのありがちなメソッドを作りたい
  • 'foo**'がパースできない。(foo*)*ならできるけど。

2009-06-05(金)

OCaml Meeting Tokyo 2009があるらしいよ

| OCaml Meeting Tokyo 2009があるらしいよ - みずぴー日記 を含むブックマーク

そこで、日本の OCaml ユーザーの情報交換と親睦を計るために、 OCaml Meeting Tokyo 2009 の開催を提案します。大

学、産業関係者だけでなく、ホビーユーザーも含め、研究から応用事例まで幅の広い情報交換を行っていければと思いま

す。

開催日は8/30でLLTVの次の日。せっかくだから、両方参加しちゃいなYO!

camlspottercamlspotter 2009/06/06 14:35 知りませんでした。偶然一日ずれてますね。よかったよかった。

mzpmzp 2009/06/06 19:01 LLTVほうが後で決まったみたいです。いずれにせよ、重ならなくてよかったです。

2009-05-18(月)

ならしコストによるQueueを実装した

| ならしコストによるQueueを実装した - みずぴー日記 を含むブックマーク

なんとなくならしコストによるQueueを実装してみたので、貼っておきますね。

シグネチャは、標準のQueueモジュールに、ある程度そろえてあります。

http://gist.github.com/113468

osiireosiire 2009/05/19 10:15 functionalだ、すばらしい。

2009-05-16(土)

OCamlでプロファイリング

| OCamlでプロファイリング - みずぴー日記 を含むブックマーク

30分プログラム、その585。OCamlのプロファラを試してみよう。

マニュアル曰く、実行したときに何回関数が呼ばれたか、何回条件分岐が行なわれたかを記録できるらしい。どうも、各関数に何秒かかったか、などの情報は取れないらしい。

1.コンパイル

とりあえず、適当なコードを書く。

let rec fact =
  function
      0 -> 1
    | n -> n * fact (n - 1)

let _ =
  Printf.printf "%d\n" (fact 10)

ocamlcpでコンパイル。

$ ls
fact.ml

$ ocamlcp -o fact fact.ml

# factができてる
$ ls
fact*  fact.cmi  fact.cmo  fact.ml

2.実行

普通に実行する。

$ ./fact
3628800

すると、ocamlprof.dumpができてる。

$ ls
fact*  fact.cmi  fact.cmo  fact.ml  ocamlprof.dump

3.表示

最後に、ocamlprofで結果を表示してやる。

$ ocamlprof fact.ml
let rec fact =
  function
      0 -> (* 1 *) 1
    | n -> (* 10 *) n * fact (n - 1)

let _ =
  Printf.printf "%d\n" (fact 10)

参考

osiireosiire 2009/05/17 20:58 ocamlopt -pオプションで取れるgprofの方が色々と情報多くていいかも。というか、私はそっちしか使ったことない。

2009-05-11(月)

SuffixArray

| SuffixArray - みずぴー日記 を含むブックマーク

30分プログラム、その580。id:Gemmaさんに借りたWEB+DB PRESS Vol.50に、suffix arrayの解説が載っていたのでやってみた。

解説を読んだときは「ちょう簡単じゃん。さくっと実装してやんよ」と思っていたけど、いざ始めたけど、けっこう大変だった。簡単とか言って、ごめんなさい。

そもそもararyとついてる時点で大変なことに気がつくべきだった。ボク、OCamlでarrayを使ったことなんてほとんどないじゃないか。

使い方

シグネチャはこんな感じ。

type t
val make : string -> t
val find : t -> string -> int list

まず、suffix arrayを作る。

# let s =
  SuffixArray.make "abracadabra";;
  val s : SuffixArray.t = <abstr>

で、文字列を検索すると、何文字目から始まっているかが分かる。

# let t =
  SuffixArray.find s "ra";;
  val t : int list = [2; 9]

ソースコード

let (@@) f g = f g

module SuffixArray : sig
  type t
  val make : string -> t
  val find : t -> string -> int list
end = struct
  type t = (string*int) array
  let make s =
    let len =
      String.length s in
    let array =
      Array.init len (fun i -> (String.sub s i (len - i),i)) in
      Array.stable_sort (fun (a,_) (b,_) -> compare a b) array;
      array

  let begin_with (entry,_) subject =
    let subject_size =
      String.length subject in
    let entry_size =
      String.length entry in
      if entry_size < subject_size then
	false
      else
	(String.sub entry 0 subject_size) = subject

  let rec take_back f array i =
    if i < Array.length array && f array.(i) then
      array.(i)::take_back f array (i+1)
    else
      []

  let rec take_forward f array i =
    if 0 <= i && f array.(i) then
      array.(i)::take_forward f array (i-1)
    else
      []

  let take_near f array i =
    array.(i)::take_back f array (i+1) @ take_forward f array (i-1)

  let rec find' s subject first last =
    if first >= last then
      []
    else
      let mid =
	(first + last) / 2 in
	if begin_with s.(mid) subject then
	  List.map snd @@ take_near (fun x -> begin_with x subject) s mid
	else
	    if (fst s.(mid)) < subject then
	      find' s subject (mid+1) last
	    else
	      find' s subject first mid

  let find s subject =
    find' s subject 0 (Array.length s)
end

let s =
  SuffixArray.make "abracadabra";;
let t =
  SuffixArray.find s "ra"

参考

yoirayoira 2009/05/12 02:45 ぼくもおなじことしておなじようになりました。

mzpmzp 2009/05/12 10:24 やっぱり、ボクだけの問題でもなかったんですね。ホントに乗り換えを検討しないとダメですね。