[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: My ideas about infinity in Scheme (revised)



  
======= Aubrey Jaffer wrote: =======
> 
>  | Date: Fri, 20 May 2005 10:28:12 +0800
>  | From: "Chongkai Zhu" <mathematica@xxxxxxxxx>
>  | 
>  | I have also considered infinities in Scheme and have some different
>  | ideas:
>  | 
>  | 1. We need both exact (rational) infinity and inexact infinity, that
>  |    is, four special numbers:
>  | 
>  | 1/0 -1/0 +inf.0 -inf.0
>  | 
>  | The first two are rational and thus exact.
> 
> In math texts (http://en.wikipedia.org/wiki/Rational_numbers):
> 
>  A rational number is a ratio or quotient of two integers, usually
>  written as the vulgar fraction a/b, where b is not zero.
> 
>  | Even if this SRFI won't specify exact infinity, it should not use
>  | the "syntax of numerical constants" 1/0 and -1/0, but +inf.0 and
>  | -inf.0 instead, so that a latter SRFI can use 1/0 and -1/0 as exact
>  | infinity.
> 
> In hundreds of years of using rational numbers, mathematicians have
> not discovered 1/0 to be a useful extension to the rational numbers.
> 
>  | This also keeps the tradition that "x/y" (in which x and
>  | y are both integers) is a rational, and the syntax of an inexact
>  | constant contains a dot.
> 
> 1/0 is very evocative for infinity.  While "finit" is a Latin root,
> "infinit" is a Middle English derivation.  Thus "inf" will be not be
> nearly as evocative for most people.  More than programmers see data
> written by programs.
> 
> How about "1/0." and "-1/0."?

Good. I just want (to leave room for) exact infinity and keep
tranditional syntax. "1/0." and "-1/0." will work for that.

> 
>  | For the same reason, the syntax of "indeterminate" should be "0/0"
>  | (exact) and "nan.0" (inexact).  The names +inf.0, -inf.0 and nan.0
>  | were borrowed from PLT scheme.
> 
> While the number syntax of R5RS can be readily extended to include
> +inf.0, -inf.0 (because of the leading sign). "nan.0" runs afoul of
> R5RS 2.1 Identifiers:
> 
>    ... in all implementations a sequence of letters, digits, and
>    "extended alphabetic characters" that begins with a character that
>    cannot begin a number is an identifier.
> 
> If NAN.0 is syntactically a number, then NOT, NULL-ENVIRONMENT, NULL?,
> NUMBER->STRING, NUMBER?, and NUMERATOR are not identifiers.

PLT Scheme has both "+nan.0" and "-nan.0", and it actually doesn't have
"nan.0". So actually it doesn't run afoul of R5RS. A tricky solution.

For "1/0." and "-1/0.", "0/0." will be a nature choice.

> 
>  | Another rationale is utility.  For example, interval arithmetic
>  | will need exact infinity.
> 
> I have used interval arithmetic in Scheme (coding #f for infinity).
> Why does it need exact infinity?

Although you use #f for infinity, it means an exact infinity.
If we have exact infinity, than an interval is a pair of two rational,
which will simplify the code of interval arithmetic (and made it more
readable).

> 
>  | 2. Since we have both positive infinity and negative infinity, we
>  |    are forced to have two (or four, if exactness is also
>  |    considered) zeroes: positive and negative.  IMO, this model is
>  |    more preferable than the "limit".
> 
> Limits are familiar to everyone who has studied the Calculus.  To my
> knowledge, limits have only been implemented on computers in symbolic
> mathematics programs.  To have them in Scheme may be an advancement.
> 

But how can you ensure the limit always return the right answer? I read
the reference implementation only to find that it is a numerical one and
can be easily cheated. AFAIK, CASs do some limits symbolically. And I
can accept a CAS give some wrong result (even different CASs return
different result giving the same input). But Scheme can't do so. 
Then must be an exact algorithm to do each thing in a Scheme spec!

I tried the reference implementation in PLT Scheme:

(define (finite? z)
  (not (and (= z (* 2 z)) (not (zero? z)))))

(define sequence->limit
  (let ((almost-zero
	 (do ((inc 1.0 (/ inc 2)) (linc 2 inc))
	     ((zero? inc) linc))))
    (lambda (proc sequence)
      (define val (proc (cadr sequence)))
      (define lval (proc (car sequence)))
      (define (loop sequence trend ldelta)
	(cond ;; don't PROC last X if diverging or there is no trend
	 ((and (null? (cdr sequence)) (not trend) (zero? ldelta)) val)
	 ((and (null? (cdr sequence)) (not trend) (not (real? val))) #f)
	 ((and (null? (cdr sequence)) (eq? trend 'diverging))
	  (and (real? val) (* (- val lval) +inf.0)))
	 (else
	  (set! lval val)
	  (set! val (proc (car sequence)))
	  (if (finite? val)
	      (let ((delta (magnitude (- val lval))))
		;;(print (car sequence) '==> val 'delta delta trend)
		(case trend
		  ((converging)
		   (cond ((null? (cdr sequence)) val)
			 ((> delta (+ almost-zero ldelta)) #f)
			 (else (loop (cdr sequence) trend delta))))
		  ((diverging)
		   (cond ((< delta ldelta) #f)
			 ((null? (cdr sequence)) val)
			 (else (loop (cdr sequence) trend delta))))
		  (else
		   (cond ((null? (cdr sequence)) val)
			 ((> delta (+ almost-zero ldelta))
			  (loop (cdr sequence) 'diverging delta))
			 ((< delta ldelta)
			  (loop (cdr sequence) 'converging delta))
			 (else
			  (loop (cdr sequence) trend delta))))))
	      val))))
      (cond ((and (finite? val) (finite? lval))
	     (loop (cddr sequence) #f (magnitude (- val lval))))
	    ((finite? lval) val)
	    (else lval)))))

(define limit
  (let ((almost-inc #f)
	(almost-inf #f)
	(sequence+1/0 #f)
	(sequence-1/0 #f))
    (do ((x 1.0 (+ x x))
	 (x-prev 0.0 x))
	((= x +inf.0)
	 (do ((x x-prev (+ x frac))
	      (frac (/ x-prev 2) (/ frac 2)))
	     ((= x +inf.0))
	   (set! almost-inc (* 2 frac))
	   (set! almost-inf x))))
    (set! sequence+1/0
	  (let ((inc (* 1024 almost-inc)))
	    (do ((x (+ almost-inf (* -8 inc)) (+ x inc))
		 (lst '() (cons x lst)))
		((not (finite? x)) (reverse (cons x lst))))))
    (set! sequence-1/0 (map - sequence+1/0))
    (lambda (proc z1 . z2)
      (cond ((finite? z1)
	     (set! z2 (car z2))
	     (if (= z1 (+ z1 z2))
		 (proc z1)
		 (let ((dec (/ z2 8.0)))
		   (do ((x (+ z1 z2) (- x dec))
			(cnt 7 (+ -1 cnt))
			(lst '() (cons x lst)))
		       ((negative? cnt)
			(sequence->limit proc (reverse (cons z1 lst))))))))
	    (else (sequence->limit proc (if (positive? z1)
					    sequence+1/0
					    sequence-1/0)))))))


> (limit (lambda (x) (/ (sin x) x)) 0 1.0e-9)
1.0
> (limit (lambda (x) (/ (sin x) x)) 0 1)
bug /: division by zero
> (limit (lambda (x) (if (exact? x) 1 0)) 0 1.0e-9)
0
> (limit (lambda (x) (if (rational? x) 1 0)) 0 1.0e-9)
1

Note that the final case can't be solved with any numerical method.


>  | For example, in PLT Scheme:
>  | 
>  | Language: Textual (MzScheme, includes R5RS).
>  | > (/ -0.0)
>  | -inf.0
>  | > (/ 0.0)
>  | +inf.0
>  | > (/ +0.0)
>  | +inf.0
>  | > (+ 0.0 -0.0)
>  | 0.0
>  | 
>  | The only compromise is the last case: (+ 0.0 -0.0) evals to +0.0
>  | 
>  | Other computation rules should be straight forward.
> 
> ;; MzScheme version 205:
> 
> > (eqv? 0.0 +0.0)
> #t
> > (eqv? 0.0 -0.0)
> #f
> > (< -0.0 +0.0)
> #f
> > (* 2.0 -0.0)
> 0.0
> > (/ 0.5 -0.0)
> -inf.0
> > (/ (* 2.0 -0.0))
> +inf.0
> 

I never meant what MzScheme does is all right.

IMO, using +0, -0 (+0.0 and -0.0 for inexact numbers), things
should be (x is a positive number):

(* x -0.0) and (* -x 0.0) should be -0.0,
(* x 0.0) and (* -x -0.0) should be 0.0

(< -1/0 -x -0 0 x 1/0)

(= 0 +0)

Anything else that is still not explained?

-		
Chongkai Zhu