私は知識に何ものかを付け加え，また他の人々がより多くのものを付け加える手助けをした --- G.H.ハーディ

全記事一覧

<< 2009/06

2009/08 >>

プロフィール

Author:あろは (alohakun)
京都で GCC やデバッガや仮想ハードウェアを開発しているサラリーマン。

本ブログの内容は，あくまでも個人的な感想や意見であり，会社の意見を代表するものでは一切ありません．

連絡先 : alohakun ___at___ gmail.com
mixi : http://mixi.jp/show_friend.pl?id=182927
twitter : http://twitter.com/alohakun

FC2カウンター

無料カウンター

ブロとも申請フォーム

この人とブロともになる

<< プリプロセッサマクロと関数の定義の切り替え｜ホーム｜Obstack >>

shinh さんのところにいろいろ書いた

2007/07/03(火) 15:40:08

ゴルフ紳士の shin-ichiro.h さんにプログラミングの才能が無いんだったら，誰にあるんだと w

http://shinh.skr.jp/m/?date=20070630#c03

まぁ，ようするに，ルールベース型の言語ってのは，人間が手書きするのではなく，自動生成のしやすさを念頭においたパラダイムだということです．その点が，他のプログラミングパラダイムとの根本的な違いですね．例えば，今話題の Haskell とかは，人間のミスをいかにして減らすかというパラダイムだと思います．

# Prolog なんかは，見た目こそルールベースですが，プログラムを作るための理論が全然整備されていません．なので，その理論の空間で何かをやろうとすると，すぐに小手先の拡張が必要になって，どんどん理論が技巧的に捻れていく (それが一見すると，いろいろ研究が進んでいて，高度化しているように見えるのですが．そのほとんどの技巧が，ET パラダイムではそもそも最初から必要の無い前提や拡張だったり)．

また，ET 言語は，表記に S 式を採用したルールベース型言語なので，メタプログラミングでルールを動的に作って，システムに追加したり削除したりしながら，動的にプログラム自身を変更していくとか，そういう人工知能的な高度で柔軟なプログラミングも容易だったりします（もちろん，それが本意では無いのですが）

あと，ルールという形は，わりかし汎用的な形式で，低水準から高水準までを広くカバーする必要がある，プログラムを作るための体系を作ろうと思うと，必然的にこの形に成らざるを得ないんじゃないかなーとさえ思っています．

僕は今，ほとんど機械語みたいに書かれた低レベルの D ルール (メモリの塊 (配列) と数値しか扱わない) を C とか C# とかに変換して実行ファイルにするコンパイラを書いているのですが (これ自体は研究ではなくて，土台を作るための単なる作業)．

そんな低レベルでも，全部末尾再帰 (goto ループになるからスタックなどは消費しない) とパターンマッチ (途中で条件比較にコンパイルされる) で書けるぶん，ルールベースの方が記述力が高いと思います．ルールは塊になってなくても，順番さえ合っていれば，最後には全部合成されて if-then-else の塊にまで落ちるので (ちゃんと順番に依存しないように条件部が書いてあれば，順番すら非依存になる)．

# もちろん，そんなレベルを手書きすることは考えてなくて，もっと上のレベルのルールから様々なプログラム変換でそのレベルまで落とすんですが．計算も，プログラム生成 (メタ計算) も，全ては等価変換の連鎖として統一的に定式化される．

あー，そんな感じかもしれません．どうもありがとうございます．

うちのブログは，こういうことを書くと全くフィードバックが無くなるうえに，僕は自分の研究領域の独特の用語の使い方をしている (のだろうと思う) ので，バックグラウンドが異なる人々と用語の食い違いもたくさんあると思います．

# 例えば，プログラミング言語，とか，コンパイル，とか，基本的な概念さえも，人によって全く想像するものが違うと思うので (なるべく明確にしようとは思ってるのですが，そのせいで毎回毎回ブログの文章が回りクドクなりすぎて，かえってアイデアがダイレクトに伝わらなくなるという悪循環が)

