.pn 0.EQdelim $$define RR 'bold R'define SS 'bold S'define II 'bold I'define mo '"\(mo"'define EXIST ?"\z\-\d\z\-\r\-\d\v'0.2m'\(br\v'-0.2m'"?define NEXIST ?"\z\-\d\z\o'\-\(sl'\r\-\d\v'0.2m'\(br\v'-0.2m'"?define ALL ?"\o'V-'"?define subset '\(sb'define subeq  '\(ib'define supset '\(sp'define supeq  '\(ip'define mo '\(mo'define nm ?"\o'\(mo\(sl'"?define li '\& sup ['define lo '\& sup ('define hi '\& sup ]'define ho '\& sup )'.EN.ls 1	.ceA LOGICAL IMPLEMENTATION OF ARITHMETIC .sp 3.ceJohn G. Cleary .ceThe University of Calgary, Alberta, Canada..sp 20\u1\dAuthor's Present Address: Man-Machine Systems Group, Department ofComputer Science, The University of Calgary, 2500 University Drive NWCalgary, Canada T2N 1N4. Phone: (403)220-6087.  .br.nfUUCP:  ...!{ihnp4,ubc-vision}!alberta!calgary!cleary       ...!nrl-css!calgary!clearyARPA:  cleary.calgary.ubc@csnet-relayCDN:   cleary@calgary.fi.sp 2.ls 2.bp 0.ls 2.ceAbstract.ppSo far implementations of real arithmetic within logic programminghave been non-logical.  A logical description of the behaviour of arithmeticon actualmachines using finite precision numbers is not readily available.  Using interval analysis a simple description of real arithmetic is possible.This can be translated to an implementation within Prolog.As well as having a sound logical basis the resulting system allows a very concise and powerful programming style and is potentiallyvery efficient..bp.sh "1 Introduction".ppLogic programming aims to use sets of logical formulae asstatements in a programming language.Because of many practical difficulties the full generality of logiccannot (yet) be used in this way.   However, by restricting theclass of formulae used to Horn clauses practical and efficientlanguages such as PROLOG are obtained.One of the main problems in logic programming is to extend this areaof practicality and efficiency to an ever wider range of formulae and applications.  This paper considers such an implementation for arithmetic..ppTo see why arithmetic as it is commonly implemented in PROLOG systemsis not logical consider the following example:.sp.nf	X = 0.67, Y = 0.45, Z is X*Y, Z = 0.30.fi.spThis uses the notation of the 'Edinburgh style' Prologs.(For the moment we assume an underlying floating pointdecimal arithmetic with two significant places.)The predicate 'is' assumes its righthand side is an arithmeticstatement, computes its value, and unifies the result with its lefthand side.In this case the entire sequence succeeds, however, there are some serious problems..ppIn a pure logic program the order of statements should be irrelevant tothe correctness of the result (at worst termination or efficiency might beaffected).  This is not true of the example above.  The direction of executionof 'is' is strictly one way so that.sp	Y = 0.45, Z = 0.30, Z is X*Y.spwill deliver an error when X is found to be uninstantiated inside 'is'..ppThe second problem is that the answer Z = 0.30 is incorrect!\ The correct infinite precision answer is Z = 0.3015.  This inaccuracyis caused by the finite precision implemented in the floating pointarithmetic of modern computers.It becomes very problematic to say what if anything it means whenZ is bound to 0.30 by 'is'.  This problem is exacerbated by long sequencesof arithmetic operations where the propagation of such errors can lead thefinal result to have little or no resemblence to the correct answer..ppThis is further class of errors, which is illustrated by the fact that thefollowing two sequences will both succeed if the underlying arithmetic rounds:.sp	X = 0.66, Y = 0.45, Z = 0.30, Z is X*Y.br	X = 0.67, Y = 0.45, Z = 0.30, Z is X*Y.spThis means that even if some invertable form of arithmetic were devisedcapable of binding X when:.sp	Y = 0.45, Z = 0.30, Z is X*Y.spit is unclear which value should be given to it..ppThe problem then, is to implement arithmetic in as logical a manneras possible while still making use of efficient floating point arithmetic.The solution to this problem has three major parts.The first is to represent PROLOG's arithmetic variables internally as intervals of real numbers.So the result of 'Z is 0.45*0.67' would be to bind Z to the open interval (0.30,0.31).  This says that Z lies somewhere in the interval$0.30 < Z < 0.31$, which is certainly true, and probably as informativeas possible given finite precision arithmetic.(Note that Z is NOT bound to the data structure (0.30,0.31), thisis a hidden representation in much the same way that pointers are usedto implement logical variables in PROLOG but are not explicitly visibleto the user.  Throughout this paper brackets such as (...) or [...] willbe used to represent open and closed intervals not Prolog data structures.).ppThe second part of the solution is to translate expressions such as\&'Z is (X*Y)/2' to the relational form 'multiply(X,Y,T0), multiply(2,Z,T0)'.Note that both the * and / operators have been translated to 'multiply'(with parameters in a different order).  This relational form will be seen to be insensitive to which parameters are instantiated and which are not,thus providing invertibility..ppThe third part is to provide a small number of control 'predicates' ableto guide the search for solutions.The resulting system is sufficiently powerful to be able tosolve equations such as '0 is X*(X-2)+1' directly..ppThe next section gives a somewhat more formal description of arithmeticimplemented this way.  Section III gives examples of its use and of thetypes of equations that are soluble within it.  Section IV compares our approach here with that of other interval arithmetic systems and withconstraint networks.  Section V notes some possibilities for a parallel dataflow implementation which avoids many of the difficulties of traditionaldataflow execution..sh "II. Interval Representation".ppDefine $II(RR)$ to be the set of intervals over the real numbers, $RR$.So that the lower and upper bounds of each interval can be operated on as single entities they will be treated as pairs of values.  Each value having an attribute of being open or closed and an associated number.  For example the interval (0.31,0.33] will betreated as the the pair $lo 0.31$ and $hi 0.33$.  The brackets are superscripted to minimize visual confusion when writeing bounds not in pairs.As well as the usual real numbers $- inf$ and $inf$, will be used as part of bounds,with the properties that $ALL x mo RR~- inf < x < inf$ The set of all upper bounds is defined as:.sp	$H(RR)~==~\{ x sup b : x mo RR union \{ inf \},~b mo \{ hi , ho \} \} $.spand the set of lower bounds as:.sp	$L(RR)~==~\{ \& sup b x : x mo RR union \{ -inf \},~b mo \{ li , lo \} \} $.spThe set of all intervals is then defined by:.sp	$II(RR)~==~L(RR) times H(RR)$.spUsing this notation rather loosely intervals will be identified with the apropriate subset of the reals.  For example the following identifications will be made:.sp	$[0.31,15)~=~< li 0.31, ho 15 >~=~ \{ x mo RR: 0.31 <= x < 15 \}$.br	$[-inf,inf]~=~< li -inf , hi inf> ~=~ RR$.brand	$(-0.51,inf]~=~< lo -0.51 , hi inf >~=~ \{ x mo RR: 0.51 < x \}$.spThe definition above carefully excludes 'intervals' such as $[inf,inf]$in the interests of simplifying some of the later development..ppThe finite arithmetic available on computers is represented by afinite subset, $SS$, of $RR$.  It is assumed that $0,1 mo SS$.  The set of intervals allowed over $SS$ is $II(SS)$ defined as above for $RR$.  $SS$ might be a bounded set of integers or some more complexset representable by floating point numbers..ppThere is a useful mapping from $II(RR)$ to $II(SS)$ which associateswith each real interval the best approximation to it:.nf.sp	$approx(<l,h>)~==~<l prime, h prime >$.brwhere	$l prime mo L(SS), l prime <= l, and NEXIST x mo L(SS)~l prime <x<l$.br	$h prime mo H(SS), h prime >= h, and NEXIST x mo H(SS)~h prime >x>h$..ppThe ordering on the bounds is defined as follows:.sp	$l < h, ~ l,h mo II(RR)~ <->~l= \& sup u x and h = \& sup v y$			and $x<y$ or $x=y$ and $u<v$where 	$ ho, li, hi, lo$ occur in this order and $x<y$ is the usual ordering on the reals extended to include $-inf$ and $inf$.  The ordering on the brackets is carefully chosen so that intervals such as(3.1,3.1) map to the empty set.Given this definition it is easily verified that 'approx' givesthe smallest interval in $II(SS)$ enclosing the original interval in $II(RR)$.The definition also allows the intersection of two intervals to be readily computed:.sp	$<l sub 1,h sub 1> inter <l sub 2, h sub 2>~=~$		$< max(l sub 1 , l sub 2), min(h sub 1 , h sub 2 )>$.spAlso and interval $<l,h>$ will be empty if $l > h$.  For example, accordingto the definition above $lo 3.1 > ho 3.1$ so (3.1,3.1) is correctly computedas being empty..ppIntervals are introduced into logic by extending the notion of unification.  A logical variable I can be bound to an interval $I$,written I:$I$.  Unification of I to any other value J gives the followingresults:.LB.NPif J is unbound then it is bound to the interval, J:$I$;.NPif J is bound to the interval J:$J$ thenI and J are bound to the same interval $I inter J$.The unification fails if $I inter J$ is empty..NPa constant C is equivalent to $approx([C,C])$;.NPif J is bound to anything other than an interval the unification fails..LE.ppBelow are some simple Prolog programs and the bindings that result whenthey are run (assuming as usual two decimal places of accuracy)..sp.nf	X = 3.141592	X:(3.1,3.2)	X > -5.22, Y <= 31, X=Y	X:(-5.3,32]  Y:(-5.3,31].fi.sp.rh "Addition".ppAddition is implemented by the relation 'add(I,J,K)'which says that K is the sum of I and J.\&'add' can be viewed as a relation on $RR times RR times RR$ definedby:.sp	$add ~==~ \{<x,y,z>:x,y,z mo  RR,~x+y=z\}$.spGiven that I,J, and K are initially bound to the intervals $I,J,K$ respectively, the fully correct set of solutions with the additionalconstrain 'add(I,J,K)' is given by all triples in the set $add inter I times J times K$.  This set is however infinite, to get an effectively computable procedureI will approximate the additional constraint by binding I, J and Kto smaller intervals.  So as not to exclude any possible triples the new bindings, $I prime, J prime roman ~and~ K prime$ must obey:.sp	$add inter I times J times K ~subeq~ I prime times J prime times K prime$.spFigure 1 illustrates this process of.ulnarrowing.The initial bindings are I:[0,2], J:[1,3]and K:[4,6].  After applying 'add(I,J,K)' the smallest possible bindingsare I:[1,2], J:[2,3] and K:[4,5].  Note that all three intervals have beennarrowed..ppIt can easily be seen that:.sp	$I prime supeq \{x:<x,y,z> ~mo~ add inter I times J times K \}$.br	$J prime supeq \{y:<x,y,z> ~mo~ add inter I times J times K \}$.br	$K prime supeq \{z:<x,y,z> ~mo~ add inter I times J times K \}$.spIf there are 'holes' in the projected set then $I prime$ will be a strictsuperset of the projection, however, $I prime$ will still be uniquely determined by the projection.  This will be true of anysubset of $RR sup n$ not just $add$..ppIn general for.sp	$R subeq RR sup n,~ I sub 1 , I sub 2 , ... , I sub n mo II(RR)$and $I prime  sub 1 , I prime  sub 2 , ... , I prime  sub n mo II(RR)$.spI will write .br	$R inter I sub 1 times I sub 2 times ... times I sub n nar I prime sub 1 times I prime sub 2 times ... times I prime sub $.br when the intervals $I prime sub 1 , I prime sub 2 , ... , I prime sub $are the uniquelly determined smallest intervals including all solutions..sh "IV. Comparison with Interval Arithmetic".pp.sh "V.  Implementation".pp.sh "VI. Summary".sh "Acknowledgements".sh "References".ls 1.[$LIST$.]