2006/09/30

GaucheにもRubyみたいなARGFがほしい。
正確にいうと、ほしがっているのは僕じゃないんだけど、確かにARGFみたいな仕組みがあると使い捨てのテキストフィルタを書いたりするのは簡単になりそうだ。Gaucheのマニュアルではmainを使うことが推奨されているけど、気楽で泥臭いスクリプトを作りたいことだってある。

RubyのリファレンスマニュアルのARGFの項目には「スクリプトに指定した引数 (ARGV を参照) をファイル名とみなして、それらのファイルを連結した 1 つの仮想ファイルを表すオブジェクト」とある。その説明がARGFのすべてなら、Gaucheに用意されている仮想ポートで似たようなものが作れるかもしれない。

でっちあげてみた。引数として渡されたファイルのテキストをいったんバッファに吐き出しているので、Rubyのように*argv*のリストが変更されるわけではない。バッファが空なら標準入力を読む。
#! /usr/local/bin/gosh

(use gauche.vport)
(use srfi-13)

(define argv-str
(let R ((files *argv*) (str ""))
(if (null? files)
""
(call-with-input-file (car files)
(lambda (port)
(let ((joined-string
(string-join (list str (port->string port)) "" 'strict-infix)))
(if (not (null? (cdr files)))
(R (cdr files) joined-string)
joined-string)))))))

(define (getc str)
(cond ((> (string-length str) 0)
(let ((c (string-ref str 0)))
(set! argv-str (string-drop str 1))
c))
((= (string-length str) 0)
"")
(else
(error "Out of Range -- getc"))))

(define (argf thunk)
(if (string-null? argv-str)
(with-input-from-port (current-input-port)
thunk)
(with-input-from-port
(make <virtual-input-port>
:getc (lambda () (getc argv-str)))
thunk)))

;;; test
(argf (lambda ()
(port-for-each
(lambda (line) (print (regexp-replace #/hello/ line "damn")))
read-line)))


実行結果
$ cat test.txt
hello world
this is argf test
$ ./argf.scm test.txt test.txt
damn world
this is argf test
damn world
this is argf test
$ cat test.txt test.txt | ./argf.scm
damn world
this is argf test
damn world
this is argf test

作ってから必ず思う、すでにこんなのは誰かが作っているんではないだろうか。

2006/09/26

荒れまくっていたウィキペディアの実数の項目が素敵な解説に直されて先週復活していた。編集履歴を見ると、Makotoyさんという方の尽力らしい。

荒れる原因になったもとの解説は数直線を使ったもので、「実数は有理数を項とする無限数列の収束値として得られる」と説明していたようだ。で、そこからなぜか無限小数の表現が0をのぞいて一意に決まるとか決まらないとかの議論になって、それで紛糾していたらしい。なにか世界には「実数」という確固たるモノがあるって素朴に思いがちだけど、実際には順序と演算を適切に用意してやることで公理的に決まるだけのものにすぎない。つまり、数字を使わなくても構築できて、でもそれは結局は数字で表現するふつうの実数と同型になる。そんなわけで、数字とか数直線上の点をもって実数とは何かを議論するのは、あんまり意味がないと思うんだけど、どうして1.0000……とか0.9999……とか、数字に異常に固執する人がいるんだろう。きっとあれだ。小学校の教師が悪いんだ。

2006/09/21

行列の固有値を求めたい。
なにをいまさら感たっぷりなんだけど、理系の出版社でテクニカルレビューっぽいことをしていると、特に統計の本なんかで行列の固有値を検算したい場合がなきにしもあらず。たいていは Maxima に突っ込んじゃえばいいんだけど、Maxima では特性多項式を作ってそれを解いているらしく、うまく解が求まりやがらないことがある。実際、maxima/share/matrix/eigen.macを見ると、charpolyという関数で特定多項式を作り、それをsolveという関数で解いている。で、この solve という多項式を解く関数がうまくないといったことがMaximaのマニュアルにも書いてある。
eigenvalues calls the function solve to find the roots of the characteristic polynomial of the matrix. Sometimes solve may not be able to find the roots of the polynomial
幸い、固有値を求めたい行列は対称行列ばっかりなので、自分でJacobi法をナイーブに実装してみた。対称行列だとうれしい理由やJacobi法については『プログラミングのための線形代数』の第5章で。

jacobi.scm
gosh> 
(define A
((make-matrix 6 6)
0.68 0.65 0.8 0.11 0.01 0.14 0.65 0.88 0.89 0.02 0.19 0.01 0.8 0.89 0.91 0.02 0.04 0.1 0.11
0.02 0.02 0.81 0.82 0.77 0.01 0.19 0.04 0.82 0.81 0.64 0.14 0.01 0.1 0.77 0.64 0.66))

gosh> A
((0.68 0.65 0.8 0.11 0.01 0.14) (0.65 0.88 0.89 0.02 0.19 0.01) (0.8 0.89 0.91 0.02 0.04 0.1)
(0.11 0.02 0.02 0.81 0.82 0.77) (0.01 0.19 0.04 0.82 0.81 0.64) (0.14 0.01 0.1 0.77 0.64 0.66))

gosh> (eigenvalues-jacobi A)
(-0.010575430595377565 -0.09400171282374802 2.109504119397093 -0.08138275206455295 0.279213041557744 2.5472427345288424)


行列のデータをどういうふうに表現すべきなのか、ひどく悩んだ。Dybvig 本のようにベクトルを使うのがセオリーなんだろう。ベクトルなら行列のij要素を取り出したり変更したりするのも簡単だ。でも、行と列を順繰りになめて各要素をちこちこ掛けたり足したりする処理ばっかり書くことになりそうで、ちょとブルー。そんなわけで今回はあえてリストのリストとして定義した(行ベクトルが1つのリスト。それを要素に持つ縦ベクトルのリストが行列)。リストなので、行列の積や和なんかも高階関数だけで定義できる。
(define (matrix-transform m)
(apply zip m))
(define (matrix-product m1 m2)
(if (not (= (line-length m1) (row-length m2)))
(error "Matrix-Product Not Defined" (list m1 m2))
(apply (make-matrix (line-length m1) (row-length m2))
(map (cut fold + 0 <>)
(map (cut apply map * <>)
(cartesian-product (list m1 (matrix-transform m2))))))))
(define (matrix-sum m1 . ms)
(map (cut apply map + <>)
(apply zip m1 ms)))
ちょっと満足。ただし単位行列や回転行列を定義するのに要素を頭からなめるはめになってるんだけどね。満足しちゃだめ!

2006/09/18

ときどきむしょうにハンダ付けがしたくなる。ちょうど先週、妙に面白いキットばかり開発して秋月で販売しているトライステートからSHOUTcast形式のインターネットラジオを再生するBBシャウトというキットが発売されたので、これを作ってみた。お値段はちょっぴり張りますが。

SHOUTcastはWinAmpで有名なNullsoftが開発したストリーミング技術で、MP3などのメディアをHTTPの拡張を使ってサーバからマルチキャストするものらしい。受信と再生はWinAmpだけでなくiTunesなどでもできる。ただ、どうやら日本にはあまりサーバがない。現に、Wikipediaには「ストリームの生成にはSHOUTcastのサービスを使うのが現実的な選択」とあるのに、ウィキペディアを見ると「インターネット放送の集合体」という適当な扱いを強いられている。まあ、ジャズとクラシックを無作為に流しっぱなしにするだけなら困ることはない。ところで店舗でBGMに海外のSHOUTcastを流してても、やっぱりJASRACから破廉恥な請求を受ける危険があるのかしら。

で、このSHOUTcast形式で配信されているストリームを受信して再生する専用のボードがBBシャウト。キットは、僕のような素人でも2時間くらいで完成します。いわゆるブロードバンドルータにつないで電源とスピーカーを接続すれば、プリセットされている放送局の音源はすぐに聴ける。

bbshout-env

やっぱり箱に入れないと不便だな。

2006/09/14

個人的な理由で2日間会社を休んでいる間に Debian サーバがアップデートされていた。ありがとうございます && ごくろうさまです > hさん。ところでなんか amazon から不思議な商品が届いたんですが、これを何に使えと?

で、アップデートの結果、telnet でログインできなくなっていた。まあ、telnetd を動かさないこと自体はまったくOKっす。ただ、今まで TeraTerm から SSH2 でログインする気になれなかったので、サーバ上には公開鍵がないんです。公開鍵を登録しようにもサーバにログインできないんです。
幸い samba が利用できるようだったので、エクスプローラ上で公開鍵をコピーして ~/.ssh/authorized_keys を作った。これでつながるよね。
ところが TeraTerm(SSH2,utf-8対応版)でまったくつながらない。Cygwin からもだめ。TeraTerm のダイアログに表示されるエラーメッセージは意味不明だし、Cygwin から ssh コマンドで接続を試みても "Permission denied (publickey)."といわれるばかりだし。

結局『OpenSSHセキュリティ管理ガイド』の267ページを見てようやく解決した。~/ssh/authorized_keys のパーミッションが user 以外に書き込み可能になってたりすると、この "Permission denied (publickey)." というエラーが出るらしい(ただし、StrictModes が no ならエラーにならない)。今回のケースだと samba から authorized_keys を作ったので、そのパーミッションは 666 になっていた。しょうがないので、あきらめてコンソールからログインしてパーミッションを設定しなおす。

教訓

* 最初からコンソールに移動して作業しろ
* エラーメッセージは google する前に本で調べろ

2006/09/12

会社を休んで日本ソフトウエア科学会のPPLサマースクールを受講してきた。へとへとになって日暮里まで帰ってきて、考え事をしながら歩いてたら、道に迷った。もう天才的な方向音痴のCさんを馬鹿にできない。っていうか、最近Cさんにセクハラで訴えられかねないくらいつらくあたりすぎ。本当に反省しています。ごめんなさい。

第4回プログラミングおよびプログラミング言語サマースクール
http://www.math.nagoya-u.ac.jp/~garrigue/ppl_ss06/


圏論の諸相(講師:木下佳樹先生)

冒頭で「諸相といっても2時間で話せるのはせいぜい1相」という前フリがあったけど、本当にそうだった。そんなわけで、Haskell→圏論というノリの参加者にはつまらなかったかもしれない。
個人的には、これまで聞きかじっている知識に横糸を何本か通すことができてよかった。以下、講義中に勝手に頭の中で構成したまとめ。絶対に参考にしてほしくないわけですが(どうせこんなページに圏論について真剣に知りたい人はこない)、詳しい人に勘違いを指摘していただくのは大歓迎です。

圏論ってのは、「集合全体の集合」とか「写像全体の写像」のように、集合論だけだとパラドクスを誘発しかねない何かを扱うべく捻り出された概念なんだよね。たしか。だから、「集合全体の集合」みたいなものにやばさを感じない限り、そもそも圏論のありがたみとか面白さはわからないような気がする。講義で「"small"な集合」という言い方を強調してたり、「集合の要素を使わずに単射の定義を与えてみよう」というクイズで「集合全体の集合を認める」という但し書きをしていたのには、そういう事情があるはず。
で、この「集合の要素を使わずに単射の定義を与えてみよう」クイズがえらく自分のツボに入った。集合AからBへの単射っていうのは、ぶっちゃけると集合Aの要素と集合Bの要素が1対1に対応しますってことで、それを「要素」とか言わないで定義しろっていうのがクイズの趣旨。答えはこうなる。
f が集合 A から集合 B への単射
=def
任意の集合C と任意の h,k:C→A について f・h = f・k ⇒ h = k
つまり、単射という写す集合と写される集合の要素に関する問題を、移すほうに値域を持つ別な任意の写像(ただし定義域は固定)どおしの関係として定義すればいいってこと(ちなみに講義では、たぶんあえて、定義域とか値域うんぬんの議論をぼかしてた。当たり前っちゃ当たり前のことなんだけど、これが固定されていないと f との合成写像を取ったところで何の意味もない。そのため圏論では、定義域と値域をあわせて写像ではなく「射」という言葉を使ってる。たぶん。僕のこれまでの圏論の認識といえば「射で考えるやり方」という程度だったので、今日の講義でようやくさっぱりした)。
同じように任意の集合とそこからの任意の射を使うことで、単射に限らず数々の集合っぽい概念を再定義できる。ところで、たとえば直積がペアをあらわすように、集合の概念はデータ構造を形成できる。ってことは、圏でもやっぱりデータ構造を定式化できるよね。たぶん、これが今日の講義のメインだったんだと思う。


2時間で真似(まね)ぶ関数型言語のコンパイラ(講師:住井英二郎先生)

MinCamlの話は仕事や趣味からはいちばん近い話題で予備知識も多かったせいか、関心するところが多すぎてあまり扇動的な気分にはなれず……。実はこのサマースクールに参加した背景には、講義の内容から技術的な知見を得たいっていう以上に、精神的にアジテートされたいっていう動機があった。まあ、お前の求めてるものがおかしいって話なんですが。
余裕があったらまとめをかく。


述語抽象化によるアルゴリズムの検証 ~ シェープ解析を例として(講師:田辺良則先生)

プログラムの安全性を検証したいけどすべての状態と状態遷移を検証するのは無理だよね、それなら数学的に証明された方法で抽象化した状態とその遷移をうまく取り出して検証しましょうって話。まったく予備知識のない分野だったせいか、3時限目にもかかわらず異常に興奮した。プレゼンも面白い。
これも、余裕があったらまとめをかく。

2006/09/05

いよいよネタ切れか。とりあえず内部でプロシージャを定義するのを止めて、ついでに末尾再帰にだけしておこう。
(define (quicksort/values/cps ls k)
(if (null? ls)
(k '())
(quicksort/values/cps
(cdr ls)
(lambda (cdrls)
(receive (low high)
(partition (cut > (car ls) <>) (k cdrls))
(append low
(cons (car ls) high)))))))
昨日で一気にFPっぷりがあがった気がする。にしてもダサい名前のつけ方だ。

2006/09/04

急がないと歯医者に間に合わないけど、ひきつづきクイックソート。partitionかあ。ありがとうございます>nobsun
(define (quicksort/values ls)
(define (low-high ls)
(partition
(cut > (car ls) <>)
(cdr ls)))
(if (null? ls)
'()
(receive (low high)
(low-high ls)
(append (quicksort/values low)
(cons (car ls) (quicksort/values high))))))
気が付くと lambda がいない。

2006/09/03

Scheme Kata の続き。いちおう毎日ちょっとでも続けたいんだけど正直ネタ切れ。なんで初日に4つも作っちゃったんだろう……。
苦し紛れに昨日の多値を使ったバージョンをそのままreceiveを使って書き直す。hanataniさんに教えてもらうまでreceiveもcutも知らなかったから、苦し紛れとはいえ個人的な訓練にはなっているような気がする。Kata だからそれでいいじゃん。
(define (quicksort/values ls)
(define (low-x-high)
(values
(filter (cut > (car ls) <>) (cdr ls))
(list (car ls))
(filter (cut <= (car ls) <>) (cdr ls))))
(if (null? ls)
'()
(receive (low x high)
(low-x-high)
(append (quicksort/values low)
x
(quicksort/values high)))))

2006/09/02

Scheme Kata のつづき。多値でクイックソート。filter からは逃れられず。
(define (quicksort/values ls)
(if (null? ls)
'()
(call-with-values
(lambda ()
(values
(filter (lambda (x) (> (car ls) x)) (cdr ls))
(list (car ls))
(filter (lambda (x) (<= (car ls) x)) (cdr ls))))
(lambda (low x high)
(append (quicksort/values low)
x
(quicksort/values high))))))

2006/09/01

いまさら Code Kata をやってみようと思った。といっても Kata 1 はコードを書くわけじゃないのか。というわけで Kata 2 から。うーん、二分木の探索ねえ。めんどくさいので勝手にクイックソートに問題を変更させていだきます。でも4つしか思いつきません。しかも二個目は一個目からコピペしただけのいんちき。ほかにどんな方法があるんだろう。
(use srfi-1)
(define ls '(4 9 2 5 8 7 3 1 6 4))

(define (quicksort1 ls)
(if (null? ls)
'()
(append (filter (lambda (x) (> (car ls) x)) (quicksort1 (cdr ls)))
(list (car ls))
(filter (lambda (x) (<= (car ls) x)) (quicksort1 (cdr ls))))))
(quicksort1 ls)

(define (quicksort2 ls)
(call/cc
(lambda (k)
(if (null? ls)
k
(append (filter (lambda (x) (> (car ls) x)) (quicksort2 (cdr ls)))
(list (car ls))
(filter (lambda (x) (<= (car ls) x)) (quicksort2 (cdr ls))))))))
(quicksort2 ls)

(define (quicksort/cps1 ls k)
(if (null? ls)
(k '())
(quicksort/cps1
(cdr ls)
(lambda (cdrls)
(append (filter (lambda (x) (> (car ls) x)) (k cdrls))
(list (car ls))
(filter (lambda (x) (<= (car ls) x)) (k cdrls)))))))
(quicksort/cps1 ls (lambda (k) k))

(define (quicksort/cps2 ls k)
(if (null? ls)
(k '())
(quicksort/cps2
(filter (lambda (x) (> (car ls) x)) (cdr ls))
(lambda (ls-lower)
(quicksort/cps2 (filter (lambda (x) (<= (car ls) x)) (cdr ls))
(lambda (ls-upper)
(k (append ls-lower
(list (car ls))
ls-upper))))))))
(quicksort/cps2 ls (lambda (k) k))
Code Kata というより Scheme Kata?
どれも基本となる部分は filter で、芸がなくって本当にがっかりだ。いろんなバリエーションを考えるのが Kata 2 の目的な気がするんだけど。なんかもうこう完全にびっくりするぐらい違うのが思いつきたい。