towards a more unified procedure application mechanism

towards a more unified procedure application mechanism

[Andy Wingo]

Hey all,

I'm working on pulling dispatch of non-VM procedure applications into
the VM -- so invoking primitives written in C can happen quickly from
within the VM.

This is also a step along the path towards native compilation. Procedure
dispatch right now has so many cases -- it is feasible to inline all of
those cases into the VM, but once we generate native code, it would be
ludicrous to do so at all call sites.

One could trampoline out to an "apply" procedure, but that loses on tail
recursion in a number of important cases.

My approach is to start by listing all the different kinds of applicable
objects, and how the VM would apply them.

 scm_tc7_program            VM procedures
   - native support

 scm_tcs_closures           Interpreted procedures
   - Currently calls out to the interpreter, but in the future we will
     only see these during the first phase of bootstrapping, when eval.c
     is compiling eval.scm. This one should probably be moved to be a
     SMOB, because there is no need for code outside of eval.c to know
     about closures, and closures will only be live during the boot
     process.

 scm_tc7_subr_2o            SCM (*) () -- 0 arguments.
 scm_tc7_subr_1             SCM (*) (SCM) -- 1 argument.
 scm_tc7_subr_1o            SCM (*) (SCM) -- 1 optional argument.
 scm_tc7_subr_2o            SCM (*) (SCM, SCM) -- 2 required args.
 scm_tc7_subr_2o            SCM (*) (SCM, SCM) -- 2 optional args.
 scm_tc7_subr_3             SCM (*) (SCM, SCM, SCM) -- 3 required args.

 scm_tc7_lsubr              SCM (*) (SCM) -- list subrs
     All arguments are passed as a list.
 scm_tc7_lsubr_2            SCM (*) (SCM, SCM, SCM)
     A list subr with two required args.

 scm_tc7_dsubr              double (*) (double) -- double subrs
     Pretty much a bad non-optimization, IMO. Converts its argument to a
     double, calls the function, then converts the result double to a
     SCM -- dispatching to a generic if the ->double conversion didn't
     work.

 scm_tc7_cxr                c[da]+r
     Interprets the SUBR pointer as some kind of bit pattern for chasing
     car/cdr pairs. Only useful in the e.g. (map cddr ...) case, because
     otherwise cddr gets compiled better for the VM. And, in the future,
     map will do some inlining, so that even (map cddr ...) will compile
     nicely.

 scm_tc7_asubr              SCM (*) (SCM, SCM) -- "accumulating" subrs.
     With 0 arguments, returns subr (SCM_UNDEFINED, SCM_UNDEFINED).
     With 1 argument, returns subr (arg1, SCM_UNDEFINED).
     Otherwise returns subr (subr (arg1, arg2), arg3), ... -- like the
     semantics of +.

 scm_tc7_rpsubr             SCM (*) (SCM, SCM) -- predicate subrs.
     With 0 arguments, returns true.
     With 1 argument, returns subr (arg1, SCM_UNDEFINED).
     Otherwise, like an asubr, but returns SCM_BOOL_F if any subr
     invocation returns false. Otherwise returns SCM_BOOL_T.

 scm_tc7_smob               Applicable smobs
     Some smobs are applicable. Actually there are a number of smob
     apply procedures that one might choose to implement:
     SCM (*apply) ();
     SCM (*apply_0) (SCM);
     SCM (*apply_1) (SCM, SCM);
     SCM (*apply_2) (SCM, SCM, SCM);
     SCM (*apply_3) (SCM, SCM, SCM, SCM);
     In the apply_3 case, the last argument is a rest arg list.

 scm_tc7_gsubr              Generic subrs
     The is the base case in which you can have N required args, N
     optional args, and maybe rest args too. SCM_DEFINE produces
     gsubrs -- at least, it tries to. scm_c_define_gsubr actually
     returns e.g. scm_tc7_subr_1 for certain combinations of req, opt,
     and rest args; but we can change that.

 scm_tc7_pws                Procedures with setters
     Gets the procedure, and applies that. This needs to be inlined into
     the VM to preserve tail recursion.

 scm_tcs_struct             Applicable structs
     Currently, a struct needs one of two bits set for this to work:
     One case is if the procedure is a "pure generic", an instance of
     <generic> and not one of its subclasses, in which case we fetch or
     compute the effective method, and apply that.

     Actually it's worth mentioning here that for pure generics, the
     current GOOPS code returns an effective method that includes an
     #@dispatch isym, to speed up dispatch in the interpreter. It
     actually mutates a cache inline to to the memoized effective
     method.

     Generics that are instances of subclasses of <generic> cannot
     currently be applied at all, due to limitations in Guile's
     implementation of the generics MOP. But now that we have compiled
     procedures, I think we can just require that the effective method
     of a generic be any kind of applicable object, but normally a
     closure, implementing the dispatch algorithm in Scheme. That should
     be sufficiently fast, and if we need VM ops for dispatch, well so
     be it. At least that way we move more to Scheme and handle tail
     recursion too. That would allow the generic function application
     MOP to be finished -- including advice, before/after/around
     methods, different dispatch algorithms, etc.

     The other case is if the struct is an "operator". I don't really
     understand what these are -- the comment in objects.h seems to
     suggest that operators were an optimization for applicable structs
     and the evaluator. But they do not appear to be used anywhere; I
     will be happy to remove them entirely.

     Pascal Constanza's R6RS enhancement request seems relevant:
     http://www.r6rs.org/formal-comments/comment-6.txt

     I think his applicable struct construct seems to be equivalent to
     GOOPS/objects.c's "entities". I prefer Constanza's name though.

