6 ms·

Prolog implementations are too heavily reliant on the stated order of predicate rules in order to make execution progress. Many predicates are non-terminating o

Prolog implementations are too heavily reliant on the stated order of predicate rules in order to make execution progress. Many predicates are non-terminating or extremely inefficient when faced with goal inversion, but are often 'fixed' by simply reversing the order of some of its rules (but making it useless in the original direction in the process). This is disappointing when trying to maximize prolog's biggest potential: building true total relations that can project in any direction with a single definition. There are technical reasons why the pursuit of term reordering is problematic, namely 'cut', which is a kind of out-of-bounds alteration of the program's execution. Previous attempts to get rid of 'cut' apparently ran into other problems. IMO the root of the issue is that prolog has no way to declare a "closed" predicate, and then optimize execution based on their presence. I think cut papers-over (heh) the lack of "closed predicates".

tom_mellior 6y ago
Define "closed"?
galaxyLogic 6y ago
Isn't Datalog the solution to much of that?
YeGoblynQueenne 6y ago
>> Many predicates are non-terminating or extremely inefficient when faced with goal inversion, but are often 'fixed' by simply reversing the order of some of its rules (but making it useless in the original direction in the process). This is disappointing when trying to maximize prolog's biggest potential: building true total relations that can project in any direction with a single definition. I don't think that's a commonly agreed-upon "biggest potential" of Prolog. Prolog is a general-purpose language with the syntax and the semantics of the first-order predicate calculus, albeit limited to Horn clauses and with many other restrictions that are necessary to make for a language that can be used in the real world, for real programming tasks. I cannot easily think of an example where changing the order of clauses (not "goals") in a predicate definition prevents the program from "runnign backwards". For example, take the typical append/3 predicate: append([],Zs,Zs). append([X|Xs],Ys,[X|Zs]):- fappend(Xs,Ys,Zs). Moving the first clause, append([],Zs,Zs), after the second, still allows three calling modes: ?- fappend([a,b],[c,d],Xs). Xs = [a, b, c, d]. ?- fappend([a,b],Xs,[a,b,c,d]). Xs = [c, d]. ?- fappend(Xs,[c,d],[a,b,c,d]). Xs = [a, b] ; false. And complexity does not seem to be affected. Can you give an example where this is not the case? >> IMO the root of the issue is that prolog has no way to declare a "closed" predicate, and then optimize execution based on their presence. I think cut papers-over (heh) the lack of "closed predicates". I, like tom_mellor, am also not sure what you mean by "closed predicates". Could you clarify?
- tom_mellior 6y ago
  > I cannot easily think of an example where changing the order of clauses (not "goals") in a predicate definition prevents the program from "runnign backwards". It's bad enough to use "directions" for what are properly called "modes", but it's positively counterproductive to say that anything in Prolog runs "backwards". Prolog always runs top-to-bottom, left-to-right, and this is precisely why it's easy to write nonterminating definitions. As a community, we are doing ourselves a disservice by claiming that anything can magically run "backwards". As for your question, the canonical example for clause ordering being a problem is where the incorrect order prevents generation of answers because a recursive clause precedes a non-recursive one. Example: xs([x | Xs]) :- xs(Xs). xs([]). This recognizes lists of xs: ?- xs([x, x, x]). true. But it cannot generate them: ?- xs(Xs). ERROR: Out of local stack Contrast with: ys([]). ys([y | Ys]) :- ys(Ys). ?- ys(Ys). Ys = [] ; Ys = [y] ; Ys = [y, y] ; Ys = [y, y, y] .
  - YeGoblynQueenne 6y ago
    I think everyone knows what we mean about "running code backwards" and I was sticking to the OP's choice of language for simplicity. I don't disagree with your (nevertheless pedantic) observation, however. I agree we should be more precise in our terminology. Anyway my bad, I guess you can think of many cases if you try a little. I apologise. I was not in my programming mind today.

tom_mellior 6y ago

Define "closed"?

galaxyLogic 6y ago

Isn't Datalog the solution to much of that?

YeGoblynQueenne 6y ago

>> Many predicates are non-terminating or extremely inefficient when faced with goal inversion, but are often 'fixed' by simply reversing the order of some of its rules (but making it useless in the original direction in the process). This is disappointing when trying to maximize prolog's biggest potential: building true total relations that can project in any direction with a single definition. I don't think that's a commonly agreed-upon "biggest potential" of Prolog. Prolog is a general-purpose language with the syntax and the semantics of the first-order predicate calculus, albeit limited to Horn clauses and with many other restrictions that are necessary to make for a language that can be used in the real world, for real programming tasks. I cannot easily think of an example where changing the order of clauses (not "goals") in a predicate definition prevents the program from "runnign backwards". For example, take the typical append/3 predicate: append([],Zs,Zs). append([X|Xs],Ys,[X|Zs]):- fappend(Xs,Ys,Zs). Moving the first clause, append([],Zs,Zs), after the second, still allows three calling modes: ?- fappend([a,b],[c,d],Xs). Xs = [a, b, c, d]. ?- fappend([a,b],Xs,[a,b,c,d]). Xs = [c, d]. ?- fappend(Xs,[c,d],[a,b,c,d]). Xs = [a, b] ; false. And complexity does not seem to be affected. Can you give an example where this is not the case? >> IMO the root of the issue is that prolog has no way to declare a "closed" predicate, and then optimize execution based on their presence. I think cut papers-over (heh) the lack of "closed predicates". I, like tom_mellor, am also not sure what you mean by "closed predicates". Could you clarify?

tom_mellior 6y ago
> I cannot easily think of an example where changing the order of clauses (not "goals") in a predicate definition prevents the program from "runnign backwards". It's bad enough to use "directions" for what are properly called "modes", but it's positively counterproductive to say that anything in Prolog runs "backwards". Prolog always runs top-to-bottom, left-to-right, and this is precisely why it's easy to write nonterminating definitions. As a community, we are doing ourselves a disservice by claiming that anything can magically run "backwards". As for your question, the canonical example for clause ordering being a problem is where the incorrect order prevents generation of answers because a recursive clause precedes a non-recursive one. Example: xs([x | Xs]) :- xs(Xs). xs([]). This recognizes lists of xs: ?- xs([x, x, x]). true. But it cannot generate them: ?- xs(Xs). ERROR: Out of local stack Contrast with: ys([]). ys([y | Ys]) :- ys(Ys). ?- ys(Ys). Ys = [] ; Ys = [y] ; Ys = [y, y] ; Ys = [y, y, y] .
- YeGoblynQueenne 6y ago
  I think everyone knows what we mean about "running code backwards" and I was sticking to the OP's choice of language for simplicity. I don't disagree with your (nevertheless pedantic) observation, however. I agree we should be more precise in our terminology. Anyway my bad, I guess you can think of many cases if you try a little. I apologise. I was not in my programming mind today.