First Class Representations

[Francois-Rene Rideau]

> I've been talking for some time about the article I was
> preparing on first class representations. I have not modifed
> it for a while so I thought I should stop putting things off
> and show you what I've done so far.
> 
> This should be of interest to both LLLers and HLLers. This
> subject is an (if not the) essential link between the two levels.
> Because high level object are _represented_ by low level objects.
> 
> If you have questions about it, I'll be pleased to answer them. Even
> if the question are of the form "What the hell does that mean !?"  :)
> 
> It doesn't talk about Tunes because it can exist outside of Tunes. But
> I had Tunes in mind when I wrote it.
> 
> You'll need a PostScript viewer or a DVI viewer to read it. A printer
> would also do of course. The URLs are :
> 
> http://www.cs.utoronto.ca/~premont/fcrep/fcrep.ps
> http://www.cs.utoronto.ca/~premont/fcrep/fcrep.dvi
> 
> Nice reading. The document has 10 pages by the way.
>
> I want feedback !
>
Late as always, here is some feedback:

* 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.

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

* 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'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:
 either "represented universe" and "representing universe",
 or "abstract universe" and "concrete universe",
 would be better, wouldn't they?

* on real computers, the set of states is finite,
 whereas on languages used, the set of objects is infinite;
 moreover, representations generally do not exhaust states
 on the destination universe either;
 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.

* Mathematically speaking, using the most common structure of quotients,
 the abstract state is (isomorphic to) the class of all
 possible representations 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 also breaks the fact that a representation be global morphism;
 it is only a *local* morphism (in the sense of Fraisse).

* 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.

* 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

* 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).
 
* To sum up, a Representation is a local morphism
 from the representing/concrete space to the represented/abstract space.

* 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.

* 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.

* 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.

* 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.

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...

== Fare' -- rideau@ens.fr -- Franc,ois-Rene' Rideau -- DDa(.ng-Vu~ Ba^n ==
Join the TUNES project for a computing system based on computing freedom !
                TUNES is a Useful, Not Expedient System
URL: "http://www.eleves.ens.fr:8080/home/rideau/Tunes/"