Re: Modelling Disjoint Subtypes

From: Marshall <>
Date: 25 Mar 2007 13:55:01 -0700
Message-ID: <>

On Mar 25, 11:53 am, "David Cressey" <> wrote:
> "Marshall" <> wrote in message
> > On Mar 25, 3:26 am, Joe Thurbon <> wrote:
> > > Marshall wrote:
> > > > Having declared to the system that the type of S1.t is
> > > > a unit type (meaning the type has exactly one value)
> > > > the system is free not to store anything for the t column.
> > > Hi Marshall,
> > > To declare the type of the column, you'll need some storage. That is, I
> > > think what your suggesting moves some of the space required 'out of the
> > > column values' and 'into the column definition'. If reckon that to store
> > > one of N types, you'll need at least log2(N) bits.
> > Yeah, that's a fair point. The column-type storage costs are
> > O(1), vs. O(count(R)), but it's still some storage.
> > > > This is possible because the number of bits needed to
> > > > represent a value of a given type is the log2 of the number
> > > > of possible values. Since T1 has 1 value, the number
> > > > of bits needed is log2(1) = 0.
> > > But there are now N extra types, and you'll need to store them
> somewhere.
> > As an aside, there exists systems in which the storage cost
> > *at runtime* for type information is zero, because the types
> > exist only at compile time, and are completely removed
> > after.
> If you are saying what I think you are saying, then I disagree.
> For example, let's I have
> float x, a, b;
> x= a + b
> If I look at the variables x, a, and b at runtime, the type is gone. But if
> I look at the code generated by the compiler, I'm going to find that the
> plus sign is represented by a floating point addition operation. So, to the
> extent that operator indicates type of operand, the information is still
> there at runtime, although buried in the code.
> This could be important if you were writing a decompiler.

It seems pretty clear we agree on what is actually happening. However there may be some disagreement on what terminology best describes that.

It hinges on your phrase: "to the extent that the operator indicates the type ..." The example you picked is one where the operators are actually supported in the CPU itself. This is a fairly unusual case. The "extent" may not be all that much in the usual case.

Since numbers are on my mind lately, let's consider rationals and integers. Suppose we have some rational numbers x and y. Further suppose we do some thing if they are integers and something else otherwise.

  if (isInt(x) and isInt(y) {
    // consider the code here
  } else { ... }

Now, inside the first pair of braces, we know *statically* that the denominator of both x and y is 1. So if we multiply x and y, the compiler, which ordinarily would be doing two multiplies (x.numerator * y.numerator, x.denominator * y.denominator) may well throw the second multiply away, since its result is a constant 1. So if you looked at the generated code, you'd see only one multiply and possibly falsely conclude that x and y are integer.

Or consider an example with float representations of Fahrenheit and Celsius as two different types. If the types are erased, and we want to compare two temperatures to see which one is higher, in both cases they will be identical unadorned floats; the distinction between F and C is gone.

Marshall Received on Sun Mar 25 2007 - 22:55:01 CEST

Original text of this message