Algorithms in Computational Geometry and Computer Aid-ed Design are
often developed for the Real RAM model of computation, which assumes
exactness of all the input arguments and operations.  In practice,
however, the exactness imposes tremendous limitations on the algorithms
-- even the basic operations become uncomputable, or prohibitively
slow.  When the computations of interest are limited to determining the
sign of polynomial expressions over floating point numbers, faster
approaches are available. One can evaluate the polynomial in floating
point first, together with some estimate of the rounding error, and fall
back to exact arithmetic only if this error is too big to determine the
sign reliably.  A particularly efficient variation on this approach has
been used by Shewchuk in his robust implementations of Orient and
InSphere geometric predicates.

We extend Shewchuk's method to arbitrary polynomial expressions.  The
expressions are given as programs in a suitable source language
featuring basic arithmetic operations of addition, subtraction,
multiplication and squaring, which are to be perceived by the programmer
as exact. The source language also allows for anonymous functions, and
thus enables the common functional programming technique of staging.
The method is presented formally through several judgments that govern
the compilation of the source expression into target code, which is then
easily transformed into SML or, in case of single-stage expressions,
into C.