Re: What databases have taught me

From: Dmitry A. Kazakov <mailbox_at_dmitry-kazakov.de>
Date: Sat, 1 Jul 2006 00:09:51 +0200
Message-ID: <1murwj51ijlvm$.7rmfuriszb04.dlg@40tude.net>

On 30 Jun 2006 12:49:36 -0700, Marshall wrote:

> Dmitry A. Kazakov wrote:

>> Types aren't sets of values.

>
> Would Russell agree, I wonder?

Do you mean Russel-Whitehead type theory?

>> They are structures like: ring, field etc.

>
> Field is a type. Natural number is also a type, and + is not required
> for that type, but it is certainly useful. So I have to disagree that
> this is the only way to look at it.

N is a type, but in a different meaning (it still has some operations defined). But this type is different from one of (N, +). (N, *) is yet another type. (N, +, *) is a fourth type. You've god the idea, I think.

>>>> type <-> function is a relation. "Member" function is rubbish. BTW, when I
>>>> talk about multiple dispatch I do include results of functions. So, say
>>>>
>>>> + : A x B -> C
>>>>
>>>> is triple dispatching. It is an operation of types A, B, C.
>>>
>>> Oh my goodness, that raises a whole host of problems! You
>>> can't effectively dispatch on the right side of the arrow, because
>>> that's the type of the result expression.
>>>
>>> For example, if you define both
>>> +: int, int -> int
>>> +: int, int -> float
>>>
>>> then what is the type of "1+1"? It could be either int or float.
>>
>> There are so many misconceptions in one single phrase, that I don't know
>> where to start from.
>>
>> 1. Why parsing need to be bottom-up?

>
> "bottom-up" is not the question; the question is context-free vs.
> context sensitive.

You should mean a grammar here. It is a different issue. You need not to resolve types during lexical analysis. It would be a very bad idea. Usually the compilers get some parsing tree and only then starts to play with types and names resolution. There is no need to know anything about types before that. [if you are interested I can give you samples parsing tree generation for Ada 95 and FCL]

>> 2. What is the type of 1?

>
> In many languages, and in my hypothetical example language, integer.

>> 3. The type of an expression (if any) is Expression.

>
> This is equivalent to saying that only untyped languages exist.

You might wish to have closures and lazy expressions. Note that you can have many types of expressions [as expressions I mean]. Further the type context might require something like an "expression resulting in the class numeric". Which means that a class of expressions is expected, So 1+1 won't dispatch in the result. It will be passed as an expression (closure) to the target and ultimately dispatch there. Everything stays strictly typed. [Lazy expressions might be very useful.]

> I reject that claim, and in fact I am relatively uninterested in
> languages that lack a static type system, although of course they exist.

Full agreement

>> 4. The type of a result of an expression is determined by the expression
>> and the context of.

>
> That's certainly a possibility, but not the only possibility, and in
> fact one that has been widely rejected by PLT as having many disadvantages.
>
> I also note that your item 4 contradicts your item 3.

It does not. Because it is typed. Consider:

f : int -> ?

then

f(1+1) is resolved to a composition of + : int x int -> int and f.

But when:

g : expr<int> -> ?

then

g(1+1) is resolved to g on the closure <int>(1+1).

>> 5. Of course you define both if int and float are in the same class. You
>> *must* define both.

>
> No, that is certainly not true. I don't know of any languages that do
> this, either.

Which is *bad*.

>> And also (assuming int was derived from float):

>
> I do not so assume.

Then +'s above are just two overloaded functions and it isn't dispatch anymore in any of parameters as well as the result. Overloading in the result is not a problem at all.

>>> You *don't* want to be in a situation where you can't assign
>>> a type to an expression; it introduces cascading ambiguity.
>>
>> See 3. As for the result of, in a typed language is *always* defined.
>> Because each object has *a* type.

>
> This doesn't say anything about whether your idea of
> dispatching on return type is feasible or not in a statically
> typed, context-free language, and in fact it isn't. It introduces
> ambiguity in the type of function invocation expressions.

It does not, because overloading isn't dispatch. For a dispatch it also cannot be ambiguous because per definition all slots of the dispatching table are required to be defined. So for any combination of types of two parameters and the result you *always* have a dispatch target. Everything you need is a trivial requirement that any object had a type. This has nothing to do with static resolution of names at compile time.

> Being able to uniquely assign types to all terms is one of the
> most important properties of statically typed languages.

Yes. And this requirement is not violated. All objects either become types, or it is a statically determinable error and thus the program is illegal.

> I also note the above confuses static concerns, specifically
> the type of an expression, with dynamic concerns, namely
> the runtime type of an object.

Not at all. It is solved by separation types of specific and polymorphic objects. The latter are classes. You can dispatch only on an instance of a class (=on a polymorphic object). Such object has exactly one type = the type of the class. Upon dispatch this object is converted into another object, which has a specific type. Also in any state an object always has exactly one type. It is bullet-proof.

>> As for your example, nothing can be said,
>> as long as it is unknown:
>>
>> 1. Whether int and float are related types.

>
> Doesn't matter. If int <: float, then my example is ambiguously typed.
> If int is distinct from float, then my example expression is
> ambiguously typed.

int <: float = they are related.

If they are, then + is defined on the class float. If they are not, then there are two overloaded +'s. In any case there is no types ambiguity.

In the latter case (of overloading) you might be unable to resolve the name +. That does not make it mistyped. BTW, you can overload functions in results. It not a problem at all. See Ada, which has it since 1983, and is one of the most strictly typed language, with the most carefully specified semantics.

>> 2. The function 1 [note, literals are parameterless functions 1:->? For
>> example it could be two overloaded 1's: 1:->int and 1:->float, but better
>> not to do such things]

>
> Why better not to do such things? Why is it okay to overload the return
> type of parametric functions, but "better not to" overload parameterless
> functions?

Because of possible name clashes, and because the semantics of integer and floating-point numbers is quite different. So 1 is misleading. Otherwise it is OK.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Received on Fri Jun 30 2006 - 17:09:51 CDT