[bitc-dev] BitC Records Figure fixed

[Swaroop Sridhar]

On Fri, 24 Dec 2004, Jonathan S. Shapiro wrote:

> On Thu, 2004-12-23 at 19:42 -0500, Swaroop Sridhar wrote:
> > > 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.
>
> I'm not sure who is being quoted here, and it would be very helpful to
> know. I begin to suspect that we have a more fundamental issue here that
> I have failed to understand.
>

Swaroop was being quoted here.

> First, I believe that structures *must* define field order and field
> type in order to be useful for the kinds of applications we are
> building. This does not correspond to the behavior of ML records, and I
> was explicitly *not* trying to duplicate the behavior of ML records.
> When this need is combined with the need for unboxing, a syntax for
> field reference quickly becomes desirable. This motivates field names so
> that we can write things like "a.b".
>
> At the highest level, my belief is that our model for named types should
> be based on name equivalence. In this sense, we should view a tuple as a
> degenerate, unnamed record. That is, given
>
> 	(defstruct s i:int c:char)
>
> then
>
> 	(let ((tup-instance (ref (5:int, #\a)))
> 	      (s-instance (s 6 #\b)))
> 	  (set! tup-instance s-instance))
>
> should be legal (though I am not convinced that I have all of the
> unboxing right). That is, when we write the tuple:
>
> 	(int, char)
>
> we are really writing
>
> 	(defstruct _ _:int _:char)
>

This was what I had in mind too.


> [Aside: should the elements of the defstruct be within parentheses? I
> think that perhaps the answer should be yes.]
>
> > It is not possible to have both of the following correctly:
> > i) Field ordering as a defining character of record type
> > ii) Record polymorphism with inferred record types
> >
> > Consider the following:
> >
> > function x ->  x.a + x.b
>
> Let's try to give more complete examples so that we can really look at
> them. I think you are concerned with something like:
>
> 	(defstruct s1  a:int  b:float c:int)
> 	(defstruct s2  a:int  m:float n:float c:char)
>
> Note that in these structures, the 'c' members disagree on both position
> and type. Now the question you pose is: "what is the type of 'x' in:"
>
> 	(defun f x (x.a + a.b))
>
> It would seem that there are two possibilities here:
>
> 1. By filtering against field names, the inference engine concludes that
> the type must be either s1 or s2, but it cannot uniquely resolve the
> type. Automatic type resolution therefore fails, and the user is
> required to specify the type explicitly, as in:
>
> 	(defun f x:s1 (x.a + a.b))
>
> 2. The inference engine concludes that the type must be either s1 or s2,
> and is not unique. We resolve this by polyinstantiating f.
>
> In abstract, I think that the preferred answer is probably (2), but I
> don't understand what implications this may have when 'f' is later used
> as a procedure parameter. What am I missing?
>
>

s2 is not a candidate for function f, as it does not have a field named
'b'.
However, consider

	(defstruct r1  a:int  b:float)
	(defstruct r2  b:float a:int)

Now both of them are valid candidates for the function f. I also agree
that your second choice is better than requiring explicit programmer
disambiguation.
In my other mail, I had suggested that we build the type graph like
   _={* a:_, b:_}
             |
             |
	     |
       ----------------------
       |                  |

  _={a:_, b:_}        _={b:_ , a:_}   // Combinations of
 					ordered fields
 					will be subtypes

Here, the type _={* a:_, b:_} can be thought of as the union-type of all
record-types containing all combinations of ordered fields. I do not know
which view (set / super-type) will be easier to deal with, with respect to
proving the soundness of our type-system.

 > -- > Jonathan S. Shapiro
<shap at eros-os.org> > > _______________________________________________
> bitc-dev mailing list
> bitc-dev at coyotos.org
> http://www.coyotos.org/mailman/listinfo/bitc-dev
>