opened
tilk
username_0
'((x . 1))
```
Substitutions are not rolled back after cut/%not
issue
created
jeapostrophe
username_1
Hi Marek,

I don't know any way to change this behavior without violating my unit
tests. I suspect that this is the correct behavior, but I'm not sure.

(%not G) is defined as (%if-then-else G %fail %true) which
is (%cut-delimiter (%or (%and G ! %fail) %true))

That means that after G has been evaluated, and the cut point is reached,
we are committed to its conclusions, meaning that we are committing to X
being 1 in your example. In contrast, if you wrote the following:

(%which (x) (%or (%cut-delimiter (%or (%and ! (%= x 1) %fail) %true))
%true))
   => '((x . _))

Then the cut point would be before you set X to be 1, so the set would be
reverted.

So, I believe this is the correct, although unintuitive, behavior.

Is there something I'm not getting?

Jay
comment
created
tilk
username_0
The behavior of cut is different to the behavior of cut in Prolog. In particular, it breaks the common double negation idiom. The double negation idiom in Prolog allows to check if the given goal can be satisfied in the current substitution, without altering it. In particular, you have:

```prolog
?- \+ \+ X = 1.
true.
?- \+ \+ X = 1, X = 2.
X = 2.
```

You are arguing that by using the cut in my example, you are committing to X being 1. Yes, we do, but only in the scope of the cut delimiter. When we backtrack outside the scope of the cut delimiter, we should no longer care what happened inside it, i.e. every substitution made inside should be reverted. In practical terms: cut should drop alternative branches created between the delimiter and the cut, but it should not drop reverting the substitution back to its original form before the delimiter was entered. This is what Prolog does.

```prolog
?- \+ X = 1 ; true.
true.
```

I wonder what would be the best implementation strategy. The traditional Prolog implementation, the Warren Abstract Machine, handles this by managing something called a trail, which is essentially a stack of bindings which need to be reverted upon backtracking. The cut operator discards choice points, but does not alter the trail.
comment
created
jeapostrophe
username_1
I agree that `cut` in Racklog is behaving different than Prolog.

Above all, Racklog is an implementation of Matthias Felleisen's “Transliterating Prolog into Scheme,” Indiana U Comp Sci Dept Tech Report #182, 1985 that is based on Dorai Sitaram's Schelog (https://username_3.github.io/schelog/index.html)

I think I am bound to maintain compatibility with this strategy and implementation that is now over 30 years old, even though it is not the best way to do Prolog-like programming.

I think you want a better Prolog-style engine in Racket, rather than something that is really defined by this embedding strategy. If so, I think my "parenlog" implementation might be a good place to start. It is a lot simpler than Racklog (although it doesn't have cut, I think it would be a lot easier to add.)

I wonder what @username_2 would say about this thread.
comment
created
mfelleisen
username_2
My Prolog embedding used a trail, which is really an undo list, to which the fail continuation returned. Cut was set up the same way. I was able to run many of my old Prolog programs back then, but I never maintained this and it never covered all of Prolog the way Dorai’s Schelog, now Racklog does. 

Dorai ( @username_3 ) do you know why the behaviors differ?
comment
created
ds26gte
username_3
Noted. I'll get back when I get some debug time.
comment
created
tilk
username_0
Just for the record: I'm teaching (with Maciej Piróg and Filip Sieczkowski) an introductory course on programming languages at the University of Wrocław, and Racket is our language of choice (part of the course is based on SICP). I decided to use Racklog to explain the concepts behind logic programming (backtracking and unification), and I believe it went well. I wanted to present cut and negation to some better students, but I decided not to because of this issue.
comment
created
ds26gte
username_3
First of all, thank you to @username_0 for bringing this up. I'm persuaded that a fix is preferable to trying to retain legacy behavior. After playing around with it for admittedly a short while, I also think there is very little fear that correct problem-solving programs (as opposed to specially written unit tests) will rely on legacy behavior being preserved.  

I've updated Schelog to username_3/schelog@8d496f4 addressing this issue. This is clearly a big change: Schelog never attempted to do trail unwinding before and I'm modifying code written very long ago. I tried @username_0's examples and I'd appreciate if the respondents here try other tests.

I haven't tackled the task of updating Racklog too: I'm sure @username_1 and/or whoever else has been maintaining Racklog will be able to do it more reliably than I can, of course after testing my Schelog changes for correctness and filing issues as needed.

Running tests on Schelog is simple: Start Racket, load `"schelog.scm"` and throw tests at it.
comment
created
jeapostrophe
username_1
#f
```

I think that is incorrect. I could fix it by changing line 342 to a normal continuation (not a failure continuation.)

@username_0 It should all be fixed now. I've added your tests to the repo for regressions.
comment
closed
jeapostrophe
username_1
issue