doug@nixtdc.uucp (Doug Moen) (08/25/90)
Thesis: call/cc and exception handling involve side effects, and are not 'functional'. >jinx@zurich.ai.mit.edu writes: >> I like to think of Scheme reified continuations as re-entrant. colin@array.UUCP (Colin Plumb) writes: >This property does some interesting things to functionality. >Obviously, >(define (foo) (1)) >Is strictly functional - it can be replaced by "1" wherever it appears. >Less obviously, >(define (bar x) (cons x 1)) >is not a function, since it can be called like: >(let ((y (call/cc bar))) > (if (= (cadr y) 1) ((car y) (cons (car y) 2))) > (cadr y)) >And it will have returned (<continuation> 2). I find this behaviour >disturbing in some odd way. Two corrections. First, (cadr y) is a typo: you meant (cdr y). Second, 'bar' is a just as much a pure function as 'foo': you can replace any occurrence of (bar n) with (cons n 1), without changing the meaning of a program. The problem lies with call/cc, not with bar. Let's look at the expression in question again (with corrections): (let ((y (call/cc bar))) (if (= (cdr y) 1) ((car y) (cons (car y) 2))) (cdr y)) This is a perfectly legal Scheme expression that evaluates to 2. If this expression were 'functional', then we would expect referential transparency to hold. Specifically, it should be possible to replace any occurrence of 'y' with its definition in the body of the let statement, without changing the meaning of the expression. This is not the case. Here's what we get if the last occurrence of 'y' is replaced by its definition: (let ((y (call/cc bar))) (if (= (cdr y) 1) ((car y) (cons (car y) 2))) (cdr (call/cc bar))) This expression evaluates to 1, instead of to 2. 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. >> I like to think of Scheme reified continuations as re-entrant. >This property does some interesting things to functionality. I think you are saying here that the reason call/cc is not functional is because continuations can be called after the original call to call/cc has returned. This is not the case. Even if we restrict call/cc so that a continuation cannot be referenced after call/cc has returned, there is *still* a problem. Recall that in Scheme, the order of evaluation of the component expressions of a combination is undefined. If you restrict yourself to the functional subset of Scheme, the evaluation order will never make a difference. Order of evaluation can only make a difference when expressions can have side effects: this is one of the things that makes functional programs easier to reason about than non-functional programs. We can use sensitivity to order of evaluation in a combination as a test to distinguish functional from non-functional features. Now consider the following: (call/cc (lambda (exit) (let ((a (lambda () (exit 0))) (b (lambda () (exit 1)))) (+ (a) (b))))) This expression returns either 0 or 1, depending on the order of evaluation in the particular implementation of Scheme used. This result also applies to traditional exception handling mechanisms such as are found in Modula-3, Ada, etc. The conclusion is that call/cc is non-functional no matter how you use it. A purely functional language cannot have call/cc or a traditional exception handling mechanism. -- Doug Moen {mnetor,alias,geac,torsqnt,lsuc}!nixtdc!doug 77 Carlton #1504, Toronto, Ontario, Canada M5B 2J7
news@usc.edu (08/27/90)
Functional exception handling is equivalent to extending functions to a universal domain. The traditional way of doing this seems to be returning a special 'null' return result, possibly with encoded information on what the error was. -- The news poster I'm using has a tendency to eat From: and Sender: lines. If you want to mail me any replies, I'm raulmill@usc.edu
wright@gefion.rice.edu (Andrew Wright) (08/29/90)
In article <1990Aug24.212055.8368@nixtdc.uucp> doug@nixtdc.UUCP (Doug Moen) writes: >... >The conclusion is that call/cc is non-functional no matter how you use it. >A purely functional language cannot have call/cc or a traditional >exception handling mechanism. I agree completely, although I think a simpler argument can be made. call-with-current-continuation grabs the current continuation, an object that depends on context. so obviously referential transparency cannot hold. Exception handling mechanisms may be viewed as a combination of call/cc and temporary assignment (or fluid-let), so by extension exception handling is not "functional" either. Andrew K. Wright Computer Science, Rice University wright@rice.edu Houston Texas 77251-1892