Re: type conversion discussion - Mailing list pgsql-hackers

I wrote:

> If I'm not mistaken then what I'm saying is that overloaded functions
> must form a lattice [...]

Indeed, I was. This attacks the problem from a different side, namely not
allowing setups that are ambiguous in the first place.

In detail:

If T1 and T2 are datatypes then T1 < T2 iff T1 is allowed to be implicitly
converted to T2, according to the promotion scheme du jour. If neither T1
promotes to T2 nor vice versa then T1 and T2 are not comparable.

Let A and B be functions with argument types (a1, a2, ... an) and (b1, b2,
... bn) respectively. Then we say that A < B iff ai < bi for all i=1..n.
If neither A < B nor B > A then A and B are not comparable. (That would
include such cases as foo(int2, float8) and foo(int8, float4).)

Define a partition on the set of all functions. Two functions F(f1, f2,
... fm) and G(g1, g2, ... gn) are in the same equivalence class iff "F" =
"G" (same name), m = n, and fi and gi are comparable for all i = 1..m. Now
I propose that you always ensure (preferably at function creation time)
that each equivalence class is a lattice under the partial order described
in the previous paragraph.

This helps because... Given a function call Q that you want to resolve you
first identify its equivalence class. Then there are three possibilities:

1) Q is not comparable to any other function in the equivalence class.
That means that the provided set of functions is incomplete. Proof: Assume
there was a function P which could handle call Q. Then, since you can only
cast "up", the arguments of P must at each position be >= those of Q. But
then P > Q.

2) Q is greater than any element in the equivalence class. This also means
that the set of provided function is unable to handle Q.

3) There exists at least one function P in the equivalence class such that
Q <= P. Consider the set A of all functions in the equivalence class that
are >= Q. Since the class is a lattice, A has a (unique) greatest lower
bound. That's the function you call.

Raise your hand if you are lost...

An example, say you define foo(int2, float8) and now want to add foo(int8,
float4), then the system would reject that because of potential ambiguity
and require adding foo(int8, float8) and foo(int2, float4) before creating
foo(int8, float4); or you would perhaps realize what you are doing and
instead just provide foo(int8, float8), or whatever you really wanted in
the first place.

(Actually, the requirement that you add foo(int8, float8) is useless,
since there is no down-casting and we don't use the least upper bound
property of lattices, so probably in practice one could settle for a
"half-lattice" requirement.)


Now I realize that this a pretty deep proposal, but at least it's a
solidly founded one (I think), it prevents the programmer-user from doing
unwise things, and it avoids any unpredictable "metrics".


-- 
Peter Eisentraut                  Sernanders väg 10:115
peter_e@gmx.net                   75262 Uppsala
http://yi.org/peter-e/            Sweden