2007.12.15

[HOP]Parsingの章終了

ようやくParsingの章を終了。手を動かす気力が無いので読んだだけです。

8.8 Backtracking Parsers
Perlで自力で継続をしながら、バックトラックをする話。

ソースはこんな感じで
sub lookfor {
 my $wanted = shift;
 my $value = shift || sub { $_[0] };
 my $u = shift;
 $wanted = [$wanted] unless ref $wanted;

 my $parser = parser {
  my ($input, $continuation) = @_;
  return unless defined $input;

  my $next = head($input);
  for my $i (0 .. $#$wanted) {
   next unless defined $wanted->[$i];
   return unless $wanted->[$i] eq $next->[$i];
  }
  my $wanted_value = $value->($next, $u);

  # Try continuation
  if (my ($v) = $continuation->(tail($input))) {
   return $wanted_value;
  } else {
   return;
  }
 };

 $N{$parser} = "[@$wanted]";
 return $parser;
}

SICPの継続の部分に構造は近い。引数に処理すべきリストと継続を渡し、成功/失敗によって自力で継続を呼び出すクロージャを返している。

同様にstreamを使ったparsingも簡単に説明。パースの選択肢がある時に、どちらかを選んで再帰していくのではなく、すべての選択肢を同時に計算していく。ここでStreamを使う。実用性はともかく発想は面白い。

8.9 Overloading
最後は、演算子のオーバーロードを使用してDSLっぽくする話。

この本で、ここまで書いてきたパーサーのソースがこれ。

$factor   = alternate(lookfor('INT'),
       T(
             concatenate(lookfor(['OP', '(']),
                  $Expression,
                  lookfor(['OP', ')'])),
        sub {$_[1]})
       );

ちなみにlookforは、引数をパースするだけのクロージャを返し、concatenateは引数のクロージャを連結したクロージャを返す。Tは、クロージャと手続きを引数にして、パースに成功したときにある手続きを読んでから値を返すクロージャを返す。最後にalternateは、複数のクロージャを引数に選択的に実行していくクロージャを返します。もうわけわかんない。

BNFからはほど遠くなっているので、Perlのオーバーロードを使用することで、こんな風に書けます。

$factor = lookfor('INT')
    | lookfor(['OP', '(']) - $Expression, lookfor(['OP', ')']
        >> sub {$_[1]})
    ;

これで確かに読みやすくなる。

こういうのに興味がある人はHigher-Order Perlお勧めですよ。

残りあと一章!

| | Comments (0) | TrackBack (0)

2007.11.24

[HOP]パーサを作ろう その2

なんとかターゲット決めうちで、ここまでパース出来るようになった。

>>>
('expression',)
('(', 'expression', ')')
('(', 'INT', '*', 'expression', ')')
('(', 'INT', '*', '(', 'expression', ')', ')')
('(', 'INT', '*', '(', 'INT', '+', 'expression', ')', ')')
('(', 'INT', '*', '(', 'INT', '+', 'INT', ')', ')')
>>>

ソースはここ

深さ優先で検索する方法が分かった。よく考えると、このパーサーのアルゴリズムで答えが無かったら無限ループするのって、幅優先も深さ優先も同じじゃね?と思ったら、やっぱりそうらしい。ここまで自分の手で動かして、ようやく@alohakun発言の意味が分かる。俺、コンピュータサイエンス弱ぇー。
http://twitter.com/alohakun/statuses/431771522
バックの絵きんもー!

yaccとか、lexとか、bisonとかいうのも、Wizard形式のプログラミングと一緒で、もともとそういうのが無くても出来る人が楽するためにあるんだよな。一歩ずつ行こう。

そんなことを思っていたら、本にコーヒーをこぼしてしまった。もう、誰にも貸せない本になった・・・

8.2 Parsing in general終了。
ようやく、再帰下降のパーサーに入る。

| | Comments (6) | TrackBack (0)

2007.11.07

再帰からループへ

Higher-order Perlから

Chapter4は延々とイテレータについて。
自作イテレータをちょこちょこと改造していく。
イテレータを使った、mapとgrepの実装は面白い。無限ストリームにも使えそう。

