mccaugh@uiucdcsm.cs.uiuc.edu (05/28/88)
I submit that "prolog" - the so-called "logic-programming" language - is (among other disclaimers) NOT altogether the "declarative" non-procedural language it is advertised to be. Case in point: sum(0,0). sum(N,M) :- N1 = N-1, sum(N1,M1), M = M1+N. In a truly non-procedural (i.e. (I anticipate controversy here) non- deterministic) language, the test: N>0 should not be necessary, and yet (as we know), it must appear to avoid stack-overflow (in CPROLOG, UNSW- PROLOG, anyway).
ok@quintus.UUCP (Richard A. O'Keefe) (05/30/88)
In article <5500005@uiucdcsm>, mccaugh@uiucdcsm.cs.uiuc.edu writes: > I submit that "prolog" - the so-called "logic-programming" language - is > (among other disclaimers) NOT altogether the "declarative" non-procedural > language it is advertised to be. Case in point: > sum(0,0). > sum(N,M) :- N1 = N-1, sum(N1,M1), M = M1+N. > In a truly non-procedural (i.e. (I anticipate controversy here) non- > deterministic) language, the test: N>0 should not be necessary, and yet > (as we know), it must appear to avoid stack-overflow (in CPROLOG, UNSW- > PROLOG, anyway). The conclusion is valid, but the argument is bogus. {What's with this N1 = N-1 business, anyway? In C Prolog the code as written will never succeed for any first argument other than 0. E.g. sum(1, X) -> sum(1-1, M1) -> sum(1-1-1, M1') -> sum(1-1-1-1, M1") -> ...} Claim: there is no "declarative" language permitting recursive declarations currently existing in which control issues can be ignored. (Lazy ML, Miranda, even the relational algebra, support this claim.) While in this case it is straightforward to show that for sum/2 to succeed its first argument must be a non-negative integer, in general it is at least as hard as solving the halting problem (insert standard trivial proof here). "Non-procedural" and "non-deterministic" are orthogonal concepts. E.g. ICON is non-deterministic but non-procedural, ML is non-procedural but not non-deterministic, Pascal is neither.