📿 👻 👩🏿‍🎓 プロローグ-ケーススタディ（パート2） ⚽️ 👨🏿‍💻 🐭

Prologの記事の最初の部分では、言語の構造、構文、および解釈について説明しました。もちろん、ノンフィクションの文学はプログラマーにとって興味深いものですが、よりインタラクティブで活気があり、発売されたものははるかに興味深いものです。したがって、この記事では、 SWI-Prologを使用して、Prologで最も単純なタスクの解決策を検討することを提案します。

始める前に、habrachitateliからの話題の質問に簡単に答えたいと思います。

-プロローグは実際にどこで使用されていますか？

-そのようなプロジェクトが存在し、一部は第1記事のコメントで引用されました。ほとんどのプログラマーが絶望のためではなく、Prologを好むので、Prologに書くことが重要です。結局のところ、Prologは、UIの作成やファイルの操作などのタスクには使用できません。

-なぜそのようなプロジェクトが少ないのですか？

-Prologを所有しているプログラマーが非常に少ないのは、人々がそれを研究していないだけでなく、完全なプログラムを書くのに十分な研究をしていないからです。主な理由は、どのような状況でそれを使用するのが最善かを人々が明確に理解していないからです。多くの場合、Prologの熱心なサポーターがキーボードやマウスハンドラーを含むすべてを書き込み、Cの場合よりもコードをさらに悪化させることがわかります。

-なぜPrologコミュニティがないのですか？

-そうです。アカデミックな環境で非常に好まれている言語の特異性です（ほとんどのPrologシステムはさまざまな大学で書かれており、ほとんどすべての大学が独自のPrologを作成しています）。このため、言語の適用性が損なわれていると言えます。コミュニティは小さいが非常に忠実であることは注目に値します。ほとんどの既知の言語は現代言語に反映されます（Lisp、ML-> F＃、Scala; Smalltalk-> Java、Scala（agents）、script-> Ruby）プロローグ。

私はこれで十分な哲学的推論であり、実際の例を進めることができると思います:)

最後に、いつものように、賞品のタスクが期待しています。

例1-完全な数字を検索する

この例では、述部が/ 2である必要があります。 Xは3 + 1 * 2-右側の式を計算し、左側の変数に代入します。これは代入（！）ではありませんが、X = 7というステートメントです。単純に言えば、X = 7、X = 3というフレーズはX同時に7と3になる。

前のトピックの問題の解決策も必要です。タスクは、すべての自然数を連続して生成する述語を書くことでした。解決策は次のとおりです。

ints(0). ints(X) :- ints(Y), X is Y + 1.

これは実際には、引数が整数であることをチェックする標準整数/ 1述語の宣言バージョンです。標準述語の問題は、リクエストに対して正しく機能することです：-整数（1）およびリクエスト整数（X）に対しては機能しません。

タスク：すべての完全な数を見つけるプログラムを作成します。

解決策は明らかです。すべての整数を調べて、それらが完全であるかどうかを確認します。この戦略は命令型言語に非常によく適用できます。解決策検索アルゴリズムをすぐに探す方法に気付いていませんが、問題を分析しません。プロローグでは、問題の解決策の検索を説明するのではなく、問題のステートメントを説明しようとする必要があります。これを行うには、ルールに従います。

解決策を見つけるための手順を説明しようとしないでください。すでに解決策を見つけていると仮定し、解決策が見つかったことを確認するだけです。

奇妙なことですが、この戦略はうまく機能します。

  %%     ints(0). ints(X) :- ints(Y), X is Y + 1. %%   -  1)   2)     perfect_number(X) :- ints(X), Y is X - 1, calculatesum_divisors_till(Sum, X, Y), Sum = X. %%    1-  , 2- -     , %% 3- -      calculatesum_divisors_till(0, _NumberToDivide, 0). calculatesum_divisors_till(Sum, NumberToDivide, Till) :- Till > 0, Rem is NumberToDivide mod Till, Rem = 0, Ts is Till - 1, calculatesum_divisors_till(SumPrev, NumberToDivide, Ts), Sum is SumPrev + Till. calculatesum_divisors_till(Sum, NumberToDivide, Till) :- Till > 0, Rem is NumberToDivide mod Till, Rem > 0, Ts is Till - 1, calculatesum_divisors_till(Sum, NumberToDivide, Ts).