というか，正直僕自身もあまり明確にわからないで行き当たりばったり書いてるので (駄目) いろいろその場の気分で不整合があるかもしれません．

まぁ，そもそも自分自身がやりたいこと，やるべきことをわかるようになるために研究しているわけですし，ブログってのは自分自身のアイデアの整理のために書いてるので．

テキトーに，僕の書いた文章から，何かを汲み取っていただけたならば幸いです．

文章に，真意も誤解も無いです．その人が得た内容が全てであり，人は結局の所，自分が読みたいようにしか文章を読むことができません．自分自身がやりたいことさえわからないのに，他人がやりたいことなど，そもそもわかるわけがない．

ふたたびコメントしたので，追記

http://shinh.skr.jp/m/?date=20070707#p03

ここの syd_syd さんに同意だな。

結局皆さんが気にしてるのは～からどの辺が「筋が良い」のか？

のあたり。

何がしたいか、っていう What はたぶんそれなりに想像がつくというか割とプログラム書きの妄想の一つだと思うんだけど、 How がよくわからないという。

という質問に対して返答が基本的にふたたび What なのでよくわからなくなるんだな。「できたプログラムの正しさが全て保証されるという点がブレイクスルーです」とかそいう。で How を知りたければ論文読むしか無いらしいのだけど、それは残念なことで僕は文章読んでもコード書かないとさっぱりわからない人間らしいので。

(01:56)
本日のツッコミ(全1件) [ツッコミを入れる]
_ あろは (2007-07-07 08:02)

ようするに，僕もそっちにはそれほど深く関わってないのでよくわからない，という．要領を得ない解答しかできなくてすいません．

# 僕も，理論屋では無く，手を動かす方が好きなタイプなので．いつまでもそれではいかんのですが… 数学は難しいです (そもそも英語すらあまり読めないという．優秀な皆様がうらやましい)．

論文を読んだのがだいぶ昔なのでいろいろ抜けてますけど，確定節からルールを作る際，その正しさが保証されることにより，かなり大きな可能性が広がるというのを実感して衝撃を受けた記憶があります．

一見大したことないように見えるかもしれませんが，他のパラダイムだと，(自動探索，あるいは人間のひらめきにより) 「一個一個ルールを作っていく」という時点で，正しさの保証が困難だと思います．

あと，まだ抽象的な論文しか無いというのも悪いんでしょうね．具体的なツールが何かあれば良いのですが，まだまだそこまでは，なかなか．

問題の背景知識を確定節 (論理式の一種) で書いておいて，解きたい問題 (クエリ) の具体例を与える．そして，問題の具体例を簡単化できるルールを確定説から抽出していくことにより，正しさが保証されたプログラム (ルール) を段階的に蓄積していくことができるというのが，その本筋だったと思います．

論理式 = 面倒で冗長，プログラム書いた方が早い，という偏見があるようですが，僕は論理式よりも表現力が豊かな表記法を他に知りません．

表現力だけだったら，Haskell なども同じくらいリッチなのかもしれませんが．関数型の方面には，「どう書けるか」ばかりで，「どう作るか」という理論的なサポートが欠けていると感じます．

っと，また抽象論になってしまいましたね．すいません．

メモ｜TB：0｜CM：6｜

▲

えー
どこにコメントしようか迷ったんですが(soutaroさんとことか)、こちらで。
D/Nルールですが、なんとなくOzの制約論理プログラミングに似ていると思いました。(もちろん、Ozには等価変換というパラダイムはないのですが)
http://www.info.ucl.ac.be/people/PVR/tutFinal.pdf
世の中には2種類の問題があって、一つは(1)algorithmic problemで、解くためのアルゴリズムが知られている問題。Ozでは関数的に記述する。もうひとつは(2)search problemで、解のためのアルゴリズムがないのだけど、宣言的に問題を記述して、制約伝播(propagator)により解空間を探索する。propagatorは問題毎に定義する必要があって、組み込みのpropagatorを使わない場合は自前のそれをC++で書かなきゃいけないとの事です。

