lee@munnari.oz.au (Lee Naish) (11/23/89)
>patch@hpldola.HP.COM (Pat Chkoreff) writes: >> ROK write: But I fail to see why the fact that a >> predicate can't be used ALL ways round is a reason for only letting me >> use it ONE way round. Why not let me use it in all the modes where it >> does work? > >But how do you determine the modes in which it works, how do you document >them in the language, and what does it mean to the compiler? You determine what modes work by first thinking about the problem (some modes might have infinite solutions), then thinking about the implementation (depending on what facilities your Prolog has, the answers might differ), then by testing. Documentation also depends on the system. Some systems allow various kinds of modes declarations. NU-Prolog allows "when declarations" which say things like "delay calling this predicate until this argument is instantiated". By having such a coroutining system, it is much easier to write reversible predicates. > sequence([]). > sequence([N|Ns]) :- > natural(N), > sequence(Ns). > > natural([]). > natural(s(N)) :- > natural(N). > >Now we write a predicate card(Ns,N), meaning that the cardinality (length) >of Ns is N: > > card([], []). > card([_|Ns], s(N)) :- > card(Ns, N). > >Now we look for sequences of cardinality 2 (s(s([]))): > > sequence(Ns), card(Ns, s(s([]))). > >We get one solution Ns=[[],[]], and on backtracking we fly off into the >weeds. In NU-Prolog you can run this code through a preprocessor (nac) which will add the following when declarations for you: ?- sequence(A) when A. ?- natural(A) when A. ?- card(A, B) when A or B. When the above query executes, sequence(Ns) initially delays. Card does the work of binding Ns to [N1,N2] (deterministically; the previous version was O(N**2) where N is the cardinality). Sequence checks that [N1,N2] is indeed a sequence (deterministically) and calls natural to check that N1 and N2 are naturals. Note that there are an infinite number of naturals, and natural/1 has a when declaration, so both calls delay. The answer returned is Ns=[N1,N2], with natural(N1) and natural(N1) still delayed. The current top level of NU-prolog does not explicitly print out the delayed calls (MU-Prolog does, and thats obviously nicer), but you can get them using the NU-Prolog debugging environment (NUDE), which analyses goals which flounder: 3?- flounder sequence(Ns), card(Ns, s(s([]))). Do static analysis? n Do dynamic flounder analysis? Floundered calls: natural(B9) natural(A9) Answer: sequence([A9, B9]), card([A9, B9], s(s([]))) Since this goal has an infinite number of solutions, we don't want it in a real program (unless it is in conjunction with other goals which will bind N1 and N2). However, you might want to use the goals like this to test your program. This can also be done nicely in NUDE: 4?- test sequence(Ns), card(Ns, C). Do static analysis? n Test known valid instances? n Test known satisfiable atoms? n Test known unsatisfiable atoms? n Generate solutions to goal? Solution found: sequence([]), card([], []). sequence([]) Valid? c % 'c' means we know the pred is correct card([], []) Valid? c Solution found: sequence([[]]), card([[]], s([])). Solution found: sequence([[], []]), card([[], []], s(s([]))). Solution found: sequence([s([])]), card([s([])], s([])). Solution found: sequence([s([]), []]), card([s([]), []], s(s([]))). etc... Every solution would be found eventually, given unbounded time and space. For efficiency reasons, its not the kind of behaviour you want when running your program, but by using the predicate logic framework its very easy to have this kind feature in a program development/debugging system. >So here's the bottom line. In order to get REALLY robust predicates, it >boils down to the ability to do a robust generate-and-test: > > interesting_object(X) :- > object(X), > interesting(X). > >This should iterate over all interesting objects, where the interesting/1 >predicate is arbitrarily complex. Of course, if there are no interesting >objects, then it will not terminate. But that's life, and I can live with >that. Hang on! One of your original complaints was about nontermination. If you want to write code like that above, and expect it to generate a possibly infinte set, you have to "live on the edge" as far as termination goes. An alternative is to use coroutines and delay things with infinite numbers of solutions (losing some capacity to generate values). Writing this kind of thing in a functional style/language is no joy either. Some problems are just difficult. If that wasn't the case we would all be using smart automatic theorem provers instead of stupid programming languages. >implemented with arrays and integer indices in a language like C, and >they'd be really fast! >> Damn right it's easy. I've done it. > >Yeah, but I'll bet your graphs weren't "constructive". I'm sure your version in C wouldn't be! I don't think there are any languages in which, for all problems, you can devise an efficient and constructive program. I don't think you should criticize Prolog for being able to do it for *some* problems. >Besides, what is "first-order logic" other than Horn clauses? Negation, of course! >I'd like to see NU Prolog working on this database: > > person(pat). > person(diana). > >with this query: > > ?- not person(X). > >I'm guessing that either X remains an unbound variable which is constrained >to not be a person, or the query freezes on X. You were right both times. The query "freezes on X", effectively constraining it to not be a person. What would you have it do - start enumerating all the natural numbers? > You could replace >"cuts" with negated conjunctions Not quite - I have a paper on it if you are interested. >but how do you define negation? In terms >of cuts, most likely. NO! You define negation in terms of model theory (this is LOGIC programming). You can *implement* negation using cut, but thats an entirely different thing. >Since in general I cannot implement completely robust relations, then give >me a language that allows me to document functional dependencies and types, >and make them meaningful to the compiler. That would be more "honest" than >a language which LOOKS relational but really isn't, and is fraught with >dangers if you think that it is. Is it more "honest" to have a language without floats because floats are not real numbers (and thinking they are is fraught with dangers), and real numbers, in general, can't be implemented on computers? Possibly so, but I don't think its a good reason for not implementing floats (as long as its done right). You have to be careful when using floats, just as you have to be careful when using relations in multiple ways. lee