Title

Define-syntax in local lexical scopes

Author

Antti Huima

Status

This SRFI is currently in withdrawn status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-24 @nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Abstract

This document specifies a proper extension to Scheme which allows define-syntax forms to appear in those places where local definitions can appear (R5RS, 5.2.2). A corresponding letrec-variant is described.

Issues

None yet...

Rationale

Local lexical scopes are often used to hide internal data. Module and object systems have been built on the idea of hiding internal state into a local lexical scope. R5RS explicitly prohibits define-syntax from appearing in local scopes (R5RS, 5.3). This gives to the top-level environment more syntactical power than to the local scopes, because on the top-level it is possible to create a mutually recursive pair of a procedure and a macro, whereas in local scopes it cannot be done conveniently. It is shown in this document that a simple transformation exists that can be used to mimic this behaviour in local scopes. The aim of this SRFI is to make this transformation explicit and give it a name, namely, define-syntax. A partial reference implementation is provided; full implementation requires system-specific features.

Specification

The following productions are added to the syntax of Scheme (R5RS, 7.1)

<definition> -> <syntax-definition>

<derived expression> -> (letrec-mixed (<syntax spec>*) (<binding spec>*) <body>)

The restriction that define-syntax cannot appear in a local scope is lifted (R5RS, 5.3). Instead, define-syntax can appear wherever a local definition of a value can.

The following equivalence is used to describe letrec-mixed. #unspecified denotes an undefined value: 

(letrec-mixed ((macro-name transformer) ...)
              ((variable init) ...)
   body body2 ...)

=

