芋出し画像

🛠メタコンピュヌティング メタシステム遷移スヌパヌコンパむル REFAL (for REcursive Functions Algorithmic Language) ノァレンティン・フョヌドロノィチ・タヌチン

任意の皮類のシステムSを考える。このシステムSのコピヌをいく぀も䜜る方法があるずする。これらのシステムは、S型のシステムをサブシステムずしお持ち、S型のサブシステムを䜕らかの方法で怜査、制埡、修正、耇補する機構も远加した新しいシステムS'に統合されるずする。そしお、S'をSに関するメタシステムず呌び、S'の生成をメタシステム遷移ず呌ぶ。

http://www.refal.net/doc/turchin/dag/node1.html

私は、拙著『科孊の珟象進化ぞのサむバネティックなアプロヌチ』39においお、考える人間の出珟を含む生物孊的・文化的進化の䞻芁なステップは、倧芏暡なメタシステム遷移にほかならないず解釈しおいる。

http://www.refal.net/doc/turchin/dag/node1.html

コンピュヌタでMSTを実珟するための最初のステップは、適切なアルゎリズム蚀語を蚭蚈するこずでした。私はこのような蚀語の最初のバヌゞョンをメタ・アルゎリズム蚀語[36]ず名付けたが、これはアルゎリズム蚀語の意味論を定矩するためのメタ蚀語ずしお機胜するはずだったからである。その埌、私はこれを簡略化しおREFAL (for REcursive Functions Algorithmic Language)ず名づけた。Refalはメタシステム階局の普遍蚀語ずしお考えられたもので、䞀方では、この蚀語でプログラムを実行する機械Refalマシンが理論分析の察象ずなりうるほど単玔であり、他方では、チュヌリングマシンやマルコフの正芏アルゎリズムちなみに埌者はRefalの源の䞀぀であるなどの玔粋に理論蚀語ずは異なり、珟実のアルゎリズムを曞くためのプログラミング蚀語ずしお十分に豊かであるずいう特城をもっおいる。

Refalの効率的なむンタプリタが最初に曞かれたのは1968幎のこずです[26]。圓時、Refalはパタヌンマッチを内蔵した玔粋な関数型蚀語であり、他の蚀語ずは倧きく異なっおいたした。関数型蚀語が䞀般的になった珟圚では、Refalの特城的な郚分を芁玄するだけで読者に芪しみを感じおもらえるず思いたす。Refalの最倧の特城は、そのデヌタドメむンにある。Refal では蚘号の操䜜にリスト (斜め二分朚) ではなく、匏を甚いたす。Refalの匏は、任意の(固定でない)ノヌドのアリティを持぀朚、たたはそのような朚のシヌケンスずしお芋るこずができる。


term ::= symbol | variable | (expression) | <function expression>
expression ::= empty | term expression

このように、s倉数s.iiはむンデックス名前は任意の蚘号を、t倉数t.iは任意の項を、e倉数e.iは任意の匏を衚しおいるのである。e-variableの堎合接頭蟞を萜ずしおもよいxはe.xず同じである。関数呌び出しの圢匏には角括匧を甚いる。<f x> ずなる。Refalにおけるプログラムは、盞互に再垰的な文(曞き換え芏則)の列であり、 曞かれた順に詊行される。以䞋は、匕数を巊から右ぞ走査し、すべおの'a'を'b'に眮き換える関数fの䟋である。

<f 'a'> = 'b'<f x>
<f s.1 x> = s.1 <f x>
<f > =

モスクワ工孊物理孊研究所の小さなグルヌプ (Stanislav Florentsev, Alexander Krasovsky, Vladimir Khoroshevsky) ず共に私たちは゜ビ゚ト連邊で最も人気のあるマシン甚の Refal コンパむラを䜜成し、 Refal はその郚分でかなり有名になりたした (Refal の開発および䜿甚に関する数幎前の文献には玄 200 点が含たれおいたす)。V.Kistlerovによっお開発された代数的操䜜のための蚀語FLAC[22,4]ず、Sergei RomanenkoずRuten GurinによるRefal Plus[17]であり、Refalのベヌスずなったアむデアの䞀皮の論理的クロヌゞャである。その埌の研究では、DOSずUNIXで動䜜するRefal-5 [44]ずいう名前のRefalの拡匵版を䜿いたした。

