Kawa proposed typing changes

[Per Bothner]

On 09/26/2009 12:23 AM, Helmut Eller wrote:
> * Per Bothner [2009-09-25 21:52+0200] writes:
>
>> (1) A top-level define will become writable only in the
>> current "module".  I.e. you can set! it in the current
>> source file, but not in other source files.  This will
>> not (at least for now) apply to the "interactive" mode
>> (i.e. the repl, eval, load) when forms are read one
>> at a time, because of the behavior/implementation of
>> the "top-level".
>
> How does this interact with macros?  A macro defined in module A may
> expand to a set! expression when used in module B.  This would no longer
> work, right?  Can R6RS macros expand to non-exported bindings?

Good questions.  I don't believe it's an issue for R6RS, since *nobody*
is allowed to set! an exported binding, so whether the set! is
direct or macro-generated - it's not allowed.

By lexical scoping, if we allows module-local modification,
then we should allow external modification if the set!
is in module-local but exported macro.  But that may be
difficult to both specify and implement.  The primary goal
of prohibiting module-external set! is to enable
type-inferencing and other optimizations (such as inlining).
How can the compiler determine that it "sees" all set!s
if we allow a macro to expand to a set!?

One option is to follow R6RS:  Disallow all set!s to
any exported binding, even set! internal to the module.
But that might break more code than desired.  Another
options is to prohibit module-external set! in the
post-macro-expansion code.  That should be easy to
implement, and good enough.  At some point we might
consider deprecating or prohibiting this extension to R6RS.

>> (3) Currently, an integer literal has type gnu.math.IntNum,
>> i.e. a "bignum".  Adding an int and an integer literal is
>> usually done using IntNum arithmetic.  (The exception is
>> if the "expected type" is int, then the compiler knows it
>> can use int arithmetic and get the same result, thanks to
>> the properties of modular arithmetic.)
>>
>> The plan is when an integer literal is in the 'int' range,
>> and is one of the operands to addition (or similar operation),
>> and the other operand has type int, then we cast the literal
>> to type int, and do the addition as int addition.  The
>> inferred type of the addition becomes int.  For example:
>>
>>    (define (foo (x :: int))
>>       (let ((x10 (* x 10)))
>>           ... x10 ...))
>>
>> Currently, the type inferred for x10 is integer (i.e. gnu.math.IntNum),
>> and the multiplication yields an IntNum result.  The plan
>> is that the type of x10 will be inferred to be int, and
>> the multiplication will be done by an inline imul instruction.
>
> This sounds rather incompatible with standard Scheme.  E.g.
> (do ((i 0 (+ i 1)))
>      ((<  i 0)))
> usually loops (until memory is exhausted) but with modular arithmetic
> the loop terminates after wrapping around.

I think you misunderstand the plan.  The literal 0 by-itself would
still have type integer (bignum).  I'm talking about when adding a
literal integer with an expression that has already been inferred to
32-bit int.

I.e. the type-inferencing rules are currently:

(+ integer integer) --> integer
(+ int integer) --> integer
(+ integer int) --> integer
(+ int int) --> int

The change would be to add two special cases:

(+ int integer-literal) --> int
(+ integer-literal int) --> int

> It would be nice if there where a (rnrs) module where + overflows to
> bignums and a (kawa) module where modular arithmetic is the default.

Modular arithmetic is the default when the operands are modular.
That would only change in one detail: If one operand to a binary
operator is modular, and the other is an untyped integer literal,
then we'd treat the integer as modular rather then bignum.

Now a separate issue:  Right now Kawa can't infer the types
when there are two values for a variable.  Your example
above has two values '0' and '(+ i 1)'.

I'm planning to enhance the type-inferncing to handle
multiple values for a variable, by calculating some
kind of union type.

A complication with '0' and '(+ i 1)' is that the latter
depends on 'i', so we still can't figure out the type of 'i'.
The plan is to special-case addition, subtraction, and
a few other operators so we'd take the union of '0' and '1',
followed by extra munging.  That would tell us that 'i' is
integer, but it doesn't tell us it is int.  To be determined
- this level of inferencing is probably a ways off.

Finally:
   (do ((i 0 (+ i 1)))
      ((>= i n) ...)
      ...)

If n has type int then we know i will never overflow the
bounds of int, so we can and should infer i to be int.
But that level of cleverness is also not coming anytime soon.

>> (4) I'm also considering adding some warnings.  ...

> Efficiency notes would be very useful.  I also would like a note when
> integer boxing

Yes, those would also be useful.  The compiler still does more
boxing than needed (for example there is no inlining of the
bitwise- operators yet, though that may be coming soon), so
such a warning may be a bit premature, until the compiler
gets a little bit more clever.

> or string conversions are needed.

What "string conversions" were you thinking about?

> Warnings about
> improper tail calls would also be nice.

I'm concerned about too many false positives.
Any ides for avoiding that?

> The changes seem to be for the better.  I hope, though, that Kawa
> doesn't get locked down too much so that it's still useful for
> interactive development.

Don't worry:  Kawa will still have eval, load, and a repl,
and type specifiers will always be optional.
-- 
	--Per Bothner
per@bothner.com   http://per.bothner.com/