Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!munnari.oz.au!mudla!ok
From: ok@mudla.cs.mu.OZ.AU (Richard O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: arithmetic overflow checking
Message-ID: <3942@munnari.oz.au>
Date: 9 May 90 03:36:01 GMT
References: <870@cluster.cs.su.oz>
Sender: news@cs.mu.oz.au
Lines: 68

In article <870@cluster.cs.su.oz>, andrewt@cluster.cs.su.oz (Andrew Taylor) writes:
> Some (most?) Prolog implementations do not check for overflow on
> (integer) arithmetic.

Some Prolog systems (for example LPA) _do_ check for overflow,
and then deliver the result as a floating-point number.  IMEO
(like IMHO except E=educated) this kind of *wrong* answer is
just as bad as the other kind, but some people like it.

I'd like to put in a kind word for ZYX Prolog; those fine people
have provided arbitrary precision integers (just like Common Lisp,
which ZYX Prolog has been very strongly influenced by).  Instead
of giving you a wrong answer or apologising for not being able to
give a right answer, ZYX Prolog gives you the right answer.   Nice.

> This doesn't seem acceptable to me.
> Does it worry anyone else?

I don't find it acceptable either, and yes I'm worried by it.
(I am also very worried indeed by C...)

> I'm interested to know why this is. Is it laziness?
> Is it inherited from the implementation languages (often C)?

Well, Xerox Quintus Prolog provides arbitrary precision integers.
They came free with the implementation language (Lisp).  If you
are trying to produce a reasonably portable system (like SB Prolog)
it is rather tricky to detect or handle integer overflow in a
portable way.  For example, because the C standard permits an
implementation to signal exceptions for overflow in signed arithmetic,
all your operations have to be done with unsigned arithmetic.
Instead of writing
	X = Y + Z;
in your C code, you have to write
	unsigned long lY = Y, lZ = Z;
	unsigned long lX = lY+lZ;

	if (Y >= 0 ? Z >= 0 && (long)lX < 0
		   : Z < 0  && (long)lX >= 0)
	    /* the answer has the wrong sign */
	    signal_overflow_in_plus();
	else
	    X = (long)lX;

You really don't want to see what multiplication looks like.
The result can't honestly be called fast.  The way to get fast
safe integer arithmetic is to rely on hardware generated overflow
signals (either a flag in the PSW or a trap), but you can't get
at that information *portably* in C.  And of course if you are
stealing tag bits out of the number, things get worse.  If you
steal bits from the top of a word, you have to do
	unsigned long lY = Y << N_TAG_BITS;
	unsigned long lZ = Z << N_TAG_BITS;
	...
	else
	    X = (lX >> N_TAG_BITS) | INT_TAG;
If you steal bits from the bottom of a word, it's easier:
	unsigned long lX = (lY-INT_TAG) + lZ;

If you want to make a *fast* Prolog implementation, you have fun
till it hurts hacking assembly code on lots of machines, and until
you actually try it, you wouldn't believe how different the ways
of detecting overflow are on some machines and how hard some
architects have made it.

Speed, the difficulty of doing it, and the tradition that it is
ok for computer programming languages to do arithmetic wrong, all
play a part.