The code is this one;
(let ((x 0) (cc '())) (set! x (+ x (call/cc (lambda (c) (set! cc c) (c 1))))) (if (< x 4) (cc 2) x))As far as I investigate, Chez, Chicken, Mosh, Sagittarius and Ypsilon went infinite loop. Chibi and Gauche returned 5. Well I'm not a guy from continuation world so I can't say which is correct. However if the call/cc is located to left hand side, then it won't be infinite loop.
;; This returns 5 (let ((x 0) (cc '())) (set! x (+ (call/cc (lambda (c) (set! cc c) (c 1))) x)) (if (< x 4) (cc 2) x))It seems the order of evaluation so I can probably get the answer.
I don't know about other implementations but Sagittarius so following guess is based on its call/cc implementation.
On Sagittarius, continuation is stack and it contains return address. So call/cc captures arguments and return address. Following is the image;
#first one
before call/cc
+----------+
| cont |
+----------+ <- captured
| pc(+) |
+----------+
| x=1 | *1
+----------+
| pc(set!) |
+----------+
#second one
before call/cc after call/cc
+----------+ +----------+
| cont | | x |
+----------+ <- captured +----------+
| pc(+) | | c(1) |
+----------+ +----------+
| pc(set!) | | pc(+) |
+----------+ +----------+
| pc(set!) |
+----------+
NOTE: pc is return address, cont is call/cc's argument.
Stack is growing upwards.
Well it's already obvious but I will describe just in case.The point is *1. The first one, the x is not a box means it's mere value (in this case 1). Then call/cc will capture the stack with the value. So the second call of (cc 2) will always be addition of 1 and 2. Thus it will never be greater than 4. On the other hand, the second case, stack doesn't have x yet so that VM will always compute what is inside of the box (x). Then (cc 2) will always compute the value of x and 2.I think implementations caused infinite loop are using the similar method to implement call/cc as Sagittarius and Chibi and Gauche use something different. And again, I'm not the those guys from continuation world, so can't say which is correct or not but as my understanding both can be correct and this case is sort of edge case of call/cc.
2 comments:
Racket also enters an infinite loop.
This is because Scheme DOES NOT SPECIFY THE ORDER OF EVALUATION of sub-expressions in a procedure-call expression. An implementation can do whatever it wants, so it may result in an infinite loop and that is not a bug.
Scheme does NOT even guarantee that the first sub-expression (the one which will return the procedure, through variable-reference or otherwise) will be evaluated first, so for example in
((get-procedure) (get-argument1) (get-argument2))
it could call the procedures `get-argument2` and `get-argument1` before calling the procedure `get-procedure`. Or it could call them in ANY other order.
So in some implementations, when you do
(set! x (+ x (call/cc (lambda (c) (set! cc c) (c 2)))))
the `x` argument in the procedure-call to + is evaluated first (the variable referenced), and returns 0, and then in the captured continuation you're left with something like
(set! x (+ 0 <...>))
and then no matter how many times you call (cc 2), it will just result in
(set! x (+ 0 2))
and x will never become greater than 2! This is valid Scheme behavior, and not a bug. If the implementation chooses another order and evaluates the (call/cc ...) first, then the variable-reference expression `x` will reference the new value of x every time, and it will grow by 2 every time you call (cc 2), and it will return 5 and not loop infinitely. That is ALSO valid Scheme behavior. I think the standards don't even say that an implementation must choose the same order every time, it can choose a different order every time, and loop infinitely once then not loop infinitely the second time you try it!
Bottom line: don't rely on order of procedure-call sub-expression evaluation in Scheme, it is UNSPECIFIED. (This allows some optimizations in a Scheme compiler; there are ways to force the order explicitly when you really need that.)
Post a Comment