% File : ARITH.PL % Author : R.A.O'Keefe % Updated: 12 June 1984 and again KJ 11-8-87 % Purpose: Define the 'plus' family of arithmetic predicates. /* ARITH.OPS : Operator declarations for arithmetic expressions Now present in UTIL, used by PRESS and others UTILITY Lawrence Updated: 2 August 81 This file defines succ/2, which is also a part of Edinburgh Prolog and therefore it cannot be consulted as it stands. Rename succ/2. [KJ] */ :- op(500,yfx,[++,--]). :- op(400,yfx,[div,mod]). :- op(300,xfy,[:,^]). :- public divide/4, ge/2, gt/2, le/2, lt/2, plus/3, succ/2, times/3. :- mode instantiation_fault_(+), ge(?, ?), gt(?, ?), le(?, ?), lt(?, ?), succ(?, ?), plus(?, ?, ?), times(?, ?, ?), times(+, +, ?, ?, ?), divide(?, ?, ?, ?). /* :- pred ge(integer, integer), gt(integer, integer), le(integer, integer), lt(integer, integer), succ(integer, integer), plus(integer, integer, integer), times(integer, integer, integer), times(integer, integer, integer, integer, integer), divide(integer, integer, integer, integer). */ /* These predicates are now primitives in C Prolog. My original reason for adding them to C-Prolog was efficiency, as the "is" expression interpreter (which has to handle floating point as well as integers) is quite complicated. succ(X, Y) is 1.2ms faster than Y is X+1 on a VAX 11-750. However, I found that using succ and plus were clearer, and because of the (limited) reversibility of these operations, lived up to Prolog's claim to have some relation to logic a little better than programs written using the strictly one-way "is". When I started using Prolog I was very taken with "is" and held my nose up at IC- Prolog for lacking it. I now think this was a mistake. Of course there are occasions when you want more than the four algorithms of antiquity, such as when you want to do bit-wise operations, or when you want to use floating-point. And it is undeniable that a single arithmetic expression involving 3 or 4 operators is a lot clearer than 3 or 4 predicate calls whose data flow needs careful tracing. The style rule I have adopted (in addition to using 'is' when these predicates simply can't express what I mean) is to use 'is' whenever I can't express what I want with a *single* call on one of these predicates. Thus to calculate 3X I might use times(3,X,Ans), but to obtain 3X+2 I would use Ans is 3*X+2. A further style rule is that if a predicate uses 'is', all similar calculations in that predicate also use 'is' so you can see what is going on. Thus if I want 3X+2 in one clause and 3X in another, I would use 'is' in both so that the reader can easily perceive the similarities and differences. Reversibility is not then an issue. This Prolog code looks bulky. It is bulky. But don't dismiss these operations for such a reason. The C code which implements them in C Prolog is much shorter, and it is much more efficient than using "is", as it knows that there is no question of walking down trees. When writing a Prolog compiler, you should consider these operations: the compiler can benefit from knowing more about the arguments, and if it keeps track of the instantiation state of source variables it may be able to generate special- purpose code. (E.g. calling plus(X,Y,Z) when Z is known to be unbound should generate "int_chk_push(X), int_chk_push(Y), add, bind_new_var(Z)" or something like that.) */ % The general idea is that if there is enough information in a goal % to detect that it must fail (e.g. succ(X,a)) we fail, if there is % enough information to determine a unique solution, we yield that % solution, and otherwise (this can generally only happen when too % few arguments are instantiated) we report an instantiation fault. % We report a fault even when the non-determinism is bounded, e.g. % in times(X, X, 4) there are only two possible solutions. This is % because these operations are primitives, that would be coded in % assembler or micro-code, and we don't want to oblige a compiler % to generate full frames for them. instantiation_fault_(Goal) :- nl, write('! instantiation fault in '), print(Goal), nl, break, abort. % {ge|gt|le|lt}(X,Y) <-> integer(X) & integer(Y) & X {>=|>|=<|<} Y % Note that there is no eq or ne, = and \= will do fine. ge(X, Y) :- integer(X), integer(Y), !, X @>= Y. ge(X, Y) :- ( var(X) ; integer(X) ), ( var(Y) ; integer(Y) ), !, instantiation_fault_(ge(X,Y)). gt(X, Y) :- integer(X), integer(Y), !, X @> Y. gt(X, Y) :- ( var(X) ; integer(X) ), ( var(Y) ; integer(Y) ), !, instantiation_fault_(gt(X,Y)). le(X, Y) :- integer(X), integer(Y), !, X @=< Y. le(X, Y) :- ( var(X) ; integer(X) ), ( var(Y) ; integer(Y) ), !, instantiation_fault_(le(X,Y)). lt(X, Y) :- integer(X), integer(Y), !, X @< Y. lt(X, Y) :- ( var(X) ; integer(X) ), ( var(Y) ; integer(Y) ), !, instantiation_fault_(lt(X,Y)). % succ(P, S) <-> integer(P) & integer(S) & P >= 0 & S = P+1 % given either of P or S we can solve for the other. % If either is neither an integer nor a variable the relation % must be false. But succ(P, S) with both arguments unbound % has infinitely many solutions. (You can generate a bounded % range of integers using between/3.) succ(Pred, Succ) :- integer(Pred), !, Pred >= 0, Succ is Pred+1. succ(Pred, Succ) :- integer(Succ), !, Succ > 0, Pred is Succ-1. succ(Pred, Succ) :- var(Pred), var(Succ), instantiation_fault_(succ(Pred,Succ)). % plus(A, B, S) <-> integer(A) & integer(B) & integer(S) & S = A+B. % given any two of the arguments, we can solve for the third. % If any argument is neither an integer nor a variable, the relation % must be false. If two are variables and the other is variable or % integer, there are infinitely many solutions. plus(A, B, S) :- integer(A), integer(B), !, S is A+B. plus(A, B, S) :- integer(A), integer(S), !, B is S-A. plus(A, B, S) :- integer(B), integer(S), !, A is S-B. plus(A, B, S) :- ( var(A) ; integer(A) ), ( var(B) ; integer(B) ), ( var(S) ; integer(S) ), !, % at most one of A,B,S is integer, the others are vars instantiation_fault_(plus(A,B,S)). % times(A, B, P) <-> integer(A) & integer(B) & integer(P) & P = A*B. % This is trickier than plus. Given A and B there is a unique solution % for P. Given A(B) and P there is at most one solution for B(A) % except in the case when P and A(B) are both 0, in which case there % are infinitely many solutions. Given just A or B there are infinitely % many solutions. Given P there is always a finite number of solutions, % but this number always exceeds 1 (even times(X,Y,1) has X,Y=1,1 or -1,-1). % So we report an instantiation error in that case two. Of course if any % argument is instantiated to a non-integer the relation must be false. times(A, B, P) :- integer(A), integer(B), !, P is A*B. times(A, B, P) :- integer(A), integer(P), !, times(P, A, B, A, B). times(A, B, P) :- integer(B), integer(P), !, times(P, B, A, A, B). times(A, B, P) :- ( var(A) ; integer(A) ), ( var(B) ; integer(B) ), ( var(P) ; integer(P) ), !, % at most one of P,A,B is integer, the others are vars instantiation_fault_(times(A,B,P)). times(P, A, B, _, _) :- A \== 0, !, 0 is P mod A, B is P div A. times(0, 0, _, X, Y) :- instantiation_fault_(times(X,Y,0)). /* divide(A, B, Q, R) means A, B, Q, and R are all integers, A = B*Q + R, A*R >= 0, (A and R have the same sign, so Q is truncated towards 0) 0 <= |R/B| < 1 (so B is non-zero) This piece of Prolog is to be taken as a specification of the predicate, an implementation may proceed differently. I assume "is", and that overflow need not be checked for, and that X / Y and X / Y are well defined for X >= 0, Y >= 1. Cases: any one of A, B, Q, R is bound to a non-integer => FAIL B is bound to 0 => FAIL {These two failures should have associated error messages} A and B bound => calculate Q', R' unify Q=Q' R=R' A, Q, and R bound => if A*R < 0 then FAIL if Q = 0 then instantiation FAULT unless |Q| divides A-R then FAIL calculate B from divide(A-R,Q,B,0) B, Q, and R bound => check conditions calculate A = B*Q+R check remaining conditions otherwise, instantiation FAULT */ divide(A, B, Q, R) :- ( nonvar(A), \+ integer(A) ; nonvar(B), \+ integer(B) ; nonvar(Q), \+ integer(Q) ; nonvar(R), \+ integer(R) ), !, % bound to fail fail. divide(A, B, Q, R) :- nonvar(A), nonvar(B), !, ( B > 0, A >= 0, Q1 is A div B ; B > 0, A < 0, Q1 is -((-A) div B) ; B < 0, A >= 0, Q1 is -(A div (-B)) ; B < 0, A < 0, Q1 is (-A) div (-B) ), !, Q = Q1, R is A-Q1*B. divide(A, B, Q, R) :- nonvar(A), nonvar(Q), nonvar(R), !, ( A >= 0, R >= 0 ; A =< 0, R =< 0 ), ( Q = 0, !, instantiation_fault_(divide(A,B,Q,R)) ; true ), !, 0 is (A-R) mod Q, B is (A-R) div Q. divide(A, B, Q, R) :- nonvar(B), nonvar(Q), nonvar(R), !, B \== 0, A is B*Q+R, ( R >= 0, A >= 0, (B > R ; -B > R) ; R =< 0, A =< 0, (B < R ; -B < R) ), !. divide(A, B, Q, R) :- instantiation_fault_(divide(A,B,Q,R)).