http://penguin-wenyang.wang/2021/12/31/fp-ip-optimization/

[utterances-bot]

Functional programming compiler optimize - 懒得想标题

Can a functional programming language compiler optimize as well as an imperative programming language compiler in practice? 在搜索FP优化的时候看到这么一个问题，高赞回答（总共也就俩回答）总结的挺好。 原回答简单翻译版 你的总结很恰当：对编译器来说，优化函数式程序更容易，但对

http://penguin-wenyang.wang/2021/12/31/fp-ip-optimization/

[wcphkust]

可以的。shape analysis可还行！函数式语言的一些特点导致很多分析变得很简单，比如很多情况下alias分析不再需要的。有的和数据结构相关的操作可以简化成优化一个纯数值程序。但是这种转化在命令式语言下变得不那么简单。

[wcphkust]

顺便附上之前和一位做性能分析的大佬的讨论的邮件（部分）：

In resource bound analysis literature, some papers deal with functional programs that involve the heap, such as Jan Hoffmann's works. In Jan Hoffmann's works, the sound transformation is trivial, because (i) the size of a data structure can be viewed as an uninterpreted function applied to a variable (that points to the data structure), (ii) the aliasing between container variables are made explicit (and therefore there is no need for alias analysis), and (iii) there is no reasoning about the contents in a container. "Liquid resource type" is probably another paper that worths taking a look at, because it attempts to reason about the contents in a container.

For imperative programs, I don't think I've ever seen a resource analysis paper that formally proves the correctness of the transformation, except for VMCAI'18(From Shapes to Amortized Complexity)

Particularly, for Jan Hoffmann's works, the aliasing between container variables need not to be considered, because they assume a linear type system. See the following quote from https://dl.acm.org/doi/10.1145/1925844.1926427

The remaining rules are affine linear in the sense that they assume that every variable occurs at most once.