あと、仕様からのプログラム自動生成は、やはりTRSや形式的仕様記述の文脈で色々と語られている気がします。関連研究はそのへんなんでしょうか。問題領域を限定しないと、至る所で決定不能になるというのは私もそう思います。さくっと日本語でググって見ただけですが、
http://jstore.jst.go.jp/cgi-bin/research/advanced/detail.cgi?data_id=2771
とか、形式的仕様からのプログラムの自動生成という文脈で探せば色々と見つかります。ただ、こちらは宣言的プログラミングという感じではなく、もろに自動生成という感じなのですが。

私は耳学問程度にしか知らない分野なので、外していたら申し訳ないのですが、例えば(1)自動生成には色々とテクニカルな困難が付きまとったりしますが、そのへんをどうやって乗り越えるのかなーとか、(2)宣言的な仕様記述と宣言的なプログラムの差異はどのへんにあるのかなとか(たとえばHaskellの純粋関数的な部分は仕様記述言語と言えなくもないですし、CafeOBJには等式を書き換えルールと見なした「仕様実行」の機能がありますし)、そういう所がクリアになればもう少し理解できる気がします。
長々とすみません。

syd_syd(Keigo IMAI) #cgf6TkE.｜2007/07/04(水) 01:39 [ 編集 ]

> syd_syd さん
宣言的な仕様記述と宣言的なプログラムは，もちろんそこだけを見たらほとんど同じ物になりますよ．目的は同じなのですから．

ただ，Haskell とかは「こう書いたらこういう意味論で動きますよ」ということしか言っていない．なので，宣言的な記述だけでは，それ以上そのレベルから (制御，データ構造を) チューニングする手段がありません．できるのは，せいぜい，処理系にハードコードできる程度の汎用の最適化のみでしょう．

だから，論文のサンプルコード程度ならともかく，まともなプログラムを書こうとすると，結局最後は，手続き的にコードを捻じ曲げて，コンパイラが最適化しやすい形に人間が合わせてプログラムを書かないと駄目になる．

Prolog も，建前は確定節の集合を定義するだけで動く，ということになってますが，あれは結局，仕様のレベルにもかかわらずカットを入れまくって不自然なチューニング (カットというのは，要するに，抽象的な定義を決定的に動作するルールに読み変えるための小細工です) を施さないとまともに動きません．なので，仕様とプログラムという根本的に異なるものを混ぜている時点で，どこから間違えを指摘したら良いのかわからないほど何もかも間違っているのです．

それに対して，ET パラダイムは，仕様とプログラムの間の「関係」をクリアにすることを目的にしています．なので，仕様のレベルでのプログラム変換よりも，はるかに広範な範囲の最適化を扱えます．よって，(2) の答えは「パラダイムが違う」ということに．

制約論理プログラミングは，結局問題領域ごとにいろいろなソルバーを持つ言語が林立した果てに発展が停滞し，もうかなり廃れていて，一応現在の最先端は，CHR (Constraint Handling Rules) という，名前からしてそうですが，極めて ET の N ルールに似たプログラミング言語になっていいるようです．マルチヘッドを許し，制約ソルバーをユーザ定義できるなど．

そして，ET ルールは CLP や CHR よりも，さらに広い空間を扱えることが，形式的に証明されているそうです (私は目を通してないですが).

「 Converting Constraint Handling Rules to Equivalent Transformation Rules 」
http://www.fujipress.jp/finder/xslt.php?mode=present&inputfile=JACII001000030012.xml

部分部分を見たら，既存の研究でもやられていることも多いです．みんなやりたいことは同じなのですから．ただ，「こうやれば～ができる」という後追いの類の研究は，なかなか後々の発展に繋がらず，どんどんマニアックな蛸壺化していく傾向があると思います Logic Programming しかり，関数型しかり(もちろん，成熟しているぶん，論文は書き易いのですが．まぁ，私はどっちも詳しくは知らないのですが，知らなくても同じことがよりエレガントにできるならば，そっちのほうが良いですよね)