ソーステキストをファイルに貼り付け、インタープリターを実行してコンパイルします（リクエスト：-compile（ 'path_to_file / perfect_numbers.pl'を使用）。リクエストを記述します：-perfect_number（X） 。注意、リクエストは次のようになります。-perfect_number（X）、X> 6.その後、すべての答えは6以上になります。もちろん、プログラムは最適に動作しません。チェック自体は単純な仕切りを使用して単純化できます。

例2-順列の生成。

この問題を定式化して解決するには、リストの概念が必要です。リストは言語の基本的な概念ではありません。リスト間では、Cのリンクリストとの直接的な類似性を引き出すことができます。再帰的なデータ構造としての用語の定義に戻りましょう。

  %%      nil list(nil). %%      1 list(t(1, nil)). %%     1, 2, 3 list(t(1, t(2, t(3, nil) ) ) ). %%        %% 1.      (1- ) %% _ -      member(X, t(Y, _)) :- X = Y. %% 2.    ,         member(X, t(_, Tail)) :- member(X, Tail).

多くの人が通常の再帰を言うので、リストがPrologで特に特別に見えないように、それらのための構文糖衣があります：nilは[]、t（1、nil）-[1]、t（1、t（2、nil）と書くことができます）-[1、2]、t（1、サブリスト）-[1 | サブリスト]、t（1、t（2、サブリスト））-[1、2 | サブリスト]。用語の内部名が異なる場合があるため、リストには構文糖衣を使用することをお勧めします（ほとんどの場合、用語は「。」と呼ばれます）。

  %% 1.      (1- ) member(X, [X|_]). %% 2.    ,         member(X, [_| Tail]) :- member(X, Tail).

順列を生成するという元の問題に戻ります。順列の数がn！であることを誰もが完全に覚えていますが、ほとんどのプログラマにこのタスクを与えると、誰もが学校でそれを書いて検索の方法を忘れたことを必死に覚えて言うでしょう。平均して、約20分後に試して苦しめた後、アルゴリズムが表示されます。Prologを知っている場合、このアルゴリズムは2分で書き込まれるか、まったく書き込まれません:)

プロローグの決定方法このルールは、解決策を見つけるためではなく、解決策が見つかったことを確認するために使用します。 Perm述語（Source、Permutation） -Sourceはソースリスト、Permutationは置換です。

  %%           perm([], []). %% 1-       , %%         , %%       %%    perm(Source, [Element|Tail]) :- member_list_exclude(Element, Source, SourceExcluded), perm(SourceExcluded, Tail). %%  ,     ,  2-      %%   member_list_exclude    %% 1- - , 2- - , 3- -    member_list_exclude(X, [X|L], L). member_list_exclude(X, [Y|L], [Y|Ls]) :- member_list_exclude(X, L, Ls).

リクエスト：-perm（[1、2、3]、X）はすべての順列を生成します。興味深いことに、リクエストは引数に対して対称です：-perm（X、[1、2、3]）。このリクエストはフリーズし、機能するためには、permでmember_list_excludeとpermを交換する必要があります。

例3-組み合わせの生成。

実装が簡単な組み合わせの生成は、順列の生成に似ています。述語メンバー/ 2が必要です-要素はリストに属します。 2つのリストがあると仮定します：1番目のソースリスト、2番目-提案された組み合わせ、組み合わせの正確性を確認する必要があります。組み合わせ項目は、ソースリストの順序で配置されます。

  member(X, [X|_]). member(X, [_|L]) :- member(X, L). comb([], []). %%  1 : 1-       comb([X|List], [X|Tail]) :- comb(List, Tail). %%  2 :      , %%   1-        comb([_|List], Tail) :- comb(List, Tail).

