トップ 最新 追記

じじぃの日記、ツッコミ可

Twitter: @jijixi_org
Xbox Live: jijixi

初心者が書いた OCaml 入門
Spotlight tips サイト内リンク集
1970|01|02|
2003|10|11|12|
2004|01|02|03|04|05|06|07|08|09|10|11|12|
2005|01|02|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|11|
2011|05|
2012|01|

2006-06-01 [長年日記]

% [Mac] 最近気付いた小ネタ

『ファイルを開く...』とか『別名で保存...』とかのダイアログに付いてる検索枠に / とか ~ とかを入れると Finder の『フォルダへ移動...』と同じダイアログが出て、指定したパスに移動できる。 地味に便利カモ。

% [game] ロコロコ

体験版やったらシビれた。 ぷよぷよ感がたまらん。 買おう。


2006-06-03 [長年日記]

% [Mac] OmniDazzle

一体何の役に立つのかは微妙だけど、何だか無性にわくわくするアプリケーション。 残念ながら、うちの環境 (iMacG5/1.6GHz / GeForce FX 5200) ではあまりスムーズには動かないみたい (今のところ…なのかもしれないけど)。

なんとなく、CoreImage API を使ってわりと簡単にプラグインを作れるようになりそうなイメージだけど、もしそうなったら流行りそうな気がする。

% [Mac][vim] fink の vim が 7.0 になっていた

info ファイルのタイプスタンプを見るかぎり、6/1 のことである。 文句言った途端にアップデートするなんて……あと一週間早くやってくれれば良いのに。

あー、この二度手間感が妙に悔しい...orz


2006-06-04 [長年日記]

% [雑談] その言語のいいとこ挙げてみろ (2ch)

12 が良い。 近いうちにスレが落ちそうな気がするから、コピペしとく↓

Whitespace

ソースの見た目がキレイ

この方向性でネタスレとして伸びてくれれば良かったんだけど、結局盛り上がらずに消えそうな感じで残念。


2006-06-05 [長年日記]

% [vim] 7.0 では :set number 時の行番号表示部が今までの半分になった

地味だけどありがたい改良点。 以前は古式に則った(?)形式で 8 桁を占有してたんだけど、今回から通常は 4 桁で足りなくなったらその都度拡張される形式に変わった。 4 桁のうち行番号の表示に使われるのは実質 3 桁だけど、1,000 行を超えるファイルを編集することなんてそうそう無いだろうから、非常に現実的な線じゃないかと。

わしも最近はすっかり Visual Mode に毒されて行番号とか表示する意味も薄れてきてるんだけど、それでもやっぱり表示されてないと落ち着かなかったりするわけで、とは言え、画面が広く使えるに越したことは無いというのも真実であり、そういう意味でわしにとってはかなり意義のある変更なのであった。

% [OCaml][Haskell] OCaml には zip が無い

いや、実際には同じことする別の名前の関数があるんだけど、微妙に名前がかっこ悪いって言うかね。 こんな感じの対応。

Haskell    OCaml
zip        combine
unzip      split
zipWith    map2

まあ combine と split は、むしろこっちの方が動きをイメージしやすい気がしなくもないけどね。 map2 も map の引数が二つになったバージョンだから良いっちゃ良いんだけど。 じゃあ何が気に入らないのかって、Scheme も Haskell も zip/unzip なのになぜ OCaml だけ違うのかと。 それどころかお仲間だと思ってた SML まで zip なんだけどよー...orz

世の中、Scheme や Haskell の話題ばっかで、それを見ながら「OCaml だとどうかなー」とか考えるときに、関数名の違いって結構思考の妨げになるんだよね。 まあ、foldl だの foldr だのって変な略称じゃなく、fold_left, fold_right って名前を使ってくれてる OCaml の方が好ましくはあるんだけど。(そのくせ List.hd なんて名前を付ける辺りは理解不能だが……)

% [OCaml][Haskell] Haskell と OCaml のリスト操作関数対応表

なんとなく書いてみた。 だいたい一対一で対応しそうなものだけ。

Haskell     OCaml (List モジュール)
map         map , rev_map (結果が逆さまになるけど末尾再帰)
(++)        (@) , append , rev_append (結果が逆さまになるけど末尾再帰)
filter      filter , find_all
concat      concat , flatten
head        hd
tail        tl
length      length
(!!)        nth
foldl       fold_left
foldr       fold_right (引数の順番が違う)
span        partition (一つずつ振り分けるので結果が全然違う)
reverse     rev
any         exists
all         for_all
elem        mem , memq (等値判定に == を使う)
lookup      assoc (見つからない時は例外発生) , assq (等値判定に == を使う)
zip         combine (各リストの流さが違うと例外発生)
zipWith     map2 (各リストの流さが違うと例外発生)
unzip       split

実際に試さず書いてるものもあるんで、間違い勘違いの指摘歓迎。

% [OCaml][雑談] こうして見ると↑

OCaml の標準ライブラリって、中途半端に SML と名前が一致してるのが変。 歴史的事情がよくわかってないから何なんだけど、hd とか tl とか rev とかって関数は古い ML から派生する以前からあったものってことなのかねえ。

% [Haskell] 『ふつうの Haskell プログラミング』買ってきた

さわりのとこと、型クラス、モナドあたりを読んだ。 内容に関してはまあ、『入門 Haskell』と同じようなレベルなのかな。 どちらも、ちゃんと通して読んだわけじゃないから、入門書として優れているのがどちらかはわからん。

