Define-syntax in local lexical scopes
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.
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.
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))) ==> 45is 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))))
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))
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.
(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.
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.