A simple, powerful, efficient typesystem

[Eric W. Biederman]

   Dear Tunespeople,

   > I have been recently doing some thinking and reviewing and trying to
   > come to terms with how to implement a system with the effeciency of
   > C++ without the high perobject space cost, and inflexibility that C++
   > has.
   Good.


   > The basic typesystem has 3 parts.
   >
   > Types -- roughly a C++ class
   >
   > Interfaces -- an abstraction that states how an instance of a type may
   >               be implemented.
   >
   > Views -- A mapping between the functions of a type, (possibly also of
   >          data) and the expected layout of an interface.

A quick rephrase.  An interface in my terminology I meant like
something out of group or field theory.  Where you define what you can
do with a type but not what type type is.  I.e. it's operators and
perhaps some of their characteristics.

The View does the mapping between the functions that actually
manipulate types, and the interface's which are what we manipulate
them with (at least when we want genericity).

My enthusiasm for this is that in the worst case it can be implemented
with approxiamently the same efficiency as C++ only degrading
slightly. 

   I had similar ideas before, but I think made them
   simpler and more homogeneous,
   after having seen how typed lambda calculi did things.
   There would be just:

   Types -- an abstraction that exports constructors and destructors
	   (using the vocabulary from Glossary.html), that is,
	   how to synthetize and analyze objects of given type
	   out of/into simpler types.

   Functors -- higher-order functions that actually build types out of
	   simpler ones.

   This scheme doesn't priviledge any kind of "basic type" that a system
   should export, and systems would export whatever suits the hardware
   best as basic types (see the LLL subproject about that).
   Because there is no priviledged low-level type, programmers are encouraged
   to use types that suit their needs best, at whatever high-level
   they design it.
   If they're not satisfied with the way the system manages to implement
   high-level types, or if the system, not being automatized enough yet,
   couldn't manage to implement those high-level types,
   then the programmer will have to manually implement these,
   by writing a functor from the type to be implemented
   into types already implemented.
   And if he's not satisfied with the LL optimizations done by the compiler
   when it inlines the functors, then he should enhance the compiler optimizer,
   and/or give it specific hints, instead of rewriting a specifically LL
   version of his objects.


   > The way this is implemented is instead of sticking type & subtype
   > information inside of every object, in the form of a virtual function
   > table pointer as in C++, the virtual function table pointer is put in
   > the object reference along with a pointer to the object.  From that
   > point on it's just like C++, in efficiency.
   Yes: we should separate the actual object from levels of view upon it,
   which allows us to strip the unneeded information when compiling and
   that information is known.


   > Views are the behide the scenes guys that make all of this work.  A
   > view really is a virtual function table.
   Well, that's what it could be *compiled to* in many cases.
   But I prefer a more generic and reflective definition,
   by having views as association between alpha-converted
   names/symbols/identifiers from the source, and objects in
   the reflective system.
   When compiling, any object statically known may be inlined;
   if no object needed requires reflectivity (e.g. a view itself),
   then the objects not statically known can be implemented with
   virtual tables. If there is unicity of view per object,
   then the compiler can build the view into the object, instead
   of having separate pointers.
      My point is that the language definition should be the most
   generic and expressive that is possible, and that it is up to the
   compiler to detect (perhaps with the programmers' helps and hints)
   that the full expressivity of the language is not used,
   so it can use more efficient implementation tricks.
   It should even be possible for the programmer to ask the compiler
   to detect non-compliance to such restrictions of expressivity.
   But the default for the system should be to allow maximal expressivity.

I have no limit that I know of to date in this scheme. 

   > But it is user configurable
   > and mappable to different functions, so you no longer have to have an
   > inheritence tree to deal with types & subtypes (As represented by
   > interfaces).  In fact all of the C++ nonsense about virtual functions
   > versus nonvirtual functions can be pretty much forgotten.
      See in the Tunes glossary what I said about inheritance
   being a very restricted case of using functors implicitly.
   Having explicit functors,
   and perhaps explicit rules for implicitly using them,
   seems a much more reasonable way to do things.

Later when I don't need to be at school in 5 minutes :)

   > The only penalty for this method of organization is that object
   > pointers are twice as big (unless you seperate views from objects ?)
   I'd definitely say separate views from objects. A same object can
   be viewed in several ways, and a same set of abstractions should be
   used to manipulate several objects.

OOPS ( I meant seperate views from object pointers!!!!!)

The implementation in g++ has them as second class citizens hiding
behind the scenes and doing all of the dirty work.  They are bound to
the reference of to an object.  Whether that binding should be relaxed
was my question.  Sorry.

   > and when a view is generated from another view essentially a whole new
   > view must be generated on the fly, so they are no longer totally
   > static.  These seem to be reasonable tradeoffs for a language that is
   > destined to as a very hll, with who knows what not going on behind the
   > scenes.
   If we dissociate views from objects, there is no more need to
   generate a new view f`or every new object, which is all the problem
   in the C++ nonsense.
   To me, objects exist because they are being viewed;
   views do not appear because some objects pop up from the void.

What I meant was in a situation where all you know about an object is
that it conforms to interface y,  interface y happens to be compatible
with interface z with appropriate mappings.  z & y grew up in
different neighborhoods.  Then to view the object as a z you need to
create a new view, from the view of it as a y.   This is not the same
as in C++.


   > It probably should be looked at to see which OO languages implement
   > this distinction of objects & interfaces.
   Well, I think that the *ML module systems are precisely about that:
   interfaces are attached to modules,
   that define types, functors, and functions;
   new objects/functions are arbitrarily built from these,
   with no personal interface attached to objects.
   However, this was designed specifically to make interface something
   higher-level and heterogeneous to objects, which "most of the time"
   is a good idea, but specifically precludes reflectivity.
   [Which nonetheless is already better and cleaner that C++ crap,
   which is not reflective either].
   A completely different (and mostly independent)
   extension to ML is existential types (different from universal ones);
   but unhappily, while many laboratories are successfully testing those,
   they are not available to the public yet.

   > This has been implemented in g++ so it's not my own idea.  Though
   > you'll have to dig to find it.  I haven't read the docs on it in a
   > very, very long time.
   I advise the reading of the articles about camlsl module system
   (much cleaner than the SML stuff) and about the OO extensions to caml.

As soon as I can.

   > I real neat potential for this reorganization of OO implementation is
   > that generics/templates could be rolled into invokers of virtual
   > functions upon views, while also being able to be specialized for
   > added efficiency.
   Definitely.

   > Anyhow so version of these concepts would work nicely I think for
   > tunes.
   I think


   NB: I'm currently finishing my "WhyNewOS" paper,
   that some people at school want me to submit to them,
   so no one's taking care of the HLL currently -- Patrick ? Eric ?
   The LLL now has its own tunes-lll list, similar to the tunes one...

I'll review as I have been and make sure all of the pieces fit
together (I can't help it) but I can't take over sorry.

Eric