[Grace-core] some thoughts on structural types & pattern matching

[Andrew P. Black]

On 30 Aug 2011, at 5:53, James Noble wrote:

> Hi all
> 
> there's a good discussion going on between John, Kim & I on the blog:
> 
> http://gracelang.org/applications/2011/08/18/from-lancaster-to-portland/#comments
> 
> The issue is - I think - given we have structural types, how do they work with
> pattern matching. For example, in minigrace, the types structural types 
> of AST nodes for variables and constant definitions turn out to be the same*, 
> so pattern matching cannot distinguish between them.
> 

I would ask: are they really the same?  I would have expected, for example, that a variable would have a method to generate an assignment to that variable, whereas a constant would not.  So, if the type are the same, the programmer should stop and think: are these really two different implementation of the SAME type,a re are they different types, and if so, what, abstractly, is the difference?

This discussion further convinces me that typecase is a bad idea in an OO Language.

> 
> I've also been wondering about a  related issue - the rhetoric that "types do not affect
> the execution of a correct program" isn't true when pattern matching is involved:
> erasing types from patterns means they no longer match.   What should we do 
> about this?
> 
> One option is to think about the ontology of Grace - as in the diagram below:
> 
> 
> types (Cat, Set)				generic types (Set[Cat])
> 
> ----------------------------------------------------------------
> 
> classes (CatImplementation)    generic classes (LinkedHashSet[T])? 
> 
> methods						generic methods
> 
> objects   					(generic objects - only implicit parameterisation
> 							via formal arguments in surrounding scope**)
> 
> blocks    						(blocks  objects - only implicit parameterisation
> 							via formal arguments in surrounding scope**)
> 
> Types (above the line) could simply be annotations: they shouldn't
> affect runtime behaviour of correct programs.
> Runtime objects (below the line) obviously have to exist at runtime.
> All of these entities can either be generic, or not: although objects and 
> blocks can only be made generic by being nested inside a generic
> class or method. 
> 
> Where does that leave us?   Well one option would be that since "patterns"
> in pattern matching *do* affect they runtime behavior of correct programs,
> they shouldn't be types.  Presumably the would rather be (generic) classes.
> This at least parallels methods - the particular method that is invoked
> obviously depends on the receiver object (more or less on that object's class ---
> although in Gracemobjects from Object literals don't really have a class).
> 
> Another option is to say that, well, pattern matching is done on "patterns" -
> patterns would presumably be another element of the ontology, "below the line".
> Perhaps types could be a subclass of patterns, so that (reified) types could be
> used as patterns - but there could also be other kinds of patterns.   Since the
> types were "patterns" we'd claim they didn't break the rule about execution not
> depending on types. 
> 
> There is still the problem of ensuring matching can discriminate as finely as 
> programmers will expect, however, which leads us back to brands or nominal types.
> 
> Newspeak has an interesting twist on this: haitss patterns are based on messages, 
> (method requests)  rather than classes - a pattern checks whether an object implements
> a particular _message_ (method) and uses that message to destructure the object 
> being matched (Newspeak's full protocol is rather complex).   The key point here is
> that these methods seem to act more or less as brands - each class carefully needs
> to implement a different matching method - although the overall typing remains 
> structural. 

This is one of the reasons that I have been opposed to typecase.  You appeased me by saying that typecase would be defined in terms of message sends.
If that is the case, then I don't see how it can do anything that could not be done by message send.  Is it no longer the case that case is defined in terms of message-send?

Note, however, that once a program sends a reflexive message, all bets are off.  The result of the program can depend on the presence or value of any annotation, or on the name of any variable, or on many other things that change the structure of a program.  That's why it's so important to distinguish reflexive and non-reflexive messages.  

Being able to trap Message not understood errors is one kind of reflection.  Being able to ask whether or not a message will be understood is another.  Typecase does the latter, does it not?

	Andrew'