In Prolog's terms, condA
is "soft cut", *->
, and condU
is "committed choice" – a combination of once
and a soft cut, so that (once(A) *-> B ; false)
expresses the cut in (A, !, B)
:
A *-> B ; C %% soft cut, condA
once(A) *-> B ; C %% committed choice, condU
In condA
, if the goal A
succeeds, all the solutions are passed through to the first clause B
and no alternative clauses C
are tried. once/1
allows its argument goal to succeed only once (keeps only one solution, if any).
condE
is a simple disjunction, and condI
is a disjunction which alternates between the solutions of its constituents.
Here's an attempt at faithfully translating the book's code, w/out logical variables and unification, into 18 lines of Haskell (where juxtaposition is curried function application, and :
means cons). See if this clarifies things:
- Sequential stream combination ("
mplus
" of the book):
(1) [] ++: ys = ys
(2) (x:xs) ++: ys = x:(xs ++: ys)
- Alternating stream combination ("
mplusI
"):
(3) [] ++/ ys = ys
(4) (x:xs) ++/ ys = x:(ys ++/ xs)
- Sequential feed ("
bind
"):
(5) [] >>: g = []
(6) (x:xs) >>: g = g x ++: (xs >>: g)
- Alternating feed ("
bindI
"):
(7) [] >>/ g = []
(8) (x:xs) >>/ g = g x ++/ (xs >>/ g)
- "
OR
" goal combination ("condE
"):
(9) (f ||: g) x = f x ++: g x
- "Alternating
OR
" goal combination ("condI
"):
(10) (f ||/ g) x = f x ++/ g x
- "
AND
" goal combination ("all
"):
(11) (f &&: g) x = f x >>: g
- "Alternating
AND
" goal combination ("allI
" of the book):
(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
Goals produce streams (possibly empty) of (possibly updated) solutions, given a (possibly partial) solution to a problem.
Re-write rules for all
are:
(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 &&/ ... ))
Re-write rules for condX
are:
(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 ...) (...) ))
To arrive at the final condE
and condI
's translation, there's no need to implement the book's ifE
and ifI
, since they reduce further to simple operator combinations, with all the operators considered to be right-associative:
(condE (g1 g2 ...) (h1 h2 ...) ...) =
(g1 &&: g2 &&: ... ) ||: (h1 &&: h2 &&: ...) ||: ...
(condI (g1 g2 ...) (h1 h2 ...) ...) =
(g1 &&: g2 &&: ... ) ||/ (h1 &&: h2 &&: ...) ||/ ...
So there's no need for any special "syntax" in Haskell, plain operators suffice. Any combination can be used, with &&/
instead of &&:
if needed. But OTOH condI
could also be implemented as a function to accept a collection (list, tree etc.) of goals to be fulfilled, that would use some smart strategy to pick of them one most likely or most needed etc, and not just simple binary alternation as in ||/
operator (or ifI
of the book).
Next, the book's condA
can be modeled by two new operators, ~~>
and ||~
, working together. We can use them in a natural way as in e.g.
g1 ~~> g2 &&: ... ||~ h1 ~~> h2 &&: ... ||~ ... ||~ gelse
which can intuitively be read as "IF g1 THEN g2 AND ... OR-ELSE IF h1 THEN ... OR-ELSE gelse
".
- "
IF-THEN
" goal combination is to produce a "try" goal which must be called with a failure-continuation goal:
(15) (g ~~> h) f x = case g x of [] -> f x ; ys -> ys >>: h
- "
OR-ELSE
" goal combination of a "try" goal and a simple goal simply calls its "try" goal with a second, on-failure goal, so it's nothing more than a convenience syntax for automatic grouping of operands:
(16) (g ||~ f) x = g f x
If the ||~
"OR-ELSE
" operator is given less binding power than the ~~>
"IF-THEN
" operator and made right-associative too, and ~~>
operator has still less binding power than &&:
and the like, sensible grouping of the above example is automatically produced as
(g1 ~~> (g2 &&: ...)) ||~ ( (h1 ~~> (h2 &&: ...)) ||~ (... ||~ gelse)...)
Last goal in an ||~
chain must thus be a simple goal. That's no limitation really, since last clause of condA
form is equivalent anyway to simple "AND
"-combination of its goals (or simple false
can be used just as well).
That's all. We can even have more types of try-goals, represented by different kinds of "IF
" operators, if we want:
- use alternating feed in a successful clause (to model what could've been called
condAI
, if there were one in the book):
(17) (g ~~>/ h) f x = case g x of [] -> f x ; ys -> ys >>/ h
- use the successful solution stream only once to produce the cut effect, to model
condU
:
(18) (g ~~>! h) f x = case g x of [] -> f x ; (y:_) -> h y
So that, finally, the re-write rules for condA
and condU
of the book are simply:
(condA (g1 g2 ...) (h1 h2 ...) ...) =
g1 ~~> g2 &&: ... ||~ h1 ~~> h2 &&: ... ||~ ...
(condU (g1 g2 ...) (h1 h2 ...) ...) =
g1 ~~>! g2 &&: ... ||~ h1 ~~>! h2 &&: ... ||~ ...