リファル

Refal ( 「再帰関数アルゴリズム言語」、ロシア語: РЕФАЛ ) は、 「文字列処理、言語翻訳、[および]人工知能」を含む「記号計算を指向した関数型 プログラミング言語」です。^[1]これはこのファミリーの最も古いメンバーの1つであり、1966年に理論的なツールとして最初に考案され、1968年に最初の実装が登場しました。Refalは、大規模で高度なプログラムを書くための数学的な単純さと実用性を組み合わせることを目的としていました。

Refal は、これを実現した最初の関数型プログラミング言語の 1 つであり、当時のLispとは異なり、パターン マッチングに基づいています。パターン マッチングは、項の書き換えと連動して機能します。

Lisp とPrologの基本的なデータ構造は、cons 操作によって順次構築される線形リストであり、リストのn番目の要素へのアクセスはO(n)です。Refal のリストは両端から構築およびスキャンされ、パターン マッチングは最上位のリストだけでなくネストされたリストでも機能します。実際には、Refal の基本的なデータ構造はリストではなくツリーです。これにより、パターン マッチングと置換という数学的に単純な制御メカニズムのみを使用して、データ構造を自由に、かつ便利に作成できます。

Refal には、効率的な部分評価をサポートするフリーザーと呼ばれる機能も含まれています。

RefalはXSLTと同様にツリー構造の処理と変換に適用できます。^[2]

Refal Hello World の例を以下に示します。

$ENTRY Go { = <Hello>;}
こんにちは {
   = <Prout 'Hello world'>;
}

上記のプログラムには、Go と Hello という 2 つの関数が含まれています。関数は、関数名の後に中括弧で囲んだ関数本体が続く形で記述されます。Go 関数は、$ENTRY ディレクティブを使用してプログラムのエントリ ポイントとしてマークされます。

関数本体の式は、 Lispのような構文での関数の「呼び出し」と考えることができます。たとえば、 Hello 関数は、文字列 'Hello world' を引数として組み込みの Prout 関数を呼び出すように見えます。ただし、呼び出しの意味とメカニズムはまったく異なります。違いを説明するために、文字列が回文であるかどうかを判定する次の関数を考えてみましょう。

Pal { = True;
    s.1 = 真;
    s.1 e.2 s.1 = <Pal e.2>;
    e.1 = 偽; }

この例では、4 つの文 (節)で構成される、より複雑な本体を持つ関数を示します。文はパターンで始まり、その後に等号が続き、右側に一般的な式が続きます。文はセミコロンで終了します。たとえば、関数の 2 番目の文のパターンは "s.1" で、式は "True" です。

例に示すように、パターンには、変数の型 (変数が一致するもの) を識別する文字の後に変数識別子が続く形式のパターン変数が含まれます。「s」で始まる変数は単一のシンボルと一致し、「e」で始まる変数は任意の式と一致します。変数識別子は、オプションでドットによって型識別子から区切られた任意の英数字シーケンスにすることができます。

関数は、定義に現れる順序で、一致する最初のパターンが見つかるまで、引数を文のパターンと比較することによって実行されます。次に、関数は引数を一致した文の右側の式に置き換えます。

関数適用の結果に山括弧内の部分式が含まれる場合 (例の 3 番目の文が適用された後のように)、結果は Refal によってさらに処理され、括弧内の最初のシンボルで識別される関数が呼び出されます。結果にこのように展開する山括弧がなくなると、実行は停止します。

したがって、関数 Pal は非公式には次のように解釈できます。「式が空の場合は True に置き換えます。式が単一のシンボルの場合は True に置き換えます。式がシンボルの後に任意の式 e.2 が続き、その後に同じシンボルが続く場合は、式 <Pal e.2> に置き換えます (つまり、先頭と末尾の 2 つの同一シンボルを破棄して再帰します)。それ以外の場合は、式を False に置き換えます (パターン e.1 は常に一致します)。」

以下は、次のステップを生成するために各ステップで適用される文番号が注釈された3つのステップごとの実行トレースです。

<パル「正午」> (#3)
 <パル 'oo'> (#3)
 <パル> (#1)
 真実

<友達「わあ」> (#3)
 <パル 'o'> (#2)
 真実

<パル「リボルバー」> (#3)
 <パルが進化する> (#3)
 <パル 'volv'> (#3)
 <パルオル> (#4)
 間違い

ここで、Hello World の例が実際には次の式変換のシーケンスとして実行されることがわかります。

      $ENTRY でマークされた初期式でマシンをシードします。
 <Go > (Goで文を適用)
 <Hello > (Helloの文を適用します)
 <Prout 'Hello world'> (Prout は何も出力せずに展開する組み込み関数です)
                       (適用するものはありません。停止)

事実 { 0 = 1;
    sN = <* sN <事実 <- sN 1>>>; }

ここで 0 は数値 0 と一致し、1 を生成します。数値であるその他の記号の場合は、(Fact (- sN 1)) の結果と乗算します。演算子のプレフィックス スタイルに注意してください。

ファクト { sn = <ループ sn 1>; };
 ループ {
    0 sf = sf;
    sn sf = <ループ <- sn 1> <* sn sf>>; }

ご覧のとおり、 sn はループ カウンターとして機能します。

等しい {
    (e.1)(e.1) = T;
    (e.1)(e.2) = F; }

ここで関数は、2 つの用語が与えられ、その用語が同じである場合、最初の句が一致して True を生成する、と定義されます。それ以外の場合は、2 番目の句が一致して False を生成します。

Refal の重要な特性は、refal 内のすべての関数が単一の引数であることです。(ただし、上記のように式内の項に分解される場合もあります。)

制御構造の定義は簡単

もし {
    T Then (e.1) Else (e.2) = e.1;
    F Then (e.1) Else (e.2) = e.2; }

ここで、入力された式が「True」に一致する場合にのみ e1 が評価され、それ以外の場合は e2 が評価され、e2 も同様に評価されます。

絞る {
    e.1'__'e.2 = <e.1'_'e.2 を絞る>;
    } 関数

(関数呼び出しを明確にするために、スペース文字の代わりに '_' を使用します。) 最初の句は、関数 Squeeze が入力式で二重の空白に遭遇するたびに一致し、それを単一の空白に置き換えます。 2 番目の句は、最初の句が一致しなかった場合にのみ一致し、現在の式である結果の値を返します。

絞る {
    '__'e.1 = <'_'e.1 を圧迫>;
    sA e.1 = sA <e.1を圧迫>;
    = ; };

• Turchin, Valentin F. (1989)。「REFAL-5 プログラミング ガイドおよびリファレンス マニュアル」。ニューヨーク市立大学、New England Publishing Co.、Holyoke。

• リファルホームページ