[plt-scheme] Macro techniques for implementing lexical scoped binding constructs

--- Jens Axel Søgaard <jensaxel at soegaard.net> wrote:

> Ryan Culpepper skrev:
> > --- Jens Axel Søgaard <jensaxel at soegaard.net> wrote:
> >> Is there a "canoncial" way of implementing lexical scoped
> >> binding constructs "from scratch"?
> > 
> > Yes: as you mentioned, syntax-parameters are good for this.
> 
> ...
> 
> >> What bothers me here is the use of local-expand.
> >>
> >> Should it bother me?
> > 
> > Yes, it should. Generally, using local-expand for "deep"
> > expansion should make you nervous about both the correctness
> > and the performance of your macros.
> 
> I don't see why local-expand hurts performance in this case.
> Since the result of the local expansion is returned as the
> result, no further expansion is needed -- oooh! -- the expander
> doesn't know that, so it reexpands again...

Yes.

> >> Is there alternatives? (syntax-parameters perhaps - but how?)
> > 
> > Here's how to do it with syntax parameters:
> > 
> >   (require (lib "stxparam.ss"))
> >   (require-for-syntax (lib "stxparam.ss"))         
> >   
> >   (define-syntax-parameter the-env null)
> >   
> >   (define-syntax (letn stx)
> >     (syntax-case stx ()
> >       [(letn ([name value] ...) . body)
> >        (with-syntax ([(var ...) (generate-temporaries #'(name
> ...))])
> >          #'(let ([var value] ...)
> >              (let-syntax ([old-env 
> >                            (syntax-parameter-value #'the-env)])
> >                (syntax-parameterize
> >                    ([the-env
> >                      (append (list (cons #'name #'var) ...)
> >                              (syntax-local-value #'old-env))])
> >                  . body))))]))
> >   
> >   (define-syntax (ref stx)
> >     (syntax-case stx ()
> >       [(ref name)
> >        (let ([env (syntax-parameter-value #'the-env)])
> >          (let loop ([env env])
> >            (cond [(pair? env)
> >                   (if (module-identifier=? #'name (car (car
> env)))
> >                       (cdr (car env))
> >                       (loop (cdr env)))]
> >                  [else 
> >                   (raise-syntax-error 'ref "unbound name" 
> >                                       #'name)])))]))
> 
> Thanks! That made things fell into place. With syntax-parameters
> the environment is embedded in the syntax objects.

More precisely, the letn macro makes the extension of the environment
explicit in the *code that it produces*, rather than by doing
something in the transformer procedure itself.

(Aside:
This theme comes up over and over in macro programming. Recall the
discussion from a couple weeks ago about attaching information to
identifiers when you cited Matthew's ICFP paper. In order make
side-effects work right, you've got to make them part of the program,
not just something that happens inside a macro transformer.)

> > The first time I tried this, I wrote the syntax-parameterize like
> > this:
> > 
> >   (syntax-parameterize 
> >         ((the-env (append --- (syntax-parameter-value
> #'the-env))))
> >     ---)
> > 
> > There seems to be a bug in the implementation of
> syntax-parameterize
> > that causes that to raise an "identifier out of context" error.
> So I
> > changed the code to retrieve the old value of the parameter
> outside
> > of the parameterization, and it worked.
> > 
> > This implementation passes your tests.
> 
> Actually, it missing the next-to-last one. My example were silly,
> so each (ref x) expands to a copy of the expression associated with
> x.

Oops, yes, I forgot that I "fixed" that.

> Here is an attempt to abstract the pattern in which
> syntax-parameter and let-syntax is used together:
> 
> (module expansion mzscheme
>    (provide (all-defined))
> 
>    (require-for-syntax   (lib "stxparam.ss"))
>    (require              (lib "stxparam.ss"))
> 
>    (define-syntax (define-expansion-parameter stx)
>      (syntax-case stx ()
>        [(_ name expr)
>         #'(define-syntax-parameter name expr)]))
> 
>    (define-syntax (expansion-parameterize stx)
>      (syntax-case stx ()
>        [(_ ([name expr] ...) body ...)
>         #'(let-syntax ([old-name (syntax-parameter-value #'name)]
>                        ...)
>             (syntax-parameterize
>              ([name expr] ...)
>              body ...))]))

Since old-name is introduced by the macro, it can't be used in the
exprs. The let-syntax there is a no-op. Actually, I expect this would
fail if you do expansion-parameterize with more than one binding
clause.

>    (define-syntax (expansion-value stx)
>      (syntax-case stx ()
>        [(_ name)
>         #'(syntax-parameter-value #'name)])))
> 
> 
> (require-for-syntax expansion)
> (require expansion)
> 
> 
> (define-expansion-parameter the-env null)
> 
> (define-syntax (letn stx)
>    (syntax-case stx ()
>      [(letn ([name value] ...) body ...)
>       (with-syntax ([((old-name . old-value) ...)
>                      (expansion-value the-env)])
>         #'(expansion-parameterize
>            ([the-env (list (cons #'name #'value) ...
>                            (cons #'old-name #'old-value) ...)])
>            (begin body ...)))]))

What you're actually doing here is fetching the old environment and
serializing it into the code the macro produces. That's another way
to solve the problem, and it works fine because alists are simple to
serialize.

> (define-syntax (ref stx)
>    (syntax-case stx ()
>      [(ref name)
>       (let ([env (expansion-value the-env)])
>         (let loop ([env env])
>           (cond [(pair? env)
>                  (if (module-identifier=? #'name (car (car env)))
>                      (cdr (car env))
>                      (loop (cdr env)))]
>                 [else
>                  (raise-syntax-error 'ref "unbound name"
>                                      #'name)])))]))
> 
> The above works. However, I tried to implement an
> expansion-parameter that allow me to write letn like this:
> 
> (define-syntax (letn stx)
>    (syntax-case stx ()
>      [(letn ([name value] ...) body ...)
>       (let ([old-env (expansion-value the-env)])
>          (expansion-parameterize
>            ([the-env (list (cons #'name #'value) ...
>                            old-env])
>            #'(begin body ...)))]))
> 
> The philosophy being that since the environment isn't part
> of the expanded syntax, it should be "hidden" behind the scenes.

The superficial problems (the "no #%app transformer" error) can be
fixed with a few require-for-templates for mzscheme and stxparam.ss
and some care with #' and #`.

The deeper problem is that expand-parameterize is the wrong
abstraction. It looks like it's introducing bindings in the
transformer procedure, but it's not; it's generating code that
produces bindings in the program itself. It makes you think you can
refer to local variables (old-env) in the right-hand side; you can't.
Once the macro transformer returns, old-env is gone, meaningless, and
you'll get an "identifier used out of context" error from the
expander.

Ryan

> My attempt to define expansion-parameter were
> (note the double #'#'):
> 
>    (define-syntax (expansion-parameterize stx)
>      (syntax-case stx ()
>        [(_ ([name expr] ...) body ...)
>         #'#'(let-syntax ([old-name (syntax-parameter-value #'name)]
>                        ...)
>             (syntax-parameterize
>              ([name expr] ...)
>              body ...))]))
> 
> Alas, I get an
> 
>    compile: bad syntax; function application is not allowed,
> because no
>    #%app syntax transformer is bound in: (let-syntax ((old-name
>    (syntax-parameter-value (syntax the-env)))) (syntax-parameterize
>    ((the-env (list (cons (syntax foo) (syntax 42))))) (syntax
> (begin (+ 1
>    (ref foo))))))
> 
> that I can't get rid of.
> 
> -- 
> Jens Axel Søgaard
> 
> The more data I punch in this card, the lighter it becomes, and the
> lower the mailing cost.
>                  -- S. Kelly-Bootle, "The Devil's DP Dictionary"