That's all the cases, afaict. I'll reply to my message with a plan of
action.

Andy
-- 
http://wingolog.org/

Re: towards a more unified procedure application mechanism

[Andy Wingo]

Hey folks,

I'd like to outline something of a plan.

The general outline is first to simplify dispatch, then to pull it into
the VM.

Ideally I would like to have only three kinds of procedures: VM
procedures, subrs, and applicable structs. It might not be possible to
simplify all of these, but we can try. We need to pay special attention
to avoiding unnecessary C API incompatibilities, but hopefully we have
sufficient room for refactoring.

On Sat 29 Aug 2009 13:38, Andy Wingo <wingo@pobox.com> writes:

>  scm_tc7_program            VM procedures
>    - native support

Yep.

>  scm_tcs_closures           Interpreted procedures

I am hoping to devise a way never to see these in the VM, on the
eval-cleanup branch.

>  scm_tc7_subr_2o            SCM (*) () -- 0 arguments.
>  scm_tc7_subr_1             SCM (*) (SCM) -- 1 argument.
>  scm_tc7_subr_1o            SCM (*) (SCM) -- 1 optional argument.
>  scm_tc7_subr_2o            SCM (*) (SCM, SCM) -- 2 required args.
>  scm_tc7_subr_2o            SCM (*) (SCM, SCM) -- 2 optional args.
>  scm_tc7_subr_3             SCM (*) (SCM, SCM, SCM) -- 3 required args.
>  scm_tc7_lsubr              SCM (*) (SCM) -- list subrs
>  scm_tc7_lsubr_2            SCM (*) (SCM, SCM, SCM)

I would like to make these all be gsubrs. There are very few places
where these constants actually exist in code "out there" -- normally the
way to do this is to use scm_c_define_gsubr, and it does the right
thing.

I'll probably do a:

#define scm_tc7_subr_2o \
  scm_tc7_subr_2o_NO_LONGER_EXISTS_USE_scm_c_define_gsubr

or something like that.

>  scm_tc7_dsubr              double (*) (double) -- double subrs

I'll remove these, changing their implementations to be gsubrs. This
only affects $sin et al; I'll probably roll the transcendental versions
into the subrs as well.

>  scm_tc7_cxr                c[da]+r

I'll change these to be subrs.

>  scm_tc7_asubr              SCM (*) (SCM, SCM) -- "accumulating" subrs.

These are interesting. We have to keep the C signature of e.g. scm_sum,
otherwise many things would break. So I'd change scm_sum to be a gsubr
with two optional arguments, and then on the Scheme level do something
like:

 (define +
   (let (($+ +))
     (lambda args
       (cond ((null? args) ($+))
             ((null? (cdr args)) ($+ (car args)))
             ((null? (cddr args)) ($+ (car args) (cadr args)))
             (else (apply + ($+ (car args) (cadr args)) (cddr args)))))))

The VM already compiles (+ a b c) to (add (add a b) c), where add is a
primitive binary instruction.

