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

From: Jens Axel Søgaard (jensaxel at soegaard.net)
Date: Sun Nov 12 18:30:48 EST 2006

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...

>> 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.

> 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.


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 ...))]))

   (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 ...)))]))

(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.

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"



Posted on the users mailing list.