Re: [Factor-talk] What exactly is the retain stack?
2014-05-16 0:29 GMT+02:00 Jon Purdy evincarofaut...@gmail.com: Is that it's only use? Then why? dip can easily be formulated using non-retain stack using primitives: For example: a b c [ append ] dip - a b c -rot append swap That implementation assumes the quotation takes two operands and produces one result, which is not always the case. More generally, the functional argument of “dip” is not really supposed to be able to touch the argument it’s operating under. If you don’t have types or a stack checker enforcing this, the formulations with a retain stack or dynamically composing quotations are safe by construction, but the “-rot” version is not. Consider “[ 3drop ] dip” or “[ append dup ] dip”. But factor *does* have a stack checker. Since the stack effect of the quotation given to dip can be inferred, you can always (I think?) rewrite them using nothing but normal stack shuffling operations. Like so: : make-shuffle-effect ( n dir -- effect ) swap 1 + iota swap dupd rotated [ array ] bi@ effect ; : emit-dip ( quot -- ) dup infer [ nip in length -1 make-shuffle-effect , \ shuffle-effect , ] [ swap , , \ call-effect , ] [ nip out length 1 make-shuffle-effect , \ shuffle-effect , ] 2tri ; : rewrite-dip ( quot -- quot' ) first2 drop [ emit-dip ] [ ] make ; [ [ append over ] dip ] rewrite-dip will output the quotation: [ ( 0 1 2 3 -- 3 0 1 2 ) shuffle-effect [ append over ] ( x x x -- x x x ) call-effect ( 0 1 2 3 -- 1 2 3 0 ) shuffle-effect ] Now neither shuffle-effect nor call-effect are Factor primitives but they easily could have been and then dip would only need to touch the data stack. -- mvh/best regards Björn Lindqvist -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs ___ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk
Re: [Factor-talk] What exactly is the retain stack?
Björn Lindqvist bjou...@gmail.com writes: Hi! Is that it's only use? Then why? dip can easily be formulated using non-retain stack using primitives: For example: a b c [ append ] dip - a b c -rot append swap What if the contents of the quotation use more than one item from the stack? How would you implement [ + ] dip, for example? Or [ + + ] dip? etc. etc. Rupert pgpDjqZUFweIY.pgp Description: PGP signature -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs___ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk
Re: [Factor-talk] What exactly is the retain stack?
On Fri, May 16, 2014 at 7:38 AM, Björn Lindqvist bjou...@gmail.com wrote: 2014-05-16 0:29 GMT+02:00 Jon Purdy evincarofaut...@gmail.com: Is that it's only use? Then why? dip can easily be formulated using non-retain stack using primitives: For example: a b c [ append ] dip - a b c -rot append swap That implementation assumes the quotation takes two operands and produces one result, which is not always the case. More generally, the functional argument of “dip” is not really supposed to be able to touch the argument it’s operating under. If you don’t have types or a stack checker enforcing this, the formulations with a retain stack or dynamically composing quotations are safe by construction, but the “-rot” version is not. Consider “[ 3drop ] dip” or “[ append dup ] dip”. But factor *does* have a stack checker. Since the stack effect of the quotation given to dip can be inferred, you can always (I think?) rewrite them using nothing but normal stack shuffling operations. Like so: : make-shuffle-effect ( n dir -- effect ) swap 1 + iota swap dupd rotated [ array ] bi@ effect ; : emit-dip ( quot -- ) dup infer [ nip in length -1 make-shuffle-effect , \ shuffle-effect , ] [ swap , , \ call-effect , ] [ nip out length 1 make-shuffle-effect , \ shuffle-effect , ] 2tri ; : rewrite-dip ( quot -- quot' ) first2 drop [ emit-dip ] [ ] make ; [ [ append over ] dip ] rewrite-dip will output the quotation: [ ( 0 1 2 3 -- 3 0 1 2 ) shuffle-effect [ append over ] ( x x x -- x x x ) call-effect ( 0 1 2 3 -- 1 2 3 0 ) shuffle-effect ] Now neither shuffle-effect nor call-effect are Factor primitives but they easily could have been and then dip would only need to touch the data stack. There are still escape hatches from the static checker, like 'with-datastack', 'clear', 'execute( -- )', etc., and before the compiler comes online, the VM JIT uses a dynamic stack model. The retain stack could however be folded into the callstack, as is traditionally done in Forth, since even the dynamic stack model relies on retain stack balance being preserved. That's one of those little optimizations we never got around to doing. -Joe -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs___ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk
Re: [Factor-talk] What exactly is the retain stack?
Hi Bjorn, The retain stack is used to implement the 'dip' combinator. Slava On Thu, May 15, 2014 at 1:46 PM, Björn Lindqvist bjou...@gmail.com wrote: Hi everyone, I've been walking around in Factors VM for a while and there is a lot of usages and references to the retain stack. But I can't for my life figure out what its purpose is or why anyone ever would want one when there is a perfectly good data stack already available. I only found these two posts by Slava Pestov about it: http://article.gmane.org/gmane.comp.lang.factor.general/1931/match=retain+stack http://factor-language.blogspot.se/2010/07/overhauling-factors-c-library-interface.html In the future, I intend on using GC maps at call sites of Factor words as well, instead of spilling temporary values to the retain stack; then I can eliminate the retain stack altogether, freeing up a register. After this is done the data stack will only be used to pass parameters between words, and not to store temporaries within a word. This will allow more values to be unboxed in more situations, and it will improve accuracy of compiler analyses. So the retain stack is useless? Freeing up a whole register sounds like it should be great for performance, at least on 32 bit x86. -- mvh/best regards Björn Lindqvist -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs ___ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs___ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk
Re: [Factor-talk] What exactly is the retain stack?
So the retain stack is useless? Freeing up a whole register sounds like it should be great for performance, at least on 32 bit x86. You can make a complete stack-based concatenative language with only one stack. But some combinators are implemented more efficiently when you have scratch space to use. Here are some pseudocode reductions. You can implement “dip” as “swap quote cat apply”: 1 2 3 [ + ] dip 1 2 3 [ + ] swap quote cat apply 1 2 [ + ] 3 quote cat apply 1 2 [ + ] [ 3 ] cat apply 1 2 [ + 3 ] apply 3 3 Or you can implement it as “swap retain apply restore”: 1 2 3 [ + ] dip 1 2 3 [ + ] swap retain apply restore 1 2 [ + ] 3 retain apply restore 1 2 [ + ] apply restore 3 restore 3 3 In the former case, you had to allocate a quotation and concatenate two quotations. These can of course be optimised out, but a retain stack has a more efficient naïve operational semantics, and having a “spare” stack for temporary use makes some code a lot nicer without needing to go as far as introducing local variables. -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs ___ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk
Re: [Factor-talk] What exactly is the retain stack?
Hi! Is that it's only use? Then why? dip can easily be formulated using non-retain stack using primitives: For example: a b c [ append ] dip - a b c -rot append swap 2014-05-15 22:49 GMT+02:00 Slava Pestov sl...@factorcode.org: Hi Bjorn, The retain stack is used to implement the 'dip' combinator. Slava On Thu, May 15, 2014 at 1:46 PM, Björn Lindqvist bjou...@gmail.com wrote: Hi everyone, I've been walking around in Factors VM for a while and there is a lot of usages and references to the retain stack. But I can't for my life figure out what its purpose is or why anyone ever would want one when there is a perfectly good data stack already available. I only found these two posts by Slava Pestov about it: http://article.gmane.org/gmane.comp.lang.factor.general/1931/match=retain+stack http://factor-language.blogspot.se/2010/07/overhauling-factors-c-library-interface.html In the future, I intend on using GC maps at call sites of Factor words as well, instead of spilling temporary values to the retain stack; then I can eliminate the retain stack altogether, freeing up a register. After this is done the data stack will only be used to pass parameters between words, and not to store temporaries within a word. This will allow more values to be unboxed in more situations, and it will improve accuracy of compiler analyses. So the retain stack is useless? Freeing up a whole register sounds like it should be great for performance, at least on 32 bit x86. -- mvh/best regards Björn Lindqvist -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs ___ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs ___ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk -- mvh/best regards Björn Lindqvist -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs ___ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk
Re: [Factor-talk] What exactly is the retain stack?
Is that it's only use? Then why? dip can easily be formulated using non-retain stack using primitives: For example: a b c [ append ] dip - a b c -rot append swap That implementation assumes the quotation takes two operands and produces one result, which is not always the case. More generally, the functional argument of “dip” is not really supposed to be able to touch the argument it’s operating under. If you don’t have types or a stack checker enforcing this, the formulations with a retain stack or dynamically composing quotations are safe by construction, but the “-rot” version is not. Consider “[ 3drop ] dip” or “[ append dup ] dip”. You can easily describe the constraint with a type dependent on the arity of the argument type, though. In the current state of Kitten: dip :: ∀R S a. (R a (R → S) → S a) -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs ___ Factor-talk mailing list Factor-talk@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/factor-talk
Re: [Factor-talk] What exactly is the retain stack?
In the current state of Kitten:
Oop, correction: this is not Kitten syntax. I had been writing in
Kitten but decided against it, then forgot to update the text. Current
Kitten would be:
def dip {.r, .s, a}(.r a (.r - .s) - .s a): …
But this is a Factor mailing list. ;)
--
Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
Instantly run your Selenium tests across 300+ browser/OS combos.
Get unparalleled scalability from the best Selenium testing platform available
Simple to use. Nothing to install. Get started now for free.
http://p.sf.net/sfu/SauceLabs
___
Factor-talk mailing list
Factor-talk@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/factor-talk
