* Non-stack-copying call-with-current-continuation? @ 2012-03-02 0:00 David Kastrup 2012-03-02 0:20 ` Noah Lavine ` (2 more replies) 0 siblings, 3 replies; 21+ messages in thread From: David Kastrup @ 2012-03-02 0:00 UTC (permalink / raw) To: guile-devel Hi, I am just meddling around with coding and have come up with the following: (define-public (find-child music predicate) "Find the first node in @var{music} that satisfies @var{predicate}." (catch 'music-found (lambda () (fold-some-music predicate (lambda (music . _) (throw 'music-found music)) #f music)) (lambda (key music) music))) Now the problem with that is that it is unhygienic. If fold-some-music were to use music-found signals, or if the predicate did, things would be awkward. One would need to work with a uniquely generated symbol. It turns out that the above can be expressed much clearer and cleaner as (define-public (find-child music predicate) "Find the first node in @var{music} that satisfies @var{predicate}." (call-with-current-continuation (lambda (music-found) (fold-some-music predicate (lambda (music . _) (music-found music)) #f music)))) at least if I did not make some thinko here. It is basically the same code and stack-upwards-only, but hygienic. Nothing can call the continuation but what is inside. Well, of course fold-some-music could save the closure calling music-found for later. But it doesn't. Is there a way to get a call-with-current-continuation that does not create a stack copy? It is fine if it fails with an exception if one still tries calling the continuation after it has already returned. -- David Kastrup ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-02 0:00 Non-stack-copying call-with-current-continuation? David Kastrup @ 2012-03-02 0:20 ` Noah Lavine 2012-03-02 0:42 ` David Kastrup 2012-03-02 1:18 ` Nala Ginrut 2012-03-03 17:41 ` Andy Wingo 2 siblings, 1 reply; 21+ messages in thread From: Noah Lavine @ 2012-03-02 0:20 UTC (permalink / raw) To: David Kastrup; +Cc: guile-devel If I understand correctly, you only need to call the continuation once. Is that right? In that case, I think you could use either catch and throw or prompts. (And catch and throw are implemented with prompts, so really, you can just choose how you want to use prompts.) Noah On Thu, Mar 1, 2012 at 7:00 PM, David Kastrup <dak@gnu.org> wrote: > > Hi, > > I am just meddling around with coding and have come up with the > following: > > (define-public (find-child music predicate) > "Find the first node in @var{music} that satisfies @var{predicate}." > (catch 'music-found > (lambda () > (fold-some-music predicate > (lambda (music . _) (throw 'music-found music)) > #f music)) > (lambda (key music) music))) > > Now the problem with that is that it is unhygienic. If fold-some-music > were to use music-found signals, or if the predicate did, things would > be awkward. One would need to work with a uniquely generated symbol. > It turns out that the above can be expressed much clearer and cleaner as > > (define-public (find-child music predicate) > "Find the first node in @var{music} that satisfies @var{predicate}." > (call-with-current-continuation > (lambda (music-found) > (fold-some-music predicate > (lambda (music . _) (music-found music)) > #f music)))) > > at least if I did not make some thinko here. It is basically the same > code and stack-upwards-only, but hygienic. Nothing can call the > continuation but what is inside. Well, of course fold-some-music could > save the closure calling music-found for later. But it doesn't. > > Is there a way to get a call-with-current-continuation that does not > create a stack copy? It is fine if it fails with an exception if one > still tries calling the continuation after it has already returned. > > -- > David Kastrup > > ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-02 0:20 ` Noah Lavine @ 2012-03-02 0:42 ` David Kastrup 2012-03-02 1:01 ` Noah Lavine 0 siblings, 1 reply; 21+ messages in thread From: David Kastrup @ 2012-03-02 0:42 UTC (permalink / raw) To: guile-devel Noah Lavine <noah.b.lavine@gmail.com> writes: > On Thu, Mar 1, 2012 at 7:00 PM, David Kastrup <dak@gnu.org> wrote: >> >> Hi, >> >> I am just meddling around with coding and have come up with the >> following: >> >> (define-public (find-child music predicate) >> "Find the first node in @var{music} that satisfies @var{predicate}." >> (catch 'music-found >> (lambda () >> (fold-some-music predicate >> (lambda (music . _) (throw 'music-found music)) >> #f music)) >> (lambda (key music) music))) >> >> Now the problem with that is that it is unhygienic. If fold-some-music >> were to use music-found signals, or if the predicate did, things would >> be awkward. One would need to work with a uniquely generated symbol. >> It turns out that the above can be expressed much clearer and cleaner as >> >> (define-public (find-child music predicate) >> "Find the first node in @var{music} that satisfies @var{predicate}." >> (call-with-current-continuation >> (lambda (music-found) >> (fold-some-music predicate >> (lambda (music . _) (music-found music)) >> #f music)))) >> >> at least if I did not make some thinko here. It is basically the same >> code and stack-upwards-only, but hygienic. Nothing can call the >> continuation but what is inside. Well, of course fold-some-music could >> save the closure calling music-found for later. But it doesn't. >> >> Is there a way to get a call-with-current-continuation that does not >> create a stack copy? It is fine if it fails with an exception if one >> still tries calling the continuation after it has already returned. > > If I understand correctly, you only need to call the continuation > once. Is that right? > > In that case, I think you could use either catch and throw or prompts. Neither of which are hygienic and also less straightforward. It is not like I did not start my posting by giving the catch/throw-based example and saying what I disliked about it. -- David Kastrup ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-02 0:42 ` David Kastrup @ 2012-03-02 1:01 ` Noah Lavine 2012-03-02 1:35 ` David Kastrup 0 siblings, 1 reply; 21+ messages in thread From: Noah Lavine @ 2012-03-02 1:01 UTC (permalink / raw) To: David Kastrup; +Cc: guile-devel Oh yes, you're right. I'm sorry I missed it. I believe you can do it hygienically though. With prompts, you can use (make-prompt-tag) to generate a new, unique tag. With catch and throw, you could use (gensym) to do the same thing. You first example would become something like (define-public (find-child music predicate) "Find the first node in @var{music} that satisfies @var{predicate}." (let ((music-found-tag (gensym))) (catch music-found-tag (lambda () (fold-some-music predicate (lambda (music . _) (throw music-found-tag music)) #f music)) (lambda (key music) music))) Does that work? Noah On Thu, Mar 1, 2012 at 7:42 PM, David Kastrup <dak@gnu.org> wrote: > Noah Lavine <noah.b.lavine@gmail.com> writes: > >> On Thu, Mar 1, 2012 at 7:00 PM, David Kastrup <dak@gnu.org> wrote: >>> >>> Hi, >>> >>> I am just meddling around with coding and have come up with the >>> following: >>> >>> (define-public (find-child music predicate) >>> "Find the first node in @var{music} that satisfies @var{predicate}." >>> (catch 'music-found >>> (lambda () >>> (fold-some-music predicate >>> (lambda (music . _) (throw 'music-found music)) >>> #f music)) >>> (lambda (key music) music))) >>> >>> Now the problem with that is that it is unhygienic. If fold-some-music >>> were to use music-found signals, or if the predicate did, things would >>> be awkward. One would need to work with a uniquely generated symbol. >>> It turns out that the above can be expressed much clearer and cleaner as >>> >>> (define-public (find-child music predicate) >>> "Find the first node in @var{music} that satisfies @var{predicate}." >>> (call-with-current-continuation >>> (lambda (music-found) >>> (fold-some-music predicate >>> (lambda (music . _) (music-found music)) >>> #f music)))) >>> >>> at least if I did not make some thinko here. It is basically the same >>> code and stack-upwards-only, but hygienic. Nothing can call the >>> continuation but what is inside. Well, of course fold-some-music could >>> save the closure calling music-found for later. But it doesn't. >>> >>> Is there a way to get a call-with-current-continuation that does not >>> create a stack copy? It is fine if it fails with an exception if one >>> still tries calling the continuation after it has already returned. >> >> If I understand correctly, you only need to call the continuation >> once. Is that right? >> >> In that case, I think you could use either catch and throw or prompts. > > Neither of which are hygienic and also less straightforward. It is not > like I did not start my posting by giving the catch/throw-based example > and saying what I disliked about it. > > -- > David Kastrup > > ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-02 1:01 ` Noah Lavine @ 2012-03-02 1:35 ` David Kastrup 2012-03-02 1:49 ` Noah Lavine 2012-03-03 17:48 ` Andy Wingo 0 siblings, 2 replies; 21+ messages in thread From: David Kastrup @ 2012-03-02 1:35 UTC (permalink / raw) To: Noah Lavine; +Cc: guile-devel Noah Lavine <noah.b.lavine@gmail.com> writes: > Oh yes, you're right. I'm sorry I missed it. > > I believe you can do it hygienically though. With prompts, you can use > (make-prompt-tag) to generate a new, unique tag. With catch and throw, > you could use (gensym) to do the same thing. You first example would > become something like > > (define-public (find-child music predicate) > "Find the first node in @var{music} that satisfies @var{predicate}." > (let ((music-found-tag (gensym))) > (catch music-found-tag > (lambda () > (fold-some-music predicate > (lambda (music . _) (throw music-found-tag music)) > #f music)) > (lambda (key music) music))) > > Does that work? Sure, but things like gensym and make-prompt-tag (and (list '()) for creating an eq?-unique object) are artificial hygiene coming at a cost in symbol table and symbol generation time rather than "lexical" hygiene. They need _extra_ work, whereas the call-with-current-continuation approach needed _less_ work. Basically I want something like call-with-single-continuation that will only allow one return (and any dynwind out counts and should work if it is the first, so it is not exactly equivalent to using with-continuation-barrier) and come without the stack-copying cost of call-with-current-continuation. Sure, you can do (define (call-with-single-continuation proc) (let ((tag (gensym))) (catch tag (proc (lambda x (throw tag x))) (lambda (tag x) (apply values x))))) Oops. (apply values ...)? Does this even work? Anyway, you get the drift. But it is not pretty and it is not primitive. And its failure mode when you disobey the "single" contract is an uncaught exception with a weird symbol. -- David Kastrup ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-02 1:35 ` David Kastrup @ 2012-03-02 1:49 ` Noah Lavine 2012-03-02 8:36 ` David Kastrup 2012-03-03 17:48 ` Andy Wingo 1 sibling, 1 reply; 21+ messages in thread From: Noah Lavine @ 2012-03-02 1:49 UTC (permalink / raw) To: David Kastrup; +Cc: guile-devel Hello, > Sure, but things like gensym and make-prompt-tag (and (list '()) for > creating an eq?-unique object) are artificial hygiene coming at a cost > in symbol table and symbol generation time rather than "lexical" > hygiene. They need _extra_ work, whereas the > call-with-current-continuation approach needed _less_ work. Basically I > want something like call-with-single-continuation that will only allow > one return (and any dynwind out counts and should work if it is the > first, so it is not exactly equivalent to using > with-continuation-barrier) and come without the stack-copying cost of > call-with-current-continuation. I agree that it's not pretty. We have hygienic macros so we don't have to use gensym, after all. But I don't know of a better way. > Sure, you can do > > (define (call-with-single-continuation proc) > (let ((tag (gensym))) > (catch tag > (proc (lambda x (throw tag x))) > (lambda (tag x) (apply values x))))) > > Oops. (apply values ...)? Does this even work? Anyway, you get the > drift. But it is not pretty and it is not primitive. And its failure > mode when you disobey the "single" contract is an uncaught exception > with a weird symbol. Well, I can't fix all of that, but you could at least make it fail better like this: (define (call-with-single-continuation proc) (let ((tag (gensym)) (thrown #f)) (catch tag (proc (lambda x (if thrown (error "Single continuation called twice") (throw tag x))) (lambda (tag . x) (apply values x))))) I think that will do what you want. It doesn't look too bad to me, although I agree with your point in general - using symbols to denote names, like prompts, undoes the hygiene that Scheme is supposed to have. But the only solution I can think of is pretty messy. Noah ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-02 1:49 ` Noah Lavine @ 2012-03-02 8:36 ` David Kastrup 2012-03-03 5:03 ` Andreas Rottmann 2012-03-03 5:04 ` Andreas Rottmann 0 siblings, 2 replies; 21+ messages in thread From: David Kastrup @ 2012-03-02 8:36 UTC (permalink / raw) To: guile-devel Noah Lavine <noah.b.lavine@gmail.com> writes: > Hello, > >> Sure, but things like gensym and make-prompt-tag (and (list '()) for >> creating an eq?-unique object) are artificial hygiene coming at a cost >> in symbol table and symbol generation time rather than "lexical" >> hygiene. They need _extra_ work, whereas the >> call-with-current-continuation approach needed _less_ work. Basically I >> want something like call-with-single-continuation that will only allow >> one return (and any dynwind out counts and should work if it is the >> first, so it is not exactly equivalent to using >> with-continuation-barrier) and come without the stack-copying cost of >> call-with-current-continuation. > > I agree that it's not pretty. We have hygienic macros so we don't have > to use gensym, after all. But I don't know of a better way. Well, to wrap this up: the manual (not current) states It is traditional in Scheme to implement exception systems using `call-with-current-continuation'. Continuations (*note Continuations::) are such a powerful concept that any other control mechanism -- including `catch' and `throw' -- can be implemented in terms of them. [...] The more targeted mechanism provided by `catch' and `throw' does not need to save and restore the C stack because the `throw' always jumps to a location higher up the stack of the code that executes the `throw'. Therefore Guile implements the `catch' and `throw' primitives independently of `call-with-current-continuation', in a way that takes advantage of this _upwards only_ nature of exceptions. I think that using something like "call-with-single-continuation" as the underlying primitive would make Guile quite more similar to "traditional" systems in the code base. It would also provide a minimally-invasive tool for tuning existing code based on call-with-current-continuation in case that the stack copying semantics are _not_ required. Definitely more Schemeish than stuff like, uh, prompts? > Well, I can't fix all of that, but you could at least make it fail > better like this: > > (define (call-with-single-continuation proc) > (let ((tag (gensym)) > (thrown #f)) > (catch tag > (proc (lambda x (if thrown (error "Single continuation called > twice") (throw tag x))) > (lambda (tag . x) (apply values x))))) > > I think that will do what you want. It would help to actually set "thrown" somewhere (which is sort of tricky considering that you need to set it also on regular return). You wrap x into a list once too often (first with lambda x, then with lambda (tag . x)). But I get the drift. > It doesn't look too bad to me, although I agree with your point in > general - using symbols to denote names, like prompts, undoes the > hygiene that Scheme is supposed to have. But the only solution I can > think of is pretty messy. Yup. call-with-single-continuation would make best sense as a primitive for building other stuff, not the other way round. -- David Kastrup ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-02 8:36 ` David Kastrup @ 2012-03-03 5:03 ` Andreas Rottmann 2012-03-03 5:04 ` Andreas Rottmann 1 sibling, 0 replies; 21+ messages in thread From: Andreas Rottmann @ 2012-03-03 5:03 UTC (permalink / raw) To: David Kastrup; +Cc: guile-devel David Kastrup <dak@gnu.org> writes: > Noah Lavine <noah.b.lavine@gmail.com> writes: > >> Hello, >> >>> Sure, but things like gensym and make-prompt-tag (and (list '()) for >>> creating an eq?-unique object) are artificial hygiene coming at a cost >>> in symbol table and symbol generation time rather than "lexical" >>> hygiene. They need _extra_ work, whereas the >>> call-with-current-continuation approach needed _less_ work. Basically I >>> want something like call-with-single-continuation that will only allow >>> one return (and any dynwind out counts and should work if it is the >>> first, so it is not exactly equivalent to using >>> with-continuation-barrier) and come without the stack-copying cost of >>> call-with-current-continuation. >> >> I agree that it's not pretty. We have hygienic macros so we don't have >> to use gensym, after all. But I don't know of a better way. > > Well, to wrap this up: the manual (not current) states > > It is traditional in Scheme to implement exception systems using > `call-with-current-continuation'. Continuations (*note > Continuations::) are such a powerful concept that any other control > mechanism -- including `catch' and `throw' -- can be implemented in > terms of them. > > [...] > > The more targeted mechanism provided by `catch' and `throw' does not > need to save and restore the C stack because the `throw' always jumps > to a location higher up the stack of the code that executes the > `throw'. Therefore Guile implements the `catch' and `throw' primitives > independently of `call-with-current-continuation', in a way that takes > advantage of this _upwards only_ nature of exceptions. > > > I think that using something like "call-with-single-continuation" as the > underlying primitive would make Guile quite more similar to > "traditional" systems in the code base. It would also provide a > minimally-invasive tool for tuning existing code based on > call-with-current-continuation in case that the stack copying semantics > are _not_ required. Definitely more Schemeish than stuff like, uh, > prompts? > Just to throw my two cents in: Racket (and probably other Schemes) provide this primitive under the name call-with-escape-continuation (call/ec): http://docs.racket-lang.org/reference/cont.html?q=call/ec#%28def._%28%28quote._~23~25kernel%29._call-with-escape-continuation%29%29 Regards, Rotty -- Andreas Rottmann -- <http://rotty.yi.org/> ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-02 8:36 ` David Kastrup 2012-03-03 5:03 ` Andreas Rottmann @ 2012-03-03 5:04 ` Andreas Rottmann 1 sibling, 0 replies; 21+ messages in thread From: Andreas Rottmann @ 2012-03-03 5:04 UTC (permalink / raw) To: David Kastrup; +Cc: guile-devel David Kastrup <dak@gnu.org> writes: > Noah Lavine <noah.b.lavine@gmail.com> writes: > >> Hello, >> >>> Sure, but things like gensym and make-prompt-tag (and (list '()) for >>> creating an eq?-unique object) are artificial hygiene coming at a cost >>> in symbol table and symbol generation time rather than "lexical" >>> hygiene. They need _extra_ work, whereas the >>> call-with-current-continuation approach needed _less_ work. Basically I >>> want something like call-with-single-continuation that will only allow >>> one return (and any dynwind out counts and should work if it is the >>> first, so it is not exactly equivalent to using >>> with-continuation-barrier) and come without the stack-copying cost of >>> call-with-current-continuation. >> >> I agree that it's not pretty. We have hygienic macros so we don't have >> to use gensym, after all. But I don't know of a better way. > > Well, to wrap this up: the manual (not current) states > > It is traditional in Scheme to implement exception systems using > `call-with-current-continuation'. Continuations (*note > Continuations::) are such a powerful concept that any other control > mechanism -- including `catch' and `throw' -- can be implemented in > terms of them. > > [...] > > The more targeted mechanism provided by `catch' and `throw' does not > need to save and restore the C stack because the `throw' always jumps > to a location higher up the stack of the code that executes the > `throw'. Therefore Guile implements the `catch' and `throw' primitives > independently of `call-with-current-continuation', in a way that takes > advantage of this _upwards only_ nature of exceptions. > > > I think that using something like "call-with-single-continuation" as the > underlying primitive would make Guile quite more similar to > "traditional" systems in the code base. It would also provide a > minimally-invasive tool for tuning existing code based on > call-with-current-continuation in case that the stack copying semantics > are _not_ required. Definitely more Schemeish than stuff like, uh, > prompts? > Just to throw my two cents in: Racket (and probably other Schemes) provide this primitive under the name call-with-escape-continuation (call/ec): http://docs.racket-lang.org/reference/cont.html?q=call/ec#%28def._%28%28quote._~23~25kernel%29._call-with-escape-continuation%29%29 Regards, Rotty -- Andreas Rottmann -- <http://rotty.yi.org/> ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-02 1:35 ` David Kastrup 2012-03-02 1:49 ` Noah Lavine @ 2012-03-03 17:48 ` Andy Wingo 2012-03-04 12:01 ` David Kastrup 1 sibling, 1 reply; 21+ messages in thread From: Andy Wingo @ 2012-03-03 17:48 UTC (permalink / raw) To: David Kastrup; +Cc: guile-devel On Fri 02 Mar 2012 02:35, David Kastrup <dak@gnu.org> writes: > Sure, but things like gensym and make-prompt-tag (and (list '()) for > creating an eq?-unique object) are artificial hygiene coming at a cost > in symbol table and symbol generation time rather than "lexical" > hygiene. "Hygiene" is not right the word here. "Hygiene" applies lexically -- statically. You want a continuation that only works within a certain dynamic extent -- that's dynamic. Unique objects are well-suited to the needs of dynamic problems. But really, your concerns are entirely misplaced. Choose clean, clear, optimizable abstractions. Call/ec is a good example. If you need to implement it, do so using whatever tools are at hand. If you can't implement it or it's slow, then bring these concerns forward. But to dismiss Noah's suggestions out of hand is inappropriate at this time. Andy -- http://wingolog.org/ ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-03 17:48 ` Andy Wingo @ 2012-03-04 12:01 ` David Kastrup 2012-03-04 12:15 ` Andy Wingo 0 siblings, 1 reply; 21+ messages in thread From: David Kastrup @ 2012-03-04 12:01 UTC (permalink / raw) To: guile-devel Andy Wingo <wingo@pobox.com> writes: > On Fri 02 Mar 2012 02:35, David Kastrup <dak@gnu.org> writes: > >> Sure, but things like gensym and make-prompt-tag (and (list '()) for >> creating an eq?-unique object) are artificial hygiene coming at a cost >> in symbol table and symbol generation time rather than "lexical" >> hygiene. > > "Hygiene" is not right the word here. "Hygiene" applies lexically -- > statically. You want a continuation that only works within a certain > dynamic extent -- that's dynamic. Unique objects are well-suited to the > needs of dynamic problems. The problem is not a unique object (you get one with every (list 0) call), the problem is a unique symbol. Of course an escape continuation works only in a dynamic context. But that does not mean that its identity needs to be represented by a globally persisting symbol. The global symbol space is a different identity space than heap equality, and it never gets garbage collected: the lifetime of a gensym is eternal. > But really, your concerns are entirely misplaced. Choose clean, > clear, optimizable abstractions. Call/ec is a good example. If you > need to implement it, do so using whatever tools are at hand. If you > can't implement it or it's slow, then bring these concerns forward. > But to dismiss Noah's suggestions out of hand is inappropriate at this > time. I am not dismissing his suggestions. I am saying that I find call/ec a nicer primitive than catch/throw exactly because it does not need a name or symbol to work but has its identity and life-time coupled to an object rather than a symbol. And frankly: the manual talks about prompts being composable and gives an example which seems utterly wrong to me since it does not actually abort a computation but rather half-finishes it. It is unclear what part of the computation will finish and what will complete. -- David Kastrup ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-04 12:01 ` David Kastrup @ 2012-03-04 12:15 ` Andy Wingo 2012-03-04 13:59 ` David Kastrup 0 siblings, 1 reply; 21+ messages in thread From: Andy Wingo @ 2012-03-04 12:15 UTC (permalink / raw) To: David Kastrup; +Cc: guile-devel Hi David, On Sun 04 Mar 2012 13:01, David Kastrup <dak@gnu.org> writes: > The global symbol space is a different identity space than heap > equality, and it never gets garbage collected: the lifetime of a > gensym is eternal. This is not true in Guile, where symbols can be garbage collected. > I am not dismissing his suggestions. I am saying that I find call/ec a > nicer primitive than catch/throw exactly because it does not need a name > or symbol to work but has its identity and life-time coupled to an > object rather than a symbol. OK. > And frankly: the manual talks about prompts being composable and gives > an example which seems utterly wrong to me since it does not actually > abort a computation but rather half-finishes it. It is unclear what > part of the computation will finish and what will complete. That is an interesting point. I guess there are two ways of answering it. One is to note that in Scheme, it's difficult in general to determine whether a computation is finished or will finish, because of call/cc. But you ask about a specific point, here: an abort to a prompt is basically boils down to a longjmp to the prompt's handler. The partial continuation is logically passed as an argument to the handler. I say "logically" because, if Guile can prove that the continuation is not referenced, then it no continuation is reified. In practice, that means that if the handler is of the form (lambda (k . other-args) FORM), and FORM does not reference `k', then an abort to that prompt does not cause the stack to be captured. We should probably say something in the manual about this. (We should probably also add higher-level interfaces like call/ec and generators, as well.) Regards, Andy -- http://wingolog.org/ ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-04 12:15 ` Andy Wingo @ 2012-03-04 13:59 ` David Kastrup 2012-03-04 18:42 ` Andy Wingo 2012-03-04 18:45 ` Mark H Weaver 0 siblings, 2 replies; 21+ messages in thread From: David Kastrup @ 2012-03-04 13:59 UTC (permalink / raw) To: Andy Wingo; +Cc: guile-devel Andy Wingo <wingo@pobox.com> writes: > Hi David, > > On Sun 04 Mar 2012 13:01, David Kastrup <dak@gnu.org> writes: > >> The global symbol space is a different identity space than heap >> equality, and it never gets garbage collected: the lifetime of a >> gensym is eternal. > > This is not true in Guile, where symbols can be garbage collected. The symbol name is not garbage collected. That is the difference between gensym and make-symbol. >> And frankly: the manual talks about prompts being composable and >> gives an example which seems utterly wrong to me since it does not >> actually abort a computation but rather half-finishes it. It is >> unclear what part of the computation will finish and what will >> complete. > > That is an interesting point. I guess there are two ways of answering > it. One is to note that in Scheme, it's difficult in general to > determine whether a computation is finished or will finish, because of > call/cc. > > But you ask about a specific point, here: an abort to a prompt is > basically boils down to a longjmp to the prompt's handler. The > partial continuation is logically passed as an argument to the > handler. But where does the "partial continuation" start and where does it end? If I am doing a "longjmp to the prompt's handler", how can it be that the calling stack frame inside of the thunk that is supposed to be exited can finish a calculation? Where is the difference between (+ 34 (abort-to-prompt 'foo)) and (let ((x (abort-to-prompt 'foo))) (+ 34 x)) ? Why is the first allowed to complete and return a result, and the second (presumably) not? Or _if_ the second is allowed to complete, what does "abort" in "abort-to-prompt" even mean? All this does not really make discernible sense to me. Whereas call/ec has rather clear semantics and usage. The one thing that is not self-evident is its behavior in case of misuse, namely when it is asked to do a job only call/cc can. -- David Kastrup ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-04 13:59 ` David Kastrup @ 2012-03-04 18:42 ` Andy Wingo 2012-03-04 18:45 ` Mark H Weaver 1 sibling, 0 replies; 21+ messages in thread From: Andy Wingo @ 2012-03-04 18:42 UTC (permalink / raw) To: David Kastrup; +Cc: guile-devel Hello, On Sun 04 Mar 2012 14:59, David Kastrup <dak@gnu.org> writes: > Andy Wingo <wingo@pobox.com> writes: > >> This is not true in Guile, where symbols can be garbage collected. > > The symbol name is not garbage collected. That is the difference > between gensym and make-symbol. Not sure I catch your meaning here... >> But you ask about a specific point, here: an abort to a prompt is >> basically boils down to a longjmp to the prompt's handler. The >> partial continuation is logically passed as an argument to the >> handler. > > But where does the "partial continuation" start and where does it end? It starts at the abort, and is delimited by the prompt. Or you can see it as the other way around. > If I am doing a "longjmp to the prompt's handler", how can it be that > the calling stack frame inside of the thunk that is supposed to be > exited can finish a calculation? You longjmp, yes: but after having reified (or not) the continuation. It's the continuation that lets you continue. > Where is the difference between > > (+ 34 (abort-to-prompt 'foo)) > > and > > (let ((x (abort-to-prompt 'foo))) (+ 34 x)) ? There is no semantic difference. > Why is the first allowed to complete and return a result, and the second > (presumably) not? Or _if_ the second is allowed to complete, what does > "abort" in "abort-to-prompt" even mean? Whether it is allowed to complete or not depends on the prompt's handler, as I mentioned before. Here is an analogy. Consider a prompt as creating a new process, in the UNIX sense. Consider "abort" as calling abort() and dumping core (or not). Consider calling the partial continuation as taking the core file and running it as a program (as used to be possible in some UNIX systems). Sometimes you enable cores because you are interested in them. Sometimes you just want to let a process quit and return a value. The analogy with reifying continuations or not is clear, I hope. > All this does not really make discernible sense to me. Whereas call/ec > has rather clear semantics and usage. Please do use call/ec, if you prefer its interface. > The one thing that is not self-evident is its behavior in case of > misuse, namely when it is asked to do a job only call/cc can. For the implementation based on "throw", you would get an error that would be caught by the nearest (catch #t ...). For prompts, you would get an error "abort to unknown prompt", which would also be caught by the nearest (catch #t ...), or a catch of `misc-error'. (Guile's error handling is not very systematic right now; something to work on.) Regards, Andy -- http://wingolog.org/ ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-04 13:59 ` David Kastrup 2012-03-04 18:42 ` Andy Wingo @ 2012-03-04 18:45 ` Mark H Weaver 2012-03-04 23:13 ` David Kastrup 1 sibling, 1 reply; 21+ messages in thread From: Mark H Weaver @ 2012-03-04 18:45 UTC (permalink / raw) To: David Kastrup; +Cc: Andy Wingo, guile-devel David Kastrup <dak@gnu.org> writes: > Andy Wingo <wingo@pobox.com> writes: > >> On Sun 04 Mar 2012 13:01, David Kastrup <dak@gnu.org> writes: >> >>> The global symbol space is a different identity space than heap >>> equality, and it never gets garbage collected: the lifetime of a >>> gensym is eternal. >> >> This is not true in Guile, where symbols can be garbage collected. > > The symbol name is not garbage collected. That is the difference > between gensym and make-symbol. Integers are plentiful and cheap. Anyway, there's a well-known "Efficient Gensym Hack" where gensyms are given names lazily. We haven't yet implemented that in Guile, but I hope to add it before 2.2. With that optimization, if you never ask for the name of a gensym (e.g. by printing it) then it is never assigned a name or even a number. Dybvig reports that in Chez Scheme, this optimization made gensym 25 times faster. Also, in Guile 2, prompt tags need not be symbols. Anything that can be compared with 'eq?' will work. >>> And frankly: the manual talks about prompts being composable and >>> gives an example which seems utterly wrong to me since it does not >>> actually abort a computation but rather half-finishes it. It is >>> unclear what part of the computation will finish and what will >>> complete. >> >> That is an interesting point. I guess there are two ways of answering >> it. One is to note that in Scheme, it's difficult in general to >> determine whether a computation is finished or will finish, because of >> call/cc. >> >> But you ask about a specific point, here: an abort to a prompt is >> basically boils down to a longjmp to the prompt's handler. The >> partial continuation is logically passed as an argument to the >> handler. > > But where does the "partial continuation" start and where does it end? A partial continuation captures the stack from the prompt to the abort. If you later call the partial continuation with some values, those values will be returned by 'abort-to-prompt', and the computation will continue until it returns to the prompt, at which point the partial continuation will return the values returned to the prompt. An approximate way to think about it is as follows. In the following: (call-with-prompt 'foo (lambda () (let ((x (abort-to-prompt 'foo))) (+ 34 x))) (lambda (k) k)) The returned partial continuation will be equivalent to the following procedure: (lambda xs (let ((x (apply values xs))) (+ 34 x))) To a first (very rough) approximation, you can imagine that you took the body of the thunk passed to 'call-with-prompt', wrapped it within (lambda xs ...), replaced the 'abort-to-prompt' that was invoked with (apply values xs), and that's sort of what the partial continuation acts like. How does this approximation fall short? First of all, it's not quite right to replace the 'abort-to-prompt' with (apply values xs), because if that 'abort-to-prompt' is called again (e.g. if it's within a loop) then it will abort again. More importantly, when you call a partial continuation, it jumps directly to the 'abort-to-prompt', rather than re-running the outer layers of code. Any mutable local variables bound between prompt and abort will have whatever values they were last set! to, rather than being rebound. > If I am doing a "longjmp to the prompt's handler", how can it be that > the calling stack frame inside of the thunk that is supposed to be > exited can finish a calculation? If the compiler cannot prove that the partial continuation is ignored by the handler passed to 'call-with-prompt', then the stack segment between the prompt and abort must be copied. If the partial continuation is later called, that stack segment will be copied back. > Where is the difference between > > (+ 34 (abort-to-prompt 'foo)) > > and > > (let ((x (abort-to-prompt 'foo))) (+ 34 x)) ? > > Why is the first allowed to complete and return a result, and the second > (presumably) not? Or _if_ the second is allowed to complete, what does > "abort" in "abort-to-prompt" even mean? What makes you think that the second would not be allowed to complete? In both of these cases, assuming that what you've written above is the entire body of the thunk passed to 'call-with-prompt', the partial continuation will be equivalent to (lambda (x . rest) (+ 34 x)). > All this does not really make discernible sense to me. Whereas call/ec > has rather clear semantics and usage. The one thing that is not > self-evident is its behavior in case of misuse, namely when it is asked > to do a job only call/cc can. I agree that Guile should have 'call/ec' (ideally backed by an efficient VM instruction), and that for many purposes 'call/ec' is more natural. However, it should be noted that prompts are strictly more powerful than 'call/ec', and that 'call/ec' can be implemented easily and efficiently using prompts. For now, you can use this definition: (cond-expand (guile-2 (define (call-with-escape-continuation proc) (let ((tag (make-prompt-tag "call/ec"))) (call-with-prompt tag (lambda () (proc (lambda xs (abort-to-prompt tag xs)))) (lambda (k xs) (apply values xs)))))) (guile (define (call-with-escape-continuation proc) (let ((key (gensym "call/ec"))) (catch key (lambda () (proc (lambda xs (throw key xs)))) (lambda (key xs) (apply values xs))))))) (define call/ec call-with-escape-continuation) Mark ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-04 18:45 ` Mark H Weaver @ 2012-03-04 23:13 ` David Kastrup 2012-03-05 0:35 ` Mark H Weaver 0 siblings, 1 reply; 21+ messages in thread From: David Kastrup @ 2012-03-04 23:13 UTC (permalink / raw) To: guile-devel Mark H Weaver <mhw@netris.org> writes: > David Kastrup <dak@gnu.org> writes: > >> Andy Wingo <wingo@pobox.com> writes: >> >>> On Sun 04 Mar 2012 13:01, David Kastrup <dak@gnu.org> writes: >>> >>>> The global symbol space is a different identity space than heap >>>> equality, and it never gets garbage collected: the lifetime of a >>>> gensym is eternal. >>> >>> This is not true in Guile, where symbols can be garbage collected. >> >> The symbol name is not garbage collected. That is the difference >> between gensym and make-symbol. > > Integers are plentiful and cheap. We are not talking about an integer generated statically here. We are talking about integers getting burned through every time a control structure is being used. Not at compilation time, but at runtime. And with today's computers, executing a loop often enough that the integers don't fit into a single Scheme cell anymore and stop being cheap is not really an extraordinary event. > Anyway, there's a well-known "Efficient Gensym Hack" where gensyms are > given names lazily. We haven't yet implemented that in Guile, but I > hope to add it before 2.2. With that optimization, if you never ask > for the name of a gensym (e.g. by printing it) then it is never > assigned a name or even a number. That would help. > Also, in Guile 2, prompt tags need not be symbols. Anything that can > be compared with 'eq?' will work. I suppose there is no compelling technical reason why this could not be made to also work with catch/throw, right? Being able to use something like (list #f) instead of gensym would seriously reduce the cost, both felt as well as actual. -- David Kastrup ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-04 23:13 ` David Kastrup @ 2012-03-05 0:35 ` Mark H Weaver 2012-03-05 1:44 ` David Kastrup 0 siblings, 1 reply; 21+ messages in thread From: Mark H Weaver @ 2012-03-05 0:35 UTC (permalink / raw) To: David Kastrup; +Cc: guile-devel David Kastrup <dak@gnu.org> writes: > Mark H Weaver <mhw@netris.org> writes: > >> David Kastrup <dak@gnu.org> writes: >> >>> The symbol name is not garbage collected. That is the difference >>> between gensym and make-symbol. >> >> Integers are plentiful and cheap. > > We are not talking about an integer generated statically here. We are > talking about integers getting burned through every time a control > structure is being used. Not at compilation time, but at runtime. And > with today's computers, executing a loop often enough that the integers > don't fit into a single Scheme cell anymore and stop being cheap is not > really an extraordinary event. Indeed, this is a good point, and another reason why we need the efficient gensym hack. >> Also, in Guile 2, prompt tags need not be symbols. Anything that can >> be compared with 'eq?' will work. > > I suppose there is no compelling technical reason why this could not be > made to also work with catch/throw, right? Being able to use something > like (list #f) instead of gensym would seriously reduce the cost, both > felt as well as actual. Indeed, I see no reason why catch/throw shouldn't accept non-symbol tags. Looking through the code of Guile 1.8, I see nothing that depends upon the tag being a symbol. Unfortunately, catch/throw have long been documented as requiring a symbol, and raise an error if given a non-symbol, at least as far back as Guile 1.4. However, catch/throw _will_ accept uninterned symbols created with 'make-symbol'. Here's a faster implementation of call/ec that uses (list 'call/ec) to create prompt tags on Guile 2, and (make-symbol "call/ec") on earlier versions of Guile: (cond-expand (guile-2 (define (call-with-escape-continuation proc) (let ((tag (list 'call/ec))) (call-with-prompt tag (lambda () (proc (lambda xs (abort-to-prompt tag xs)))) (lambda (k xs) (apply values xs)))))) (guile (define (call-with-escape-continuation proc) (let ((key (make-symbol "call/ec"))) (catch key (lambda () (proc (lambda xs (throw key xs)))) (lambda (key xs) (apply values xs))))))) (define call/ec call-with-escape-continuation) Regards, Mark ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-05 0:35 ` Mark H Weaver @ 2012-03-05 1:44 ` David Kastrup 0 siblings, 0 replies; 21+ messages in thread From: David Kastrup @ 2012-03-05 1:44 UTC (permalink / raw) To: guile-devel Mark H Weaver <mhw@netris.org> writes: > However, catch/throw _will_ accept uninterned symbols created with > 'make-symbol'. Personally, I like uninterned symbols much better. They can be a bit confusing in Lisp because they share print names, but one can't exactly say that they do in Guile: guile> (make-symbol "xxx") #<uninterned-symbol xxx b7838a10> guile> Which feels a bit like gensym-on-demand, except that the serialization happens by address rather than counting. > Here's a faster implementation of call/ec that uses (list 'call/ec) to > create prompt tags on Guile 2, and (make-symbol "call/ec") on earlier > versions of Guile: > > (cond-expand > (guile-2 (define (call-with-escape-continuation proc) > (let ((tag (list 'call/ec))) > (call-with-prompt > tag > (lambda () (proc (lambda xs (abort-to-prompt tag xs)))) > (lambda (k xs) (apply values xs)))))) > > (guile (define (call-with-escape-continuation proc) > (let ((key (make-symbol "call/ec"))) > (catch key > (lambda () (proc (lambda xs (throw key xs)))) > (lambda (key xs) (apply values xs))))))) > > (define call/ec call-with-escape-continuation) Given the constraints of current guile-1 and guile-2, I doubt that there is much to take away anymore from this solution. Thanks -- David Kastrup ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-02 0:00 Non-stack-copying call-with-current-continuation? David Kastrup 2012-03-02 0:20 ` Noah Lavine @ 2012-03-02 1:18 ` Nala Ginrut 2012-03-02 1:25 ` Noah Lavine 2012-03-03 17:41 ` Andy Wingo 2 siblings, 1 reply; 21+ messages in thread From: Nala Ginrut @ 2012-03-02 1:18 UTC (permalink / raw) To: David Kastrup; +Cc: guile-devel [-- Attachment #1: Type: text/plain, Size: 1827 bytes --] On Fri, Mar 2, 2012 at 8:00 AM, David Kastrup <dak@gnu.org> wrote: > > Hi, > > I am just meddling around with coding and have come up with the > following: > > (define-public (find-child music predicate) > "Find the first node in @var{music} that satisfies @var{predicate}." > (catch 'music-found > (lambda () > (fold-some-music predicate > (lambda (music . _) (throw 'music-found music)) > #f music)) > (lambda (key music) music))) > > Now the problem with that is that it is unhygienic. If fold-some-music > were to use music-found signals, or if the predicate did, things would > be awkward. One would need to work with a uniquely generated symbol. > It turns out that the above can be expressed much clearer and cleaner as > > (define-public (find-child music predicate) > "Find the first node in @var{music} that satisfies @var{predicate}." > (call-with-current-continuation > (lambda (music-found) > (fold-some-music predicate > (lambda (music . _) (music-found music)) > #f music)))) > > at least if I did not make some thinko here. It is basically the same > code and stack-upwards-only, but hygienic. Nothing can call the > continuation but what is inside. Well, of course fold-some-music could > save the closure calling music-found for later. But it doesn't. > > Is there a way to get a call-with-current-continuation that does not > create a stack copy? IIRC, the stack copying in Guile's continuation implementation is inevitable. Though it's inefficient, the consideration is to cooperate with other languages such as C. > It is fine if it fails with an exception if one > still tries calling the continuation after it has already returned. > > -- > David Kastrup > > > [-- Attachment #2: Type: text/html, Size: 2523 bytes --] ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-02 1:18 ` Nala Ginrut @ 2012-03-02 1:25 ` Noah Lavine 0 siblings, 0 replies; 21+ messages in thread From: Noah Lavine @ 2012-03-02 1:25 UTC (permalink / raw) To: Nala Ginrut; +Cc: David Kastrup, guile-devel Hello, > IIRC, the stack copying in Guile's continuation implementation is > inevitable. Though it's inefficient, the consideration is to cooperate with > other languages such as C. It's inevitable in the general case, where the continuation might return multiple times. However, in this situation, he knows the continuation will only ever return once, so it is not necessary to copy the stack. This control structure will be the equivalent of setjmp and longjmp in C. Prompts have an optimization where they don't actually copy the stack if it is clear that they can only return once. That is why catch and throw are implemented that way. Noah ^ permalink raw reply [flat|nested] 21+ messages in thread
* Re: Non-stack-copying call-with-current-continuation? 2012-03-02 0:00 Non-stack-copying call-with-current-continuation? David Kastrup 2012-03-02 0:20 ` Noah Lavine 2012-03-02 1:18 ` Nala Ginrut @ 2012-03-03 17:41 ` Andy Wingo 2 siblings, 0 replies; 21+ messages in thread From: Andy Wingo @ 2012-03-03 17:41 UTC (permalink / raw) To: David Kastrup; +Cc: guile-devel Hi David, On Fri 02 Mar 2012 01:00, David Kastrup <dak@gnu.org> writes: > Is there a way to get a call-with-current-continuation that does not > create a stack copy? This is usually referred to as `call-with-escape-continuation'. For example, here are Racket's words on the topic: http://docs.racket-lang.org/reference/cont.html#(def._((quote._~23~25kernel)._call-with-escape-continuation)) Here is a good definition of call/ec in Guile: (define (call/ec proc) (let ((tag (make-prompt-tag))) (define (abort . args) (abort-to-prompt tag args)) (call-with-prompt tag (lambda () (proc abort)) (lambda (k args) (apply values args))))) That one won't work in Guile 1.8 though. A portable definition: (define (call/ec proc) (let ((key (gensym "escape "))) (define (abort . args) (throw key args)) (catch key (lambda () (proc abort)) (lambda (key args) (apply values args))))) Regards, Andy -- http://wingolog.org/ ^ permalink raw reply [flat|nested] 21+ messages in thread
end of thread, other threads:[~2012-03-05 1:44 UTC | newest] Thread overview: 21+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2012-03-02 0:00 Non-stack-copying call-with-current-continuation? David Kastrup 2012-03-02 0:20 ` Noah Lavine 2012-03-02 0:42 ` David Kastrup 2012-03-02 1:01 ` Noah Lavine 2012-03-02 1:35 ` David Kastrup 2012-03-02 1:49 ` Noah Lavine 2012-03-02 8:36 ` David Kastrup 2012-03-03 5:03 ` Andreas Rottmann 2012-03-03 5:04 ` Andreas Rottmann 2012-03-03 17:48 ` Andy Wingo 2012-03-04 12:01 ` David Kastrup 2012-03-04 12:15 ` Andy Wingo 2012-03-04 13:59 ` David Kastrup 2012-03-04 18:42 ` Andy Wingo 2012-03-04 18:45 ` Mark H Weaver 2012-03-04 23:13 ` David Kastrup 2012-03-05 0:35 ` Mark H Weaver 2012-03-05 1:44 ` David Kastrup 2012-03-02 1:18 ` Nala Ginrut 2012-03-02 1:25 ` Noah Lavine 2012-03-03 17:41 ` Andy Wingo
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).