(let ((variable #unspecified) ...)
  (letrec-syntax ((macro-name transformer) ...)
    (set! variable init) ...
    body body2 ...))
More precisely, the order in which the variables receive their real values is unspecified in the manner as for letrec (R5RS, 7.3). Every init expression must be able to evaluate without making a reference to the other bound (run-time) variables. Every macro transformer is defined in the scope in which the bound variables are defined, and the initializing expressions as well as the body sequence are macro-expanded in a scope where the defined macros are visible. So the macros and the init-expressions can be mutually recursive.

It is an error for any symbol to appear in both the list of macro-names and variables.

The description of internal definitions (R5RS, 5.2.2) is changed to be given in the terms of letrec-mixed: A body containing internal definitions and internal syntax definitions can be converted into a completely equivalent letrec-mixed expression. For example, 

(let ((x 5))
  (define-syntax foo
    (syntax-rules ()
      ((foo y) (bar x y))))
  (define bar (lambda (a b) (+ (* a b) a)))
  (foo (+ x 3))) ==> 45
is equivalent to 
(let ((x 5))
  (letrec-mixed ((foo (syntax-rules ()
                        ((foo y) (bar x y)))))
                ((bar (lambda (a b) (+ (* a b) a))))
    (foo (+ x 3))))

Implementation

The following reference implementation represents the idea but is not full implementation. The author believes strongly that a complete implementation is impossible to write by using the macro system of R5RS alone. The problem here is that in order to make the process of expanding internal definitions visible, the keyword lambda must be redefined. However, the new expansion of lambda must refer to the original definition of lambda. Therefore define-syntax cannot be used to rebind lambda, so we need to resort to describing the effect upon a single expression E by putting it inside a series of let-syntaxes and letrec-syntaxes. Also, all derived forms must be redefined to use the new lambda form. The place for this is denoted below but the details are omitted. Moreover, only literally appearing begin, define and define-syntax forms are recognized. If a macro expands to begin, define or define-syntax form the expansion of internal definitions stops [although R5RS is not completely clear on whether allowing internal definitions as results of macro expansion is mandatory].

This being explained, let E be a Scheme expression. The effects of the extension above can be implemented by (letrec-mixed incorrectly fixes evaluation order): 

(define-syntax letrec-mixed
  (syntax-rules ()
    ((letrec-mixed ((?s ?d) ...) ((?v ?e) ...) ?b ?b2 ...)
     (let ((?v #f) ...)
       (letrec-syntax ((?s ?d) ...)
	 (set! ?v ?e) ...
	 ?b ?b2 ...)))))

(letrec-syntax
    ((expand-internal-definitions
      (syntax-rules (begin define define-syntax)

	((expand-internal-definitions ?syntaxes ?values
	    (begin ?expr ...) ?later ...)
	 (expand-internal-definitions
	  ?syntaxes ?values
	  ?expr ... ?later ...))

	((expand-internal-definitions ?syntaxes ?values
	    (define (?variable . ?args) ?body ?body2 ...) ?later ...)
	 (expand-internal-definitions
	  ?syntaxes ?values
	  (define ?variable (lambda ?args ?body ?body2 ...))
	  ?later ...))

	((expand-internal-definitions ?syntaxes ?values
                                      (define ?variable ?value) ?later ...)
	 (expand-internal-definitions
	  ?syntaxes
	  ((?variable ?value) . ?values)
	  ?later ...))

	((expand-internal-definitions ?syntaxes ?values
            (define-syntax ?macro ?expansion) ?later ...)
	 (expand-internal-definitions
	  ((?macro ?expansion) . ?syntaxes)
	  ?values
	  ?later ...))

	((expand-internal-definitions ((?macro ?expansion) ...)
	    ((?variable ?value) ...)
	    ?other ...)
	 (letrec-mixed ((?macro ?expansion) ...)
		       ((?variable ?value) ...)
	    ?other ...)))))
  (let-syntax
      ((lambda
	   (syntax-rules ()
	     ((lambda ?args ?body ?body2 ...)
	      (lambda ?args
		(expand-internal-definitions () () ?body ?body2 ...))))))
      (letrec-syntax REDEFINE DERIVED FORMS ...
         E)))

This has been tested to work on Petite Scheme. Here is an example that has mutually recursive macros and procedures: 

(let ()
  (define (x n)
    (if (> n 0) (+ 1 (call-y (- n 1))) 0))
  (define (y n)
    (if (> n 0) (* 2 (call-x-indirectly (- n 1))) 1))
  (define-syntax call-x-indirectly
    (syntax-rules () ((_ arg ...) (call-x arg ...))))
  (define-syntax call-x
    (syntax-rules () ((_ arg ...) (x arg ...))))
  (define-syntax call-y
    (syntax-rules () ((_ arg ...) (y arg ...))))
  (call-x 10)) ==> 31

On a conforming implementation the expression evaluates to 31, and is completely equivalent to 

(let ()
  (define (x n) (if (> n 0) (+ 1 (y (- n 1))) 0))
  (define (y n) (if (> n 0) (* 2 (x (- n 1))) 1))
  (x 10))

Note on set!-free implementations

A Scheme implementation can prefer to implement the expansion of letrec without employing set!. The expansion of letrec-mixed is also easy to describe in terms of alpha-conversion and (conceptually) created environment frames. The standard letrec-form 

(letrec ((v e) ...) b b2 ...)

can be though to work as follows: every variable v is alpha-converted to v* inside all the e's and the bodies. Upon run-time, an environment frame (a set of locations) is created when the evaluation of letrec starts, and the alpha-converted variables v* denote each one slot in this frame. The frame contains originally undefined values. The initializing expressions e are evaluated in some order and the resulting values are written to the environment frame. If a reference to the frame is made such that the initial, undefined value is returned, an error occurs.

Then 

(letrec-mixed ((m x) ...) ((v e) ...) b b2 ...)
can be described by first performing the alpha-conversion of v's to v*'s inside x's, e's and the bodies. After that, the form is handled by macro-expanding the e's and bodies by applying the alpha-converted macro expanders.

Copyright

Copyright (C) Antti Huima (2001). All Rights Reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Editor: Mike Sperber
Last modified: Fri Oct 12 18:22:39 CEST 2007