31

ReasonedSchemerを読んでいます。

私はどのように機能するかについていくつかの直感を持っていますconde。

しかし、私は///が何をするかについての正式な定義を見つけることができcondeませcondaん。conducondi

https://www.cs.indiana.edu/~webyrd/を知っていますが、定義ではなく例があるようです。

conde、、、の正式な定義はどこかcondaにありますか？condicondu

4

4 に答える 4

53

プロローグで言えば、

  • condA「ソフトカット 」と*->も呼ばA *-> B ; Cれ(A, B ; not(A), C)ます。一方

  • condUは「コミットされた選択」であり、 と の組み合わせでonceあり、次のように(once(A) *-> B ; false)表現されます(A, !, B)(カットが内側にある場合):

condA:     A        *->  B  ;  C        %  soft cut,
                                        %     (A ,    B ; not(A) , C)
condU:     once(A)  *->  B  ;  C        %  committed choice,
                                        %     (A , !, B ; not(A) , C)

( 「または」の;意味と「および」の意味、つまり、それぞれ目標の分離と結合)。,

ではcondA、ゴールAが成功した場合、すべての解が最初の句に渡され、B代替句Cは試行されません。

ではcondU、once/1その引数のゴールが 1 回だけ成功することを許可します (解があれば 1 つだけ保持します)。

condEは接続詞の単純な選言であり、その構成要素の解の間を交互に行き来し、その流れをインターリーブcondIする選言です。

これは、本書のコードを、論理変数と統合を除いて、18 行の Haskell に忠実に翻訳する試みです。これは、ほとんどが構文の怠惰な Lispです。( * )これで問題が解決するかどうかを確認してください:

  • シーケンシャル ストリームの組み合わせ (mplus本の「 」):
    (1)   []     ++: ys  =  ys
    (2)   (x:xs) ++: ys  =  x : (xs ++: ys)

  • 代替ストリームの組み合わせ (" mplusI"):

      (3)   []     ++/ ys  =  ys
  (4)   (x:xs) ++/ ys  =  x : (ys ++/ xs)

  • 順次送り (" bind"):

      (5)   []     >>: g  =  []
  (6)   (x:xs) >>: g  =  g x ++: (xs >>: g)

  • 交互送り (" bindI"):

      (7)   []     >>/ g  =  []
  (8)   (x:xs) >>/ g  =  g x ++/ (xs >>/ g)

  • " OR"目標の組み合わせ (" condE"):

      (9)   (f ||: g) x  =  f x ++: g x

  • "交互OR" の目標の組み合わせ (" condI"):

      (10)  (f ||/ g) x  =  f x ++/ g x

  • " AND" 目標の組み合わせ (" all"):

      (11)  (f &&: g) x  =  f x >>: g

  • 「交互AND」allIの目標の組み合わせ (本の「 」):

      (12)  (f &&/ g) x  =  f x >>/ g

  • スペシャルゴール

      (13)  true  x  =  [x]  -- a sigleton list with the same solution repackaged
  (14)  false x  =  []   -- an empty list, meaning the solution is rejected

目標は、問題に対する (おそらく部分的な) 解決策が与えられた場合に、(おそらく更新された) 解決策のストリーム (おそらく空の) を生成します。

の書き換えルールは次のallとおりです。

(all)      =  true
(all  g1)  =  g1
(all  g1 g2 g3 ...)  =  (\x -> g1 x >>: (all g2 g3 ...))
                     =  g1 &&: (g2 &&: (g3 &&: ... ))
(allI g1 g2 g3 ...)  =  (\x -> g1 x >>/ (allI g2 g3 ...))
                     =  g1 &&/ (g2 &&/ (g3 &&/ ... ))

の書き換えルールは次のcondXとおりです。

(condX)  =  false
(condX (else g1 g2 ...))  =  (all g1 g2 ...)  =  g1 &&: (g2 &&: (...))
(condX (g1 g2 ...))       =  (all g1 g2 ...)  =  g1 &&: (g2 &&: (...))
(condX (g1 g2 ...) (h1 h2 ...) ...)  =  (ifX g1 (all g2 ...) 
                                          (ifX h1 (all h2 ...) (...) ))

condEandの最終的なcondI翻訳に到達するために、本のifEandを実装する必要はありません。なぜなら、それらは単純な演算子の組み合わせにさらに還元され、すべての演算子が右結合ifIであると見なされるからです。

(condE (g1 g2 ...) (h1 h2 ...) ...)  =
     (g1 &&: g2 &&: ... )  ||:  (h1 &&: h2 &&: ...)  ||:  ...
(condI (g1 g2 ...) (h1 h2 ...) ...)  =
     (g1 &&: g2 &&: ... )  ||/  (h1 &&: h2 &&: ...)  ||/  ...

したがって、Haskell では特別な「構文」は必要なく、単純な二項中置演算子で十分です。任意の組み合わせをどこでも使用でき、必要に応じて&&/代わりに使用でき&&:ます。しかし一方condIで、達成される目標のコレクション（リスト、ツリーなど）を受け入れる関数として実装することもできます。これは、スマートな戦略を使用して、最も可能性が高い、または最も必要なものなどを選択します。||/演算子 (または本) のような単純な二項交替ifI。

次に、本は2 つの新しい演算子とが協力してcondAモデル化できます。たとえば、自然な方法でそれらを使用できます~~>||~

g1 ~~> g2 &&: ...  ||~  h1 ~~> h2 &&: ...  ||~  ...  ||~  gelse

