Scheme:初心者の質問箱

メーリングリストで質問したり、WiLiKiに自分のページを作ったりするのはちょっと… というシャイなあなたのためのスペースです。

あたらしい質問は、項目の先頭に追加していって下さい。

書き方を間違えても小人さんが直してくれるので、こわがらなくてもだいじょうぶ。

長くなってきたので過去ログ:

write の出力のカスタマイズ

osn(2010/05/27 22:16:11 PDT): 実数の write での出力では、桁数に応じて固定小数点表記あるいは浮動小数点表記とが切り替わります。

gosh> (write 1.0)
1.0
gosh> (write 10000000.0)
10000000.0
gosh> (write 100000000000.0)
1.0e11

この表記の切り替わりの桁数や浮動小数点表記内容をカスタマイズできないでしょうか。write-object でできないかと思い、以下のようなことをやってみたのですが、効果ありませんでした。

gosh> (define-method write-object ((obj <real>) out) (format out "~a*1000" (/ obj 1000)))
#<generic write-object (3)>
gosh> (write 3e3)
3000.0   (3*1000 と表示されることを期待)

他処理系で生成されたS式のファイルを gauche で読み込んで write とすると数の表記が変わってしまい、できれば元の処理系と同じ規則を定義して出力したいと思っています。よろしくお願いします。

齊藤(2010/05/28 00:24:07 PDT): write に直接メソッドをかぶせれば一応そのような動作をさせることは出来るようです。
```
(define-method write ((obj <real>) . rest)
  (let-optionals* rest
      ((out (standard-output-port)))
    (format out "~d*1000" (inexact->exact (/ obj 1000)))))
```
```
gosh> (write 3e3)
3*1000
```
でも、 Scheme では write して read したら同じものになるのが基本なので、こういうカスタマイズはスジが悪い方法かも。別の名前で専用の関数 (メソッド) を用意した方が無難に思えます。

Shiro(2010/05/28 00:53:18 PDT): write-objectはプリミティブ型には効果を及ぼしません。原則としてユーザレベルで追加したクラスに対するもの、という位置づけです。 write-objectによるプリミティブ型の表示の変更を許すと、性能上の問題と、メソッドオーバロードによる変更は効果がグローバルに出るために制御しにくいという問題が出ます。
また、齊藤さんの方式は他の構造体中にある浮動小数点数には影響を及ぼしません。 writeは内部的に組み込みのScm_Writeを直接呼んでいるので。
したがって、現在のGaucheでは、(1)write相当の手続きを再実装するか (2)一度構造をwalkして浮動小数点数を<my-flonum>などのオブジェクトに置き換えて、それに対するwrite-objectメソッドを定義しておくか、になると思います。
将来的には、何らかのパラメータで制御できるようにするアイディアはあります。既に現場での需要として、IEEE 754形式のバイナリを16進表記で読み書きする、というものがあるので (そうすると高価な2進-10進変換が避けられる。大量のflonumデータを読み書きする際に有利)。
なお、<real>は正確な整数や有理数も含むクラスなので、<real>にスペシャライズするのは多分やりたいことと違うと思います。本来は、抽象型<real>を継承した<flonum>のような型であるべきなんですね (cf. Gauche:NumericTower)。

osn(2010/05/28 01:26:48 PDT):齊藤さん、Shiro さん、ありがとうございました。私の不正確な表記から汲み取っていただいて Shiro さんが解説いただいた内容で納得しました。（実数、と安易に書いたりしてましたが、整数も実数なわけで、小数点部を持つ実数、と書くべきでした。）50MbytesのS式のファイルを処理しようとして、処理結果の確認をする際にちょっとひっかかってご相談させていただきました。幸い、gauche の write の出力を問題の他処理系でも問題なく読み込め、実用上は問題とはならなそうです。ありがとうございました。

gauche/gdbm on openSUSE 11.x

