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
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
>
>
>
>
>
>
>