kiyoka.2006_07_23 RSSPLAIN

Related pages: !kiyoka.blog.list !kiyoka.blog.2006_07
555555555555555555555555555555555555
5

[プログラミング] 高速CPUの使い道

5

Paul Grahamのこのエッセーを読んだ時には、次の様な富豪な言語設計は大分先にならないと受入れられないだろうと思っていました。

5

 

5
 The Hundred-Year LanguageEXT
5
 多くのデータ構造は速度のために存在する。例えば、現代の言語の多くは文字
5
 列とリストを持っている。意味的には、文字列は、全ての要素が文字であると
5
 いうリストであって、一般的なリストのサブセットと言える。ならどうして別
5
 のデータタイプが必要なんだろう。実は必要じゃないんだ。文字列は単に効率
5
 のためだけに存在している。けれど、プログラムを速く走らせるハックのため
5
 だけに言語に意味をごてごてと付け足すなんて、スマートじゃない。
5
 言語のコアを公理の集合と考えると、何ら表現能力を増やさない公理を効率の
5
 ためだけに追加するというのは醜いことだ。効率は重要だが、公理を追加する
5
 ことで達成するのは正しいやりかたとは思えない。
5
 正しいやりかたは、プログラムの意味と実装の詳細を分けることだ。リストと
5
 文字列を持つ代わりに、リストだけにしておいて、コンパイラが必要なら文字
5
 列を連続したバイトとして表現できるような最適化のアドバイスを与えられる
5
 ようにしておくんだ。
5
 大抵の、速度が問題じゃないプログラムにおいては、こんな細かいことを気に
5
 する必要はないだろう。コンピュータが速くなればなるほど、そういう場合は
5
 増えてくる。
5
 実装を気にして書く必要が少なくなれば、プログラムはより柔軟になる。プロ
5
 グラムを書いている最中に仕様が変わっても対応できる。これは単に避け難い
5
 というだけでなく、望ましいことだ。
5

 

5

ところが、最近知ったHaskellという言語はPaul Grahamのいう通り文字列型はなく、文字列は文字のリストで表現します。しかも人気の言語になっていきそうです。...

5

(ちなみに最近興味を持っているJOYEXTという言語も同様ですね。)

5

うーん、大量のCPUパワーがあれば人間のブレインパワーの消費を肩代わりしてくれるという感じでしょうか。

5

Gauche等、特定のScheme実装で、文字列を文字のリストとして表現できるんではないかと思ったんですが、Schemeの仕様を守れなくなりそうですね。

5

(list? str) がリストだと言われてしまうと、過去のプログラムが動かなくなりそうです。(string? str)を必ず先に評価していないと破綻するという。

5

そうか、よく考えるとHaskellはコンパイラ言語だから、最適化できるんですね。

5

でも、このままCPUが高速になっていけば、Paul Grahamのいう通りになっていくのかもしれませんね。

5

 

5

 

5

COMMENTshiro

確かに、Schemeにはtype disjointnessの縛りがあるので規格を守ったまま文字列をリストにしてしまうことはできませんね。それと、文字のみからなるリストは文字列風に出力したいところですが、非均質リストを許すSchemeの場合、あるリストが文字のみからなるかどうかは一度最後まで読んでみないとわからないとか、色々面倒なことはあります。

ただ、大文字集合の時代になって「文字列=文字の配列」という最適化が不適切になって来たのは確かなんですよね。Gaucheみたいにマルチバイトで扱うならstring-refはO(n)になってリストと変わりませんし、たとえUCS4の配列にしたってまともにテキスト処理をやろうとするとcomposed characterの問題があるので結局一度は頭からスキャンしないとならない。全てprecomposedされた「文字オブジェクト」の列にするという方法はありますが、文字ってのはその前後との意味的な結び付きが強いので、処理もやっぱり周辺のコンテキストを含めたものが多くなります。そうなると「文字列=リスト」だって決して効率が悪いとは言い切れなくなりますね (さらにテキスト処理には部分文字列の共有が頻出するので、その点でも有利)。

5

COMMENTkiyoka

shiroさん、こんにちは。

なるほど、勉強になります。1文字の持つ意味が大きくなれば、文字のリストという考えかたもそんなに悪くないという事ですね。

Unicode仕様を始めとした現代の文字を扱う仕様もCPUパワーが上がるのを期待した富豪な仕様になっているのですね。

composed characterで重ねた文字も(length str)関数で1文字とカウントしなければならないということを忘れていました。

私は、言語処理系をちょっと試作してみようと思っているのですが、C言語などの低レベルな言語ではやらず、Gaucheなどの上に構築したほうがいいと改めて思いました。

5

...comment disabled...