Title

Type-Restricted Numerical Functions

Author

Aubrey Jaffer

Status

This SRFI is currently in ``final'' status. To see an explanation of each status that a SRFI can hold, see here. To provide input on this SRFI, please mail to <srfi minus 94 at srfi dot schemers dot org>. See instructions here to subscribe to the list. You can access previous messages via the archive of the mailing list.

Abstract

In the coding of numerial calculations in latent-typed languages it is good practice to assure that those calculations are using the intended number system. The most common number systems for programmatic calculations are the integers, reals, and complexes. This SRFI introduces 14 real-only and 3 integer-only variants of R5RS procedures to facilitate numerical type checking and declaration.

Issues

With the exception of `=' and `zero?', Scheme's numerical comparison operators are already restricted to real numbers.

The larger question is whether to make integer-only versions of `=', `zero?', `<', `>', `<=', `>=', `positive?', and `negative?'. (`odd?' and `even?' are already integer-only).

Because `quotient', `modulo', and `remainder' constrain both their inputs and outputs, and because `vector-ref', `vector-set!', `string-ref', `string-set!', `list-ref', `list-tail', `odd?', and `even?' constrain one of their inputs as integers, I think that integer-only comparison operators are not needed.

Terminology

Use of the terms integer, real, and complex follows R5RS and SRFI-70. All integers are real; all reals are complex.

Rationale

The infinities introduced by SRFI-70 extend the range of Scheme numerical calculations. But with that larger range, the signaling of numerical errors resulting from bad inputs or mistakes in program logic is delayed, and sometimes missed entirely.

The SRFI-77 shotgun approach creates type-restricted variants of all the numerical operations, but does not allow those operations to signal errors when they are forced out of bounds! For instance `flsqrt' and `inexact-sqrt':

Returns the principal square root of z [sic]. For a negative argument, the result may be a NaN, or may be some meaningless flonum.
SRFI-77 here misses an opportunity to increase the declarative power of Scheme numerical operations. By the present SRFI making `real-sqrt' and `real-ln' of negative numbers an error, compilers can deduce that the expressions calculating the inputs to `real-sqrt' and `real-ln' must return non-negative reals. Similarly, use of the other real-only transcendental functions declares their inputs and outputs to be real.

For addition, subtraction, negation, and multiplication, the results of the operation will be members of the same number system as the operation's inputs when those inputs are all of the same number system. It would be unnecessary tedium to apply run-time tests to intermediate or final results of chains of these common operations.

Division of reals yields a real; division of complexes yields a complex. So real and complex division also need not be distinguished. `max' of integers yields an integer; and `max' of reals yields a real. So these are not distinguished; neither is `min'.

But division of integers can yield a non-integer. To address this, R5RS defines a division operator, `quotient', which is specified only for integer arguments. This SRFI mandates that `quotient', `remainder', and `modulo' signal an error when passed an argument which is not an exact-integer.

The criterion is exact-integer instead of just integer so that the results of integer calculations are guaranteed to be of the correct type to pass as index arguments.

Arithmetic operations on mixtures of integer, real, and complex numbers are well defined and very common in use. This SRFI does not alter R5RS behavior of arithmetic operations with mixed type inputs.

This SRFI introduces some integer-only and real-only variants of the transcendental functions of R5RS. Those type-restricted functions are mandated to signal an error if called with arguments or producing results which are not in the designated number system. Thus (real-sqrt -1) must signal an error even though -1 is an exact real. Following SRFI-70, #+inf.0 and #-inf.0 are real; NaNs are not. None of these infinities is an integer.

The complex transcendental functions from R5RS are unchanged by this SRFI. They accept complex (hence also integer and real) arguments. The functions `abs', `make-rectangular', and `make-polar'; and `atan' when called with two arguments are changed to require them to signal an error when passed a non-real number. Note that integers are real numbers.

Although the language of this SRFI calls for error signaling, that signaling is not limited to run-time. An error can be reported during compilation. Run-time type testing can be skipped if the compiler can prove that arguments are of the correct type and within the correct range. It would be reasonable for SRFI-77's "unsafe mode" to disable run-time checking.

single argument
Exact-integer Real Complex
real-exp exp
real-ln ln
real-atan atan
real-acos acos
real-asin asin
real-tan tan
real-cos cos
real-sin sin
abs abs magnitude
integer-sqrt real-sqrt sqrt
multi-argument
Exact-integer Real Complex
integer-expt real-expt expt
integer-log real-log
atan
+ + +
- - -
* * *
/ /
quotient quo
modulo mod
remainder rem
max max
min min

The `arithmetic-shift' and `integer-length' procedures of SRFI-60 are related to the base-2 exponential and logarithm respectively, but are not included in the table.

`mod' and `rem' are the real functions from Common-Lisp. `quo' is the analogous division (truncate (/ x1 x2)).

Although not a type-restricted function, `ln' is added as a synonym for `log' because `log' is not used consistently to denote the natural logarithm.

`Real-log' returns the logarithm of its second argument using its first argument as the base. `integer-log' is the analogous two-argument logarithm function for integers.

