Hello. Scheme interpreter is starting look like its going to do some serious stuff in the near future, or maybe I am just too enthusiastic about it. What we have now: - We can execute simple expressions like: (+ 1 2 1.3 -2) Nested ones also works. - (define <var> <value>) works with a given context, so: (define var 2) (+ var 40) => 42 - Conditional (if <cond> <then> <else>) seem to work fine, <else> is not arbitrary. pypy/lang/scheme/test/test_eval.py Gives you the best overview. What will be done in the nearest future: - comparison primitives: = < > eq? eqv? - (cons <car> <cdr>) (car <pair>) (cdr <pair>) so we can play with lists. That kind of stuff. You can take a look at: pypy/lang/scheme/TODO.txt Will postpone quotations and symbols implementation for a while. I have to think about it, how much of it is parsing matter. Then i would like to work on (lambda ...). This will probably take some time to think again execution context, make a hard distinction between procedures and macros and a lot of stuff, that I don't even dare to think about now :-). Before EP I would like to make lambdas work and also have some tuning done (whatever it means), so on the sprint we could focus on really interesting stuff instead of refactoring and bug fixes. I would like to refine what I would like to do during the sprint, but not sure right now. Any ideas, what would be worth trying then? Cheers, Jakub Gustak
Hi Jakub (sorry for mis-spelling your name last time)! 2007/6/29, Jakub Gustak <jgustak@gmail.com>:
All sounds good!
I would do cons, car, cdr first (they should be easy anyway).
A lof of it is a matter of parsing, yes. I can help you there, if you want me to.
Simple lambdas should be kind of easy, I would hope.
Good things to do on the sprint are things were you need the help of other PyPy people. Two ideas: - thinking about how to implement call/cc with the primitives stackless provides - making the interpreter rpython Cheers, Carl Friedrich
Hello. What we have done on scheme interpreter: Working lambdas, with closures almost as described in r5rs. What we miss here is proper tail-recursion and issues, when lambda is called with wrong number of arguments (though should be simple to add). Some rethinking on ExecutionContext. Now we have global and local scope (looks like python). When copying ExecutionContext only local scope is copied, global one is shared. What more, copied ExecutionContext cannot bound new variables in global scope, though it can set new values to existing ones. Done quotations both as (quote <obj>) and as '<obj>. After all it looks like distinction between W_Identifier and W_Symbol is useless. So probably only one of them will live in the future. Also implemented parsing for dotted lists (needed for lambdas definition). cons, car, cdr were easy ones. Probably not much hacking before the sprint. So the plan for EP sprint is RPython. I would like also to discuss some other features, if time will let us. See you soon on #pypy or on EP. Cheers, Jakub
What's on with scheme interpreter: Nice progress during post EuroPython sprint, see: http://codespeak.net/pipermail/pypy-dev/2007q3/003919.html And after the sprint: (define (fun <args>) <body>) syntactic sugar added to lambda definitions. (begin ...), (letrec ...) added. This leads to small changes in ExecutionContext (set-car! <pair>), (set-cdr! <pair>) added. Careful, it is possible to create circural list, and crash interpreter when it will try to display such list. Added quasi-quotations. Code is not so straightforward. Maybe it can be done differently. W_Identifier and W_Symbol are now W_Symbol. All symbols are created by symbol(name) function, which stores all symbols in global W_Symbol.obarray dictionary or returns existing one. It makes comparing symbols trivial. Next step is to implement macros. There was also plan to move some some of the syntax checking to parser: e.g. (if test then else) to get parsed directly to MacroIf(test, then, else). The problem is, that this syntax can change in scheme on runtime: e.g. (define if #t) so it doesn't make much sense. And later adding main primitive procedures will make scheme interpreter quite usable. Cheers, Jakub
Next step is to implement macros.
We have working simple macros. They are hygienic and referentially transparent. There is no <ellipsis> support so you can't use (expr ...) syntax yet. There is also no support for recursive expanding also. There was again some ExecutionContext refactoring. Still only (let ...) and (let* ...) are fully compatible with macro expanding. (letrec ...) is not. In the future: more macros! (ellipsis, recursive expanding and CPS style macros) Cheers, Jakub Gustak
Some more info.
We have working simple macros. They are hygienic and referentially transparent.
r5rs states that if macro introduces new binding, it should be renamed to avoid conflicts with other identifiers. In our case we create syntactic closure like described in: http://people.csail.mit.edu/people/jhbrown/scheme/macroslides04.pdf ExecutionContext.sput() (creating new binding) checks if it deals with syntactic closure or not, and depending on that binds location in proper context. W_Transformer can be called with quoted expression as argument, then appropriate template will expand and then expanded expression will be evaluated. This way of evaluation will surely cause problems with recursive macros, so it is not recommended. __ Jakub
A first, a joke: (syntax-rules () ((i-have-spare day ...) (hack 'macros (day ....)))) So we have recursive macros expanding recursively, as they should. I was working on macros with ellipsis almost whole week i. I was changing approach several times. But it looks like flat ellipses (not nested) work well. All most important parts of macros are SyntaxRule.match method, or rather matchr, and W_Transformer.substitute. They raise exception when discover ellipsis to handle it at higher level. matchr is kinda handling nested ellipses, but substitute not yet. That's pretty it. I would like to get nested ellipses working and then start playing with continuations. Wish me luck. Cheers, Jakub Gustak
Macros looks like working. One thing to be added: they are acting like first-class objects, but should not. Right now I am working on continuations. First a puzzle: What will return evaluation of s-expression like this: (call/cc call/cc) Or what will be bound to k after this s-expression: (define k (call/cc call/cc)) After some asking on #pypy I decided to create own implementation of continuations, and not try to use stackless. The reason is that coroutines are one-shot. So I created execution stack simulation, or rather stack for continuation frames. Right now not every macro uses it, so not every one is continuation-safe. If macro has defined method continue_tr it should get along with continuations well. Another issue: this implementations is stack-only so it introduce lot of overhead both on capturing and throwing continuations. And one more: every W_Procedure is continuations-safe but VERY slow, even when no capture occurs. I'd rather would like to think about how to throw continuations more generally, and not have to implement continue_tr for every W_Callable, than implementing capture differently. Or maybe try totally different approach e.g write every call in CPS, but it probably would require way too much changes right now. Cheers, Jakub Gustak
This is last scheme status report during SoC. So I will sum things up in the end.
Macros looks like working. One thing to be added: they are acting like first-class objects, but should not.
Found a bug, when ellipsis matched zero objects, fized now. Scheme48 acts differently in some cases. On the other hand in this cases mzScheme works just as expected. In this meaning macros are evil. There is no explicit specification how they should behave in r5rs. They look like added to the specification in last minute. Continuations:
I made them a little faster by decreasing number of operations, but still for every non-tail-call a new instance of ContinuationFrame is created and is stored on stack. On every return it is popped form stack and forgotten. When no capture will happen, it is time and memory waste.
No progress in this direction. Still every W_Callable to be continuations friendly has to use eval_cf instead of eval and must implement continue_tr method.
Or maybe try totally different approach e.g write every call in CPS, but it probably would require way too much changes right now.
Nor here. Summarization: * Interactive interpreter (not RPythonic) lang/scheme/interactive.py * Can be translated using: translation/goal/targetscheme.py PyPy Scheme Interpreter features: * uses rpythonic packrat parser * every "syntax" definitions are implemented * quotations and quasi-quotations * delayed evaluation * proper tail-recursion * hygienic macros * partly working continuations (some macros are not continuations friendly yet). * no dynamic-wind procedure Known issues and "to be added": * lambda does not check if it is called with correct arguments number * macros are acting like first-class objects, though they shouldn't * missing input/output procedures * no support for chars, vectors * strings are supported, but no string-operations procedures * quite a few procedures are missing, but they can be easily added * no call-with-values and values * missing some "library syntax", can be defined using macros What's next? I will probably mysteriously disappear and became grave-digger or hermit. Never touch computer again and live happily ever after ;-). Cheers, Jakub Gustak
Hi Jakub, On Fri, Aug 17, 2007 at 02:35:20PM +0200, Jakub Gustak wrote:
This is last scheme status report during SoC. So I will sum things up in the end.
Thanks for the good work you did during the summer! The result looks good to me, even with the missing features, but we'd really need a Scheme guy to guide us from now on, if we want to make the interpreter more usable.
Indeed, the current approach allows impressive-looking tests to pass, but the code is quite verbose and inefficient. We can start thinking at some point about using the stackless and/or GC-based cloning operations of RPython as a more orthogonal alternative, but that's an involved topic.
If you do, then farewell! In the event that you're interested to continue, though (:-), here are in summary some possible future directions: * get some Scheme people interested in the project, try to run real Scheme projects * implement more of the missing features * think how to do continuations with stackless or GC-based cloning * also, we could try to integrate pypy/lang/scheme and pypy/interpreter in one of the many possible ways, to offer a combined Python+Scheme environment... A bientot, Armin.
Hi Jakub (sorry for mis-spelling your name last time)! 2007/6/29, Jakub Gustak <jgustak@gmail.com>:
All sounds good!
I would do cons, car, cdr first (they should be easy anyway).
A lof of it is a matter of parsing, yes. I can help you there, if you want me to.
Simple lambdas should be kind of easy, I would hope.
Good things to do on the sprint are things were you need the help of other PyPy people. Two ideas: - thinking about how to implement call/cc with the primitives stackless provides - making the interpreter rpython Cheers, Carl Friedrich
Hello. What we have done on scheme interpreter: Working lambdas, with closures almost as described in r5rs. What we miss here is proper tail-recursion and issues, when lambda is called with wrong number of arguments (though should be simple to add). Some rethinking on ExecutionContext. Now we have global and local scope (looks like python). When copying ExecutionContext only local scope is copied, global one is shared. What more, copied ExecutionContext cannot bound new variables in global scope, though it can set new values to existing ones. Done quotations both as (quote <obj>) and as '<obj>. After all it looks like distinction between W_Identifier and W_Symbol is useless. So probably only one of them will live in the future. Also implemented parsing for dotted lists (needed for lambdas definition). cons, car, cdr were easy ones. Probably not much hacking before the sprint. So the plan for EP sprint is RPython. I would like also to discuss some other features, if time will let us. See you soon on #pypy or on EP. Cheers, Jakub
What's on with scheme interpreter: Nice progress during post EuroPython sprint, see: http://codespeak.net/pipermail/pypy-dev/2007q3/003919.html And after the sprint: (define (fun <args>) <body>) syntactic sugar added to lambda definitions. (begin ...), (letrec ...) added. This leads to small changes in ExecutionContext (set-car! <pair>), (set-cdr! <pair>) added. Careful, it is possible to create circural list, and crash interpreter when it will try to display such list. Added quasi-quotations. Code is not so straightforward. Maybe it can be done differently. W_Identifier and W_Symbol are now W_Symbol. All symbols are created by symbol(name) function, which stores all symbols in global W_Symbol.obarray dictionary or returns existing one. It makes comparing symbols trivial. Next step is to implement macros. There was also plan to move some some of the syntax checking to parser: e.g. (if test then else) to get parsed directly to MacroIf(test, then, else). The problem is, that this syntax can change in scheme on runtime: e.g. (define if #t) so it doesn't make much sense. And later adding main primitive procedures will make scheme interpreter quite usable. Cheers, Jakub
Next step is to implement macros.
We have working simple macros. They are hygienic and referentially transparent. There is no <ellipsis> support so you can't use (expr ...) syntax yet. There is also no support for recursive expanding also. There was again some ExecutionContext refactoring. Still only (let ...) and (let* ...) are fully compatible with macro expanding. (letrec ...) is not. In the future: more macros! (ellipsis, recursive expanding and CPS style macros) Cheers, Jakub Gustak
Some more info.
We have working simple macros. They are hygienic and referentially transparent.
r5rs states that if macro introduces new binding, it should be renamed to avoid conflicts with other identifiers. In our case we create syntactic closure like described in: http://people.csail.mit.edu/people/jhbrown/scheme/macroslides04.pdf ExecutionContext.sput() (creating new binding) checks if it deals with syntactic closure or not, and depending on that binds location in proper context. W_Transformer can be called with quoted expression as argument, then appropriate template will expand and then expanded expression will be evaluated. This way of evaluation will surely cause problems with recursive macros, so it is not recommended. __ Jakub
A first, a joke: (syntax-rules () ((i-have-spare day ...) (hack 'macros (day ....)))) So we have recursive macros expanding recursively, as they should. I was working on macros with ellipsis almost whole week i. I was changing approach several times. But it looks like flat ellipses (not nested) work well. All most important parts of macros are SyntaxRule.match method, or rather matchr, and W_Transformer.substitute. They raise exception when discover ellipsis to handle it at higher level. matchr is kinda handling nested ellipses, but substitute not yet. That's pretty it. I would like to get nested ellipses working and then start playing with continuations. Wish me luck. Cheers, Jakub Gustak
Macros looks like working. One thing to be added: they are acting like first-class objects, but should not. Right now I am working on continuations. First a puzzle: What will return evaluation of s-expression like this: (call/cc call/cc) Or what will be bound to k after this s-expression: (define k (call/cc call/cc)) After some asking on #pypy I decided to create own implementation of continuations, and not try to use stackless. The reason is that coroutines are one-shot. So I created execution stack simulation, or rather stack for continuation frames. Right now not every macro uses it, so not every one is continuation-safe. If macro has defined method continue_tr it should get along with continuations well. Another issue: this implementations is stack-only so it introduce lot of overhead both on capturing and throwing continuations. And one more: every W_Procedure is continuations-safe but VERY slow, even when no capture occurs. I'd rather would like to think about how to throw continuations more generally, and not have to implement continue_tr for every W_Callable, than implementing capture differently. Or maybe try totally different approach e.g write every call in CPS, but it probably would require way too much changes right now. Cheers, Jakub Gustak
This is last scheme status report during SoC. So I will sum things up in the end.
Macros looks like working. One thing to be added: they are acting like first-class objects, but should not.
Found a bug, when ellipsis matched zero objects, fized now. Scheme48 acts differently in some cases. On the other hand in this cases mzScheme works just as expected. In this meaning macros are evil. There is no explicit specification how they should behave in r5rs. They look like added to the specification in last minute. Continuations:
I made them a little faster by decreasing number of operations, but still for every non-tail-call a new instance of ContinuationFrame is created and is stored on stack. On every return it is popped form stack and forgotten. When no capture will happen, it is time and memory waste.
No progress in this direction. Still every W_Callable to be continuations friendly has to use eval_cf instead of eval and must implement continue_tr method.
Or maybe try totally different approach e.g write every call in CPS, but it probably would require way too much changes right now.
Nor here. Summarization: * Interactive interpreter (not RPythonic) lang/scheme/interactive.py * Can be translated using: translation/goal/targetscheme.py PyPy Scheme Interpreter features: * uses rpythonic packrat parser * every "syntax" definitions are implemented * quotations and quasi-quotations * delayed evaluation * proper tail-recursion * hygienic macros * partly working continuations (some macros are not continuations friendly yet). * no dynamic-wind procedure Known issues and "to be added": * lambda does not check if it is called with correct arguments number * macros are acting like first-class objects, though they shouldn't * missing input/output procedures * no support for chars, vectors * strings are supported, but no string-operations procedures * quite a few procedures are missing, but they can be easily added * no call-with-values and values * missing some "library syntax", can be defined using macros What's next? I will probably mysteriously disappear and became grave-digger or hermit. Never touch computer again and live happily ever after ;-). Cheers, Jakub Gustak
Hi Jakub, On Fri, Aug 17, 2007 at 02:35:20PM +0200, Jakub Gustak wrote:
This is last scheme status report during SoC. So I will sum things up in the end.
Thanks for the good work you did during the summer! The result looks good to me, even with the missing features, but we'd really need a Scheme guy to guide us from now on, if we want to make the interpreter more usable.
Indeed, the current approach allows impressive-looking tests to pass, but the code is quite verbose and inefficient. We can start thinking at some point about using the stackless and/or GC-based cloning operations of RPython as a more orthogonal alternative, but that's an involved topic.
If you do, then farewell! In the event that you're interested to continue, though (:-), here are in summary some possible future directions: * get some Scheme people interested in the project, try to run real Scheme projects * implement more of the missing features * think how to do continuations with stackless or GC-based cloning * also, we could try to integrate pypy/lang/scheme and pypy/interpreter in one of the many possible ways, to offer a combined Python+Scheme environment... A bientot, Armin.
participants (4)
-
Armin Rigo -
Carl Friedrich Bolz -
Jakub Gustak -
Maciek Fijalkowski