In Factor 0.84, accumulate now has stack effect
( seq identity quot -- final newseq ). So you can define your words
as follows:
: accum accumulate swap add ;
: accum1 >r unclip r> accum ;
The old behavior can be got by calling 'accumulate nip'.
Have fun,
Slava
On 6-Aug-06, at 4:45 PM, Boyko Bantchev wrote:
> Hi all,
>
> This is a somewhat lengthy posting -- almost 200 lines --
> in which I take some pains in hope to convince you that the
> present definition of the word accumulate in Factor should
> be changed. I strongly believe that this is advantageous
> to the ability of Factor to deal with sequences.
>
> I start with some general considerations, and then present
> several examples. The examples may be of interest even to
> those of you who do not (at present) actually care how
> exactly accumulate is defined.
>
> Consider the following description of an accumulating
> word accum with an input a sequence s, an initial value
> z, and a quotation q:
> the output of accum is a sequence whose items are the
> results of applying reduce (with the given z and q) on
> all initial subsequences of s, including the empty
> sequence and s itself.
> (If s is empty, the output is a sequence with a single
> item z.)
> That is, accum's input is the same as that of accumulate
> presently in Factor, but the output of the latter differs
> from that of the former in that it misses the last item:
> the result of applying reduce on the whole sequence s.
>
> The following may serve as a model implementation of accum
> (note that this is essentially a single call of reduce with
> a properly chosen quotation):
>
> : accum [ swap dup >r peek swap ] swap add
> [ call r> swap add ] append
>> r >r { } over like r> add r> reduce ;
>
> It makes sense to define also the following word:
>
> : accum1 >r unclip r> accum ;
>
> accum1 is different by not using an initial value: it
> operates solely on the elements of a non-empty sequence,
> and raises an error if the input sequence is empty.
>
> I argue that accum (and accum1) are more natural and more
> useful than accumulate, and that therefore accumulate, as
> presently defined in Factor, should be changed to mirror
> the behaviour of accum. It will be even better if accum1
> is also present in some form as a library-defined word.
> (In my experience, accum1 is even more often needed than
> accum, but as the latter is more general, both should be
> kept.)
>
> Why is accum better than accumulate?
>
> First, note that definitions, more or less equivalent to
> accum or accum1 are present in other languages, such as
> APL, J, K, and Haskell. None of the mentioned languages,
> and hardly any one at all, defines accumulation the way
> Factor does. In Common Lisp, there seems to be no
> accumulating function defined, but there is reduce there,
> and accumulating can be implemented as a call of reduce,
> in the style of the definition of accum above. This close
> relation between reduction and accumulation once more
> suggests that the natural way to accumulate is that of
> accum and accum1, and not that of accumulate.
>
> The presence of accumulating functions in the said languages
> (and others, such as those of the mathematical systems) is
> not accidental: this is what we use to compute cumulative
> sums (or products, or counts etc). Also on this base,
> though with some additional work, we compute running values:
> moving averages and running maximums/minimums are typical
> examples. All these rely on accumulating as in accum or
> accum1, and not as in Factor's accumulate.
>
> In Factor, if you try to find cumulative sums -- say,
> cumulative revenues for six months -- and you have stored
> the values in a six-element array which you pass to
> accumulate, you do not get the correct result. In fact,
> the last input value is not used at all, and the last sum
> you get output is that of the first five months!
>
> In general, the very defining of a word to *not* use some
> of its input is highly suspicious and in most cases a sign
> that something is wrong with the definition. (Because we
> are talking of true computation here, not of shuffling
> combinators whose sole purpose is to move data around the
> stack, and possibly drop some of it.)
>
> Note that in the particular case of a one-element sequence
> the whole of it is discarded, as in this case accumulate
> outputs the ``initial value''. This is all the more wrong
> because the same output is given when the sequence is empty,
> so working on one-element sequences is indistinguishable
> from working on empty ones.
>
> Note also that, when the last item in the output from
> accum is not needed, it is easy to remove it (or to
> apply accum on a shortened sequence) while doing the
> reverse, i.e. computing and adding the needed item to
> the output from accumulate needs more work.
>
> Let me now present several examples of accumulation.
> All of them support the usefulness of the above defined
> accum and accum1.
>
> Parsing postfix expressions
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^
> I do not give any code here, but the idea is clear enough.
> A postfix arithmetic or other expression, consisting of
> values and operators can be parsed as follows. Replace
> each value with 1, and each operator with the difference
> between the number of its outputs and that of its inputs.
> Thus, a unary + or - is replaced by 0, addition by -1 and
> so on. For example, if the expression is a b - c d * +,
> the resulting sequence is 1 1 -1 1 1 -1 -1.
> An expression is correctly formed if the result of applying
> [ + ] accum1 on the encoding sequence for the expression
> only contains positive numbers, and its last member equals
> the number of outputs of the last operator. For the above
> example, we obtain 1 2 1 2 3 2 1, which reflects the fact
> that that expression is correct, whereas x y + - z is
> encoded as 1 1 -1 -1 1, from which we get 1 2 1 0 1 --
> that contains a non-positive value and indeed the expression
> is not correct.
>
> Maximum sum of successive elements
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> This is a well known problem: given a sequence of numbers,
> output the maximal sum of successive elements, or 0 if all
> items are negative. One possible solution is:
> : maxcumsum 0 swap 0 [ + 0 max [ max ] keep ] reduce drop ;
> which only uses reduce. However, the same idea is perhaps
> more clearly expressed as:
> : maxcumsum 0 [ + 0 max ] accum 0 [ max ] reduce ;
>
> Computations with polynomials
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> Consider a polynomial p(x) of one variable. For the sake
> of doing computations on p(x), it is natural to represent
> it as a sequence of coefficients. Computing p at whatever
> point u is conveniently and efficiently expressed using
> Horner's rule and reduction. Define
> : horn [ swap pick * + ] ;
> Then, given u and p,
> : peval 0 horn reduce nip ;
> outputs p(u). For example, if p(x) = 2x^3+3x^2-5x+1
> and u = 2:
> 2 { 2 3 -5 1 } peval
> yields 19.
>
> But what does this have to do with accumulation?
> It is known from school algebra that applying Horner's
> rule gives more than just a single value. Using reduce
> above, we throw away the intermediate results that we
> obtain at the individual iteration steps as we call the
> horn word.
>
> p(x) is uniquely represented: p(x) = q(x).(x-u)+r,
> where the degree of q(x) is one less than that of p(x).
> Apparently r = p(u). Now, define
> : pdiv horn accum1 nip 1 over head* swap peek ;
> and apply it instead of peval on the same data, obtaining
> both q(x) and r = p(u). For the above example,
> 2x^3+3x^2-5x+1 = (2x^2+7x+9)(x-2)+19, i.e. q(x) = 2x^2+7x+9
> and indeed
> 2 { 2 3 -5 1 } pdiv
> outputs { 2 7 9 } 19.
>
> Catalan numbers
> ^^^^^^^^^^^^^^^
> Catalan numbers
> (http://mathworld.wolfram.com/CatalanNumber.html)
> are of the form (2n)!/(n!)^2/(n+1), but there is an
> interesting way to compute them by only using addition.
> The method is based on the so called Catalan triangle
> and can be implemented as follows:
> : cat dup peek [ add ] keep rot ?push swap [ + ] accum1 ;
> : gencat [ cat ] times swap ;
>
> Here are some examples of computing Catalan numbers:
> f { 1 } 10 gencat ! get an array of the first 10 numbers
> drop f swap 5 gencat ! clear those 10, and get another 5
> swap 7 gencat ! add another 7 to those 5
> swap 3 gencat ! add 3 more
>
> Finally, let me observe the following. Reductions and
> accumulations are also useful when done in right-to-left
> order. A number of languages recognize this by providing
> both kinds of functions. Cf. Haskell:
> http://www.haskell.org/onlinereport/standard-prelude.html#$vfoldl ,
> where reduce is ``fold'' and accumulate is ``scan''.
> Also see Common Lisp:
> http://www.lisp.org/HyperSpec/Body/fun_reduce.html ,
> whose function reduce can be adapted for traversion in
> each direction, as well as for using or not using initial
> value. I guess there is no reason why such a variety of
> options would not be beneficial to Factor, too.
>
> Boyko
>
> ----------------------------------------------------------------------
> ---
> Take Surveys. Earn Cash. Influence the Future of IT
> Join SourceForge.net's Techsay panel and you'll get the chance to
> share your
> opinions on IT & business topics through brief surveys -- and earn
> cash
> http://www.techsay.com/default.php?
> page=join.php&p=sourceforge&CID=DEVDEV
> _______________________________________________
> Factor-talk mailing list
> Factor-talk@...
> https://lists.sourceforge.net/lists/listinfo/factor-talk
|