[Grace-core] Match and generics

[Andrew P. Black]

On 10 Jun 2011, at 01:35 , James Noble wrote:

> Hi Kim 
> 
>> We're starting to think about implementing match,
> 
> good!
> 
>> so I wanted to get the syntax correct and think through some of the decisions.  It made sense to try it out with the Option types, as that is likely to be the most likely use of match, as we avoid the use of null pointers.  Of course Option uses type parameters (the type parameter indicates the type of the value if it is different from the object None), so that has a few complicating factors..
> 
> yep.
> 
>> Writing this out raised a number of questions about the design, embedded as comments below.  Please let me know what you think.
>> 
>> type Option<T> comprises Some<T>, None<T> {
>>  isNone: -> Boolean
>>  getOrElse: (T) -> T // argument is default value to return if receiver is None, 
>>                                    // otherwise returns value in the option (see code below)
>> }

Wouldn't it also be useful to have a method get -> T which fails if the Option is not a Some[T].

We have been carefully reserving square brackets for parameters, so I suggest that we start using them! 
> 
> seems OK - but that type syntax looks a little odd 
> isNone -> Boolean
> getOrElse(T) -> T  

It's OK, we are succeeding in converting Kim to Smalltalk syntax!

> should option be abstract?

Are not all types "abstract"?

> 
>> // The result of this declaration indicates that Some and None are the 
>> // only classes that can implement Option<T>.  I don't know whether this
>> // should imply that Option<T> has no subtypes.  Otherwise we might
>> // accidentally define an type U that happens to extend Option<T> 
>> // and some classes that implement U.  
> 
> yep.  
> this gets more tricky with structural typing - any type defining
> isNone & getOrElse is a subtype - right?

In the example that I used from the Strings library (about which I don't recall getting the feedback), I used comprises with Objects (not types).  In this case it's unambiguous what it means: that object, not any object extending it.

My suggestion is that comprises means that the type is NOT structural, but that but must be implemented by one of the listed things.   If the thing is another type, then any implementation of that type will do.  It it's an object, then only that object will do.  If it's a class, then any instance of that class.

	type x comprises class y 

would then mean that y is the ONLY valid implementation of x; no other class will be allowed.  I have trouble seeing why one would want to restrict the future in these ways, but sometimes, doubtless, it will be desirable.

	type x comprises class y 

is thus a bit like final in Java, but better.  It doesn't say "you are not permitted to inherit form this class", it says, go and inherit form this class if you want, but the result will not be treated as an x.   I always finds it very frustrating that in Java, the fact that String is final means that not only can't I change what must be acceptable to the the built-in String interface (perhaps a reasonable restriction), but that I can't reuse the code in the String class in my own Strings (unreasonable, and frustrating).


>> // If we used nominal typing then it would be easier to block any 
>> // type extending Option.  Semantically we could model the type as a bounded 
>> // existential to block extensions (whether in a nominal or structural regime)

This is all true.  But doesn't the "comprises" already block extensions of Option?

>> object None<T> implements Option<T>{
>>  method isNone -> Boolean {return true}
>>  method getOrElse(default: T) -> T { return default }
>>  // we could make parameter to getOrElse have type of block instead, but not sure needed
>> }
> 
> making it a block is the Smalltalk/Self design, gives a little more power in that you don't then
> need another case / test to on that result: you just do it directly. 

Making it a block gives a /lot/ more flexibility: the getOrElse {statements} is now a control-structure that can /do/ something if the option is a none.  (Of course, once one has this power, case becomes superfluous.)
> 
> how is this structurally different from Option<T> ?
> 
>> // Note that this design gives a different None object for each type.
>> // Puzzle -- should this be written as a class since there are more than
>> // one??  It seems like it should because we will have an instance 
>> // variable representing the type T.  However, I'll leave it an object
>> // for now.
> 
> seems fine.
> 
>> // To avoid having different None's we'd have to make Option covariant 
>> // in T and let None implement Option<Nothing> where Nothing is the "bottom" 
>> // type.  That way it implements Option<T> for all T.
>> // I lean toward defining it as above so we don't have to worry about 
>> // covariance annotations, but could be convinced otherwise.
>> 
>> class Some<T> {x:T ->
>>   const val = x
>>   method isNone -> Boolean { return false}
>>   method extract -> T { return val }
>> }
> 
> so the point is having the "extract" method makes Some structurally different to None...
> 
>> Let y: Option<Number>.  Then we can use it with match as follows:
>> 
>> match(y) {
>>   case { Some<Number>(n) -> ...n... }
>>   case { None<Number> -> ... }
>> }
> 
> yep 
> 
>> // The spec doesn't indicate there should be curly braces around all the 
>> // case statements, but that seems necessary to delimit the scope of match,
>> // at least from a human reader's point of view.  
> 
> yep. also they are blocks / lambdas, which have to be in  { } 
> I remember a discussion about declarations, headers & blocks as the only
> binding constructs - so those *are* lambdas, just "matching lambdas", 
> 
>> The spec also uses "=>" 
>> // instead of "->", but I believe that was a typo.  (Though I wouldn't mind
>> // using "=>".)
> 
> does it? The latest version uses -> I think!
> anyway it should be consistent.
> 
>> // Note that a match based on the type of None<T>, which is Option<T>,
>> // does not seem as useful as the match based on the classes themselves.  
> 
> Static or dynamic type?
> And yes, I've thought this is difficult for structural matching.
> 
>> // While Some<T> has a type extending Option<T> 
>> // (it has the extra extract method), the test on classes seems 
>> // more appropriate.  In particular if you test for None's type before 
>> // Some's type then both kinds of objects will match None's type, really 
>> // confusing students.
> 
> yes indeed!
> 
>> Comments on the code and design?
> 
> I think we still need to consider if we don't want to "build in" more direct
> support for non-null types (even if only writing "Option<T>" as say "?T"  - prefix type operator
> and somehow supporting some kind of default desttructing. so one can write
> 
> var t : ?T := potentially null value
> 
> if (t.isNil) then { // handle nil
>   }  else { // handle t : T
>   }
> 

This is a really weak case (excuse pun) for case.  Without any new forms or type-comprises and the complexity that they imply, we can already write

	ifNil t 
		then {handle nil}
		else { n -> handle n as the non-nil value of T }

by simply declaring (at the "top level")

	method (or procedure) ifNil()then()else() 

and writing ifNil()ifNotNil() methods on the null value and on Object.

So if the goal is to start thinking about match, I think that a compelling example that simplifies otherwise complex code would be a good starting point.
		
	Andrew