例4-ソート。

この例を十分に詳細に検討し、主要なソリューションの最適化を試みます。 Prologに書き込むプロセスは次のとおりです：1）問題の初期の説明と徹底的な解決策の取得2）右側の述語の再配置による論理的な最適化3）単純化されたチェックの導入または不要な条件の削除の論理的な最適化4）カットオフによるヒューリスティックの導入と個々のケースの最適化

オプション1。並べ替えは単純です。並べ替えられた配列の最初の要素は最小限に抑え、残りの要素は並べ替える必要があります。最初の配列はソースで、2番目の配列はソートされたソースです。

  sort([], []). sort(List, [Min|SortRest]) :- min_list_exclude(Min, List, Exclude), sort(Exclude, SortRest). %%    ,        min_list_exclude(M, [M], []). min_list_exclude(Min, [M|L], ExcludeRes) :- min_list_exclude(Ms, L, Exclude), find_result(result(M, L), result(Ms, [M|Exclude]), result(Min, ExcludeRes)). %%         find_result(result(M, L), result(Ms, _), result(M, L)):- M < Ms. find_result(result(M, _), result(Ms, Exclude), result(Ms, Exclude)):- Ms =< M.

このアルゴリズムの複雑さは二次関数であり、主な問題は、有用な情報を保存せずに最小要素を探すたびに発生することに気付くかもしれません。

また、ソートされた配列の最初の要素が何であるかを決定しようとしていることに注意してください。

オプション2.クイックソート。 問題を2番目の側から見て、ソートされた配列内のリストの最初の要素の位置を決定してみましょう（元の配列に再帰を適用します）。

  sort_b([], []). sort_b([T|R], List) :- split(T, R, Less, Great), sort_b(Less, LessSort), sort_b(Great, GreatSort), append(LessSort, [T|GreatSort], List). %%    2     split(_, [],[], []). split(T, [M|R],[M|Less], Great) :- M < T, split(T,R, Less,Great). split(T, [M|R],Less, [M|Great]) :- M >= T, split(T,R, Less,Great). %%  2  append([], M, M). append([L|Left], Right, [L|Res]) :- append(Left, Right, Res).

クイックソートはバブルソートよりも確実に高速であるため、ソート結果が改善されていることに気付くでしょう。結果をさらに改善するために、マージソートを思い出すことができます。マージソートはいずれの場合もO（n lg n）を返しますが、残念ながらこのソートは配列のみに適用され、作業するリンクリストには適用されません。ストレージに追加のデータ構造を使用する唯一のオプションはツリーです。

オプション3.バイナリツリーを使用した並べ替え。

この種のソートでは、元のリストをバイナリツリーに変換し、左側のツリートラバーサルを使用して、ソートされた配列を取得します。ツリーは、再帰用語ツリー（Object、LeftSubTree、RightSubTree）で表されます。

  sort_tree([], nil). sort_tree([X|L], Tree) :- sort_tree(L, LTree), plus(X, LTree, Tree). %%      plus(X, nil, tree(X, nil, nil)). plus(X, tree(O, L, R), tree(O, ResL, R)) :- O >= X, plus(X, L, ResL). plus(X, tree(O, L, R), tree(O, L, ResR)) :- O < X, plus(X, R, ResR). sort_t(X, Y) :- sort_tree(X, Tree), tree_list(Tree, Y). append_list([], L, L). append_list([X|L], R, [X|T]) :- append_list(L, R, T). tree_list(nil, []). tree_list(tree(X, L, R), List) :- tree_list(L, ListL), tree_list(R, ListR), append_list(ListL, [X|ListR], List).

オプション4.平衡二分木を使用したソート。

