🛠Refal言語入門　末尾再帰標準装備で命令型言語をディスる　パターンマッチングの起源

2022年8月14日 17:27

REFALは、自然言語や人工言語に基づくコンピュータプログラムの解析、送信、テキストの推敲など、シンボルデータの推敲に重点を置いた関数型プログラミング言語である。
まずこの言語は、1968年にValentin Fedorovich Turchinによってメタ言語[1]、すなわち他のプログラミング言語のセマンティクスを記述するための言語として提案されました。言い換えれば、これは擬似コードであり、ある種の数学的表記法である。その後、REFALをコンピュータに実装するための新しい効果的な方法が登場し、すでに完全な機能を持ったプログラミング言語になっている。

基本Refalとは一般にRefal意味的部分集合を指し、関数文は2つの部分からなり、変数はs-、t-またはe-型（Refal-2修飾子はない）、記号型はリテラル文字、数字、単語のみである。

https://bmstu-iu9.github.io/refal-5-lambda/3-basics.en.html

Refal-5λでは、どんなプログラムも関数の集合体です（結局、関数型プログラミング言語なのです）。このプログラムも例外ではありません。Go関数はここで定義されている。関数の定義は、関数名とブロック（中括弧で囲まれた関数本体：それぞれ文字列1、3）で記述されています。Goという名前は偶然ではありません。Refalのプログラムには必ずGoまたはGOという名前の関数定義が1つあります。

おそらくC言語でいうmainのようなものか

まず、一次活性部分式は、他の活性化括弧を含まない活性化括弧の左端のペアを選択する。これは、Refal - が応用言語であり、関数計算の順序が左から右へと正確に定義されることを意味する。つまり、文の右側にいくつかの関数の呼び出しがある場合、それらは左から右へ、最も内部的なものから最も外部的なものへと計算される。したがって、副作用のある関数（たとえば、Prout）を使う場合、その副作用がいつ発生するのかを知って使うことができる。

左から右はAPLの逆

第二に、Refalがいわゆる末尾再帰の最適化を実装していることは、ビューフィールドのセマンティクスからすぐに理解できる。
多くの命令型プログラミング言語では、再帰は非常に高価であり、計算コンテキスト（末尾呼び出しの完了後に実行プロセスが戻らなければならないポイント）を維持するためのオーバーヘッドが必要である。そして、この保存のためのメモリは、限られた領域、つまりシステムスタックから提供される。プログラマは原則としてシステムスタックの大きさを制御できないし、スタックがオーバーフローするとプログラムが異常終了してしまう。したがって、このような言語では、再帰を使って周期的に繰り返される動作を実装してはならない（特に、命令型言語ではそのための反復演算子がある）。

命令型言語を豪快にディスる

Refal関数は、再帰呼び出しを実行する関数が次の再帰呼び出しの前に終了するため、値を返すために計算コンテキストを保持する必要がない。そして、右の部分の再帰呼び出しを最後に実行すれば、不完全な計算がビューフィールドに集まらないことを意味する。つまり、実際には再帰（囲まれた文脈）は観察されないが、サイクルは観察される。

Refal-5には、標準的な組み込み関数のライブラリが含まれています。これらは、I/Oや算術演算、Refalでは定義できない様々なシステムジョブ、および効率化のためにシステムに組み込まれた簡単な手続きなどです。

http://www.botik.ru/~scp/book/ref_c.html

REFALと他の関数型言語（FL）との違いは、まず第一に、特殊なデータ構造であるオブジェクト式が使われていることである。多くのFLでは、単一リンクリスト（左辺だけがアクセス可能な要素の列）を使って、直接推敲することができます。つまり、最初の要素を探す、最初の要素を切り取る、最初のリストの先頭に要素を追加して新しいリストを作る、といった操作しかできない。
最後の要素を得るには、最初の要素を空っぽになるまで順次切り捨てていく、つまり最後に切り捨てた要素がリストの最後の要素になります。2つのリストを連結する(glue)ためには、最初のリストの要素を逆順に2番目のリストの先頭に追加しなければならない。
REFALは双方向のシーケンス(「オブジェクト式」と呼ばれる)を操作することができます。 両側で同じ操作(最初の要素を切り離す、要素を追加する)だけでなく、連結や分離もどこでも可能です (open e-variable について先を参照してください)。これらの操作はすべて原始的なものですこのため、プログラムの表現力が増します。

https://bmstu-iu9.github.io/refal-5-lambda/2-intro.en.html

パターン式は、すべての変数に許容値を代入して得られるオブジェクト式の集合と見なすことができる。したがって，パターンA e.1は，記号Aで始まるすべてのオブジェクト式の集合を表す．同じ変数のすべてのエントリは，同じ値で置き換えられなければならない．パターンs.1 e.2 s.1は，同じ記号で始まり，同じ記号で終わる，少なくとも2つの記号を持つすべての目的語表現の集合と見ることができる．
しかし、パターン式にはもう一つの機能がある。それは、パターン中の変数がオブジェクト式の一部と同定される、つまりある値をとるという、オブジェクト式の分解を記述することである。このように考えると，A e.1 は，与えられたオブジェクト式の最初の記号が A であることを確認し，その残りの部分を値として e.1 に代入する手続きである．この手続きはパターンマッチングと呼ばれる。

http://refal.botik.ru/book/html/

ここまでのRefal側の言い分をまとめてみたよ

はじめに