よって (1) は，従来は困難であったテクニカルな問題のうち，ET パラダイムの筋が良いために容易に解決できるクラスが存在すれば，それだけでも素晴らしい (本質的にどうしようも無い問題も多いと思います) 従来 (理論的に) 困難であった問題の多くは，そのパラダイムが扱う範囲と目的の本質的な狭さであることが多いと思います．

というか，私はまだまだペーペーも良い所で，英語すらろくに読めないような子なので，あまり信用しないでくださいね (汗)

あろは #wNX6xxGw｜2007/07/04(水) 03:31 [ 編集 ]

なるほど
なるほど、ちょっと分かるようになりました。わざわざすみません。論文は…さすがに購入できないので機会があればどこか探してみます。

＞できるのは，せいぜい，処理系にハードコードできる程度の汎用の最適化のみでしょう．
つプログラム運算
http://www.kmonos.net/wlog/71.html#_1953070310
とか。それこそ、宣言的でより仕様に近い関数型プログラムを、実行効率が良い関数型プログラムに「等価変換」しようという研究は沢山あると思います。関数型は並列化しやすいですし、GoogleのMapReduceなんかも近いのでは。論理型は分かりませんが、関数型については、まだまだ発展の余地があるんではないかなと。私の専門ではないですが、マニアックな蛸壺は言い過ぎな気がします。
# Prologはほとんど書いた事がないので分からないですが

ETの「等価変換」が、いかなる意味論の枠で「等価」なのか、というのも気になる点ではあります。操作的意味論で仕様と実装にsimulationがあるとか、そういうのがあるのでしょうか。公理的意味論とかPrologの意味論はよく知らない(エルブランモデルがどうとか..)ので、これも外しているかもしれませんが。

＞従来 (理論的に) 困難であった問題の多くは，そのパラダイムが扱う範囲と目的の本質的な狭さであることが多いと思います．
パラダイムの扱う範囲が広いのは結構なことだと思いますが、直観的には、問題領域が狭いほうが、最適化が容易で実現可能性がより高いように思えます。どうですかね。ETは、何らか(計算可能性というか…)の意味で、より自動生成しやすい枠組みになっているのかなと想像します。CHRよりもクラスが広いというのはスゴいと思います。

CHRは、Haskellのmulti-parameter型クラスのfunctional dependencyの意味論として使われているそうです。気になってはいたのですが、ちゃんと知りたくなってきました。

syd_syd(Keigo IMAI) #cgf6TkE.｜2007/07/04(水) 08:00 [ 編集 ]

> syd_syd さん
運算含めて，宣言的プログラムの空間に限定された最適化には限界がある，という話でした．

問題領域が狭いならば最適化がしやすいというのは，仕様記述手法のレイヤーの話になるので，またちょっとズレた話だと思います．

関数型言語が (関数型言語だから) 並列化しやすいというのも，ちょっと観点がズレた話で．そういう後付けの優位性を探すのも良いのですが，最初から並列化しやすいような形の仕様記述手法を設計するほうが筋が良いのかなと (そして，仕様とプログラムを分離することにより，仕様記述の表現力を純粋に追及することができる)

そういう諸々を含めたアプローチの方向性自体が根本的に異なるので．一つ一つの優位性自体は，本質では無いと思います．「～でも～はできる」論で議論を進められても，すれ違うばかりかと．そういう類の議論を蛸壺と言ったのは，確かに言いすぎだったかもしれませんが．

一般的には，扱えるプログラム空間が広い方が，理論をはみ出さずに可能な最適化の幅が広がるので証明などが有利 (楽，自然) になります．Haskell の，純関数プログラムの空間というのは，極めて限定されたものだと私には思えます．遅延評価の意味論だと，末尾再帰の最適化すら正当化できませんから．

