clojure - 康达, 康迪, 康德, 康杜

Question

我正在阅读Reasoned Schemer。

我对如何conde工作有一些直觉。

但是，我找不到///做什么的conde正式定义conda。conducondi

我知道https://www.cs.indiana.edu/~webyrd/但这似乎有例子而不是定义。

某处有conde, conda, condi,的正式定义吗？condu

score 53 · Accepted Answer

用 Prolog 的话来说，

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

In condU,once/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 ...) (...) ))

为了得到最终的condEandcondI的翻译，没有必要实现本书的ifEand ifI，因为它们进一步简化为简单的运算符组合，所有运算符都被认为是右结合的：

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

所以在 Haskell 中不需要任何特殊的“语法”，简单的二进制中缀运算符就足够了。任何组合都可以在任何地方使用，&&/而不是&&:根据需要。但另一方面condI，也可以将其实现为接受要实现的目标集合（列表、树等）的函数，这将使用一些智能策略来选择最有可能或最需要的目标等，而不仅仅是||/运算符（或ifI书本）中的简单二元交替。

接下来，这本书condA可以由两个新的运算符~~>和||~一起建模。我们可以以自然的方式使用它们，例如

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

可以直观地理解为“ IF g1 THEN g2 AND ... OR-ELSE IF h1 THEN ... OR-ELSE gelse”：

" IF-THEN" 目标组合是产生一个“尝试”目标，必须用失败-继续目标来调用它：
```
  (15)  (g ~~> h) f x  =  case g x of [] -> f x  ;  ys -> ys >>: h
```
" OR-ELSE" 一个try目标和一个简单目标的目标组合只是将它的try目标与第二个失败时目标一起调用，因此它只不过是一种用于操作数自动分组的便捷语法：
```
  (16)  (g ||~ f) x  =  g f x
```

由于“ OR-ELSE”||~运算符的绑定能力低于“ IF-THEN”~~>运算符并且也具有右关联性，并且~~>运算符的绑定能力仍小于&&:等，因此自动生成上述示例的合理分组为

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

因此，链中的最后一个目标||~必须是一个简单的目标。这实际上没有限制，因为condAform 的最后一个子句无论如何都等同于简单AND的 " " - 其目标的组合（或者false也可以使用简单的）。

就这样。如果我们愿意，我们甚至可以有更多类型的try目标，由不同类型的 " " 运算符表示：IF

condAI在成功的子句中使用交替提要（如果书中有一个可以称为的模型）：
```
  (17)  (g ~~>/ h) f x  =  case g x of [] -> f x  ;  ys -> ys >>/ h
```
仅使用一次成功的解决方案流来产生剪切效果，以建模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 函数， (lambda (a) b)
foo x = y是捷径foo = (\ x -> y )
a @@ b = y(@@) a b = y是中缀运算符定义的快捷方式@@
括号( )仅用于分组
[]是空列表，并且
:表示cons - 作为构造函数（惰性，因为整个语言都是惰性的，即按需调用），在定义的右侧=；并作为解构模式，在左侧（或在模式匹配case表达式中）。

score 15 · Accepted Answer

Reasoned Schemer 涵盖conda（软切）和condu（承诺选择）。您还可以在 William Byrd关于 miniKanren 的优秀论文中找到对他们行为的解释。您已将此帖子标记为关于 core.logic。需要明确的是，core.logic 是基于 miniKanren 的更新版本，而不是 The Reasoned Schemer 中介绍的版本。miniKanren 总是交错分离目标 - condi和交错变体不再存在。conde现在 是 condi。

score 2 · Accepted Answer

例如，使用 core.logic：

conde 将运行每个组，如果至少一个组成功，则成功，并返回所有成功组的所有结果。

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仅从第一个成功组返回一个结果。

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

不知道 condi 做了什么。

score 0 · Accepted Answer

根据 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 归档。

clojure - 康达, 康迪, 康德, 康杜

4 回答 4

Related

Reference