assertions are better than types

[Kent M Pitman <KMP@SCRC-STONY-BROOK.ARPA>]

I haven't had a chance to go over the recent burst of proposals in
enough depth to comment, but will get to it.

Let me mention, though, while I'm thinking about it, that with regard to:

    Date: Sun, 17 Mar 85 17:21:05 est
    From: Will Clinger <willc%indiana.csnet@csnet-relay.arpa>

    ... Here is doubly recursive Fibonacci: 

    ; Gerry's proposal 

    (define (fib n) 
      (if (<? n 2)    ; notice again that (integer <?) won't work
	  n
	  ((integer +) (fib ((integer -) n 1)) (fib ((integer -) n 2)))))

    ; With assertions 

    (define (fib n) 
      (assert integer? n)
      (if (<? n 2)
	  n
	  (+ (assert integer? (fib (- n 1)))
	     (assert integer? (fib (- n 2))))))

    ; With a good compiler, this would suffice.  

    (define (fib n) 
      (assert integer? n)
      (if (<? n 2)
	  n
	  (+ (fib (- n 1)) (fib (- n 2)))))

Please be careful when writing your compilers not to copy the Maclisp bug
where:

(DEFUN F (X Y) (DECLARE (FIXNUM X Y)) (PLUS X Y))

turns into a single-instruction addition, ignoring overflow. Gerry's proposal
does not specify much of any way to get code that can do that. It was an
unfortunate mistake since when X and Y are large, the addition can overflow
and bad values can get returned (something GJS's proposal frowns on).

When we thought about this in T a long time ago, we noticed that there are
some kinds of integers which can be said in the abstract to be suitable for
machine-instruction operations. For example, things that count other things
in the address space (eg, array indices) are somehow bounded in a way that
you could usefully take advantage of. It may be useful, therefore, to create
a type called something like INDEX which is like INTEGER but is bounded by
the number of addressable things in the world. Then one can write:
 (ASSERT INDEX? (+ (ASSERT INDEX? X) (ASSERT INDEX? Y)))
to get a machine-instruction addition in those cases where it is reliable.
Systems which had addressing schemes that made it impossible to place a bound
on the size of an INDEX could just treat it as synonymous with INTEGER, which
would be invisible to the user except performance-wise.

By the way, changing the subject slightly, but still on the topic of assertions,
my original proposal for T was to have PLUS and + be synonyms, but to have
operators ASSERT and MAP-ASSERT which let one write customizations such as:

 (DEFINE-OPEN-CODED (+ . ARGS)
   (ASSERT INTEGER? (APPLY PLUS (MAP-ASSERT INTEGER? ARGS))))

 so that (+ X Y) 
 would be like (ASSERT INTEGER? (PLUS (ASSERT INTEGER? X) (ASSERT INTEGER? Y)))

or

 (DEFINE-OPEN-CODED (INTEGER OPERATOR)
   (LAMBDA ARGS (ASSERT INTEGER? (APPLY OPERATOR (MAP-ASSERT INTEGER? ARGS)))))

 so that ((INTEGER +) X Y)
 would be like (ASSERT INTEGER? (+ (ASSERT INTEGER? X) (ASSERT INTEGER? Y)))

I think MAP-ASSERT got lost from T somewhere along the way, but perhaps it 
would be worth picking back up if people thought this sort of thing was fun.