Chapter5は、再帰からループの変換について。
再帰で美しく書かれているアルゴリズムを、自作スタックとGOTOでループに変えていく。それってどうよ?と思うんだが、Perlの場合は再帰よりもループの方が効率的らしい。

面白いと思ったのが2つ

・他の書籍に突っ込む
Mastering Algorithms With Perlに出てくる再帰を書き直す話。

最初:http://perl.codefetch.com/example/ht/Examples/Chap5/powerset-0?qy=%25s
最後:http://perl.codefetch.com/example/ht/Examples/Chap5/powerset-4?qy=null

再帰が無くなっただけでなく、プロタイプがすっきしりたり、for(;;)の構文が無くなってローカル変数が減ったりしている。ムックとか雑誌ならありそうだけど、普通の技術書でこういう他の書籍に出典付きで突っ込むって珍しと思った。

・再帰からループへ

sub fib {
 my $n = shift;
 if ($n < 2) { return $n }
 fib($n-2) + fib($n-1);
}

のような綺麗だけど効率の悪い再帰も、この本にかかるとこんな感じ。

sub fib {
 my $n = shift;
 my ($s1, $return);
 my $BRANCH = 0;
 my @STACK;
 while (1) {
  if ($n < 2) {
   $return = $n;
  } else {
   if ($BRANCH == 0) {
    push (@STACK, [ 1, 0, $n ]), $n -= 1 while $n >= 2;
    $return = $n;
   } elsif ($BRANCH == 1) {
    push @STACK, [ 2, $return, $n ];
    $n -= 2;
    $BRANCH = 0;
    next;
   } elsif ($BRANCH == 2) {
    $return += $s1;
   }
  }

  return $return unless @STACK;
  ($BRANCH, $s1, $n) = @{pop @STACK};
 }
}

10ページ近く書けて、ゆっくりと再帰を剥がして最適化していく。わかりにくくなったよ。ママン。
興味がある人は、ここのfib-0からfib-12まで順に見てみよう。
http://hop.perl.plover.com/Examples/Chap5/

250ページを読んでまだまだ絶賛ベタ褒め中。

| | Comments (0) | TrackBack (0)

2007.11.05

Iteratorで順列を作る

Higher-order Perlから

Chap4はiteratorの話。一番身近なiteratorはファイルハンドル、という説明は分かりやすい。

タイトルの通り、Iteratorを使って順列を作る話。('A' 'B' 'C')のリストからこんな出力が欲しい。
[A B C]
[A C B]
[B A C]
[B C A]
[C A B]
[C B A]

普通に再帰を使って順列を作ると、CPUとメモリを大きく消費するし、順列に対して一つずつ処理するのがやりにくい。(ファイルハンドルでも、ファイルを全部読み込みたいときと、1行ずつ or 一文字ずつ処理したいときあるよね)

そこでIteratorを使う。
面白いのが、まずこんな感じのカウンターを作ります。(名前ありそうだけどね)

0000
0010
0100
0110
0200
0210
1000
1010
1100
1110
1200
1210
2000
2010
:
2210
3000
3010

3200
3210

最下位の桁は0固定として、その次から下位から順に、2進、3進、4進のカウンターになっています。4桁だとちょうど24個で、順列の数になっています。0000から始まって、3210が最大です。3桁だと、000から210までなので、これも3個の順列で6個の値を取ります。

戦略としては、iteratorを使ってこのカウンターを順次インクリメントする→カウンターの値から対応するリストを取り出す、になります。順列を一つずつ作る部分と、順列からリストを作る部分が分離しているのが美しい。

目的のリストのつくりかたを簡単に説明します。カウンターの最上位に対応する要素を抜き出します、抜き出されて要素が一つ減ったリストと、カウンターの最上位を取り除いた物で同じように処理します。簡単な再帰なのですが、文章だけではわかりにくいと思います。

もとのリストが、(A B C D)カウンターの値が2010の時、カウンターの最上位が2なので、Cを取り出します。

