重写表达式以优化它们的理论
假设我有一种语言，可以输入表达式，就像这个过于简化的示例：
if A() > B() then A() else B() end
所以 A() 和 B() 是函数，并且表达式返回两者中较大的一个。简单的评估方法是调用 A 和 B，然后再次调用两者中最大的一个。因此，如果 A 返回 10，B 返回 20，则 B 更大，并且会被调用两次。
我想要实现的是一种机制，该机制将理解，由于 A() 和 B() 是确定性的（总是给出相同的结果），因此表达式可以重写为：
tmpA = A()
tmpB = B()
if tmpA > tmpB then tmpA else tmpB end
此代码只会调用 A 和 B 一次，如果两者都调用同样昂贵，这将节省 33% 的执行时间。
我想这样做，这样用户就不必担心性能，我的语言是针对业务用户而不是程序员。用户将像在白板上一样输入表达式，程序将其解析为表达式树，优化器将自动重写该表达式以实现高效执行，然后进行编译。
有谁知道处理这个主题的好书或资源？这有什么正式的理论吗？上面的情况很容易发现，但是当事情变得更复杂时我就会感到紧张。当我重写表达式并改变行为时，这不是一件好事。
一个更复杂的例子是
A = 10
B = if A > 5 then 100 else 0 end
C = if A > 5 then B * 2 else 0 end
我不会让你厌倦所有的细节，但假设 A 是一个标志，指示是否应该做某事。中间函数B也是用户可以调用的结果。
如果我调用 C，它会检查 A > > 5然后调用B，B会再次检查A然后返回。因此，当我替换（内联）表达式时，我会得到
C = if A > 5 then if A > 5 then 100 else 0 end * 2 else 0 end
可以优化为的
C = if A > 5 then 200 else 0
表达式。在典型的模型中，有数百个这些表达式都互相调用递归，因此这些事情可能会变得非常复杂。如果可能的话，我不想通过反复试验来发现这一点，而是利用其他人在这个领域所做的事情。
提前致谢，
格特·扬
Suppose I have a language where I can enter expression like this oversimplified example:
if A() > B() then A() else B() end
So A() and B() are functions and the expression returns the bigger of the two. The naive way of evaluating this would call both A and B, and then call the biggest of the two again. So if A returns 10 and B returns 20, B is bigger and would be called twice.
What I would like to implement is a mechanism that would undertsand that since A() and B() are deterministic (always give the same result) the expression can be rewritten to this:
tmpA = A()
tmpB = B()
if tmpA > tmpB then tmpA else tmpB end
This code would only call A and B once, if both are equally expensive this would save 33% of execution time.
I want to do this so the user does not have to worry about performance, my langiage is targeted towards business users rather than programmers. The user would enter the expressions just as (s)he would on a whiteboard, the program parses it into an expression tree and an optimizer would automagically rewrite that for efficient execution and then compile.
Does anyone know of a good book or resource that handles this topic? Is there any formal theory on this? The case above is easy to spot, but when things get more complicated I get nervous. When I rewrite an expression and change the behaviour that would not be a good thing.
A more involved example would be
A = 10
B = if A > 5 then 100 else 0 end
C = if A > 5 then B * 2 else 0 end
I won't bore you with all the details, but suppose A is a flag that indicates if something should be done. The intermedtiate function B is also a result that the user could call.
If I call C, it would check for A > 5 and then call B, wich would check A again and then return. so when I substitute (inline) the expressions, I would get
C = if A > 5 then if A > 5 then 100 else 0 end * 2 else 0 end
which can be optimized to
C = if A > 5 then 200 else 0
In a typical model there are hundreds of these expression all calling eachother of recursive, so these things can get pretty complicated. If possible I'd like to not find this out through trial and eror but tap into what others have doen in this field.
Thanks in advance,
Gert-Jan
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
只是一个想法，但是如果您让代码参考预先填充的变量（在第一次调用之前填充在行上以避免不必要的调用）来替换所有重复的方法调用，您能不能让编译器拾取其余部分..
我可能是错的，但我原以为他们已经在这些类型的优化上投入了大量的精力..取决于语言、编译器（有时还有编译选项），但这些比代码优化的研究速度更快，因为整体..
只是一个建议
Just a thought but if you get your code to replace all duplicated method calls with reference to a pre-populated variable (populated on the line prior to its first call to avoid un-unnecessary calling) can you not let the compiler pick up the rest..
I could be wrong but I would have thought they would have put quite a bit of effort into those types of optimizations already.. depends on the language, compiler (and sometimes compile options) but those are faster to research than code optimization as a whole..
just a suggestion though