A simple, powerful, efficient typesystem

[Francois-Rene Rideau]

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.

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.

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

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

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

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


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


--    ,                                         ,           _ v    ~  ^  --
-- Fare -- rideau@clipper.ens.fr -- Francois-Rene Rideau -- +)ang-Vu Ban --
--                                      '                   / .          --
Join the TUNES project for a computing system based on computing freedom !
                 TUNES is a Useful, Not Expedient System
WWW page at URL: "http://www.eleves.ens.fr:8080/home/rideau/Tunes/"