Re: [stack] Constant folding algorithm

On Dec 5, 2007 9:33 PM, Daniel Ehrenberg <[email protected]> wrote:
>
> Hi all,
>
> Right now, I'm working on a module called inverse for Factor. The
> basic goal is to provide an inverse (or, technically, a section) of a
> quotation, for a generalized form of pattern matching. I've noticed
> that this can work both more efficiently and more generally if I first
> perform constant folding on the quotation, for example transforming [
> 1 2 + * ] into [ 3 * ], which can more easily be inverted. Right now,
> I have a very simple constant folding algorithm which looks for a word
> in a certain predefined set of words, preceded by two constants.  This
> fails, though, if I use something like [ 1 2 + 3 4 + / ]. I'm
> wondering if anyone has any idea of how to make an algorithm which,
> given a quotation and a list of safe-to-fold words with their arities,
> will perform as much constant folding as is possible on a function.

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

> The Factor compiler implements constant folding, but it operates on an
> intermediate dataflow representation rather than quotations.

What does the representation look like?

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

> though I'm
> sure there's a good solution this problem. The first thing that comes
> to mind is to use a slightly modified metacircular interpreter, but
> that would be very complicated to implement. Ideas?

- Christopher