head 1.65; access; symbols; locks; strict; comment @# @; 1.65 date 2007.11.05.02.50.34; author al; state Exp; branches; next 1.64; 1.64 date 2006.11.25.05.11.24; author al; state Exp; branches; next 1.63; 1.63 date 2006.05.28.03.42.52; author al; state Exp; branches; next 1.62; 1.62 date 2006.05.28.00.57.55; author al; state Exp; branches; next 1.61; 1.61 date 2006.05.24.00.54.56; author al; state Exp; branches; next 1.60; 1.60 date 2006.05.24.00.54.01; author al; state Exp; branches; next 1.59; 1.59 date 2006.05.23.23.47.17; author al; state Exp; branches; next 1.58; 1.58 date 2004.10.29.00.41.35; author al; state Exp; branches; next 1.57; 1.57 date 2004.10.29.00.37.04; author al; state Exp; branches; next 1.56; 1.56 date 2004.10.28.11.12.33; author al; state Exp; branches; next 1.55; 1.55 date 2004.10.28.09.43.14; author al; state Exp; branches; next 1.54; 1.54 date 2003.11.16.02.27.39; author al; state Exp; branches; next 1.53; 1.53 date 2003.11.15.17.40.54; author al; state Exp; branches; next 1.52; 1.52 date 2003.11.15.00.55.27; author al; state Exp; branches; next 1.51; 1.51 date 2003.10.25.19.14.46; author al; state Exp; branches; next 1.50; 1.50 date 2003.10.23.04.11.31; author al; state Exp; branches; next 1.49; 1.49 date 2003.10.20.07.10.42; author al; state Exp; branches; next 1.48; 1.48 date 2003.10.20.01.03.09; author al; state Exp; branches; next 1.47; 1.47 date 2003.10.20.00.33.03; author al; state Exp; branches; next 1.46; 1.46 date 2003.10.18.20.39.04; author al; state Exp; branches; next 1.45; 1.45 date 2003.10.18.12.17.05; author al; state Exp; branches; next 1.44; 1.44 date 2003.10.06.01.05.06; author al; state Exp; branches; next 1.43; 1.43 date 2003.10.05.17.06.04; author al; state Exp; branches; next 1.42; 1.42 date 2002.10.03.18.47.08; author al; state Exp; branches; next 1.41; 1.41 date 2002.09.25.20.44.50; author al; state Exp; branches; next 1.40; 1.40 date 2002.09.16.04.48.48; author al; state Exp; branches; next 1.39; 1.39 date 2002.09.15.23.29.39; author al; state Exp; branches; next 1.38; 1.38 date 2002.09.12.05.06.55; author al; state Exp; branches; next 1.37; 1.37 date 2002.09.12.01.28.04; author al; state Exp; branches; next 1.36; 1.36 date 2002.09.11.22.22.23; author al; state Exp; branches; next 1.35; 1.35 date 2002.09.11.06.11.28; author al; state Exp; branches; next 1.34; 1.34 date 2002.09.09.04.27.35; author al; state Exp; branches; next 1.33; 1.33 date 2002.09.06.20.17.26; author al; state Exp; branches; next 1.32; 1.32 date 2002.09.06.20.07.05; author al; state Exp; branches; next 1.31; 1.31 date 2002.09.06.12.33.16; author al; state Exp; branches; next 1.30; 1.30 date 2002.09.06.07.08.36; author al; state Exp; branches; next 1.29; 1.29 date 2002.09.06.04.01.48; author al; state Exp; branches; next 1.28; 1.28 date 2002.09.06.02.18.36; author al; state Exp; branches; next 1.27; 1.27 date 2002.09.05.19.45.08; author al; state Exp; branches; next 1.26; 1.26 date 2002.09.05.17.30.35; author al; state Exp; branches; next 1.25; 1.25 date 2002.09.05.09.44.36; author al; state Exp; branches; next 1.24; 1.24 date 2002.09.04.22.50.03; author al; state Exp; branches; next 1.23; 1.23 date 2002.09.04.14.56.38; author al; state Exp; branches; next 1.22; 1.22 date 2002.09.04.03.01.39; author al; state Exp; branches; next 1.21; 1.21 date 2002.08.25.06.22.16; author al; state Exp; branches; next 1.20; 1.20 date 2002.08.23.22.02.03; author al; state Exp; branches; next 1.19; 1.19 date 2002.08.20.16.36.32; author al; state Exp; branches; next 1.18; 1.18 date 2002.08.19.23.27.56; author al; state Exp; branches; next 1.17; 1.17 date 2002.08.19.19.50.11; author al; state Exp; branches; next 1.16; 1.16 date 2002.08.19.14.23.39; author al; state Exp; branches; next 1.15; 1.15 date 2002.08.18.21.06.12; author al; state Exp; branches; next 1.14; 1.14 date 2002.08.18.18.48.35; author al; state Exp; branches; next 1.13; 1.13 date 2002.08.18.12.18.01; author al; state Exp; branches; next 1.12; 1.12 date 2002.08.18.05.00.19; author al; state Exp; branches; next 1.11; 1.11 date 2002.08.18.00.20.54; author al; state Exp; branches; next 1.10; 1.10 date 2002.08.17.19.47.28; author al; state Exp; branches; next 1.9; 1.9 date 2002.08.17.04.03.39; author al; state Exp; branches; next 1.8; 1.8 date 2002.08.07.23.19.28; author al; state Exp; branches; next 1.7; 1.7 date 2002.08.07.23.10.47; author al; state Exp; branches; next 1.6; 1.6 date 2002.08.07.04.42.10; author al; state Exp; branches; next 1.5; 1.5 date 2002.08.06.21.49.53; author al; state Exp; branches; next 1.4; 1.4 date 2002.08.06.17.56.10; author al; state Exp; branches; next 1.3; 1.3 date 2002.08.02.04.25.41; author al; state Exp; branches; next 1.2; 1.2 date 2002.08.02.01.31.33; author al; state Exp; branches; next 1.1; 1.1 date 2002.08.01.22.30.13; author al; state Exp; branches; next ; desc @@ 1.65 log @Local variables are no longer all gratuitously renamed. We only rename when necessary. See unrename-locals. New function expand-program-to-simple shows how to use a second pass to get even simpler output (with no LETREC, DELAY, or BEGIN). Now dual-licensed under 3-clause BSD license and GNU GPL >= 2. (Added BSD licensing per request of Felix Winkelmann, for use in Chicken-related work.) Choosing symbols for variables in the final output is now put off to a later pass (the symbolize function). During the main expander functions, any variables in the generated pieces of output code are represented by vectors. No new symbols are created until symbolize is invoked. Added a link to the source distribution site (petrofsky.org). New top-level functions: expand-top-level-sexps (broken out from expand-top-level-forms), make-var1, make-var2, var-name, var-loc, make-letrec (broken out from expand-body), unrename-locals, symbolize, var->symbol, expand-program-to-simple. Renamed functions: variable? -> var? @ text @;; alexpander.scm: a macro expander for scheme. ;; $Id$ ;; Copyright 2002-2004,2006,2007 Al Petrofsky ;; LICENSING (3-clause BSD or GNU GPL 2 and up) ;; Redistribution and use in source and binary forms, with or without ;; modification, are permitted provided that the following conditions ;; are met: ;; ;; Redistributions of source code must retain the above copyright ;; notice, this list of conditions and the following disclaimer. ;; ;; Redistributions in binary form must reproduce the above copyright ;; notice, this list of conditions and the following disclaimer in ;; the documentation and/or other materials provided with the ;; distribution. ;; ;; Neither the name of the author nor the names of its contributors ;; may be used to endorse or promote products derived from this ;; software without specific prior written permission. ;; ;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT ;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR ;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT ;; HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, ;; INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, ;; BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS ;; OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED ;; AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT ;; LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY ;; WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE ;; POSSIBILITY OF SUCH DAMAGE. ;; Alternatively, you may redistribute, use, or modify this software ;; according to the terms of the GNU General Public License as ;; published by the Free Software Foundation (fsf.org); either version ;; 2, or (at your option) any later version. ;; INTRODUCTION: ;; This file implements a macro-expander for r5rs scheme (plus some ;; interesting extensions). There is no magic here to hook this into ;; your native eval system: this is a simple data-in, data-out program ;; that takes a macro-using program represented as scheme data and ;; produces an equivalent macro-free program represented as scheme ;; data. ;; This is mostly intended as a demonstration. Although it certainly ;; could be useful for adding macros to a simple scheme system that ;; lacks any macros, it may not be feasible to get it to interact ;; properly with a low-level macro system or a module system. ;; The expander is written in portable r5rs scheme, except for one use ;; of the pretty-print procedure which you can easily comment out. ;; To try it out, just load the file and execute (alexpander-repl). ;; Skip to the "BASIC USAGE" section for more information. ;; To find the latest version of this program, try here: ;; http://petrofsky.org/src/alexpander.scm ;; ;; To find older versions or the log messages between versions, try here: ;; http://petrofsky.org/src/RCS/alexpander.scm,v ;; If you are wondering what "r5rs scheme" is, see: ;; Richard Kelsey, William Clinger, and Jonathan Rees, "Revised^5 ;; report on the algorithmic language Scheme", Higher-Order and ;; Symbolic Computation, 11(1):7-105, 1998. Available at: ;; PDF: http://www-swiss.ai.mit.edu/~jaffer/r5rs.pdf ;; LaTeX source: ftp://swiss.csail.mit.edu/pub/scheme-reports/r5rs.tar.gz ;; EXTENSIONS: ;; The expander supports all the features of the r5rs macro system, ;; plus several extensions in the way syntaxes can be specified and ;; used, which are best summarized in BNF: ;; Modified r5rs productions: ;; ---> | | ;; | | | ;; | | | ;; | ;; ;; ---> (define-syntax ) ;; | (begin *) ;; | ;; ;; ---> ( ) ;; ;; ---> ( *) ;; ;; ---> (define ) ;; | (define ( ) ) ;; | (define ) ;; | (begin *) ;; | ;; | ;; ;; ---> | ;; | (begin *) ;; | ;; | ;; New productions: ;; ---> | ;; ;; ---> ;; | ;; | ;; | ;; ;; ---> ( ) ;; ;; ;; ---> ( ) ;; ;; ;; ---> (*) * ;; ;; ---> let-syntax | letrec-syntax ;; These extensions all have the obvious meaning. ;; Okay, I'll elaborate on that a little bit. Consider the intializer ;; position of a syntax definition and the head position of a ;; list-format expression: ;; (define-syntax ) ;; ( *) ;; In r5rs, must be a transformer. may be an expression, ;; in which case the enclosing expression is taken to be a procedure ;; call and the s are the expressions for the operands, or ;; may be a keyword bound to a syntax (a builtin or transformer), in ;; which case the s are processed according to that syntax. ;; The core generalization in our system is that both and ;; may be any type of expression or syntax. The four forms of syntax ;; allowed are: a transformer (as allowed in the position in ;; r5rs), a keyword (as allowed in the position in r5rs), a ;; macro use that expands into a syntax, and a macro block (let-syntax ;; or letrec-syntax) whose body is a syntax. ;; Some examples: ;; ;; ;; a macro with a local macro ;; (let-syntax ((foo (let-syntax ((bar (syntax-rules () ((bar x) (- x))))) ;; (syntax-rules () ((foo) (bar 2)))))) ;; (foo)) ;; => -2 ;; ;; ;; an anonymous let transformer, used directly in a macro call. ;; ((syntax-rules () ;; ((let ((var init) ...) . body) ;; ((lambda (var ...) . body) ;; init ...))) ;; ((x 1) (y 2)) ;; (+ x y)) ;; => 3 ;; ;; ;; a keyword used to initialize a keyword ;; (let-syntax ((q quote)) (q x)) => x ;; ;; ;; Binding a keyword to an expression (which could also be thought ;; ;; of as creating a macro that is called without arguments). ;; (let ((n 0)) ;; (let-syntax ((x (set! n (+ n 1)))) ;; (begin x x x n))) ;; => 3 ;; ;; (let-syntax ((x append)) ((x x))) => () ;; Internal syntax definitions. ;; Internal syntax definitions are supported wherever they would make ;; sense (see the BNF), and they have the letrec-syntax semantics you ;; would expect. It is legal for the initializer of an internal ;; variable definition to use one of the internal syntax definitions ;; in the same body: ;; (let () ;; (define x (y)) ;; (define-syntax y (syntax-rules () ((y) 1))) ;; x) ;; => 1 ;; It's also legal for internal syntax definitions to be mutually ;; recursive transformers, but it is an error for the expansion of a ;; syntax definition's initializer to require the result of another ;; initializer: ;; (let () ;; (define-syntax m1 (syntax-rules () ((m1) #f) ((m1 . args) (m2 . args)))) ;; (define-syntax m2 (syntax-rules () ((m2 arg . args) (m1 . args)))) ;; (m1 foo bar baz)) ;; => #f ;; (let () ;; (define-syntax simple-transformer ;; (syntax-rules () ;; ((simple-transformer pattern template) ;; (syntax-rules () (pattern template))))) ;; (define-syntax m (simple-transformer (m x) (- x))) ;; (m 1)) ;; => error ("Premature use of keyword bound by an internal define-syntax") ;; (let () ;; (define-syntax simple-transformer ;; (syntax-rules () ;; ((simple-transformer pattern template) ;; (syntax-rules () (pattern template))))) ;; (let () ;; (define-syntax m (simple-transformer (m x) (- x))) ;; (m 1))) ;; => -1 ;; Top-level macro blocks. ;; At the top level, if a macro block (i.e., a let-syntax or ;; letrec-syntax form) has only one body element, or if all of the ;; body elements before the last one are internal syntax definitions, ;; then the last body element need not be an expression (as would be ;; required in r5rs). Instead, it may be anything allowed at top ;; level: an expression, a definition, a begin sequence of top-level ;; forms, or another macro block containing a top-level form. ;; (let-syntax ((- quote)) ;; (define x (- 1))) ;; ;; (list x (- 1)) ;; => (1 -1) ;; Note that, unlike the similar extension in Chez scheme 6.0, this is ;; still r5rs-compatible, because we only treat definitions within the ;; last body element as top-level definitions (and r5rs does not allow ;; internal definitions within a body's last element, even if it is a ;; begin form): ;; (define x 1) ;; (define (f) x) ;; (let-syntax () ;; (define x 2) ;; (f)) ;; => 1, in r5rs and alexpander, but 2 in Chez scheme ;; (define x 1) ;; (define (f) x) ;; (let-syntax () ;; (begin ;; (define x 2) ;; (f))) ;; => 2, in alexpander and in Chez scheme, but an error in r5rs. ;; Syntax-rules ellipsis ;; Per SRFI-46, syntax-rules transformers can specify the ;; identifier to be used as the ellipsis (such a specification is ;; treated as a hygienic binding), and a list pattern may contain ;; subpatterns after an ellipsis as well as before it: ;; ---> (syntax-rules (*) *) ;; | (syntax-rules (*) *) ;; ;; ---> (