Racket: local-expanding recursive definitions

Question

I'm trying to write a macro behaving just like racket define, but processing fully expanded racket procedures in some way (just expanding for simplicity in the example below):

(define-syntax (define/expand stx)
  (syntax-case stx ()
    [(_ (head args ...) body body-rest ...)
       (let* ([define/racket (syntax/loc stx (define (head args ...) body body-rest ...))]
              [fully-expanded (local-expand define/racket 'top-level (list))])
           fully-expanded)]
    [(_ id expr) (syntax/loc stx (define id expr))]))

Everything is fine unless recursive definition is met:

(define/expand (sum n)
  (if (<= n 0)
      0
      (+ n (sum (- n 1)))))

Running it raises an error

sum: unbound identifier in module in: sum

pointing the call of the sum (not the definition). Obviously the definition of sum is not captured by local expander. I've tried a straightforward way of fixing it: creating new local definition context and binding head into it:

(define-syntax (define/expand stx)
  (syntax-case stx ()
    [(_ (head args ...) body body-rest ...)
       (let* ([ctx (syntax-local-make-definition-context)]          ; <- These two lines added 
              [_ (syntax-local-bind-syntaxes (list #'head) #f ctx)] ; <--/
              [define/racket (syntax/loc stx (define (head args ...) body body-rest ...))]
              [fully-expanded (local-expand define/racket 'top-level (list) ctx)])
           fully-expanded)]
    [(_ id expr) (syntax/loc stx (define id expr))]))

It solves the problem (local expanded successfully expands the procedure into define-values), but creates the other one:

module: out-of-context identifier for definition in: sum

pointing the definition of sum. The reason is probably that expander binds identifiers to one in ctx instead of head in current context.

Intuitively it does not seem to be a rare problem, but I could not find the solution over the network. I thought that I should somehow use local-expand/capture-lifts and syntax-local-lift-expression, but I don't get how to use it properly. Could someone clarify what's going on and/or give a hint how to fix it?

Another sometimes-useful trick: call local-expand on a lambda binding the unbound variables, then pattern-match the result to get the body out. — Ben Greenman

soegaard soegaard · Accepted Answer · 2016-09-05T11:36:53

Let's try your first program in a top-level (repl):

#lang racket
(define-syntax (define/expand stx)
  (syntax-case stx ()
    [(_ (head args ...) body body-rest ...)
     (let*
         ([define/racket  (syntax/loc stx (define (head args ...) body body-rest ...))]
          [fully-expanded (local-expand define/racket 'top-level (list))])
       fully-expanded)]
    [(_ id expr)
     (syntax/loc stx (define id expr))]))

and then in the repl:

Welcome to DrRacket, version 6.6.0.3--2016-07-28(-/f) [3m].
Language: racket, with debugging [custom]; memory limit: 1024 MB.
> (define/expand (sum n)
  (if (<= n 0)
      0
      (+ n (sum (- n 1)))))
.#<syntax:3:2 (define-values (sum) (lambda ...>
> (sum 5)
15

This shows that your program works at the top-level.

The reason the same approach doesn't work in a module context is that the #%module-begin uses partial expansion of forms to detect definitions before expanding expressions. In other words define/expand must tell #%module-begin that it expands into a definition of sum but must delay the use of local-expand until #%module-begin has detected all bound identifiers at the module level.

This suggests a two step approach:

#lang racket

(define-syntax (delay-expansion stx)
  (syntax-case stx ()
    [(_delay-expansion more ...)
     (let ([fully-expanded (local-expand #'(lambda () more ...) 'module (list))])
       (display fully-expanded)
       fully-expanded)]))

(define-syntax (define/expand stx)
  (syntax-case stx ()
    [(_ (head args ...) body body-rest ...)
     (syntax/loc stx
       (define (head args ...)
         ((delay-expansion
           body body-rest ...))))]
    [(_ id expr)
     (syntax/loc stx
       (define id expr))]))


(define/expand (sum n)
  (if (<= n 0)
      0
      (+ n (sum (- n 1)))))

(sum 5)

See more here: https://groups.google.com/d/msg/racket-users/RB3inP62SVA/54r6pJL0wMYJ

Racket: local-expanding recursive definitions

1 Answers