[bitc-dev] BitC Records Figure fixed

[Swaroop Sridhar]

I am sorry that the ASCII figure in my mail was scrambled in my previous 
note. It looked alright when I composed it. I am resending the whole 
letter with the figure redrawn, I hope it will not be scrambled again.

-----------------------------------------------------

I think the right way to think about records is as a graph of sub-types, 
rather than a set of types. (I know that this means multiple 
inheritance, please read till the end)

The definition of the type of a record in our language should be based 
on Field Types AND Field ordering AND Field names AND record-name.

Now, we can construct:
(The notation is struct_type_name={field_name:field_type,
                                      field_name:field_type, ... })


_={_:_}
|
|-------|
|       V
|     _={a:_}
|         |
|         |---------------
|         |----------    |
|         |---------     |
|                        |
|                        |
|                        |
|--------|               |
|        V               |
|         _={_:'b}       |
|                |       v
|                |------> _={a:int} |
|
|
|
|--------|
|        V
|      s={_:_}
|    Descendants of this branch should be explicitly declared
|    (as in single-inheritance)
|
|
|
|-------|
         V
     _={_:_, _:_}

This looks like multiple inheritance. But, this is a LIMITED kind of 
multiple inheritance, and my first thought is that it is OK because,

i) Named Records:
     Two records with cannot have the same name with different 
structures in the same scope.

ii) Unnamed Records:
     Two records whose structures are the same, are of the same type.

In other words, in the above graph, each attribute of a particular type 
  can be traced back to precisely ONE parent, and hence we will avoid 
the problems introduced by c++ style multiple inheritance.

Now, the advantage we get from this mechanism is that
the type of the function

fun x -> x.a

is _={a:'b} -> 'b, (NOT a set of all plausible record types)

and x could be {a:int}, {a:<whatever>}, {a:int, b:byte, c:unboxed record 
p}, s={a:int} , etc, but does not take in {_:int, b:_}.

And, type s = {a:int}; fun x:s -> x.a does not take any arbitrary {a:int}.

Also, different structures with same field names are OK (unlike ML), and 
the unification decision is based on the other parameters in determining 
the type. We cannot drop the field names from the type anyway, whether 
we like it or not.

I think this solves all of the problems we raised, but I am sure it will 
cause other problems. There should be some reason why this is not done 
in ML. I will speak to someone in the PL lab tomorrow, or read more 
about it to find out.


Thanks,
Swaroop.