Re: Is a function a relation?

On Jun 22, 8:44 pm, David BL <davi..._at_iinet.net.au> wrote:
> Since Keith popped up recently, I'm interesting in reopening the
> question of whether a function is a relation (I have a small point to
> add).
>
> I'm interpreting "is a" in the same way as D&D.  i.e. the question is
> equivalent to asking whether every function value is a relation value.
>
> D&D use the CIRCLE and ELLIPSE example to illustrate the idea of type
> inheritance as specialisation by constraint. CIRCLE is a subtype of
> ELLIPSE because every value of type CIRCLE is also a value of type
> ELLIPSE.
>
> Let E be a variable of type ELLIPSE that happens to hold a value of
> type CIRCLE. D&D mention that THE_R(E) is not permitted, and it is
> necessary to instead use THE_R(TREAT_DOWN_AS_CIRCLE(E)). Implicit in
> this idea is that when an ellipse value happens to also be a circle
> value, the interpretation of the ellipse as a circle is unambiguous.
>
> Consider the binary relation with the following graph
>
>     { (x,y) | y = x+1 }
>
> and the following two functions
>
>     f(x)  =  x+1
>     g(y)  =  y-1
>
> It seems to me that assuming D&D's interpretation of "is a", it cannot
> be said that a function is a relation because TREAT_DOWN_AS_FUNCTION
> is ambiguous when provided with a relation variable that holds the
> value f.

Note that downcasting is a partial function that may succeed or fail at runtime.

If we treat the attributes of a function uniformly, we lose the distinction
between input and output attributes. If we lose that distinction, then try to get it back, it may be the case that we cannot do so uniquely.

A particularly familiar and yet complex case is the "+" relation:

  +: a, b -> c

Every nonempty partition of the attributes specifies a function

   a, b -> c
   b, c -> a
   a, c -> b

We can go further and consider the whole thing a predicate:

   a, b, c ->? ()

Note how much this looks like functional dependencies.

It is my considered opinion that we ought to have these distinctions present in the type system, because they are ideal candidates for static analysis.

Marshall Received on Wed Jun 24 2009 - 05:11:45 CEST