>  scm_tc7_rpsubr             SCM (*) (SCM, SCM) -- predicate subrs.

Likewise, we'll have to do something like the + case.

>  scm_tc7_smob               Applicable smobs

Well... we probably have to support these also as a primitive procedure
type. It could be we rework smobs in terms of structs, and if that
happens, we can use applicable structs -- but barring that, this would
be a fourth procedure type.

>  scm_tc7_gsubr              Generic subrs

Actually applying gsubrs can be complicated, due to optional args, rest
args, and the lack of `apply' in C. I guess we should farm out
application to a scm_i_gsubr_applyv trampoline that takes its args as an
on-the-stack vector.

>  scm_tc7_pws                Procedures with setters
>      Gets the procedure, and applies that. This needs to be inlined into
>      the VM to preserve tail recursion.

Ideally these would be implemented as applicable structs. We'll see.

>  scm_tcs_struct             Applicable structs

Check if the struct is applicable, and if so apply its effective method.


Well, that's my plan. Let me know if you have any concerns. This work is
probably not for this release.

Andy
-- 
http://wingolog.org/

Re: towards a more unified procedure application mechanism

[Ludovic Courtès]

Hi!

Andy Wingo <wingo@pobox.com> writes:

[...]

>>  scm_tcs_closures           Interpreted procedures
>
> I am hoping to devise a way never to see these in the VM, on the
> eval-cleanup branch.

Cool!

>>  scm_tc7_subr_2o            SCM (*) () -- 0 arguments.
>>  scm_tc7_subr_1             SCM (*) (SCM) -- 1 argument.
>>  scm_tc7_subr_1o            SCM (*) (SCM) -- 1 optional argument.
>>  scm_tc7_subr_2o            SCM (*) (SCM, SCM) -- 2 required args.
>>  scm_tc7_subr_2o            SCM (*) (SCM, SCM) -- 2 optional args.
>>  scm_tc7_subr_3             SCM (*) (SCM, SCM, SCM) -- 3 required args.
>>  scm_tc7_lsubr              SCM (*) (SCM) -- list subrs
>>  scm_tc7_lsubr_2            SCM (*) (SCM, SCM, SCM)
>
> I would like to make these all be gsubrs. There are very few places
> where these constants actually exist in code "out there" -- normally the
> way to do this is to use scm_c_define_gsubr, and it does the right
> thing.
>
> I'll probably do a:
>
> #define scm_tc7_subr_2o \
>   scm_tc7_subr_2o_NO_LONGER_EXISTS_USE_scm_c_define_gsubr
>
> or something like that.

You can't do that because such subrs are created by `create_gsubr ()'
when the signature allows it.  Or did you mean `create_gsubr ()' would
now create only gsubrs?

These specialized subr types allow for faster dispatch, as opposed to
the argument count checks (and argument copies) that are done in
`scm_i_gsubr_apply ()'.  Thus, I think replacing all of them with gsubrs
may have a negative impact performance-wise.

>>  scm_tc7_dsubr              double (*) (double) -- double subrs
>
> I'll remove these, changing their implementations to be gsubrs. This
> only affects $sin et al; I'll probably roll the transcendental versions
> into the subrs as well.

Yes, it seems to be seldom used.  However, it might be a semi-public
API...

>>  scm_tc7_cxr                c[da]+r
>
> I'll change these to be subrs.

OK (this was essentially an interpreter hack AIUI).

>>  scm_tc7_asubr              SCM (*) (SCM, SCM) -- "accumulating" subrs.
>
> These are interesting. We have to keep the C signature of e.g. scm_sum,
> otherwise many things would break. So I'd change scm_sum to be a gsubr
> with two optional arguments, and then on the Scheme level do something
> like:
>
>  (define +
>    (let (($+ +))
>      (lambda args
>        (cond ((null? args) ($+))
>              ((null? (cdr args)) ($+ (car args)))
>              ((null? (cddr args)) ($+ (car args) (cadr args)))
>              (else (apply + ($+ (car args) (cadr args)) (cddr args)))))))
>
> The VM already compiles (+ a b c) to (add (add a b) c), where add is a
> primitive binary instruction.

OK.