基本的なリファール
1.1 簡単な関数定義
1.2 記号と式
1.3 パターンマッチ
1.4 文章とプログラム
1.5 抽象的なRefalマシン
1.6 その他の関数の例
コンピュータにおけるリファール
2.1 実行方法
2.2 プログラムモジュール
2.3 入力-出力
2.4 Refal式の表現
2.5 パターンマッチングのアルゴリズム
プログラミングの基本技法
3.1 ポインタとしてのブラケット
3.2 関数の書式
3.3 暗黙の再帰と明示の再帰
3.4 変数の重複
3.5 アルゴリズモの関数への分解
3.6 再帰と反復
3.7 入れ子になった括弧の処理
拡張リファール
4.1 条件
4.2 ブロック
4.3 Bury-Dig関数
プログラム開発
5.1 宣教師とカニバール
5.2 ソートアルゴリスム
5.3 グラフのパス
5.4 算術式の翻訳
メタシステム遷移
6.1 メタファンクションミュー
6.2 メタコード
6.3 評価器
6.4 フリーザ
演習問題解答
参考マニュアル
A. 設置方法と使用方法
B. 構文概要
C. 組み込み関数
D. リファールトレーサー
INDEX

ここで強調しておきたいのは、Refalにおける表現の概念はより一般的であるということである。Refalでは、式を特別に解釈することはなく、様々な方法で使用することができます。Refalの式は、記号と構造括弧からある種の方法で構築された構造体である。各構造括弧には、ちょうど1つの対になる括弧があります。これらは一種の箱か袋のようなものである。それらは、全体システムの一部でありながら、その統一性を保つ、全体システムのサブシステムを区切ります。この部分構造の一方の境界を特定すれば、他方の境界は一意に定まる。システムとそのサブシステムの関係は、世界の非常に重要な側面である。私たちが世界の象徴的なモデルを作るとき、構造括弧はこの関係をモデル化する。ピアノ、バイオリン、ビオラがアンのアパートにあり、チェロとベースがボブのアパートにある場合、この状況はRefal式でモデル化することができる。

またボブかい太郎かボブかという

はい、こんな感じで表現します　ピアノ、バイオリン、ビオラがアンのアパートにあり、チェロとベースがボブのアパートにある場合

自由変数は、型記号、ドット、インデックスで形成されます。変数のインデックスは識別子または整数である。型記号は3つある。これらは小文字のs、t、eで表され、対応する変数はs-、t-、e-変数と呼ばれる。これらの違いは、許容される値の集合にある。s変数は1つの記号だけを値として取ることができる。t変数は任意の項を値とする（項は構造体括弧内の記号または式であることを想起してほしい）。e変数は、任意の式を値とすることができる。

パターンマッチング

前述のように、RefalとLisp、およびリストを扱う他の言語との大きな違いは、データドメインにあります。Refalの式は左から右へ、あるいは右から左へ処理することができる項列です。また、アリティが固定されていない任意の木構造です。Lispのリストは特殊なRefal表現です。私がメタ計算でRefal式を頑なに使うのにはいくつかの理由がある（主な理由は隠そうとしているのだが、私が発明したからである）

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

1.近い将来、メタ計算の手法が、大規模かつ高速なプログラムの自動開発に、産業規模で利用されることを期待している。アルゴリズムの効率は、データ構造と密接に関係していることはよく知られている。文字列のような重要なデータ構造を放棄することに、実用的なプログラマが同意するとは思えない。リストに限定すると、効率的なアルゴリズムの巨大なセットを投げ捨てることになる。

べつにLISPで放棄してる印象はないが、別の帰結を見せているようにも思える。Forthもなかな難しい

2.2節で見たように、Refal式はリストでは表現できないような一般化を可能にする。これにより、スーパーコンパイルが容易になり、より効率的になる。我々が使用するデータ構造は、基本的には現実のモデルである。より洗練されたデータ構造を用いることで、媒体のより微妙な特徴を表現することができる。グラフに基づく言語は、Refalが純粋なリスト処理言語に対して持っているのと同じような利点をRefalに対して持つことになる。

3.対象機械の動作を調査・制御するためのメタマシンを作成する場合、その歩みを前方・後方の両方向に追跡したい場合が多い。計算の履歴は、当然ながら状態の文字列で表現される。第3.1節では、計算機の構成から計算機による計算の歴史に切り替えることで、スーパーコンパイルがどのように強化されるかを示す。さらに、後方への移動はスーパーコンピューティングの概念の一部である。後戻りは避けることができますが、その代償として、概念的な簡略化という代償を払わなければなりません。私たちが使う言語は、今やっていることを表現するのに役立つだけでなく、さらに何ができるかを示唆してくれる。スーパーコンパイルの概念がRefalのような言語の文脈で最初に登場したのは偶然ではありません。

Forthがスタックで、木構造をネイティブに取り扱っている点でユニーク、似たようなネイティブ機構をScalaはXMLで持っているが、どういうコンセプトか、Scalaに興味が沸いた

4.純粋なリスト処理言語は、再帰的なプログラミングには向いているが、アルゴリズムが反復的である場合には不向きである。一方、再帰的なアルゴリズムは明確でエレガントであるが、効率が悪いため、反復的な形に変換しなければならない状況にしばしば直面する。Lispでは、リストを反転させない単純なトラバーサルでさえ、反復的に行うと不可能になる。Refalは再帰的なプログラミングも反復的なプログラミングも同様に得意としています。

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

お願い致します

🛠Refal言語入門 末尾再帰標準装備で命令型言語をディスる パターンマッチングの起源

ここまでのRefal側の言い分をまとめてみたよ

🛠Refal言語入門　末尾再帰標準装備で命令型言語をディスる　パターンマッチングの起源