transcendence

[last year's man]

question 1g of the fall 89 final asks about "the problem of
transcendence." what is it?

[Gordon V. Cormack]

In article <Pine.ULT.3.95q.98042...@mobius04.math.uwaterloo.ca>,

last year's man <jmat...@mobius04.math.uwaterloo.ca> wrote:
>question 1g of the fall 89 final asks about "the problem of
>transcendence." what is it?
>

I don't believe I used that word this term. But I covered the general
concept.

Here are some notes I wrote a few years ago.

--

Transcendence

Transcendence is the ability to define a function that operates on
the hidden representation of two objects. For example,

f(a,b)

In a pure object-oriented language, this is impossible. The only
option is to place the function inside either a or b, and to have
the other export facilities to allow the manipulation of its internal
representation. A call to f would then be something like

a.f(b)

where b would have to export its representation so that a could
access it.

C++ and Eiffel provide a selective mechanism to make the internal
representation of a class available outside. In C++, one class
may name another class as a "friend". In Eiffel, and export
statement may specify which hidden functions are to be visible to
to other classes. Thus if a's class and b's class both contained
the declaration "friend f" it would be possible to define

f(a,b)

In abstract data type sytems, f can be defined provided a and
b are the same type. An abstract data type is like a class except
that functions are common to all instances of the type rather than
being replicated with each object. This means that f can be defined
inside the ADT, an can access the internals of any variables of the
ADT.

Packages (as in Ada) are more general still. It is possible to
define several abstract data types inside the same module. Any function
defined within the module can acess instances of any types defined
within the module. That is,

f(a,b)

could be defined provided a's type, b's type, and f were all defined
in the same module. This imposes some structure on the program,
but the structure is more flexible than the two approaches above.

A problem arises with generics. The function

f(a,b)

cannot reference the hidden representation of both a and b if a's
type and b's type come from different instances of the same generic
package. Here, the only solution is to export the necessary low-level
functions from the package, and to have f import those operations
as generic parameters.

This approach exposes the abstraction to possible tampering and
exposes f to possible forgery. It is possible to use Ada's type
system to prevent this. It is illegal to define a procedure
that takes an "in out" parameter of a limited private type, except
inside the package defining the type. Therefore, we can authenticate
any call to a routine by requiring such a procedure to be passed.

ML's core type system is the most general in this regard. Abstypes
can be parameterized apart from their operations, and the operations
are polymorphic across all instances of the abstypes. Therefore,
functions like f can be written within the body of the abstype.
for example:

abstype 'a fred = FRED of a
with
fun plus f (FRED x, FRED y) =
FRED(f(x,y))
end;

Yields:

type 'a fred
val plus = fn : ('a * 'b -> 'c) -> 'a fred * 'b fred -> 'c fred

Unfortunately the functor/structure system in ML suffers from the
same transcendence problems as Ada's generics.
--
Gordon V. Cormack CS Dept, University of Waterloo, Canada N2L 3G1
gvco...@uwaterloo.ca http://cormack.uwaterloo.ca/cormack