Discussion about how module-system, macro-expansion, memoization and evaluation interact, and how this could be done in the future. ==================================================================== Version: $Id: evaluation.txt,v 1.1 2002/06/13 22:52:27 dirk Exp $ 1. Background: -------------- The evaluation of scheme code can in principle be subdivided in several, somewhat independent subtasks: * Macro expansion performs syntactic transformations on the original code, delivering scheme code which only contains a limited set of built-in syntactic forms. Inputs are the original scheme code and the set of top-level bindings. * Memoization (or compilation) transforms the already macro-expanded scheme code into an execution friendly format. This can be machine code, bytecode for a virtual machine or something more abstract. * Execution finally runs the memoized code. 2. Current solution in Guile: ----------------------------- In Guile, two different implementations are available: * As long as the user does not explicitly (using 'use-syntax) activate a syntax-transformer, macro expansion using the built-in transformer for "acros, macros and mmacros", memoization and execution are performed together in the function eval.c:SCM_EVAL. * After a syntax-tranformer is selected, macro expansion of those macros, which are defined using that syntax-transformer, is actually performed as a separate subtask. The expansion of the the remaining "acros, macros and mmacros" as well as memoization and execution are still performed together in the function eval.c:SCM_EVAL. The fact, that eval.c:SCM_EVAL has to deal with all three (macro expansion, memoization and execution) leads to a couple of problems. 2.1 Use of syntax transformers with Guile ----------------------------------------- For each module in Guile an individual syntax transformer can be specified using 'use-syntax. If an expression is evaluated using 'eval while some module x is the current module, the expression will first be processed by the syntax transformer function associated with module x. This transformation using the syntax transformer function is the very first step performed when an expression is evaluated. After the syntax transformer function has been applied to some expression, there may only be those syntactic forms remaining in the code that are to be processed by Guile's built-in syntax transformer for "acros, macros and mmacros" described below. Since giving a syntax transformer using 'use-syntax is optional, the resulting expression after applying a syntax transformer may still contain all R5RS macros, since these are defined using Guile's "acros, macros and mmacros". Moreover, all module system macros and a couple of other macros may be contained in the output expression generated by the syntax transformer. 2.2 Guile's built-in syntax transformer for "acros, macros and mmacros" ----------------------------------------------------------------------- Guile's built in syntax transformer distinguishes three different kinds of macros, named as follows: * acro, also referenced as type 0 macros, created by scm_makacro from C, by procedure->syntax from scheme. * macro, also referenced as type 1 macros, created by scm_makmacro from C, by procedure->macro from scheme. * mmacro, also referenced as type 1 macros, created by scm_makmmacro from C, by procedure->memoizing-macro from scheme. All three functions procedure->syntax, procedure->macro and procedure->memoizing-macro take exactly one argument, namely a scheme function that takes two arguments. They all return an object that satisfies the SCM_MACROP predicate. The macro type of a macro object is delivered by the macro SCM_MACRO_TYPE. The scheme function that was given as the argument to procedure->syntax, procedure->macro or procedure->memoizing-macro can be retrieved by the macro SCM_MACRO_CODE. We will refer to the function given at the creation of the acro (macro, mmacro) as to the acro (macro, mmacro) function. It is possible to create acro, macro and mmacro objects dynamically. The evaluator handles the acro, macro and mmacro objects specially: If the evaluator has to evaluate an expression (proc args ...) where proc evaluates to an acro, macro or mmacro, the following is done: * acro: The acro function is evaluated with the current environment as the first argument, and the expression (proc args ...) as the second argument. Whatever the acro function returns is returned as the result of the expression (proc args ...). In this respect acros are not actually syntax transformers: They don't transform scheme code into different scheme code. Rather, they transform scheme code immediately into a result. * macro: The macro function is evaluated with the current environment as the first argument, and the expression (proc args ...) as the second argument. The macro function will transform the expression (proc args ....) into a new scheme expression and return the new expression as its result. Then, the transformed expression will be evaluated by the evaluator. The result of the evaluation of the new expression is then returned. The new expression itself is not used any more. That is, the transformation done by the macro function will have to be performed every time the evaluator runs over the original expression, since the transformed code is not stored. * mmacro: The mmacro function is evaluated with the current environment as the first argument, and the expression (proc args ...) as the second argument. The mmacro function will transform the expression (proc args ...) into a new scheme expression and return the new expression as its result. The evaluator will take the new expression and replace the original code with the result. Then, the new expression is evaluated. As has been said, acros are not actually syntax transformers. However, also macros and mmacros are not only syntax transformers in the strict sense, since they are not required to return scheme code, but may also return 'memoized' code, which is tailored to the evaluator. That is, Guile's mechanism of using acros, macros and mmacros is used dynamically during the evaluation of the code. The following example demonstrates some aspects of the behaviour of Guile's built-in syntax transformer. The form 'defmacro, btw., introduces a mmacro. (define (foo x) (if x (bar) (bar))) (defmacro bar () ''first) (foo #t) --> first (defmacro bar () ''second) (foo #t) --> first (foo #f) --> second (foo #t) --> first We see that macro expansion happens during evaluation. Otherwise, if expansion was done after 'read, the references to 'bar in the definition of 'foo would not be expanded: 'bar is not known to be a macro at the time when 'foo is defined. Second, we see that, once the code has been evaluated and the mmacro function has been executed, the transformed code is memoized. Otherwise the second execution of (foo #t) would have resulted in 'second. This also shows that there appears no re-compilation in case of a redefinition of a mmacro. Third, we see that macro expansion is only done in those paths which are actually executed. Otherwise after the first execution of (foo #t) _all_ references to 'bar would have been replaced by 'first. Summarized: Guile's built-in mechanism of acros, macros and mmacros performs tasks related to macro expansion and memoization. Acros, macros and mmacros can be defined dynamically. The corresponding acro, macro and mmacro functions are executed dynamically depending on the execution paths (in contrast to statically depending on the syntax). 2.3 Guile's memoized code ------------------------- As has been described before, guile mixes parts of syntax transformation together with memoization/compilation and execution. More explicitly, the memoization as well as the internally defined acros, macros and mmacros modify parts of the code on the fly. Before, the code is given in the form that is provided by the reader or as it is delivered by a potential syntax transformer. That is, it is stored as an ordinary scheme object or lists representing the code. During evaluation the code will be modified by introducing special objects into the code and by re-organizing some of the code structure to speed up execution. The memoized code will differ from the original input in the following ways: * Symbols that represent a variable with a binding in some module, are replaced in the code with a "variable", which is an object that directly points to the memory location associated with the variable. For example, the expression '(foo 1 2 3)' is, after reading it, represented as a list with the symbol 'foo at the first position. If the expression is evaluated in a module where a binding for 'foo is present, the expression will be changed to '( 1 2 3'. Accessing the variable in the memoized code is very fast. * If a symbol is detected that represents a local variable, that symbol is replaced with an ILOC object. An ILOC object is a special object indicating how the corresponding location in the local environment can be found. This is done using two numbers: The first number indicates, how many environment frames outside of the current one the binding is defined, the second number indicates the index of the variable in that environment frame. For both numbers there is a maximum that can be represented in an ILOC object. [FIXME: What happens if that maximum is exceeded? Have to check. Assumption: In such a case no memoization is done.] For example: The expression '(a b c)' as it occurs in the code '(let ((a 0)) (let ((b 1) (c 2)) (a b c)))' will after memoizatin be transformed into '( )', because the value of a will be found by stepping out of one environment frame and taking the first element of that frame. The value of c will be found by looking into the current environment frame and taking the second element of that frame. Accessing the variable in the memoized code requires to step along the list of environment frames, and then to step along the list of elements of that frame. This is directly related to the way Guile represents environments. [although I can't yet think of a better way] * Symbols that represent acros, macros and mmacros are, in the first step, treated like the two cases above. That is, '(and #t #f) is replaced by '( #t #f). Then, after the memoization is performed and the memoized expression is to be executed, Guile looks into the content of the variable (or ILOC). There it detects the acro, macro or mmacro object. The expression is passed to the It should be noted, that the order in which memoization happens makes sure that in an expression '(a b c d) first 'a is memoized, then it is checked for being a acro/macro/mmacro, then the corresponding acro/macro/mmacro function is executed. In case of a mmacro, the original expression is replace. In case of a macro/mmacro the resulting code then is evaluated again. That is, 'b 'c 'd from the above expression will only be memoized if all outer macro transformations have already been performed. * As has been stated already, Guile's built in mmacros deliver not just scheme code, but they are closely merged into the memoization process and deliver already memoized code. A common pattern is, that the mmacro function for a mmacro like 'and will replace the code in the following way: (begin x y z) will in the first step, as described above, become: ( x y z). When the evaluator comes to the application phase, it will look into the contents of the variable and will see that it holds a mmacro. The mmacro functions replaces the code by (#@begin x y z), where #@begin is a special object only known to the evaluator. Then, the resulting code is evaluated. Now, the evaluator does not have to do any macro expansion for this occurence of 'and again. Rather, since it knows about #@begin, it immediately knows how to treat the sequence of x y z. A similar mechanism as with 'and is performed with a lot of other built-in mmacros, like 'quote, 'begin, 'if, 'set, 'case, 'cond, ... Replacing the original code by the memoized code as in these examples allows the evaluator to distinguish between code, for which syntax expansion already has happened, and code, for which a macro expansion may still be necessary. Some mmacros go a little bit further when replacing the original form. The mmacro for 'and for example replaces the code in the following way: '(and x y z) becomes (#@and x y z), but '(and) becomes #t. In a similar way, a use of the syntactic form 'or is replaced. Other macros do some re-organization of the code. The syntactic form 'do for example is most radically altered: (do (( ) ( ) ... ) ( ) ) is transformed by the mmacro function into (#@do ( ... ) ( ... ) ( ) () ... ) ;; missing steps replaced by var which avoids to do some re-ordering during execution. Despite this number of transformations that are performed during transformation, the memoized code is not fully checked for syntax errors. The empty combination '() may, for example, still occur illegally in the memoized code. Further, a lot of other static information that can be obtained easily is not made use of. Constant expressions that occur in places where only side-effecting operations are relevant are not removed from the code. Redundant nestings of 'begin forms are not simplified. In other words, even a couple of code optimizations that could be applied without changing the format of memoized code are not yet performed. 3. Incremental changes for improving the evaluator ================================================== * [According to Marius, the following step should be performed first:] revoke macro transformers from being stored in variables. I.e. (define-macro (foo ...) ...) (define bar foo) will no longer work. Instead, put macros into the toplevel by binding them directly to a symbol. We now have (module lookup) (variable-ref) symbol ------> variable ------> # but should have (module lookup) symbol ------> # [I don't understand why not storing macro transformers in variables should be helpful. What would we gain if this was performed as a first step? By looking at the code, I could not see which particular problem would be solved by this step, nor which further step would be simplified: If macro expansion was performed before execution, macros won't appear as first class objects any more during execution anyway. What am I missing here? Maybe Marius has a special implementation of memoization/compilation in mind that I don't currently see...] * [According to Marius, the next step should be:] Make syntax-case use this arrangement, and make it work correctly with modules in general. [I think Marius refers to the following requirement about macros: If a macro introduces identifiers, their bindings have to come from the environment where the macro was defined. That is, somehow the relationship between the macro and its environment has to be retained.] * Separating memoization/compilation and execution. Instead of doing memoization combined with execution, these two issues should be separated. That is, after reading an expression, the code is first transformed by the syntax transformer (if one is given). Then, the resulting code is processed by a memoization phase. In this phase, all remaining syntax checks and transformations are performed. The result of this phase is the memoized code that is run by the executor. Problems: There are a couple of problems that have to be addressed when this step is to be performed: First, some existing code will break, namely code that provides macro definitions late. Second, code that dynamically creates acros, macros and mmacros may break. Third, "macros" won't work at all any more. In general, code that makes use of guile's built-in system to create acros, macros and mmacros may have problems. 4. Architectural Aspects ======================== Data structures relevant for evaluation: * input code - This is the interface between the reader, the syntax transformer, the memoizer/compiler and the debugger. Input code is delivered as the output of the reader and processed by the syntax transformer. Given that we always want to be able to identifiy the relationship of the currently executed code to the originial input code, the syntax transformer as well as the memoizer/compiler will have to preserve the relationship. The debugger finally will have to be able to use the relationship to show debugging information to the user. * code after syntax transformation - This is the interface between the syntax transformer and the memoizer/compiler. Except for a limited set of built-in syntactic forms understood by the memoizer/compiler, all macro uses will be expanded. * code after memoization - This is the interface between the memoizer/compiler and the executor. There should also be some way to store memoized/compiled code and read it in later. The format of the memoized code may also influence the layout of the stack/continuation data structure as well as the layout of the local environment data structure. * stack/continuation - This is an interface between the executor and the debugger. In a 'stackless' execution model, scheme stacks and continuations will probably be quite similar data structures, if not even identical. * functions, closures, ... - This is an interface between the executor and a lot of other parts of guile. The creation of functions and closures is part of guile's API. The set of different possible function types influences the design of the executor. * top level environments - These are used during syntax transformation, memoization/compilation, execution and debugging. * local environments - These are used within the executor. There may also be a need to examine them from the debugger. * debug information (breakpoints, trace points etc.) - This is an interface between the executor and the debugger.