元のリスト カウンター 新しいリスト
(A B C D) 2010     ()
(A B D)   010    (C)    ← Cを抜き出し、カウンターの最上位を取り除く。

次は、カウンターの最上位が0なので、(A B D)の0番目にあたるAを取り除きます。

(B D)    10   (C A)    ← Aを抜き出し、カウンターの最上位を取り除く。

次は、カウンターの最上位が1なので、(B D)の1番目にあたるDを取り除きます。

(B)     0  (C A D)    ← Dを抜き出し、カウンターの最上位を取り除く。

最後、カウンターの最上位が0なので、(B)の0番目にあたるBを取り除きます。

()         (C A D B)    ← Bを抜き出し、カウンターの最上位を取り除く。

これで、(A B C D)と2010から、(C A D B)が取り出せます。

使い方はこんな感じです。
my $it = permute('A' .. 'D'); #iteratorを返す

while (my @p = $it->()) { # iteratorが空のリストを返すまで順次インクリメント
 print "@p\n";
}

package Iterator_Utils;が上手く使えず、自力で書いたのは秘密。

| | Comments (0) | TrackBack (0)

2007.11.04

Cが最速なんてもう言わない

例によってHigher-order Perlから

昨日までは、同じ処理を同じアルゴリズムで書いたらC/C++が一番早いに決まっているという信念があったのですが、この本を読んで考えが変わりました。2007年11月3日はそんな記念日。

相変わらずメモ化の話なんですが、

・フィボナッチ書けたよ → 遅くね?
・メモ化したよ → 毎回メモ化の仕組み作るの面倒じゃね?
・closureがあるよ → 引数が一つの時しか使えなくね?
・joinでつなぐよ → f("x,", "y")と、f("x", ",y")でバグるよ
・正規表現でエスケープするよ → 遅くね?
・key generatorを引数で渡して、if文で切り替えたらどうよ → if文無駄じゃね?
・eval使うよ ← 今ここ

という議論を経て、evalを使う話。上の議論は全部Perlのソース付きで説明されています。
で、問題のコードがこれ。

sub memoize {
 my ($func, $keygen) = @_;
 $keygen ||= q{join ',', @_};

 my %cache;
 my $newcode = q{
  sub { my $key = do { KEYGEN };
    $cache{$key} = $func->(@_) unless exists $cache{$key};
     return $cache{$key};
    }
 };
 $newcode =~ s/KEYGEN/$keygen/g;
 return eval $newcode;
}
 
引用のレベルだと思うけど、念のため。ソースはここから取得可能、ソースのライセンスはここです。

evalを使う前ののソースが、my $key = $keygen ? $keygen->(_@) : join ',' , @_; と、引数$keygenがあるかないかで、joinを使うか、引数で与えられた$keygen関数を使うかを切り分けていたのが、上のやり方で三項演算子が一つ消えている。つまり、自分で最適化されたソースを作り出し(KEYGEN部分の置換)、evalしてそのまま利用することで条件分岐を減らしているわけだ。これはC言語では難しい。条件分岐をnopでつぶすとか、DLL作り直して再ロードとかできなくはないが、明らかにCの範囲を超えている。これCommon Lispでできたらすごい事になる事に気がついた。

状況としては、良く呼ばれてボトルネックになっている関数があるとする。その関数が、起動時のオプションや実行時の状態によって、ちょっとずつ動きを変える必要があるとする。Cで書くと、どうしても動きを変えるためにif文が必要になる。Common Lispだと動きを変えたS式を作り出し、最適化を書けてコンパイルして使い続けることができる。Lispについてのよくある誤解と、その中にあるちょっとした真実にあるように、もともとCommon Lispのコンパイル能力は高いらしいので、「いろいろ変わる条件」が複雑になればなるほど、Common Lispの方が速い可能性が出てくる。Cでも、考えられる組み合わせにはそれぞれ別の関数を作るってやり方もあるけど「100回以上呼ばれたら、自動的に最適化されたS式を作り出して、再コンパイル」みたいな芸当はCにはできない。

結論:Lispすげー!

メモ化の話としては、内容的にも、ページ数的にも、ここで折り返し
後は、特殊な状況下での考察がソース付きで続く。Higher-Orderはあまり関係ない。