遅延評価が重要なのではなくて，副作用を排除して，プログラムを宣言的にすることが本来やりたかったことのはずなのに．仕様とプログラムが区別されていないので，両方が歪むというのが宣言的プログラムのパラダイムがおかした根本的な間違いだと思います．そして，いくら Haskell のプログラムをこねくり回したところで，必ず速度に限界が生じます (全く同じアルゴリズムを，同じ抽象度で記述したケースでさえ)．

ET の等価変換の定義は，エルブランの意味論の一般化になっています．また，特殊化システムという枠組みにより，LP のように，論理式にデータ構造が限定もされていません．

論文は

ttp://assam.cims.hokudai.ac.jp/akama/indexj.html

の

「Formalization of the Equivalent Transformation Computation Model」
ttp://assam.cims.hokudai.ac.jp/akama/j/papers/0605.pdf

あたりに，意味論の定義が載っています．私程度の理解度で何を言ったところで，誤解が広がるだけなので，このへんで (^-^;

あろは #wNX6xxGw｜2007/07/04(水) 18:19 [ 編集 ]

いや
どうも、手仕舞いにしたい所ひっぱって申し訳ないのですが、指摘したい所だけ書いてしまいます。

うーん、結局皆さんが気にしているのは、「既存の枠組みで解けない(たとえば仕様からプログラム自動生成など)問題を、ETで解けるのなら、どのへんにブレイクスルーがあるのか？」という事だと思います。ある問題が決定不能というのは、「停止するアルゴリズムが存在しない」という事だったと思います。例えば「λ計算の停止性は決定不能ですが、型付けできる部分クラスについてはただちに明らか」など、何らか(例えば型理論とか)のテクニックで、従来解けなかった問題(停止性)を解けるようにしているのなら、ETのテクニックは何か？というのが知りたくなると思います。

これに対して、あろはさんは
＞従来は困難であったテクニカルな問題のうち，ET パラダイムの筋が良いために容易に解決できるクラスが存在すれば，それだけでも素晴らしい
と答えました。まだ大した自動生成や最適化は実現していないという事だと思いますが、でもETなる言語の実装は既に存在する。しかし、ETのどの辺の「筋が良い」というのが、いまいち誰にも掴めていないのではないでしょうか。「Prologにしか見えない」、とか「TRSにしか見えない」、というのは、ET で筋の良いという点が全く実感できない、という事を言っているのだと思います。

あと、少し前の話ですが、「パラダイムが違う」でぶった切ってしまうのはよろしくないというか、何の説明にもなっていないと思います。まあブログで説明しろというのが無理なのかもしれませんが、そういう言葉で逃げを打つのはよろしくない。計算機科学の根本は、計算可能性の理論だと思うのですが、その文脈ですべての手法の有利な点を継承して比較検討してお互いに高めあっていくのでなければ、それは科学とは言えないと思います。なんて、えらそうな事をいって、私は決定問題がどうというのは全然知らないんですが。

工学の分野で適当な手法がもてはやされると、私の先生は、「アルゴリズムはあるの？」と質問するのが常道ですが、これに当てはめると、ETで仕様からプログラムを自動生成できるというのなら、そのアルゴリズムの指針くらいはあるのでしょうね？ということが聞きたかったのです。ある手法とかパラダイムの筋の良さというのはそういう事だと思います。

＞「～でも～はできる」論で議論を進められても，すれ違うばかりかと．
や、CafeOBJやHaskellを持ち出したのは、「これと比べてどう違うの？どこがブレイクスルーなの？」ということが聞きたかっただけで、別にETを貶めたいわけではありません。あと蛸壺はまずいんじゃないかと思ったんですが、これは訂正されてますね。

＞一般的には，扱えるプログラム空間が広い方が，
というくだりは…特にHaskellについては誤解が多いと思うのですがこれはまた。

論文へのポインタをありがとうございました。どこまで理解できるかわかりませんが、目を通してます。

syd_syd #cgf6TkE.｜2007/07/04(水) 21:20 [ 編集 ]

> syd_syd さん
いや～，逃げを打つと言うか，単にそういう上のレベルは，私がかかわっている部分では無いから，よく知らない (私は，もっともっとずっと下のレベルの，コード生成の正当性の証明とか，そこらへんをやっているので) & 誤解を広めるくらいなら何も書かないほうが良い & どこまでブログに書いて良いのかわからないから，どうしてもかなり昔の話題 (もう既に論文がパブリッシュ済み) に限定して話さざるを得ない (から，歯に衣着せたような言い方にどうしてもなってしまう)，というだけのことで (あと，おっしゃる通り，ブログだけでちゃんと説明するのは厳しいです．さわりだけ説明して，後は論文を読んでいただくしか今の所はありません．それが一番正確ですし，実は一番わかりやすいと思います．私のようなペーペーの要領を得ない戯言を百万回聞くよりも，偉大な研究者の生の言葉なのですから．私は大まかな概念や目的だけをブログには書いていいるつもりです)．

>> どうも、手仕舞いにしたい所ひっぱって申し訳ないのですが、指摘したい所だけ書いてしまいます。

いえいえ，興味を持っていただけただけで，ブログに何度も何度も同じようなことをしつこく書いてきたかいがあったというものです．大変ありがたいことだと思います．

メタ計算によるプログラムの自動生成や最適化の方の理論は，かなり確立されているはず．とりあえず，私が目を通したことがあるのは…

http://www.fujipress.jp/finder/xslt.php?mode=present&inputfile=JACII001100050006.xml
http://citeseer.ist.psu.edu/akama01class.html (こっちは PDF で論文取れます．かなり古いですが)

そして，ET パラダイムは，ルール一つ一つに対して仕様に対するプログラムの正当性を検証可能なので，例えば「搾り出し方 (squeeze method)」のような人間のヒューリスティックに頼る生成方法を取ったとしても，できたプログラムの正しさが全て保証されるという点がブレイクスルーです(それだけではありませんが)

あと，ET パラダイムが目指すのは，計算可能性の一つ上に，プログラムを作るための理論の階層を作ることです．従来のパラダイムは，「どう書けば，どう動くか」でしたが，ET パラダイムは「どう書いて，どうやって作るか」なので．

フェアじゃない云々言われましても，本当に方向性自体が違うので．もちろん，Haskell などでも，同じような目的の研究はたくさんありますけど．ET パラダイムは，最初から目標を明示して作られているという点 (目的をクリアにした点) が新しいところだと思います．つまり，言われて見れば当たり前すぎるコロンブスの卵なのに，そこを明確にして理論体系を作っただけで，こんなに大きな世界が広がるのだ，という視点が得られる点が面白いところだと思います (従来のパラダイムの発想に縛られていると「そんなの～と同じじゃないの」「～を使っても同じことができるよ」という反応をされがちなのですが．もし，私のような駄目院生の話に，何か面白い発想の輝きが見られるのだとしたら，それは私が優秀なのでは全然無くて，それが ET パラダイム (と，うちのボス) から得られた新しい視点，理論から得られる新しい知見の力なのだと思います)．

と，また身の無い抽象論ばかりと言われてしまいそうな感じになってしまいましたが．それは ET パラダイムが空理空論だからではなく，単に私が身のある話をできるくらい深く理解していないというだけのことです．

まだ ET パラダイムは 10 年ぐらいの新しいものなので．どのパラダイムが発展し，どれが停滞するのか．その真価が問われてくるのはこれからでしょうね．関数型などは，もう 30 ～ 40 年の歴史があるのですから．

あろは #wNX6xxGw｜2007/07/04(水) 23:59 [ 編集 ]

コメントの投稿

トラックバック

トラックバックURLはこちら
http://alohakun.blog7.fc2.com/tb.php/776-025c1f62