First Class Representations

[Patrick Premont]

> Late as always, here is some feedback:

No problem, it takes time to read and comment this kind of thing and
we are all short of it.

> * I think that if we consider representations as a general concept,
>  not only for representing end-user objects with low-level bit streams,
>  then we got something very generic,
>  that is the very basis of computational reflection:
>  more abstract objects being represented by more concrete objects,
>  with arbitrary variations and subtleties about abstractness/concreteness.

Yes absolutely. I've specialized my description for low level cases to
show that it can go all the way down. The next version should be an
almost complete rewrite where I forget about that triple and see
representations as relations (or morphisms) between two sets. Calling
them abstract and concrete looks like a good idea. Although I'd pitch
in some comment that what makes a representation useful for computation
in our physical universe is that its concrete set is a set of states
of some system (or can be mapped to such a set through additional
representations).

> * the key terms that you introduce should be put in italics when they appear,
>  so the reader understands better.

Yes.

> * you could say that a representation is characterized by a triplet (sp?)
>  <T,S,F>: T(R)/S(R)/F(R) makes it heavier,
>  while keeping a consistent dependency order in presenting those concepts
>  will help the reader;
>  the bijection should be introduced after the source and destination sets.

I'm not sure about the order but I'll consider it. I think placing the
thing that relates the two sets in the middle has some intuitive
justification. But this might all disappear when representations are
just relations.

> * I'd call both sets Universes rather than Type and Set of States.
>  You'd have the "Univers de depart" and "Univers d'arrivee" of your mapping.
>  For many reasons, and particularly because I don't agree with the
>  direction of your mapping, I propose that another terminology be used:

What do you mean by direction ? You mean you'd like it to go in the opposite
direction ? I think I'll use relations anyway. Are you saying you'd
prefer the concrete universe to be the first argument of the relation ?
I tend to prefer the other way.

>  either "represented universe" and "representing universe",
>  or "abstract universe" and "concrete universe",
>  would be better, wouldn't they?

Yes for abstract and concrete. But the terms I used are still
appropriate in the sense that eventually representations will be
composed to form representations that reach from the type to represent
all the way down to the states of the machine. So the state space could
be the special case of the concrete space or universe.

> * on real computers, the set of states is finite,
>  whereas on languages used, the set of objects is infinite;

Yes. And that leads to the infamous "out of memory" problem.

>  moreover, representations generally do not exhaust states
>  on the destination universe either;

How is that ? I would think the opposite, if something is represented
on a system then for each of its states you can determine what is
represented (perhaps only ambiguously but it never represents
nothing). But maybe that's what you want, to have states that say
that nothing is represented. I'm not sure if that is a good idea. I'd
have to think about it. What are your views on that ?

>  hence a total bijection might not be a good idea;
>  a partial function from the low-level universe to the high-level universe
>  might be more fit.
>  Or a relation between those universes,
>  in the case of "inexact" representations.

You go from low to high... hmm. I understand you comment here but you
should address the assumption above.

> * Mathematically speaking, using the most common structure of quotients,
>  the abstract state is (isomorphic to) the class of all
>  possible representations for an object.

I struggling to understand here. Quotients used to confuse me and now
I'm afraid I forgot what they are (you're talking about the things
where we say that a morphism divides another ? I may not be making
sense at all, just say so). I could look them up but I'm afraid, even
then, I would not see the isomorphism you refer to. Also what do you
mean by abstract state? Your abstract universe ? And the class of all
possible representations for an object ? I've defined representations
for a type but not for an object.

> * Well, in the particular case that we're interested in,
>  the representation needs not be surjective,
>  with the most annoying problem being the lack of sufficient resources
>  to represent some state.

This comment must assume that the functions go from low to high level...

> * This also breaks the fact that a representation be global morphism;
>  it is only a *local* morphism (in the sense of Fraisse).

Oops, never heard of global or local morphisms. Can it be defined quickly ?
Is it worth learning ? On the intuitive level, I think the representations
I talked about are and should be global. Higher level representations may,
when composed with others to form a representation from type to machine
state, have only local effects but that is not a problem with the formalism.

> * Dynamic memory allocation alone is such that the state
>  of a dynamic environment can be represented in many
>  different ways, according to the pattern with which memory was allocated
>  during the construction of the state.

Yes. I don't think that's a problem with the formalism.

> * if the abstract object is defined in some kind of behavioral way
>  (operational semantics), then a large set of isomorphic representations may
>  exist, that only need to

oops, incomplete.

> * whether something is a representation for an object can be considered
>  as a set of equations. The set of solutions can be difficult
>  or impossible to compute, but we only need find one solution,
>  in an incremental way if possible (because of real-time constraints).

Not sure I understand you here. I'm not suggesting that we'll be able
to find representations automatically, in a computable manner, for
types defined by a set of equations. But you're not saying I suggested
that either.

> * To sum up, a Representation is a local morphism
>  from the representing/concrete space to the represented/abstract space.

this local thing...

> * Hence, the design process of refining representations
>  is an operation that, contrarily to
>  composition of simpler known objects into new more complex ones,
>  is *contravariant*, not covariant, with computation.

Oops, covariant, contravariant, what do these mean ? Does one ever know
enough mathematics ? :) Are these worth learning ?

> * Up to now, for reasons of easier computability,
>  people have priviledged covariant design,
>  and tried to artificially apply it to representation,
>  whereas we can only grossly approximate the inverse
>  of the contravariant function with covariant constructs.

Of course I don't understand this...

> * in the best cases, reflection could be used
>  to make the approximation implicit, and absorb it,
>  with some kind of exception being raised when the approximation fails.
>  Because the basic computable constructs are all covariant with themselves,
>  this is the Right Way to *implement* things;
>  but as long as only covariant interfaces can be specified,
>  there will be a mismatch between what people need to express,
>  and what they can express.

...and this.

> * Representation as concrete->abstract morphism makes many things easier.
>  But that's only a better starting point,
>  and doesn't solve trivially solve any of the problems you pose
>  after page 5.

Yes, exactly.

> Please tell me if there's anything wrong about what I said.
> If you've got anything to add, I'm interested:
> I think I'll use many of those ideas in my speech about reflection...

I'm sure I'll have more eventually but probably not before you
speech. We can discuss your points however.

Patrick