キーワードだけ列挙
・f(A=>32, C=>99)と、A(C=>99, A=>32)を同じに扱うべきかどうか
・デフォルト引数的な動きをする関数をどう扱うか。
・オブジェクトのメソッドをメモ化するときの注意点
・オブジェクト(のアドレス)をキーにしてはいけない理由
・メモ化の結果をDiskに残して、後で再利用する
・時刻を取得する関数をメモ化が有効な時
・sort関数でのメモ化
・Orcish Maneuver
・Semipredicate problem
・"0e0"問題
・100回呼ばれたら自動的にメモ化する

100ページを読んでまだまだ絶賛ベタ褒め中。

| | Comments (2) | TrackBack (0)

2007.11.03

中はLISPです

Higher-Order Perl、chap3から。

メモ化の話
少し前に流行った、fib関数をメモ化して速度を上げる話。
普通にいろんな実装方法を説明した後、どうやって一般化するかでMemoize.pmの紹介がある。

Perlだと メモ化を個人で実装する必要はなくて、
use Memoize;
memoize 'fib';
で関数fibをメモ化できる。この本では、紹介だけでなくMemoize.pmの動きをちゃんと説明している。Memoize.pmはPerlの内部テーブルを書き換える話をした後に、closureが来る。

どうみても、Lispです。
Padというのは、ローカル変数のbindingを行うデータ構造で、StubはPerlのjargonではCV(code,value)と呼ばれる。carが手続き(code)をさして、cdrがpad(ローカル変数のbinding)を指すと説明が入る。Perlでclosureが作られるとその数だけCVが作られる。普通にbindとか、lexical closureとか単語が飛び出し、ここだけ読んだらPerlの本とは思えない。SICP実践編って感じだ。銀行口座よりも、メモ化で高速にする方が面白い。

気がついたんだけど、Pythonとかanonymousなんちゃらの概念がある言語って同じ仕組みになっている気がする。ということは、gccもPerlもRubyもPythonも中はLispでできているんじゃね?Lispはあまり普及していないっていうけど、見えないところにLispの根ってのががっちり蔓延っていて、僕たちは毎日Lispを無意識に使っているんですよ。

あとは、将来言語設計に進みたい人はLispってのが避けて通れないと思った。

| | Comments (1) | TrackBack (0)

2007.11.02

電卓

Higher-Order Perl、から。

Perlで逆ポーランドの電卓を作ろうという話題

#!/bin/perl
use strict;

my @stack;
my $actions = {
    '+' => sub { push @stack, pop(@stack) + pop(@stack) },
    '*' => sub { push @stack, pop(@stack) * pop(@stack) },
    '-' => sub { my $s = pop(@stack); push @stack, pop(@stack) - $s },
    '/' => sub { my $s = pop(@stack); push @stack, pop(@stack) / $s },
    'NUMBER' => sub {push @stack, $_[0] },
    '_DEFAULT_' => sub { die "Unrecognized token '$_[0]'; aborting" }
};

my $result = evaluate($ARGV[0], $actions);
print "Result: $result\n";

sub evaluate {
    my ($expr, $actions) = @_;
    my @tokens = split /\s+/, $expr;
    
    for my $token (@tokens) {
        my $type;
        if ($token =~ /^\d+$/) {
            $type = 'NUMBER';
        }

        my $action = $actions->{$type} || $actions->{$token} || $actions->{_DEFAULT_};

        $action->($token, $type, $actions);
    }
    return pop(@stack);
}

ざっとこんな感じ。
my $action = $actions->{$type} || $actions->{$token} || $actions->{_DEFAULT_};
この辺りがLLぽい。一つめのハッシュが駄目なら、次のハッシュ。

class calclator {
public:
  int calc(std::vector tokens) {
    std::vector::iterator it;
    for(it=tokens.begin();it!=tokens.end();it++) {
      if(it->type() == NUMBER) {
        st.push(*it);
      } else if(it->type() == OPERATOR) {
        token op2 = st.top(); st.pop();
        token op1 = st.top(); st.pop();
        st.push((*it)(op1, op2));
      } else {
        std::cout << "error" << std::endl;
      }
    }
    token result = st.top();
    st.pop();
    return result.value();
  }
  
private:
  std::stack st;
};

