conda, condi, conde, condu

Question

Sto leggendo the Reasoned Schemer.

Ho qualche intuizione su come funziona conde.

Tuttavia, non riesco a trovare una definizione formale di ciò che conde/conda/condu/condi fanno.

Sono a conoscenza di https://www.cs.indiana.edu/~webyrd/ ma sembra avere esempi piuttosto che definizioni.

Esiste una definizione formale di conde, conda, condi, condu da qualche parte?

Answer 1

In termini di Prolog, condA è "taglio soft", *->, e condU è "scelta impegnati" – una combinazione di once e un taglio morbido, in modo che (once(A) *-> B ; false) esprime il tagliare in (A, !, B):

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

In condA, se l'obiettivo A ha esito positivo, tutte le soluzioni vengono passate alla prima clausola B e non vengono provate clausole alternative C. once/1 consente al suo argomento obiettivo di riuscire una sola volta (mantiene solo una soluzione, se presente).

condE è un semplice disgiunzione, e condI è una disgiunzione che alterna tra le soluzioni dei suoi costituenti.

---

Ecco un tentativo di tradurre fedelmente codice del libro, w/out variabili logiche e unificazione, in 18 righe di Haskell (dove giustapposizione è un'applicazione funzione curry, e : significa cons).Vedere se questo chiarisce le cose:

• sequenziale flusso di combinazione ("mplus "del libro):

(1) []  ++: ys = ys 
    (2) (x:xs) ++: ys = x:(xs ++: ys) 

• flusso combinazione alternata (" mplusI"):

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

• avanzamento sequenziale ("bind "):

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

• alimentazione alternata (" bindI"):

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

• "OR" obiettivo combinazione ("condE "):

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

• "Alternando OR" combinazione obiettivo (" condI"):

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

• "AND" combinazione obiettivo ("all "):

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

• "Alternando AND" combinazione obiettivo (" allI" del libro):

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

• obiettivi speciali

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

Reti flussi produrre (possibilmente vuoto) di soluzioni (eventualmente aggiornati), data una soluzione (eventualmente parziale) di un problema.

regole Ri-scrittura per all sono:

(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 &&/ ...)) 

regole Ri-scrittura per condX sono:

(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 ...) (...))) 

per arrivare alla finale condE e condI La traduzione, t qui c'è bisogno di attuare il libro ifE e ifI, dal momento che riducono ulteriormente a semplici combinazioni di operatore, con tutti gli operatori considerati destra-associativo:

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

Quindi non c'è bisogno di alcuna speciale "sintassi" in Haskell, gli operatori semplici sono sufficienti. È possibile utilizzare qualsiasi combinazione, con &&/ anziché &&: se necessario. Ma OTOH condI potrebbe anche essere implementato come una funzione per accettare una raccolta (elenco, albero ecc.) Degli obiettivi da soddisfare, che userebbe qualche strategia intelligente per sceglierne uno più probabile o più necessario ecc., E non solo semplice alternazione binaria come nell'operatore ||/ (o ifI del libro).

Avanti, del condA può essere modellato da due nuovi operatori, ~~> e ||~, che lavorano insieme libro. Possiamo usarli in modo naturale come ad es.

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

che può essere letto intuitivamente come "IF g1 THEN g2 AND ... OR-ELSE IF h1 THEN ... OR-ELSE gelse".

• "IF-THEN" combinazione obiettivo è quello di produrre un obiettivo "provare" che deve essere chiamato con un obiettivo mancato di continuazione:

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

• "OR-ELSE" obiettivo combinazione di una "prova "l'obiettivo e un obiettivo semplice si limitano a chiamare il suo obiettivo" try "con un secondo obiettivo in caso di errore, quindi non è altro che una sintassi di comodità per il raggruppamento automatico degli operandi:

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

Se l'operatore ||~ "OR-ELSE" è dato potenza meno vincolante rispetto all'operatore ~~> "IF-THEN" realizzando destra-associativo troppo, e ~~> operatore ha ancora meno vincolante potenza rispetto &&: e simili, raggruppamento sensibile del sopra esempio viene prodotto automaticamente come

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

Ultimo obiettivo in una catena ||~ deve quindi essere un obiettivo semplice.Questa non è una limitazione, dato che l'ultima clausola del modulo condA equivale comunque al semplice "AND" -combinazione dei propri obiettivi (o semplice false può essere utilizzato altrettanto bene).

Questo è tutto. Possiamo anche avere più tipi di try-obiettivi, rappresentati da diversi tipi di "IF" operatori, se vogliamo:

• destinati all'alimentazione degli animali alternata in una clausola di successo (per modellare quello che potrebbe essere stato chiamato condAI , se ci fosse uno nel libro):

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

• utilizzare il flusso di soluzione di successo solo una volta per produrre il tagliare effetto, per modellare condU:

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

In modo che, finalmente, le regole di ri-scrittura per condA e condU del libro sono semplicemente:

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

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

Answer 2

Lo Schema ragionato copre conda (soft cut) e condu (scelta impegnata). Troverai anche spiegazioni sul loro comportamento nell'eccellente dissertation on miniKanren di William Byrd. Hai taggato questo post come su core.logic. Per essere chiari, core.logic si basa su una versione più recente di miniKanren rispetto a quella presentata in The Reasoned Schemer. miniKanren è sempre interleaves obiettivi disgiuntivi - condi e le varianti di interleaving non esistono più. condeècondi ora.

Answer 3

con l'esempio, con core.logic:

conde verrà eseguito ogni gruppo, avere successo se almeno un gruppo riesce, e ritorno tutti i risultati di tutti i gruppi di successo.

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

Conda e condu: entrambi si fermerà dopo il primo gruppo di successo (dall'alto in basso)

Conda restituisce tutti i risultati solo il primo gruppo di successo.

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

condu restituisce un solo risultato da solo il primo gruppo di successo.

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

Non ho idea di cosa condi.