Hello,
are there any documentation how to implement call/cc call on top of GVM?
So far, looking at the use of the register 0 and jumps at the end of basic blocks, I optimistic concluded that GVM code is in the continuation-passing style. (Is it true?) Therefore, I tried a call/cc definition from "The 90 minute Scheme to C compiler":
(define call/cc (lambda (k f) (f k (lambda (dummy-k result) (k result)))))
A pseudocode for a GVM interpreter looks like:
#<primitive ##call-with-current-continuation>: pc = reg1 reg1 = new continuation(reg0) goto pc
A jump to the continuation is: pc = continuation.get_label() goto pc
It nearly worked, but I don't know what to do with the stack. Consider an example:
(define (f return) (return 2) 3) (display (f (lambda (x) x)))(newline) ; displays 3 (display (call-with-current-continuation f))(newline) ; displays 2
Here is the GVM code for the #<procedure ~#f>:
#1 0 entry-point 1 () -1 = +0 -2 = +1 +1 = '2 +0 = #3 -3 = . -4 = . jump* 4 #2
A new stack frame is allocated.
#2 4 jump 4 -2 1
Exit from ~#f due to the jump to the continuation. But: the stack frame still exists, it is not revoked. Therefore in
jump 4 '#<primitive ##call-with-current-continuation> 1 #6 4 return-point +0 = #7 jump 4 '#<primitive display> 1 #7 4 return-point +0 = -1 jump* 4 #8
the register 0 is restored using the wrong frame.
How to restore the stack correctly when jumping to a continuation?
Afficher les réponses par date
Hello,
answering to myself:
How to restore the stack correctly when jumping to a continuation?
After some observation, I decided that GVM code has the property: values in the stack are read-only. Therefore, call/cc makes a copy of the stack, and a jump to a continuation restores this copy.
Maybe this solution is not optimal, but it works at least for the yin-yang puzzle. (http://en.wikipedia.org/wiki/Call-with-current-continuation )
On 2011-02-04, at 8:38 AM, Oleg Parashchenko wrote:
Hello,
answering to myself:
How to restore the stack correctly when jumping to a continuation?
After some observation, I decided that GVM code has the property: values in the stack are read-only. Therefore, call/cc makes a copy of the stack, and a jump to a continuation restores this copy.
Maybe this solution is not optimal, but it works at least for the yin-yang puzzle. (http://en.wikipedia.org/wiki/Call-with-current-continuation )
It is not quite true that stack slots are read-only, because a stack slot can be reused for a different variable when the variable it was holding is no longer live. Mutable Scheme variables are allocated in the heap, so in that sense a "set!" will not change the stack.
So... continuations can indeed be implemented by copying the stack. Copying the entire stack however is wasteful and can lead to very poor performance. For this reason Gambit copies each frame independently. Pages 72-80 of the "Gambit inside out" presentation explain how continuations are implemented in Gambit (see the Gambit wiki main page for the link to the talk).
Marc
Hello Marc,
On Fri, 4 Feb 2011 09:26:21 -0500 Marc Feeley feeley@iro.umontreal.ca wrote:
...
So... continuations can indeed be implemented by copying the stack. Copying the entire stack however is wasteful and can lead to very poor performance. For this reason Gambit copies each frame independently. Pages 72-80 of the "Gambit inside out" presentation explain how continuations are implemented in Gambit (see the Gambit wiki main page for the link to the talk).
Thanks for the pointer, and the whole presentation is very interesting!
Marc