バイナリツリーを使用する問題は、クイックソートを使用する場合と同じです。この方法は、最適なパフォーマンスを保証するものではありません。二分木の場合、木は不均衡である可能性があり、要素を追加する手順は対数ではなく線形にすることができます。特にこのために、ツリーバランシング手順が実行されます。以下では、慣れるために、 AVLツリーを使用したアルゴリズムを示します。

  sort_btree(X, Y) :- sort_tree(X, Tree), tree_list(Tree, Y). tree_list(nil, []). tree_list(tree(X, L, R, _), List) :- tree_list(L, ListL), tree_list(R, ListR), append(ListL, [X|ListR], List). sort_tree([], nil). sort_tree([X|L], Tree) :- sort_tree(L, LTree), plus_tree(X, LTree, Tree). construct_tree(A, AL, AR, tree(A, AL, AR, ADepth)) :- diff(AL, AR, _, ADepth). diff(AL, AR, ADiff, ADepth) :- depth_tree(ALs, AL), depth_tree(ARs, AR), ADiff is ALs - ARs, max_int(ALs, ARs, AD), ADepth is AD + 1. max_int(A, B, A) :- A > B. max_int(A, B, B) :- A =< B. append([], L, L). append([X|L], R, [X|T]) :- append(L, R, T). depth_tree(0, nil). depth_tree(X, tree(_, _, _, X)). plus_tree(X, nil, tree(X, nil, nil, 1)). plus_tree(X, tree(O, L, R, _), Res) :- O >= X, plus_tree(X, L, ResL), diff(ResL, R, Diff, Dep), balance_tree(tree(O, ResL, R, Dep), Diff, Res). plus_tree(X, tree(O, L, R, _), Res) :- O < X, plus_tree(X, R, ResR), diff(L, ResR, Diff, Dep), balance_tree(tree(O, L, ResR, Dep), Diff, Res). %% No rotations balance_tree(Tree, ADiff, Tree) :- ADiff < 2, ADiff > -2. %% Small right rotation balance_tree(tree(A, tree(B, BL, BR, _), AR, _), ADiff, Result) :- ADiff > 1, diff(BL, BR, BDiff, _), BDiff >= 0, construct_tree(A, BR, AR, ASubTree), construct_tree(B, BL, ASubTree, Result). %% Big right rotation balance_tree(tree(A, tree(B, BL, BR, _), AR, _), ADiff, Result) :- ADiff > 1, diff(BL, BR, BDiff, _), BDiff < 0, BR = tree(C, CL, CR, _), construct_tree(B, BL, CL, BSubTree), construct_tree(A, CR, AR, ASubTree), construct_tree(C, BSubTree, ASubTree, Result). %% Small left rotation balance_tree(tree(A, AL, tree(B, BL, BR, _), _), ADiff, Result) :- ADiff < -1, diff(BL, BR, BDiff, _), BDiff =< 0, construct_tree(A, AL, BL, ASubTree), construct_tree(B, ASubTree, BR, Result). %% Big left rotation balance_tree(tree(A, AL, tree(B, BL, BR, _), _), ADiff, Result) :- ADiff < -1, diff(BL, BR, BDiff, _), BDiff > 0, BL = tree(C, CL, CR, _), construct_tree(B, CR, BR, BSubTree), construct_tree(A, AL, CL, ASubTree), construct_tree(C, ASubTree, BSubTree, Result).

この例は、Prologでの実装には十分な表現力がありませんが、中規模のプログラムのアイデアを提供します。トレーニングのために、バブルソートまたは挿入によるソートを実装できます。これは読者の裁量に任されています。

例5-輸血の問題。

次のタスクとして、古典的な状態の問題を検討してください;このタスクは、Prologを使用する利点をはるかによく反映しています。問題の一般的な声明：水の入ったいくつかの容器がある場合、輸血によって特定の容器に一定量の水を得ることが必要です。たとえば、容量が12リットル、8リットル、5リットルの水差しを3つ用意し、最初の水差し、つまり12リットルを完全に満たし、タスクを6リットルに設定します。 まず、ペンと紙でこの学校の問題を解決してみてください :)

