Re: relations aren't types?

John Jacob <jingleheimerschmitt_at_hotmail.com> schrieb:
> Would I be right in saying that C++ templates are examples of
> polymorphic types?

I think so in principle, though I've heard that C++ templates are a actually turing-complete language on their own.

> Scalar types are not exactly records. A scalar type may have multiple
> possible representations.

This is where I think we're talking at cross purposes. A type doesn't have a "representation", at least as far as type theory is concerned -- it describes a set of values (sometimes in terms of other sets). How it's represented depends on the compiler, though you might give the compiler hints.

So you give an example of a date type which has a record representation and a string representation -- but "the set of records like this" and "the set of strings like that" are DIFFERENT TYPES, and obviously the same operations won't work on them since the same operations don't work on strings and records.

But here's where we get into abstract datatypes -- if a type gives you no interface to it's values other than functions it exports, THEN you might be able to use different "concrete types" in place of that abstract type and the code is the same.

But this "abstractness" is a property of the interface. If I let you use my dates as records, then they're not abstract, but if I don't, then they are. That doesn't depend on the type of the values themselves -- they might still be records even if I don't let you use them as such.

> I read the definition, and I have to say it was beyond me. I thought
> I understood it until it said that list was an algebraic type. If
> tuple is an algebraic type because it defines a set of values by
> combining values of other types, then how is list an algebraic type?

Here's how we could define list using only algebraic type operators: List a = Nil | Cons a (List a)

In english, a list is either nil or a cons of a value (of the appropriate type) and another list (the tail). This is better called a singly-linked list, which is what some circles mean when they say just "list".

> I agree that if a given construct can be implemented as a short-hand
> for some more primitive construct then it should, but I'm not
> convinced that the type system given in TTM can be reduced.

I'm convinced by experience with, i.e. Haskell which certainly seems to be at the cutting edge of usable type systems. I haven't read TTM (yet) though.

> I think we are going to have to clarify abstract and concrete types.
> I'm pretty sure I know what you mean, but I would like to be certain.
> An abstract type is a record or class, while a concrete type is a
> system-provided construct like list or array. Right?

I have to admit I don't have a really good definition so I'll defer to foldoc:
http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=abstract+datatype

The main point I want to make in the context of this debate is that, while abstract datatypes seem to fit your use of "scalar", the "abstractness" is not a property of the type so much as the interface. But then maybe the interface is part of the type, so I could be wrong.

> We want a language that allows us to write relational expressions as
> easily as possible... We also want to be able to define relation
> variables as easily as possible...

Well, I think this doesn't imply syntax but just appropriate builtin constructors: i.e.
type my_table = Relation RTuple {name: String, number: Int} [Constraint ...]

While a bit of syntactic sugar around that would be nice, I don't think it's crucial -- and the point is that you *could* have defined all these types yourself without relying on builtin syntax for relations, if efficiency weren't important.

And relational expressions should be just functions: (join foo bar) etc.

I'm a big fan of languages like lisp where EVERYTHING is either a macro or a function expression, where there's no statements or blocks or anything, so that's my bias. Received on Mon Jan 12 2004 - 00:18:52 CET