osn(2010/04/14 20:15:08 PDT): (便乗したようなタイトルですいません。;） openSUSE 11.1,11.2(gcc-4.4.1) に Gauche-0.8.14,0.9 をインストールしようとしたところ、./configure の結果では、

  optional modules: odbm ndbm gdbm zlib

となっているのに、コンパイル終了時点で、lib/dbm には fsdbm.scm のみしかなく、gdbm インターフェースが生成されないようです。 config.log をみると

configure:11795: checking for dbm_open
configure:11851: gcc -std=gnu99 -o conftest -g -O2     conftest.c -ldl -lcrypt -
lutil -lm  -lpthread >&5
/tmp/ccEbKcoc.o: In function `main':
/root/Gauche-0.9/conftest.c:135: undefined reference to `dbm_open'
...
configure:12871: checking for dbminit in -ldbm
configure:12906: gcc -std=gnu99 -o conftest -g -O2     conftest.c -ldbm  -ldl -l
crypt -lutil -lm  -lpthread >&5
/usr/lib64/gcc/x86_64-suse-linux/4.4/../../../../x86_64-suse-linux/bin/ld: canno
t find -ldbm
collect2: ld returned 1 exit status
...

等が見られるので、dbm インターフェースに関連して、gauche のコンパイルに失敗しているのかも、と想像しているのですが、対策が分からず困ってます。openSUSE 10.x (gcc-4.1.0)等では問題なくインストールできているのですが、、、対応方法をご教示いただけるとありがたくよろしくお願いします。（gdbm は 1.8.3 で、gauche のインストール可否にかかわらず同バージョンです。）

Shiro(2010/04/14 20:25:49 PDT): ndbm, odbmについてはconfigure内で本来のライブラリと gdbmエミュレーションを順次チェックするので、一方がfailしていること自体は問題ではないです。ext/dbm以下のmake時のメッセージはどのようになっていますか。

osn(2010/04/14 20:46:28 PDT):エラーメッセージが出ていました。確認不足ですいません。といっても対応方法はわからないのですけれど。^^;;

make[2]: Entering directory `/root/Gauche-0.9/ext/dbm'
../../src/gosh -ftest ../../src/precomp -e -o dbm--odbm odbm.scm
gcc -std=gnu99 -DHAVE_CONFIG_H -I. -I../../src -I../../gc/include    -g -O2 -fPI
C  -fomit-frame-pointer  -c dbm--odbm.c
odbm.scm: In function 'dbm__odbmodbm_close':
odbm.scm:212: error: too few arguments to function 'dbmclose'
make[2]: *** [dbm--odbm.o] Error 1
make[2]: Leaving directory `/root/Gauche-0.9/ext/dbm'

Shiro(2010/04/14 23:07:30 PDT): あれ? dbm互換のヘッダじゃない何かが見えているのかな? ext/dbm/dbmconfig.hを見て、
- HAVE_DBM_H が #defineされてたら dbm.h
- HAVE_GDBM_SLASH_DBM_H が #define されてたら gdbm/dbm.h
- HAVE_GDBM_MINUS_DBM_H が #define されてたら gdbm-dbm.h
をシステムのincludeディレクトリから探してください。
見つかったら、その中のdbmcloseの定義を見てみてください。
Ubuntuの場合、HAVE_DBM_Hが#defineされ、システムのヘッダは /usr/include/dbm.hにあり、dbmcloseの定義は extern int dbmclose() となっています。
もしdbmcloseの定義が違っていたら、legacy dbm互換でない別のライブラリが入っててそれと衝突していることになります。

osn(2010/04/15 00:18:06 PDT): コメントありがとうございます。
- #define HAVE_DBM_H 1　でした。
- /usr/include/dbm.h を見たところ、
```
/* Determine if the C(++) compiler requires complete function prototype  */
#ifndef __P
#if defined(__STDC__) || defined(__cplusplus) || defined(c_plusplus)
#define __P(x) x
#else
#define __P(x) ()
#endif
#endif
...
extern int      dbmclose __P((DBM *));
```
  となってました。#define __P(x) x が有効になって、dbmclose の引数の数があわない、ということになってるということですね。
- プリプロセッサの実際の動作等、分かってないんですが、#define __P(x) () をこの前にどこかで定義してやればいいんでしょうか。
- なお、openSUSE 10.x(問題なかったもの）では、単に extern int dbmclose (); となってました。

osn(2010/04/15 01:07:50 PDT): 追加情報です。
- /usr/include/dbm.h に#define __P(x) () を挿入して Gauche のコンパイルをしてみましたら、一応、OK となったっぽいです。
- このマクロ(__P)は、suse のパッケージ化の際に加えられたもののようです。 http://lists.opensuse.org/opensuse-commit/2008-02/msg01086.html
- どう対処するのが妥当なのか、ご意見お願いします。

Shiro(2010/04/15 02:04:12 PDT): オリジナルのdbm APIでもgdbm 1.8.3の互換APIでも dbmclose()は引数を取らないので、そもそも__P((DBM *))というのがおかしいです。プロトタイプが必要なら__P((void))となっていなければならないはず。なので、OpenSUSEがパッケージ化の際にエンバグしたか、あるいはlegacy dbm互換を捨てた (そもそもdbm互換レイヤが古いプログラム対応のためなので、いまさらそこに非互換性を持ち込む意味はないと思うのですが)ってことだと思います。で、"opensuse dbmclose"でぐぐるとPerlのdbmパッケージでやっぱりビルドエラーが出てるんですが、なんとopensuseのPerlパッケージは非互換なdbmcloseに合わせてperlの方にパッチをあててしまっているようです。 http://lists.opensuse.org/opensuse-commit/2008-03/msg00374.html
(他には、「ODBMのサポートを外してコンパイルしたら?」というようなアドバイスが目立ちます)。
コミットから2年も経ってて誰も指摘してないってのが不思議なんですが、今時legacy dbmを使ってるアプリってまず無いので問題が出てないのかなあ。でもこれはOpenSUSEのdbmパッケージがfixすべき問題です。
Gaucheとしての対応ですが、現代においてlegacy dbmだけしかない環境っておそらく皆無なので、いっそlegacy dbmのサポートを落としてしまうっていうのもありかも。(Schemeのdbm.odbmはそのままで、Gaucheのルーチンの方で ndbmかgdbmを呼ぶってのでもいい。)
osnさんの手元でさえ動けば良いのなら、こうしてみてください。
```
--- odbm.scm    (revision 7085)
+++ odbm.scm    (working copy)
@@ -207,7 +207,7 @@
      (result r)))
 
  (define-cproc odbm-close () ::<void>
-   (when odbm_opened (dbmclose) (set! odbm_opened FALSE)))
+   (when odbm_opened (dbmclose NULL) (set! odbm_opened FALSE)))
 
  (define-cproc odbm-closed? () ::<boolean>
    (result (not odbm_opened)))
```

osn(2010/04/15 05:28:04 PDT): 上記修正でのコンパイル＆動作OKを確認しました。気をつけて利用していきたいと思います。ありがとうございました。
- 私も、2年前からあった問題のはずなのに、、と、ちょっと悩ましく思っておりました。openSUSE はそれなりにユーザーも多いつもりで使ってきていたので、ちょっとショック。
- 自分では、wiliki等、たまたま、FreeBSD や他ディストリでしか運用していなかったので、openSUSE 11.x の gauche インストールの際、 dbm インターフェースの構築に失敗していたことに気づいてませんでした。それが、最近、近くの者がopenSUSE 11.1 で wiliki を動かそうとしてうまくいかない、と相談してきたのでした。

gauche-gdbm on FreeBSD 8.0

suzuki@cis.iwate-u.ac.jp (2010/03/21)

WiLiKi のデータベースに gdbm を使っています。 FreeBSD 8.0 で，portupgrade databases/gauche-gdbm に失敗します。 0.9 がBROKENになっているためです。試しに，Makefile 中の　BROKEN をコメントにして make してみると， gdbm.stub がないと怒られます。 0.8.13 のgdbm.stub をコピーしてmakeすると，実行時エラーになります。

gdbm を使うのはおすすめではないのでしょうか？

対処方法とおすすめのデータベース形式を教えていただけませんか？

Shiro(2010/03/20 17:12:51 PDT): FreeBSDで何故BROKENになっているのかが分からないので何とも。Gauche本家としてはgdbmは今までどおりサポートしており、非推奨ということはありません。
0.8.xと0.9の間にext/dbmのソース構成が変わっているので、古いバージョンのソースは使えません。Gauche本体は0.9なんですよね?
とりあえず使うならGauche-0.9のソースからコンパイルしてみては。
ちゃんと直すならBROKENの理由を調べることから、ですかね。

osn(2010/03/20 19:05:52 PDT) FreeBSD 7-stable ですが、やはり BROKEN で往生したので、ソースから素朴にインストールして問題なく使えています。WiLiKi が半日でも使えないと苦情が来ますもので。御参考まで。

suzuki (2010/03/21 16:30 jst) Gauche-0.9 のソースからコンパイルしてみます。
BROKENの理由を調べようとしていますが，行き詰まって，相談しました。
ありがとうございました。

suzuki (2010/03/22 14:40 jst) Gauche-0.9 のソースからインストールしました。FreeBSD 8.0-Release です。下記二ヶ所で悩みました。

configure のオプションで gdbm を有効にする方法が分からなかったので
ext/dbm/dbmconfig.h.in を修正して HAVE_GDBM_H を define しました。
'--with-local=/usr/local' を指定。しないと libgdbm.so がリンクされなくなり，実行時にgdbm_errno が undef になりました。

suzuki (2010/03/22 14:40 jst) FreeBSD の gauche-gdbm-0.9が BROKEN状態になっていて、Mark BROKEN with 0.9 updateと記載されています。Makefile は 0.8.13 のものと同じで，ソースディレクトリは，Gauche-0.9/ext/dbm をさしています。
0.9 にまだ対応していないものと思いましたが。。。

Shiro(2010/03/21 23:00:35 PDT): ちょっと謎です。
- gdbmは明示的に有効にしなくても、configure時にライブラリが見つかれば自動的に有効になります。従って/usr/local/{include,lib} にgdbmがインストールされているなら、 ./configure --with-local=/usr/local とするだけで良いはず。手動でconfig.hなどをいじる必要はありません。

suzuki (2010/03/22 17:10 jst): ご指摘のとおりでした。gauche-gdbm が別ポートになっているので，何か指定をしないといけないと思いんでました。すっきりしました。

portsの方ですが、元々のext/dbm/Makefileなどはコアに含まれてリリース毎にアップデートされるので、同じMakefileになっているというのはおかしいですね。もしかするとBSD部分とGPL部分とを分けるために、手動でgdbmに依存するコードだけ分離しているのかな? だとしたらリリース毎にその作業が必要で、0.9についてはそれをやっていないってだけかもしれません。

文字列上の繰り返しと部分文字列

ziro (2010/03/19 00:53:38 PDT) 勉強のためにいろんな文字列のアルゴリズムを Gauche で書いています．文字列の各文字を順番に見るときには，マルチバイト文字列上でのインデックスによるアクセスは遅いので，string port を使ったほうがいいんですよね．そうして文字列を舐めている途中の二つの状態の間に対応する部分文字列を取得する方法はありますか？今は port から読んだ文字を別の string port に書いているのですが，どうにも格好がつきません．

Shiro(2010/03/19 04:43:06 PDT): 「遅い」といっても程度の問題で、データのサイズや必要な性能要件によって変わってきます。インデックスアクセスは入力文字列長に比例するので、特に問題になるのは「長い文字列に対して頻繁にインデックスアクセスする」という場合です。

従って、(dotimes (n len) (do-something (string-ref str n))) のようなコードは O(N^2)になってしまいますが、もし取得する部分文字列の総数が定数ならば、

文字列を舐めるのにはstring portを使い、マッチした文字インデックスを覚えておく
部分文字列を取り出すのはsubstringで行う

でもいけるかもしれません。

入力文字列が巨大で、substringで深くインデックスするのを避けたいという場合は、部分文字列の先頭になり得る箇所で、get-remaining-input-stringで半部分文字列 (その箇所以降の文字列)を取得しておく、という手もあります。Gaucheでは文字列本体は共有されるので、get-remaining-input-stringが返す文字列は事実上入力文字列の途中を指すポインタみたいなもので、たくさん取得しておいてもさほど性能に影響は出ません。さらにマッチングを進めて、切り取るべき文字列の終端が分かったら、get-remaining-input-stringで取った文字列partial-strに対して (substring partial-str 0 (- end-index start-index)) のようにして切り取ります。 string-takeでもいいです。この場合、文字列のインデックスアクセスのオーバヘッドは部分文字列の長さに制限され、入力文字列の大きさには影響を受けません。

気になるのがどちらかというと性能よりもコードの簡潔さ、読みやすさだというのなら、切り取る部分は文字のリストにしといて後でlist->stringするのがたぶんエレガントになると思います。オーバヘッドはありますがO(N)なのでこれでもstring-refで舐めるよりはずっと良いと思います。

ziro (2010/03/19 07:26:51 PDT) ありがとうございます．安直には，バイト数ベースの添字で substring ができると簡単だと思いますが，そんなことはできないのでしょうか (incomplete string を使えばできる？)．それから，文字列の途中から逆向きに辿ってみたいと思うのですが，添字を使わないですます方法はありますか？

Shiro(2010/03/19 12:47:08 PDT): これ以上は目的がわからないと何とも言えないのですが、かなり性能的にシビアな状況なのでしょうか。

substringをincomplete stringに適用すれば(今のところ)バイトインデックスとして扱われますが、文字インデックスからバイトインデックスを簡単に求める方法が無いので使いどころが難しいですね。string-portで読み出しつつport-tellでオフセットを記録するって手はあります (ただし、peek-charするとオフセットがずれるというバグがあるので注意)。

とにかく今、性能が欲しいということでしたら、unofficialなstring-pointerというのがあるにはあります。途中から逆向きということができます。ただし将来無くなるかもしれません。

あとは、アルゴリズム的にインデックスアクセスが綺麗に書ける、ということならいっそベクタに変換してしまうとか。綺麗さにこだわるなら読んだ文字を全部リストにしとくとか、文字列から離れる手もあります。

ziro (2010/03/20 05:24:03 PDT) 私の状況は要件が厳しいというものではなく，毎回再計算が起こるから string-ref は軽い気持ちでは使い難いという程度のものです．紹介して下さった方法の一で書いて実際の文字列に適用してみて，様子を見たいと思います．まともに可変バイト長の文字エンコーディングを扱えるのはとても有り難いことなので，うまく Gauche を使えたらと思います．ありがとうございました．

Shiro(2010/03/20 07:15:28 PDT): それなら、とりあえず

読み出しはstring-portから。文字数を数えておく。
部分文字列の取得は数えておいた文字数を使ってsubstringで。
途中から逆向きに探す可能性があるのなら、既に読んだ文字列をリストにconsしてゆき、そのリストから探すようにする。

というのが、多分シンプルさと性能のバランスのいいところじゃないかと思います。それで問題が出てきたら上に挙げた他の方法を試すということで。

Last modified : 2010/05/28 01:29:57 PDT