This is the mail archive of the guile@sources.redhat.com mailing list for the Guile project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

After GOOPS integration: Computation with native types!


I was really impressed tonight by Keisuke's VM.  I think he's on the
right track and I think we should use his VM to replace the "normal"
evaluator in Guile fairly soon.  [This will have the side-effect of
making eval.c more readable, as somone probably already has pointed
out. :) ]

Together with the integration of GOOPS, this opens new perspectives
for Guile.

GOOPS is prepared for a fairly advanced type of optimization, the main
feature of which is to eliminate most type dispatches.

The method compiler in GOOPS has the advantage that it *knows* the
types of the method arguments.  The "observers" of Jost's environment
implementation, which Dirk is currently merging into Guile, allow us
to safely replace many generic function invocations with method
invocations, and we may even break closure borders and do some
inlining.

An example of the effect this has on method code is that most type
dispatches in GOOPS object slot accessors can be removed from the
method code.

Now, with Keisuke's VM, things start to get *really* exciting.  It
will be possible to install a method compiler which compiles to byte
codes.  And since we're fairly free to introduce new byte code
instructions, we can do the following:

Let FOO be a Guile primitive operating on two <integer>s and returning
an <integer>.  Assume that if FOO is given two <fixnum>s, it is
guaranteed to return a <fixnum> (example: a binary `-').

Further, assume that among the parameters to the method M are
(x <integer>) and (y <integer>) and that M invokes FOO on x and y in
its body:

  M = (method (... (x <integer>) ... (y <integer>) ...)
        ...
        (FOO x y)
        ...)

But the method compiler in GOOPS doesn't operate on the type specified
in the formal parameters to M.  Instead it operates lazily at the
first method invocation, which means that it knows the types of the
actual arguments.

In fact, each time a generic function is applied to a new unique
combination of types, the method compiler is invoked, and its result,
a "cmethod", is stored in a "method cache".  This cmethod is then
reused next time that particular type combination is encountered
again.

[Originally, I was worried that we would suffer from a combinatorial
explosion of cmethods and that GOOPS would spend too much time in the
compiler.  But experience with the current GOOPS (where a lot of this
administration in fact is performed in Scheme code) indicates that we
shouldn't worry too much.]

So, if M is invoked on two <fixnum>s, the method compiler will see:

  Mi = (method (... (x <fixnum>) ... (y <fixnum>) ...)
         ...
         (FOO x y)
         ...)

The information Mi given to the method compiler makes sure that the
concrete type of x and y is known throughout Mi.  While the computer
scientists are getting gray hairs while thinking out inference systems
which can deduce the concrete type, GOOPS is benefitting from its lazy
compilation.

This allows us to move the type information from the objects which x
and y are bound to to the "data flow channels" which x and y
represent.

So, the byte code generated for Mi above doesn't need to compute with
typed objects, but can operate on native integers!

Proposal:

Currently, type assertions, convertion into native form, and
convertion back to type tagged form is made *within* Guile primitives.

I propose that we instead give each Guile primitive a type signature,
and that argument checking and conversions are made outside of the
code of the primitive.

As an optimization, instances of commonly occurring type signatures
could be provided explicitly, while the rest could by implemented
using some kind of data-driven programming.

Splitting out type checking and conversion from the body of the code
leaves FOO free to operate on native types; Mi above is freed from
conversions; the dispatch in the generic function replaces type
checking, and if the generic function is being invoked from a context
where, again, the concrete types are known, even this dispatch may be
eliminated.

As a further gain, the Guile library will probably shrink.

Mikael

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]