>>  scm_tc7_rpsubr             SCM (*) (SCM, SCM) -- predicate subrs.
>
> Likewise, we'll have to do something like the + case.
>
>>  scm_tc7_smob               Applicable smobs
>
> Well... we probably have to support these also as a primitive procedure
> type. It could be we rework smobs in terms of structs, and if that
> happens, we can use applicable structs -- but barring that, this would
> be a fourth procedure type.

Yes.

>>  scm_tc7_gsubr              Generic subrs
>
> Actually applying gsubrs can be complicated, due to optional args, rest
> args, and the lack of `apply' in C. I guess we should farm out
> application to a scm_i_gsubr_applyv trampoline that takes its args as an
> on-the-stack vector.

Indeed.

>>  scm_tc7_pws                Procedures with setters
>>      Gets the procedure, and applies that. This needs to be inlined into
>>      the VM to preserve tail recursion.
>
> Ideally these would be implemented as applicable structs. We'll see.
>
>>  scm_tcs_struct             Applicable structs
>
> Check if the struct is applicable, and if so apply its effective method.

Sounds like a nice plan!

Thanks,
Ludo'.

Re: towards a more unified procedure application mechanism

[Andy Wingo]

Hi Ludovic,

On Mon 31 Aug 2009 10:42, ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> writes:
>
>>>  scm_tc7_subr_2o            SCM (*) () -- 0 arguments.
>>>  scm_tc7_subr_1             SCM (*) (SCM) -- 1 argument.
>>>  scm_tc7_subr_1o            SCM (*) (SCM) -- 1 optional argument.
>>>  scm_tc7_subr_2o            SCM (*) (SCM, SCM) -- 2 required args.
>>>  scm_tc7_subr_2o            SCM (*) (SCM, SCM) -- 2 optional args.
>>>  scm_tc7_subr_3             SCM (*) (SCM, SCM, SCM) -- 3 required args.
>>>  scm_tc7_lsubr              SCM (*) (SCM) -- list subrs
>>>  scm_tc7_lsubr_2            SCM (*) (SCM, SCM, SCM)
>>
>> I would like to make these all be gsubrs. There are very few places
>> where these constants actually exist in code "out there" -- normally the
>> way to do this is to use scm_c_define_gsubr, and it does the right
>> thing.
>>
>> I'll probably do a:
>>
>> #define scm_tc7_subr_2o \
>>   scm_tc7_subr_2o_NO_LONGER_EXISTS_USE_scm_c_define_gsubr
>>
>> or something like that.
>
> You can't do that because such subrs are created by `create_gsubr ()'
> when the signature allows it.  Or did you mean `create_gsubr ()' would
> now create only gsubrs?

Yes, I mean for create_gsubr to return gsubrs.

> These specialized subr types allow for faster dispatch, as opposed to
> the argument count checks (and argument copies) that are done in
> `scm_i_gsubr_apply ()'.  Thus, I think replacing all of them with gsubrs
> may have a negative impact performance-wise.

That might be true with the current implementation, but it need not be
true with dispatch in the VM. The specialized subr types don't actually
gain us anything; you can do a gsubr dispatch just as fast, comparing
the tc16 instead of the tc7.

>>>  scm_tc7_dsubr              double (*) (double) -- double subrs
>>
>> I'll remove these, changing their implementations to be gsubrs. This
>> only affects $sin et al; I'll probably roll the transcendental versions
>> into the subrs as well.
>
> Yes, it seems to be seldom used.  However, it might be a semi-public
> API...

Undocumented of course. I seriously doubt this removal will cause
problems.

> Sounds like a nice plan!

We'll see how it goes :) This will be on my subr-simplification branch.

A
-- 
http://wingolog.org/

Re: towards a more unified procedure application mechanism

[Ludovic Courtès]

Hi!

Andy Wingo <wingo@pobox.com> writes:

>> These specialized subr types allow for faster dispatch, as opposed to
>> the argument count checks (and argument copies) that are done in
>> `scm_i_gsubr_apply ()'.  Thus, I think replacing all of them with gsubrs
>> may have a negative impact performance-wise.
>
> That might be true with the current implementation, but it need not be
> true with dispatch in the VM. The specialized subr types don't actually
> gain us anything; you can do a gsubr dispatch just as fast, comparing
> the tc16 instead of the tc7.

Hmm yes, you're right.  In the end you still have to compare something
and somehow handle optional and rest arguments.  Maybe you could try to
run `subr.bm' in your branch to see how it goes.

Thanks,
Ludo'.