Re: what are keys and surrogates?

From: Marshall <>
Date: Wed, 9 Jan 2008 23:02:56 -0800 (PST)
Message-ID: <>

On Jan 9, 9:07 pm, David BL <> wrote:
> On Jan 10, 11:44 am, Marshall <> wrote:
> > On Jan 9, 5:26 pm, David BL <> wrote:
> > > > I'd just say, a la SML:
> > > > product(sum(5, 6), x)
> > > So is the name of a relation part of its value?
> > No. The "product" and "sum" above are what are usually called
> > "constructors." The above is a value. You can put it in a relation
> > if you want. (Probably I introduced the confusion by talking about
> > union types immediately after talking about RVAs.)
> Is "constructor" the same as what C. Date calls a "selector"?

Yes. Date calls it a selector, and the entire rest of the world calls it a constructor. :-)

> > > If "relational" encompasses too wide a spectrum then the word starts
> > > to become rather meaningless. It's not meant to have any bearing on
> > > how one solves problems - I'm not suggesting that RVAs are evil in any
> > > sense!
> > Okay. But let me be explicit: in my mind the "ideal" programming
> > language encompasses different "pure" computing models into
> > a single hybrid computing model. That model will necessarily
> > include relations, (because they are so awesome) and it will
> > also necessarily include other things, such as first class functions,
> > because they too are awesome.
> I completely agree.


An interesting note, by the way: functions are relations...

> > Well, my own thoughts in this area are evolving and may
> > sound pretty weird at this point. Roughly: there are two "kinds"
> > of values: relations and atoms. The type of a relation is
> > exclusively the set of its attribute names. Atoms don't have
> > types, however we may specify a set of atoms in such a
> > way as looks very much like what is usually called a type.
> > (Thus: we have the set of natural numbers, and we have
> > the set of integers, and N is a subset of Z. And we can
> > tell of an atom whether it belong to N, etc.) In addition
> > we have constraints, and the constraint language is
> > Turing complete (and hence not decidable.) We can
> > specify a constraint on a variable, in which case it is
> > a runtime construct, or we may specify a constraint
> > on immutable constructs, in which case they should
> > be checked at compile time. Under this scheme much
> > of the machinery usually associated with types gets
> > taken over by constraints.
> How do operators fit into that picture - given that a type is
> conventionally a set together with the operators available on that
> set?

The picture includes functions. Functions have in and out parameters. There are no methods.

(I also support var parameters and closures, but they don't qualify as true functions. I'm still not sure what limitations they should have. Clearly we don't want back doors to the constraint system via mutable relation values, to list just one of the many ways to screw up.)

I have no strong feelings about encapsulated ADTs; what Date calls ... uh. Shit. I can't remember what he calls them. I don't entirely see the reason for them. Performance I guess?

I don't see a big reason for a close tying of functions to types. CLOS seems like an interesting idea. Maybe it's a bit *too* configurable, though.

I think it would be neat if you could, for example, have declarations like

  +:(x:num, y:num -> z:num)
  +:(x:int, y:int -> z:int)

and have the system know from this that it can add any two numbers, but also that it can (efficiently) add two integers, and that when you add two integers you always get an integer.

> > This is just my own particular way of thinking; it doesn't
> > represent anything more than that.
> > > > > Would there be some concept of
> > > > > inheritance for relation types (by analogy to an OO implementation of
> > > > > an AST that uses a Node base class)?
> > > > I'm inclined to say NOOOOOOO!!!!!</vader>
> > > I wonder then how all the relevant constraints would be specified.
> > Given a Turing complete constraint language, any constraint
> > that can be computed can be expressed. I don't think you
> > can do any better than that. :-) Of course, this approach brings
> > its own issues ...
> Like needing Ctrl+C to abort the compiler!

Well, yeah, that's the danger. There are conservative ways to handle that sort of thing, though. The compiler can be smart enough to know when a constraint isn't within the bounds that it can prove it can decide. And it can have resource limits.

It's possible to consider some constraints as proof obligations. And the compiler can try to satisfy that obligation and if it can't do so within a fixed period of time, that can be an error. And there is also the possibility of the (sophisticated) programmer supplying the proof, as an adjunct to the source code.

The papers I've read suggest that the distinct majority of proof obligations can be met automatically.

Marshall Received on Thu Jan 10 2008 - 08:02:56 CET

Original text of this message