各种Normal Form

March 31, 2013

讨论Haskell的性能的时候总少不了个各种Normal Form,所以特意翻资料看了一下。

Normal Form

NF指已经被完全求值、不能再归约的表达式。一个表达式里有多个可归约表达式(redex)时,non-strict语义保证不同的求值顺序最终得到一样的Normal Form(前提是求值能结束)。

deepseq a b会把a求值到NF。

Weak Head Normal Form

WHNF指求值到最外层构造器或者函数抽象或者一个部分调用的内建函数,所以看到一个表达式是个函数或者构造器,那它就是WHNF了。

Lazy evaluation就是把表达式求值到WHNF,seq a b会把a求值到WHNF。

值得注意的是WHNF对子表达式没做要求,子表达式可以是NF或WHNF,以前我不知道这点,总想不明白为什么NF也是WHNF。因为NF肯定也求值到最外层,子表达式如果有也都是NF了,所以NF都是WHNF。

WHNF原来是SPJ造出来的。

Head Normal Form

比较完整的只找到FOLDOC上的解释:

(HNF) A term describing a lambda expression whose top level is either a variable, a data value, a built-in function applied to too few arguments, or a lambda abstraction whose body is not reducible. I.e. the top level is neither a redex nor a lambda abstraction with a reducible body.

An expression in HNF may contain redexes in argument postions whereas a normal form may not.

Haskell里是没有HNF的。

参考

  1. Head Normal Form from FOLDOC
  2. Weak Head Normal Form from FOLDOC
  3. Haskell: What is Weak Head Normal Form?
  4. Weak Head Normal Form