# gendip combinator

## Greg Buchholz — 2005-10-21 22:55:52

    After having come down with a case of the stack shuffling blues, I

    started exploring options for evaluating functions deeper inside the

    stack.  The first thing I came up with is something I'm temporarily

    calling "gendip", for "generalized dip".  The basic idea is that we have

    a list of combinators which we apply to corresponding elements of the

    stack.  Think of zipWith in Haskell (or mapcar in lisp) where we apply a

    function to the elements in two lists at the same position.  In this case

    the function will be the i combinator, one of the lists will be the

    stack, and the other list will be a list of functions to be applied to

    the individual stack items.  Here are a couple of examples...

        1 2 3 [[pred] [dup *] [12 +]] gendip

    ...would yield a stack of...

        0 4 15

    ...or...

        ["foo" "bar" "baz"] 42   3.14    [+]

        [            [size] [] [2.718] [pop] ] gendip

    ...resulting in...

        3 42 3.14 2.718

    ...This does a little damage the concatenative properties of a program

    though, since we're packing more of our program into quotations.  But it

    seems nicer than Forth-like local variables.  You could also think of it

    kind-of-like a parallel execution combinator, since each separate

    combinator in the list could be run in parallel and the results

    collected and placed in the stack at the end.

      Anyway, here's what the "annoying" quadratic formula looks like with

    gendip...

    (*stack =>    a b c    *)

    quad ==      rolldown

    (*stack =>    b c a    *)

              [[neg dup sqr] [] [dup [4 *] dip         2 *]] gendip

    (*stack =>   -b     b^2  c         4a               2a         *)

                                          [* - sqrt +-]    dip [/] cons map;

    ...The next combinator I came up with I'm calling "group".  It takes a

    template and conses up lists according to the specification in the

    template...

        1 2 3 4 [[x x] [x x]] group

    ...gives...

        [1 2] [3 4]

    ...and...

        1 2 3 4 [x [x x] x] group

    ...results in...

        1 [2 3] 4

    ...and combining the two functions a little...

        1 2 3 4 5 6 [[x x]                    x  x  x  x ] group

                    [[uncons uncons pop swap] [] [] [] []] gendip

    ...yields...

        2 1 3 4 5 6

    ...the "x" combinator used there has no special meaning, you could

    replace it with anything other than a list (i.e. a number, a string,

    etc.)

      I thought I'd ask the catenative community for their thoughts.   Does

    any concatenative language currently have similar functions?  If so, are

    there any drawbacks or advantages compared to stack shuffling?  Do you

    think they would be generally useful?  Would it be better if the

    semantics were slightly different? Is there a better name than "gendip"?

    Maybe "para" for its parallel nature, or "zipdip"?  Attached is a Joy

    program with all the definitions and a few examples that you can run.

    Greg Buchholz

    __________________________________

    Yahoo! FareChase: Search multiple travel sites in one click.

    http://farechase.yahoo.com

    [Non-text portions of this message have been removed]