一応C++でもそれっぽくできて動いたけど、なんかダサイ。
スタックに、文字列でも数字でも入れられるようにしようとしたのが失敗。逆ポーランド記法ではスタックに入るのは数字のみと気がついたのは、完成間近。それに気がついたとたんやる気がなくなった。なんでもほいほいpushできるLLすげー。普通の会社でC++で開発していて、やべー設計間違ってるって時、どうしてるんだろうな。

'+'のアクションで、std::plusが使えそうだったけど上手く行かなかった。今日はstd::stackが使えるようになったので良しとしよう。一日一歩。

Perl、入出力込みで数時間。(丸写しだけどね)
C++、3日がかりで、入力はソースに直書き。

むう、そろそろC++挫折しそうになってきた。

| | Comments (0) | TrackBack (0)

2007.10.31

Higher-Order Perlは面白い!

Higher-Order Perl、Chapter2に入りました。

VERBOSITY 8
CHDIR /usr/local/app

のように文字列が並んでいる設定ファイルを読み込む話。一行ずつ読み込んで、splitしてまでは同じ。
普通にif elsifを並べるのではなく、

$dispatch_table =
{ CHDIR => \&change_dir,
  LOG_FILE => \&open_log_file,
  VERBOSITY => \&set_verbosity
}
というような、コマンドと飛び先のテーブルを作ると良いという話。関数のポインター並べて、テーブルジャンプは組み込みプログラマなら良くやる処理。割り込みベクタとか、テーブルジャンプそのものだし。

同じ事をPerlでやると俄然面白くなる。テーブルは変数なので、DEFINEが出てきたら以降の文字列を置き換える、といった処理も追加可能。新しい命令を作る命令なんかを定義しても、テーブルに追加するだけ。これはすごい。テーブルでジャンプと、ジャンプ先の書き換えくらいは思いつくが、テーブルを拡張するという発想は無かった。Cプログラマから見て凄いと思うのが、設定ファイルの中に処理系が理解できるコードを書くと、文字列として受け取ってそのままeval出来ること。もちろん、加工してevalもできる。設定ファイルが簡易処理系になるんだ。こうやって、でぃえすえるって奴ができるのか。

SICPでも同じようなことやっているんだけど、SICPはどうしても処理系引きこもりになりがちだったのに対し、この本は操作の対象がディレクトリ、HTML、設定ファイルと実践的なのが良い。SICPで学んだ事をどう使うかって事が書いてある。

最初の50ページを読んで、絶賛ベタ褒め中。

| | Comments (2) | TrackBack (0)

2007.09.25

Larryが決めた

とりあえず「初めてのPerl」を最後まで読んだ。いろんな所で「Larryがそう決めた」と出てきて面白い。

「続・初めてのPerl」に入ろう。

プログラミング言語Perlから。

> これまでに見た最もお気に入りのアニメは「少女革命ウテナ」で
> 今見ている最もお気に入りのアニメは「るろうに剣心」である。

Larry Wallが、るろうに剣心好きと書いてあって一生Perl使おうと思った。

| | Comments (0) | TrackBack (0)

2007.09.20

Perlの勉強

Perlの勉強を始める。

何回か読んだ入門Perlは内容が古いらしい。どうりで、他でみるコードは雰囲気が違うはずだ。

本棚を眺めて、とりあえず「初めてのPerl」とタイトルが付くオライリー本が4冊もある。
初めてのPerl続・初めてのPerl 改訂版の順で読んでいけばよさそう。

古い初めてのPerlとfor win32、Effective Perl、プログラミングPerlの第二版も必要ないか。2000年以前に書かれた本は実家に送ろう。

| | Comments (0) | TrackBack (0)

その他のカテゴリー

C++ | FPGA | FreeBSD | Lisp | Perl | pmeteo | Python | Systemc | Verilog | wifehack | お勉強 | プライベート | モバイル | 読書