レファル
関数型プログラミング言語
レファル
パラダイムパターンマッチングと項書き換え
デザイン：ヴァレンティン・ターチン
開発者Valentin Turchin、S. Florentsev、V. Olyunin 他
初登場1968 （1968年）
タイピングの規律強い、ダイナミックな
Webサイトhttp://www.refal.net
主要な実装
リファール-2、リファール-5、リファール-6、リファール+

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

Refalは、これを実現した最初の関数型プログラミング言語の一つであり、当時の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 { = 真;
    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)
 <Pal 'volv'> (#3)
 <パル 'ol'> (#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 を絞る>;
    e.1 = e.1; }

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

明示的なループを使用したスクイーズ

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

参考文献

  • Turchin, Valentin F. (1989). 「REFAL-5 プログラミングガイドおよびリファレンスマニュアル」. ニューヨーク市立大学、ニューイングランド出版、ホリヨーク.
  1. ^ Turchin, Valentin F. (1989). 「Refal入門」. REFAL-5プログラミングガイド＆リファレンスマニュアル. Holyoke: New England Publishing Co. 2008年7月3日時点のオリジナルよりアーカイブ。 2010年4月5日閲覧。
  2. ^ 「Refal: XML文書処理言語」。2007年12月6日時点のオリジナルよりアーカイブ。 2008年3月18日閲覧。
  • Refalホームページ
「https://en.wikipedia.org/w/index.php?title=Refal&oldid=1255092984」より取得