Re: A proper tail version of with-fluids
On Fri 04 Jan 2013 00:36, l...@gnu.org (Ludovic Courtès) writes: Hmm, I can’t see how ‘with-fluids’ or ‘parameterize’ could be tail-recursive given that it uses ‘dynamic-wind’. Am I missing something? It doesn't use dynamic-wind. scheme@(guile-user) ,x (lambda () (with-fluids ((foo 1)) 2)) 0(assert-nargs-ee/locals 0) ;; 0 args, 0 locals 2(toplevel-ref 1);; `foo' 4(make-int8:1) ;; 1 5(wind-fluids 1) 7(make-int8 2) ;; 2 9(unwind-fluids) 10(return) 11(unwind-fluids) 12(return/nvalues) The wind-fluids and unwind-fluids do not use dynamic-wind (though they do use the dynamic stack (dynwind stack)). As you can see the body is inlined. The same for parameterize -- it compiles to with-fluids eventually. Anyway, the trick is to detect with-fluids in a tail position, and to detect recursive tail calls -- and in that case, to update the binding in place, and actually do a tail call instead of pushing a new frame. Andy -- http://wingolog.org/
Re: A proper tail version of with-fluids
You are correct Noha, but please play down the impressed part, we have not reached the goal yet. 1. I did not implement the proper full scale one where we actually can (In case of knowing that no continuation have been stored, get proper tail calls) The reason is that 1. It contains a significant overhead, 2. I'm yet a little ignorant about the inner workings of guile fluids. But in principle, one add meta information to the fluids so that one can know that it's safe to overwrite the old fluid. 2. The one I implemented was simply pushing things on the dynstack located on the heap. This still saves a lot of memory because the function stack was handled more optimal because we used the tail call mechanism. The trick was to be able to unwind automatically in a correct way when we issue a return. 3. Although I coded a version that should mix well with continuations, I haven't tested it yet. /Stefan On Fri, Jan 4, 2013 at 12:44 AM, Noah Lavine noah.b.lav...@gmail.comwrote: I think with-fluids could at least be semi-tail-recursive. If you imagine a normal non-tail-recursive implementation, you might get to a point where your continuation is going to set a fluid back to a value, and then the *next* continuation is going to set that fluid back to *another* value. Since these are only set!s and have no side-effects, you could somehow notice that and not do the first set!. So your continuation only needs to have one set! for each fluid, no matter how many times that fluid is changed by with-fluids. But that seems tricky to implement. I haven't looked at how Stefan did it, but I'm impressed. Noah On Thu, Jan 3, 2013 at 6:36 PM, Ludovic Courtès l...@gnu.org wrote: Hi Stefan, Stefan Israelsson Tampe stefan.ita...@gmail.com skribis: (define f (lambda (n) (if (= n 0) (fluid-ref a) (with-fluids ((a n)) (f (- n 1)) with the modified VM: scheme@(guile-user) (f 1000) $2 = 1 with the old VM, it craches. It works! Hmm, I can’t see how ‘with-fluids’ or ‘parameterize’ could be tail-recursive given that it uses ‘dynamic-wind’. Am I missing something? Ludo’.
Re: A proper tail version of with-fluids
Hi Stefan, Stefan Israelsson Tampe stefan.ita...@gmail.com skribis: (define f (lambda (n) (if (= n 0) (fluid-ref a) (with-fluids ((a n)) (f (- n 1)) with the modified VM: scheme@(guile-user) (f 1000) $2 = 1 with the old VM, it craches. It works! Hmm, I can’t see how ‘with-fluids’ or ‘parameterize’ could be tail-recursive given that it uses ‘dynamic-wind’. Am I missing something? Ludo’.
Re: A proper tail version of with-fluids
I think with-fluids could at least be semi-tail-recursive. If you imagine a normal non-tail-recursive implementation, you might get to a point where your continuation is going to set a fluid back to a value, and then the *next* continuation is going to set that fluid back to *another* value. Since these are only set!s and have no side-effects, you could somehow notice that and not do the first set!. So your continuation only needs to have one set! for each fluid, no matter how many times that fluid is changed by with-fluids. But that seems tricky to implement. I haven't looked at how Stefan did it, but I'm impressed. Noah On Thu, Jan 3, 2013 at 6:36 PM, Ludovic Courtès l...@gnu.org wrote: Hi Stefan, Stefan Israelsson Tampe stefan.ita...@gmail.com skribis: (define f (lambda (n) (if (= n 0) (fluid-ref a) (with-fluids ((a n)) (f (- n 1)) with the modified VM: scheme@(guile-user) (f 1000) $2 = 1 with the old VM, it craches. It works! Hmm, I can’t see how ‘with-fluids’ or ‘parameterize’ could be tail-recursive given that it uses ‘dynamic-wind’. Am I missing something? Ludo’.