さまざまなアルゴリズムを生成してタスクに適用する前に、まずPrologの観点から条件を書き直しましょう。容量をsosud（Id、MaximumCapacity、CurrentCapacity）という用語として説明し、システムの状態を容量のリストとして説明します。例[sosud（1、12、12）、sosud（2、8、0）、sosud（3、5、0）] 。次に、リクエストについて説明します。

  %% solve_pr_wo(InitialState, Goal, Steps). :- solve_pr_wo([sosud(1, 12, 12), sosud(2, 8, 0), sosud(3, 5, 0)], sosud(X, _, 6), Steps).

目標= sosud（_、_、6）であることに注意してください。つまり、正確に6リットルを含むように、船の容量は重要ではありません。

これですべてがわかったので、ステップがSteps変数で指定されていると仮定して、ソリューションを検証する方法を説明します。

  %%        , %%        solve_pr_wo(State, Goal, []) :- member(Goal, State). %%      Sosud  Sosud2    %%   ResSosud,   ResSosud2. %%    : %% mv(sosud(1, 12, 12) -> sosud(2, 8, 0), sosud(1, 12, 4) -> sosud(2, 8, 8)). solve_pr_wo(State, Goal, [mv(Sosud -> Sosud2 , ResSosud -> ResSosud2)| Steps]) :- %%     ,    %%           member(Sosud, State), member(Sosud2, State), not(Sosud = Sosud2), %%   ,  %%   4   mv(Sosud, Sosud2, ResSosud, ResSosud2), %%         replace(Sosud, State, ResSosud, State2), replace(Sosud2, State2, ResSosud2, StateX), %%       solve_pr_wo(StateX, Goal, Steps). %%         %% replace(ElementToReplace, InList, ElementToReplaceWith, OutList). replace(S, [S|L], X, [X|L]). replace(S, [T|L], X, [T|Ls]) :- replace(S, L, X, Ls). %%   - 2  %%        %%      mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, 0), sosud(Id2, Max2, Current3)) :- Current > 0, Current3 is Current2 + Current, Current3 =< Max2. %%        mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, Current3), sosud(Id2, Max2, Max2)) :- Current > 0, Current3 is Current2 + Current - Max2, Current3 >= 0.

さらに、輸血の手順が正しい場合は、それらが説明する内容を確認できないため、ドメインの検証は必要ないように思われるかもしれません。実際、検証の完全性は、プログラムが正しく収益を上げる可能性を大幅に向上させます。そうは言っても、プログラムを過剰にチェックすると機能し、場合によっては最適化しない場合よりもさらに最適化されますが、プログラムのチェックが不十分な場合、完全に誤った結果が生成されたり、一部の入力データでフリーズします。

さて、プログラムの説明が書かれています-あなたはそれを実行することができます。プログラムが機能しないことに驚かないでください、単にハングします:)これは見た目ほど悪くありません。プログラムがハングしなかった場合、それは正しい答えを与えるからです。なぜハングしたのかを理解する必要があります。ここで、Prologがルールを展開して解決策を見つける方法を理解するのに役立ちます。実際、solve_pr_wo-> solve_pr_woを再帰的に呼び出すたびに、2つのメンバー/ 2つの述語を呼び出し、常に同じ1番目と2番目を生成することを理解するために、最大10個の戻り点を記憶できる頭を持つ必要はありません2番目の船（述部はバックトラッキングを引き起こさず、メンバーが1番目と1番目の船を選択することを許可しません）。つまり、アルゴリズムは常に第1から第2に、およびその逆に流れます。

この不条理を解決するために、同じアクションを2回実行することを禁止すること、つまり、状態の履歴を保持し、条件がすでに満たされている場合は再入力を禁止することがすぐに思い浮かびます。繰り返しを除き、多くの許容可能な輸血戦略を絞り込むことがわかりました。実際、戦略のセットを絞り込んでも、システムの許容可能な状態のセット、つまり解法は絞り込みませんが、これは証明することは難しくありません。

