2009年12月28日月曜日

継続でフィボナッチ

継続と言うか、call/ccに関してはいつかどこかで纏めて書こうと思ってるんですけどね。
色々継続に関して言うと文句があって(笑)、どっかでキッチリとトドメをさしておきたい(笑)。

それはともかく。
上記リンクに面白いコードが紹介されていました。

def fib
a, b = callcc {|$c| [0,1] }
puts b
$c.call b, a + b if b < 100
end

fib


上の例が解れば、やってることは同じなので難しくはないと思います。

難しいって(爆)。
Schemeでだいぶ継続慣れした、とか思ってたんですが、いやなかなか。解読するのに時間がかかりました。

一応、フィボナッチ数列の復習してみましょうか。定義はWikipediaに書いてありますがね。
Schemeで定義通りにバカ正直に実装すると次のようになります。

(define (fib n)
(cond ((zero? n)
0)
((= n 1)
1)
(else
(+ (fib (- n 2)) (fib (- n 1))))))

Rubyだと次のようになるのかな?まあ、Rubyとして適切な書き方かどうかは分かりませんが(注1)。

def fib (n)
if n == 0
0
elsif n == 1
1
else
fib(n - 2) + fib(n - 1)
end
end

構造的には上のようになりますよね。定義のまんま、って事で。
ただ、この構造は再帰ですけど、二つ再帰で呼び出される手続き(あるいはメソッド)が定義されていて、その計算結果を保持しながらなおかつ加算を行うんで無駄が多いと言えば多いです。
Lispをやってる人は、大抵のLisp処理系には末尾再帰最適化が実装されている筈だ、と信じて(注2)、次のように書く事を好みます。

(define (fib n)
;; ローカル手続きloopを定義
(define (loop m a b)
(if (zero? m)
a
(loop (- m 1) b (+ a b))))
;; loopに初期引数を与えて呼び出す
(loop n 0 1))

Rubyは末尾再帰最適化は行わない筈ですが、末尾再帰自体は次のように書けるでしょう。

def fib (n)
# ローカルメソッドloopを定義
def loop (m, a, b)
if m == 0
a
else
loop(m - 1, b, a + b)
end
end
# loopに初期引数を与えて呼び出す
loop(n, 0, 1)
end

ご覧の通り、再帰部分で呼び出した手続き(あるいはメソッド)には、手続き(あるいはメソッド)の外で余計な事(例えば足したり引いたり)をしていません。こう言うスタイルの再帰を末尾再帰(tail recursive)と呼んで、特にSchemerは重宝しています。数学的にはgotoでのジャンプ構文と同じそうです。
まあ、実際末尾再帰に煩いのはSchemerくらいなんですけどね(笑)。Cのプログラマは再帰は知ってるけど、末尾再帰って言い方は知らないケースが多いようです。何せ教科書にはほぼ書いてない(注3)。

いずれにしても、この2種類の書き方がフィボナッチ数列の書き方の定番です。

が、「継続でフィボナッチ」と言うのはなかなか目にしないネタなんでビックリですね(笑)。

継続の説明自体は元リンクを見てもらうとして。
call/ccってのはRubyで存在する、ってのは聞いた事あるんですが(元々Schemeの機能)。それを使ったコード自体が初見です。大体、今調べてみたんですが、たのしいRuby 第2版 Rubyではじめる気軽なプログラミングには載ってない(爆)。多分ほとんどのRubyistに対しても謎の機能?
もう一回コード見てみますか。


def fib
a, b = callcc {|$c| [0,1] }
puts b
$c.call b, a + b if b < 100
end

fib

う~ん。ここままじゃちょっと(Schemeにある程度慣れてる僕には)分かり辛いですねえ。
一旦Schemeに直してみたいと思います。

とは思ったけど、これが結構大変だったんだ(爆)。

まず、Rubyの場合、$記号を付けて宣言された変数はグローバル変数、となる模様です。上のコード例で言うと$cってのがグローバル変数ですね。
つまり、Schemeにはそう言う便利な記法は存在しないんで、明示的にグローバル変数を宣言する必要があります。


