--- Begin Message ---
|
Subject: |
Re: Applicable smobs & guile-vm |
|
Date: |
31 Aug 2000 05:47:59 +0200 |
Keisuke Nishida <address@hidden> writes:
> > But in order to achieve this, we need to support tail-recursion!
> > Otherwise, we'll not have Scheme semantics.
>
> I don't understand how Guile handles tail-recursion.
Essentially by a jump back to `loop:' in SCM_CEVAL.
In Guile, this makes closures properly tail-recursive. And everything
else which is properly tail-recursive makes use of this.
For example, `apply' is defined like this:
(set! apply (lambda (fun . args) (@apply fun (apply:nconc2last args))))
where @apply is a tail-recursive form.
(BTW, it is essential that the call/cc in your VM is tail-recursive.
Guile's call/cc is defined like this:
(define (call-with-current-continuation proc)
(@call-with-current-continuation proc))
where @call-with-current-continuation is a tail-recursive form which
simply "replaces itself" with proc.)
> Why do applicable smobs suffer from it?
Because invoking them involves a call to a C function. This call
leaves a return address on the stack---the stack grows. If the smob
then calls another function, the stack grows even more. Proper tail
calls doesn't cause the stack to grow. In Scheme, iterative processes
should be possible to write using tail calls. If the stack would
grow, the maximum stack size would set a limit to the number of
iterations.
This is no problem as long as the smob application never invokes user
closures, but it is a problem if it invokes programs of your VM,
because the user expects a closure compiled to byte code to be
properly tail-recursive.
> I think applicable objects are better, too. Are they already
> available?
Yes, but the current objects are based upon structs which are
generally awkward to handle. You could probably use them, but instead
of using your program mark function, you would have to produce an
object layout (prurprprur etc, where "p" means protected word).
If you do this, your programs should be instances of the class
<program> which itself should be a subclass of <operator-class>.
You use `set-object-procedure' on <program> to set the operator
procedure (the VM interpreter).
> Do they optimize tail-recursion?
If the operator procedure is a closure, and the closure is
tail-recursive, then the operator itself is tail-recursive.
If you, for example, embed the call to the byte-code interpreter in
macro and let the interpreter return the tail-call form, then you can
make the thing tail-recursive.
But, probably, Michael Livshin's suggestion is better: to have a
special type for tail-calls. In this case, we should implement a new
type of applicable GOOPS object for this.
> By the way, why do procedure-with-setters exist? Aren't procedures +
> setter properties sufficient?
1. Setter properties can be implemented efficient or inefficient. An
efficient implementation means adding a `setter' field to
closures. We don't want that because closures should be extrely
lightweight. We don't want an inefficient implementation at all.
2. It is natural to be able to set properties. We can't allow this
because the association of the setter to the procedure needs to be
permanent. This is because the compiler should be able to
eliminate the setter invocation construction entirely, leaving only
the actual mutating code. For example, the compiler should be able
to cut through the setter-construction, the GF invocation and the
method closure in order to convert the GOOPS expression
(set! (counter object) 0)
to
SCM_SLOT (object, 3) = 0;
> If Guile is supporting applicable smobs, I'll optimize them.
An applicable smob representation of gsubrs is much more attractive
than the current cclo implementation. For gsubrs, it *is* actually
nice that the applicable smobs are so lightweight.
Also, I just made a benchmark indicating that the interpreter is at
least as fast as before introducing applicable smobs. (I again
noticed the funny phenomenon that the interpreter seems to get faster
every time we extend the switch statements in SCM_CEVAL...)
Therefore, I suggest that we keep the applicable smobs at least until
we have lightweight applicable GOOPS objects (which might take some
time) and implement gsubrs using these. After introducing the new
GOOPS object representation we can still keep the smob API for a
while, just replacing the internals of smobs.
If you want to carry out the optimization I suggested (or a better one
which you have thought of) you should do it so that we can re-use the
code for the gsubrs.
For example, in my suggested optimization, you need to "compile" a
certain procedure arity into four different trampolines (including the
potential no-trampoline direct call cases).
If we represent gsubrs using applicable smobs, these, in turn, need
four trampolines stored in the actual object. The gsubr smob
trampoline (which corresponds to the current scm_gsubr_apply) would
simply hand over the arguments to the trampoline of the gsubr
instance.
With such a construction, note that the code for compiling an arity to
four trampolines can be re-used to compute the trampolines of the
gsubr instance.
--- End Message ---
--- Begin Message ---
|
Subject: |
Applicable smobs & guile-vm |
|
Date: |
Fri, 25 Aug 2000 23:35:07 +0200 |
I vacillated back and forth many times this night on the point of
whether it was a good decision or not to add applicability to smobs.
In any case:
- It is not a good solution to your problem, Keisuke.
Before integrating the VM fully, one should be able to take an
arbitrary closure, compile it to a program, and then have it
interact with the rest of the Scheme as if it hadn't been compiled
at all, right?
But in order to achieve this, we need to support tail-recursion!
Otherwise, we'll not have Scheme semantics.
We need to think about this. We could learn from how RScheme
achieves tail-recursion, from the closure `apply' (which calls the
syntactic form address@hidden' internally, and from GOOPS methods and
compiled closures.
- I feel a little uncomfortable extending the Guile API without a
strong motivation. Smobs are supposed to be a way to add basic,
light-weight types. We are supposed to use the *new* (unfortunately
non-existing) GOOPS object representation for representing all other
new types. The only real motivation for using smobs instead of
GOOPS objects is when we want instance creation to be really simple
and where we want memory overhead to be small. This is not
generally the case for applicable objects.
- By adding `scm_set_smob_apply', we are at the same time promising to
support this in the future... There are now tons of applicable
things in the evaluator, and since these things are part of the
Guile API, any new interpreter or compiler needs to support them:
subrs, cclos, structs, GFs, pwses (and I've probably omitted
something).
- We can probably not use applicable smobs as the basic representation
for cclos because of the tail-recursiveness problem, so we can't
motivate them because they can eliminate the use of cclos. (If we
find a smart solution to the tail-recursiveness problem, they
actually might.)
- Same goes for pwses (procedure-with-setters).
On the other hand:
+ As I said before, applicable smobs could be a natural representation
for many internal Guile things, such as Guardians and standard eval
closures.
+ In fact, they would be a much better representation for gsubrs than
the current use of cclo.
+ In the future, we might want to eliminate smobs, replacing them with
a super-lightweight form of GOOPS object which has the class pointer
stored in a table.
+ Maybe, after all, applicability is a natural thing to support.
In any case, here's a point on the current applicable smobs:
It's possible to optimize the current smob dispatch mechanism
according to the following:
Currently, the role of the scm_apply_smob_X functions is to
translate the shape of the call to a shape which fits the function
installed in the smob type.
The structure of the scm_apply_smob_X functions is as switch
statements which select an appropriate translation form. Let's
call such a form a "trampoline".
Currently, we dynamically do all of the job to select the correct
trampoline at each call, when a lot of this job could actually be
performed once and for all in scm_set_smob_apply.
Here's a suggestion for a more efficient approach:
* We replace the current gsubr_type field in the smob descriptor
with the fields trampoline0, trampoline1, trampoline2, and,
trampoline3.
* Instead of having the trampolines in switch statements, we
implement them as separate C functions.
* Instead of calling the *generic* function (not in the OO sense!)
scm_apply_smob_0 in the evaluator, we call the function stored in
trampoline0. This field is *ahead of time* prepared with a
trampoline function which translates a zero arg call to the shape
appropriate for the function stored in the `apply' field.
* scm_set_smob_apply in a sense "compiles" the type by selecting
the appropriate trampolines at type creation time.
* Note now the possibility for a nice optimization:
If the function stored in `apply' takes, for example, two
required arguments, then the *function itself* can be stored in
`trampoline2', and we have eliminated one level of indirection.
--- End Message ---