Aiur – ZelluX 的技术博客

1. Algol 60为了模仿宏定义的行为，采用了正则序求值，这本书上貌似没详细介绍正则序和应用序。记得SICP(Structures and Interpretation of Computer Programmes)上对这两个概念讲得很详细。所谓正则序，normal-order，是一种’fully expand and then reduce’的计算方式。举个SICP上的计算例子

(sum-of-squares (+ 5 1) (* 5 2))
(+ (square (+ 5 1)) (square (* 5 2)) )
(+ (* (+ 5 1) (+ 5 1)) (* (+ 5 2) (+ 5 2)) )
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

而应用序则是’evaluate the arguments then apply’。
P.S GeSHi默认的lisp着色怎么是这样的 =_=

2. 惰性求值。应用序通常会更高效一点，但有时会出现不必要运行出错的情况，比如SICP中的习题1.5

(define (p) (p))
(define (test x y)
    (if (= x 0)
        0
        y))
(test 0 (p))

在应用序求值的情况下是会出现不必要的死循环的。于是有了折中的惰性求值lazy evaluation，需要的时候再求值。

一个用途就是创建惰性数据结构，Scheme手册中的一个例子，创建了一个表，内容是所有的自然数：

(define naturals
    (letrec ((next (lambda (n) (cons n (delay (next (+ n 1)))))))
       (next 1)))
(define head car)
(define tail (lambda (stream) (force (cdr stream))))

(head naturals) => 1
(head (tail naturals)) => 2
(head (tail (tail naturals))) => 3

Haskell中求值没有任何副作用，所有的参数都采用惰性求值。

[417/899]

Related Posts

• 2008/10/16 -- Programming Language Pragmatics 笔记 [1]