## Greg Buchholz — 2005-10-21 23:10:31

    (* Yahoo apparently ate my attachment.  The code is below, or you can *)

    (* grab it at...  http://sleepingsquirrel.org/almost/zipdip.joy  *)

    DEFINE

    reverse == [[]] [""] iflist swap shunt;

    shunt == [swons] step;

    flatten == [null] [] [uncons] [concat] linrec;

    zipit == [null] (* empty list of functions? *)

             [pop [] cons]  (* then pop it off and unitlist the rest of stack

    *)

             [ [uncons [[] cons] dip] dip uncons swapd  (* [s] ss x xs -> [s]

    x ss xs *)

               [[infra] dip] dip

               zipit cons] ifte ;

    gendip == [stack] dip reverse zipit flatten unstack ;

    gsize == [size] [1] iflist ;

    splitAt == [] swap [[uncons] dip swapd cons] times ;

    gprime == [null] [pop ]

               [uncons [splitAt [size 1 =] [uncons pop] [] ifte] dip swap

                 [gprime] dip swap cons ] ifte ;

    group == [stack] dip reverse [gsize] map (* turn template into list of

    lengths *)

             gprime unstack ;

    +- == [[+] [-]] [i] map ;

    sqr == dup * ;

    (*stack =>    a b c    *)

    quad ==      rolldown

    (*stack =>    b c a    *)

              [[neg dup sqr] [] [dup [4 *] dip         2 *]] gendip

    (*stack =>   -b     b^2  c         4a               2a         *)

                                          [* - sqrt +-]    dip [/] cons map;

    showstack == stack reverse

    .

    "gendip examples...\n" putchars

    "foo" "bar" 1 2 3 [[pred] [dup *] [12 +]] gendip showstack.

    [] unstack

    ["foo" "bar" "baz"] 42 3.14 [+] [[size] [] [2.718] [pop]] gendip

    showstack.

    [] unstack

    "\ngrouping examples...\n" putchars

    1 2 3 4 [[x x] [x x]] group showstack.

    [] unstack

    1 2 3 4 5 6 7 [[x x x] x [x x]] group showstack.

    [] unstack

    1 2 3 4 5 6 [[x x] x x x x] group [[uncons uncons pop swap] [] [] [] []]

    gendip

    showstack.

    "\nquadradic formula...\n" putchars

    [] unstack

    1 0 -2 quad .

    __________________________________

    Yahoo! FareChase: Search multiple travel sites in one click.

    http://farechase.yahoo.com

## Greg Buchholz — 2005-10-22 00:51:21

    --- Greg Buchholz <sleepingsquirrel@...> wrote:

     >   I thought I'd ask the catenative community for their thoughts.   Does

    > any concatenative language currently have similar functions?

         There is truly nothing new under the sun.  Back in the original

    "Annoying Quadratic Formula" thread, Ivan Tomac and John Carter discuss

    pretty much this very thing, calling it "thread"...

       http://groups.yahoo.com/group/concatenative/message/2184

       http://groups.yahoo.com/group/concatenative/message/2185

    I guess if it is a good wheel, everyone will reinvent it.

    Greg Buchholz

    __________________________________

    Yahoo! Mail - PC Magazine Editors' Choice 2005

    http://mail.yahoo.com

## Mackenzie Straight — 2005-10-22 01:47:24

    On 10/21/05, Greg Buchholz <sleepingsquirrel@...> wrote:

     >   I thought I'd ask the catenative community for their thoughts.   Does

    > any concatenative language currently have similar functions?

     Something like this, perhaps?

    http://paste.lisp.org/display/11003

    It uses Factor's stack effect inference.

## Greg Buchholz — 2005-10-22 16:11:48

    --- Mackenzie Straight <eizneckam@...> wrote:

     >

    > Something like this, perhaps?

    >

         Yep.  Do you find it reduces the amount of stack shuffling you need?

    Greg Buchholz

    __________________________________

    Yahoo! Mail - PC Magazine Editors' Choice 2005

    http://mail.yahoo.com

## Greg Buchholz — 2005-10-24 22:58:23

    While doing some more thinking after my posting on gendip, I thought

    I'd also throw "combinator_lisp" out there for discussion.  If a Joy

    program is a list of combinators, a "combinator_lisp" program is a tree

    of combinators.  See below for a function which evaluates a lambda-less

    postfix lisp dialect.  Again, I think you could use something like this

    to reduce the need for stack shuffling, at the cost of some loss of

    concativity.  If nothing else the defintion is pleasantly concise.  One

    drawback of the implementation below is that you can't refer directly to

    literal lists, since "combinator_lisp" would attempt to evaluate them

    (And I haven't yet come up with a nice clean alternative).

        If you think of Joy combinators are function from stacks to stack, I

    wonder if a useful language of combinators could be defined from trees to

    trees.  Thoughts?

    Greg Buchholz

    (* begin combinator lisp *)

    DEFINE

    reverse == [[]] [""] iflist swap shunt;

    shunt == [swons] step;

    flatten == [null] [] [uncons] [concat] linrec;

    showstack == stack reverse;

    combinator_lisp == lisp uncons pop ;

    lisp ==

        [ reverse uncons  (* grab "last item" in list and rest of list     *)

          [lisp] map      (* recursively eval the elements in rest of list *)

          flatten

          swap [] [[] cons] iflist (* if "last item" is bareword then quote*)

          infra ]            (* apply the "last item" to the argument list *)

        [[] cons] iflist  (* if expression is a list, then eval, else

    quote*);

    empty_list == [] ;

    .

    [[1 2 -] [3 [dup *]] +] combinator_lisp .  (* evaluates to: 8       *)

    [42 [3 sqrt] *] combinator_lisp .          (* evaluates to: 72.7461 *)

    ["abc" [empty_list] cons] combinator_lisp .(* evaluates to: ["abc"] *)

    [3.14 2 [* [empty_list] cons] i] combinator_lisp . (* eval to: 6.28 *)

    (* end of combinator lisp *)

    __________________________________

    Yahoo! Mail - PC Magazine Editors' Choice 2005

    http://mail.yahoo.com

## Greg Buchholz — 2005-10-25 21:54:09

    As long as I'm on a roll, here's one more attempt at cleaning up the

    quadratic formula.  This procedure is related to a reader/state monad.

    We create an alternate parallel universe with a separate stack and

    functions for communicating between the universes.  You use the "indip"

    combinator to execute quotations on the alternative stack.  Special

    helper functions are needed to move values from the real stack to the

    fake one.  This works great for pushing "formal" parameters around at

    will without stack shuffling...

    DEFINE

    fst == first ;

    snd == rest first ;

    thd == rest rest first;

    (* helper functions which take elements from our argument *)

    (* list and pushing them onto the alternate stack         *)

    a == uncons uncons [[dup fst] dip cons] dip cons cons ;

    b == uncons uncons [[dup snd] dip cons] dip cons cons ;

    c == uncons uncons [[dup thd] dip cons] dip cons cons ;

    +- == [[+] [-]] [i] map ;

    setup == [] swap [cons] times [] [] cons cons ;

    tear_down == rest first first ;

    quad == 3 setup (* three arguments from stack *)

               b [neg dup dup *] indip a c [4 * * - sqrt +- ] indip

               a [ 2 * [/] cons map] indip

            tear_down; (* grab the top item on alternate stack *)

    indip == [uncons first] dip infra [] cons cons;

    .

    6 7 8 9 4 setup .                (* result => [[6 7 8 9] []]*)

    [[1 2 3] []] b .                 (* result => [[1 2 3] [2]] *)

    [[1 2 3] []] b c a [+ *] indip.  (* result => [[1 2 3] [8]] *)

    1 0 -2 quad .                    (* result => [1.414 -1.414]*)

    __________________________________

    Yahoo! Mail - PC Magazine Editors' Choice 2005

    http://mail.yahoo.com

## Greg Buchholz — 2005-10-26 00:12:19

    Here's one more improvement.  Using strings to look up formal

    parameter values from an association list.  This prevents the global

    namespace pollution present in the last message (function a,b, and c).

    This is a pretty far cry from a traditional concatenative approach.  Is

    it too far out there?  And on an unrelated note, are there better ways to

    manipulate and edit quotations compared to the "edit" function below?

    DEFINE

    uncons2   ==  [uncons ] dip uncons  swapd ;

    null2  ==  [null] [true] [pop null] ifte ;

    pairlist    ==  [] cons cons ;

    zip == [ null2 ]

           [ pop pop [] ]

           [ uncons2 ]

           [ [pairlist] dip cons ] linrec ;

    reverse == [[]] [""] iflist swap shunt;

    shunt == [swons] step;

    lookup == [= [swap pop first] [pop] branch] cons [unswons] swap concat

              "No Match" swap fold;

    (* look up string names in environment and push on alternate stack *)

    @ == [uncons uncons [[dup "REPLACE_ME" lookup] dip cons] dip cons cons]

         swap edit i;

    edit == [pop] cons reverse ["REPLACE_ME" =] swap [[] ifte] cons cons

            [map] treerec;

    +- == [[+] [-]] [i] map ;

    setup2 == dup size swap [[] swap [cons] times] dip swap zip [] [] cons

    cons ;

    tear_down == rest first first ;

    quad == ["a" "b" "c"] setup2 (* name three arguments on stack *)

               "b" @ [neg dup dup *] indip "a" @ "c" @ [4 * * - sqrt +- ]

               indip "a" @ [ 2 * [/] cons map] indip

            tear_down; (* grab the top item on alternate stack *)

    indip == [uncons first] dip infra [] cons cons;

    .

    1 0 -3 quad .

    __________________________________

    Yahoo! Mail - PC Magazine Editors' Choice 2005

    http://mail.yahoo.com

## phimvt@lurac.latrobe.edu.au — 2005-10-28 06:15:23

    On Mon, 24 Oct 2005, Greg Buchholz wrote:

    [..]

    >     If you think of Joy combinators are function from stacks to stack, I

    > wonder if a useful language of combinators could be defined from trees to

    > trees.  Thoughts?

    Trees can be representedd as lists possibly containing other lists

    possibly containing .. . The Joy stack is a list possibly containing

    lists possibly containing .. . So Joy is already a language in which

    programs denote functions from trees to trees. Two combinators are

    particularly useful for digging into the tree: [P] dip will go down

    the stack to execute P and then restore the top item, and [P] infra

    will treat a list on top as the stack and return the modified list.

    There is also the operator called stack, which pushes the whole stack

    as a list, and the operator unstack which does the reverse. So all

    tree operations can aready be done. Whether there are any other

    generally useful operators and combinators specifically for trees

    I do not know - I have not come across any occasions where they could

    be useful. But it it an interesting question.

    > (* begin combinator lisp *)

    >

    > DEFINE

    >

    > reverse == [[]] [""] iflist swap shunt;

    > shunt == [swons] step;

    > flatten == [null] [] [uncons] [concat] linrec;

    > showstack == stack reverse;

    >

    > combinator_lisp == lisp uncons pop ;

    > lisp ==

    >     [ reverse uncons  (* grab "last item" in list and rest of list     *)

    >       [lisp] map      (* recursively eval the elements in rest of list *)

    >       flatten

    >       swap [] [[] cons] iflist (* if "last item" is bareword then quote*)

    >

    >       infra ]            (* apply the "last item" to the argument list *)

    >     [[] cons] iflist  (* if expression is a list, then eval, else

    quote*);

    >

    > empty_list == [] ;

    > .

    Your combinator_lisp is essentially an evaluator for a postfix version of

    Lisp without lambda abstractions. I was going to write: "But technically

    it is not a combinator since it takes as argument not a Joy program that

    it executes". That isn't quite correct either,since your lisp does use the

    Joy evaluator to evaluate each part of the lisp program. An interesting

    borderline case. (You are no doubt aware that it would be just as easy

    to let the lisp use prefix order.)

    But I now see that there could be all sorts of combinators which take

    trees as arguments and execute various parts of them. As you suggest,

    they could be quite different from the usual Joy combinators which take

    a fixed number of quotations and execute them without further analysis.

    You have found yourself an interesting research topic, I would say.

    Keep it up.

      - Manfred

## Greg Buchholz — 2005-10-28 19:51:22

    --- phimvt@... wrote:

     >

    > But I now see that there could be all sorts of combinators which take

    > trees as arguments and execute various parts of them. As you suggest,

    > they could be quite different from the usual Joy combinators which take

    > a fixed number of quotations and execute them without further analysis.

     Here's another possible example.  In Joy-like lanugage, if you have a

    stack of [1,2,3] and you apply the "+" combinator, you get a new stack

    [1,5].  Now let's say you have a tree based language and are given an

    initial tree like...

             1

            / \

           2   3

          / \   \

         4   5   6

    ...what tree results after applying the "+" combinator?  Maybe you need

    to add a modifier to each combinator to tell it which direction to take

    arguments from (left branches vs. right branches).  Then if you apply

    "+r" you'd get...

             4

            / \

           2   6

          / \

         4   5

    ...or some-such.  And if your combinator needs more than 2 arguments, you

    keep appending direction modifiers, like "iftelr"...

             [false branch]

              /           \

        [true branch]     42

         /          \

       ["foo"]     [predicate]

                    /        \

    ...Then that starts sounding like a zipper

    (http://www.haskell.org/hawiki/TheZipper).  Maybe with this sort of

    scheme you could reduce the number of "stack" shufflers for any given

    operation from O(n) to O(log n).

    Greg Buchholz

    __________________________________

    Yahoo! FareChase: Search multiple travel sites in one click.

    http://farechase.yahoo.com

## phimvt@lurac.latrobe.edu.au — 2005-10-31 04:12:52

    On Fri, 28 Oct 2005, Greg Buchholz wrote:

    [..]

    > Here's another possible example.  In Joy-like lanugage, if you have a

    > stack of [1,2,3] and you apply the "+" combinator, you get a new stack

    > [1,5].  Now let's say you have a tree based language and are given an

    > initial tree like...

    >

    >          1

    >         / \

    >        2   3

    >       / \   \

    >      4   5   6

    >

    > ...what tree results after applying the "+" combinator?  Maybe you need

    > to add a modifier to each combinator to tell it which direction to take

    > arguments from (left branches vs. right branches).  Then if you apply

    > "+r" you'd get...

    >

    >          4

    >         / \

    >        2   6

    >       / \

    >      4   5

    >

    The +r operator would be easy to implement in current Joy, provided

    the original binary tree is implemented as

        [1  [2 [4] [5]]  [3 [] [6]] ]

    > ...or some-such.  And if your combinator needs more than 2 arguments, you

    > keep appending direction modifiers, like "iftelr"...

    >

    >          [false branch]

    >           /           \

    >     [true branch]     42

    >      /          \

    >    ["foo"]     [predicate]

    >                 /        \

    >

    > ...Then that starts sounding like a zipper

    > (http://www.haskell.org/hawiki/TheZipper).  Maybe with this sort of

    > scheme you could reduce the number of "stack" shufflers for any given

    > operation from O(n) to O(log n).

    I started reading Oleg's paper, Google: "Zipper in Scheme", but I have

    not fully understood it yet. But it may be more relevant because Joy

    resembles Lisp/Scheme (weakly dynamically typed) more than ML/Haskell

    (strongly statically typed).

    A related idea was to add a "current-position/current-node pointer to

    lists (and hence trees implemented as recursive lists). The idea is

    familiar from text editors, which have a current insertion/deletion

    pointer which moves around, partly under user control, partly

    automatically. In Joy, to move a pointer around a list you can treat

    the list as two lists, one forward and backwards. To move a pointer

    you shift (shunt a single element) from one to the other. But I have

    never found any use for such a thing - except perhaps for implementing

    a Turing machine tape. Presumably a similar idea can be adapted for

    recursive lists and hence for trees. Your tree combinators could

    utilise such pointers.

    Keep us posted with your ideas.

      - Manfred

## William Tanksley, Jr — 2005-12-07 03:06:00

    On 10/25/05, Greg Buchholz <sleepingsquirrel@...> wrote:

     >    As long as I'm on a roll, here's one more attempt at cleaning up the

    > quadratic formula.

     Sorry to hijack your message, but I just wanted to bring up a point I

    realised at work today.

    I've often said that concatenative languages have their advantages,

    but it seems consensus that math is just an area where concatenative

    languages will always be second-best. Well, I just hit a problem for

    which concatenative thinking provided an immediately obvious and very

    elegant solution for a mathematical problem.

    The challenge was to use a single-variable polynomial (18th order) to

    approximate a function simulating something in the real world. The

    equation was something like

    y = 1.5 * (1.2 - 0.03x^2 - 0.02x^4 - 0.0076x^6 ... );

    If you're thinking in C, it's obvious how to implement that -- it

    would look mostly like the equation. But how would you implement it in

    a concatenative language? Please feel free to invent your coefficients

    (like I just did), and don't worry about matching mine. Optimise for

    number of multiplication operations and runtime memory.

    -Billy

## Greg Buchholz — 2005-12-07 18:38:20

    --- "William Tanksley, Jr" <wtanksleyjr@...> wrote:

     > If you're thinking in C, it's obvious how to implement that -- it

    > would look mostly like the equation. But how would you implement it in

    > a concatenative language? Please feel free to invent your coefficients

    > (like I just did), and don't worry about matching mine. Optimise for

    > number of multiplication operations and runtime memory.

       OK. Not optimized at all, but here's my "obvious" stab at the problem.

    It stores the coefficients in a list and uses a few list munging helper

    functions.  Ignoring the library functions needed, "poly_eval" seems

    reasonably concise.

    DEFINE

    (* Yes, this ugly and inefficient definition of unfold *)

    (* needs to be cleaned up badly                        *)

    unfold == xpfgTOxpfgxp i [xpfgTO []] [xpfgTOxpfgxf i

                                          xpfgaTOxpfgaxg i

                                          xpfgabTOabpfg unfold cons] branch ;

    xpfgTOxpfgxp == [] cons cons [[] cons cons dup uncons uncons pop

    rolldown] dip

                    swap [uncons uncons pop] dip uncons uncons pop ;

    xpfgTOxpfgxf == [] cons cons cons dupd swap [uncons uncons uncons pop]

    dip

                    [] cons cons dupd swap [uncons uncons pop] dip ;

    xpfgaTOxpfgaxg == [] cons cons cons cons dupd swap

                         [uncons uncons uncons uncons pop] dip

                      [] cons cons dupd swap [uncons uncons pop] dip ;

    xpfgabTOabpfg == [] cons cons cons cons cons swap pop uncons uncons

    uncons

                        [[] cons cons cons] dip swap [uncons uncons pop] dip

                     uncons uncons uncons pop ;

    xpfgTO == pop pop pop pop ;

    enumFromTo == [>] cons [id] [1 +] unfold ;

    uncons2 ==  [uncons ] dip uncons  swapd ;

    null2   ==  [null] [true] [pop null] ifte ;

    pop2    == pop pop;

    zipwith == [ [null2] [pop2 []] [uncons2] ] dip

               [dip cons] cons

               linrec ;

    sum == 0 [+] fold ;

    poly_eval == dup size 1 -                (* order of polynomial *)

                 0 swap enumFromTo swapd [pow] map   (* powers of x *)

                 swap pop                  (* get rid of unneeded x *)

                 [*] zipwith           (* multiply coeffs by powers *)

                 sum ;                              (* add up terms *)

              (* x^0  x^1   x^2   x^3   x^4    x^5   x^6   *)

    coeffs == [  1.2  0.0  -0.03  0.0  -0.02   0.0  -0.0076 ] ;

    END

    (* evaluate the polynomial described by the list in coeffs at *)

    (* at the value x=10 *)

    10 coeffs poly_eval 1.5 * .

    __________________________________________

    Yahoo! DSL  Something to write home about.

    Just $16.99/mo. or less.

    dsl.yahoo.com

## Mackenzie Straight — 2005-12-07 21:23:45

    On 12/6/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

     > If you're thinking in C, it's obvious how to implement that -- it

    > would look mostly like the equation. But how would you implement it in

    > a concatenative language? Please feel free to invent your coefficients

    > (like I just did), and don't worry about matching mine. Optimise for

    > number of multiplication operations and runtime memory.

     Factor:

    <slava_> here is my polynomial evaluator:

    <slava_> : powers ( x n -- { 1 x x^2 x^3 ... } ) 1 swap [ drop [ dupd

    * ] keep ] map 2nip ;

    <slava_> : polyval ( x p -- p[x] ) [ powers ] keep v. ;

    (OT) K:

    <eiz> The K equivalent to Greg's function is +/y*x^!#y

    (Actually, y _dot x^!#y should use less memory...)

## Mackenzie Straight — 2005-12-08 15:43:18

    On 12/7/05, Mackenzie Straight <eizneckam@...> wrote:

     > (OT) K:

    > <eiz> The K equivalent to Greg's function is +/y*x^!#y

    >

    > (Actually, y _dot x^!#y should use less memory...)

    >

     (Still OT, but stevan might like this one:) x _sv|y

## William Tanksley, Jr — 2005-12-15 05:26:11

    William Tanksley, Jr <wtanksleyjr@...> wrote:

     > I've often said that concatenative languages have their advantages,

    > but it seems consensus that math is just an area where concatenative

    > languages will always be second-best. Well, I just hit a problem for

    > which concatenative thinking provided an immediately obvious and very

    > elegant solution for a mathematical problem.

     Good work, all; but you're elegantly solving the wrong problem. It's

    my fault for a lack of explanation.

     > The challenge was to use a single-variable polynomial (18th order) to

    > approximate a function simulating something in the real world. The

    > equation was something like

    > y = 1.5 * (1.2 - 0.03x^2 - 0.02x^4 - 0.0076x^6 ... );

    > If you're thinking in C, it's obvious how to implement that -- it

    > would look mostly like the equation. But how would you implement it in

    > a concatenative language? Please feel free to invent your coefficients

    > (like I just did), and don't worry about matching mine. Optimise for

    > number of multiplication operations and runtime memory.

     Notice the last sentance. If you haven't counted the number of

    multiplications, you haven't solved this problem. As another note,

    you're free to invent very general polynomial frameworks, but the

    important thing is to evaluate a single polynomial, not all possible

    ones. I'm working under time and space constraints. If you invent a

    general polynomial evaluation library you'll still get partial credit

    if you use the right algorithm, and do so in a way that (as I

    mentioned) looks more natural in a concatenative language than it does

    in an infix one.

    Remember, time and space are of the essence. If you've started consing

    a list, you're heading in the wrong direction. Accuracy and numeric

    stability are also important.

    -Billy

## janvanlent — 2005-12-15 14:59:57

    --- In concatenative@yahoogroups.com, "William Tanksley, Jr"

     >>The challenge was to use a single-variable polynomial (18th order) to

    >>>>approximate a function simulating something in the real world. The

    >>>>equation was something like

    >>>>y = 1.5 * (1.2 - 0.03x2 - 0.02x4 - 0.0076x6 ... );

    >

    >>

    >>

    >

    >>>>If you're thinking in C, it's obvious how to implement that -- it

    >>>>would look mostly like the equation. But how would you implement it in

    >>>>a concatenative language? Please feel free to invent your coefficients

    >>>>(like I just did), and don't worry about matching mine. Optimise for

    >>>>number of multiplication operations and runtime memory.

     Evaluation of

    y = 1.5 * ( 1.2 - 0.03x2 - 0.02x4 - 0.0076x6 )

    in Factor. This uses Horner's rule.

    The general case:

    : ep1 ( x -- y )

      0.0076 over * over * 0.02 + over * over * 0.03 + over * over * 1.2 +

      1.5 *  nip ;

    Using the fact that it is a polynomial in x2:

    : ep2 ( x -- y )

      dup * 0.0076 over * 0.02 + over * 0.03 + over * 1.2 + 1.5 * nip ;

    The last multiplication in each definition can be removed by

    distributing it over the coefficients.

    It shouldn't be too hard to write a word that compiles a list of

    coefficients into the sequence of instructions that performs the

    evaluation. E.g. in Factor:

    : ep1 ( x -- y )

      [ 0.0076 0 0.02 0 0.03 0 1.2 ] compile-horner 1.5 * ;

    : ep2 ( x -- y )

      dup * [ 0.0076 0.02 0.03 1.2 ] compile-horner 1.5 * ;

    Or using a defining word:

    :horner ep1_ 0.0076 0 0.02 0 0.03 0 1.2  ;

    : ep1 ( x -- y ) ep1_ 1.5 * ;

    Something similar can be done in Forth.

    jan

## William Tanksley, Jr — 2005-12-16 03:10:07

    janvanlent <jan.vanlent+concatenative@...> wrote:

     > --- In concatenative@yahoogroups.com, "William Tanksley, Jr"

    > >>The challenge was to use a single-variable polynomial (18th order) to

    > >>>>approximate a function simulating something in the real world. The

    > >>>>equation was something like

    > >>>>y = 1.5 * (1.2 - 0.03x2 - 0.02x4 - 0.0076x6 ... );

    > >>>>If you're thinking in C, it's obvious how to implement that -- it

    > >>>>would look mostly like the equation. But how would you implement it in

    > >>>>a concatenative language? Please feel free to invent your coefficients

    > >>>>(like I just did), and don't worry about matching mine. Optimise for

    > >>>>number of multiplication operations and runtime memory.

    > Evaluation of

    > y = 1.5 * ( 1.2 - 0.03x2 - 0.02x4 - 0.0076x6 )

    > in Factor. This uses Horner's rule.

     Perfect. Full credit for numeric stability and optimization in all

    criteria: memory, multiplications, and use of concatenativity. :-)

     > Using the fact that it is a polynomial in x2:

    > : ep2 ( x -- y )

    >   dup * 0.0076 over * 0.02 + over * 0.03 + over * 1.2 + 1.5 * nip ;

     Yup, that's pretty much what I was thinking. I would consider naming

    "over *" as "x*" or something. But I see this as nice for

    concatenativity, because it so happens that the easiest (most

    consistent) way to write this formula in a concatenative language is

    also numerically stable and fast. I guess my point was just that

    syntax-heavy languages don't always have ALL the advantages :-).

    (Admittedly, having syntax IS an advantage wherever that syntax is

    tailored to the job at hand-- Fortran, for example.)

    By the way, for those not familiar with Horner's, what happened here

    was that he rewrote the polynomial from something like:

    p(x) = ax^3 + bx^2 + cx + d

    to:

    p(x) = (((a)x + b)x + c)x + d

    Using my definition of "x*", this is (almost) as simple as "a x* b +

    x* c + x* d +". Adding more coefficients is done in the obvious way.

    If you read RPN, which is as natural as algebraic once you know it,

    it's at least as clear to read as the naive algebraic method.

     > It shouldn't be too hard to write a word that compiles a list of

    > coefficients into the sequence of instructions that performs the

    > evaluation. E.g. in Factor:

     True true.

     > jan

     -Billy

## John Cowan — 2005-12-16 03:29:19

    William Tanksley, Jr scripsit:

     > By the way, for those not familiar with Horner's, what happened here

    > was that he rewrote the polynomial from something like:

    >

    > p(x) = ax^3 + bx^2 + cx + d

    >

    > to:

    >

    > p(x) = (((a)x + b)x + c)x + d

     This is the same approach used to convert digit-strings to numbers left to

    right: add the next digit, quit if no more, multiply by ten, repeat.

    --

    A rabbi whose congregation doesn't want         John Cowan

    to drive him out of town isn't a rabbi,         http://www.ccil.org/~cowan

    and a rabbi who lets them do it                 cowan@...

    isn't a man.    --Jewish saying                 http://www.reutershealth.com

## Rodney Price — 2005-12-16 05:26:17

    Presumably this is what you're looking for? (from the Mathematica

    documentation)

    --

    Any polynomial can be rewritten in Horner, or nested, form.

    p(x) = a[0] x^n + ... + a[n-1] x + a[n]

          = ((...(a[0] x + a[1]) x + a[2]) x + ... + a[n-1]) x + a[n]

    Assume that x^n can be calculated using only log_2(n) multiplications

    for integer n. For a polynomial of degree n, the Horner form requires

    n multiplications and n additions. The expanded form, however,

    requires log_2(Gamma(1+n)) multiplications, which is already more

    than twice as expensive for a polynomial of degree 10. Thus, one

    advantage of Horner form is that the work involved in exponentiation

    is distributed across addition and multiplication, resulting in

    savings of some basic arithmetic operations. Another advantage is

    that Horner form is more stable to evaluate numerically when compared

    with the expanded form. The reason for this is that each sum and

    product involve quantities which vary on a more evenly distributed

    scale.

    --

    Yes, Horner form does look easy to adapt to a stack-based language.

    -Rod

     On Dec 14, 2005, at 10:26 PM, William Tanksley, Jr wrote:

    > William Tanksley, Jr <wtanksleyjr@...> wrote:

    >> I've often said that concatenative languages have their advantages,

    >> but it seems consensus that math is just an area where concatenative

    >> languages will always be second-best. Well, I just hit a problem for

    >> which concatenative thinking provided an immediately obvious and very

    >> elegant solution for a mathematical problem.

    >

    > Good work, all; but you're elegantly solving the wrong problem. It's

    > my fault for a lack of explanation.

    >

    >> The challenge was to use a single-variable polynomial (18th order) to

    >> approximate a function simulating something in the real world. The

    >> equation was something like

    >> y = 1.5 * (1.2 - 0.03x^2 - 0.02x^4 - 0.0076x^6 ... );

    >

    >> If you're thinking in C, it's obvious how to implement that -- it

    >> would look mostly like the equation. But how would you implement

    >> it in

    >> a concatenative language? Please feel free to invent your

    >> coefficients

    >> (like I just did), and don't worry about matching mine. Optimise for

    >> number of multiplication operations and runtime memory.

    >

    > Notice the last sentance. If you haven't counted the number of

    > multiplications, you haven't solved this problem. As another note,

    > you're free to invent very general polynomial frameworks, but the

    > important thing is to evaluate a single polynomial, not all possible

    > ones. I'm working under time and space constraints. If you invent a

    > general polynomial evaluation library you'll still get partial credit

    > if you use the right algorithm, and do so in a way that (as I

    > mentioned) looks more natural in a concatenative language than it does

    > in an infix one.

    >

    > Remember, time and space are of the essence. If you've started consing

    > a list, you're heading in the wrong direction. Accuracy and numeric

    > stability are also important.

    >

    > -Billy

    >

    >

    > ------------------------ Yahoo! Groups Sponsor --------------------

    > ~-->

    > Fair play? Video games influencing politics. Click and talk back!

    > http://us.click.yahoo.com/2jUsvC/tzNLAA/TtwFAA/saFolB/TM

    > --------------------------------------------------------------------

    > ~->

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >