[<<][compsci][>>][..]
Fri Jan 22 14:48:58 CET 2010

Common expression elimination

Here is a pattern I ran into today.  It is somewhat related to loop
exchange and memoization.  Translated to a Scheme program
transformation problem it is:


(begin
  (let ((a 1)
        (b 2)
        (c 3))
    ...)
  (let ((a 1)
        (b 7)
        (c 19))
    ...)
  (let ((a 1)
        (b 5)
        (c 3))
    ...))

->

(let ((a 1))
  (begin
    (let ((b 2)
          (c 3))
      ...)
    (let ((b 7)
          (c 19))
      ...)
    (let ((b 5)
          (c 3))
      ...)))

I.e.: if all the bindings of `a' are the same, pull them out.

This is useful for presenting a hierarchical view of a database table.

The solution is straightforward, especially if this needs to be done
over only one level: transpose the nesting and pull out rows that have
the same values.

Now, the interesting thing is that the table view comes from a
different hierarchical nesting that's been flattened as the variables
visible in the deepest nesting level.  So then this gives a way to
invert certain nested namespaces into another nesting.




[Reply][About]
[<<][compsci][>>][..]