Re: I found a FORTH stack optimzer, but could use a better version.

"Rod Pemberton" <do_not_have@[EMAIL PROTECTED]
> writes:
>
>I ran across an interesting optimizer for FORTH stack words in java by
Ram
>Janovski, and Vassilii Khachaturov, dated 2004, here:
>
>  http://black.cs.bgu.ac.il/forth-opt
>
>Depending on which FORTH stack words you select, it'll attempt to
generate a
>optimized definition using the input set of words.
>
>  i.e., if you input ab -- ba, for SWAP, and select DROP,DUP,TUCK it'll
>output:
>
>    Transforming ab ==> ba
>    TUCK ( ab -- bab )
>    DROP ( bab -- ba )
>
>  i.e., if you input ab -- ba, for SWAP, and select DROP,DUP,ROT it'll
>output:
>
>    Transforming ab ==> ba
>    DUP ( ab -- abb )
>    ROT ( abb -- bba )
>    ROT ( bba -- bab )
>    DROP ( bab -- ba )
>
>Anyone aware of other FORTH stack optimizers?

A number of these things have been posted in the past, among them:

http://www.complang.tuwien.ac.at/forth/stack-opt

That's in Prolog and uses backtracking with iterative deepening, so
it's probably less efficient for large problems than the shortest-path
algorithm used in the Java program, but I guess that it is also much
shorter, and easy to understand (at least if you know Prolog).

I remember that other programs were posted or at least posted about
that were written in Forth.

However, most of these programs, including the ones you and I
reference only are good for optimizing a sequence of stack
manipulation words; usually we don't have long sequences of those, and
if we have them, that's an alarm sign that our programming is wrong.

What might be more interesting in some cases is if we can rewrite a
sequence that contains other words in a way that reduces the stack
manipulation words or makes the stack manipulation clearer.  I can see
a way to write a variant of the Prolog program that does this.

But even that would only rarely be useful: in general the things were
we need most help with run across control structure boundaries,
especially across calls or returns, which also involves other words,
or involve some arithmetic equivalences, or other more complex cases.
Optimal solutions in these cases are out of the reach of current
technology (and even characterizing optimality is probably a
challenge), although I can imagine that one could have a program that
works in many cases (like we have in the case of symbolic integration
and theorem proving); but that would probably be a major research and
development effort.

Followups set to comp.lang.forth.

- 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.complang.tuwien.ac.at/anton/euroforth/ef08.html