When I post a challenge for better factoring, there is usually no
followup. I wonder if this is because the challenges come from real
programs (so they are usually not as abstract as the puzzles that draw
more attention), because they are so hard, or because my solution is
already optimal (which I doubt).

Anyway, here's a problem that should be abstract enough to avoid the
first problem, even though it came up in the context of a real program.

To explain the problem, let's start out with a simple unbalanced
reduce:

: reduce ( 0 x1 ... [x2 x3 -- x4] -- x )
\ e.g. 0 5 6 7 ' + reduce = 5 6 7 + + = 18

." no operand" abort
endif
begin
over while
r@ execute
repeat ( 0 x )
swap drop r> drop ;

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: balanced REDUCE: a challenge for the brave
[..]

[..]

Why not use two deques a and b:

Anton Ertl wrote:

What exactly do you mean by "unbalanced?" Is the following unbalanced?

0 1 2 3 4 5 ' + reduce ==> 4 5 + 3 + 2 + 1 +

Your code evaluated this as:

4 5 + 3 2 + + 1 +

So is "balanced" another way of saying you want minimal height in
evaluation tree?

According to Anton Ertl mips.complang.tuwien.ac.at>:

Composition of permutations can be used. For instance, consider
permutations of 8 elements. Each permutation is represented by a 32-bit
integer, where hexadecimal digit n contains the value on which n is
mapped through the permutation. Thus, 0x76543210 is the identity (maps 0
to 0, 1 to 1,...) while 0x67453210 exchanges 6 and 7, and 4 and 5, while
keeping 0, 1, 2 and 3 unchanged.

You may then compose two such permutations with this:

: hdigit ( u n -- u ) 4 * rshift 15 and ;
: hshift ( u n -- u ) 4 * lshift ;
: compose ( p1 p2 -- p3 )
0 8 0 do
-rot 2dup i hdigit hdigit

loop -root 2drop;

anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

You're reducing the generality quite a bit by never allowing a result of zero.

Would you consider a solution that knows how many items there are at the start, rather than continuing until it gets a zero?

anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:

\ a quick hack to create a third stack. >T T@ TDROP T>
\ Use a third stack instead if you have one.
: >T ( x -- )
, ;
: T@ ( -- x )
-1 cells here + @ ;
: TDROP ( -- )
-1 cells allot ;
: T> ( -- x )
T@ TDROP ;

\ analog of .S that works only for current problem
: .T
here begin 1 cells - dup @ while dup @ . repeat drop ;

\ The third stack will hold partial values and their levels.
\ 1 1 my-+ T: x 1
\ 1 1 my-+ 1 1 my-+ ( T: x 1 x 1 ) my-+ T: x' 2

John Passaniti JapanIsShinto.com> writes:

Yes.

Yes. Sorry if that did not come out clearly.

So, while I love a good programming challenge, (and no offense is
intended) I find challenges like these to be the very opposite of what
Forth is good at. By that, I don't mean that Forth can't reduce values
in an array, or work on large data sets, or ....

What I mean is that part of the Forth mentality: factoring, is many
times about changing the problem in such a way that it can be
expressed more concisely, tested more thoroughly, and factored into
more finely tuned components.

While many times there is an external force that requires us - as
programmers - to slam our collective heads on our keyboards because of
crazy system, hardware, or managerial requirements placed on us, toy
problems definitely aren't one of them. :)

As an example, aside from intentionally making the problem more
difficult, is there any particular reason to enforce "balanced" vs.
"unbalanced" in this particular case? Maybe. But you are asking for a...

"Jeff M." gmail.com> wrote:

I could imagine problems where it made a difference. Like, for floating point you'd prefer the errors to all have about the same effect. Order of operations could much affect that. And you could solve something like that with this code. Each item could be the address of a floating point array, and the execution token does an operation on two such arrays and returns an address for the result. And in that case you'll never get a zero address for a result and you can use zero to mark the end of the list.

It won't be commutative if it uses subtraction or division, or matrix multiplication. (or quaternion multiplication.)

That might turn out to be pretty complicated. By factoring out a simple statement of part of the criteria, he gives us an understandable problem to solve.

"Jeff M." gmail.com> writes:

Sure, it's not easy in Forth, otherwise it would not be a challenge.
It's also unidiomatic, in having a variable stack effect.

Yes.