Re: [Sml-implementers] extensions to SML

[Daniel C. W. <dc...@ag...>]

At 09:49 AM 9/18/2001 +0200, Andreas Rossberg wrote:
>"Daniel C. Wang" wrote:
>> 
>> Another semantics would be for (op =) to be a partial function i.e.
>>   'a * 'a -> bool option  (or it could raise an exception of some sort)
>
>That is problematic. Consider
>
>        (2, ....fn x => x....) = (3, ....fn x => x....)
>
>where "...." is meant to indicate some deeply nested data structure.
>Now, for the semantics of equality to be well-defined short-cutting the
>comparison after seeing 2<>3 is no longer possible - you always have to
>traverse the whole structure. That implies a serious performance
>penalty. Same for using options.
>
> 

If you're "cleaver" you can avoid this particular problem, and introduce
others. Every value can have an extra "poison" bit, which you set at 
allocation time. If you know the "eqness" of an object at 
compile time because the type is known, then you can set the poison bit 
appropriately. If the eqness of a type is unknown because it is polymorphic  
(i.e. a list) then you set the bit at runtime by inspecting the bit of its 
argument or the type at runtime if you're passing type info at runtime. 
Since, every value now has a "poison" bit. You can first check the poison 
bit and return NONE or else run the standard short-circuiting poly-eq test. 

Your poly-eq function is probably examining some type tags at runtime, so you 
can piggy back the extra bit on your existing tags. If you're doing 
something fancy like dictionary passing to implement poly-eq changing 
your system to implement this trick is pretty easy too. If you're doing 
whole program compilation you statically know when you should just return 
NONE. 

Anyway, you can easily implement this in a way that returns NONE when 
comparing two non-equality types without having to examine the entire 
object. It's just like the partial unboxing tricks used in FLINT and other 
compilers.

I'm not so concerned about the implementation details about this. I think, 
the bigger problem is that it has ugly semantics, from a user point of view. 
This proposal just pushes problems at the type-level into the 
runtime/compile time level.