Re: [stack] Constant folding algorithm

On Dec 6, 2007 1:38 PM, Daniel Ehrenberg <[email protected]> wrote:
> > 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.
>
> No, I'm not doing anything with the compiler source code. This is a
> separate project and is implemented through quotation introspection.
> But the way that the Factor error handling system works, it is
> possible to trap stack underflow at runtime. Also, each word has it
> marked whether it's suitable for constant folding (for the compiler's
> use, but I can take advantage...)

Oh, then I misunderstood. You don't have access to a Factor evaluator,
or do you? Essentially I imagined you were performing a partial
evaluation of Factor step by step. If so then
I think you can detect the underflow by counting the number of
arguments that are about to be consumed, during each stage of the
evalution.

> > 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?
> >
> It might not be difficult to convert a stack language to SSA, but I
> have no idea how to change it back into a quotation. Anyway, I don't
> think such a transformation would work for this, since it would change
> the quotation in other ways.

So when introspecting the code, you are getting the SSA form?

> > > 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.
> >
>
> What do you mean?

I misunderstood the problem to be that "x" was free. To resolve this,
a standard compilation technique of functional languages is to remove
free variables (e.g. variables that are not arguments or locally
declared) and pass them as arguments. This process is known as lambda
lifting (http://en.wikipedia.org/wiki/Lambda_lifting). However, after
looking at your problem statement the fact that "x" is free or bound
is irrelevant, the problem is that it is a variable, so forget what I
am talking about.

- Christopher