Specification

procedure: real-exp x
procedure: real-ln x
procedure: real-log y x
procedure: real-sin x
procedure: real-cos x
procedure: real-tan x
procedure: real-asin x
procedure: real-acos x
procedure: real-atan x
procedure: atan y x

These procedures are part of every implementation that supports general real numbers; they compute the usual transcendental functions. `Real-ln' computes the natural logarithm of x (not the base ten logarithm); `real-log' computes the logarithm of x base y, which is (/ (real-ln x) (real-ln y)) If arguments x and y are not both real; or if the correct result would not be real, then these procedures signal an error.

procedure: real-sqrt x

For non-negative real x the result will be its positive square root; otherwise an error will be signaled.

procedure: integer-sqrt n

For non-negative integer n returns the largest integer whose square is less than or equal to n; otherwise signals an error.

procedure: integer-log k1 k2

Returns the largest exact integer whose power of k1 is less than or equal to k2. If k1 or k2 is not a positive exact integer, then integer-log signals an error.

procedure: integer-expt n1 n2

Returns n1 raised to the power n2 if that result is an exact integer; otherwise signals an error.

(integer-expt 0 n2)
returns 1 for n2 equal to 0;
returns 0 for positive integer n2;
signals an error otherwise.

procedure: real-expt x1 x2

Returns x1 raised to the power x2 if that result is a real number; otherwise signals an error.

(real-expt 0.0 x2)
returns 1.0 for x2 equal to 0.0;
returns 0.0 for positive real x2;
signals an error otherwise.

procedure: quo x1 x2
procedure: rem x1 x2
procedure: mod x1 x2

x2 should be non-zero.

    (quo x1 x2)                     ==> n_q
    (rem x1 x2)                     ==> x_r
    (mod x1 x2)                     ==> x_m

where n_q is x1/x2 rounded towards zero, 0 < |x_r| < |x2|, 0 < |x_m| < |x2|, x_r and x_m differ from x1 by a multiple of x2, x_r has the same sign as x1, and x_m has the same sign as x2.

From this we can conclude that for x2 not equal to 0,

     (= x1 (+ (* x2 (quo x1 x2))
           (rem x1 x2)))
                                       ==>  #t

provided all numbers involved in that computation are exact.


(quo 2/3 1/5)                          ==>  3
(mod 2/3 1/5)			       ==>  1/15

(quo .666 1/5)			       ==>  3.0
(mod .666 1/5)			       ==>  65.99999999999995e-3

procedure: ln z

These procedures are part of every implementation that supports general real numbers. `Ln' computes the natural logarithm of z.

In general, the mathematical function ln is multiply defined. The value of ln z is defined to be the one whose imaginary part lies in the range from -pi (exclusive) to pi (inclusive).


The specification of two-argument `atan' above and the following six procedures are changed from R5RS. Deleted text is marked with a line through it. Additions and changes are marked in red.

procedure: make-rectangular x1 x2
procedure: make-polar x3 x4

These procedures are part of every implementation that supports general complex numbers. Suppose x1, x2, x3, and x4 are real numbers and z is a complex number such that

z = x1 + i x2 = x3 ei x4

Then

(make-rectangular x1 x2)               ==> z
(make-polar x3 x4)                     ==> z

where -pi < x_angle <= pi with x_angle = x4 + 2pi n for some integer n.

If an argument is not real, then these procedures signal an error.

library procedure: abs x

