# Re: What databases have taught me

From: Dmitry A. Kazakov <mailbox_at_dmitry-kazakov.de>
Date: Sat, 1 Jul 2006 11:52:19 +0200
Message-ID: <1o8wy08pti6fv.5vrqqrffeogi\$.dlg_at_40tude.net>

> Dmitry A. Kazakov wrote:

```>> 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?
```

>
> Yes.

There was a time I thought they were unrelated. But now it seems to me that there is a deep connection between their types theory and types in programming languages.

```>>>> 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.
```

>
> Okay. So if I have a type N, with a minimal set of operators (just "successor")
> and another module extends N with a + function, and a different module
> extends N with a * function, then we have three different types of N, is
> that correct?

Right.

> Have we broken interoperability between N values coming
> from the three modules now? If not, in what sense are they different
> types?

It depends on how you add operations. If you do it upon inheritance, then interoperability will not be broken, though values will be different.

Let you have T = (N, +). Then you say S is a subtype of T. That precisely means that S inherits operations of T. Now, because values of S (from N') aren't values of T (from N), inheritance of the operation + means that there is another + defined on N' as a composition

S.+ = T.+ o from_N_to_N' (assuming covariance in the result)

Function from_N_to_N' converts arguments from N to N'. This gives you interoperability while keeping things strongly typed. Needless to say that from N to N' does nothing as long as values representations are same.

```>>>> 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* brought up parsing, not me. Or do you think that grammars and
> parsing are unrelated?!

It depends on what you parse. If you want to reserve the word "parsing" for formal grammars, then OK. Replace "parsing" above with "matching" or "analysis" or "resolution." Let's not argue about wording.

> In any event, the issue you are raising is
> one of context sensitivity, which, while occasionally practiced in
> languages such as ADA and Perl, has been widely repudiated as
```--