Re: [stack] Constant folding algorithm

On Dec 6, 2007 12:49 AM, Daniel Ehrenberg <[email protected]> wrote:
> Thanks for your response, Chris,
> > Have you considered the brute force approach? Try to evaluate a
> > sub-expression: if it throws an error it doesn't work, otherwise go
> > ahead and replace the subexpression with its evaluateion. Pretty
> > naive, but very easy to code. This is how I implemented partial
> > evaluation in an earlier version of Cat (currently broken, while I
> > focus on other issues).
> >
> That might work, but using that approach, how can I tell where a
> successful partial evaluation begins and ends? Is it like you take
> each possible starting point in the code?

That's what I did. I would take n consecutive terms (where n was
bounded by some constant to keep the algorithm linear) apply these
terms to the empty stack, and if it doesn't underflow the stack, use
the resulting stack as the new expression.

> Maybe something like that,
> though not necessarily relying on the exception system, is possible.

So, I'm assuming you are hacking the compiler source code? You can
modify it slightly to detect underflow without waiting for exceptions,
which is admittedly quite ugly.

> > > The Factor compiler implements constant folding, but it operates on an
> > > intermediate dataflow representation rather than quotations.
> >
> > What does the representation look like?
> >
> I've never looked into it, but Slava has said it's basically Single
> Static Assignment. It can't easily be converted back into a quotation.

That really surprise me, because I always thought that a language like
Joy or Cat (where there is only one explicit stack) was as easy to
work with as SSA. I suspect it is because Slava does his own register
allocations?

> >
> > > This
> > > looks like one area where it's a little easier to manipulate an
> > > applicative programming language than a concatenative one,
> >
> > Can you tell me more why you feel this is? I am skeptical about this
> claim.
>
> In an applicative language, or at least one with a readily inspectable
> AST like Lisp, you could just traverse the code in postorder,
> evaluating all code which doesn't refer to variables and calls a
> function on a known list.

That makes sense. In the Cat optimizer I use type inference to
reconstruct an AST.

> For example, you could tell that (+ x (* (-
> 4 5) 2)) can reduce, from the inside, to (+ x (+ -1 2)) and then to (+
> x 1), though no further, since x is a (free) variable. But I hope I'm
> wrong and that a similarly simple, explicit algorithm is possible.

Why not remove free variables (e.g. pass them as parameters)? It
simplifies a lot of analyses.

> The
> brute force approach sounds a little complicated to get right, but
> I'll see if I can get it to work...

You'll have to be careful to identify code with side effects for it to
work. You don't want to write to the console for example while
performing partial evaluation (i.e. constant folding)

> Daniel Ehrenberg

Christopher
http://www.cdiggins.com