joemu@mentorg.com (Joe Mueller @ APD x1367) (05/29/91)
I'm trying to map the various C control statements into Scheme. The translation of break, continue, and return are giving me trouble. (I am not a scheme programmer so an obvious answer may not be obvious to me) I suspect I need to do something with call-with-current-continuation but I don't see exactly how to do it. Anyone care to help? Joe Mueller Joe_Mueller@mentorg.com ...!uunet!mntgfx!joemu
gyro@cymbal.reasoning.COM (Scott Layson Burson) (05/31/91)
Date: 28 May 91 19:18:34 GMT
From: "Joe Mueller @ APD x1367" <joemu@mentorg.com>
I'm trying to map the various C control statements into
Scheme. The translation of break, continue, and return
are giving me trouble. (I am not a scheme programmer so
an obvious answer may not be obvious to me)
I suspect I need to do something with
call-with-current-continuation but I don't see exactly how
to do it. Anyone care to help?
You don't need call-with-current-continuation.
`return' is implicit in Scheme: a lambda body always returns the value of its
last form. So you don't have to do anything special with it; e.g.
int foo() { return 3; }
-->
(define (foo) 3)
The way `break' and `continue' work is tied up in the way iteration is modelled
using tail-recursion. For instance
for (i = 0; i < 10; ++i) {
if (p1(i)) continue;
/* ... <1> */
if (p2(i)) break;
/* ... <2> */
}
-->
(letrec (((loop i)
(if (not (< i 10)) #f
(if (p1 i) (loop (+ 1 i))) ; `continue'
;; ... <1>
(if (p2 i) #f ; `break' value necessary
(begin
;; ... <2>
(loop (+ 1 i)))))))
(loop 0))
(Apologies if I screwed up the syntax -- I haven't written much Scheme lately.)
Here you see that the `continue' has turned into `(loop (+ 1 i))', which
invokes the next cycle of the loop, and `break' has turned into `#f' (it
doesn't matter what the value is, but there has to be one). That is, `break'
amounts to simply not invoking the next iteration.
A bit mind-bending, eh?
-- Scotthieb@heston.cs.indiana.edu (Robert Hieb) (05/31/91)
gyro@cymbal.reasoning.COM (Scott Layson Burson) writes: > Date: 28 May 91 19:18:34 GMT > From: "Joe Mueller @ APD x1367" <joemu@mentorg.com> > I'm trying to map the various C control statements into > Scheme. The translation of break, continue, and return > are giving me trouble. >You don't need call-with-current-continuation. >`return' is implicit in Scheme: a lambda body always returns the value of its >last form. So you don't have to do anything special with it... This is true only if the "return" is in tail position with respect to the procedure body, which is not in general true in C code. Such code can often be rewritten to put all return statements in tail position, but that may not be the sort of transformation desired, and is not always reasonable. To get a fully general return mechanism "call/cc" IS required; one must wrap a call to "call/cc" around each procedure body that has an explicit return in nontail position. One can then invoke the continuation to return. >The way `break' and `continue' work is tied up in the way iteration is modelled >using tail-recursion. "continue" statements cannot be turned into recursive function invocations, nor can "break" statements be removed, unless they are in tail position with respect to the loop body. One may be able to rewrite code to obey this constraint, but it is not always trivial to do so, especially if automatic or literal translations are desired. "break" can be gotten easily by wrapping the recursion in a "call/cc" invocation. "continue" is more difficult. For a loop of the form (while test body) the following would work: (call/cc (lambda (break) (let loop () (call/cc (lambda (continue) (if <test> <body> (break #f)))) (loop)))) To limit the number of continuations captured to two (instead of two plus one for each loop repeat) one can also write: (call/cc (lambda (break) (let ((continue (call/cc (lambda (k) k)))) (let loop () (if <test> (begin <body> (loop))))))) To make the above work, "continues" must look like (continue continue) rather than (continue <anything>) Or limit the number of continuations captured to one, at the expense of an extra test each time you use one: (let ((loop-control (call/cc (lambda (k) k)))) (if loop-control (let loop () (if <test> (begin <body> (loop)))))) Now "continue" statements look like (loop-control loop-control) and "break" statments look like (loop-control #f) It is true that one rarely needs to use continuations for loop control or procedure exit in Scheme---proper use of tail-recursive procedures is usually adequate. Using continuations unnecessarily in Scheme is just as bad as using "goto" (or "break", "continue", or "return") unecessarily in C.
quale@saavik.cs.wisc.edu (Douglas E. Quale) (06/01/91)
In article <1991May31.093235.25653@news.cs.indiana.edu> hieb@heston.cs.indiana.edu (Robert Hieb) writes: >gyro@cymbal.reasoning.COM (Scott Layson Burson) writes: > > >> Date: 28 May 91 19:18:34 GMT >> From: "Joe Mueller @ APD x1367" <joemu@mentorg.com> > >> I'm trying to map the various C control statements into >> Scheme. The translation of break, continue, and return >> are giving me trouble. > >>You don't need call-with-current-continuation. > >>`return' is implicit in Scheme: a lambda body always returns the value of its >>last form. So you don't have to do anything special with it... > >This is true only if the "return" is in tail position with respect to >the procedure body, which is not in general true in C code. Such code >can often be rewritten to put all return statements in tail position, >but that may not be the sort of transformation desired, and is not >always reasonable. To get a fully general return mechanism "call/cc" >IS required; one must wrap a call to "call/cc" around each procedure >body that has an explicit return in nontail position. One can then >invoke the continuation to return. > Actually regardless of where the return occurs, it is always possible to rewrite the code using no more than conditionals and procedure calls. A return is no more powerful than a goto, and gotos can be translated into procedure calls. The result isn't always very pretty. See the first published paper on lisp, by John McCarthy in CACM circa 1961.... (I've given up waiting for part 2!) -- Doug Quale quale@saavik.cs.wisc.edu
gyro@cymbal.reasoning.COM (Scott Layson Burson) (06/02/91)
Date: Fri, 31 May 91 09:32:15 EST From: Robert Hieb <hieb@heston.cs.indiana.edu> gyro@cymbal.reasoning.COM (Scott Layson Burson) writes: > Date: 28 May 91 19:18:34 GMT > From: "Joe Mueller @ APD x1367" <joemu@mentorg.com> > I'm trying to map the various C control statements into > Scheme. The translation of break, continue, and return > are giving me trouble. >You don't need call-with-current-continuation. >`return' is implicit in Scheme: a lambda body always returns the value of its >last form. So you don't have to do anything special with it... This is true only if the "return" is in tail position with respect to the procedure body, which is not in general true in C code. Such code can often be rewritten to put all return statements in tail position, but that may not be the sort of transformation desired, and is not always reasonable. To get a fully general return mechanism "call/cc" IS required; one must wrap a call to "call/cc" around each procedure body that has an explicit return in nontail position. One can then invoke the continuation to return. It is *always* possible to transform the C program into the appropriate form. Therefore CALL/CC is *not* *required* for a "fully general" return mechanism (in the C sense). It is not until you get to setjmp/longjmp that CALL/CC becomes necessary. Whether the result is "pretty" is another question, but beauty is in the eye of the beholder. I think it is quite a worthwhile exercise for anyone to understand how control constructs from traditional languages get translated into Scheme by means of these transformations, and without use of CALL/CC. I would go so far as to say that such an understanding is a prerequisite to developing a true Scheme style. This is the spirit in which I replied to Joe Mueller's question. Yes, you can do these things with CALL/CC, but you'll miss the chance to really understand what Scheme is all about. -- Scott Gyro@Reasoning.COM