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

[James Noble]

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.

(background on Grace's matching is here:
http://gracelang.org/applications/2011/02/10/the-case-for-case/)

What should we do about this?   -- Some options are mentioned in the blog post,
most of them involve reintroducing nominal types one way or the other...


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. 

James

----

* for what it's worth, the minigrace type debugger says:

<Object_38> is a subtype of: Dynamic VarDefAstNode <Object_38> <Object_65>
<Object_65> is a subtype of: Dynamic VarDefAstNode <Object_38> <Object_65>

where Object_38 is varnode, Object_65 is defnode - in minigrace currently the
AST is declared via object literals, not types, thus the Object_ type names.
So we have: 

((Object_38 <: Object_65) & (Object_65 <: Object_38)) ==> (Object_38 = Object_65)

given a definition of VarDefAstNode like this:

type VarDefAstNode = {
       kind -> String
       name -> String
       value -> Object
       dtype -> Object
       register -> Object
       line -> Number
       pretty(depth : Dynamic) -> Dynamic 
}

** The point about objects & blocks is there is no syntax for declaring generic
object literals or blocks explicitly - but objects or blocks nested inside a
generic method or class would then effectively be generic:

class Example[T] {
 def holder = object { def field : T }   // object type  { field -> T }
 def block = { return holder.field }     // return type of block is the same T 
}