Re: [srfi-70] Limit Aubrey Jaffer 24 May 2005 17:56 UTC

 | From: Sebastian Egner <xxxxxx@philips.com>
 | Date: Tue, 24 May 2005 11:00:58 +0200
 |
 | Jens Axel Søgaard wrote:
 | > The draft says
 | >
 | >    Function: limit proc z1 z2
 | >    Function: limit proc -1/0
 | >    Function: limit proc 1/0
 | >
 | >      Proc must be a procedure taking a single inexact argument.
 | >
 | >      Limit computes the mathematical limit of proc as its argument
 | >      approaches z1 from z1 + z2. Limit returns a complex number or
 | >      real infinity if the limit exists; and `#f' otherwise.
 | >
 | > Is this well defined?
 |
 | No, of course it is not.
 |
 | It is another smoke screen of the "wish it were so" type related to
 | floating point representations of rational numbers.
 |
 | But seriously...  The problem with LIMIT is that it tries to solve
 | an unsolvable problem.  There is no "finite-precision version" of
 | taking general limits.  For certain types of limits,
 | e.g. integrals, there is a theory what you get and how useful that
 | might be.  These computations are usually not limits of simple
 | sequences but some sort of infinite summation with known
 | convergence properties (e.g. all the standard transcendental
 | functions, exp/log/sin/cos etc.)

Here is a more serious specification for LIMIT:

  Function: limit proc z1 z2

      Proc must be a procedure taking a single inexact argument.

      z2 should be chosen so that proc is expected to be monotonic or
      constant on arguments between z1 and z1 + z2.

      Limit computes the limit of proc as its argument approaches z1
      from z1 + z2.  Limit returns a complex number or real infinity
      or `#f'.

  Function: limit proc -1/0

      Computes the limit of proc as its its argument approaches -1/0
      (from -179.76931348606807e306 if using IEEE-754 flonums).

  Function: limit proc 1/0

      Computes the limit of proc as its its argument approaches 1/0
      (from 179.76931348606807e306 if using IEEE-754 flonums).

      Limit examines the magnitudes of the differences between
      successive values returned by proc called with a succession of
      numbers ending with the second argument to limit.

      If the magnitudes of differences are monotonically decreasing,
      then the value of proc at the second argument is returned.  If
      the magnitudes of differences are monotonically increasing, then
      1/0 or -1/0 is returned if the values returned by proc are real;
      otherwise #f.

      If the magnitudes of differences are constant (within the
      positive inexact number closest to 0), then the value of proc on
      the second argument is returned, unless the magnitudes of
      differences are zero; in which case the value of proc on the
      second to last value is returned.  If the magnitudes of
      differences are not monotonic, then #f is returned.

  (limit / 0 1.0e-9)                              ==> 1/0
  (limit / 0 -1.0e-9)                             ==> -1/0
  (limit / -1/0)                                  ==> 0.0
  (limit / 1/0)                                   ==> 0.0
  (limit (lambda (x) (/ x x)) 0 1.0e-9)           ==> 1.0
  (limit (lambda (x) (/ (log x) x)) 0 1.0e-9)     ==> -1/0
  (limit (lambda (x) (/ (log x) x)) 0 -1.0e-9)    ==> #f
  (limit (lambda (x) (/ (magnitude (log x)) x)) 0 -1.0e-9)
						  ==> -1/0
  (limit (lambda (x) (/ x (log x))) 0 1.0e-9)     ==> 0.0
  (limit sin 1/0)                                 ==> #f
  (limit (lambda (x) (sin (/ x))) 0 1.0e-9)       ==> #f
  (limit (lambda (x) (sin (/ x))) 0 -1.0e-9)      ==> #f
  (limit (lambda (x) (sin (/ x))) 1/0)            ==> 0.0
  (limit (lambda (x) (/ (+ (exp (/ x)) 1))) 0 1.0e-9)
						  ==> 0.0
  (limit (lambda (x) (/ (+ (exp (/ x)) 1))) 0 -1.0e-9)
						  ==> 1.0
  (limit (lambda (x) (expt (tan x) (cos x))) (/ pi 2) 1.0e-18)
						  ==> 1.0000000000000022

 | A general LIMIT procedure on the other hand can only be specified
 | as "returns what the reference implementation computes."  Unless
 | you want to redefine the meaning of "mathematical limit", which
 | might be exceptionally controversal.

Because of:

      z2 should be chosen so that proc is expected to be monotonic or
      constant on arguments between z1 and z1 + z2.

this new definition of LIMIT does not need the full mathematical power
of analysis; and should serve as a specification more abstract than
"what the reference implementation computes".  It is possible to fool
limit, but it is possible to fool any programmed transcendental
function: (sin (* 1e18 (atan 1)))

 | What I said until now is just the famous "It might work in
 | practice, but it will never work in theory." Now my real problem is
 | that I missed which important problem the LIMIT procedure solves
 | (satisfactorily or not) in Scheme.

LIMIT was created so that static choices for limit cases like:

  (expt 0 0)                                    ==> 1
or
  (expt 0 0)                                    ==> 0/0

don't necessitate workarounds when computing with functions like
(lambda (x) (expt x x)):

  (limit (lambda (x) (expt x x)) 0 1e-9)        ==> 1/0

 | With the program you can select your favorite limiting value by
 | varying c:
 |
 |     (limit (lambda (x) (sin (/ 1.0 x))) 0 1) => #f          ; according to spec
 |     (limit (lambda (x) (sin (/ 0.2 x))) 0 1) => 1/0
 |     (limit (lambda (x) (sin (/ 0.3 x))) 0 1) => -1/0

With smaller z2 values, these limits are well behaved:

  (limit (lambda (x) (sin (/ 1.0 x))) 0 1e-9) ==> #f
  (limit (lambda (x) (sin (/ 0.2 x))) 0 1e-9) ==> #f
  (limit (lambda (x) (sin (/ 0.3 x))) 0 1e-9) ==> #f