『ふつうの』には余談の類が全然無いのが個人的にはつまらないかも。 弾さんの言に倣えば「愛」が足りない(笑

まあ明確に Java プログラマをターゲットにしてるせいもあるのかもしれないけど、もう少し遊びがあっても良いような気がする。 『カリー化』って言葉が 348 ページに至るまで出てこない (付録と索引を除いた最終ページは 352 だ) 辺りにはある種のいさぎ良さを感じるけど。

話ははずれるけど、結局モナドの説明で一番すっきりしてるのは『モナドの物理的なアナロジー』のページなんじゃないか思う。 どっかで「わからないうちはさっぱり意味がわかんないけど、わかるようになればこれが一番わかりやすい」みたいなことが言われてたと思ったが、まさにそういう感じ。 矛盾してるんだけど、そうとしか言いようがないというか(苦笑)。 いきなりこれを読んでもさっぱりなんだけど、ある程度モナドの動きを体で覚えてから読みなおすとカチッとはまる。

% [OCaml] 使い捨ての signature

なんかいろいろ調べてるうちに巡り巡って Concurrent ML のソースなんて読んでたりするんだけど、そこで今まで考えたこと無いような書き方してるところがあって、ちょっとびっくり。 ためしに OCaml でもやってみたらできたんで、何かに使えそうだからメモ。

要するに、module を定義するときの型指定を無名の signature でするって話。 例えばこんな感じ。

# module Hoge : sig
    val hoge : string
  end = struct
    let hoge = "hoge"
    let fuga = "fuga"
  end;;
module Hoge : sig val hoge : string end

# Hoge.hoge;;
- : string = "hoge"

# Hoge.fuga;;
Unbound value Hoge.fuga

ちゃんと fuga が隠蔽されている。 つーか、この位置に signature の定義を直接書けるとは盲点だったなあ。 まあ、今までも struct は無名で使ってたし、それと同じことだと考えれば納得だけど。

% [SML] SML/NJ には first-class continuations がある

ぬおぉ……

% sml
Standard ML of New Jersey v110.58 [built: Sun May 28 16:01:12 2006]
- open SMLofNJ;
[autoloading]
[library $SMLNJ-BASIS/basis.cm is stable]
[autoloading done]
opening SMLofNJ
  structure Cont :
    sig
      type 'a cont = 'a cont
      val callcc : ('a cont -> 'a) -> 'a
      val throw : 'a cont -> 'a -> 'b
      val isolate : ('a -> unit) -> 'a cont
      type 'a control_cont = 'a control_cont
      val capture : ('a control_cont -> 'a) -> 'a
      val escape : 'a control_cont -> 'a -> 'b
    end
(以下略)

……と、ここでさくっと簡単なサンプルでも……と思ったんだけど、SML に慣れてないのに加えて静的型付けだと異様にややこしくて、ほんの簡単なテストすらできなかったのであった。 自分の無能さが切ない...orz

% [SML][OCaml] ついでだからレコード型で遊んでみた

OCaml とどう違うだろう。

- type hoge = { str : string, old : int };
type hoge = {old:int, str:string}

- val h = { str = "hoge", old = 1 };
val h = {old=1,str="hoge"} : {old:int, str:string}

- type fuga = { str : string, new : float };
stdIn:3.34-3.39 Error: unbound type constructor: float

いやん。

- type fuga = { str : string, new : real }; 
type fuga = {new:real, str:string}

- val f = { str = "fuga", new = 2.0 };
val f = {new=2.0,str="fuga"} : {new:real, str:string}

- val h2 = { str = "h2", old = 2 };
val h2 = {old=2,str="h2"} : {old:int, str:string}

おお。

- val { str = s, ... } = h;
val s = "hoge" : string

- val { str = s, ... } = h2;
val s = "h2" : string

- val { str = s, ... } = f; 
val s = "fuga" : string

おお。 各要素に直接アクセスする方法がわからんが、OCaml よりカッチョイイな。 直接アクセスができないってことは、mutable なものを作るのも不可? リファレンス使えば一応できなくはないか?

ともあれ…

- fun get_str r = let val { str = s, ... } = r in s end;
stdIn:8.26-9.53 Error: unresolved flex record
   (can't tell what fields there are besides #str)

あー、さすがにこれはダメか。 "..." は残りの要素を気にしないんじゃなくて、適宜推論するって意味なんだろうな。 だから一意に型を決められない時はエラーって感じ。 この辺は OCaml の object の方が強力だ。

- fun get_str r = let val { str = s, old = _ } = r in s end;
val get_str = fn : {old:'a, str:'b} -> 'b

へぇ……とすると……

- type hoge2 = { str : int, old : string };
type hoge2 = {old:string, str:int}

- get_str { str = 0, old = "foo" };
val it = 0 : int

おー、これはこれでおもしろい。 機能的には OCaml のレコードとオブジェクトの中間って感じかねえ。


2006-06-06 [長年日記]

% [vim] vim 7.0 の新機能

そういやどっかで見かけたまま忘れてたんだけど、タブ機能が付いたらしいのである。 コマンド補完で見てみると、たしかに :tab なんちゃらってコマンドがいっぱいあるわ。 てことで、簡単な使い方とかメモしてみる。 詳細は :help tabpage を見るべし。

:tabe
   新たにタブを開く。ファイル名を続ければ、そのファイルを編集する状態で始まる。

:tab {cmd}
   実行するとウィンドウを分割するようなコマンド (split とか help とか) を指定してやると、
   分割する代わりに新しいタブを開くらしい。

:tabc
   タブを閉じる。

:tabo
   他のタブを閉じる。

:tabn
gt
   次(右)のタブに移動。

:tabp
:tabN
gT
   後ろ(左)のタブに移動。

:tabr
   最初(最左)のタブに移動。

:tabl
   最後(最右)のタブに移動。

:tabs
   タブのリストを表示。

こんな機能が無くても複数のファイルを開いて、切り替えながら編集することは可能なわけだけど、どれだけファイルを開いてるかを常に表示できるという意味では便利なのかしら。 buffer は各タブ共有みたいなんで、複数ファイル指定で開いてから適当にタブに割り振ったりもできそう。 ……なんだけど、そもそも起動時に -p オプションを付けると複数ファイル指定したときにタブに展開してくれるみたいなんで、あんまり気にすることもない。

ともあれ、buffer コマンドとか使ったこと無いような人には便利なんでしょうな。 buffer をバリバリ使ってるような人にはどうなんだろ。 ……って、ああそうか、どうやらタブだといちいち保存しなくても移動できるみたいだ。 これは場合によっては便利かもしれん。

% [vim] とりあえず alias vim='vim -p' な生活をしてみようと思った

たくさんタブが開いてるときに、終了しようと思っても :q じゃタブが一つずつ閉じるだけでウゼーってときは :tabdo q すれば良いようだ。 要するに :tabdo は全部のタブにコマンドを送るコマンドらしい。

% [vim] 実用性はともかく、なんかオラ楽しくなってきたぞ

gvim でタブ使うとなんかイイ。

:set showtabline=2

とかしておくと (なぜ 2 なのかわからんが) 常にタブバーが表示されるようになる。 んでそのバーの空いたとこをダブルクリックすると新しいタブが開いたり、右端の X をクリックするとタブが閉じたり、おまえは FireFox か。

% [Scheme] 繰り返しのための let

SML の callcc を試すサンプルにしようと思ってここのページを読んでたんだけど、↓のコードが読めなくてまいった。

(define list-product
  (lambda (s)
    (let recur ((s s))
      (if (null? s) 1
          (* (car s) (recur (cdr s)))))))

let のとこがさっぱり意味がわからない。 と言うか、結果から考えれば recur は手続きになってるんだと思うんだけど、let ってこんな風に使えんの?……と。

あーもー、ほんとに知らないことだらけだよ。 仕方なく gauche のマニュアルとかほじくる。

まず『4.6 変数束縛』を見るが、それらしき情報は無い。 んで、あーだこーだ探してやっと見つけた『4.8 繰り返し』……あー…… R5RS とか、まともに読んでないのがバレバレです(苦笑

(define (list-product s)
  (if (null? s) 1
      (* (car s) (list-product (cdr s)))))

こう書いてくれれば良いのに……(八つ当たり)

(define list-product
  (lambda (s)
    (letrec ((recur (lambda (s)
                      (if (null? s) 1
                        (* (car s) (recur (cdr s)))))))
      (recur s))))

今までの知識で lambda 使った書き方するならこんな感じ? OCaml なんかだとこういう書き方になると思うんだけど、たしかに繰り返しの let を使った方がすっきりしてるかな。


2006-06-07 [長年日記]

% [SML] callcc の練習

昨日書いたように独習 Scheme 三週間の継続のページからお題をいただく。 まずはこれ。

(+ 1 (call/cc
       (lambda (k)
         (+ 2 (k 3)))))

結果が 4 になれば OK 。

% sml
Standard ML of New Jersey v110.58 [built: Sun May 28 16:01:12 2006]
- open SMLofNJ.Cont;
[autoloading]
[library $SMLNJ-BASIS/basis.cm is stable]
[autoloading done]
opening SMLofNJ.Cont
  type 'a cont = 'a ?.cont
  val callcc : ('a cont -> 'a) -> 'a
  val throw : 'a cont -> 'a -> 'b
  val isolate : ('a -> unit) -> 'a cont
  type 'a control_cont = 'a ?.InlineT.control_cont
  val capture : ('a control_cont -> 'a) -> 'a
  val escape : 'a control_cont -> 'a -> 'b

下準備。 ……んで。

- 1 + (callcc        
=       (fn k =>
=         2 + (k 3)));
stdIn:2.6-4.19 Error: operator and operand don't agree [tycon mismatch]
  operator domain: 'Z cont -> 'Z
  operand:         (int -> int) -> int
  in expression:
    callcc (fn k => 2 + k <exp>)

これではダメ。 まあ、この辺は静的型付けの宿命と言うか。 ただ、SML に慣れてないせいで、いまいちエラーの意味がわからなくて難儀したけど。 この場合、k は 'a cont 型になるはずなのに、(k 3) のところで k が int -> int として推論されてしまってダメってことだね。

てことで、継続を呼び出すには throw を使う。

- 1 + (callcc         
=       (fn k =>      
=         2 + (throw k 3)));
val it = 4 : int

めでたし。

次に継続を保存するパターン。

- val r : int cont option ref = ref NONE;
val r = ref NONE : int cont option ref
- 1 + (callcc
=       (fn k =>
=         r := SOME k; 2 + (throw k 3)));
stdIn:18.32 Error: unbound variable or constructor: k
stdIn:16.6-18.38 Error: operator and operand don't agree [literal]
  operator domain: 'Z cont -> 'Z
  operand:         int
  in expression:
    callcc ((fn k => <exp> := <exp>); 2 + (throw <exp>) 3)

あらー。SML の文法がいまいちわからん。

- 1 + (callcc                            
=       (fn k =>                         
=         (r := SOME k; 2 + (throw k 3))));
val it = 4 : int

これで良いのかな。

- let val SOME k = !r in throw k 5 end;
stdIn:20.42-21.36 Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)
stdIn:21.8-21.20 Warning: binding not exhaustive
          SOME k = ...
Error: throw from one top-level expression into another

ん? どういうエラーだ、これは。 トップレベルの式から別のトップレベル式には飛べないってこと? うーん……

- val _ =
= let val r = ref NONE
= in
=   (1 + (callcc (fn k => (r := SOME k; 2 + (throw k 3))));
=    let val SOME k = !r in print (Int.toString (throw k 5)) end)
= end;
stdIn:52.11-52.23 Warning: binding not exhaustive
          SOME k = ...

Interrupt

……帰ってこなくなった...orz

あー、よくわかんね。 継続の保存はあきらめて次行こう。 続く……

% [SML] callcc の練習その2

13.2 脱出継続を再現。 まず通常のバージョンを SML で書いてみる。

% cat list_product.sml
val list_product =
  fn s =>
    let
      fun recur s =
        if null s then 1
        else (hd s) * (recur (tl s))
    in
      recur s
    end
% sml
- use "list_product.sml";
[opening list_product.sml]
val list_product = fn : int list -> int
val it = () : unit
- list_product [2,3,4];
val it = 24 : int

うむ。 継続を使って脱出するバージョン。

% cat list_product2.sml
open SMLofNJ.Cont

val list_product2 =
  fn s =>
    callcc
      (fn exit =>
        let
          fun recur s =
            if null s then 1
            else
              if (hd s) = 0 then (print "exit\n"; throw exit 0)
              else (hd s) * (recur (tl s))
        in
          recur s
        end)

念のため、継続で抜けるときはメッセージを表示するように。

% sml
- use "list_product2.sml";
[opening list_product2.sml]
  (中略)
val list_product2 = fn : int list -> int
val it = () : unit

- list_product2 [1,2,3,4,5];
val it = 120 : int

- list_product2 [1,2,0,4,5];
exit
val it = 0 : int

はあ、今回は簡単だった。 めでたしめでたし。

さて、さらに続くかは気分次第。

% [SML][OCaml] SML のハマリポイント

こういうの↓

- val o = "hoge";
stdIn:1.4 Error: expression or pattern begins with infix identifier "o"

最初、「なにごとか〜!?」と思った。 練習とかでゴミコードを書き散らすときに一文字変数使いまくるわしにとっては、かなりワナ。

SML では中置の "o" が関数合成演算子として定義されているのであった。 似たようなワナには OCaml の mod がある。

# let mod = "hoge";;
Syntax error

ほんと、記号以外の識別子がこっそり中置扱いになってるのはワナでしかないと思うんだが...orz

% [SML] レコードやタプルの要素に直接アクセス

ふむふむ。

- type r = { name : string, num : int };
type r = {name:string, num:int}

- val hoge = { name = "hoge", num = 1 };
val hoge = {name="hoge",num=1} : {name:string, num:int}

- #name hoge;
val it = "hoge" : string
- val v = ("hoge", "fuga");
val v = ("hoge","fuga") : string * string
- #1 v;
val it = "hoge" : string

良いな、これ。

- type r = { name : string ref, num : int ref };
type r = {name:string ref, num:int ref}

- val hoge = { name = ref "hoge", num = ref 0 };
val hoge = {name=ref "hoge",num=ref 0} : {name:string ref, num:int ref}

- (#name hoge) := "fuga";
val it = () : unit

- hoge;
val it = {name=ref "fuga",num=ref 0} : {name:string ref, num:int ref}

% [雑談] 流行に乗りたくない症候群

なんつーかね、Haskell とかすっかりメジャーになりつつあって、もうあんまりマジメにいじる気になれないの。 その点 OCaml は良いよね。 世間が ML を通りこして Haskell に行っちゃったんなら、このままずっとマイナーなままだろ(ぉぃ

そんなマイナー志向のわしが今興味を持ってるのは SML なわけだが。 いや、厳密に言うと SML でも SML/NJ 限定か。 素の SML はやっぱりシンプルすぎるというか、おもしろいのは主に SML/NJ の独自拡張の部分だったりする。 でも SML/NJ のソースアーカイブの混沌っぷりはどうかしてるんで何とかしてほしいもんだが…… どこに何があるのか、わかりゃしねえ。

そういや SML# のソースは部外者でも見れるようになったのかな。

% [SML] OCaml にも local 構文欲しいなぁ

良いなー、欲しいなー

- local
=   val s = "hoge" 
=   fun f x = s ^ x
= in
= val hoge = f        
= end;
val hoge = fn : string -> string

これがあれば、わざわざ mli ファイル作らなくても簡単に関数を隠蔽できるのに。

まあ、要するにそういうことなんだろうな。 SML には OCaml の mli に相当する仕組みが無いみたいだから (よく調べないで言ってますよ)、こういう構文が無いといろいろ大変だろう。


2006-06-08 [長年日記]

% [SML] SML のレコードっていちいち type 宣言しなくて良いのか

タプルの仲間みたいな扱いなのかな。 ちょっとうらやましいかも。

でも、ちょろっとテストするときとかならともかく、ちゃんとしたものを書くならどっちみち何か型名付けるような気がするし、それほどうらやましいってわけでもないか。


2006-06-09 [長年日記]

% [Nemerle] 遅延評価があると言うので、たらいまわしてみようかと思ったのですよ

んで、四苦八苦しながら以前の向井さんの OCaml バージョンを参考にしつつ、↓ってとこまで書いた。

% cat tak.n
using System;
using Nemerle;

class M {
   static Tak ([Lazy] x : int,
               [Lazy] y : int,
               [Lazy] z : int) : int
   {
      if (x <= y) {
         y;
      } else {
         Tak(lazy(Tak(lazy(x), lazy(y), lazy(z))),
             lazy(Tak(lazy(y), lazy(z), lazy(x))),
             lazy(Tak(lazy(z), lazy(x), lazy(y))));
      }
   }

   public static Main (args : array [string]) : void {
      def (x, y, z) =
         if (args.Length == 4) {
            (Convert.ToInt32(args[1]),
             Convert.ToInt32(args[2]),
             Convert.ToInt32(args[3]));
         } else {
            (10, 5, 0);
         };
      IO.printf("tak(%d, %d, %d) = %d\n", x, y, z,
            Tak(lazy(x), lazy(y), lazy(z)));
   }
}

ここまで来て、ようやくコンパイルできたので、ともあれ実行してみる。

% ncc -o tak tak.n
% mono tak.exe
[1]    1172 illegal hardware instruction  mono tak.exe

これ以上デバッグする気が失せた...orz

えーと……型安全とかは……と思ったが、この辺りの説明には type safe だなんて一言も書かれていないのであった。 ……いや、そういう問題か?

いくらわしのコードがヘボだとしても、こんな死に方する Mono にも問題はあると思うんだが、とは言えそんな地雷を見事に踏んじゃう Nemerle もまた罪なやつよのう。 念の為環境もメモっとこう。

% mono -V
Mono JIT compiler version 1.1.10, (C) 2002-2005 Novell, Inc and Contributors.
www.mono-project.com
        TLS:           normal
        GC:            Included Boehm (with typed GC)
        SIGSEGV      : normal
% ncc -V
Nemerle Compiler (ncc) version 0.9.3 (release)
(c) 2003-2005 University of Wroclaw, All rights reserved.

はあ、なんか変な風に疲れた。 また今度、Mono を新しくしたらやってみよう。

% [OCaml] Syntax extension for Monads in Ocaml

via reddit.

Haskell の do 記法を追加する camlp4 モジュール。 一緒にいくつかのモナド実装も含まれてるが、それはとりあえず置いておく。

(>>=) 演算子に相当する bind という名前の関数が存在すれば使えるので、ここはあえてわしのモナドもどきを使ってみるテスト(笑

% ocaml
# #use "topfind";;
# #camlp4o;;
# #load "pa_monad.cmo";;
# #load "monad.cma";;

# open MonadIO;;        
# let bind = (>>=);;
val bind : 'a Monad.t -> ('a -> 'b Monad.t) -> 'b Monad.t = <fun>
# let m =                  
  perform                  
    putChar 'H';           
    putChar 'e';           
    putStrLn "llo World!";;
val m : unit Monad.t = <abstr>
# invoke m;;
Hello World!
- : unit = ()

わは、使える。

# let n =
  perform
    c <-- getChar ();
    return c;;
val n : char Monad.t = <abstr>
# invoke n;;
0
- : char = '0'

よし、モナドもどきにもあらかじめ (>>=) の別名として bind を仕込んでおくことにしよう。


2006-06-10 [長年日記]

% [Nemerle] たらいまわしリベンジ

昨日の続き。

mono を↓にバージョンアップしてみた…

% mono -V
Mono JIT compiler version 1.1.13.8, (C) 2002-2005 Novell, Inc and Contributors.
 www.mono-project.com
        TLS:           normal
        GC:            Included Boehm (with typed GC)
        SIGSEGV      : normal

…が同じエラーで死ぬ。 仕方ないのでとりあえず遅延評価を使わないようにしてみようと思ってコードをいじってたら気付いた…………再帰するときに 1 引くのがどっか行ってる...orz

lazy がどーのこーのって辺りを試行錯誤しながらいじってるうちに抜けてたんだなあ。 最初はちゃんと 1 引いてたはずなんだけど(負けおしみ)。 そりゃ同じ値で再帰すりゃ無限ループだわなぁ。 まあ、だからって illegal hardware instruction なんて死に方してちゃあかんと思うが…… って言うか、ちゃんとスタックオーバーフローで死んでくれてれば、もう少し早く問題に気付けたよ。

ともあれ問題は解決できたので、続きをやってみたよ。 Main メソッドが受けとる配列の仕様が想定と違ってたんで、そこら辺の直しもやって、できたのが以下のコード。

using System;
using Nemerle;

class M {
   static Tak ([Lazy] x : int,
               [Lazy] y : int,
               [Lazy] z : int) : int
   {
      if (x <= y) {
         y;
      } else {
         Tak(lazy(Tak(lazy(x - 1), lazy(y), lazy(z))),
             lazy(Tak(lazy(y - 1), lazy(z), lazy(x))),
             lazy(Tak(lazy(z - 1), lazy(x), lazy(y))));
      }
   }

   public static Main (args : array [string]) : void {
      def (x, y, z) =
         if (args.Length == 3) {
            (Convert.ToInt32(args[0]),
             Convert.ToInt32(args[1]),
             Convert.ToInt32(args[2]));
         } else {
            (10, 5, 0);
         };
      IO.printf("tak(%d, %d, %d) = %d\n", x, y, z,
            Tak(lazy(x), lazy(y), lazy(z)));
   }
}

んでテスト。

% ncc -o tak tak.n
% time mono tak.exe 100 50 0
tak(100, 50, 0) = 100
mono tak.exe 100 50 0  0.26s user 0.08s system 52% cpu 0.642 total

いちおう遅延評価を使わないバージョンも作ってみたけど↓

% ncc -o tak_normal tak_normal.n
% time mono tak_normal.exe 100 50 0
^C
mono tak_normal.exe 100 50 0  20.01s user 0.31s system 79% cpu 25.613 total

終わらないんで途中で止めた。 ちなみに gauche の遅延評価使用版だと…

% time gosh tak.scm 100 50 0
tak(100, 50, 0) = 100
gosh tak.scm 100 50 0  0.09s user 0.03s system 51% cpu 0.242 total

これくらい。 まあ、Nemerle とか Scala とかは最初にランタイムを読み込むのがえらく時間かかるんで、こういう起動してすぐ終わるようなもので実行時間を比べてもあんまり意味無い感じだけど。

できあがったコードを見ればわかると思うけど、Nemerle の遅延評価機構って Scheme や OCaml のものと違って force 関数みたいな『ここで評価します』みたいなのが無いんだよね。 そのせいで Tak を再帰するところではいちいち全部 lazy で包みなおしてるのが汚ない。 まあ、大抵の場合はこういう仕様の方が便利なんだろうけど。 でも、これってどうやって実装してんだろ。マクロ?


2006-06-11 [長年日記]

% [Nemerle] 遅延評価の実装

Lazy evaluation のページをよく見たら、下の方に書いてあったけど、やっぱマクロだったんだね。 ソースへのリンクもあるけど、わしには読めない(苦笑

lazy が LazyValue クラスの値を作ってるのはさすがにわかる。 Lazy はたぶん実際の動きから考えるに、仮引数名に .Value (LazyValue の値を取り出すメソッド) を付加したり、型名を LazyValue に書き換えたりしてるんだと思われ。

% [Nemerle] 実は Nemerle ってマクロだらけの言語だった

なんとなくソース眺めてたらこのファイルを見てびっくり仰天。 if とか while とかの制御構造が軒並マクロで書かれてる。 ほんとの組み込み文法はすごく少ないみたい。 そうかー、そういう言語だったのか。

他にも Memoize とか便利そうなマクロがいろいろあるみたいなんだけど、ソース見ただけじゃイマイチ使い方がわかんない (ヌルい) のが残念。 ドキュメントも見当たらないし……


2006-06-12 [長年日記]

% [C++] C++ ってある意味関数型言語なんだなーと思った

ここ(J) を読んだ感想。

C++ は『オブジェクト指向言語』じゃなくて、『オブジェクト指向も使えるマルチパラダイム言語』だってのは知識としてはわかってるつもりだけど、こういう実例を見せられると改めて納得する。 Java は『オブジェクト指向言語』だから、こういうの書きにくそう。 Java の Generics はこういう (多相関数を作るような) 使い方できないよね、たしか。

% [雑談] 子猫 vs Frontrow (YouTube)

悶え死にそうになった(笑

% [OCaml] 三日坊主企画、『C言語による最新アルゴリズム事典』の例を OCaml で書いてみるコーナー

暇なんだったら SICP でも買えば良いのに……と思いつつ、流行に乗りたくない症候群なのであえてこういう斜めにずれたことをやってみたり。 すぐ飽きるかもしれないんで、続くかどうかは神のみぞ知る。

基本的にはアルゴリズム自体は変えないようにしつつ、C からのベタ移植 (while 使いまくりとか) は避けてなるべく OCaml らしく書くように心がけるつもり。 てことで頭の方から順番に。 と言いつつ、最初の『値の交換』はスルー。 OCaml ではこんなこと考える意味が無いからね。 今後もそういうのはスルーする予定。

……どうせだから、新しくカテゴリ作って次から始めよう。 つづく。

% [OCaml][アルゴリズム事典] 暗号

rand_max のでっち上げ方がキモかったかも。

% cat crypt.ml
exception Bad_args

let crypt ?(seed = 1) in_ch out_ch =
   let rand_max = max_int - 1 in
   Random.init seed;
   let rec mk_num () =
      let r = (Random.int rand_max) / ((rand_max + 1) / 256) in
      if r >= 256 then mk_num () else r
   in
   let rec crypt' () =
      try
         let c = input_byte in_ch in
         output_byte out_ch (c lxor (mk_num ()));
         crypt' ()
      with End_of_file -> ()
   in
   crypt' ()

let main () =
   try
      let argc = Array.length Sys.argv in
      if argc < 3 ||  argc > 4 then raise Bad_args;
      begin try
         let in_ch = open_in Sys.argv.(1) in
         let out_ch = open_out Sys.argv.(2) in
         let seed = begin
            try
               Some (int_of_string Sys.argv.(3))
            with _ -> None
         end in
         match seed with
         | None -> crypt in_ch out_ch
         | Some s -> crypt ~seed:s in_ch out_ch
      with _ -> raise Bad_args
      end;
      exit 0
   with
   | Bad_args ->
        prerr_endline "Usage: crypt infile outfile [key]";
        exit 1
   | _ -> exit 2

let _ = main ()

入出力がからむとどうしても例外を使いまくりになるんだけど、try 節をネストするときはカッコや begin..end で囲むのを忘れないようにしないと色々痛い目を見る。 crypt' 関数のところは、Stream.of_channel を使って iter でががっと回してもおもしろかったかもしれないなー。

% [OCaml][アルゴリズム事典] 安定な結婚の問題 (失敗)

リストを使って書いてみようと思ったんだけど挫折...orz

元の例のとおり配列使ってどんどん中身を書き換えていくやり方なら簡単なんだけど、副作用無しで書こうとすると、なんか適当なデータ構造作ってやるとかしないとややこしくて無理っぽい (少なくともわしの脳ミソでは……)。 てことで、このお題はまた今度。 まあ、配列版は書いといても良いけど、今日はもうめんどいや。

本日のツッコミ(全2件) [ツッコミを入れる]

% みずしま [一応、JavaのGenericsにも多相関数に相当するものはあります が(JLSでは<a href="http://..]

% jijixi [認識不足を指摘ありがとうございます。 Java の Generics も C++ の Template もあんまりち..]


2006-06-13 [長年日記]

% [OCaml][アルゴリズム事典] 安定な結婚の問題

C の例は関数型思考的にはあまりにも美しくないので(苦笑)、配列使って書くのは美意識が許さないんだけど、とは言え、単純なリストではどうにもうまく行きそうにないので、結局 Map モジュールを使った。 んで、結局美しく書けたのかと言うと……うあぁ、聞かなかったことにして...orz

% cat marriage.ml
module M = Map.Make (struct
                        type t = int
                        let compare = Pervasives.compare
                     end)

let start = 1
let num   = 3

let input_rank n =
   let rec loop count name map =
      match count with
      | 0 -> map
      | _ ->
           let str = read_line () in
           let rec mapping idx l =
              if idx < 0
              then l
              else
                 let i = int_of_string (Char.escaped str.[idx]) in
                 if i < start || i > n || List.mem i l
                 then invalid_arg "bad input."
                 else mapping (idx - 1) (i :: l)
           in
           let tmp = mapping (n - 1) [] in
           loop (count - 1) (name + 1) (M.add name tmp map)
   in
   loop n start M.empty

let rec couple girls boys =
   let pairs =
      M.map begin fun v ->
         match v with
         | x :: xs -> x
         | _ -> failwith "unknown error."
      end boys
   in
   let dup_list, _ =
      M.fold begin fun i v tup ->
         let dup, exist = tup in
         if M.mem v exist
         then
            let l = i :: (M.find v exist) in
            (M.add v l dup, M.add v l exist)
         else (dup, M.add v [i] exist)
      end pairs (M.empty, M.empty)
   in
   if M.is_empty dup_list
   then pairs
   else
      let boys' =
         let rank_check g bs seed =
            let rec check gs =
               match gs with
               | x :: xs ->
                    if List.mem x bs
                    then
                       List.fold_left begin fun s v ->
                          if v = x then s
                          else 
                             let b = M.find v s in
                             M.add v (List.tl b) s
                       end seed bs
                    else check xs
               | _ -> failwith "unknown error."
            in
            check (M.find g girls)
         in
         M.fold rank_check dup_list boys
      in
      couple girls boys'

let main () =
   let n =
      try
         int_of_string Sys.argv.(1)
      with _ -> num
   in
   let girls = input_rank n in
   let boys  = input_rank n in
   let cpl =
      M.fold begin fun i v lst ->
         M.add v i lst
      end (couple girls boys) M.empty
   in
   M.iter begin fun i v ->
      Printf.printf "girl %d - boy %d\n" i v 
   end cpl;
   exit 0

let _ = main ()

ぶっちゃけ配列を使わない時点で元とは違うロジックで書くしかなくて、ちゃんとアルゴリズムを再現できてるのかはさっぱりわからんす。 一応なんとなく動いてるような気はするけども……

誰かがもっとこう、エレガントなコードを書いてくれると良いなあ。

% [OCaml][アルゴリズム事典] 石取りゲーム 1

結婚問題はやっててつらかったけど、これは楽しんで書けた。 インチキ英語炸裂してるけど……

% cat ishi1.ml
let rec prompt checker str =
   print_string str;
   let r = read_line () in
   let i =
      try
         let tmp = int_of_string r in
         if checker tmp
         then tmp
         else failwith str
      with
      | Failure _ ->
         print_endline "invalid value! input again.";
         prompt checker str
      | e -> raise e
   in
   i

type winner = Me | You

let print_num = Printf.printf "%d stone(s) left.\n"

let rec my_turn stone max =
   match stone with
   | 0 -> Me
   | _ ->
        print_num stone;
        let x = (stone - 1) mod (max + 1) in
        let x' = if x = 0 then 1 else x in
        Printf.printf "I take %d stone(s).\n" x';
        your_turn (stone - x') max
and your_turn stone max =
   match stone with
   | 0 -> You
   | _ ->
        print_num stone;
        let x = prompt
                   (fun i -> i > 0 && i <= max && i <= stone)
                   "How many stones you'll take? "
        in
        my_turn (stone - x) max

let main () =
   let checker i = i > 0 in
   let stone = prompt checker "Number of stones? " in
   let max   = prompt checker "Max of to take? " in
   let winner = my_turn stone max in
   begin
      match winner with
      | Me  -> print_endline "You lost."
      | You -> print_endline "You won."
   end;
   exit 0

let _ = main ()

自分と相手の手番を、相互再帰した関数で行ったり来たりさせてるあたりがお楽しみポイント。 どーでも良いけど、これって必ずコンピュータ側が先手だから、絶対勝てないと思ふ。

% [雑談] 某メーリングリストに…

さりげなく 3 タブ同盟なコードを晒してる人がいて、ちょっぴり嬉しかった :-)


2006-06-14 [長年日記]

% [OCaml][アルゴリズム事典] エジプトの分数

三日坊主との宣言どおりだんだんかったるくなってきたので、ぱらぱら本をめくってさらっと書けそうな短めのものを選んでやってくことにした。 元々順番に読んでくような本じゃないし。 あと、端末入出力の部分も飽きたんで省略。 どうせ対話環境でいじれるんだしね。

% cat egypfrac.ml
let frac m n =
   let rec frac' m' n' ret =
      match n' mod m' with
      | 0 -> (n' / m') :: ret
      | _ ->
           let q = n' / m' + 1 in
           frac'
              (m' * q - n')
              (n' * q)
              (q :: ret)
   in
   frac' m n []

典型的な末尾再帰のパターン。 再帰するときに引数の順番を間違えて、変な結果に悩んだのは内緒 (ヌルいなあ……)。 や、m とか n とかって適当な変数名なのが良くないよ、うん、そういうことだと思う。 ……そういうことだと良いなあ。

% [雑談] gooサジェストβ with ATOK

おもしろいなあ、これ。 特に skk とかの、ひらがな直入力な環境でバシバシ入力してくと楽しすぎる。

% [OCaml][アルゴリズム事典] 累乗

整数乗の方だけ。 次への伏線。

% cat power.ml
let ipower x n =
   let rec ipower' x' n' ret =
      match n' with
      | 0 -> ret
      | _ ->
           let ret' = if n' land 0x1 > 0 then ret *. x' else ret in
           ipower' (x' *. x') (n' lsr 1) ret'
   in
   let r = ipower' x (abs n) 1. in
   if n >= 0 then r else (1. /. r)

二進数ってすごいなーっていうアルゴリズム。 でも、今どきこんな方法知らなくても困らない気はするけど。 ただまあ、こういうビット演算を使う方法ってパズル的でおもしろいのは確か。

% [OCaml][アルゴリズム事典] Fibonacci 数列

ぶっちゃけ C の例の fib2 が何やってんのか、さっぱりわからん(苦笑)。 わからんので『行列の累乗』ってのをもう少し素直に書いてみたりした。 これの無駄を省いていけば、いつかは C の例になる……のか? (行列とかわかんね)

% cat fib.ml
let rec fib n =
   match n with
   | 1 | 2 -> 1
   | _ when n > 0 ->
        (fib (n - 1)) + (fib (n - 2))
   | _ ->
        invalid_arg "error"

let fib1 n =
   int_of_float ( (((1. +. (sqrt 5.)) /. 2.) ** (float_of_int n))
                  /. (sqrt 5.) +. 0.5)

let fib2 n =
   let n2n1 = (1, 1) in
   let matrix = ((1, 1), (1, 0)) in
   let m_multi m1 m2 =
      let (m1_11, m1_12), (m1_21, m1_22) = m1 in
      let (m2_11, m2_12), (m2_21, m2_22) = m2 in
      ((m1_11 * m2_11 + m1_12 * m2_21,  m1_11 * m2_12 + m1_12 * m2_22),
       (m1_21 * m2_11 + m1_22 * m2_21,  m1_21 * m2_12 + m1_22 * m2_22))
   in
   let m_multi' m v =
      let (m11, m12), (m21, m22) = m in
      let v1, v2 = v in
      (m11 * v1 + m12 * v2,  m21 * v1 + m22 * v2)
   in
   let m_pow m p =
      let rec pow m' p' r =
         match p' with
         | 0 ->
              begin match r with
              | x :: xs ->
                   List.fold_right (fun m1 m2 -> m_multi m2 m1) xs x
              | [] -> invalid_arg "error"
              end
         | _ when p' > 0 ->
              let r' = if p' land 0x1 > 0 then m' :: r else r in
              pow (m_multi m' m') (p' lsr 1) r'
         | _ -> invalid_arg "error"
      in
      pow m p []
   in
   match n with
   | 1 | 2 -> 1
   | _ when n > 0 ->
        let r, _ = m_multi' (m_pow matrix (n - 2)) n2n1 in r
   | _ -> invalid_arg "error"

一つ目 (fib) は C 版の移植じゃなくて、漸化式を素直に書き下したもの (関数型言語のマニュアルでは定番やね)。 二つ目 (fib1) は C 版の fib1 をそのまま OCaml に直したもの。 三つ目 (fib2) は行列を使って書かれた漸化式を、さっきの累乗のアルゴリズムを利用して書いたもの。 はっきり言ってほんとにあってるのかさっぱりなんだけど、とりあえず他と同じ結果が出るみたいなんで多分なんとかなってる。 C 版の fib2 は速いアルゴリズムとして紹介されてるけど、こっちのはたぶん全然速くないっす。 つーか、富豪的には一つ目のをメモ化しときゃ良いだろーと。

……とここまで書いてから、ふと思いついて Wikipedia を見てみたら、行列から答えを導く方法が書いてあるな。 日本語版には無いのに…… あとで読もう。

% [OCaml] Digest モジュール

向井さんとこ読んでて、ちょっと気になったんで OCaml の MD5 絡みを調べてみた。

どうやら Digest.file という関数があって、ファイル名を指定するとダイジェスト値を返してくれる。 んで、file 関数は Digest.channel 関数を使って実装されていて、この channel 関数は C で書かれた関数で実装は byterun/md5.c の caml_md5_chan という関数だ。 この関数をざっと眺めるかぎり、4096byte のバッファを使って処理を回してるみたい。

Ruby みたいにバッファの大きさを自分で決めることはできないけど、ファイルを全部読み込んで…みたいな富豪すぎることにはならないみたいで一安心。


2006-06-15 [長年日記]

% [PC][雑談] 富豪なクイックソート

Haskell のすごいところっていう文脈でよくでてくるクイックソートって、たしかにシンプルでカッコイイけど、あれって曲芸的なかっこ良さであって現実には役に立たないんとちゃうのー?? みたいなネタを書こうと思ったんだけど、念のため調べてみたら向井さんがとっくの昔に言いたいこと全部言ってくれてたので終了。

基本的にクイックソートのアルゴリズムってリストに向いてないと思う。 ちなみに OCaml の List モジュールのソートは向井さんの言うとおりマージソートだけど、Array モジュールでは sort がヒープソートで stable_sort, fast_sort がマージソートらしい。

あとクイックソートはある程度入力値の傾向がわかってて、それに応じたチューニングができるようなシチュエーションじゃないとオーダーの変動が大きすぎるから、ライブラリ側が用意することってあんまり無いんじゃないかって気もする。 C には qsort ってのがあるけど、現実はともかく規格上は別にどんなアルゴリズムで実装しようが関係ないはず。

% [OCaml][アルゴリズム事典] ISBN 番号

定義上はかけ算を使うのに、隣の要素との足し算だけで済ませてしまうのがおもしろい。 自分じゃこんなの絶対思いつかない気がする。 つーか、思いつこうとも思わないってか?

% cat isbn.ml
let rec read_number s =
   let re = Str.regexp "^[0-9]+[0-9xX]$" in
   match String.length s with
   | 10 as len when Str.string_match re s 0 ->
        let rec loop ct ret =
           match ct with
           | 0 -> ret
           | _ ->
                let n = ct - 1 in
                let i =
                   let c = s.[n] in
                   if c = 'x' || c = 'X'
                   then 10
                   else int_of_string (Char.escaped c)
                in
                loop n (i :: ret)
        in
        loop len []
   | _ ->
        invalid_arg "error"

let check s =
   let lst = read_number s in
   let f a b =
      match a with
      | [] -> invalid_arg "error"
      | x :: xs as l ->
           (x + b) :: l
   in
   let result =
      let seed = [0] in
      let l1 = List.fold_left f seed lst in
      let l2 = List.fold_left f seed (List.rev l1) in
      (List.hd l2) mod 11
   in
   if result = 0
   then `Valid
   else `Wrong

それにしても、Str モジュールはしょぼいなー。

% [OCaml][雑談] List.stable_sort

…のソースを読むとちょっとおもしろい。 まあ、自分でマージソート書くとしても似たようなことやりそうな気はするけど。

要するに、マージ時に append じゃなく rev_append を使うために、正順ソートと逆順ソートを交互にやってんのね。 スタック消費を抑えるための涙ぐましい努力だなー(笑)。 や、標準ライブラリとして作るなら、これくらいやるべきだとは思うけども。


2006-06-16 [長年日記]

% [OCaml][雑談] object についての小ネタ

OCaml のオブジェクトって、いわゆる『オブジェクト指向言語』の経験者が初めていじるとハマリポイントが多い気がするんだけど、それを乗り越えて独特の感触を掴めればいろいろおもしろい。 てことで、適当にツラツラ書く。

例えば、今までにも書いたことあるけど、メソッドの型が一致してさえいれば、継承関係とか関係なく一元的に扱えるって話。

# class hoge = object
    method hoge = "hoge"
    method quack = "meow" 
  end;;
class hoge : object method hoge : string method quack : string end

# class fuga = object
    method fuga = "fuga"
    method run = print_endline "run"
    method quack = "bowwow"
  end;;
class fuga :
  object method fuga : string method quack : string method run : unit end

# let h, f = new hoge, new fuga;;
val h : hoge = <obj>
val f : fuga = <obj>

# let quack obj = print_endline obj#quack;;
val quack : < quack : string; .. > -> unit = <fun>

# quack h;;
meow
- : unit = ()

# quack f;;
bowwow
- : unit = ()

この例では hoge クラスと fuga クラスには継承関係なんて無い。 単に quack という名前で string 型を返すメソッドを持っているという点が一致してるだけ。 まあ、Java とかでも interface を使えばこういうことはできるけど、そういうかったるいこと抜きにできるってのがありがたいわけで。

注意点としては、オブジェクトは関数よりも多相化の縛りがキツイので、上記の quack 関数みたいなのはオブジェクトの中に入れないようにした方が良い。 オブジェクトは構造体に毛が生えたもの程度と考えて、メソッド定義は内部状態をいじるものやアクセサの類に限定して、それ以外の操作は外部の関数を使うと面倒が少ないと思う。 名前空間なんかは、モジュールでいくらでもパッケージできるわけだし。

話は変わって、mutable なオブジェクトを作るときのバッドノウハウ。 OCaml ではインスタンス変数は常に隠蔽されるので、アクセスするには適当にメソッドを定義してやらなきゃならない。 で、オーバーロードとかはできないので結局こんなのを量産することになる。

# class foo = object
    val mutable name = "foo"
    method get_name = name
    method set_name s = name <- s
  end;;
class foo :
  object
    val mutable name : string
    method get_name : string
    method set_name : string -> unit
  end

ウザい。 アクセサを自動定義してくれる機能とか付けてくれって思う (と言いつつ、最近はそもそもこういう構成のオブジェクトを作らなくなってるけど)。

んで、外部に公開するようなものならこういう風にするのも仕方ないと思うけど、内部だけで使うなら少しインチキしても良いのとちゃう? などと思ったのであった。

# class bar = object
    val name = ref "bar"
    method name = name
  end;;
class bar : object val name : string ref method name : string ref end

# let obj = new bar;;
val obj : bar = <obj>

# !(obj#name);;
- : string = "bar"

# obj#name.contents;;
- : string = "bar"

# obj#name := "baz";;
- : unit = ()

# obj#name.contents;;
- : string = "baz"

たぶんタイプ量は大幅に減る(笑

% [OCaml][雑談] レコードの代わりにオブジェクト

某所を見てて、そーいやー今は object 式ってのがあったんだよなーと思い出したんだけど、これって SML のレコードみたいな使い方ができそうだなーと思った。

- val r = { re = 3.14, im = 0.0 };
val r = {im=0.0,re=3.14} : {im:real, re:real}
- #re r; 
val it = 3.14 : real

SML だとこういうのが…

# let r = object method re = 3.14 method im = 0.0 end;;
val r : < im : float; re : float > = <obj>
# r#re;;
- : float = 3.14

こんな感じで。 mutable なの作ろうとするとちょっとめんどいけど…

ファクトリを書いてやれば、class を定義して new するのとほとんど同じことができる。

# let make a b = object
    method a = a
    method b = b
  end;;
val make : 'a -> 'b -> < a : 'a; b : 'b > = <fun>
# let o = make "hoge" 0;;
val o : < a : string; b : int > = <obj>

もしこれと同じのを class 定義からやろうとすると…

# class ['a,'b] hoge a b = object
    method a : 'a = a
    method b : 'b = b
  end;;
class ['a, 'b] hoge : 'a -> 'b -> object method a : 'a method b : 'b end
# let o = new hoge "hoge" 0;;
val o : (string, int) hoge = <obj>

こんなかな。 継承とか initializer とかが必要無いなら、object 式で書いた方が楽だね。 型変数とかに気をつかわなくて良いし。

……と思ったら継承も initializer も使えるよ。 クラス名とかどーでも良いなら、class なんて定義する必要無いのか? まあ、被継承クラスは定義しなきゃならんだろうけど……

# let o = object(self)           
    inherit ['a,'b] hoge "hoge" 0
    method p = "hoge"            
    initializer                  
      print_endline "hoge"       
  end;;                          
hoge
val o : < a : string; b : int; p : string > = <obj>

何はともあれ、レコード型を使う理由が減っていく感触(苦笑


2006-06-17 [長年日記]

% [Mac] OmniDazzle 1.0

正式版になった。 最終的にライセンス形態をどうする気なのか気にしてたんだけど、結局未登録の場合は『一時間ごとにアプリケーションを再起動する必要がある』だけで、他の制限は無い模様。 それ以上がっちり使いたい人は $14.95 払う (もちろんそうじゃなくても、気に入ったならなるべく払ってあげて欲しい)。 まあ、良い感じに落ち付いた。

下手な制限の仕方だと流行らずに消えるかもと思ったけど、これなら多分大丈夫だろう。 一時間ごとに再起動ってのも、金を払わずに済ませたい人が享受すべき面倒としては無難なとこだと思うし。 つーか、今のところずっと起動しっぱなしにしなきゃならないようなプラグインが無いんで、事実上制限なんて無いようなもんな気がする。

% [Mac] OmniDazzle がサポートするビデオカード

うちの iMac G5 は GeForce FX 5200 なんだけど、最初のうちは Fully Supported になってたはずなのに、結局最終的には Partially Supported になっちゃってるなあ...orz

% [OCaml][Mac] OCaml を 64bit バージョンでビルド (失敗)

せっかく PowerPC G5 のマシンを使ってるんだから OCaml も 64bit 版を使ってみたいなーと思ったのである (ぶっちゃけ必要性は無いんだけども)。

なんだけど、基本的に何も指定しないで gcc を呼び出すと arch が ppc になってしまうので、じゃなくて ppc64 で呼ばれるようになってもらわないといけない。 んで、gcc 側でそれをやる方法がわからんので、OCaml の configure を適当にいじって 64bit 版を呼ぶようにしてみた。 非常にアドホックだけど (つーか、ちゃんと動くようならもっとちゃんとパッチ書こうと思ったんだけどさ…)

--- configure.orig     2006-06-13 21:17:14.000000000 +0900
+++ configure  2006-06-13 21:36:15.000000000 +0900
@@ -22,7 +22,7 @@
 mandir=''
 manext=1
 host_type=unknown
-ccoption=''
+ccoption='gcc -m64'
 cclibs=''
 curseslibs=''
 mathlib='-lm'
@@ -537,7 +537,7 @@
       mksharedlibrpath="-rpath "
       shared_libraries_supported=true;;
     powerpc-apple-darwin*)
-      mksharedlib="cc -bundle -flat_namespace -undefined suppress -o"
+      mksharedlib="cc -m64 -bundle -flat_namespace -undefined suppress -o"
       bytecccompopts="$dl_defs $bytecccompopts"
       #sharedcccompopts="-fnocommon"
       dl_needs_underscore=true
@@ -627,8 +627,8 @@
   *,gcc*,*,*)          nativecccompopts="$gcc_warnings";;
 esac
 
-asflags=''
-aspp='$(AS)'
+asflags='-arch ppc64'
+aspp='$(AS) -arch ppc64'
 asppflags=''
 asppprofflags='-DPROFILING'
 
@@ -1043,7 +1043,7 @@
                  else bng_asm_level=1
                  fi;;
   mips-*-*)      bng_arch=mips; bng_asm_level=1;;
-  powerpc-*-*)   bng_arch=ppc; bng_asm_level=1;;
+  powerpc-*-*)   bng_arch=ppc64; bng_asm_level=1;;
   sparc*-*-*)    bng_arch=sparc; bng_asm_level=1;;
   x86_64-*-*)    bng_arch=amd64; bng_asm_level=1;;
   *)             bng_arch=generic; bng_asm_level=0;;

んで、この configure を使ってビルドしてみると、make world はうまく行ったんだけど、make opt でエラーが出て止まる。

../boot/ocamlrun ../ocamlopt -warn-error A -nostdlib `./Compflags pervasives.cmx` -c pervasives.ml
/tmp/camlasm8ca0bc.s:433:Value 0x3cb0000000000000 truncated to 0x0.
/tmp/camlasm8ca0bc.s:439:Value 0x10000000000000 truncated to 0x0.
/tmp/camlasm8ca0bc.s:445:Value 0x7fefffffffffffff truncated to 0xffffffff.
/tmp/camlasm8ca0bc.s:451:Value 0x7ff0000000000001 truncated to 0x1.
/tmp/camlasm8ca0bc.s:457:Value 0xfff0000000000000 truncated to 0x0.
/tmp/camlasm8ca0bc.s:463:Value 0x7ff0000000000000 truncated to 0x0.
Assembler error, input left in file /tmp/camlasm8ca0bc.s
make[1]: *** [pervasives.cmx] Error 2
make: *** [libraryopt] Error 2

どうも 64bit の値を使おうしてるのに 32bit に丸められてしまってるみたい? なんのこっちゃ……

件の箇所は…

       .long   9218868437227405311

みたいになってるんだけど、ppc64 でも .long は 32bit だってことなのかなあ。 そうだとすると、ocamlopt まで修正しないとダメっぽい。 つーか、こんな基本的な部分でハマるんだとすれば、他にどんだけ不具合があるかわかったもんじゃないな……がっくり。

てことで、基本的にはあきらめムード。 一応、バイトコード版はできてるので、遊んでみる。

% OCAMLLIB=./stdlib byterun/ocamlrun ./ocaml
        Objective Caml version 3.09.2

# max_int;;
- : int = 4611686018427387903
# min_int;;
- : int = -4611686018427387904

わーい。

# Sys.word_size;;
- : int = 64
# Sys.max_string_length;;
- : int = 144115188075855863
# Sys.max_array_length;;
- : int = 18014398509481983

ふう、ごちそうさま。 おまけとして、32bit だとどんな結果かも貼っとこ。

# max_int;;
- : int = 1073741823
# min_int;;
- : int = -1073741824
# Sys.word_size;;
- : int = 32
# Sys.max_string_length;;
- : int = 16777211
# Sys.max_array_length;;
- : int = 4194303

64bit ってすげぇなあ(笑

% [OCaml][Mac] せっかくだからバイトコード版だけでもキープしとくことに

./configure 後、config/Makefile を…

...
LIBDIR=$(PREFIX)/lib/ocaml64
...
EXE=64

くらいいじっておいて、make world …… yacc/Makefile にバグ発見。

28c28
<       $(CC) $(CFLAGS) $(CCLINKFLAGS) -o ocamlyacc $(OBJS)
---
>       $(CC) $(CFLAGS) $(CCLINKFLAGS) -o ocamlyacc$(EXE) $(OBJS)

これでビルドはできるので、あとはインストール……とその前に、make -n install で確認。 うーん、ocamlmktop と ocamlmklib の名前に問題あり。 通常の OCaml は godi で別の場所に入れてるから上書きの心配は無いんだけど、名前で区別できないと面倒だからこれも直す。 tools/Makefile を修正。

84c84
<       cp ocamlmktop $(BINDIR)/ocamlmktop
---
>       cp ocamlmktop $(BINDIR)/ocamlmktop$(EXE)
95c95
<       cp ocamlmklib $(BINDIR)/ocamlmklib
---
>       cp ocamlmklib $(BINDIR)/ocamlmklib$(EXE)

これでオッケーかなーと思ったら camlp4 に $(EXE) が伝搬してない...orz $(LIBDIR) は伝わってるのになんでだ。 あうう。Makefile を修正。

260c260
<       cd camlp4; $(MAKE) install BINDIR=$(BINDIR) LIBDIR=$(LIBDIR) MANDIR=$(MANDIR)
---
>       cd camlp4; $(MAKE) install BINDIR=$(BINDIR) LIBDIR=$(LIBDIR) MANDIR=$(MANDIR) EXE=$(EXE)

あーもー不毛な作業だな。 camlp4/etc/Makefile もか。 くそー、おまえら $(EXE) に関するデバッグしてないだろ。

88,89c88,89
<       cp mkcamlp4.sh "$(BINDIR)/mkcamlp4"
<       chmod a+x "$(BINDIR)/mkcamlp4"
---
>       cp mkcamlp4.sh "$(BINDIR)/mkcamlp4$(EXE)"
>       chmod a+x "$(BINDIR)/mkcamlp4$(EXE)"

なんかまだ opt 方面で似たような問題ありそうに見えるけど、とりあえず今必要な分は直せたようだ。 あーぐったり。 よし、ではやっとこ make install だな。 ……はあ、ocamldoc/Makefile もね。

260c260
<       $(CP) $(OCAMLDOC)$(EXE) $(INSTALL_BINDIR)/$(OCAMLDOC)$(EXE)
---
>       $(CP) $(OCAMLDOC) $(INSTALL_BINDIR)/$(OCAMLDOC)$(EXE)

やっと終了。

% ocaml64
zsh: command not found: ocaml64

orz

もう死んでほしい。

% head -n1 /usr/local/bin/ocaml64
#!/usr/local/bin/ocamlrun

これだもんなー…… もうめんどくさいから、エディタで書き換えて終わりにするよ...orz

今日の教訓
OCaml をビルドするときには EXE 変数を使うな

% [OCaml][アルゴリズム事典] Eratosthenes (エラトステネス) のふるい

何やら巷では素数が熱いらしいので。 なんか停止条件を勘違いしまくって、妙に時間がかかってしまった...orz

% cat sieve1.ml
let mk_seed n =
   let s =
      Stream.from begin fun i ->
         let r = i * 2 + 3 in
         if r <= n then Some r else None
      end
   in
   Stream.npeek n s

let sieve1 seed =
   let fold_f a b =
      let lst, next, base, cont = a in
      if b <= base || b mod base <> 0
      then (b :: lst,
            (if b > base then min b next else next),
            base,
            cont)
      else (lst, next, base, true)
   in
   let rec fold s =
      let l, n, _, c = s in
      if c
      then begin
         let r = List.fold_left fold_f ([], max_int, n, false) l in
         fold_rev r
      end
      else l
   and fold_rev s =
      let l, n, b, c = s in
      let s' =
         ([],
          max_int,
          (if c then n else b),
          false)
      in
      let r = List.fold_left fold_f s' l in
      fold r
   in
   2 :: (fold (seed, List.hd seed, 0, true))

let sieve n = sieve1 (mk_seed n)

いまいち合ってるのか心配なんだけど、合ってるってことにする。 一応末尾再帰な fold_left だけを使うようにしてるんで、それなりに速いしスタック溢れの心配も無いはず。 ……と言うつもりだったんだけど、Stream.npeek がスタックオーバーフローするワナ...orz

Stream じゃなく Array を使えば良かったかなぁ。 いや、それよりマジメに逆順のリスト作って fold_rev から始めるようにすりゃ良いのか。 でも、めんどいからもう良いや(駄

% [OCaml][アルゴリズム事典] 続 Eratosthenes

ちょっと考えてみたら大した手間でもなさそうだったんで、結局書いた。 今度こそ stack overflow free だと思う。 まあ、それでも heap full には対処してないけども。

% cat sieve1_2.ml
let mk_seed n =
   let rec loop ct l =
      if ct > n then l
      else loop (ct + 2) (ct :: l)
   in
   loop 3 []

let sieve1 seed =
   let fold_f a b =
      let lst, next, base, cont = a in
      if b <= base || b mod base <> 0
      then (b :: lst,
            (if b > base then min b next else next),
            base,
            cont)
      else (lst, next, base, true)
   in
   let rec fold s =
      let l, n, _, c = s in
      if c
      then begin
         let r = List.fold_left fold_f ([], max_int, n, false) l in
         fold_rev r
      end
      else l
   and fold_rev s =
      let l, n, b, c = s in
      let s' =
         ([],
          max_int,
          (if c then n else b),
          false)
      in
      let r = List.fold_left fold_f s' l in
      fold r
   in
   2 :: (fold_rev (seed, 3, 0, true))

let sieve n = sieve1 (mk_seed n)

いじったのは mk_seed 関数と sieve1 の最後の行だけ。 n = 100,000 くらいなら、わりとすんなり行く。 それ以上になるとメモリとの戦いな気が。 つーか、その辺になると結果が出てもリストじゃ使いものにならんだろうな(苦笑

% [OCaml][Haskell] strict な言語では左向き、lazy な言語では右向きが偉い

fold の話。厳密には言語というより、リストが正格か遅延かって話だと思うけど。

ともあれ、OCaml 使いなら List.fold_right より、末尾再帰な List.fold_left を好んで使うに違いない……と思う。 逆に Haskell の場合は foldl より foldr を使った方が良いらしいが、どうしてなのかはピンと来てない。 なんでだろう。

% [OCaml] Stream モジュールで遊ぶ

唐突に思いついたんで Stream の map とか書いてみる。

# let map f stream =                                                    
    Stream.from (fun i ->
      try Some (f (Stream.next stream))
      with Stream.Failure -> None);;
val map : ('a -> 'b) -> 'a Stream.t -> 'b Stream.t = <fun>

# let s1 = Stream.from (fun i -> print_int i; print_newline (); Some i);;
val s1 : int Stream.t = <abstr>

# let s2 = map (fun v -> v * 2) s1;;
val s2 : int Stream.t = <abstr>

# Stream.npeek 10 s2;;
0
1
2
3
4
5
6
7
8
9
- : int list = [0; 2; 4; 6; 8; 10; 12; 14; 16; 18]

map した後もちゃんと遅延してるのがわかる。 でも、map 後のストリームを使う前に元のストリームをいじっちゃうと……

# let s3 = Stream.from (fun i -> if i < 20 then Some i else None);;
val s3 : int Stream.t = <abstr>

# let s4 = map (fun v -> v * 2) s3;;
val s4 : int Stream.t = <abstr>

# Stream.iter (fun i -> print_int i) s3;;
012345678910111213141516171819- : unit = ()

# Stream.iter (fun i -> print_int i) s4;;
- : unit = ()

ショボーン。空っぽ。

% [OCaml] Stream モジュールの隠し関数で遊んでみる

stream.mli とか読むとわかるけど、"For system use only, not for the casual user" と書かれた関数が存在する。

val iapp : 'a t -> 'a t -> 'a t
val icons : 'a -> 'a t -> 'a t
val ising : 'a -> 'a t

val lapp : (unit -> 'a t) -> 'a t -> 'a t
val lcons : (unit -> 'a) -> 'a t -> 'a t
val lsing : (unit -> 'a) -> 'a t

val sempty : 'a t
val slazy : (unit -> 'a t) -> 'a t

val dump : ('a -> unit) -> 'a t -> unit

それぞれリストに例えると…

iapp    => [0;1] @ [2;3] -> [0;1;2;3]
icons   => 0 :: [1;2;3]  -> [0;1;2;3]
ising   => [0]

lapp, lcons, lsing  => 上記三つの遅延評価版

sempty  => []
slazy   => よくわからん

こんな感じ。 dump は Stream.t の内部表現を可視化する。

# Stream.dump print_int (Stream.of_list [1;2;3]);;
{count = 0; data = Scons (1, Scons (2, Scons (3, Sempty)))}
- : unit = ()

なんかこの辺使うとストリームの map とか fold とか書けそうではあるね。 あとでやってみっかなー。

% [OCaml][アルゴリズム事典] 続続 Eratosthenes

1,000,000 個目の素数を求めろとかって話になってんのねー。 さすがにさっきのでそれをやる度胸は無いから、今度は配列使って書いてみた。 速度はともかく、メモリ効率はそこそこじゃないかしら。 とりあえず求める個数分の配列さえ確保できれば何とかなる。

let mk_nums () = Stream.from (fun i -> Some (3 + i * 2))
let mk_buf n = Array.make (n + 1) None

exception Break
exception Finish
let check ary num =
   try
      let rec loop idx =
         match ary.(idx) with
         | Some i ->
              if i > num / 2 then raise Finish;
              begin match num mod i with
              | 0 -> raise Break
              | _ -> loop (idx + 1)
              end
         | None -> raise Finish
      in
      loop 0
   with
   | Break  -> false
   | Finish -> true

let sieve num =
   let s = mk_nums () in
   let next () = Stream.next s in
   let buf = mk_buf num in
   let _ = buf.(0) <- Some 2 in
   let is_prime = check buf in
   let last = num - 1 in
   let rec loop n idx =
      if idx = num
      then ()
      else begin
         let idx' =
            if is_prime n
            then begin
               buf.(idx) <- Some n;
               idx + 1
            end
            else idx
         in
         loop (next ()) idx' 
      end
   in
   loop (next ()) 1;
   match buf.(last) with
   | Some i -> i
   | None -> failwith "error"

let main () =
   let n = int_of_string Sys.argv.(1) in
   let r = sieve n in
   Printf.printf "%dth prime number is %d\n" n r

let _ = main ()

対話環境で動かしてみたら、10,000 くらいで数秒待つようになってきたから、やっぱりネイティブコンパイルしてやってみる。

% ocamlopt -o sieve sieve1_array.ml

% time ./sieve 10000
10000th prime number is 104729
./sieve 10000  0.89s user 0.02s system 67% cpu 1.341 total

% time ./sieve 100000
100000th prime number is 1299709
./sieve 100000  86.78s user 1.21s system 69% cpu 2:06.62 total

さて、このスケールで行くと 1,000,000 だと何時間かかるんだ? 残念だけどやる気がしない(苦笑

一応バイトコード版で 100,000 にチャレンジしてみたけど…

% time ./sieve_b 100000
^C
./sieve_b 100000  356.55s user 4.37s system 78% cpu 7:41.35 total

いつまでも終わらないんで途中で止めた。 やっぱ重い処理になると随分違うんだなー。


2006-06-18 [長年日記]

% [雑談] あー、なんか昨日ははりきりすぎだったなー

昨日の分の日記がすごい量になってるよ(苦笑

素数ネタは L.L.Ring のページにトラックバックするかどうか迷ったけど、結局やめた。 だってシャイなんだもん。 つーか、コードが長いからさー、「こんなん LL ちゃう」言われたらスンマセン言うしかないやん?

ところで、昨日の配列使ったバージョンは、単に n 番目の素数を返せば良いだけならバッファに使う配列のサイズを半分くらいにできる。 結局ふるいのチェックに使うのは n 番目の素数の半分の大きさの素数までだから。 その場合、配列は n/2 + マージンくらいの大きさで良いと思う。 けど、なんかさすがにそこまでするのは貧乏くさいし、せっかく計算した素数を捨てるのもったいないしってことであーゆー形に。

% [OCaml][アルゴリズム事典] 続x3 Eratosthenes

1000000個の素数(HaHaHa!) を読む。 ……あーーそーーかーー...orz

n/2 じゃなく sqrt n までチェックすれば良いんだ。 たしかにそんな感じだなあ。

てことで、昨日のをほんのちょっぴり手直し。

--- sieve1_array.ml     2006-06-18 00:50:00.000000000 +0900
+++ sieve1_array_2.ml   2006-06-18 14:28:11.000000000 +0900
@@ -8,7 +8,7 @@
       let rec loop idx =
          match ary.(idx) with
          | Some i ->
-              if i > num / 2 then raise Finish;
+              if i * i > num then raise Finish;
               begin match num mod i with
               | 0 -> raise Break
               | _ -> loop (idx + 1)
% ocamlopt -o sieve_2 sieve1_array_2.ml

% time ./sieve_2 10000
10000th prime number is 104729
./sieve_2 10000  0.08s user 0.03s system 27% cpu 0.408 total

% time ./sieve_2 100000
100000th prime number is 1299709
./sieve_2 100000  0.91s user 0.03s system 83% cpu 1.127 total

% time ./sieve_2 1000000
1000000th prime number is 15485863
./sieve_2 1000000  18.90s user 0.34s system 73% cpu 26.036 total

わー、劇的に速くなった。 でも色気を出してもう一桁…と思うと、

% time ./sieve_2 10000000
Fatal error: exception Invalid_argument("Array.make")
./sieve_2 10000000  0.00s user 0.02s system 20% cpu 0.092 total

配列のサイズ制限に引っかかる(苦笑)。 Bigarray 使ってやってみても良いけど、かったるいから良いや。 ぶっちゃけ素数なんてどうでも良いし。

あー、でも 64bit OCaml のネイティブ版が作れてたら配列でやってみたかったなーって気はするかも。

% [OCaml][アルゴリズム事典] 続x4 Eratosthenes

いい加減これで最後。 lethevert さんのを参考に、配列の要素をレコードにしたら微妙に速くなったんで、これで完成形ってことにしよう。

type prime = { n : int; nn : int }
let mk_nums () = Stream.from (fun i -> Some (3 + i * 2))
let mk_buf n = Array.make (n + 1) None

exception Break
exception Finish
let check ary num =
   try
      let rec loop idx =
         match ary.(idx) with
         | Some {n = i; nn = ii} ->
              if ii > num then raise Finish;
              begin match num mod i with
              | 0 -> raise Break
              | _ -> loop (idx + 1)
              end
         | None -> raise Finish
      in
      loop 0
   with
   | Break  -> false
   | Finish -> true

let sieve num =
   let s = mk_nums () in
   let next () = Stream.next s in
   let buf = mk_buf num in
   let _ = buf.(0) <- Some { n = 2; nn = 2*2 } in
   let is_prime = check buf in
   let last = num - 1 in
   let rec loop n idx =
      if idx = num
      then ()
      else begin
         let idx' =
            if is_prime n
            then begin
               buf.(idx) <- Some { n = n; nn = n*n };
               idx + 1
            end
            else idx
         in
         loop (next ()) idx' 
      end
   in
   loop (next ()) 1;
   match buf.(last) with
   | Some { n = i; nn = _ } -> i
   | None -> failwith "error"

let main () =
   let n = int_of_string Sys.argv.(1) in
   let r = sieve n in
   Printf.printf "%dth prime number is %d\n" n r

let _ = main ()
% ocamlopt -o sieve_3 sieve1_array_3.ml

% time ./sieve_3 10000
10000th prime number is 104729
./sieve_3 10000  0.09s user 0.03s system 48% cpu 0.230 total

% time ./sieve_3 100000
100000th prime number is 1299709
./sieve_3 100000  0.86s user 0.04s system 88% cpu 1.011 total

% time ./sieve_3 1000000
1000000th prime number is 15485863
./sieve_3 1000000  18.97s user 0.37s system 89% cpu 21.669 total

整数のオーバーフローには対処しておりません(苦笑)。 実際のところ、配列の大きさの上限が max_int よりずっと小さいから、多分整数のオーバーフローが問題になるケースは無いだろうとは思うけど (問題が起きるとしたら、n が max_int 付近のときだろうし)。

一応配列の最大値でやってみっか。

% time ./sieve_3 4194302
4194302th prime number is 71378537
./sieve_3 4194302  140.31s user 2.39s system 84% cpu 2:47.90 total

ちゃんと止まった。 処理時間も想定のレベルだし、多分合ってるだろう。 出力してるメッセージが適当 (2th って) なのは仕様です(笑

% [OCaml][雑談] main 関数の書き方

OCaml には明示的なエントリポイント (C の main 関数みたいなの) って無いんだけど、まあ何となくわかりやすいように最初に動くべき関数には main って名前を付けといて、それを呼び出すことで開始になるような構成にしたりする。 ついでに言うと、Ruby でも同じようなことやるクセがついてる。

んで、例えばコード書きながらも、部分的に対話環境で動かしてみたいことってのがわりとある。 そんなときには、ocaml コマンドを起動して #use "source.ml";; てな感じで読み込ませるわけだ。 ところが、そのときに main の呼び出しまでされてしまってウザい思いをすることがある。

それが嫌なので、今までは完成するまで最後の let _ = main () を書かないようにしたり (あるいはコメントアウトしたり) してたんだけど、Sys モジュールをよーく観察したら便利なものがあったので、これからはこれで行こうと思う。

let main () = ...

let _ = if not !Sys.interactive then main ()

Sys.interactive は bool ref 型の値で、対話環境の場合に true が入るようになっている。 なので、それが false のとき (対話環境ではないとき) だけ main () が呼ばれるようにしておけばバッチリという仕組み。

ちなみに Ruby には、

if $0 == __FILE__
   ...
end

っていうイディオムがあるね。 実はあんまり使ったこと無いけど (つーかいつも忘れるから、今わざわざ調べたょ)。


2006-06-19 [長年日記]

% [OCaml] 多相型のメソッドを定義する方法

定期的(?)に OCaml のオブジェクトがマイブームになるのである。 今も、他の場所でちらほら話題が出てるせいで、ちょっとブーム。 てことで知識の整理をして (テディベアに話しかけて) みる。

例えばこんなクラスを作ろうとする。 (ほとんどマニュアルのとおりの例で恐縮だが)

# class int_list (l : int list) = object
    method isEmpty = (l = [])
    method fold f accu = List.fold_left f accu l
  end;;

だがこれは…

Some type variables are unbound in this type:
  class int_list :
    int list ->
    object
      method fold : ('a -> int -> 'a) -> 'a -> 'a
      method isEmpty : bool
    end
The method fold has type ('a -> int -> 'a) -> 'a -> 'a where 'a is unbound

という風に怒られる。 とは言え…

# class ['a] int_list (l : int list) = object   
    method isEmpty = (l = [])                   
    method fold f (accu : 'a) = List.fold_left f accu l
  end;;                                                
class ['a] int_list :
  int list ->
  object
    method fold : ('a -> int -> 'a) -> 'a -> 'a
    method isEmpty : bool
  end

あせってこんなの書いちゃうとハマる。

# let o = new int_list [0;1;2;3];;
val o : '_a int_list = <obj>

# o#fold;;
- : ('_a -> int -> '_a) -> '_a -> '_a = <fun>

# o#fold (+) 0;;
- : int = 6

# o#fold (fun a b -> a ^ (string_of_int b)) "0";;
This expression has type int but is here used with type string

# o#fold;;
- : (int -> int -> int) -> int -> int = <fun>

ね、fold メソッドが単相になっちゃって全然使いものにならない。 ちゃんと fold が多相になるようにするにはこう書く。

# class int_list (l : int list) = object
    method isEmpty = (l = [])
    method fold : 'a. ('a -> int -> 'a) -> 'a -> 'a =
      fun f accu -> List.fold_left f accu l
  end;;
class int_list :
  int list ->
  object
    method fold : ('a -> int -> 'a) -> 'a -> 'a
    method isEmpty : bool
  end

これだと…

# let o = new int_list [0;1;2;3];;
val o : int_list = <obj>
# o#fold;;
- : ('_a -> int -> '_a) -> '_a -> '_a = <fun>
# o#fold (+) 0;;
- : int = 6
# o#fold (fun a b -> a ^ (string_of_int b)) "0";;
- : string = "00123"
# o#fold;;
- : ('_a -> int -> '_a) -> '_a -> '_a = <fun>

めでたし。 o#fold の型が単相に見えるのがハテナ? って感じだけど(苦笑

さて、そうすると今度は多相型のクラスにも多相型のメソッドを定義してみたくなる。 ってことで、こんな風に書いてみよう。

# class ['elm] poly_list (l : 'elm list) = object
    method isEmpty = (l = [])
    method fold : 'a. ('a -> 'elm -> 'a) -> 'a -> 'a =
      fun f accu -> List.fold_left f accu l
  end;;
class ['a] poly_list :
  'a list ->
  object method fold : ('b -> 'a -> 'b) -> 'b -> 'b method isEmpty : bool end
# o#fold;;
- : ('_a -> int -> '_a) -> '_a -> '_a = <fun>

# o#fold (+) 0;;
- : int = 6

# o#fold;;
- : ('_a -> int -> '_a) -> '_a -> '_a = <fun>

# o#fold (fun a b -> a ^ (string_of_int b)) "0";;
- : string = "00123"

# o#fold;;                                       
- : ('_a -> int -> '_a) -> '_a -> '_a = <fun>

おおー偉い。 実はこんなことができるなんて知ったのは最近なので、すでにこういうメソッドはオブジェクトの外に出すスタイルが身についちゃっててあんま嬉しくないんだけどね(苦笑)。 つーか、気合入れて書くならまだしも、適当に書くときにはこんないちいち型指定をちまちま書かなきゃならないのはかったるい。 まあ、憶えておいて損は無いと思うけど、頻繁に使うものでも無いような気はする。 オブジェクト指向が大好きで、何でもオブジェクトを基本にしないと気が済まないような人にはお勧め。

% [OCaml] サブタイピング

も一つオブジェクトネタ。 個人的にはメソッドの型による多相がお気に入りだから、あんまり気にしたことないんだけど、継承関係を使ったサブタイピングも存在する。

# class hoge = object
    method p = "hoge"
  end;;
class hoge : object method p : string end

# class fuga = object
    inherit hoge
    method p = "fuga"
    method q = "aguf"
  end;;
class fuga : object method p : string method q : string end

ここで、fuga は hoge のサブクラス (サブタイプ) である。 そして、こんな関数を書いたとする。

# let f (o : hoge) = o#p;;
val f : hoge -> string = <fun>

これはもちろん↓のように使う。

# let ho = new hoge;;
val ho : hoge = <obj>
# f ho;;
- : string = "hoge"

で、他のオブジェクト指向言語に慣れた人は、同じようにこうするだろう。

# let fu = new fuga;;
val fu : fuga = <obj>
# f fu;;
This expression has type fuga but is here used with type hoge
Only the first object type has a method q

な、なんだって〜!!

実は継承関係を持っていても、暗黙のアップキャストはされないのであった。 上の例で行くと、関数 f を少しいじってやるとこの問題は解決できる。

# let f' o = (o :> hoge)#p;;
val f' : #hoge -> string = <fun>

(o :> hoge) というのは『o を hoge として扱う』ことを示している。 型の表示の #hoge は『o は hoge のサブタイプである (ので hoge として扱える)』という意味。

# let f' (o :> hoge) = o#p;;
Syntax error: ')' expected, the highlighted '(' might be unmatched

こういう風には書けないので注意。 他の書き方としては、

# let f' (o : #hoge) = o#p;;
val f' : #hoge -> string = <fun>

とか、

# let f' o = (o : #hoge)#p;;
val f' : #hoge -> string = <fun>

とか。 ともあれ、これで…

# f' ho;;
- : string = "hoge"

# f' fu;;
- : string = "fuga"

こうなる。

関数 f の型が…

# let f'' o = o#p;;
val f'' : < p : 'a; .. > -> 'a = <fun>

こういうのでは型の制限が甘くてあかん…ってシチュエーションでは必要になる知識だと思う。 わしはそこまで必要なものって書いたことないけど(苦笑


2006-06-20 [長年日記]

% [OCaml] 再帰的なモジュール

いつの間にかこんなのあったのか。知らなかった。 ……いや、もしかすると以前ちらっと見たかもしれないけど、思いっきり忘れ去ってた。 Language extensions のページ の 7.9 ね。 どうやら 3.07 の頃からあるらしい。 随分前じゃん...orz

シグネチャの指定が必須なのが面倒だけど、まあ仕方ないんだろうなあ。

This is an experimental extension of Objective Caml: the class of recursive definitions accepted, as well as its dynamic semantics are not final and subject to change in future releases.

とか書いてあるんで、あんまり積極的に使おうって気にはならないけど、必要になることもあるかも知れないから憶えておこう。

% [独り言] あ〜〜〜〜...orz

printf デバッグができる環境って、何て豊かなんだろう。 あーもーわかんねー!!


2006-06-21 [長年日記]

% [雑談] あれ? セッション内容から OCaml が消えてるよ?

なぜー!!

『オブジェクトと多相バリアントで泥縄プログラミング』とか、そーゆーネタで誰かしゃべってきてくださいよ (別にわしがそういうネタを持ってるわけではありません)。 もしくは『ファンクターでオブジェクト指向プログラミング』とか (重ねて言いますが、そういうネタを持ってるわけではありません)。

% [Mac][Haskell] Hugs がビルドでけん

Fink の Hugs があまりにも古いので (Version: February 2001 って書いてある) 最新のをビルドしようと思ったんだけど、謎のエラーが出てうまく行かない。

% cd hugs98-plus-May2006
% CC=gcc-3.3 ./configure
% make
...(中略)
gcc-3.3 -c -DNDEBUG=1 -g -no-cpp-precomp  subst.c
gcc-3.3 -c -DNDEBUG=1 -g -no-cpp-precomp  type.c
gcc-3.3 -flat_namespace   hugs.o edit.o observe.o builtin.o char.o compiler.o errors.o
 evaluator.o ffi.o goal.o input.o machdep.o machine.o module.o opts.o output.o plugin.o
 script.o static.o storage.o strutil.o subst.o type.o version.o  -lreadline -lncurses
 -lm -ldl  -o hugs 
ld: Undefined symbols:
_mallocBytesRWX
make[1]: *** [hugs] Error 1
make: *** [all] Error 2

こんな感じ。 gcc-4.0 でも同じ状況。

なんでこんなエラーが出るのかがよくわからん。 mallocBytesRWX って関数は builtin.c に定義されてる static 関数で、もちろん builtin.c 内部でしか使われていない。 なんなんだろなーこれ。

DarwinPorts ではこのバージョンの port があるんで、大丈夫だと思ったんだけど……

% [OCaml][アルゴリズム事典] バブルソート

思いっきり三日坊主 (四日か?) だったんで反省して再開。 こんなばかばかしいお題でも (失礼) OCaml で書くと微妙に楽しい。

% cat bubsort.ml
let bubble_sort cmp lst =
   let rec bsort l cont =
      match l with
      | x1::x2::xs ->
           if cmp x1 x2 > 0
           then begin
              let r, c = bsort (x1 :: xs) true in
              (x2 :: r, c)
           end
           else begin
              let r, c = bsort (x2 :: xs) cont in
              (x1 :: r, c)
           end
      | _ :: [] | [] -> (l, cont)
   in
   let rec loop l =
      let ret, cont = bsort l false in
      if cont then loop ret else ret
   in
   loop lst
% ocaml

# #use "bubsort.ml";;                  
val bubble_sort : ('a -> 'a -> int) -> 'a list -> 'a list = <fun>

# bubble_sort compare [2;6;3;1;7;9;0];;
- : int list = [0; 1; 2; 3; 6; 7; 9]

まあなんつーか、バブルソートで効率を追求してもしょうがないから、末尾再帰にこだわるのはやめた。 どのみちスタックの深さが気になるほどの、でかいリストには使えないっしょ。

% [雑談] ワールドカップ中継!大規模 v.s. 小規模 (バグで行こう)

なんか妙に笑えた。

% [OCaml][アルゴリズム事典] 選択ソート

単純なソート特集。 挿入ソートもやろうと思ったんだけど、リストで簡潔にやる方法を思いつかなかったんで、またいずれ。

% cat select.ml
let selection_sort cmp lst =
   let select l =
      match l with
      | x :: xs ->
           List.fold_left begin fun a b ->
              let a', a'' = a in
              if cmp a' b > 0 then (b, a' :: a'') else (a', b :: a'')
           end (x, []) xs
      | [] -> invalid_arg "select"
   in
   let rec loop l =
      let a, ax = select l in
      match ax with
      | [] -> l
      | _ :: _ -> a :: (loop ax)
   in
   loop lst
# #use "select.ml";;                      
val selection_sort : ('a -> 'a -> int) -> 'a list -> 'a list = <fun>

# selection_sort compare [2;6;3;1;7;9;0];;
- : int list = [0; 1; 2; 3; 6; 7; 9]

fold 使ってるところは fold_left でも fold_right でもどっちでも良いと思うけど、どうしても fold_right を使うのは躊躇してしまう(苦笑)。 動きのイメージとしては fold_right の方が合ってるような気もするんだけど。

本日のツッコミ(全3件) [ツッコミを入れる]

% 向井 [しゃべれる人がいなかった、ってことでは>LL Ring かく言う私も打診を受けたのですが、そもそも LL Ring ..]

% jijixi [> perl がない な、なんだっt(ry ほんとだ!!]

% TrackBack [http://jijixi.azito.com/cgi-bin/diary/index.rb?date=200609..]


2006-06-22 [長年日記]

% [C][objc] それなんて Objective-C ?

や、おもしろいんだけど…

  • 「動的」な言語
  • リフレクション
  • 高い柔軟性

どう見ても Objective-C です。 ほんとうにありがとうございました。

Objective-C は C のスーパーセットです。 参考→ダイナミックObjective-C

% [雑談] へなぎなら外してた (続・妄想的日常)

ちょwww

% [OCaml] キミならどう書く 2.0 - ROUND 1 - (L.L.Ring)

このネタ (otsune's SnakeOil) にインスパイアされたので、スレッドを各ノードに見立てて趣味レーションしてみた。

説明しよう。『趣味レーション』とは、いんちきくさいけどどうせ趣味の範囲だから良いんだと割り切って行う似非シミュレーションのことである(大嘘)。

% cat threaded_prime.ml
let channels n = Array.init n (fun _ -> Event.new_channel ())

let proc (i, ch) =
   let rec loop c =
      match i with
      | 0 | 1 -> None
      | _ ->
           if c * c > i then Some i
           else
              if i mod c = 0 then None else loop (c + 1)
   in
   let e = Event.send ch (loop 2) in
   Event.sync e

let create_threads n =
   let chs = channels (n + 1) in
   Array.mapi begin fun i ch ->
      (Thread.create proc (i, ch), ch)
   end chs

let main () =
   let threads = create_threads (int_of_string Sys.argv.(1)) in
   let primes =
      Array.fold_right begin fun a b ->
         let e = Event.receive (snd a) in
         match Event.sync e with
         | None -> b
         | Some i -> i :: b
      end threads []
   in
   List.iter (fun i -> Printf.printf "%d," i) primes;
   print_newline ();
   exit 0

let _ = if not !Sys.interactive then main ()
% ocamlc -thread unix.cma threads.cma threaded_prime.ml -o prime
% ./prime 100
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,

すばらしく無駄。

よーし、今度こそトラックバックしてみっかな。(変な勢いがついています)

% [OCaml][雑談] Obj.magic を自作 (flatline@物工 の日記)

Obj.magic 相当のものを自分で作れることよりも、多相型の要素を持つ例外を定義できることの方がおどろいた。 盲点だったなあ……

% [Ruby][雑談] いや、ちょっと思っただけで、何がどーのって話ではない

まーなんつーの、配列をハッシュテーブルのキーに使うときは気をつけた方が良いっつーか。

% irb
irb(main):001:0> hs = {}
=> {}

irb(main):002:0> a = [1,2]
=> [1, 2]

irb(main):003:0> hs[a] = 3
=> 3

irb(main):004:0> hs[a]
=> 3

irb(main):005:0> hs[[1,2]]
=> 3

irb(main):006:0> a[0] = 0
=> 0

irb(main):007:0> hs[a]
=> nil

irb(main):008:0> hs[[1,2]]
=> nil

irb(main):009:0> hs[[0,2]]
=> nil

3 はどこへ?

% [OCaml][雑談] 多相バリアントを見たら、まず良いか悪いか確かめよう

多相バリアントには二種類ある。良い多相バリアントと悪い多相バリアントだ。(ネタですからね。念の為)

良いか悪いかは、対話環境で型を表示させてみればわかる。

# let f x =
  match x with
  | `i i -> print_int i; print_newline ()
  | `f f -> print_float f; print_newline ()
  | _ -> print_endline "hoge";;
val f : [> `f of float | `i of int ] -> unit = <fun>
# let g y =
  match y with
  | `i i -> print_int i; print_newline ()
  | `f f -> print_float f; print_newline ();;
val g : [< `f of float | `i of int ] -> unit = <fun>

f の引数の型が悪い多相バリアント、g の引数の型が良い多相バリアントだ。 さらに、

# type hoge = [ `Hoge of string | `Fuga of char ];;
type hoge = [ `Fuga of char | `Hoge of string ]

これも良い多相バリアントだ。 これを、

# let h (z : hoge) =                         
  match z with                               
  | `Fuga c -> print_char c; print_newline ()
  | `Hoge s -> print_endline s;;             
val h : hoge -> unit = <fun>

このように使うのは非常に良い。 良い多相バリアントは静的型付け言語としての ML の美学を壊さない。 かつ、同じモジュール内で複数の型に同じバリアントタグを使用できないという、通常のバリアントの欠点を補ってくれる。

だが悪い多相バリアントは危険だ。 これは泥縄プログラミングを助長する悪の道具である。 ここでは悪の使い方として、インチキオーバーロード関数を作ってみよう。

# exception Undefined;;
exception Undefined

# let (+) x y =                          
  match x, y with                        
  | `int i, `int j -> `int (i + j)       
  | `float f, `float g -> `float (f +. g)
  | _, _ -> raise Undefined;;
val ( + ) :
  [> `float of float | `int of int ] ->
  [> `float of float | `int of int ] -> [> `float of float | `int of int ] =
  <fun>

# (`int 1) + (`int 2);;
- : [> `float of float | `int of int ] = `int 3

# (`float 1.) + (`float 2.);;
- : [> `float of float | `int of int ] = `float 3.

# (`string "1") + (`string "2");;
Exception: Undefined.

すでに相当邪悪である。 ところが悪い多相バリアントはさらに邪悪なことを可能にするのだ。

# let (+) x y =                              
  try                                        
    x + y                                    
  with Undefined as e ->                     
    match x, y with                          
    | `string s, `string t -> `string (s ^ t)
    | _, _ -> raise e;;                      
val ( + ) :
  [> `float of float | `int of int | `string of string ] ->
  [> `float of float | `int of int | `string of string ] ->
  [> `float of float | `int of int | `string of string ] = <fun>

# (`string "1") + (`string "2");;
- : [> `float of float | `int of int | `string of string ] = `string "12"

これを邪悪と呼ばずして何と言おう。

諸君、悪い多相バリアントには十分に気をつけなくてはいけない。 多相バリアントの暗黒面に飲み込まれないようにしたまえ。

……ネタですからね。


2006-06-23 [長年日記]

% [雑談] Language Update に OCaml キター!!

まー、どっちにしろわしは、直接見にいくことはできないわけだが(苦笑)、誰かがレポートしてくれることを期待しよう。

それにしても、相変わらず Perl が無いな。

% [OCaml] void* みたいなのが欲しいときには (邪悪なので注意)

邪悪だけど、例えば C に対する Objective-C みたいな動的な仕組みを作ろうと思うと、どうしても『どんな型の値でも、とりあえず無理矢理詰めておける型』が欲しくなる。

んで、無理矢理別の型に変換すること自体は Obj.magic を使えばできるんだけど、それをいかに安全に元の型に戻すかってのはいろいろ工夫のしがいがあると思う。 ってことで、昨日の多相バリアントの延長線になるんだけど、今のところそれなりに形になってる方法を書いてみよう。 もちろん、いろいろ邪悪なので、ご利用の際は計画的に。

# type void_ptr = [ `Void of float | `Int of int ];;
type void_ptr = [ `Int of int | `Void of float ]

# let mk_data value : void_ptr = `Void (Obj.magic value);;
val mk_data : 'a -> void_ptr = <fun>

まず値を入れる器の型を作る。 `Void というのがそれ。 保持する型は別に float じゃなくても、int 以外なら何でも良い (と思う…たぶん)。 詳しい説明は省くけど、int だけは特別な型なので、`Int という特別なタグも用意しておくと、int も一元的に扱える。

次に、この void_ptr 型を保持するオブジェクトを作る。 レコードでもタプルでも良いと思うけど、内部でごにょごにょやる可能性を考えると、オブジェクトの方が良いような気がする。 とにかく、型を表わすバリアントタグとデータを対で持つような何かを作るわけね。

# class ['a,'b] various_data (type_tag:'a) (data:void_ptr) = object
    method get : 'b =                                              
      match type_tag, data with
      | `int,    `Int  n -> `int n
      | `float,  `Void v -> `float ((Obj.magic v) : float)
      | `string, `Void v -> `string ((Obj.magic v) : string)
      | _ -> invalid_arg "various_data#get"
  end;;
class ['a, 'b] various_data :
  'a ->
  void_ptr ->
  object
    constraint 'a = [> `float | `int | `string ]
    constraint 'b = [> `float of float | `int of int | `string of string ]
    method get : 'b
  end

ちなみに、void_ptr に `Float of float とか `String of string とか用意してやれば良いじゃんって話もあるけど、扱う型が増える度に修正する対象が増える (と思うけど、状況によって違うかも) ので間違いの元になりそうな気がする。 まあ、その分 Obj.magic がいらなくなって安全と言えば安全なんだけど。

ともあれ、ここまで来ればあとは、ある型か否かを確かめる関数とバリアントから中身を取り出す関数を用意してやればオッケー。

# let is_int v = 
    match v#get with
    | `int _ -> true
    | _ -> false;;
val is_int : < get : [> `int of 'a ]; .. > -> bool = <fun>

# let is_float v = match v#get with `float _ -> true | _ -> false;;
val is_float : < get : [> `float of 'a ]; .. > -> bool = <fun>

# let is_string v = match v#get with `string _ -> true | _ -> false;;
val is_string : < get : [> `string of 'a ]; .. > -> bool = <fun>

# let take_i v =
    match v#get with
    | `int i -> i
    | _ -> invalid_arg "take_i";;
val take_i : < get : [> `int of 'a ]; .. > -> 'a = <fun>

# let take_f v = match v#get with `float f -> f | _ -> invalid_arg "take_f";;
val take_f : < get : [> `float of 'a ]; .. > -> 'a = <fun>

# let take_s v = match v#get with `string s -> s | _ -> invalid_arg "take_s";;
val take_s : < get : [> `string of 'a ]; .. > -> 'a = <fun>

んで…

# let o1 = new various_data `int (`Int 1);;
val o1 :
  (_[> `float | `int | `string ],
   _[> `float of float | `int of int | `string of string ])
  various_data = <obj>

# let o2 = new various_data `float (mk_data 2.0);;
val o2 :
  (_[> `float | `int | `string ],
   _[> `float of float | `int of int | `string of string ])
  various_data = <obj>

# let o3 = new various_data `string (mk_data "hoge");;
val o3 :
  (_[> `float | `int | `string ],
   _[> `float of float | `int of int | `string of string ])
  various_data = <obj>

# is_int o1;;
- : bool = true
# take_i o1;;
- : int = 1

# is_int o2;;
- : bool = false
# is_float o2;;
- : bool = true
# take_f o2;;
- : float = 2.

# is_string o3;;
- : bool = true
# take_s o3;;
- : string = "hoge"
# take_i o3;;
Exception: Invalid_argument "take_i".

このように使う。 この辺はオブジェクトに定義しちゃっても良いかもしれないけど、そこら辺はお好みで。 various_data をもっとたくさんの型を扱うように拡張したいなら、こいつを継承したクラスを作って、昨日の例外を使った泥縄戦法を使って継ぎ足していけば良い。

# class ['a,'b] various_data_plus type_tag data = object            
    inherit ['a,'b] various_data type_tag data as super             
    method get =                                                    
      try                                                           
        super#get                                                   
      with Invalid_argument _ ->                                    
        match type_tag, data with                                   
        | `int_list, `Void v -> `int_list ((Obj.magic v) : int list)
        | _ -> invalid_arg "various_data_plus#get"                  
  end;;                                                             
class ['a, 'b] various_data_plus :
  'a ->
  void_ptr ->
  object
    constraint 'a = [> `float | `int | `int_list | `string ]
    constraint 'b =
      [> `float of float
       | `int of int
       | `int_list of int list
       | `string of string ]
    method get : 'b
  end

あー泥縄泥縄。

% [OCaml] #パターン (soutaroにっき)

な、なんだってー!!

なんて邪悪な。多相バリアントって邪悪すぎ!! (や、本音は『だから楽しい』んだけど)

でもこれ使うと、拡張するごとに try がネストしていってどんどん効率が悪くなっていく泥縄っぷりが無くなってつまんないなー(ぉぃ


2006-06-24 [長年日記]

% [OCaml][アルゴリズム事典] 挿入ソート

ソート対象がリストで、List.append でリストの最後に要素一つ付け足すみたいなことは極力せずに、あまり長くならないように書く……っていう縛りで書こうとすると結構パズル的で楽しかった。 つーか、merge の辺りがほとんど List.rev みたいなもんなんで、もう少し何とかならんかとも思うんだけど、まあ良いや。

let insertion_sort cmp lst =
   let rec insert ret l =
      match l with
      | [] -> ret
      | x::xs ->
           let rec merge left right =
              match left with
              | [] -> right
              | y::ys -> merge ys (y :: right)
           in
           let rec loop left right =
              match right with
              | [] -> merge left [x]
              | z::zs ->
                   if cmp x z > 0
                   then loop (z :: left) zs
                   else merge left (x :: right)
           in
           let ret' = loop [] ret in
           insert ret' xs
   in
   insert [] lst
# #use "inssort.ml";;
val insertion_sort : ('a -> 'a -> int) -> 'a list -> 'a list = <fun>
# insertion_sort compare [2;6;3;1;7;9;0];;
- : int list = [0; 1; 2; 3; 6; 7; 9]

一応アルゴリズム的には挿入ソートになってるとは思うけど、配列使うのとは全然ノリが違うので変な感じではある。 まあ、それは今までやったソートでもそうだったけど、こいつの場合は特にそんな感じ。

% [OCaml][アルゴリズム事典] 番外編 : パリティチェック

本に載ってるものじゃなくて、ある MCU のアセンブリで書かれた 8bit 値の立ってるビット数が偶数か奇数か調べる方法。

% cat parity.ml
let odd_number_of_bits bits =
   let b = bits land 0xFF in
   let b_swap = ((b land 0b11110000) lsr 4) lor ((b land 0b00001111) lsl 4) in
   let b2 = b_swap lxor b in
   let b3 = (b2 lsr 2) lxor b2 in
   if (b3 + 1) land 0b10 <> 0 then true else false
# #use "parity.ml";;
val odd_number_of_bits : int -> bool = <fun>
# odd_number_of_bits 0b1110;;
- : bool = true
# odd_number_of_bits 0b11110;;
- : bool = false
# odd_number_of_bits 0b10110;;
- : bool = true

はっきり言って、なんでこれで判定できるのかさっぱりわからんのだけど (苦笑)、一応何をやってるか解説すると……

  • 元の値 (b) とそれのニブル交換 (上 4bit と下 4bit の入れ替え) したもの (b_swap) の排他的論理和 (xor) を取る (b2)。
  • b2 と、 b2 を右に 2bit シフトしたものの xor を取る (b3)。
  • b3 に 1 を足したものの 1 番ビット (2bit 目) が立っていれば奇数。

OCaml のビット演算は見づらいので、Ruby でも書いておく。

def odd_number_of_bits bits
   b = bits & 0xFF
   b_swap = ((b & 0b11110000) >> 4) | ((b & 0b00001111) << 4)
   b2 = b_swap ^ b
   b3 = (b2 >> 2) ^ b2
   if (b3 + 1) & 0b10 != 0 then true else false end
end

いやー、ビット演算って奥が深い (って言うのか、これ?)。 そう言えば、reddit かどっか経由で見つけたこういうページもあったなー。

本日のツッコミ(全1件) [ツッコミを入れる]

% TrackBack [http://jijixi.azito.com/cgi-bin/diary/index.rb?date=200606..]


2006-06-25 [長年日記]

% [アルゴリズム事典] 番外編:続パリティチェック

昨日の例はアセンブリ言語に特化した書き方をしたものを、そのまま持ってきたものだったのでちょっと意味がわかりづらかったと思うけど、なんとなくそうなんだろう…と思ってた考えで整理してみたらわりとすっきりしたのでフォローしておく。

まずは整理したコード (Ruby で書く)。

def odd_number_of_bits bits
   b76,b54,b32,b10 = (bits & 0b11000000) >> 6,
                     (bits & 0b00110000) >> 4,
                     (bits & 0b00001100) >> 2,
                      bits & 0b00000011
   b = b76 ^ b54 ^ b32 ^ b10
   if (b + 1) & 0b10 != 0 then true else false end
end

要するに 2bit ずつに区切って、それぞれの排他的論理和を取っている。 このとき、対象は 4 つなので、各 bit が偶数個立っているとき結果の各 bit は 0 になる。 その結果… b の値が 0b00 か 0b11 のとき、立っているビット数が偶数だということになる。 逆に言うと 0b10 か 0b01 のときには奇数だ。

ここまで来ればわかると思うけど、2bit だから取り得る値はこの 4 つだけで、これらそれぞれに 0b1 を足してみると……

0b00 + 0b01 = 0b001
0b11 + 0b01 = 0b100
0b10 + 0b01 = 0b011
0b01 + 0b01 = 0b010
                 ^

このように見事に 2bit 目で偶奇の判断が付くようになるのであった。

わかってみれば「なるほどー」で済む話だけど、なかなか自分じゃ思いつかないよなー。 ……あれ? 思いつかない…ですよね? わしの頭が特別ヌルいわけじゃないですよね、ね?

% [雑談] まわりくどい人キタ!

((Common Lisp) (Scheme) :Part 15) (2ch) イカすスレタイに賞賛の声。

なんか妙に笑えた。

% [本日のリンク元] Google 検索 (リアルピノコ)

なんだ、何のブームなんだ? 謎すぎる。


2006-06-27 [長年日記]

% [雑談] 腰が痛い

おととい久しぶりに力仕事をしたんで腰が……

ところどころ筋肉痛も残ってるし、色んな意味でダメすぎる自分を実感する今日この頃...orz

% [雑談] はー、ブラジル強いなー

ガーナももう少し良い勝負すると思ってたんだけど……


2006-06-29 [長年日記]

% [雑談] あー……何もする気が起きん

早く明日になんないかなー。明日っつーか明後日の 0 時にー。

……って感じで相変わらず決勝トーナメントが始まってからちゃんと見始めるわし。


2006-06-30 [長年日記]

% [雑談] ドイツ vs アルゼンチンまで、あと 30 分

ワクワク、テカテカ。 今大会屈指の好カードっすよねー。 こっちのブロックは、この試合の勝者が決勝に行くでしょう。 今回イタリアはいまいちパッとしないし。

もう一方のブロックは十中八九ブラジルが勝ち上がると思うけど、フランスも調子を上げてきてるから楽しみだ。 今日明日は寝られへん。

つーかさー、カーンが試合に出ないのがつまんねーよー。カムバーックモミアゲ。

% [雑談] 延長戦〜

燃える。

% [雑談] ドイツ勝った……

アルゼンチンは選手交代が失敗だったなあ。

% [雑談] お召し上がりでよろしかったでしょうか (どーんとやってみよう)

や、言われてることはいちいちごもっともなんだけど、その件についてはどうでも良く……

「そりゃ食うさ、どこで食うかは知らんけどな!」

ってセリフが妙にツボに入って笑い転げてしまったことを、ここに記す次第。


トップ 最新 追記

日記ってのは本来、自分で読み返すためにあるもんだよなあ……
もしくは有名人になったら死後に本になったりとかか?

RSS はこちら

jijixi at azito.com