For real argument x, `abs' returns the absolute value of x; otherwise it signals an error.

(abs -7)                               ==>  7

procedure: quotient n1 n2
procedure: remainder n1 n2
procedure: modulo n1 n2

These procedures implement number-theoretic (integer) division. n2 should be non-zero. If n1 is not an exact integer, or if n2 is not an exact non-zero integer, an error is signaled. All three procedures return exact integers. If n1/n2 is an integer:

    (quotient n1 n2)                   ==> n1/n2
    (remainder n1 n2)                  ==> 0
    (modulo n1 n2)                     ==> 0

If n1/n2 is not an integer:

    (quotient n1 n2)                   ==> n_q
    (remainder n1 n2)                  ==> x_r
    (modulo n1 n2)                     ==> x_m

where n_q is n1/n2 rounded towards zero, 0 < |x_r| < |n2|, 0 < |x_m| < |n2|, x_r and x_m differ from n1 by a multiple of n2, x_r has the same sign as n1, and x_m has the same sign as n2.

From this we can conclude that for integers n1 and n2 with n2 not equal to 0,

     (= n1 (+ (* n2 (quotient n1 n2))
           (remainder n1 n2)))
                                       ==>  #t
provided all numbers involved in that computation are exact.

(modulo 13 4)                          ==>  1
(remainder 13 4)                       ==>  1

(modulo -13 4)                         ==>  3
(remainder -13 4)                      ==>  -1

(modulo 13 -4)                         ==>  -3
(remainder 13 -4)                      ==>  1

(modulo -13 -4)                        ==>  -1
(remainder -13 -4)                     ==>  -1

(remainder -13 -4.0)                   ==>  -1.0  ; inexact

Implementation

The error procedure is from SRFI-23. The ash and integer-length procedures are from SRFI-60.
(require 'srfi-60)			;ash, integer-length
(require 'srfi-23)			;error

(define (type-error procedure . args) (apply error procedure args))
;@
(define (integer-expt x1 x2)
  (cond ((and (exact? x1) (integer? x1)
	      (exact? x2) (integer? x2)
	      (not (and (not (<= -1 x1 1)) (negative? x2))))
	 (expt x1 x2))
	(else (type-error 'integer-expt x1 x2))))
;@
(define (integer-log base k)
  (define (ilog m b k)
    (cond ((< k b) k)
	  (else
	   (set! n (+ n m))
	   (let ((q (ilog (+ m m) (* b b) (quotient k b))))
	     (cond ((< q b) q)
		   (else (set! n (+ m n))
			 (quotient q b)))))))
  (define n 1)
  (define (eigt? k j) (and (exact? k) (integer? k) (> k j)))
  (cond ((not (and (eigt? base 1) (eigt? k 0)))
	 (type-error 'integer-log base k))
	((< k base) 0)
	(else (ilog 1 base (quotient k base)) n)))

;;;; http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/math/isqrt/isqrt.txt
;;; Akira Kurihara
;;; School of Mathematics
;;; Japan Women's University
;@
(define integer-sqrt
  (let ((table '#(0
		  1 1 1
		  2 2 2 2 2
		  3 3 3 3 3 3 3
		  4 4 4 4 4 4 4 4 4))
	(square (lambda (x) (* x x))))
    (lambda (n)
      (define (isqrt n)
	(if (> n 24)
	    (let* ((len/4 (quotient (- (integer-length n) 1) 4))
		   (top (isqrt (ash n (* -2 len/4))))
		   (init (ash top len/4))
		   (q (quotient n init))
		   (iter (quotient (+ init q) 2)))
	      (cond ((odd? q) iter)
		    ((< (remainder n init) (square (- iter init))) (- iter 1))
		    (else iter)))
	    (vector-ref table n)))
      (if (and (exact? n) (integer? n) (not (negative? n)))
	  (isqrt n)
	  (type-error 'integer-sqrt n)))))

(define (must-be-exact-integer2 name proc)
  (lambda (n1 n2)
    (if (and (integer? n1) (integer? n2) (exact? n1) (exact? n2))
	(proc n1 n2)
	(type-error name n1 n2))))
;@
(define quotient  (must-be-exact-integer2 'quotient quotient))
(define remainder (must-be-exact-integer2 'remainder remainder))
(define modulo    (must-be-exact-integer2 'modulo modulo))

;;;; real-only functions
;@
(define (quo x1 x2) (truncate (/ x1 x2)))
(define (rem x1 x2) (- x1 (* x2 (quo x1 x2))))
(define (mod x1 x2) (- x1 (* x2 (floor (/ x1 x2)))))

(define (must-be-real name proc)
  (lambda (x1)
    (if (real? x1) (proc x1) (type-error name x1))))
(define (must-be-real+ name proc)
  (lambda (x1)
    (if (and (real? x1) (>= x1 0))
	(proc x1)
	(type-error name x1))))
(define (must-be-real-1+1 name proc)
  (lambda (x1)
    (if (and (real? x1) (<= -1 x1 1))
	(proc x1)
	(type-error name x1))))
;@
(define ln log)
(define abs       (must-be-real 'abs abs))
(define real-sin  (must-be-real 'real-sin sin))
(define real-cos  (must-be-real 'real-cos cos))
(define real-tan  (must-be-real 'real-tan tan))
(define real-exp  (must-be-real 'real-exp exp))
(define real-ln   (must-be-real+ 'ln ln))
(define real-sqrt (must-be-real+ 'real-sqrt sqrt))
(define real-asin (must-be-real-1+1 'real-asin asin))
(define real-acos (must-be-real-1+1 'real-acos acos))

(define (must-be-real2 name proc)
  (lambda (x1 x2)
    (if (and (real? x1) (real? x2)) (proc x1 x2) (type-error name x1 x2))))
;@
(define make-rectangular (must-be-real2 'make-rectangular make-rectangular))
(define make-polar       (must-be-real2 'make-polar make-polar))

;@
(define real-log
  (lambda (base x)
    (if (and (real? x) (positive? x)
	     (real? base) (positive? base))
	(/ (ln x) (ln base))
	(type-error 'real-log base x))))
;@
(define (real-expt x1 x2)
  (cond ((and (real? x1)
	      (real? x2)
	      (or (not (negative? x1)) (integer? x2)))
	 (expt x1 x2))
	(else (type-error 'real-expt x1 x2))))

;@
(define real-atan
  (lambda (y . x)
    (if (and (real? y)
	     (or (null? x)
		 (and (= 1 (length x))
		      (real? (car x)))))
	(apply atan y x)
	(apply type-error 'real-atan y x))))

Copyright

Copyright (C) Aubrey Jaffer 2006. All Rights Reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.


Editor: Donovan Kolbly