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