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
lyn@ALTDORF.AI.MIT.EDU (Franklyn Turbak) (08/30/90)
In article <1543@anaxagoras.ils.nwu.edu>, Bruce Krulwich writes: > 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. You could make the same claim about SET! and the store. That is, SET! only hurts "pure functionality" because a portion of the information in a procedure call (i.e. the store) is left implicit in Scheme. Just as with CALL/CC, with SET! it is always possible to regain pure functionality by passing an extra argument (the store) explicitly to every procedure. (In the case of stores it is also necessary to *return* the store from every procedure call so that it is single-threaded throughout the computation.) The key point is that any kind of hidden state destroys referential transparency, and making all state explicit restores referential transparency. This point is especially clear in the denotational definitions of programming languages. That is, if we want to model the meanings of programs with mathematical functions (which of necessity are "pure"), we are required to make all state explicit. This is why the valuation functions for programming languages like Scheme (see the script-E function in the Formal Semantics section of R^3RS) typically have a signature that looks something like: Expression x Environment x Continuation x Store -> Ans (Usually this is presented in a curried form, but let's ignore that here.) Thus, an expression only has meaning with respect to three other pieces of state: the environment, the continuation, and the store. The environment associated with an expression is statically apparent from the lexical structure of the program, and so we generally do not consider it a piece of "hidden state". But the continuation and store model dynamic behavior; leaving these implicit is what destroys referential transparency. - Lyn -
daniel@MOJAVE.STANFORD.EDU (Daniel Weise) (08/30/90)
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. This is not true. CALL/CC gives you access to a continuation you can never construct yourself: the top-level one that your program is invoked with. It's this continuation that causes problems because it is not a function, it does not return a value. The other continuations ones you explicitly construct with lambda are functions. 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. 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. EVALUATION ORDER is the hidden state that causes problems, not continuations per se. CPS conversion does two things: it fixes the evaluation order and it introduces continuations. Steele's thesis confused these two tasks and they have been confused ever since. It is making the evaluation order explicit that makes continuations gotten by call/cc become referentially transparent. Think of it this way: the semantics of Scheme are non-deterministic, they specify a set of possible evaluation orders. An interpreter merely has to pick one of them to be correct. Call/cc exposes the evaluation order chosen by the interpreter, and is therefore referentially opaque because its use exposes hidden varying state. CPS conversion does the choosing instead of having the interpreter doing the choosing. (That CPS conversion also happens to make continuations explicit is irrelevant to this argument.) Since there is now only one evaluation order, there is no hidden state for call/cc to expose, and its use becomes transparent. Note that this argument applies to eager languages where one can specify the order of evaluation using application. For a lazy language, where order of evaluation is not controllable, call/cc, which gives access to the initial continuation, is not a functional construct. Daniel
gateley@datura.rice.edu (John Gateley) (08/30/90)
In article <1543@anaxagoras.ils.nwu.edu> krulwich@ils.nwu.edu (Bruce Krulwich) writes: > (define ... > ... > (let -loop-name- (... vars ...) > ... > (another-proc ... > (lambda (arg) (-loop-name- arg)) ; success continuation > (lambda () (-loop-name- var)) ; failure continuation > ) )) The question about whether or not the above is functional hinges on one issue - how is the let loop implemented (heap space was mentioned in the article). If it is implemented with a let/set! approach (the normal macroexpansion for letrec), then it is NOT functional. If it is implemented with Y, then it is functional. However, I don't think you can translate call/cc in to some magic combinator Z so that it too is functional, it is still dependent on context. John gateley@rice.edu
mkatz@GARLIC.STANFORD.EDU (Morris Katz) (09/05/90)
Date: 30 Aug 90 16:44:57 GMT From: John Gateley <news@rice.edu> Organization: Rice University, Houston References: <583@array.UUCP>, <1990Aug24.212055.8368@nixtdc.uucp>, <1543@anaxagoras.ils.nwu.edu> Sender: scheme-request@mc.lcs.mit.edu In article <1543@anaxagoras.ils.nwu.edu> krulwich@ils.nwu.edu (Bruce Krulwich) writes: > (define ... > ... > (let -loop-name- (... vars ...) > ... > (another-proc ... > (lambda (arg) (-loop-name- arg)) ; success continuation > (lambda () (-loop-name- var)) ; failure continuation > ) )) The question about whether or not the above is functional hinges on one issue - how is the let loop implemented (heap space was mentioned in the article). If it is implemented with a let/set! approach (the normal macroexpansion for letrec), then it is NOT functional. I disagree! If a construct has a functional implementation, any implementation for which there is no operation that can demonstrate that it is not functional is effectively functional. (Sorry about all the negations, but I can't seem to find any better phraseology at the moment.) My interpreter might implement + using side effects for some perverse reason, but that does not necessarily make + an imperative operator. ------------------------------------------------------------------------------- Morry Katz katz@cs.stanford.edu -------------------------------------------------------------------------------
mkatz@GARLIC.STANFORD.EDU (Morris Katz) (09/05/90)
Date: Tue, 4 Sep 90 14:20:09 CDT From: John Gateley <gateley@rice.edu> Well, I mostly agree with you, but don't forget that call/cc can distinguish between the two flavors of letrec (the letrec implementation of cell which came across the net a year or two ago). I was very careful about how I phrased my statement. Two implementations which can be differentiated via call/cc are not equivalent according to my definition. Since the semantics of letrec I believe should be specified in terms of the Y combinator functionality, I consider the side effect based implementation to in some sense be incorrect. A really good compiler would use the more efficient side effect based implementation only when it could prove that the side effect could not be detected by a call/cc. ------------------------------------------------------------------------------- Morry Katz katz@cs.stanford.edu -------------------------------------------------------------------------------