Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!linus!decvax!harpo!floyd!clyde!ihnp4!zehntel!hplabs!sri-unix!OKeefe.R.A.@EDXA From: OKeefe.R.A.@EDXA@sri-unix.UUCP Newsgroups: net.lang.prolog Subject: Defining functor/3 Message-ID: <12345@sri-arpa.UUCP> Date: Tue, 4-Oct-83 07:09:09 EDT Article-I.D.: sri-arpa.12345 Posted: Tue Oct 4 07:09:09 1983 Date-Received: Sun, 9-Oct-83 18:16:41 EDT Lines: 155 From: Richard HPS (on ERCC DEC-10) I recently had the opportunity of looking at a Prolog system which had been developed from the Clocksin & Mellish textbook. The trouble is that the Clocksin & Mellish book was written to help beginners learn how to use three existing Prolog interpreters ( the DEC-10, PDP-11, and EMAS Prolog systems ), and not to help Prolog implementers produce exactly the same language. So they didn't discuss fine points. An obvious example of this is the fact that in the DEC-10, EMAS, & C-Prolog systems, disjunction is transparent to cut just like conjunction. What I mean by this is that in p :- a, !, b; c. p :- d. if 'a' is true but 'b' is false, 'p' will fail, because the cut cut right back to p, and didn't stop at the semicolon. If you are an implementor, you will regret this, because otherwise you could write (A ; B) :- call(A). (A ; B) :- call(B). But if you are NOT an implementor, there is no reason for you to expect disjunction to be any different from conjunction in this respect. The transparency of semicolon falls quite naturally out of the way the DEC-10 compiler and interpreter work. C-Prolog ( based on EMAS Prolog ) gets it right, but it is much harder. Because PDP-11 Prolog Sacrificed Semicolon ( and a lot of other things ) to keep its size down, and because disjunction is not central to Prolog, the Clocksin & Mellish book doesn't mention this "detail". ( Of course, if Prolog didn't have cuts, the problem wouldn't arise... ) A less obvious question is what functor, arg, and univ should do. The point of this message is that there is a clear design principle which can settle the question, regardless of what any particular implementation happens to do. { I haven't tried all possible combinations on the DEC-10. If it doesn't act in accord with this principle, I shall regard DEC-10 Prolog as wrong. } The principle is this: as far as possible, every system predicate should behave AS IF it were defined by an explicit table. The interpreter or whatever should only produce an error message when it is unable to simulate the table. Here is a simple example. The predicate succ/2 is "notionally" defined by the infinite table succ(0, 1). }i succ(1, 2). ... succ(56432, 56433). ... We can use this + the principle to specify exactly how succ(X,Y) should behave in all circumstances: X instantiated, but not a non-negative integer => fail Y instantiated, but not a positive integer => fail X unbound, Y > 0 => bind X to Y-1 Y unbound, X >= 0 => bind Y to X+1 X and Y both unbound => apologise and abort A more than acceptable alternative in the last case would be to enumerate all possible solutions by backtracking, but this is not always possible. The point that I am making is that succ(foo,Y) is not in error, it is simply false. There are only two "error" messages that succ is entitled to produce: sorry, succ(,_) overflows sorry, succ(_,_) needs at least one argument instantiated and in both cases the error is the interpreter's, not the programmer's. Of course, it is not particularly sensible to call succ(a,b), but it is perfectly well defined. It is probably a good idea to have a type-checking option which will print a warning message if either argument of succ is bound to a non-integer, but it MUST not abort the computation or cause an exception, it must just fail. Type-checking is better done at compile-time ( see files TYPECH.PL and PROLOG.TYP at SU-SCORE ). Now we come to functor/3. The only thing that the principle doesn't tell us is what is to be done with integers (or floating point numbers, or data base references, or whatever). The DEC-10 and C-Prolog rule is functor(X, X, 0) :- atomic(X). so that for example functor(9, 9, 0) is true. This convention greatly simplifies term hacking. So we imagine a table functor(0, 0, 0). functor(654987, 654987, 0). functor('', '', 0). functor(asdflkjhfdsa, asdflkjhfdsa, 0). functor(A+B, +, 2). ... Since functor(Term, never_before, 1297) may ( in implementation terms) create a new functor never before seen, it is clear that this table cannot be confined to the functors that appear in the program. There is another predicate for that, called current_functor, which depends on the current state of the program. Taking this together with the principle tells us what functor(Term,F,N) must do: Term atomic => unify F=Term, N=0 Term compound => unify F=function symbol, N=arity Term unbound, F unbound => apologise and abort Term unbound, F compound => fail Term unbound, F atomic but not an atom => unify N=0, Term=F Term unbound, N bound but not a non-negative integer => fail Term unbound, F atom, N unbound => apologise and abort Term unbound, F atom, N non-negative integer => unify Term=F(_1,...,_N) Without some sort of principle available to judge by, it would be difficult to decide what functor(X, 9, N) should do. With this principle, it is easy to see that there is exactly one solution, and we can cheaply find it, so it should succeed and bind X=9, N=0. A similar analysis can be applied to arg/3 and =../2. For example, Term =.. [f,a|_] is "apologise and abort", while 1 =.. [1] is true. If we have a system which follows the principle, it follows that any call on one of these evaluable predicates will have one of three outcomes: - the goal is true in the table, and succeeds corretly - the goal is false in the table, and fails correctly - there is insufficient information for the interpreter to tell In the last case, it would not be correct to fail. If the interpreter has enough information to tell that the goal is false, it should fail with no further ado. So there might be true instances of the goal. But the interpreter lacks the information to find such an instance ( or the patience ), so it would not be correct to fail either. That is why I suggest "apologise and abort". DEC-10 compiled code does not abide by this rule. If there is an uninstantiated variable in an arithmetic expression, for example, it calmly substitutes 0 ( but doesn't bind the variable ) and continues, though it does warn you. "abort" need not be taken too literally: ideally the interpreter should enter a debugging mode, at the very least you should be able to inspect the goal stack. There are lots of things in Prolog that probably won't be in DeuLog ( ho deuteros logos ), but I think functor/arg/univ/succ/plus and so on probably will be. They make sense even in a parallel system, and are much closer to logic than say I/O is. So it is worth taking some trouble over their definitions.