1.pn 0 2.EQ 3delim $$ 4define RR 'bold R' 5define SS 'bold S' 6define II 'bold I' 7define mo '"\(mo"' 8define EXIST ?"\z\-\d\z\-\r\-\d\v'0.2m'\(br\v'-0.2m'"? 9define NEXIST ?"\z\-\d\z\o'\-\(sl'\r\-\d\v'0.2m'\(br\v'-0.2m'"? 10define ALL ?"\o'V-'"? 11define subset '\(sb' 12define subeq '\(ib' 13define supset '\(sp' 14define supeq '\(ip' 15define mo '\(mo' 16define nm ?"\o'\(mo\(sl'"? 17define li '\& sup [' 18define lo '\& sup (' 19define hi '\& sup ]' 20define ho '\& sup )' 21.EN 22.ls 1 23.ce 24A LOGICAL IMPLEMENTATION OF ARITHMETIC 25.sp 3 26.ce 27John G. Cleary 28.ce 29The University of Calgary, Alberta, Canada. 30.sp 20 31\u1\dAuthor's Present Address: Man-Machine Systems Group, Department of 32Computer Science, The University of Calgary, 2500 University Drive NW 33Calgary, Canada T2N 1N4. Phone: (403)220-6087. 34.br 35.nf 36UUCP: ...!{ihnp4,ubc-vision}!alberta!calgary!cleary 37 ...!nrl-css!calgary!cleary 38ARPA: cleary.calgary.ubc@csnet-relay 39CDN: cleary@calgary 40.fi 41.sp 2 42.ls 2 43.bp 0 44.ls 2 45.ce 46Abstract 47.pp 48So far implementations of real arithmetic within logic programming 49have been non-logical. A logical description of the behaviour of arithmetic 50on actual 51machines using finite precision numbers is not readily available. 52Using interval analysis a simple description of real arithmetic is possible. 53This can be translated to an implementation within Prolog. 54As well as having a sound logical basis the resulting system 55allows a very concise and powerful programming style and is potentially 56very efficient. 57.bp 58.sh "1 Introduction" 59.pp 60Logic programming aims to use sets of logical formulae as 61statements in a programming language. 62Because of many practical difficulties the full generality of logic 63cannot (yet) be used in this way. However, by restricting the 64class of formulae used to Horn clauses practical and efficient 65languages such as PROLOG are obtained. 66One of the main problems in logic programming is to extend this area 67of practicality and efficiency to an ever wider range of formulae and 68applications. 69This paper considers such an implementation for arithmetic. 70.pp 71To see why arithmetic as it is commonly implemented in PROLOG systems 72is not logical consider the following example: 73.sp 74.nf 75 X = 0.67, Y = 0.45, Z is X*Y, Z = 0.30 76.fi 77.sp 78This uses the notation of the 'Edinburgh style' Prologs. 79(For the moment we assume an underlying floating point 80decimal arithmetic with two significant places.) 81The predicate 'is' assumes its righthand side is an arithmetic 82statement, computes its value, and unifies the result with its lefthand side. 83In this case the entire sequence succeeds, however, there are some serious 84problems. 85.pp 86In a pure logic program the order of statements should be irrelevant to 87the correctness of the result (at worst termination or efficiency might be 88affected). This is not true of the example above. The direction of execution 89of 'is' is strictly one way so that 90.sp 91 Y = 0.45, Z = 0.30, Z is X*Y 92.sp 93will deliver an error when X is found to be uninstantiated inside 'is'. 94.pp 95The second problem is that the answer Z = 0.30 is incorrect!\ 96The correct infinite precision answer is Z = 0.3015. This inaccuracy 97is caused by the finite precision implemented in the floating point 98arithmetic of modern computers. 99It becomes very problematic to say what if anything it means when 100Z is bound to 0.30 by 'is'. This problem is exacerbated by long sequences 101of arithmetic operations where the propagation of such errors can lead the 102final result to have little or no resemblence to the correct answer. 103.pp 104This is further class of errors, which is illustrated by the fact that the 105following two sequences will both succeed if the underlying arithmetic rounds: 106.sp 107 X = 0.66, Y = 0.45, Z = 0.30, Z is X*Y 108.br 109 X = 0.67, Y = 0.45, Z = 0.30, Z is X*Y 110.sp 111This means that even if some invertable form of arithmetic were devised 112capable of binding X when: 113.sp 114 Y = 0.45, Z = 0.30, Z is X*Y 115.sp 116it is unclear which value should be given to it. 117.pp 118The problem then, is to implement arithmetic in as logical a manner 119as possible while still making use of efficient floating point arithmetic. 120The solution to this problem has three major parts. 121The first is to represent PROLOG's 122arithmetic variables internally as intervals of real numbers. 123So the result of 'Z is 0.45*0.67' would be to bind Z to the 124open interval (0.30,0.31). 125This says that Z lies somewhere in the interval 126$0.30 < Z < 0.31$, which is certainly true, and probably as informative 127as possible given finite precision arithmetic. 128(Note that Z is NOT bound to the data structure (0.30,0.31), this 129is a hidden representation in much the same way that pointers are used 130to implement logical variables in PROLOG but are not explicitly visible 131to the user. Throughout this paper brackets such as (...) or [...] will 132be used to represent open and closed intervals not Prolog data structures.) 133.pp 134The second part of the solution is to translate expressions such as 135\&'Z is (X*Y)/2' to the relational form 'multiply(X,Y,T0), multiply(2,Z,T0)'. 136Note that both the * and / operators have been translated to 'multiply' 137(with parameters in a different order). This relational form will be seen to 138be insensitive to which parameters are instantiated and which are not, 139thus providing invertibility. 140.pp 141The third part is to provide a small number of control 'predicates' able 142to guide the search for solutions. 143The resulting system is sufficiently powerful to be able to 144solve equations such as '0 is X*(X-2)+1' directly. 145.pp 146The next section gives a somewhat more formal description of arithmetic 147implemented this way. Section III gives examples of its use and of the 148types of equations that are soluble within it. Section IV compares our 149approach here with that of other interval arithmetic systems and with 150constraint networks. Section V notes some possibilities for a parallel 151dataflow implementation which avoids many of the difficulties of traditional 152dataflow execution. 153.sh "II. Interval Representation" 154.pp 155Define $II(RR)$ to be the set of intervals over the real numbers, $RR$. 156So that the lower and upper bounds of each interval can be operated on as 157single entities they will be treated as pairs of values. 158Each value having an attribute of being open or closed 159and an associated number. For example the interval (0.31,0.33] will be 160treated as the the pair $lo 0.31$ and $hi 0.33$. 161The brackets are superscripted to minimize visual confusion when writeing 162bounds not in pairs. 163As well as the usual real numbers 164$- inf$ and $inf$, will be used as part of bounds, 165with the properties that $ALL x mo RR~- inf < x < inf$ 166The set of all upper bounds is defined as: 167.sp 168 $H(RR)~==~\{ x sup b : x mo RR union \{ inf \},~b mo \{ hi , ho \} \} $ 169.sp 170and the set of lower bounds as: 171.sp 172 $L(RR)~==~\{ \& sup b x : x mo RR union \{ -inf \},~b mo \{ li , lo \} \} $ 173.sp 174The set of all intervals is then defined by: 175.sp 176 $II(RR)~==~L(RR) times H(RR)$ 177.sp 178Using this notation rather loosely intervals will be identified 179with the apropriate subset of the reals. For example the following 180identifications will be made: 181.sp 182 $[0.31,15)~=~< li 0.31, ho 15 >~=~ \{ x mo RR: 0.31 <= x < 15 \}$ 183.br 184 $[-inf,inf]~=~< li -inf , hi inf> ~=~ RR$ 185.br 186and $(-0.51,inf]~=~< lo -0.51 , hi inf >~=~ \{ x mo RR: 0.51 < x \}$ 187.sp 188The definition above carefully excludes 'intervals' such as $[inf,inf]$ 189in the interests of simplifying some of the later development. 190.pp 191The finite arithmetic available on computers is represented by a 192finite subset, $SS$, of $RR$. It is assumed that 193$0,1 mo SS$. The set of intervals allowed over $SS$ is $II(SS)$ defined as 194above for $RR$. $SS$ might be a bounded set of integers or some more complex 195set representable by floating point numbers. 196.pp 197There is a useful mapping from $II(RR)$ to $II(SS)$ which associates 198with each real interval the best approximation to it: 199.nf 200.sp 201 $approx(<l,h>)~==~<l prime, h prime >$ 202.br 203where $l prime mo L(SS), l prime <= l, and NEXIST x mo L(SS)~l prime <x<l$ 204.br 205 $h prime mo H(SS), h prime >= h, and NEXIST x mo H(SS)~h prime >x>h$. 206.pp 207The ordering on the bounds is defined as follows: 208.sp 209 $l < h, ~ l,h mo II(RR)~ <->~l= \& sup u x and h = \& sup v y$ 210 and $x<y$ or $x=y$ and $u<v$ 211where $ ho, li, hi, lo$ occur in this order and $x<y$ is the usual ordering 212on the reals extended to include $-inf$ and $inf$. 213The ordering on the brackets is carefully chosen so that intervals such as 214(3.1,3.1) map to the empty set. 215Given this definition it is easily verified that 'approx' gives 216the smallest interval in $II(SS)$ enclosing the original interval in $II(RR)$. 217The definition also allows the intersection of two intervals to be readily 218computed: 219.sp 220 $<l sub 1,h sub 1> inter <l sub 2, h sub 2>~=~$ 221 $< max(l sub 1 , l sub 2), min(h sub 1 , h sub 2 )>$ 222.sp 223Also and interval $<l,h>$ will be empty if $l > h$. For example, according 224to the definition above $lo 3.1 > ho 3.1$ so (3.1,3.1) is correctly computed 225as being empty. 226.pp 227Intervals are introduced into logic by extending the notion of 228unification. A logical variable I can be bound to an interval $I$, 229written I:$I$. Unification of I to any other value J gives the following 230results: 231.LB 232.NP 233if J is unbound then it is bound to the interval, J:$I$; 234.NP 235if J is bound to the interval J:$J$ then 236I and J are bound to the same interval $I inter J$. 237The unification fails if $I inter J$ is empty. 238.NP 239a constant C is equivalent to $approx([C,C])$; 240.NP 241if J is bound to anything other than an interval the unification fails. 242.LE 243.pp 244Below are some simple Prolog programs and the bindings that result when 245they are run (assuming as usual two decimal places of accuracy). 246.sp 247.nf 248 X = 3.141592 249 X:(3.1,3.2) 250 251 X > -5.22, Y <= 31, X=Y 252 X:(-5.3,32] Y:(-5.3,31] 253.fi 254.sp 255.rh "Addition" 256.pp 257Addition is implemented by the relation 'add(I,J,K)' 258which says that K is the sum of I and J. 259\&'add' can be viewed as a relation on $RR times RR times RR$ defined 260by: 261.sp 262 $add ~==~ \{<x,y,z>:x,y,z mo RR,~x+y=z\}$ 263.sp 264Given that I,J, and K are initially bound to the intervals $I,J,K$ 265respectively, the fully correct set of solutions with the additional 266constrain 'add(I,J,K)' is given by all triples in the set 267$add inter I times J times K$. 268This set is however infinite, to get an effectively computable procedure 269I will approximate the additional constraint by binding I, J and K 270to smaller intervals. 271So as not to exclude any possible triples the new bindings, 272$I prime, J prime roman ~and~ K prime$ must obey: 273.sp 274 $add inter I times J times K ~subeq~ I prime times J prime times K prime$ 275.sp 276Figure 1 illustrates this process of 277.ul 278narrowing. 279The initial bindings are I:[0,2], J:[1,3] 280and K:[4,6]. After applying 'add(I,J,K)' the smallest possible bindings 281are I:[1,2], J:[2,3] and K:[4,5]. Note that all three intervals have been 282narrowed. 283.pp 284It can easily be seen that: 285.sp 286 $I prime supeq \{x:<x,y,z> ~mo~ add inter I times J times K \}$ 287.br 288 $J prime supeq \{y:<x,y,z> ~mo~ add inter I times J times K \}$ 289.br 290 $K prime supeq \{z:<x,y,z> ~mo~ add inter I times J times K \}$ 291.sp 292If there are 'holes' in the projected set then $I prime$ will be a strict 293superset of the projection, however, $I prime$ will still 294be uniquely determined by the projection. This will be true of any 295subset of $RR sup n$ not just $add$. 296.pp 297In general for 298.sp 299 $R subeq RR sup n,~ I sub 1 , I sub 2 , ... , I sub n mo II(RR)$ 300and $I prime sub 1 , I prime sub 2 , ... , I prime sub n mo II(RR)$ 301.sp 302I will write 303.br 304 $R inter I sub 1 times I sub 2 times ... times I sub n nar 305I prime sub 1 times I prime sub 2 times ... times I prime sub $ 306.br 307when the intervals $I prime sub 1 , I prime sub 2 , ... , I prime sub $ 308are the uniquelly determined smallest intervals including all solutions. 309 310.sh "IV. Comparison with Interval Arithmetic" 311.pp 312.sh "V. Implementation" 313.pp 314.sh "VI. Summary" 315.sh "Acknowledgements" 316.sh "References" 317.ls 1 318.[ 319$LIST$ 320.] 321