Evaluation Schemes
主要有这几种 evaluation scheme:
- full beta-reduction
- 只要是
(lambda x. t1) t2
的形式,就可以 reduce
- 只要是
- normal order
- 优先 reduce outermost, leftmost。如果没有,那就再考虑其它的形式。
- call by name
- 不允许在 abstraction 内部进行 reduce (i.e.
t1 t2
orlambda z. t2
的 t2,被禁止 reduce) - variants used by ALGOL-60 and Haskell: call by need
- 不允许在 abstraction 内部进行 reduce (i.e.
- call by value
- 和 call by name 正相反。
lambda z. t2
仍然禁止 reduce,但是t1 t2
中,必须先 reduce t2,才能进一步 reduce 左侧的
- 和 call by name 正相反。
本书中,我们使用 call-by-value 策略。因为 call-by-value 应用最广泛,而且很容易扩展到 reference 以及 exception。