蚀語を固定化した埌の次の抂念的な局は運転であった[37,38]。䞊の関数fの呌び出し<f 'a'x>があるずする。明らかに'b'<f x>ず眮き換えるこずができる。これはRefalマシンが関数評䟡の1ステップで行うこずだからである。郚分的な評䟡が行われ、これは単玔な運転の堎合である。今床は、郚分評䟡噚が䜕もしない<f x>ずいう呌び出しを考えおみよう。しかし、運転はただ可胜である。なぜなら、それはいかなる状況でも蚈算の1ステップのシミュレヌションであるからである。プログラムの等䟡倉換をある方皋匏の䜿甚ず考えるず、郚分評䟡は方皋匏<f 'a'x> ='b'<f x>の䜿甚であり、これは完党に理にかなっおいる。しかし、<f x>ずいう呌び方がある以䞊、プログラムを改善するような方皋匏は芋あたらない。運転は、サむバネティックな思考の産物である。私たちはメタマシンを䜜り、それがRefalマシンで最初にできるこずは、その動䜜をシミュレヌトするこずでなければならない。぀たり、メタマシンはRefalマシンを駆動し、本来は準備されおいない、自由倉数を持぀匏に察する蚈算をさせるのである。このような蚈算はメタ蚈算ず呌ぶのがふさわしい。その結果は関数の倀ではなく、その倀に向かう蚈算の1ステップを蚘述したRefalマシンの状態や遷移のグラフである。この堎合、運転はグラフを生成する。

e:pは、匏eをパタヌンpにマッチさせる操䜜を衚す。パタヌンは、操䜜の䞀意性を保蚌する特別な皮類の匏(rigidず呌ばれる)である。匏Eは、(1)s倉数だけがEに2回以䞊入るこずができ、(2)Eの郚分匏(E自身を含む)が匏で区切られた2぀のe倉数を含たないずき、剛䜓であるずいう。なお、[]は読みやすくするために空匏を衚しおいる。

運転からスヌパヌコンパむル略しおSCPに行き着いた。このプログラム倉換の技術に぀いお、倚くの詳现やバリ゚ヌションはさおおき、簡単に説明しよう。スヌパヌコンパむルはドラむバのアップグレヌドである。ドラむビングがリファヌルマシンの1぀のステップを説明しおいるのに察しお、スヌパヌコンパむルはいく぀ものステップを含むこずができる。ドラむビングで新しいアクティブなすなわち関数呌び出しを衚すノヌドCが珟れるず、スヌパヌコンパむラはその祖先を調べ、各祖先C'に関しお次の3぀の決定のうち1぀を行う。

スヌパヌコンパむルの原理ず通垞のプログラム倉換の考え方の違いに泚意しおほしいスヌパヌコンパむルでは、元のプログラムを倉曎するこずはない。それを䞀皮の「自然法則」ずみなし、その法則に埓った蚈算過皋のモデルを構築する。そしお、そのモデルが自己完結するようになったら、倉曎されおいない元のプログラムを捚おればよいのです。私は、スヌパヌコンパむルずは、人間の知識の䞀般原理をコンピュヌタで実珟したものだず考えおいる。䞀般原理ずは、䞖界のある郚分に぀いお自己充足的なモデルを構築できるような、䞀般化された状態を探玢するこずだず考えおいるのだ。

Neil Jones [21] は郚分評䟡ず比范したドラむビングの培底的な理論的分析を行った。最近、DIKUからスヌパヌコンピュヌティングに関するより倚くの論文が出おいる[13,32,33,34,35]。その䞭でGlÃŒckの圹割は、参考文献を芋ればわかるように、最も重芁なものでした。

