Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!usc!ucsd!ucsdhub!hp-sdd!hplabs!hpfcso!hpldola!patch From: patch@hpldola.HP.COM (Pat Chkoreff) Newsgroups: comp.lang.prolog Subject: Re: Fun. vs. Logic Message-ID: <11500020@hpldola.HP.COM> Date: 1 Dec 89 00:25:18 GMT References: <11500018@hpldola.HP.COM> Organization: HP Elec. Design Div. -ColoSpgs Lines: 181 || / hpldola:comp.lang.prolog / djk@cs.mu.OZ.AU (David Keegel) / 12:48 am || Nov 23, 1989 / | In article <11500019@hpldola.HP.COM> patch@hpldola.HP.COM (Pat Chkoreff) | writes: || the danger of NON-TERMINATION is constantly rearing its ugly head. || I can either document these dangers in comments, mode declarations, or some || other "bag" on the side of the language, or I can rewrite my predicate to be || robust. I, a self-styled purist, usually opt for the latter. | Or you can use a co-routining system like NU-Prolog which can often | delay evaluation of a predicate which would cause infinite loops. I'm glad that you (and others) brought up NU-Prolog. I am now more aware that the *operational* semantics of Prolog should be kept distinct from its *model-theoretic* semantics. My goal of being able to generate all objects in a domain upon backtracking is of no real value. It leads to data structures which are artifacts of the operational semantics of the particular dialect of Prolog I'm using. For example, my structure for "sequences of natural numbers" was highly unnatural, but allowed all sequences to be generated using standard, "eager" Prolog. (Of course, I can still do this with "standard" sequences if I first constrain the arithmetic sum of all the elements in the sequence.) This means that I can relax a little when I'm using Prolog. Let's say I'm writing a "file editor", and I have a function which applies an editing command to a file: apply_command(Command, File0, File1). % File1 is the file resulting from the application of Command to the % file File0. I don't have to worry too much about what happens when it's called with no arguments bound. I certainly don't need to enumerate all possible solutions upon backtracking! If Command and File1 are bound, but File0 is not, I don't need to enumerate all possible solutions for File0. Many relations implement functions which are not invertible in principle. My reasoning about the termination properties of such relations is intimately related to the *operational* semantics of the Prolog I'm using. For example, in "eager" Prolog, I have no *general* way of preventing the interpreter from "flying into the weeds" when File0 is unbound. The Command could implement an arbitrary function which cannot be inverted. With NU-Prolog, I can control this behavior: I can simply "block" on Command and File0, but not on File1. This gives me the ability to implement robust "functions" when I have to, while retaining the power of logic programming to implement more general "relations" when I can. I still maintain that the danger of non-termination is higher in "eager" Prolog than in any functional language, either eager or lazy. In particular, eager Prolog is more dangerous than eager ML. In eager ML, you know that arguments to functions will be ground terms, and you can reason about termination accordingly. In eager Prolog, you have no such knowledge, and there are many nonterminating call modes that you cannot prevent. Lazy Prolog is a "horse of a different color": nontermination can often be replaced by suspension. Since I'm using eager Prolog, I'll just have to be careful, and document things in comments. || object([]). || object([C|X]) :- || object(X), || construct(C, X). | I don't understand why you don't have "construct(C, X), object(X)" as | the body of the second clause, so you can use tail recursion. Never mind. Because construct(C,X) is guaranteed to terminate a finite number of times with C ground, but only if X is a ground term representing an object, and the only way to guarantee that is to call object(X). This is an artifact of my desire to generate all possible objects upon backtracking, and my desire to represent objects as ground terms. Regarding my representation for natural numbers: | (I thought s(s(....(s(0))...)) was the standard notation, but never mind.) I figured that [] was a perfectly good niladic functor, so I might as well use it to represent the natural number 0. But that's kind of obscure, I'll admit. The fact that I'm using "0" right now to represent 0 is a good argument against me! || In order to make things more efficient, I'll have to start || using more ad-hoc data structures. For example, I could represent "sets" as || trees and get O(logN) access time. But I'd have to give up my so-called || "constructive" ideal: I doubt that it's possible to write omni-directional || predicates for manipulating trees, since they're doubly-recursive. | I don't understand. What is the problem with double recursion? Why do | you call trees "ad-hoc"? Using trees obscures the specification. I like to represents "sets of objects" as lists, and just use the natural numbers 0, s(0), s(s(0)), etc. to identify the objects. It keeps things as simple as possible, but no simpler. Some of my algorithms are O(N^2) in the worst case, but the same would go for trees unless I kept them balanced. (Besides, I could translate these specs into C using arrays and integer indices and get that blazing speed I was talking about.) Of course, I CAN write robust doubly-recursive predicates -- sort of. For example, the flatten/2 predicate below will work in all call modes, even though it's a functional relation from T onto Xs. I have to pass an extra reference to Xs into an auxiliary predicate flatten/5 to give it something to "chew on" before the left-recursive call. %---------------------------------------------------------------- % flatten(T, Xs). % % T is a tree which is flattened to form the list Xs. %---------------------------------------------------------------- flatten(T, Xs) :- flatten(T, Xs, [], Xs, []). flatten([], Xs, Xs, Ys, Ys). flatten(t(X,Ta,Tb), Xs, Xs0, [_|Ys], Ys0) :- flatten(Ta, Xs, [X|Xs1], Ys, Ys1), flatten(Tb, Xs1, Xs0, Ys1, Ys0). However, the auxiliary predicate flatten/5 is "dangerous" in eager Prolog. The query below succeeds with {T=[],Ys=[]}, and then fails to terminate upon backtracking. flatten(T,[],[],Ys,[]). I suppose I could document this in NU-Prolog with something like: ?- flatten(_,_,_,Ys,_) when Ys. || Besides, what is "first-order logic" other than Horn clauses? (That's not || a rhetorical question.) | First-order logic includes negation (you have heard of that, haven't | you? :-), as well as implication and quantifiers. I wanted to find out what O'Keefe was calling "first-order logic". I claimed that the "theory" behind Prolog was "pure Horn clauses"; he claimed that it was "first-order logic", which includes negation. In the literature that I've seen, the semantics of Horn clause programs are defined model- theoretically, but the semantics of negation are defined operationally (cit. Chapter 5 of "The Art of Prolog"). A perverse reader might have surmised that my question was "yet another example of the shocking absence of logic from our undergrad curricula". You, in contrast, used a smiley face (:-). Negation worries me. A language feature should either be essential for computation, or defined in terms of something that is. Negation is NOT essential for computation, so I HOPE that it can be defined in terms of pure Horn clauses, which are. Is there an effective procedure for removing negation from a first-order logic program, resulting in a pure Horn clause program? I wouldn't necessarily USE the procedure -- I just want to know if it exists. If not, then something stinks. This is one thing that I like about functional languages like ML and Miranda: everything in the language is just syntactic sugar for pure combinatorial lambda expressions (K's and S's). I'll continue to use the eager Prolog that's available to me. I need to find out about NU-Prolog, even if I don't use it. At least it might give me a "meta-language" for documenting (and thinking about) the termination properties of my predicates. Patrick Chkoreff 719-590-5983 {hpfcla,hplabs}!hpldola!patch P.S. /jha@lfcs.ed.ac.uk Jamie Andrews at Laboratory for the Foundations of /Computer Science writes: | My apologies if any of the flaming above caused serious | offense. :-) None taken, but who pissed in your Corn Flakes?