Re: macro helpers

[Mark H Weaver]

Hi Stefan,

Stefan Israelsson Tampe <address@hidden> writes:

> Writing efficient macros is a bit difficult. Let me explain by using
> an example. The background is that I maintaining a python compiler and
> python like object system and would like to program a scheme macro
> that would be the scheme counterpart to various python construct. For
> fun consider pythons for loop. it's looping depending on iterators and
> have break and continue.
>
> Here is a hypothetical for loop:
>
> (for lp ((x : I)) ((c 1))
> (lp #:continue (+ x c))
>
> #:final
> c)
>
> The python iterators signals the end of the loop with raising en
> exception which is not too costly and we will return the #:final as a
> value at that point. This is a mix of scheme and python. Now what we
> can do further is to introduce break,continue and break and final as
>
> (lp #:continue c) e.g. continue with c
> (lp #:break c) e.g. break with c
> (lp #:final) e.g. execute final with current c
>
> This has a great potential of a easy generalization of python for
> loops an implementation could be like, its very slow though, here is a
> take on the implementation which describes the macro (more work is
> needed, not a propper pattern here)
>
> (define-syntax for
> (lambda (x)
> (syntax-case x ()
> ((for lp ((x ... : E) ... (c n) ...) code ... #:final fin ...)
> (with-syntax (((It ...) (generate-temporaries #'(O ...)))
> ((cc ...) (generate-temporaries #'(c ...)))
> (((x1 ...) ...) (generate-temporaries #'((x ...) ...)))
> (((x2 ...) ...) (generate-temporaries #'((x ...) ...))))
> #'(let ((It E) ... (c n) ... (x 'None) ... ...)
> (let/ec lp-break
> (catch IteratorException
> (lambda ()
> (letrec ((enclosing
> (lambda (cc ...)
> (set! c cc) ...
> (call-with-values
> (lambda () (next It))
> (lambda (x2 ...)
> (set! x1 x2) ...))
> ...
> (set! x x1)
> ... ...
> (call-with-values
> (lambda ()
> (let/ec lp-continue
> (define (lp tag . args)
> (cond
> ((eq? tag #:continue)
> (apply lp-continue args))
> ((eq? tag #:break)
> (apply lp-break args))
> ((eq? tag #:final)
> (lp-continuation #:final))))
> code ...))))
> (lambda args
> (if (eq? (car args) #:final)
> (throw IteratorException)
> (apply enclosing (cdr args))))))))
> (enclosing c ...)))
> (lambda q fin ...)))))))))

You will probably have an easier time finding reviewers if they aren't
forced to copy your code into another buffer and to re-indent it.  To
make matters worse, when I try to re-indent it, I find that the
parentheses are not balanced.

However, I can point out a few efficiency problems right off the top:

* Your macro inserts the following procedure within each loop:

    (define (lp tag . args)
      (cond
       ((eq? tag #:continue)
        (apply lp-continue args))
       ((eq? tag #:break)
        (apply lp-break args))
       ((eq? tag #:final)
        (lp-continuation #:final))))

  It's pretty bad for these basic loop control features to be combined
  into a single procedure, which must then dispatch on the value of
  'tag'.  However, to make matters worse, the existence of the 'rest'
  argument 'args' forces list structure to be head-allocated for those
  arguments.

  A better solution would be to make 'lp' into a macro that dispatches
  on its keyword argument at compile-time.

* You use 'set!' on many variables, which prevents most (all?)
  optimizations from being done on those variables, and forces
  heap-allocated variable objects to be created for them.

> The value of tail position is transfered to the next iteration of the
> loop. It's not functional. But this is for the full featured version
> in which lp may be transferred to another function and there inside a
> loop called e.g.all crazy things, the easy steps would be to have full
> control in multiple loops.  Note how this enables great refactoring of
> functions with many loops inside loops. Anyway for normal loops this
> is really really slow, and one would really like to have streamlined
> code when (lp #:continue ...) is used at tail positions and for cases
> where we can prove that lp is never used in any advanced
> configuration, we would like to know if lp, (lp #:continue ..) (in
> tail position) and finally if (lp #:break ...) is used or not. But how
> to do this at the macro level?

It can't be done, because of macros.  Macros must be expanded outermost
first, because until the outermost macros are expanded, you have no way
of knowing which inner constructs will be expressions.  However, this
means that when your loop macro is expanded, the macros within have not
yet been expanded yet, so you have no way of understanding the structure
of the inner code.

However, you could perhaps arrange to generate code that Guile's
compiler will be able to optimize effectively.  Avoiding mutation of
variables, and eliminating things like the dynamic dispatch on 'tag' in
your multiplexed 'lp' procedure, would go a long way toward that goal.

       Mark