Function Arguments and Continuations

Question

My question is about function arguments in conjunction with continuations. Specifically, what behavior is required, and what is allowed.

Suppose you have a function call (f arg1 arg2 arg3). I realize that a compliant Scheme implementation is allowed to evaluate the arguments arg1, arg2, and arg3 in any order. That's fine. But now suppose that, say, arg2 creates a continuation. In general, some of the other arguments may be evaluated before arg2 is evaluated, and some may be evaluated after arg2 is evaluated.

Suppose that, in the Scheme implementation we're using, arg1 is evaluated before arg2. Further, suppose that f modifies its local copy of the first argument. Later, when the continuation created during the evaluation of arg2 is called, arg3 will be evaluated again and f will be called.

The question is this: When f is called a second time, via the continuation, what value must/may its first argument have? Does it need to be the same value that arg1 evaluated to? Or may it be the modified value from the previous call to f? (Again, this example assumes that arg1 is evaluated before arg2, but the same issue applies with different argument evaluation orders. I.e., if arg3 is evaluated before arg2, then the question applies to arg3.)

I have tried this in a couple of Scheme implementations, and have obtained differing results. I took into account different orders of evaluation of the arguments (it's easy to track it by having the argument expressions log when they're being evaluated). Ignoring that difference, one implementation always used the original argument values, and another sometimes used the original argument values, and sometimes used the modified argument values, depending on whether f was an inline lambda vs. a global function. Presumably the difference is due to whether the actual arguments end up being copied into the function's local variables, or whether they are used in-place.

Here is a version that uses a global function:

(define (bar x cc y)
    (set! x (* x 2))
    (set! y (* y 3))
    (format #t "~a ~a\n" x y)
    cc)

(define (foo a b)
    (let* ((first #t)
           (cb (bar
                (+ a 10)
                (call/cc (lambda (x) x))
                (+ b 100))))
        (if first
            (begin
                (set! first #f)
                cb)
            (cb '()))))

(define cc (foo 1 2))
(call/cc cc)
(call/cc cc)

The above version uses the original argument values when calling the function bar in both of the Scheme implementations that I tested. The function bar sees 11 for the first argument and 102 for the third argument each time it is called. The output is:

22 306
22 306
22 306

Now, here is a version that replaces the global function with an inline lambda:

(define (foo a b)
    (let* ((first #t)
           (cb ((lambda (x cc y)
                    (set! x (* x 2))
                    (set! y (* y 3))
                    (format #t "~a ~a\n" x y)
                    cc)
                (+ a 10)
                (call/cc (lambda (x) x))
                (+ b 100))))
        (if first
            (begin
                (set! first #f)
                cb)
            (cb '()))))

(define cc (foo 1 2))
(call/cc cc)
(call/cc cc)

In one of the Scheme implementations I tested (BiwaScheme), this behaves the same as the previous version. I.e., the called function always sees the original argument values.

In another Scheme implementation (Gosh/Gauche), this behaves differently from the previous version. In this case, the called function uses the modified value of the first argument. In other words, it handles the inline lambda differently, taking advantage of the fact that it can see the function definition, and is presumably using a more direct argument passing mechanism that avoids having to copy them. Since it isn't copying the arguments, the ones that were evaluated before the continuation point retain their modified values. The lambda sees 11 and 102 for the first and third arguments the first time, then it sees 22 and 102 the second time, and 44 and 102 the third time. So the continuation is picking up the modified argument values. The output is:

22 306
44 306
88 306

So again, my question is this: Are both behaviors allowed by the Scheme standard (R6RS and/or R7RS)? Or does Scheme in fact require that the original argument values be used when the continuation is invoked?

Update: I originally reported that the Gauche Scheme implementation gave the three different sets of values shown above. That was true, but only for certain versions of Gauche. The version I originally tested was Gauche 0.9.3.3, which shows the three different sets of values. I later found a site that has three different versions of Gauche. The oldest, Gauche 0.9.4, also shows the three different sets of values. But the two newer versions, Gauche 0.9.5 and Gauche 0.9.8, both show the repeated values:

22 306
22 306
22 306

This argues pretty strongly that this was considered a bug which has since been fixed (just as everyone has been saying).

Answer 1

A continuation will literally create a copy of the stack in the moment of calling call/cc, copy that is also called a control-point. The continuation also stores inside it a copy of the current dynamic environment (more precisely, of the state-space from the dynamic-wind module) and a copy of the thread-local state.

So, when you reactivate the continuation, everything will continue from the moment when it was saved. If some arguments were previously evaluated, their evaluation is saved on the stack and the rest of arguments will be re-evaluated a second time. (as a remark, the dynamic state in scheme is implemented over the dynamic-wind module, so saving the dynamic state involved saving the state of dynamic wind, which is a combination between stack and the state-space (a tree keeping the in-out thunks for dynamic-wind calls)).

The stack starts from the top-level (actually there are other stacklets that represent continuations of the shutdown procedures, but those are touched only when you finish your code), they are not memorized when you call call/cc. So, if in a file/repl you gave 2 expressions, such as

(+ (f 1) 2)
(display "ok")

each of these expressions will have its own stacklet, so saving the continuation within f won't re-evaluate the display.

I think this should be enough to analyse your problem. The arguments are evaluated in unspecified order.

EDIT:

Concerning the answer of foo, for sure it is not correct 22 306 44 306 88 306 but it's correct 22 306 22 306 22 306.

I never used any of these 2 implementations. It is a bug in the implementation that does not bind x after each invocation of the (lambda (x cc y) ...), as the capture of the continuation is made outside the lambda().

The implementation bug seems obvious, it's in their generation of Scode -- they keep x on the stack, despite the fact that set! x was present, which should be an indicator to allocate x as a box on the heap.

Answer 2

While the evaluation order is undefined in the report it is not undefined in an implementtions CPS code. Eg.

(f (+ x 4) (call/cc cont-fun)), where x is a free variable, becomes either:

(call/cc& 
 cont-fun&
 (lambda (v2)
   (+& x 
       4
       (lambda (v1)
         (f& v1 v2 halt&))))

Or:

(+& x 
    4
    (lambda (v1)
      (call/cc& 
       cont-fun&
       (lambda (v2)
         (f& v1 v2 halt&)))))

So if the continuation function cont-fun& mutates x this will have an impact of the result in the version that evaluates the arguments right to left since the addition is done in the continuation of it, but in the second version mutating x will not affect the addition since the value is already computed in the passed value v2 and in the event the continuation is captured and rerun this value will never be recomputed. In the first version though you always compute v1 so here mutating the free variable x will affect the result.

If you as a developer wants to avoid this you let* the damn thing:

(let* ((a2 (call/cc cont-fun))
       (a1 (+ x 4)))
  (f a1 a2))

This code will force the behavior of the addition always being in the continuation of determining a2.

Now I avoided using your mutating examples, but in reality those are just bindings being rerouted. You have overcomplicated bar as the set! does not have any lasting effect. It is always the same as:

(define (bar x cc y)
  (format #t "~a ~a\n" (* x 2) (* y 3))
  cc)

The continuation caught in:

(bar (+ a 10)
     (call/cc (lambda (x) x))
     (+ b 100))

Regardless of the order we know the call to bar is the final continuation after evaluating all 3 expressions and then do the body of the let* the first and the 2 consecutive times.

Your second version doesn't change anything since the function doesn't rely on free variables. How the consecutive call to the continuation gave you 44 and 88 is most definitely a compiler optimization that fails. It shouldn't do that. I would have reported it as a bug.