Hi,
Using the EyeProlog example code, I get this
result in a ISO compliant Prolog processor.
The predicate turns out to be non-deterministic
operational:
?- normal_form(append(append(append(a,b),c),d), X).
X = append(a, append(b, append(c, d))) ;
X = append(a, append(b, append(c, d))) ;
false.
So normal form has spurious choice points. And
would explode in practice, when deployed as a
normal form routine and when supplied larger terms.
A fix would be:
normal_form(Term, Term) :-
-a-a-a-a \+ rewrite_once(Term, _, _).
normal_form(Term, Normal) :-
-a-a-a-a once(rewrite_once(Term, Next, _)),
-a-a-a-a normal_form(Next, Normal).
But once/1 is not among your list of "by" justifications?
Lean 4 does solve this problem in that already match/with
is deterministic. But Lean 4 can make it declarative
by a recursor / motive translation.
Bye
Hi,
Well the interesting part of the normal_form/2
predicate, is also that negation as failure is
not called with a ground goal argument, so the
example leans out of the framework
of SLDNF, where \+ G are supposed to have G ground
at runtime. If it were ground, as a next step in
some Datalog frameworks it can then indeed be
interpreted as absence of a fact or
derived fact, due to negation stratification. But
Robert St|nrk already observed that the two extra
variables _and _, in the call, make it basically
asking a not exists query,
and therefore the justifiation is not only
absence but rather the proof tree of a finite
failure. But if we look at the example it is also
not stead fast, an input 2nd argument
my divert the derivation, and last but not least
rewrite_once is left recursive, and has an infinite
answer set, i.e. all normal terms. One might wonder
whether Robert St|nrk left academia back then,
because such a large number of problems is just too
much for a Human. Just joking. The resilient Prologer
might also see it as the birth place of cuts, since
an alternative formulation often
found in the wild would be:
normal_form(Term, Normal) :-
-a-a-a-a rewrite_once(Term, Next, _), !,
-a-a-a-a normal_form(Next, Normal).
normal_form(Term, Term).
Its even steadfast now in the 2nd argument, and
calls rewrite_once/3 not in two different places,
but only in one place, giving yet anoter inch
more performance.
Have Fun!
Bye
Mild Shock schrieb:
Hi,
Using the EyeProlog example code, I get this
result in a ISO compliant Prolog processor.
The predicate turns out to be non-deterministic
operational:
?- normal_form(append(append(append(a,b),c),d), X).
X = append(a, append(b, append(c, d))) ;
X = append(a, append(b, append(c, d))) ;
false.
So normal form has spurious choice points. And
would explode in practice, when deployed as a
normal form routine and when supplied larger terms.
A fix would be:
normal_form(Term, Term) :-
-a-a-a-a-a \+ rewrite_once(Term, _, _).
normal_form(Term, Normal) :-
-a-a-a-a-a once(rewrite_once(Term, Next, _)),
-a-a-a-a-a normal_form(Next, Normal).
But once/1 is not among your list of "by" justifications?
Lean 4 does solve this problem in that already match/with
is deterministic. But Lean 4 can make it declarative
by a recursor / motive translation.
Bye
| Sysop: | Amessyroom |
|---|---|
| Location: | Fayetteville, NC |
| Users: | 76 |
| Nodes: | 6 (0 / 6) |
| Uptime: | 56:24:08 |
| Calls: | 1,265 |
| Calls today: | 1 |
| Files: | 1,362 |
| D/L today: |
3 files (2,684K bytes) |
| Messages: | 285,806 |