これは直観的に " IF g1 THEN g2 AND ... OR-ELSE IF h1 THEN ... OR-ELSE gelse" と読むことができます:

  • " IF-THEN" ゴールの組み合わせは、失敗と継続のゴールで呼び出されなければならない"try"ゴールを生成することです:

      (15)  (g ~~> h) f x  =  case g x of [] -> f x  ;  ys -> ys >>: h

  • " " tryゴールと単純なゴールOR-ELSEのゴールの組み合わせは、2 番目の失敗時のゴールでそのtryゴールを呼び出すだけなので、オペランドを自動的にグループ化するための便利な構文にすぎません。

      (16)  (g ||~ f) x  =  g f x

" OR-ELSE"演算子は " "||~演算子よりも束縛力が低く、右結合もされており、演算子などよりもさらに束縛力が弱いため、上記の例の賢明なグループ化は次のように自動的に生成されます。IF-THEN~~>~~>&&:

(g1 ~~> (g2 &&: ...))  ||~  ( (h1 ~~> (h2 &&: ...))  ||~  (...  ||~  gelse ...) )

||~したがって、チェーンの最後のゴールは単純なゴールでなければなりません。condAformの最後の句は単純な " AND" - その目的の組み合わせと同等であるため (または単純なfalseも同様に使用できるため)、これは実際には制限ではありません。

それで全部です。必要に応じて、さまざまな種類の " " 演算子で表されるより多くの種類のtryゴールを使用することもできます。IF

  • 成功した句で交互フィードを使用します（condAI本に1つあった場合、 と呼ばれていた可能性のあるものをモデル化するため）：

      (17)  (g ~~>/ h) f x  =  case g x of [] -> f x  ;  ys -> ys >>/ h

  • 成功したソリューション ストリームを 1回だけ使用して、カット効果を生成し、モデル化しcondUます。

      (18)  (g ~~>! h) f x  =  case g x of [] -> f x  ;  (y:_) -> h y

condA最後に、この本の書き直しルールはcondU次のとおりです。

(condA (g1 g2 ...) (h1 h2 ...) ...)  = 
      g1 ~~> g2 &&: ...  ||~  h1 ~~> h2 &&: ...  ||~  ... 

(condU (g1 g2 ...) (h1 h2 ...) ...)  = 
      g1 ~~>! g2 &&: ...  ||~  h1 ~~>! h2 &&: ...  ||~  ...

( * )つまり:

  • 単純な並置はカリー化機能適用、
    f a b c =~= (((f a) b) c) =~= f(a, b, c)
  • (\ a -> b )はラムダ関数、 (lambda (a) b)
  • foo x = yのショートカットですfoo = (\ x -> y )
  • a @@ b = yのショートカット(@@) a b = y、中置演算子の定義です@@
  • 括弧( )は単にグループ化するためのものです
  • []は空のリストであり、
  • :consを意味します-- 両方のコンストラクタとして ( lazy、言語全体がlazyであるため、つまり、必要に応じて呼び出す)、in 定義の右側にあります。左側(またはパターン マッチング式内)の分割パターン=として。case
于 2012-06-01T10:51:04.557 に答える
15

Reasoned Schemer は、conda (ソフト カット) とcondu (コミットされた選択) をカバーしています。また、William Byrd のminiKanren に関する優れた論文にも、それらの動作の説明があります。この投稿は、core.logic に関するものとしてタグ付けされています。明確にするために、core.logic は The Reasoned Schemer で提示されたものよりも新しいバージョンの miniKanren に基づいています。miniKanren は常に選言ゴールをインターリーブします - condi とインターリーブの変種はもはや存在しません。コンデ は コンデになりました。

于 2012-06-01T12:34:35.790 に答える
2

例では、core.logic を使用します。

conde はすべてのグループを実行し、少なくとも 1 つのグループが成功した場合に成功し、成功したすべてのグループからすべての結果を返します。

user>  (run* [w q]
                (conde [u#]
                       [(or* [(== w 1) (== w 2)])
                        (== q :first)]
                       [(== q :second)]))
([_0 :second] [1 :first] [2 :first])

conda と condu: どちらも最初に成功したグループの後に停止します (上から下へ)

condaは、最初に成功したグループのみからすべての結果を返します。 

user> (run* [w q]
                (conda [u#]
                       [(or* [(== w 1) (== w 2)])
                        (== q :first)]
                       [(== q :second)]))
([1 :first] [2 :first])

conduは、最初に成功したグループのみから 1 つの結果のみを返します。

user> (run* [w q]
                (condu [u#]
                       [(or* [(== w 1) (== w 2)])
                        (== q :first)]
                       [(== q :second)]))
([1 :first])

ただし、condiが何をするのかわかりません。

于 2016-12-31T18:08:05.200 に答える
0

ISO Prolog コア標準によると、(,)/2、(;)/2、(->)/2 などの制御構造は透明にカットされます。(*->)/2 は ISO Prolog コア標準にはありませんが、通常、Prolog システムはカット トランスペアレントも実装します。

これは翻訳できないことを意味します:

once(A) *-> B;C

にA, !, B; C。後者は他の制御構造に埋め込まれている可能性があり、それらの間に選言がある場合、これらの選択ポイントも切り取られます。一方、合理的に見えるものはA -> B; C、

単に ISO Prolog コア標準if-then-elseとして知られています。このように定義されたカットの動作は、たとえば、例外をスローせずに繰り返しループから抜け出すのに役立ちます。通常のプログラミング パターンは、if-then-else でアーカイブするのがより困難です。

于 2019-04-12T14:48:40.413 に答える