Re: balanced REDUCE: a challenge for the brave

"Jeff M." <massung@xxxxxxxxx> writes:
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.

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

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?

Yes.

Maybe. But you are asking for a
more well-factored snippet of code. Factoring (at least for me)
usually involves more than just breaking out snippet A of code into
it's own function. If by allowing for an "unbalanced" solution one
could cut the code in half, make it more readable, more maintainable,
and more extensible, isn't that the end goal?

Not in this case. I started out with an unbalanced version that is
half the size and more readable, and more maintainable (and presumably
more extensible), but that is not good enough (or maybe it is; I was
fine with it for 18+ years, but just assume that we want to improve on
it). I actually posted the unbalanced version in the posting that
started the thread.

Perhaps instead of
saying that it has to be balanced, you would get better solutions if
you instead stated the problem that being balanced solved, and just
make solving that particular problem a part of the solution. Again,
distill the problem down into it's most fundamental components, and
solve those; don't put arbitrary restrictions on the programmer
because you've already solved portion A with assumption X.

So you want the big picture? Here it is:

I was discussing performance improvemnts for the code generated by
Gray <http://www.complang.tuwien.ac.at/forth/Gray5.zip> with Gerry.
He showed me some of the code generated for the scanner of Marcels PL1
(I think). It contained a large chunk of code that looked somewhat
like

symbol '(' = if
...
else
symbol ')' = if
...
else
... if
...
else
...
...
...
then
then
then

with a 24-deep (or so) nested if. This is slow because it tests for
each character sequentially. Now the optimum would be to use a jump
table for dispatching the actual pieces of code, but

1) that would require rewriting a significant part of Gray, and

2) it would disable some of the features that Gerry's way of treating
actions enables (but, OTOH, these things don't work in the original
Gray, so if we want to keep the versions compatible, we do not need to
support these features).

So, the next question is, how does the source code look for which this
if-else-cascade is generated? It looks like this:

(( "(" || ")" || ... || ... || ... || ......... ))

That's actually syntactic sugar for

"(" ")" ......... alt ... alt

The unbalanced usage of the ALTs is what causes the lopsided
if-else-cascade. If the ALTs were applied in a balanced way (ALT is
associative), the cascade would look more balanced, e.g. something
like:

symbol "()..." member? if
... if
...
else
...
then
else
...
then

If the symbol is one of the later ones in the sequence, the first test
will fail, and there is only one test needed where originally there
would be a dozen or more; more generally, with balanced ALTs we would
have only up to ceil(ld(n)) tests rather than up to n tests with the
current approach.

Now, in typical Forth fashion we could ask the users to actually avoid
writing such long sequences, and ask them to rewrite these sequences
as a balanced tree of parentheses, e.g.:

(( (( (( "(" || ")" )) || (( ... || ... )) )) || (( ... || .........)) ))

This would result in a balanced cascade, too.

However, I think that a balanced ALT-tree is easy enough to create
that we should not burden the user with such issues. Gray is not an
easy tool to learn as it is, no need to add complications.

So, if we look at what generates the unbalanced ALTs out of the syntax
"(( ... || ... ))", it comes down to an application of REDUCE. You
will find it at the end of gray.fs (after the "syntactic sugar"
heading comment).

Any further questions?

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2008: http://www.euroforth.org/ef08.html
.