Xref: utzoo comp.theory:1777 comp.lang.functional:721
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!decwrl!asylum!osc!jgk
From: jgk@osc.COM (Joe Keane)
Newsgroups: comp.theory,comp.lang.functional
Subject: Re: do computers believe in real numbers?
Summary: They do, but languages tend not to.
Keywords: redundant representation
Message-ID: <4722@osc.COM>
Date: 5 Apr 91 05:59:12 GMT
References: <7197@munnari.oz.au> <91090.154205NN1@awiwuw11.wu-wien.ac.at> <6878@rex.cs.tulane.edu>
Reply-To: jgk@osc.COM (Joe Keane)
Followup-To: comp.theory
Organization: Versant Object Technology, Menlo Park, CA
Lines: 76

We can characterise constructive real numbers by the primitive operations that
are provided on them.  For example, one way to describe the numbers in [0,2[
is by the following operations:
	return the integer part of a given real (0 or 1)
	return twice the fractional part of a given real (another real)
	make a new real given its integer part and twice its fractional part

It should be clear that these operations are all that is needed.  Given them,
you can write functions to add two numbers, and so on.  I have restricted the
numbers to [0,2[ for simplicity, but i trust you will see that this isn't a
problem.

These operations suggest a simple implementation.  We can represent a real
number by a (possibly lazy) list of 0 or 1.  Then the two operations are just
car, cdr, and cons on the representation.

Here is another set of operations which can define real numbers:
	return the integer part of a given real
	return the reciprocal of the fractional part of a given real
	make a new real given its integer part and the reciprocal of its
		fractional part

These operations suggest a different simple implementation.  We can represent
a real number by a list of integers which is its continued fraction expansion.
Again the operations are just car, cdr, and cons.

There's no reason for us to think that either or these sets of operations (or
some other) is the `right' one to define real numbers.  Rather, given an
implementation which directly supports a set of operations powerful enough to
define the reals, we can implement the other operations in terms of these.
For a given implementation, some operations are primitive (they work directly
on the representation) and some are generic, built from primitive operations.

Now we can code up any number of implementations, and if they support the
basic operations, they will work together.  That is, we can add together a
number in binary form and one in continued fraction form without any problem.

Although these operations seem intuitive, there's a problem with them.  They
are too strict, because they require exact tests.  For example taking the
integer part leaves no room for error: floor(0.9999) = 0 while floor(1.0000) =
1.  So in place of a strict test like x > 0, we can have an operation like
this:
	given x return either x < 1 or x > -1
Note that the results overlap.  By allowing a choice of return values for some
range of arguments, we eliminate the problems of strict tests.

A similar operation is the following:
	given x and a positive number epsilon, return either
		x < 0, x > 0, or |x| < epsilon
In this case we can provide a tolerance as small as we want, but not zero.  Of
course by providing a smaller tolerance we can expect the test to take longer.
I hope you see that these operations are equivalent, assuming we also have
some simple ones like `double a number'.

Tests like this suggest a redundant number representation.  It's been
recognized since Turing that redundant representations are the way to go.
With a non-redundant representation, even such a simple thing as adding two
numbers can require you to look at an unbounded number of digits of the
arguments.  In contrast, a redundant representation allows you to generate the
result `on the fly' with a minimal (bounded) amount of look-ahead.

Of course people want to see numbers in decimal or test if they're positive,
so we have to convert to a non-redundant form some time.  But by delaying this
as long as possible, we eliminate most of the problems with things looking too
far ahead.  When there is such a problem, it's because the user asked a
question which is hard to answer, and not because we did something wrong.

So how do you implement these things?  Well, all you have to do is pick the
right set of combinators, and algorithms to go with them.  Of course this
makes it sound simple.  Really a lot of problems (compiling programs for
example) can be reduced to ``pick the right set of combinators'' (plus
algorithms to use them of course).  That may give some insight, but it doesn't
necessarily make it easy.
--
Joe Keane, supercombinator hacker
jgk@osc.com (...!uunet!stratus!osc!jgk)