[racket] [bug?] Racklog cut differs from Prolog cut

This seems to have been enough for me to fix the problem.I'm about to
push a fix. Although I'm not totally confident in my solution.

Basically, Racklog [1] compiles

(%rel [arg-pattern subgoals ...] ...)

into

(let ([! fail-relation]) (%or (%and (unify args arg-pattern) subgoals ...) ...))

where ! is bound to the failure continuation that went into %or even
though it appears inside of the subgoal part.

So, Racklog was skipping the subsequent clauses of the relation, but
it was not un-doing the unification of the current clause.

I basically had to hack it so unify's failure continuation can be
called by a subgoal and then the fact that a cut is happening is
caught before going to the next clause... like:

(define cut? #f)
(%or (begin (when cut? (fail-relation)) (%and (unify args arg-pattern)
(let ([! (lambda () (set! cut? #t) fail-unify)]) (%and subgoals
...)))) ...)

This test case and all my existing ! test cases succeed... but I'm
scared it doesn't really work. Any other ! puzzles would be
appreciated.

Jay

1. Racklog is based on schelog version 2003-06-01. This problem exists
in that version of schelog too. I decided to check schelog's source:
Matthias' original paper "Transliterating Prolog into Scheme"
published in October 1985 (I was 4 months old when it was written...
at least when it was published.) It appears that the same problem is
there.

On Mon, Aug 13, 2012 at 12:48 PM, Matthias Felleisen
<matthias at ccs.neu.edu> wrote:
>
> The Prolog program looks like this (alpha renamed):
>
> a(X) :- b(X).
> a(Z) :- c(Z).
> b(1) :- !.
> b(2).
> c(2).
>
> 1. a(Y) unifies with [the head of] the first line, which gives us Y = X, and b(Y) as the goal.
> 2. b(Y) unifies with the third line, which gives us Y = 1.
> 3. Solution found: 1
> 4. Reject solution.
> 5. Backtracking on b fails due to prompt.
> 6. Backtrack on 2 and therefore on 1.
> 7. a(Y) unifies with the second line, which once again gives us Y = Z and c(Y) as the goal.
> 8. c(Y) unifies with the fourth line, which yields Y = 2.
>
> A cut is an exit continuation to the current relation that undoes local bindings.
>
> -- Matthias
>
>
>
>
>
> On Aug 13, 2012, at 2:15 PM, Jay McCarthy wrote:
>
>> Can you help me understand this example and why x should be 2? My
>> understanding of cut and prolog is that this should happen:
>>
>> a(X)                [X = _ ]
>> ---->
>> b(X) ; c(X)       [ X = _ ]
>> ---->
>> b(1) ; b(2); c(X) [ X = _ ]
>> ---->
>> X = 1; ! ; b(2) ; c(X)    [ X = _ ]
>> ---->
>> ! ; b(2) ; c(X)              [ X = 1 ]
>>
>> ! evaluates to succeed and then we get the X = 1 solution.
>>
>> But because we cut, the change to the X logic variable won't be
>> undone, so when we try we get to...
>>
>> b(2) ; c(X)
>> ----->
>> 1 = 2 ; c(X)
>> ---->
>> fail ; c(X)
>> ---->
>> c(X)
>> ---->
>> c(2)
>> ----->
>> 1 = 2
>> ---->
>> fail
>>
>> and never see that X = 2
>>
>> I must be wrong because you show that prologs actually give 2, but
>> could you help me see why?
>>
>> Jay
>>
>> On Sat, Aug 11, 2012 at 11:32 PM, Erik Dominikus
>> <erik.dominikus71 at gmail.com> wrote:
>>> Racket version:
>>>
>>> 5.2.
>>>
>>> Output of 'uname -a':
>>>
>>> Linux kire 2.6.32-41-generic #91-Ubuntu SMP Wed Jun 13 11:43:55 UTC 2012
>>> x86_64 GNU/Linux
>>>
>>> Symptom:
>>>
>>> In SWI Prolog (or any Prolog interpreter I think), querying a(X) gives
>>> X=1 and X=2. Racklog only gives x=1.
>>>
>>> How to reproduce:
>>>
>>> Download 'a.pl' (attached).
>>> Run 'prolog -f a.pl' (if using SWI Prolog).
>>> Enter 'a(X).'.
>>> Press ';' (semicolon) key until it prints false.
>>>
>>> Download 'a.rkt' (attached).
>>> Run 'racket a.rkt'.
>>>
>>> Expectation:
>>>
>>> Racklog gives x=1 and x=2.
>>>
>>>
>>> Thank you.
>>>
>>> ____________________
>>>  Racket Users list:
>>>  http://lists.racket-lang.org/users
>>>
>>
>>
>>
>> --
>> Jay McCarthy <jay at cs.byu.edu>
>> Assistant Professor / Brigham Young University
>> http://faculty.cs.byu.edu/~jay
>>
>> "The glory of God is Intelligence" - D&C 93
>> ____________________
>>  Racket Users list:
>>  http://lists.racket-lang.org/users
>



-- 
Jay McCarthy <jay at cs.byu.edu>
Assistant Professor / Brigham Young University
http://faculty.cs.byu.edu/~jay

"The glory of God is Intelligence" - D&C 93