Adding Identities to Peval

[Noah Lavine]

Hello,

I've been working on a patch to add a new sort of optimization to
peval, and I think it's almost ready. It's based on some of the ideas
in "Environment Analysis of Higher-Order Languages".

The goal is to recognize when two quantities are equal even when we
don't know what they are. My working example has been this expression:

(let* ((x (random))
       (y x))
  (eq? x y))

The patch attached to this message lets peval optimize that to

(begin (random) #t)

This happens through objects called 'identities'. We make a new
identity for every constant and the result of every procedure call.
Identities are associated with values, not variables, so x and y above
have the same identity. When it looks at the eq?, peval notices that x
and y have the same identity, and concludes that they must be eq? even
without knowing their value.

The patch adds some members to the <operand> record type to store an
identity for the operand, and an identity-visit function that matches
the visit function used to get values. It also has a few utility
functions and the definition of a new record type <identity> with no
members. The logic added is pretty minimal. I tested it by running
check-guile. It passes about the same number of tests as it did before
I added the patch.

There's one glaring wart. The identity checking is activiated by calls
to (toplevel 'eq?). Clearly, it should be activated by calls to the
primitive 'eq? (and eqv? and equal?). The reason it's not is that my
example above compiles to (call (toplevel-ref 'eq?) ...), and I don't
know how to make it turn into a (primcall 'eq? ...). I tried a few
variants, but they didn't work. What test code should I be using to
produce a primcall?

However, that problem is easy to fix, and besides that I believe the
patch is correct.

This also relates to my earlier ideas for a compiler. After thinking
about it more, I'm not sure I like the direction I took in the
wip-compiler branch, so I decided to start working on peval instead.
This patch has an ulterior motive - besides adding a new optimization
itself, it uses a lot of the infrastructure you'd want for more
aggressive optimization like type-checking. So part of the purpose of
this was to learn how to do that.

What do you think?
Noah

0001-Add-Identity-Optimization.patch
Description: Binary data