言語ゲーム

とあるエンジニアが嘘ばかり書く日記

Twitter: @propella
トップ > うまく行かない(と fold について)

うまく行かない(と fold について)

今週はずっと AVM2 アセンブラ abcsx http://github.com/propella/abcsx を他の Scheme に移植するという作業をやっていた。仕事の内容としてはそもそも Scheme で動かす必要すら無いのだけど、私は lisp 系の言語でプログラムを書く経験が乏しいので、色々な Scheme で動くようにするなかでノウハウが溜まるかなと考えた。特に、関数の引き数の順序とか名前の付け方とかはまとまったプログラムを自分で書かないとコツが掴めない。今の所 abcsx は PLT-Scheme と Gauche で動くようになった。あと、他の R6RS の処理系と Scheme48 でも動かしたいなと思うんだけど、なかなか上手く行かない。

まず R6RS について。R6RS ではリスト操作やバイナリ操作など便利な関数が標準になっているので、出来たらそっちを使いたいと思った。PLT-Scheme でも plt-r6rs というコマンドを使うと R6RS 準拠モードで動くのだが、R6RS にした途端ライブラリの仕組みを使わないといけなくなる。ライブラリというのは Haskell のモジュールのようなもんだが、今までフリーダムだった物が急にきっちりしだして、記述量も増えて、別のファイルに書いたソースをただ読みたいという簡単な事が大仕事になるので、面倒になって諦めてしまった。

つぎに Scheme48 について、これもマニュアルを読んでも普通にスクリプトを書く方法が全然わからなくて困った。これもスクリプト実行用の実行ファイルがいくつか用意してあって、特に scheme-srfi-7 というやつはライブラリを読む標準化した方法を提供するまさに欲しい物だったんだけど、そこから Scheme48 独自ライブラリを読む方法が分からなかったり、あと折角だから PLT-Scheme 用も srfi-7 で動かそうと思ったんだけど今度は全く動かなかったり、とにかく挫ける事ばかり。こんな事に時間を費やすと本筋の仕事が進まないので、とりあえず Scheme48 と R6RS は諦める事にした。

あと、Scheme の fold について、こういう事か！と納得したので書く。

Scheme の fold は Haskell ファンから見ると奇妙な引き数の並びをしている。例えば 16 - 8 - 4 - 2 - 1 を計算するのに、Haskell だと

> foldl (-) 16 [8, 4, 2, 1]
1

なのに、PLT-Scheme だと

> (foldl - 16 '(8 4 2 1))
11

こんな変な値になってしまう。実は、PLT-Scheme (と SRFI-1) の foldl は引き数に与える関数の引き数の順序(ややこしい。。。)が逆になっていて。こう書かないといけない。

> (foldl (lambda (a b) (- b a)) 16 '(8 4 2 1))
1

うわ、この糞が！と最初思ったんだけど、実はこの順序には利点があって、reverse が簡単に書ける。

> (foldl cons '() '(8 4 2 1))
(1 2 4 8)

考えてみればこのようにリストを受け取って逆にリストを作りながら何か処理をする(そして最後にまた reverse)というのは Scheme でわりとあちこちで見かける処理なので、これはこれで合理的なのでは無いかという考えに至った。

Haskell は遅延評価をするので、このようにリストを受けながらリストを作るという処理は foldr を使う。右側でリストを作りながら左から出来たリストを取り出せるからだ。しかし Scheme の foldr はスタックを掘り進めてしまうので代わりに foldl を使うと考えれば cons に最適化されている設計に納得が行くのではないか！つまり、fold の設計は言語の評価順序に最適化されている！！かと思ったら Ocaml の順序は Haskell と同じだった。。。

# List.fold_left (-) 16 [8; 4; 2; 1];;
- : int = 1

(追記) R6RS には fold-left というのがあって、これは PLT-Scheme の foldl や SRFI-1 の fold と違って Haskell と同じように動くみたいです。PLT-Scheme で試してみた例。

> (require rnrs/lists-6)
> (require scheme/mpair)
> (fold-left - 16 (list->mlist '(8 4 2 1)))
1

折角なので Squeak でもやってみました。大体 Haskell と同じですが引き数の並びは真逆。リストをレシーバに持ってきます。

#(8 4 2 1) inject: 16 into: [:a :b | a - b]
1

Ruby は Squeak と同じ。

>> [8, 4, 2, 1].inject(16) { |a, b| a - b }
=> 1

Python は初期値とリストが逆というまた変態的なパターン。初期値をオプショナル引き数にしたいからかな。

>>> reduce(lambda a, b: a - b, [8, 4, 2, 1], 16)
1