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

Re: assertions are better than types

Hi.  Before you jump, I just want to clarify a few points about what I
meant by type-restricted operators -- I know I didn't say this in the
draft I sent you, but I didn't realize the scope of possible
confusion.  I rspond pointwise:

Willc:  Speaking for myself, I would not want to clutter my code 
	with all these type-restricted operators as I write the code, 
	because	it would make the code less readable.  (I guess 
	readability is more important to my debugging processes than are 
	type checks.) I would be willing to add type assertions when the 
	time came to make the code run fast.  Hence for me at least, the 
	type restrictions would be more important as advice to the 
	compiler than as debugging aids.  

GJS:  I agree, usually we would not write the ugly kind of code which
is illustrated below:

(define (tak x y z) 
  (if (not (<? y x))      ; notice that you can't say (integer <?)
      (tak (tak ((integer -1+) x) y z)
	   (tak ((integer -1+) y) z x)
	   (tak ((integer -1+) z) x y))))

Instead we would write something like this:

(define tak
  (let ((-1+ (integer -1+))
	(<? (integer <?)))	;Note that we can say this, see below!
    (lambda (x y z) 
      (if (not (<? y x))	
	  (tak (tak (-1+ x) y z)
	       (tak (-1+ y) z x)
	       (tak (-1+ z) x y))))))

Presumably, with a good compiler it would be just as efficient to

(define (tak x y z) 
  (let ((-1+ (integer -1+))
	(<? (integer <?)))	;Note that we can say this, see below!
    (if (not (<? y x))	
	(tak (tak (-1+ x) y z)
	     (tak (-1+ y) z x)
	     (tak (-1+ z) x y)))))

Willc:	The type restrictors require that all operands and the 
	result be of the same type.  This works reasonably well for 
	numeric operators but is going to be awkward when the time comes 
	to generalize it to other operators.  How am I going to tell the 
	compiler that the first argument to vector-ref is a vector of 

Willc:	These procedures take a numeric operator op and return a 
	procedure that acts like op except that it is restricted to 
	operate on numbers of the specified type and to return numbers 
	of the specified type.

GJS: The type restrictions are not intended to be simply error-checking
on the type of the inputs and outputs, but rather to be an entry to a
more coherent system built on the numerical tower.  The idea is that
for each kind of number there is a set of appropriate kinds of operations
that make sense for it.  For example, the INTEGERS are a ring, hence they
do not support arbitrary division.  This does not stop us from defining
"/" for the INTEGERS to be anything we like, such as an entry to higher
types on the tower.  Additionally, I am not even attempting to clarify
the types for things like strings or vectors of strings, since they do
not have the mathematical structure of numbers... This is trying to be a
coherent theory about numbers, rather than an incoherent theory of

For example, Hal and I have been hacking a new version of generic 
arithmetic based on these principles -- I include a fragment for your
amusement.  Basically, there is an operation table, and "restrictions"
like INTEGER are things that transform the generic operator, like +,
into the actual operation from the table.

The following code creates a "rational package" for a
given RING, the new objects have type FIELD.

;;; Rational operations generator

(define (make-rational-operations! ring field)

  (let ((+r (ring +)) (-r (ring -)) (*r (ring *)) (negate-r (ring negate)) 
	(=r (ring =)) (gcd (ring gcd)) (quotient (ring quotient))
	(sign-r (ring sign)) (one-r (ring 'one)) (zero-r (ring 'zero)))

    (define (make-rational n d)
      (let ((s (sign-r d)))
	(cond ((=r one-r s)
	       (cons '*numeric-type*
		     (cons field (cons n d))))
	      ((=r zero-r s)
	       (error "Bad rational construction" field (list n d)))
	       (cons '*numeric-type*
		     (cons field
			   (cons (quotient n s)
				 (quotient d s))))))))
    (define numer caddr)
    (define denom cdddr)

    (define (+_rational x y)
      (let ((d1 (gcd (denom x) (denom y))))
	(if (=r one-r d1)    ;GIGO
	    (make-rational (+r (*r (numer x) (denom y))
			      (*r (denom x) (numer y)))
			   (*r (denom x) (denom y)))
	    (let ((dx/d1 (quotient (denom x) d1)))
	      (let ((tem (+r (*r (quotient (denom y) d1) (numer x))
			    (*r dx/d1 (numer y)))))
		(let ((d2 (gcd tem d1)))
		  (make-rational (quotient tem d2)
				 (*r dx/d1
				    (quotient (denom y) d2)))))))))

    (define (-_rational x y)
      (+_rational x (make-rational (negate-r (numer y)) (denom y))))

    (define (*_rational x y)
      (let ((d1 (gcd (numer x) (denom y)))
	    (d2 (gcd (numer y) (denom x))))
	(make-rational (*r (quotient (numer x) d1)
			  (quotient (numer y) d2))
		       (*r (quotient (denom x) d2)
			  (quotient (denom y) d1)))))

    (define (/_rational x y)
      (*_rational x (make-rational (denom y) (numer y))))

    (define (=_rational x y)
      (and (=r (numer x) (numer y)) (=r (denom x) (denom y))))

    (define (negate-rational x)
      (make-rational (negate-r (numer x)) (denom x)))

    (define (recip-rational x)
      (make-rational (denom x) (numer x)))

    (define (raise i)
      (make-rational i one-r))

    (put-coercion! raise ring field)

    (put-op! (raise zero-r) 'zero field)
    (put-op! (raise one-r) 'one field)

    (put-op! +_rational + field)
    (put-op! -_rational - field)
    (put-op! *_rational * field)
    (put-op! /_rational / field)
    (put-op! =_rational = field)

    (put-op! negate-rational negate field)
    (put-op! recip-rational recip field)

    (put-op! (lambda (x) (sign-r (numer x))) sign field)

    (put-op! numer numerator field)
    (put-op! denom denominator field)


;;;Now we can use this to define the rationals over integers

(define (rational op) (get-op op rational))

(define (rational? x)
  (or (integer? x)
      (eq? (numeric-type x) rational)))

(make-rational-operations! integer rational 'rational)

;;;For these particular rationals, we may also want some additional
;;;operations that are not sensible for arbitrary rationals, e.g.,
;;;based upon polynomial rings.  For example:

(define (raise-rational-unary-operation op)
  (lambda (x) (op (rational->real x))))

(put-op! (raise-rational-unary-operation sqrt) sqrt rational)
(put-op! (raise-rational-unary-operation sin) sin rational)
(put-op! (raise-rational-unary-operation cos) cos rational)
(put-op! (raise-rational-unary-operation tan) tan rational)

(put-op! (raise-rational-unary-operation real-part) real-part rational)
(put-op! (raise-rational-unary-operation imag-part) imag-part rational)
(put-op! (raise-rational-unary-operation magnitude) magnitude rational)
(put-op! (raise-rational-unary-operation angle) angle rational)