(define *c* #f)


グローバル変数*c*の中身は、まあ何でも良いんで、取りあえず#fを束縛しておきます。
このグローバル変数に「継続」と言われるものを束縛するんですね。

次に、Rubyには多重代入と言う機能があります。左側が複数の変数で右辺が配列だった場合、位置的に対応しているもの同士が順番に束縛されていく模様です。

irb(main):001:0> a, b = [0, 1]
[0, 1]
irb(main):002:0> a
0
irb(main):003:0> b
1
irb(main):004:0>

ちょっとこう言う手続き型言語的に便利な機能は、S式のカタマリであるSchemeには存在してないんで(苦笑)。
元のRubyのコード見る限り・・・多値で実装するのが一番近いかなあ。
とは言っても。
Schemeなんかで「多値を返す」のは良く見かけるネタなんですが、一方、「多値を受け取る」のはどうすんだ、と(笑)。
元のコード見ると、最終行で

$c.call b, a + b if b < 100

と、また多重代入やってるっぽいんで、多値で「受け取る」事が必要そうなんですが・・・。
ふ~む、どうすっぺえ。ANSI Common Lispのmultiple-value-bindみたいな機能があれば良いんですけどねえ。
仕様書(R5RS)見てみると、次のような事が書いてあります。

(call-with-values producer consumer) 手続き
producer 引数を無引数で呼び出し,そしてある継続を呼び
出す。この継続は,(複数個の) 値が渡されると,それらの
値を引数としてconsumer 手続きを呼び出す。consumer へ
の呼出しに対する継続は,call-with-values への呼出し
の継続である。


> (call-with-values (lambda () (values 4 5))
(lambda (a b) b))
5
> (call-with-values * -)
-1


うわ、何じゃこりゃ、分かり辛い(苦笑)。
ANSI Common Lispのmultiple-value-bindみたいな形式にしてくれりゃあエエのに。すっげえ見づらいぞ、それ。
まあ、それでも、Rubyのコードとの対比を考えると、保存する領域は最初の変数部分で、そこをcall-with-valuesのconsumer部分で呼び出せば良いのかな。
一応それを方針としてSchemeで書き直してみたのが以下のコードです。

(define *c* #f) ;継続保存用のグローバル変数

(define (fib)
(call-with-values
;; producer部
(lambda ()
(call/cc
(lambda (k)
(set! *c* k) ;継続kをグローバル変数*c*に保存
(values 0 1))))
;; consumer部
(lambda (a b)
(display b)
(newline)
(and (< b 100)
(*c* b (+ a b))))))

これに関して言うと、Rubyの方がシンプルだなあ。メゲました(笑)。

ただ、オリジナルのRubyコードだと、ちょっとcall/ccの使い方が大仰しい気もしますけどね。大域変数への継続の保存より、脱出の方がより本質的なんじゃないか、と思います。
と言うのも、Schemeの仕様書にはハッキリこう記述されているんです。

手続きcall-with-current-continuation は,現在の継続を“脱出手続き” (escape procedure) としてパッケージ化し,それをproc に引数として渡す。脱出手続きとは,もし後でこれを呼び出すと,その時たとえどんな継続が有効であっても捨て去り,そのかわりに脱出手続きが造られた時に有効だった継続を使うことになるScheme手続
きである。


call/ccは本来、悩むようなものでもなく、単に「脱出の為に」設計されているんです。方向性の自由度は高いんですが、他の、例えば「継続の保存」ってのは使い方で言うと結構副作用的なんですよ。
脱出とはどう言うものか、と言うと、例えばわざと無限ループを作っておいて、何らかの条件を満たした場合、処理を中断してトップレベルに戻る、とか。割にC言語とかではお馴染みの概念でして、かつ、それ自体は大して難しいものではないんですよね。
例えば、お題のフィボナッチ数列を実装するとして、次のように実装しちゃえばこれは明らかに無限ループなのです。

(define (fib n)
;; 無限ループのローカル手続き
(define (loop m a b)
(display a)
(newline)
(loop (- m 1) b (+ a b)))
;; ローカル手続きloopの呼び出し
(loop n 0 1))

この無限ループのフィボナッチ数列はベースケース(注4)が無いんで止まりません。0から始まって延々とフィボナッチ数を印字し続けます。
もちろん、最初に見た通り、これを「定型的な」フィボナッチ数列の実装として書き直した方が、普通は無難です。
が、敢えてcall/ccを使うとしては、最初のステップとしては、ローカル手続きとその実行部を(call/cc (lambda (c) ...))として包んでしまいます。

(define (fib n)
(call/cc
(lambda (c)
;; 無限ループのローカル手続き
(define (loop m a b)
(display a)
(newline)
(loop (- m 1) b (+ a b)))
;; ローカル手続きloopの呼び出し
(loop n 0 1))))

そして、ローカル手続きの第一引数、mが0に到達した時「計算を捨てて脱出すれば良い」ので、評価対象はmになりますね。このロジックを繰り込めば、次のように記述できるでしょう。

(define (fib n)
(call/cc
(lambda (c)
;; 無限ループのローカル手続き
(define (loop m a b)
(display a)
(newline)
(loop (- (if (zero? m) ;ここにベースケースを突っ込む
(c #f) ;cは(例えば)#fを持って脱出
m) 1) b (+ a b)))
;; ローカル手続きloopの呼び出し
(loop n 0 1))))

このように、コードの「無限ループ性」を生かしたまま、call/ccを使った脱出で計算を(ある意味無理矢理)終了させる事が可能なんです。
僕が思うには、こっちの「脱出版」の方が幾分考え方としてはスッキリしてると思います。
Rubyだとどーなるんだろうな(注5)。




注釈:

  1. イテレータの豊富さがRubyの特徴なんで、明らかにこんな書き方はフツーはしないでしょう。

  2. Schemeでは末尾再帰最適化が仕様で要求されています。反面、ANSI Common Lispはそうでもなくって、結果、CLerは、一般的にはそこまで再帰にこだわりません。

  3. とは言っても、実装依存の話になりますが、Cの処理系によっては末尾再帰最適化してくれる処理系もチラホラある模様です。代表的なのがgcc。だから、C系のプログラマでも「末尾再帰」って単語は知っておいて損は無いと思います。
    例えば、与題のコードを末尾再帰でCで書けば以下のようになるでしょう。多分。

    #include <stdio.h>
    #include <stdlib.h>

    int fib(int m, int a, int b);

    int main(int argc, char *argv[])
    {
    int (*pM)(int m, int a, int b);

    pM = fib;

    if (argc != 2) {
    printf("パラメータの数が違います。\n");
    return 1;
    }

    (*pM)(atoi(argv[1]), 0, 1);

    return 0;
    }

    int fib(int m, int a, int b)
    {
    printf("%d\n", a);
    if (m == 0) {
    return a;
    } else {
    return fib(m - 1, b, a + b);
    }
    }

    これをgccで最適化レベル2、-Sオプションを合わせてコンパイルすると次のアセンブリコードを吐き出します。

    .file "fib.c"
    .section .rodata.str1.1,"aMS",@progbits,1
    .LC0:
    .string "%d\n"
    .text
    .p2align 4,,15
    .globl fib
    .type fib, @function
    fib:
    pushl %ebp
    movl %esp, %ebp
    pushl %edi
    pushl %esi
    pushl %ebx
    subl $28, %esp
    movl 8(%ebp), %esi
    movl 12(%ebp), %ebx
    movl 16(%ebp), %edi
    jmp .L3
    .p2align 4,,7
    .p2align 3
    .L6:
    leal (%edi,%ebx), %eax
    subl $1, %esi
    movl %edi, %ebx
    movl %eax, %edi
    .L3:
    movl %ebx, 8(%esp)
    movl $.LC0, 4(%esp)
    movl $1, (%esp)
    call __printf_chk
    testl %esi, %esi
    jne .L6
    addl $28, %esp
    movl %ebx, %eax
    popl %ebx
    popl %esi
    popl %edi
    popl %ebp
    ret
    .size fib, .-fib
    .section .rodata.str1.4,"aMS",@progbits,1
    .align 4
    .LC1:
    .string "\343\203\221\343\203\251\343\203\241\343\203\274\343\202\277\343\201\256\346\225\260\343\201\214\351\201\225\343\201\204\343\201\276\343\201\231\343\200\202\n"
    .text
    .p2align 4,,15
    .globl main
    .type main, @function
    main:
    pushl %ebp
    movl %esp, %ebp
    andl $-16, %esp
    subl $16, %esp
    cmpl $2, 8(%ebp)
    je .L8
    movl $.LC1, 4(%esp)
    movl $1, (%esp)
    call __printf_chk
    movl $1, %eax
    leave
    ret
    .p2align 4,,7
    .p2align 3
    .L8:
    movl $10, 8(%esp)
    movl $0, 4(%esp)
    movl 12(%ebp), %eax
    movl 4(%eax), %eax
    movl %eax, (%esp)
    call strtol
    movl $1, 8(%esp)
    movl $0, 4(%esp)
    movl %eax, (%esp)
    call fib
    xorl %eax, %eax
    leave
    ret
    .size main, .-main
    .ident "GCC: (Ubuntu 4.4.1-4ubuntu8) 4.4.1"
    .section .note.GNU-stack,"",@progbits

    僕は残念ながらアセンブリは読めないんですが、アセンブリが読める人は、gccがCによる末尾再帰コードを単なるジャンプ構文に変換しているかどうか確かめてみてください。

  4. 終了条件の事。

  5. Rubyでも書けるか、とトライしてみたが、callccが持つブロックの作用が良く分からず挫折致しました(爆)。

2009年12月24日木曜日

PLT Scheme のストラクチャ

SchemeはR5RSではストラクチャ(構造体)を持っていません。
僕は正直ピンと来ないんですが、ストラクチャは便利であるらしく、Schemeでは今までも実装依存でストラクチャが提供されてたり、あるいはSRFIで提案されていたり、挙句の果てに、今後どうなるか分からないR6RSでは正式に仕様として加わった模様です。

ここでは、PLT Scheme 依存のストラクチャに付いてちょっと書いておきます。
何故PLT Scheme依存なのか?
端的に言うと理由は以下の三つです。

  1. 比較的、ANSI Common Lispのストラクチャに似てるから。

  2. SRFIR6RSの「レコード型」と言う呼び方が気に喰わない(笑)。

  3. SRFIR6RSのドキュメンテーションが抽象的で良く分からん。


と言った感じですかね。

まあ、2番目の「呼び方が気に喰わない」ってのはクダラナイ理由って言えば理由なんですけどね(笑)。でも今時Pascalじゃねえんだから、とかちょっと思うんですよね。
しかも、「仕様に無い」時点での、独自に「レコード型と呼びましょう」ってのはANSI Common Lispに「不必要に」対抗しているように見えて正直好きじゃないんです。CLもSchemeもLisp語族ですが、この二つの言語間を行き来している人も多いでしょうから、なおさら「ツマラン理由で」呼び名を変えるのはロクな事になりませんって、絶対。
そして、SRFIR6RS辺りのドキュメンテーションが正直良く分からんのですよ。極めて読みづらく、動作が想像しづらいのです。ストラクチャに限らず、一般に、Schemeのドキュメンテーションって不必要に抽象的で分かり辛い、と思います。誰がアレで「実用的なプログラム」を書こうと出来るのか、思えるのか。ホント、敢えて言いますが、Schemeのドキュメントって概してサイテーですよ(笑)。リファレンスとして機能しないケースがあまりにも多いと思います。
結局、1番のPLTのストラクチャが「CLに似てるっぽいのが良い」ってのに還元されるわけです。見た目似てたらCLのドキュメントを調べながら動作確認がしやすいから、ですよね。CLはCLHSなんかあって、しかも例示が比較的多いんで、Schemeに比べると遥に分かりやすいのです。マジでこの辺、SchemeはANSI Common Lispを見習うべきだと思いますよ。

PLT Schemeのストラクチャをポール・グレアムのANSI Common Lisp (スタンダードテキスト)
っぽく見てみましょうか。

PLT Schemeでストラクチャを定義するには、define-structを使う。最も単純な場合には、ストラクチャの名前とフィールドの名前、#:mutable、#:transparentを与えるだけである。

(define-struct point (x y)
#:mutable
#:transparent)

これによって、x、yという2つのフィールドをもったストラクチャpointが定義される。また暗黙に、make-point、point?、point-x、point-yと言う手続きも定義される。
make-pointを呼び出すたびに、新しいpointが返される。

> (define p (make-point 0 0))
> p
#(struct:point 0 0)

pointのフィールドへのアクセサは値を引き出す。set-ストラクチャ名-フィールド名!はフィールドの値を変更する。

> (point-x p)
0
> (set-point-y! p 2)
> p
#(struct:point 0 2)

ストラクチャを定義するとその名前のストラクチャの型も定義される。個々のpointは、pointと言う型に属し、さらにストラクト(struct)という型に属することになる。pointであるかどうか判定するにはpoint?を使う。

> (point? p)
#t

2009年12月23日水曜日

How to make an adventure game built on Scheme vol.3

どうも、PLT Schemeの構造体のアクセサをズラズラ書き並べるのがあまり美しくないです。
make-scenarioだらけ。
やってみると、高階手続きでマッピングしながら構造体を作成する事も出来るっぽいんで、コードをそのように修正してみます。
本体はともかくとして、こっちの方がSchemeっぽいのではないでしょうか。

;; PLT Scheme 依存

(define-struct scenario
(iKind ;処理の種類(0 -> 通常文章 1-> 選択肢 2-> キー待ち)
pString ;文章
idx1 ;次のシナリオのインデックス(-1で終了)
idx2 ;次のシナリオのインデックス
))

(define *s-aScenario*
(list->vector
(map (lambda (x)
(apply make-scenario x))
'((0 "シナリオ1\n" 1 0)
(1 "選択肢1 -> 1 選択肢2 -> 2\n" 2 3)
(0 "シナリオ2\n" 9 0)
(0 "シナリオ3\n" 4 0)
(1 "選択肢1 -> 1 選択肢2 -> 2\n" 5 6)
(0 "シナリオ4\n" 9 0)
(0 "シナリオ5\n" 7 0)
(2 "Hit Any Key" 8 0)
(0 "シナリオ6\n" 9 0)
(0 "エンドシナリオ\n" -1 0)))))

(define (main)
(do ((index 0
(let ((it (vector-ref *s-aScenario* index)))
(case (scenario-iKind it)
((0) (scenario-idx1 it))
((1) (let ((getche (read)))
(if (= getche 1)
(scenario-idx1 it)
(scenario-idx2 it))))
((2) (let ((getche (read)))
(scenario-idx1 it)))))))
((< index 0))
(display (scenario-pString (vector-ref *s-aScenario* index)))))


vol.4があるかどうかは知らない。

How to make an adventure game built on Scheme vol.2

取りあえず何も考えずに上のリンクに従って実装。


;; PLT Scheme 依存

(define-struct scenario
(iKind ;処理の種類(0 -> 通常文章 1-> 選択肢 2-> キー待ち)
pString ;文章
idx1 ;次のシナリオのインデックス(-1で終了)
idx2 ;次のシナリオのインデックス
))

(define *s-aScenario*
(vector
(make-scenario 0 "シナリオ1\n" 1 0)
(make-scenario 1 "選択肢1 -> 1 選択肢2 -> 2\n" 2 3)
(make-scenario 0 "シナリオ2\n" 9 0)
(make-scenario 0 "シナリオ3\n" 4 0)
(make-scenario 1 "選択肢1 -> 1 選択肢2 -> 2\n" 5 6)
(make-scenario 0 "シナリオ4\n" 9 0)
(make-scenario 0 "シナリオ5\n" 7 0)
(make-scenario 2 "Hit Any Key" 8 0)
(make-scenario 0 "シナリオ6\n" 9 0)
(make-scenario 0 "エンドシナリオ\n" -1 0)))

(define (main)
(do ((index 0
(let ((it (vector-ref *s-aScenario* index)))
(case (scenario-iKind it)
((0) (scenario-idx1 it))
((1) (let ((getche (read)))
(if (= getche 1)
(scenario-idx1 it)
(scenario-idx2 it))))
((2) (let ((getche (read)))
(scenario-idx1 it)))))))
((< index 0))
(display (scenario-pString (vector-ref *s-aScenario* index)))))


個人的な好みで言うと、Cのコードってそんなに綺麗と思わない。重複多いし。
Schemeへの翻訳は結構大変だったりします。

vol.3があるかどうかは知らない。

How to make an adventure game built on Scheme vol.1

取りあえず何も疑問を抱かずに上のリンクの方針に従う。

(define (main)
(display "シナリオ1\n")
(display "選択肢1 -> 1 選択肢2 -> 2\n")
(let loop ()
(let ((i (read)))
(cond
((not (integer? i))
(display "間違った入力です\n")
(loop))
((= i 1)
(display "シナリオ4\n"))
(else
(display "シナリオ5\n")))))
(display "エンドシナリオ\n"))

vol.2があるかどうかは知らない。

Y Combinator

SchemeによるY Combinatorの実装例。
たった一行で済む。

(define (y f . n)
(apply (f f) n))

2009年12月20日日曜日

#9LISP の003回のチャレンジ問題の回答例


  1. Schemeによる記号処理入門 より

    • 次のコードの評価を考えてみる


      (((lambda (x)(lambda (x)(+ x 1))) 2) 4)



    • 回答例:
      クロージャの問題。
      ラムダラムダだと見づらいんですが、define使って書き直して見た方が直感的です。
      題意の大枠の手続きの部分は、引数を一つ取り、手続きを返す高階手続き

      (define (hoge x) (lambda (x) (+ x 1)))


      と等価です。
      この手続きhogeに引数2を与えても、内側のラムダ式が返されるだけなんで、結果形式的には、題意は

      ((lambda (x) (+ x 1)) 4)


      として実行されます。また、クロージャにより、内側のxは外側のxから保護されているので丸っきり別物です。レキシカル・スコーピングですね。
      結果、5が返ります。
      この手の問題は、Schemeでは定番なんですけど、実はあんま好きじゃないです(笑)。「見づらさ」がとにかくトリッキーなだけ、って印象なんです。
      反面、ANSI Common Lispではこう言う問題は見かけませんね。
      ちなみに、題意のコードの「スタイル」ってのは実はletのマクロ(として実装されてれば、と言う話ですが)の展開形に他なりません。
      実は題意のコードは、


      ((let ((x 2))
      (lambda (x) (+ x 1)))
      4)


      と等価である、って事を付け加えておきます。
      これはletにより、xが2に束縛されていますが、ボディー部のxは外側のxと全く関係なく存在し、結果let式はボディーのラムダ式を「ただ返してる」に過ぎないのです。



  2. SICP より

    • 組み込みの特殊形式if と同じ動作をするnew-if 手続きを定義してみる

      • ifがなぜ特殊形式であるか考えてみる

    • 回答例:
      多少インチキですが、題意の通りだとすると、


      (define-syntax new-if
      (syntax-rules ()
      ((_ pred then-clause else-clause)
      (cond (pred
      then-clause)
      (else
      else-clause)))))


      でしょう。
      ifが特殊形式である理由は、普通の手続きだと、ボディの評価を始める前に引数の評価を全て終えてからボディが実行される、からです。
      普通は問題が生じないのですが、再帰なんかの場合、「先に引数を評価」してしまうと、引数がいつまでも展開されていって、終了地点に到達しません。これを避ける為には条件に従って引数を評価したりしなかったり、と言う仕組みが必要になります。
      これがifが特殊形式でなければならない理由です。


  3. The Little Schemer より

    • 引数がatomであるか判定するatom?手続きを定義してみる

      • 回答例:


        (define (atom? x)
        (not (pair? x)))


        これはちょっと微妙な問題ですね(笑)。なんせANSI Common Lispと違って、Schemeにはアトムが定義されていません。
        ANSI Common Lisp上のatomの定義は「コンスじゃないもの」です。コンスかどうか調べる述語がANSI Common Lispではconspで、Schemeではpair?にあたります。



    • 引数のリストの要素がすべてatomであるか判定するlat?手続きを定義してみる

    • 回答例:


      (define (lat? ls)
      (call/cc
      (lambda (return)
      ;; 注:実は Scheme には atom と言う概念はありません
      ;; ANSI Common Lisp の定義に従うと
      ;; atom は pair じゃないもの、でO.K.です
      ;; しかし、CL では空リストが偽を表すのに対し、
      ;; Scheme では空リストは偽を表さず #t となります
      ;; その為、両者の計算結果に整合性が出ないので、
      ;; atom? を弄るのではなく、 lat? の最初で
      ;; 引数リスト ls の pair? 判定を加えました。
      ;; (ただし、論理的に必要か、と言われると疑問です)
      (and (pair? ls)
      (map (lambda (x)
      (let ((it (atom? x)))
      (if it it (return it)))) ls)
      #t))))


      若干トリッキーな書き方をしているように見えますが、ポイントは四つです。

      1. 高階手続きmapで引数のリストの各要素にatom?を適用する。

      2. 1番目の「要素への適用」で、どっかで#fが返ったら即座にcall/ccで処理を中断して#fを持って脱出する。結果、必ずしもリストの末尾まで走査しなくても良い。

      3. ポールグレアムのOn Lispに載っているアナフォリック・マクロの影響を受けてる。ただし、R5RSの衛生的マクロではアナフォリック・マクロは書けないので、アイディアだけ借用。述語による判定結果をitに束縛して、if内で使いまわしている。

      4. mapで引数リストを末尾まで走査し終わればリストの要素は全てatomである。またその結果は論理的には#tとなる。そのまま返しても論理上は構わないが、一応仕様に従って#tか#fを返すようにした。鍵はandでmapがリスト末尾まで走査終了=#tなので、andの第二引数である#tが評価値として返される。



    • 引数で指定されたatomが引数のリスト内に存在するか判定するmember?手続きを定義してみる

    • 回答例:


      (define (member? atom ls)
      (call/cc
      (lambda (return)
      (not (map (lambda (x)
      (let ((it (eqv? atom x)))
      (if it (return it) it))) ls)))))


      解法のネタとしては前出のやり方と同じです。call/ccでの脱出を用いています。前問と逆で、itが#tの場合にitを持ったまま計算を脱出します。
      mapが引数リストの末尾まで走査してリストを返した場合、返り値のリストは論理的には#tとなります。従って、そのリストをnotで否定すれば与題の解となります。

  4. Schemeで書いてみる


    • FizzBuzz

    • 回答例:

      (define (fizzbuzz ls)
      (map
      (lambda (x)
      (cond
      ((zero? (modulo x 15))
      "Fizz Buzz")
      ((zero? (modulo x 5))
      "Buzz")
      ((zero? (modulo x 3))
      "Fizz")
      (else
      x))) ls))


      これはまあ、定型的な解き方ですね。

    • 階乗

    • 回答例:


      (define (factorial k)
      (let loop ((n k) (return 1))
      (if (zero? n)
      return
      (loop (- n 1) (* return n)))))


      これも定番ですね。

    • フィボナッチ数

    • 回答例:


      (define (fibonacci n)
      (let loop ((count 0) (f0 0) (f1 1))
      (if (= n count)
      f0
      (loop (+ count 1) f1 (+ f0 f1)))))


      フィボナッチ数列は良く「複雑で計算コストがかかる再帰の例」として挙げられますが、実際は末尾再帰として上のように書くことが可能です。引数内処理を試みて、引数をどんどんズラしていくイメージで書けばそんなにコストはかからないでしょう。

    • コラッツの問題

    • 回答例:


      (define (a n)
      ;; ローカル手続きで f を定義
      (define (f n)
      (if (even? n)
      (/ n 2)
      (+ (* 3 n) 1)))
      ;; n が (* 3 (expt 2 53)) までは1へと収束する事が確かめられている
      ;; 基本的に未解決問題なので、(= i 1) が完全なベースケースかどうかは不明
      (let loop ((i n) (ls '()))
      (let ((ls0 (cons i ls)))
      (if (= i 1)
      (reverse ls0)
      (loop (f i) ls0)))))


      これは初見の問題でした。
      が、数学的なアルゴリズムは実は実装そのものはそんなに難しく無いですね。何せ、数学的な定義式を「そのまま」S式に置き換えれば一丁上がり、ですから。
      Wikipediaの指示に従って、手続きfを定義し、それを局所手続きとして実装しています。

    • アッカーマン関数

    • 回答例


      (define (ack m n)
      (cond
      ((zero? m)
      (+ n 1))
      ((zero? n)
      (ack (- m 1) 1))
      (else
      (ack (- m 1) (ack m (- n 1))))))


      アッカーマン関数はマジで計算負荷が大きい手続きとなります。あんまり大きい数を与えると処理が終わらないでしょう。
      定義的に言うと、「数式をそのままS式に置き換えた」だけで末尾再帰の式となります。
      ただし、形式的には末尾再帰ですが、引数内でまた末尾再帰が起こり、スタックが開放されないので、言わばこれは「最適化できない」末尾再帰の典型例だと思います。



2009年12月19日土曜日

うぶんちゅ!第6話のギミックが少々不快な件に付いて

今回、アスキーから出版されたUbuntu Magazine Japan vol.02 (アスキームック)ですが。創刊号とは違って、今回は比較的ネットも穏やかなものです。あんま取り上げられていませんね。
まあ、取り上げなくなったのは逆に良い事なんですよ。「普遍化して落ち着いた」「購買層が定着した」って言い方も出来ますし。誰が毎週「今週ビッグコミックスピリッツが発売します!!!」なんて記事をブログに上げるのですか(笑)。早くも初回で普遍化してユーザーベース(と言えばいいのか)を得た、ってのは賞賛に値します。偉い。iBus使いにくい(謎)。
あ、僕は今はスピリッツじゃなくってヤングガンガン派ですけど(謎)。

ただ、ですね~~。
Ubuntu Magazine Japan創刊号から思ってたんですが。

うぶんちゅ!って漫画、本当に面白い?

いや、定期刊行誌(2ヶ月に1度?)になる前は、一回に一つずつ、「何らかのオープンソース絡みのアイディア」を短い中で分かりやすく説明しよう、って頑張ってたんですよね。そこは認める。
ただ、定期刊行誌になって、第一回、第二回と、

実はUbuntuにもオープンソースにもネタ的には全く関係無くね?

って感じたのが正直なトコで。
早くも定期刊行誌第二回で「失速してる」んですよね~~~(笑)。

いや、別にさ。実際「Ubuntuネタだけ」とか「オープンソースネタだけ」で漫画展開させよう、としてもネタ切れなるだろうな、って危惧は分かるんですよ。多分そうだろうな、と思います。
正直言うと、うぶんちゅ!のような、ある種の「啓蒙漫画」ってのは、不定期の本の「企画モノ」で成り立つスタイルであって、このままの形で「定期連載」ってそもそも無理があるでしょ、って事なんです。
タイトルにある通り、素直に「ラブコメ」に移行してった方が良くない?マジで。

んでね、今回ギミックとして使われてて酷かったのが

魔術師本

なんですよ。曰く、

「そりゃ女の子は魔法に弱いんだもーん♥」

とか書いていて。
正直イラっとしました(爆)。率直に

「アホか?」

とか思って(笑)。
そんな「女の子は魔法に弱いんだもーん」とか言うような本か?これって。
あまりに酷すぎる。持ってるだけにかなり不快なセリフだったのです。
作者、分かってやってんだろうな?

計算機プログラムの構造と解釈、通称SICPとか魔術師本と呼ばれるこの本は、MITのコンピュータ・サイエンスの初年度の学生の為に長年使われてきた本です。
極めて難解な本で、正直、僕もまだ読破出来ていません。多くの人が読破を試みてるんですが、マジメな話、難攻不落と言って良い本なんです。
しかも、この本はSchemeと言うLisp方言を使って、「プログラミングを教える」と言うより、アセンブリレベルの話を延々と書いていて、全くもって意味不明な本なんです(笑)。実際有名な本なんですが、批判も多い。
まず、ポイントなんですが、
  • Ubuntu Magazine Japan と言う、どー見てもLinux初心者が購読層の多数を占めてるような雑誌で、名前を出すのは不適切である。

と言う事です。
いや、素人さんは怖いんですよ。

「いやあ、魔術師本なんてカワイイなあ。漫画うぶんちゅで紹介されているくらいなんだからUbuntuに関係あるのかも。買ってみようか。」

とかなるかもしれません。
いや、マジで不適切です(笑)。これは「あり得る」んですよ。
しかし、そう簡単に読みこなせるような本じゃないです。泣いてます(笑)。
それともう一つ。同書でMITで書かれたSchemeと言うLisp方言を使ってる、って意味に付いて。そもそもLispってのはUNIX文化と全く違うトコで生育されたプログラミング言語なんです。つまり、Ubuntu以前にUNIXとも「全く関係無い」んですね。
Cをベースにした「UNIXの世界観」と全く違うプログラミング言語なんだって。
ハテサテ。ではうぶんちゅ!と言う漫画で「ネタにする」必要性があった本なんでしょうか?
結論は無いですね。単なるギミック。こんな漫画の描き方、って無いですよ。
だって、Ubuntu Magazine Japan vol.02 (アスキームック)の第6話のあらすじってこうですよ?

Ubuntu 9.10がリリースされる。

1行で済んじゃう(笑)。広告より酷い(笑)。それで不必要なギミック投入・・・。
たまりませんわな。

いやさ、マジメな話。
「Ubuntuに付いてだけ」「オープンソースに付いてだけ」で漫画のストーリー展開するのって無理ある、って。実際作者の人、これ以上やらせたら「可哀想」ってレベルになってきてると思いますよ。マジな話で。
だったら。
絵がカワイイんだから、ASCIIの編集部も自由に描かせてあげればいいじゃない。
例えばさ。僕は昔「ファミ通」とか愛読してた事あるんで(笑)、敢えて言いますけど、ファミ通に「連載されていた」漫画って必ずしも「ゲーム漫画だけ」だった、って事ねーじゃん。
いくらUbuntu専門誌でも「Ubuntuだらけ」にする必要無いんだってばさ。もちろん、本文はUbuntuテンコ盛りで構わない(と言うかそれを望んでる)んですが、漫画くらい雑誌のオアシスでしょ?何も「Ubuntuに無理矢理関連させた」漫画じゃなくっても良いと思うんですけど。
これは明らかに無理な企画が祟ってると思います。不定期刊行誌時代の「企画」のままで突っ走らなくても良いんだってばさ。

どーせやるんだったら、例えば鈴木みそさんみたいな「突撃レポート」ものでも良いし(笑)。たわごとでかおりんさんが紹介してたこの記事の漫画版みたいなさ。Ubuntu未経験者の一漫画家が編集部の要請によりUbuntuエキスパートユーザーに向かって「成長するのか?」みたいな(笑)。実体験レポ。読んでる読者も「あるある」って思い当たる節がたくさんある漫画になると思うけどなあ。
下手すれば批判っぽい内容になる可能性もあるけど、「賛美だけ」じゃダメだよ。漫画だから「こそ」描ける毒があるべきだし、みんな引っかかるトコはみんな引っかかるんだ、って実例にもなるんじゃない?
あるいは。奇作ファミ通のアレ(仮題)みたいなワケ分からん漫画とか(笑)。「Ubuntuのアレ(仮題)」とかやってくれねえかな、竹熊健太郎氏(笑)。こーゆーヘンな漫画が掲載されてる事「だけ」でもコアな漫画ファンがUbuntu Magazine Japan買ってくれるぞ(笑)。

まあ、とにかく、今のままではうぶんちゅ!は先細りになるのが目に見えています。企画考え直した方がいいよ。あるいは路線変更、とかさ。
如月あかねとかの「生粋のUNIXER」なんて設定自体が今回全然生きてないし。元々プログラミングやってる、なんて設定でも無いでしょ?何で魔術師本を欲しがるんだか。
ぶっちゃけ、「生粋のUNIXER=凄腕のプログラマ」でも無いんだよね。パーセンテージで言うと。
僕が観察してた限りで言うと、Slackwareなんか弄り倒している人間はとても「プログラミング」まで辿り着けません。そこに行くまで障害が多すぎるし、また、「OSをイジる事だけが」目的と化すような人が多いんで、UNIXER=凄腕プログラマ、なんて設定にはほぼ、ならんのです。
(逆に、Windowsのような「プログラミング環境構築」が比較的簡単なトコでプログラミング「自体」を覚えて、Slackwareなんかに移ってきて「本領発揮」って事はあり得ますがね。)

Allegro CL 8.1 Free Express Edition を Ubuntu 9.10 にインストール

Allegro CL 8.1 Free Express Edition を Ubuntu 9.10 にインストールしてみる。
ぶっちゃけた話、公式ページExpress Installation for UNIX (Linux and FreeBSD) ってのがクソの役にも立たないので、ここで手順をメモっておきます。

  1. クソ苛立たしいアンケートの必須事項に記入し、submitボタンを押す。
  2. acl81_express.bz2をダウンロードする。
  3. acl81_express.bz2をダブルクリックして展開し(ここでは$HOMEに展開するものとする)、acl81_expressと言う圧縮ファイルを生成する。
  4. もう一発acl81_expressをダブルクリックして展開し、同名のacl81_expressと言うフォルダを作る。
  5. acl81_expressを適切なフォルダに移動する。Ubuntuのパッケージ管理システムとぶつからないように、ここでは/optディレクトリに移動する、とする。コマンドは以下のように。
    sudo mv acl81_express /opt/


  6. 続けて次のコマンド群を入力する。


    cd /opt/acl81_express
    sudo ./newlicense
    sudo ./update



  7. Ubuntuの[システム]→[設定]→[メインメニュー]を辿り、「メニュー」から「プログラミング」を選択して、「新しいアイテム」ボタンを押す。
    名前(N)を「Allegro CL」にして、コマンド(A)/opt/acl81_express/allegro-expressに設定して「OK」ボタンを押す。
  8. [アプリケーション]→[プログラミング]→[Allegro CL]と辿ればAllegro CLが起動する。




2009年12月17日木曜日

gedit TextMate化計画

Mac OS XではTextMateと言う名前のテキストエディタにやたら人気があるらしい。
残念ながら、日本語入力がかなり怪しいそうなんで、日本ではまるでCarbon Emacsの独断場のようにまで見えるんですけど、海外のハッカーの口からはやたらその名前を聞きます。
こんなに人気あるんだったらオープンソースなのか?と思いきや、いや、れっきとしたプロプライエタリソフトだそうです。
正直言うと、オープンソースに囲まれて暮らしていると、今更プロプライエタリなソフトを使うのがバカらしくなるんですが、そこはそれ。

「そんなにいい、っつーのならどんなもんなんだ?」

と気になるのですね。
なんせ、最近Windows版TextMateであるE-TextEditorなるものまで登場したそうなんで、興味は絶頂です。

Linux版は出るのか?

う~ん、今のトコその予定は無いようで・・・。
面白いよな。同じPC-UNIX系であるLinux版は出さずにWindows版を出すとは・・・。

僕は今、一応Emacsユーザーではありますが、別にIDE vs. テキストエディタの論争には丸っきり興味がありません。
いつでも「より使いやすいもの」があればそっちに動く心づもりです。
全然ツールにはこだわらん。
まあ、viも操作系は「爆笑」って程可笑しいとは思っていて、別に「嫌い」とか全然感じないんですが、単に日本語打つ際、メンドくせえな、ってのがvi触った率直な感想です。
でも、より面白そうなテキストエディタであるTextMate、興味ありますね。どんなもんでしょう?

んで、Web散策してみると、Ubuntu標準のテキストエディタをTextMateみたいにしてしまおう、と言うようなネタがあって。

ちょっと軽く紹介しておきましょうか。

  1. 端末から次のコマンドを走らせる。

    sudo aptitude install gedit-plugins



  2. geditの[編集]→[設定]から「geditの設定」を呼び出し、タブからプラグインを選び、

    • セッションの保存

    • コード・スニペット

    • ファイル参照ペイン

    • コードのコメント

    • 外部ツール


    の5つにチェックを入れて有効にする。

  3. 次の3つのプラグイン



    mkdir .gnome2/gedit/plugin

    とした後、~/.gnome2/gedit/pluginsに放り込む。
    その後、geditの[編集]→[設定]から「geditの設定」を呼び出し、タブからプラグインを選び、これらのプラグインを有効化する。

  4. 端末から、


    wget http://robzon.kapati.net/rails/rhtml.lang && sudo mv rhtml.lang /usr/share/gtksourceview-2.0/language-specs/
    wget http://robzon.kapati.net/rails/rails.xml && sudo mv rails.xml /usr/share/mime/packages
    sudo update-mime-database /usr/share/mime

    を走らせる。

  5. 端末から

    sudo aptitude install ri

    を走らせる。これでRubyのインタラクティヴ・ドキュメンテーションが参照出来る。
    使い方は、geditの[ツール]→[External Tools]→[コマンドの実行]を出し、

    ri String.split

    等と打ち込んで実行する。

  6. Rubyユーザーは、端末で


    sudo gem install rspec ZenTest
    sudo apt-get install ruby-gnome2
    wget http://grigio.org/files/ruby-libnotify_0.3.3-1_i386.deb && sudo gdebi-gtk ruby-libnotify_0.3.3-1_i386.deb


    を走らせておけば、autotestなるものも簡易に行えるらしい(良く知らん)。


とまあ、こうすればgeditがTextMateみたいになるらしい。
でも、良く分かりませんね(笑)。なんせ、TextMate自体を使った事が無いんで(笑)、比較出来ない。
あと、サードパーティのプラグインを探してインストールするのもメンド臭いですし。tarballか何かにそのうち纏めてみましょうか。
そして、gedit自体がCommon Lispに対応してないんで、僕個人としては、あまり意味があるカスタマイズじゃなかったです(苦笑)。