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

Metacompilation:Metasystem Transitions

任意の種類のシステム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

ニュートン式 超図解 最強に面白い!! 地球46 億年 (ニュートン式超図解 最強に面白い!!)

ターチンの科学的研究の哲学的核心は、システムの構造と機能においてより高いレベルの制御が出現する進化的プロセスを示すメタシステム遷移の概念である。
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. コンパイラジェネレータの生成: さらに、上記の部分評価プロセス自体を部分評価すると、コンパイラジェネレータを得ることができる。