状態のリストとソリューションを呼び出す単一の述語を含むプログラムのフルバージョン：

  write_list([]). write_list([X|L]) :- writeln(X), write_list(L). solution :- solve_pr([sosud(1, 12, 12), sosud(2, 8, 0), sosud(3, 5, 0)], sosud(_, _, 6), [], Steps), write_list(Steps). replace(S, [S|L], X, [X|L]). replace(S, [T|L], X, [T|Ls]) :- replace(S, L, X, Ls). %%       ,     %%     ,   ,     solve_pr(State, Goal, _, [State]) :- member(Goal, State). solve_pr(State, Goal, History, [State|Steps]) :- member(Sosud, State), member(Sosud2, State), not(Sosud = Sosud2), mv(Sosud, Sosud2, ResSosud, ResSosud2), replace(Sosud, State, ResSosud, State2), replace(Sosud2, State2, ResSosud2, StateX), %%%      not(member(StateX, [State|History])), solve_pr(StateX, Goal, [State|History], Steps). %% mv(sosud(_Id, Max, Current), sosud(_Id2, Max2, Current2), ...,...). %%      mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, 0), sosud(Id2, Max2, Current3)) :- Current > 0, Current3 is Current2 + Current, Current3 =< Max2. %%        mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, Current3), sosud(Id2, Max2, Max2)) :- Current > 0, Current3 is Current2 + Current - Max2, Current3 >= 0.

すべてが現在機能しています！演習として、最適なステップ数で輸血を見つけるようにプログラムを変更できます。これらのタスクを試すことができます。

注：命令型プログラミングの熱心なサポーターは、すべての状態を戻り値（深さのパス）で反復するだけであり、ヒューリスティックを使用せずに完全に正しいことに気付くでしょう。事実、Prologでの思考は、総当たりで行うのではなく、問題の説明とソリューションの検証の説明で行う必要があり、必要な場合は常に最適化のために計算の必須性に戻る必要があります！自然の二重性はマイナスではなく、プラスです。また、大規模なPrologシステムは、リターンのある状態を検索するのに非常によく適合していることにも注意してください。

おわりに

この記事で説明するタスクは、Prologでのプログラミングの研究です。それらのほとんどは約10〜15行かかるため、Prologのプログラマは十分な頻度でそれらをメモリから再現できます。そして、あなたは間違いなくそれらに戻らなければなりません。これはプログラミングの技術を思い起こさせるからです（Cでのクイックソートのように）。毎日の使用のためのより複雑で適用されたタスクについては、後で説明します。

最後に、賞品にはすでに2つのタスクがあります 。

ご存じのように、機能的および論理的な方法で、あらゆる方法で副作用のあるプログラムを避け、モナドにラップし、特別な概念を考え出します。標準的な問題は、外界の問題です。たとえば、ファイルへのデータの書き込み、ファイルへの記録のロールバック、ソケットによる数バイトの送信のキャンセルが不可能であるため、バックトラッキングは正しく機能しません。 1つのアドバイス-これらの目的にPrologを使用しないでください。しかし、Prologに非常に適した特定の述語がありますが、副作用があります。 assert（asserta、assertz）の例：ルール（ファクト）データベースに単純なルール（ファクト）を追加します。 assert（prime（3））の例 ：3が素数であるという事実とクエリ：-prime（X）は、ソースプログラムが空であっても3を返すようになりました。

目的： assertの宣言バージョンを記述します。つまり、バックトラッキングプログラムを返すとき、事実はメモリに残しておくべきではなく、論理的な仮定として機能する必要があります。

操作例 ：クエリc（X）は、次のプログラムに対して1つの数値4を返す必要があります！
```
  a(X) :- b(Y), X is Y + 1 . c(X) :- my_assert(b(3)), a(X). c(X) :- b(X).
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     
```

2 , — . , . , — , — . , — . , , — .

: a/1 ( , ), subset_a/1, , a.

: subset_a(X) X = [], X = [1], X = [2], X = [1, 2] ( ):

  a(1). a(2). subset_a(X) :- ....?

ご清聴ありがとうございました。

プロローグ-ケーススタディ（パート2）