ノァレンティン・フョヌドロノィチ・トゥルチンロシア語。ВалеМтО́М ЀёЎПрПвОч ТурчО́М、1931幎2月14日ポドルスク - 2010幎4月7日ニュヌゞャヌゞヌ州オヌクランド[1]は、゜連ずアメリカの物理孊者、サむバネティックス、コンピュヌタヌ科孊者である。プログラミング蚀語Refal、メタシステム遷移の理論、スヌパヌコンパむルの抂念を開発した。人工知胜のパむオニアであり、地球脳仮説の提唱者でもある。

https://en.wikipedia.org/wiki/Valentin_Turchin

タヌチンの科孊的研究の哲孊的栞心は、システムの構造ず機胜においおより高いレベルの制埡が出珟する進化的プロセスを瀺すメタシステム遷移の抂念である。
Turchinはこの抂念を甚いお、グロヌバルな進化論ず䞀貫した瀟䌚システム理論を提䟛し、完党なサむバネティックスの哲孊・倫理䜓系を開発し、数孊の構成䞻矩的基瀎を構築しおいる。
たた、REFAL蚀語を甚いお、メタシステム遷移に基づくプログラムの倉換ず最適化のための統䞀的手法であるスヌパヌコンパむラを実装しおいる

https://en.wikipedia.org/wiki/Valentin_Turchin

圓時二村はLispのマニュアルを読んでコンパむラを実装する仕事に取り組んでいた。マニュアル (LISP 1.5 Programmer's Manual[1]) では、そのむンタプリタがいかなるものであるかを説明するこずでLispが説明されおおり、むンタプリタがあればそこからコンパむラを生成するこずができるのではないか、ずいうのが最初の発想だった。郚分蚈算や自己適甚ずいう抂念は「運良く」導き出すこずができたものだ、ずいう。
最初の発衚は「蚈算過皋の郚分評䟡: コンパむラ・コンパむラの䞀方法」1971幎ずいう題でたずめられた。アンドレむ・゚ルショフ英語版露: АМЎре́й ПетрП́вОч ЕршП́вがbit誌に寄せた1980幎掲茉「フタムラの射圱に぀いお」では、郚分評䟡同文献䞭では「混合蚈算」ず呌んでいるプログラムずむンタプリタ、コンパむラ、コンパむラゞェネレヌタの関係を瀺した3぀の匏に぀いお『教科曞が曞かれるずきにはすばらしい関係匏 (I) (II) および (III) は「フタムラの射圱」ず圓然呌ばれるでありたしょう』ず締めくくっおおり、それが「二村射圱」ずいう衚珟の初出ず蚀えるがなお、゚ルショフはそのように曞いおいるが、実際には最初の発衚では前述の α(α, α) = αα がコンパむラゞェネレヌタであるずは明確に觊れおおらず、72幎ず73幎の報告が初出である、英語でFutamura Projectionずいう衚珟が䜿われたのは、郚分評䟡に関する囜際䌚議Partial Evaluation and Mixed Computation (PEMC) においお1987幎のこずであった。初出の文献は日本゜フトりェア科孊䌚の『コンピュヌタ゜フトりェア』Vol. 21, No. 5に二村ぞのQ&Aずずもに再録されおいる

二村射圱の栞心

郚分評䟡は、プログラムの䞀郚の情報を事前に知っおいる堎合に、その情報を䜿っおプログラムを簡略化たたは最適化する手法です。二村射圱は、郚分評䟡を甚いお以䞋の3぀の興味深い結果を瀺しおいたす

  1. むンタプリタずプログラムの郚分評䟡: むンタプリタにプログラムを固定しお郚分評䟡を行うず、そのプログラムのコンパむルされたバヌゞョンを埗るこずができる。

  2. コンパむラの生成: むンタプリタに察する郚分評䟡自䜓を郚分評䟡するず、そのむンタプリタのためのコンパむラを生成するこずができる。

  3. コンパむラゞェネレヌタの生成: さらに、䞊蚘の郚分評䟡プロセス自䜓を郚分評䟡するず、コンパむラゞェネレヌタを埗るこずができる。



お願い臎したす