A forwarded message from Oleg. ---------- Forwarded message ---------- From: <oleg@okmij.org> Date: Mon, Feb 27, 2012 at 1:56 PM Subject: Re: Comments on draft 6 about call/cc To: alexshinn@gmail.com Cc: scheme-reports <scheme-reports@scheme-reports.org> Hello! Thank you indeed for such detailed comments. Since your comments have touched so many different issues, let me reply to them in different messages. In this message I'd like to comment on the following: > With mutation, call/cc can implement delimited continuations. The > inverse is not so - delimited continuations can't implement call/cc > nor many uses of it such as amb. > > Thus call/cc makes Scheme strictly more expressive than delimited > continuations. Since it can be used to implement delimited > continuations as a library, it is preferable from a theoretical > standpoint. From a practical standpoint implementations are free to > implement the delimited conts more efficiently (and in fact use the > same infrastructure to implement call/cc by wrapping a delimiter > around the whole program). So in the long term I think it makes the > most sense to provide both, treat call/cc as more fundamental, yet > encourage use of delimited conts wherever possible. The implementation of delimited control in terms of call/cc is much more complex and subtle than it appears from Filinski's code. If we wish to use native Scheme exception handling, then delimited control cannot be portably implemented in terms of call/cc at all. I further argue that in practice call/cc captures a delimited continuation, and hence is implementable with shift. First recall that Filinski expression did not take into account dynamic environment such as parameters and exceptions. A limited form of dynamic environment existed in earlier Schemes (e.g, current-input-port). R7RS has these forms explicitly. One can give a very simple operational semantics of exceptions and dynamic binding. Informally, the semantics will associate exception handling (or dlet) to some parts of the continuation (stack). Incidentally, this is how exception handling is commonly implemented. (Racket uses such a semantics explicitly, btw, to reason about control and environment). Since delimited control captures the prefix of the continuation, it should likewise capture the associated exception handlers. Why this is a reasonable position? There are _practical_ reasons for that, and our ICFP 06 paper and the code showed many examples. If you implement shift/reset in terms of call/cc and use dynamic binding facilities of Scheme (such as provided by the parameterize SRFI at the time of the writing, which is now part of R7RS) then several confusing things happen. First, Filinksi code has a memory leak. If we fix the memory leak using trampolines, the result of the program changes. So, we no longer have one `canonical' implementation of delimited control in terms of call/cc. Subtle details such as trampolining become exposed. There are far bigger practical problems. See the slides of Chung-chieh Shan's ICFP06 talk http://www.cs.rutgers.edu/~ccshan/dynscope/talk.pdf particularly slide 31 and the ones leading to it. A program uses delimited control to implement generators to make enumeration over a file convenient. The program relies on exception handling to make sure the file is always closed when the enumeration finishes, normally or abnormally. If you use Filinksi implementation of shift/reset and native facilities for exceptions (we use many versions of Scheme plus SML plus OCaml), the file may remain unclosed. One may say this is a bug -- a very subtle bug. See slide 33 of the talk for the overview of the problem. There are two solutions. We may accept Filinksi definition of shift in terms of call/cc and mutation -- but then we have to re-implement our own exception handling and dynamic binding forms, in terms of shift. The ICFP06 paper mainly described that solution. Thus we are saying to the users: your Scheme system may have dynamic binding and exception handling; R7RS has exception handling and dynamic binding. *DON'T USE THEM*. Use our forms. I guess many people will find a problem with such an advice, recommending them not to use the facilities provided in the standard. The paper mentioned an alternative: if we wish to use native exception handling and dynamic binding, we have to find a different expression for shift. Filinksi expression no longer applies. Alas, the new expression for shift relies on the ability to capture a part of a dynamic environment and splice it in. None of the Scheme standards provide the needed primitives. I have implemented the alternative solution specifically for Scheme 48 (which doesn't directly provide the needed primitives either. Fortunately, it was possible to convince some of its internal functions to do the desired things). The ICFP06 paper's code archive has the code. Thus, if some form of delimited control has to be provided, it has to be provided as a primitive. We can't in general rely on the call/cc plus mutation. Racket has took exactly that approach (described in an ICFP07 paper). > With mutation, call/cc can implement delimited continuations. The > inverse is not so - delimited continuations can't implement call/cc > nor many uses of it such as amb. I am yet to come across any practical use of specifically undelimited continuations at all. I came to believe that call/cc per se has no practical use. I am intrigued by your mention of amb: certainly amb can be expressed using delimited control, I've done it many times in many languages. Could you send me an example of using amb that you think must use undelimited control? Finally, practically speaking call/cc captures a delimited continuation anyway. Many Scheme systems put an implicit reset around the REPL. (When a debugger is entered, the reset is put around it as well. If a Scheme provides a threading facility, sometimes implicit resets are placed around threads.) For example, in Petite Chez: (let ((k0 #f)) (call/cc (lambda (k) (set! k0 k))) (display "OK") (newline) (k0 #f)) That code prints the unending stream of OK. Now, I change the code to put each operation on its own line (evaluated by its own REPL). (define k0 #f) (call/cc (lambda (k) (set! k0 k))) (display "OK") (newline) (k0 #f) The result: OK #f So, call/cc has captured the identity continuation. Not only undelimited continuations have no practical use -- undelimited continuations don't even exist in practice. In practical systems, call/cc captures delimited continuation, which can certainly be implemented with shift. Cheers, Oleg P.S. If my message doesn't show up in the list archive, could you forward it? Thank you. _______________________________________________ Scheme-reports mailing list Scheme-reports@scheme-reports.org http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports
