krulwich@ils.nwu.edu (Bruce Krulwich) (08/30/90)
In article <1990Aug24.212055.8368@nixtdc.uucp>, doug@nixtdc (Doug Moen) writes: [example deleted] >If this expression were 'functional', then we would expect referential >transparency to hold. ... >The problem is that each call to call/cc generates a different continuation >value, and this is a kind of side effect. Thus, the two occurrences of >(call/cc bar) return different values. ... >It follows that call/cc in its most general form cannot be part of >a purely functional language. This statement has bothered me since I first saw it a week ago. The system that I've written in my research on machine learning uses _explicit_ continuations throughout. Almost all procedures take as arguments success and failure continuations, and call the appropriate one with their results. This meshes well with my use of an iteration construct borrowed from T that is essentially the same as a named LET in Scheme. Many functions in my system will pass a continuation to another function that calls the iteration loop function to continue an iteration, as in: (define ... ... (let -loop-name- (... vars ...) ... (another-proc ... (lambda (arg) (-loop-name- arg)) ; success continuation (lambda () (-loop-name- var)) ; failure continuation ) )) in this way the loop in the procedure shown is continued in different ways based on the success or failure of "another-proc." This may result in some heap-consing of the closures for the named let, but I can live with that. The point is that I pass down explicit continuations (in the form of lambda expressions) that reenter a loop by calling the loop variable. Fine so far. The next question is what should happen if the procedure shown above were to exit with one of the explicit continuations still referenced. For example, suppose "another-proc" were to succeed, and thus call the success continuation, but keep around a reference to (ie, pass out) the failure continuation to be called in the case of a subsequent failure. The answer, I think clearly, is that it should do just what is intended, and reenter the loop at the point of the saved continuation. This works because in order to save the continuation the closure had to have been heap-cons'ed, so there is no problem reentering the loop with the appropriate variable bindings. Is a system that does this "purely functional" ?? I see no reason why not. The above can be done in a _very_ pure functional style through closure construction and calling. 100% functional, no side effects, caffeine free. OK, what's the point, you ask? Simple, I answer. The only difference between code that does what I've described and code that uses CALL/CC (with multiple procedure reentries) is that in my code above the continuations (and their associated contexts) are explicit while in code using CALL/CC they're implicit. In every Scheme procedure call there's an implicit continuation with associated binding context, which is made explicit by CPS conversion. When this is explicit, as in the code I describe above, you would think nothing of saving the continuations around and calling them more than once. The reason that CALL/CC causes difficulties in Scheme is that the continuation information is implicit. This seems to correspond to research on accomplishing other tasks that would seemingly hurt "pure" functionality, such as I/O. As far as I remember, the work in this area that I've seen (which isn't much, I admit) works by somehow making the I/O "situation" explicit, to differentiate calls to I/O procedures. This seems analogous to making CALL/CC survive constraints of referential transparency by making the continuations explicit (as in CPS conversion). To conclude, CALL/CC only hurts "pure functionality" (ie, referential transparency) because a portion of the information in a procedure call is left implicit in Scheme. When this is made explicit, as by CPS conversion or by programmers using explicit continuations, the problems go away. Bruce Krulwich krulwich@ils.nwu.edu