プロローグで再確認します。 セブンラインマジック

認識マシンが象の写真に「ムラ」信号で応答する場合、ラクダの画像も「ムラ」であり、著名な科学者の肖像画は再び「ムラ」です。これは必ずしも欠陥があることを意味しません。 彼女はただ哲学的でありえます。

ウラジミール・サフチェンコ、「自分を開く」

1.リファールが大好き。 すぐに！

そのようなプログラミング言語があることを誰もが知っています-リファール。 Refalは1966年に同胞のValentin Turchinによって開発されました。 リファールの運命は複雑ですが、彼の言語はまだ生きていて発展しています。 興味がある人のために、ここにいくつかのリンクがあります：

• Refala-5の独立した研究。 学生の表情
• ジャーナル「関数型プログラミングの実践」第7号 （彼に記憶を与えてください！）。 記事「REFAL language-a view from side」および「Supercompilation：idea and methods」

非常に誇張して、RefalはLispとPrologの混合物であると言えます。 言語構文には、いわゆるパターンとの比較という興味深い機能が1つあります。 「直接結論。」



つまり、たとえば、Refalでパリンドロームを決定するための述語は、次のように記述できます。

Palindrom { = True; s.1 = True ; s.1 e.2 s.1 = <Palindrom e.2> ; e.1 = False ; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

中括弧内の各行は、パターンマッチングルールです。 各ルールの本文は、記号「=」で区切られています。 サンプル要素はスペースで区切られます。 関数呼び出しは山括弧で書かれています。 「s」と「e」で始まる文字は、特定の種類の変数です。 変数の名前は、ピリオドの後に書き込まれます。

• タイプ「s」の変数は、マッピングがシーケンスの1つの要素に対してのみ真であることを意味します
• タイプ「e」の変数は、0個以上の要素に対して一致が真であることを意味します

T.O. 回文のこの定義は、次のように読むことができます。

• 式は、空のリストに対して真です。 つまり 空のシーケンスは回文と呼ばれます。
• この式は、単一要素のリストに当てはまります。 つまり 1つの要素のシーケンスは回文と呼ばれます。 s変数の型は、パターンが1つの要素に対してのみ有効であることを示しています。
• この式は、リストの最初と最後の要素が等しい少なくとも2つの要素で構成されるリストに対して真です。 最初と最後の要素が等しいことは、同じ変数名（ "1"）で示されます。 回文については、最初と最後の要素の間のサブリスト（変数「e.2」、つまりそのようなサブリストの長さは0以上の要素）を再帰的にチェックする必要があります。
• 上記のルールのいずれも機能しなかった場合、渡された引数は回文ではありません。

Refalの最新の実装では、モデルとの比較が非常に効率的に実装されていることをキャンセルする必要があります。

2.プロローグ。 魔法が始まります！

RefalにはPrologからたくさんのことがあります。 Prologのサンプルとのrefalovskoe比較のメカニズムの実装を試みます。



始める前に、ヘルパー述語「prefix」を定義します。 述部は、最初の引数が2番目の引数の始まりであるかどうかを確認する必要があります。 2番目の引数の残りは、3番目の引数に示されます。

 prefix([], [X|Xs], [X|Xs]). prefix([X|Prefix], [X|List], Rest) :- prefix(Prefix, List, Rest).
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

呼び出し例：

 ?- prefix([1,2], [1,2,3,4], [3,4]). true. ?- prefix([], [1,2,3,4], X). X = [1, 2, 3, 4].
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、サンプルと一致するrefalovoeの述語を決定する準備がすべて整いました（述語「rf」と呼びましょう）。 例と同じパリンドロームを使用した「rf」の使用例は次のとおりです（実装自体は少し後です）。

 palindrom([]). palindrom([_]). palindrom(List) :- rf([s(X1), e(Y), s(X1)], List), palindrom(Y).
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ご覧のとおり、この定義は以前にRefalで書いたものと似ています。 refalovの例の4番目のルールは必要ありませんでした。 プロローグ自体は、マッピングの誤った分岐を遮断します。 例の「s」と「e」は通常のProlog用語であることに注意してください。



回文を呼び出す例：

 ?- palindrom("abc"). false. ?- palindrom("abcba"). true . ?- palindrom("aa"). true .
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、rf述語の定義に移りましょう。

 rf([X | Pattern], [X|Xs]) :- rf(Pattern, Xs). rf([s(X) | Pattern], [X|Xs]) :- rf(Pattern, Xs). rf([e(X) | Pattern], Xs) :- prefix(X, Xs, Rest), rf(Pattern, Rest). rf([e(X)], X). rf([], []).
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

定義について1行ずつコメントします。

• 少なくともサンプルとリストの両方が同じ要素（変数X）で始まる場合、比較は真です。 次に、残りの引数を確認します
• この規則は、パターンの「s」要素にも当てはまります。
• サンプルの次の要素が「e」変数である場合、変数Xが2番目の引数のプレフィックスであるかどうかを確認します（空のリストもプレフィックスである可能性があることを思い出してください）。 次に、残りの引数を確認します
• 残りの2つのルールは、些細な一致ケースを説明しています。

3.例

3.1。 最初の例

素晴らしい記事「Prolog、Introduction」は、 PrologのRefalコミュニティで提案された問題の解決策を提供します。 問題文：

入力ファイルには2つのASCII行があり、1つは大きなラテン文字のみで構成され、もう1つは大きなラテン文字と2つの特殊文字-*（アスタリスク）および？ （疑問符）。 文字列の長さは1〜255文字で、ランダムな順序でファイルに格納できます（ただし、入力データ形式は正しいので、2つしかありません）。 文字のみの行は単語と呼ばれます。 特殊文字を含む行-「？」が含まれるパターン および「*」は、DOSまたはUnixシェルのファイル名のワイルドカードと同じ規則に従って、ワイルドカード文字の役割を果たします。 「？」 任意の1文字を正確に置き換え、「*」は任意の数の任意の文字を置き換えます-0以上（つまり、空の文字列を置き換えることができます）。 単語がパターンに一致する（一致する）場合、プログラムはYESと答え、そうでない場合はNOと答えます。

リファールの解決策：

 Match { s.1 e.2 (s.1 e.3) = <Match e.2 (e.3)>; s.1 e.2 ('?' e.3) = <Match e.2 (e.3)>; e.1 ('*' e.3) = { e.1 : e.11 e.12, <Match e.12 (e.3)>; }; /*empty*/ () = /*yes*/; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

上記のアプローチを使用して、PrologのRefal述語を書き換えます。

 ischar(H, [H]). match([],[]) :- !. match("*",_) :- !. match(Pattern, Word) :- rf([s(T1), e(E1)], Pattern), rf([s(T1), e(E2)],Word), match(E1, E2),!. match(Pattern, Word) :- rf([s(T1), e(E1)], Pattern), ischar(T1, "?"), rf([s(_T2), e(E2)], Word), match(E1,E2),!. match(Pattern, Word) :- rf([s(T1), e(E1)], Pattern), ischar(T1, "*"), rf([e(_E21), e(E22)], Word), match(E1,E22),!. check:- match("ASDFAASDASDAAASDASDASD", "ASDFAASDASDAAASDASDASD"), match("*", "ASDFAASDASDAAASDASDASD"), match("A?DF?A*ASD*ASDA?DASD", "ASDFAASDASDAAASDASDASD"), \+ match("ASDFAASDADAAASDASDASD", "ASDFAASASDAAASDASDASD").
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

もちろん、私たちの定義は、記事「Prolog、Introduction」のソリューションよりもはるかに効果が低いことに注意してください。

3.2。 2番目の例

述語を使用する別の例を次に示します。 文字列の算術式を計算する簡単な述語を定義します。



使用例：

 ?- infix("2+2*2", R). R = 6. ?- infix("1+1+1+1", R). R = 4.
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

中置述語に加算と乗算の演算のみを「理解」させます。 次に、ソリューションは次のようになります。

 ischar(H, [H]). infix(A,R) :- rf([e(X), OpPlus, e(Y)], A), ischar(OpPlus, "+"), infix(X,R1), infix(Y,R2), R is R1 + R2,!. infix(A,R) :- rf([e(X), OpMul, e(Y)], A), ischar(OpMul, "*"), infix(X,R1), infix(Y,R2), R is R1 * R2, !. infix(A,R) :- rf([e(X)], A), number_codes(R, X),!.
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

他の演算子の実装は独立した研究に任せます。

結論の代わりに

上記のコードは、一意または実用的であると主張していません。 しかし、読者がPrologやRefalのような素晴らしい言語に精通するようになることを願っています。