• Is (\+)/1 enough for executable specifications?

    From Mild Shock@janburse@fastmail.fm to comp.lang.prolog on Tue Nov 3 01:28:33 2026
    From Newsgroup: comp.lang.prolog

    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) :-
    \+ rewrite_once(Term, _, _).
    normal_form(Term, Normal) :-
    once(rewrite_once(Term, Next, _)),
    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

    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Mild Shock@janburse@fastmail.fm to comp.lang.prolog on Tue Nov 3 15:59:33 2026
    From Newsgroup: comp.lang.prolog

    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) :-
    rewrite_once(Term, Next, _), !,
    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 \+ 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


    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Mild Shock@janburse@fastmail.fm to comp.lang.prolog on Tue Nov 3 16:07:44 2026
    From Newsgroup: comp.lang.prolog

    Hi,

    Well in this definition, the second
    normal_form/2 call is with mode (+,+),
    ad not anymore with mode (+,-):

    joined_pair(Name) :-
    critical_pair(Name, Left, Right),
    normal_form(Left, Normal),
    normal_form(Right, Normal).

    Bye

    Mild Shock schrieb:
    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



    --- Synchronet 3.22a-Linux NewsLink 1.2