Hello again.
I have been thinking about how to implement the syntactic tower in a simple but correct way. What I have come up with is this: In a module, there are different environments, one for each different phase of evaluation (runtime, macro expansion time, macro macro expansion time and so on). (This is not a new invention in any way. I just hope that I have copied the concepts correctly.)
If you write normal code with no macros, only environment with phase 0 is into play. You get into the next phase in macro definitions or by using the syntax-begin form:
(import srfi-1)
(syntax-begin (import srfi-13))
(define (a-function) ;; This is inside environment phase 0. ;; Things from srfi-1 are available, but not things from srfi-13. fold)
(define-macro (a-macro) ;; Because this is macro definition, this is inside environment phase 1. ;; Things from srfi-13 are available, but not things from srfi-1
(define-macro (an-inner-macro) ;; This is inside environment phase 2. ;; Neither srfi-1 nor srfi-13 are imported in this environment. "hello world")
(string-titlecase (an-inner-macro)))
The module system's runtime functions (for instance expand-macro and syntax-rules) are available at the REPL and at all environments whose phase >= 1. It's possible to use the module system's runtime in modules' functions, but then you have to explicitly import the module system.
This is to make it clear that unless explicitly noted, compiled code is not dependent on the module system. This also makes it easier to tell which modules need to be loaded when compiling a module.
Does this make sense? Or am I trying to solve a non-problem? Is this overly difficult to understand?
/Per
Afficher les réponses par date
On 30-Mar-09, at 6:10 AM, Per Eckerdal wrote:
Does this make sense? Or am I trying to solve a non-problem? Is this overly difficult to understand?
No, it makes perfect sense (to me).
We can argue over the name (syntax-begin, begin-syntax, for-syntax, meta, ...), syntax (what is allowed inside the form?) and scope. But basically such a mechanism is necessary to distinguish the run time environment and the syntactic environment(s).
I assume that
(syntax-begin (syntax-begin (define (foo) ...)))
would define foo in the environment of the syntactic part of the syntactic part of the run time environment.
Possible problems I see at the semantic level are
1) The global variables are shared. Global variable X in the syntax environment is the same variable as global variable X in the run time environment. So in the interpreter, if you load a file containing
(syntax-begin (require srfi-1))
then all the procedures defined in srfi-1 will persist. They will be available to subsequently loaded files, and the REPL. However they are only available with a fully qualified name (srfi-1#append!).
2) This could be "fixed" so that each level of the tower has its own set of global variables, but I am worried about the cost of duplicating many variables (to be consistent all the Gambit predefined variables would have to be duplicated). Also I'm not sure this would be right semantically. Perhaps each module should have its own syntax environment, in other words it is not a single tower but a set of towers (*not* a tree). This is the purest model that ensures that something defined for syntax in one module is not available to the syntactic part of another module.
Marc
On Mar 30, 2009, at 8:45 AM, Marc Feeley wrote:
On 30-Mar-09, at 6:10 AM, Per Eckerdal wrote:
Does this make sense? Or am I trying to solve a non-problem? Is this overly difficult to understand?
No, it makes perfect sense (to me).
We can argue over the name (syntax-begin, begin-syntax, for-syntax, meta, ...), syntax (what is allowed inside the form?) and scope. But basically such a mechanism is necessary to distinguish the run time environment and the syntactic environment(s).
Just to throw this in there:
The way Scheme48 does it is it has a special form in the module definition to import other modules for the syntax environment. It's my understand this limits you to only import complete modules (not arbitrary code) for the current module's syntax environment. It would look like this:
(module foo (imports bar baz) (for-syntax qux mumble))
The IMPORTS statement does the usual. FOR-SYNTAX imports the `qux' and `mumble' modules for foo's syntactic environment. The syntactic tower comes in to play if qux or mumble imports other packages for their syntactic environment.
This seems less arbitrary and might make it easier to implement.
On the same note, Per, you mentioned not being satisfied with the syntax of your module definitions. It does get complex when you support renaming and other advanced features. Scheme48 has a really syntax good for doing all sorts of cool things when importing modules. You should take a peek at it if you want something different.
- James
30 mar 2009, at 18.08 James Long wrote:
The way Scheme48 does it is it has a special form in the module definition to import other modules for the syntax environment. It's my understand this limits you to only import complete modules (not arbitrary code) for the current module's syntax environment. It would look like this:
(module foo (imports bar baz) (for-syntax qux mumble))
The IMPORTS statement does the usual. FOR-SYNTAX imports the `qux' and `mumble' modules for foo's syntactic environment. The syntactic tower comes in to play if qux or mumble imports other packages for their syntactic environment.
This seems less arbitrary and might make it easier to implement.
Even without imports, a notion of syntactic tower is useful; it arises when defining macros inside definitions of macros.
Another small note: Black hole assumes a 1:1 mapping of modules to files, while Scheme48 doesn't. This would probably make a pure FOR- SYNTAX style implementation of the concept rather clunky from time to time, compared to doing the same thing in Scheme48. It might become very cumbersome to do macros only in the REPL, because you would be forced to create a module file for utilities, or to temporarily embed those functions inside the macro definition.
But of course, there is little actual difference in power, and it's definitely easier to define and to understand. Maybe it's worth it.
On the same note, Per, you mentioned not being satisfied with the syntax of your module definitions. It does get complex when you support renaming and other advanced features. Scheme48 has a really syntax good for doing all sorts of cool things when importing modules. You should take a peek at it if you want something different.
Interesting. I hadn't looked at Scheme48's module system. One thing in particular that I hadn't thought of is that it's possible to allow for macro expansions even inside import forms.
/Per
30 mar 2009 kl. 14.45 skrev Marc Feeley:
We can argue over the name (syntax-begin, begin-syntax, for-syntax, meta, ...),
Indeed. I'm not quite content with the name syntax-begin, it just doesn't feel elegant. But at this stage of development I felt it was more important to get a proof-of-concept out than having the perfect name. I picked it because it seems like that name is rather unique, and a long name is ok since it isn't used all too often.
syntax (what is allowed inside the form?)
In the current implementation (if I understand the code correctly): Anything that's allowed in the REPL is allowed inside syntax-begin. Right now it's implemented simply with eval and some toying around with the hygiene environment. I haven't really spent the time to think what this actually means to what is allowed.
I chose the name syntax-begin because I made the semantics to resemble that of begin: (syntax-begin (+ 3 3) (+ 2 2)) macro-expands to 4.
Possible problems I see at the semantic level are
- The global variables are shared. Global variable X in the syntax
environment is the same variable as global variable X in the run time environment. So in the interpreter, if you load a file containing
(syntax-begin (require srfi-1))
then all the procedures defined in srfi-1 will persist. They will be available to subsequently loaded files, and the REPL. However they are only available with a fully qualified name (srfi-1#append!). 2) This could be "fixed" so that each level of the tower has its own set of global variables, but I am worried about the cost of duplicating many variables (to be consistent all the Gambit predefined variables would have to be duplicated).
Hmm.. Yes. Could you give a more concrete example where the problem would arise? It seems PLT's module system does things to avoid this kind of problems, but I haven't fully understood when they arise in practise.
Also I'm not sure this would be right semantically. Perhaps each module should have its own syntax environment, in other words it is not a single tower but a set of towers (*not* a tree). This is the purest model that ensures that something defined for syntax in one module is not available to the syntactic part of another module.
I'm not sure I understand what you mean by syntax environment. Do you mean a set of global variables, or just a set of bindings to globals?
In the current black hole implementation every module (and the REPL) has its own syntax environment in the weaker sense that they have their own namespace. You'll need to pull some bug fixes I did today if you want to try it out.
/Per
On 30-Mar-09, at 8:45 AM, Marc Feeley wrote:
- This could be "fixed" so that each level of the tower has its own
set of global variables, but I am worried about the cost of duplicating many variables (to be consistent all the Gambit predefined variables would have to be duplicated). Also I'm not sure this would be right semantically. Perhaps each module should have its own syntax environment, in other words it is not a single tower but a set of towers (*not* a tree). This is the purest model that ensures that something defined for syntax in one module is not available to the syntactic part of another module.
I've been looking into this some more. Let me just explain what I mean by "separate set of global variables".
I will use the notation Xi to denote instance i of module X. In a model with a syntactic tower, i is an integer "level" starting with i=0 for the run time level, and i=1 for its syntactic expansion level, etc.
Assume we have modules A and B like this:
;;; module A
(import B) (init-v 11)
(syntax-begin (import B) (init-v 22))
(define-macro (foo) (let ((z (* v 10))) `(cons ,z ,z)))
;;; module B
(define v #f)
(define (init-v x) (set! v x) (pp v))
Note that A requires B both for run time and expansion time. In a model with a syntactic tower there are two instances of B, that is B0 (run time) and B1 (expansion time). What is the relationship between v from B0 and v from B1 (let's call them B0.v and B1.v)? I feel that there should be no interaction between levels, except the macro expander acts as a bridge between levels. So B0.v and B1.v should be distinct variables.
Do we all agree on this?
There will be a substantial run time cost to implement this because each instance of a module is basically a closure, and thus there will be an additional indirection to access global variables.
Marc
On Thu, Apr 2, 2009 at 8:33 AM, Marc Feeley feeley@iro.umontreal.ca wrote:
Note that A requires B both for run time and expansion time. In a model with a syntactic tower there are two instances of B, that is B0 (run time) and B1 (expansion time). What is the relationship between v from B0 and v from B1 (let's call them B0.v and B1.v)? I feel that there should be no interaction between levels, except the macro expander acts as a bridge between levels. So B0.v and B1.v should be distinct variables.
Do we all agree on this?
Yep, I agree.
There will be a substantial run time cost to implement this because each instance of a module is basically a closure, and thus there will be an additional indirection to access global variables.
I'm assuming you mean "run-time" of the compiler. You could, of course, compile all this out. But this might make the compilation stage take longer.
If you wanted to keep all the symbols in a flat list for efficiency, what about mangling names of identifiers in syntactic environments? It seems that you would know which level of the syntactic tower you are at when you evaluate a piece of code. You could suffix the level to an identifier, so B1.v would become B1.v-1.
(I hope this message doesn't go through multiple times, having troubles with my mail client)
- James
On 2-Apr-09, at 12:23 PM, James Long wrote:
On Thu, Apr 2, 2009 at 8:33 AM, Marc Feeley feeley@iro.umontreal.ca wrote:
Note that A requires B both for run time and expansion time. In a model with a syntactic tower there are two instances of B, that is B0 (run time) and B1 (expansion time). What is the relationship between v from B0 and v from B1 (let's call them B0.v and B1.v)? I feel that there should be no interaction between levels, except the macro expander acts as a bridge between levels. So B0.v and B1.v should be distinct variables.
Do we all agree on this?
Yep, I agree.
There will be a substantial run time cost to implement this because each instance of a module is basically a closure, and thus there will be an additional indirection to access global variables.
I'm assuming you mean "run-time" of the compiler.
No I mean run time of the program.
You could, of course, compile all this out. But this might make the compilation stage take longer.
If you wanted to keep all the symbols in a flat list for efficiency, what about mangling names of identifiers in syntactic environments? It seems that you would know which level of the syntactic tower you are at when you evaluate a piece of code. You could suffix the level to an identifier, so B1.v would become B1.v-1.
To compile it out you'd need the compiler to generate an object file (or .c/.o file) for every possible value of i. So module B.scm would generate B0.o1, B1.o1, B2.o1, etc (obviously in a lazy way for above a certain level) and the system would load the one appropriate for a particular level. However this would be very wasteful since the code would be duplicated. This is akin to implementing closures like this:
;;; source code (define (f x) (lambda (y) (+ y (* x y)))) (define a (f 11)) (define b (f 22)) (define c (f 33))
;;; generated code (define (f x) (lambda (y) (+ y (* x y)))) (define a (lambda (y) (+ y (* 11 y)))) (define b (lambda (y) (+ y (* 22 y)))) (define c (lambda (y) (+ y (* 33 y))))
Of course in the case of modules the "code" part of the "closure" is much larger than in the above example.
So a more space efficient approach is to add to each functional object (closure, primitive or return address) a pointer to the "global environment" of that module. When a module is "loaded" (in other words instantiated) a new global environment would be allocated, and all of its functional objects would be created and setup with a pointer to that instance's global environment. At run time an additional indirection would be required to get to the content of a module's global variables. Moreover, there is an overhead when calling functions because the "module environment" of the target function has to be read.
Marc
This is akin to implementing closures like this:
;;; source code (define (f x) (lambda (y) (+ y (* x y)))) (define a (f 11)) (define b (f 22)) (define c (f 33))
;;; generated code (define (f x) (lambda (y) (+ y (* x y)))) (define a (lambda (y) (+ y (* 11 y)))) (define b (lambda (y) (+ y (* 22 y)))) (define c (lambda (y) (+ y (* 33 y))))
Of course in the case of modules the "code" part of the "closure" is much larger than in the above example.
So a more space efficient approach is to add to each functional object (closure, primitive or return address) a pointer to the "global environment" of that module. When a module is "loaded" (in other words instantiated) a new global environment would be allocated, and all of its functional objects would be created and setup with a pointer to that instance's global environment. At run time an additional indirection would be required to get to the content of a module's global variables. Moreover, there is an overhead when calling functions because the "module environment" of the target function has to be read.
I see what you mean, but I was hoping that after all of the macro expansion is finished, we could forego that step of indirection. I'll have to think more about this though, but I'm willing to sacrifice correctness for efficiency if that helps.
On 2-Apr-09, at 2:46 PM, James Long wrote:
I see what you mean, but I was hoping that after all of the macro expansion is finished, we could forego that step of indirection. I'll have to think more about this though, but I'm willing to sacrifice correctness for efficiency if that helps.
Similarly to closures, you have to think about it like this for module instances:
When code is executed in a module, it has to know which module instance is executing so that it can tell which location is referred to when accessing a given module global variable. In other words, the module instance is a parameter of the module's code.
Marc
To compile it out you'd need the compiler to generate an object file (or .c/.o file) for every possible value of i. So module B.scm would generate B0.o1, B1.o1, B2.o1, etc (obviously in a lazy way for above a certain level) and the system would load the one appropriate for a particular level. However this would be very wasteful since the code would be duplicated.
Lately I have been working on some tools in black hole for batch compilation, that is, compiling several modules into one shared library file. For that I use the ##load-object-file procedure you sent a mail to this list about earlier. Now my French isn't the very best, but as far as I understand it from your description, this function allows the user to choose when to initialize the module by providing a function to call that initializes the module.
Also, it provides some facilities to see the globals that are not bound. Is it possible to hack something here? I'm thinking adding some options to how those unbound globals are resolved.
And another thing: It should be very doable to reduce this problem to two levels: Run-time and compilation.
When compiling, it seems safest to have a fresh initialization of every used module, and to do this once for each compiled file. And, when compiling, the "higher" levels (the ones with high numbers) are always processed strictly before the levels below. This means that for compilation, only one set of globals is needed at any time, because all modules can just be re-initialized and overwrite the levels above. Is this correct? (This solution obviously kills thread safety, but is that really a problem?)
This leads me to think that this isn't such a great problem after all, because when the problem is reduced to this point, one "solution" could simply be to say that compile-time code is always interpreted. With that limitation, it's easy to give all compile-time instances of modules a separate namespace from the run-time instances, because the code is re-loaded and hygienified (which is where namespaces are chosen) every time anyways.
Loading interpreted code is significantly slower than loading compiled code, but in practise I find that macros rarely use very many libraries. Obviously it would be even cooler to have real compiled macros, but I think it's not as important as having a correct and working solution.
This interpreted "solution" probably doesn't extend to the Gambit base libraries though. But is it really needed to have multiple instances of them? They don't have much global state do they?
/Per
This leads me to think that this isn't such a great problem after all, because when the problem is reduced to this point, one "solution" could simply be to say that compile-time code is always interpreted. With that limitation, it's easy to give all compile- time instances of modules a separate namespace from the run-time instances, because the code is re-loaded and hygienified (which is where namespaces are chosen) every time anyways.
Loading interpreted code is significantly slower than loading compiled code, but in practise I find that macros rarely use very many libraries. Obviously it would be even cooler to have real compiled macros, but I think it's not as important as having a correct and working solution.
Hmm.. When thinking about this some more, maybe pure interpretation isn't such a great solution after all. I can imagine a couple of cases where this would assume something similar to an exponential behavior (I haven't thought about this very closely).
It might be possible to work around that by caching half-compiled (that is, fully macro-expanded) code. This would benefit performance for other situations as well, in particular interactive development where the interpreter's debugging features are desired. I wonder if this can be done completely transparently to the user or if it's too complex to be a good solution.
But I still don't see any error in the main point of my previous mail, that is that only two different sets of globals are needed.
/Per
(Sorry for double post, Marc)
gambit-modules-list@iro.umontreal.ca
-
James Long -
James Long -
Marc Feeley -
Per Eckerdal