setitimer on leopard

POSIX系OSでプロファイラなどを作る際にsetitimer関数を利用します。以下のようにするとタイマを設定することが出来ます。

struct itimer value, ovalue;

value.it_interval.tv_sec  = 0;
value.it_interval.tv_usec = 1;
value.it_value.tv_sec  = 0;
value.it_value.tv_usec = 1;
if (setitimer(ITIMER_PROF, &value, &ovalue) != 0)
  { error_code; }

ここで設定した秒数ごとにSIGPROFシグナルが投げられますので、プロファイラをsigactionでSIGPROFに設定しておきます。

struct sigaction old;
struct sigaction new;

memset(&new, 0, sizeof(new));
new.sa_handler = プロファイラ関数;
if (sigaction(SIGPROF, &new, &old) != 0)
  { error_code; }

ところでプロファイラを起動する間隔ですが、これは先ほど設定したSIGPROFを投げるインターバルに依存しますから、上の例のように気軽に1マイクロ秒とかには出来ないわけです。基本的には。でもLinuxなどでは適当な値に丸められるので、上記のようなコードが放置されるケースが見受けられます。

さて先頃リリースされたLeopardにコレといった不具合も出てないようだったので喜んでインストールした私です。そして色々とソフト入れてて上の問題にぶつかったわけです(SWI-Prologでしたが)。なんとLeopardは1マイクロ秒でもタイマが起動しちゃようです、ビビりました。そんな間隔で起動されたら他のプロセスにちっともスイッチされなくなります。そういうわけなので統計クロックから適切な値を設定してやるようにしましょう。

value.it_interval.tv_usec = 1000000/(int)sysconf(_SC_CLK_TCK);

Prolog (6)

なんかunfoldの定義を少し間違って記憶してたように思います。Haskellでリスト用の定義を見るとこんな感じ。

unfold p f g x = 
  if p x 
     then [] 
     else f x : unfold p f g (g x)

Prologでは前回示したようにunfoldの外のゴールでバックトラック制御を行えますから、終了判定は要らないですね。アレはアレで使い道はあるのでunfold2とかにリネームしておいて、リスト用unfoldlを正しく書くとこんな感じですかね？

% unfoldl/5
unfoldl(Fn1, _, X, L, L1) :-
  G =.. [Fn1, X, Y],
  call(G),
  append(L, Y, L1).
unfoldl(Fn1, Fn2, X, L, L2) :-
  unfoldl(Fn1, Fn2, X, L, L1),
  G =.. [Fn2, X, Y],
  call(G),
  unfoldl(Fn1, Fn2, Y, L1, L2).

% make_list/2
make_list(X, [X]).

?- unfoldl(make_list, inc, 1, [], L), length(L, 100), foldl(plus, 0, L, Sum).
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
Sum = 5050

ただHaskellだと型システムのチェックが働く部分や、カリー化された関数が書き易い部分が組み合わさって強力なfold/unfoldですが、Prologだとその辺りでメリットが無いので正直なところ使い勝手は微妙です。

ところで最近都内でProlog勉強会をやっています。ご興味をお持ちの方が居られましたら是非ご一報を。隔週で長期的にやっております。
次回開催概要
場所: 中目黒GTタワー
日時: 11/10(Sat) 14:00-
内容: Prologへの入門 4-5章
連絡: hiro.kosh@gmail.com

Prolog (5)

前回に引き続きリスト系のユーティリティ述語の紹介です。

fold(l/r)を定義したら当然のことですがunfoldが定義したくなりますね？幸いにもPrologはバックトラックがありますから、特に遅延評価のための仕組みを用意せずとも、Haskellのようにunfoldを書くことが出来ます。しかしその前にもっと細かいユーティリティを定義しておきます。

まずはリストの最後の要素を取得するlast/2です。

% last/2
last([X], X).
last([_|R], X) :- last(R, X).

?- last([1, 2, 3], X).
X = 3

続いてリストの最後以外の部分を取得するunlast/2です。

% unlast/2
unlast(L, R) :-
  last(L, Y),
  append(R, [Y], L).

?- unlast([1, 2, 3], L).
L = [1, 2]

個人的にはこの述語なんか簡単で、如何にも宣言的な書き方かなぁと思っています。二つ目のゴールで最後の要素を後ろに付けたリストが元のリストだと宣言してるわけですね。

さてリストのN番目の要素を取得するnth/3はこんな感じ。

% nth/3
nth(1, [X|_], X).
nth(N, [_|R], X) :- N > 1, N1 is N - 1, nth(N1, R, X).

?- nth([1, 2, 3], 2, X).
X = 2

ところで引数の並びをどうするかというのは悩みどころです。特に高階述語を書く場合は、与える引数の位置が重要ですからね。そこで自分の中でルールを決めておくという手もあるのですが、順番を変えたい場合はチェインというのを定義してやります。

% last1/2
last1(X, L) :- last(L, X).

上のlast1/2ではlastを呼び出すことしかしません。ただし引数を並び替えています。このようにエイリアスのような役目をする述語を(慣用的に)チェインと呼びます。

それではunfold/4を定義してみましょう。

% unfold/4
unfold(Fn, X, L, L1) :-
  last(L, Y),
  G =.. [Fn, X, Y, Y1],
  call(G),
  append(L, [Y1], L1).
unfold(Fn, X, L, L2) :-
  last(L, Y),
  unfold(Fn, X, L, L1),
  unfold(Fn, Y, L1, L2).

?- nth(10, L, X), unfold(plus, 0, [1], L).
L = [1, 1, 2, 3, 5, 8, 13, 21, 34|...],
X = 55

出来ました。ちなみにnth/3を使っている理由はもうすでにお気づきですね？それではunfold/4単体でフィボナッチ数を計算してみましょう。

?- unfold(plus, 0, [1], L).
L = [1, 1] ;
L = [1, 1, 2] ;
L = [1, 1, 2, 3] ;
L = [1, 1, 2, 3, 5] ;
...

ご覧の様に、別の解を要求する度にリストが伸びて計算を行っていきます。上の例ではnth/3でリストの幾つ目の要素が欲しいのかを条件として与えていますから、それを満たすリスト長になるまでバックトラックを起こして次の値を計算しているわけです。