Daniel Ehrenberg — 2007-12-06 02:33:56

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.
The Factor compiler implements constant folding, but it operates on an
intermediate dataflow representation rather than quotations. This
looks like one area where it's a little easier to manipulate an
applicative programming language than a concatenative one, 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?

Daniel Ehrenberg

Christopher Diggins — 2007-12-06 03:11:04

On Dec 5, 2007 9:33 PM, Daniel Ehrenberg <microdan@...> 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

Daniel Ehrenberg — 2007-12-06 05:49:44

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? Maybe something like that,
though not necessarily relying on the exception system, is possible.

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

>
> > 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. 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. The
brute force approach sounds a little complicated to get right, but
I'll see if I can get it to work...

Daniel Ehrenberg

Christopher Diggins — 2007-12-06 14:25:31

On Dec 6, 2007 12:49 AM, Daniel Ehrenberg <microdan@...> 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

John Cowan — 2007-12-06 14:41:44

Christopher Diggins scripsit:

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

What is more, when you see a non-primitive word whose definition you have,
you can inline it (provided, of course, that you are not already inlining it!)

--
A: "Spiro conjectures Ex-Lax." John Cowan
Q: "What does Pat Nixon frost her cakes with?" cowan@...
--"Jeopardy" for generative semanticists http://www.ccil.org/~cowan

Daniel Ehrenberg — 2007-12-06 18:38:35

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

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

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

Daniel Ehrenberg

Christopher Diggins — 2007-12-06 19:38:28

On Dec 6, 2007 1:38 PM, Daniel Ehrenberg <microdan@...> 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

Daniel Ehrenberg — 2007-12-06 20:26:17

> 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 makes sense. We kept misunderstanding each other, though. I have
access to the Factor evaluator easily. (I also have access to the
compiler, though it's not particularly useful.)

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

No, I get a quotation, which is manipulable like quotations in Joy,
except that it's a random-access array rather than a linked list. The
SSA form is only for compilation.

Thanks for your help, Chris (and John, though I was already doing that)!

Daniel Ehrenberg

William Tanksley, Jr — 2007-12-09 20:14:41

Daniel Ehrenberg <microdan@...> wrote:

> 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

Wow, that's impressive.

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

That makes sense. A friend of mine has an algorithm for Forth which
seems to catch a lot of opportunities for optimization (including
stack manipulation and constant folding); I'll see if I can convince
him to either write it up or join this list. In essence, he uses a
stack at compile time to track the type and knownness of values
encountered and/or produced. It's linear time, so it's not hard to
understand.

> looks like one area where it's a little easier to manipulate an
> applicative programming language than a concatenative one, though I'm

Heh. I doubt it.