Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
73 lines (67 sloc) 2.35 KB
; 为了书写方便,我用%表示remainder函数
(define (% a b)
  (remainder a b))

(define (gcd a b)
  (if (= b 0)
    a
    (gcd b (% a b))))

下面先看(gcd 206 40)的正则序(全部展开,最后依次求值)求值过程

(if (= 40 0)
    206
    (gcd 40 (% 206 40)))
; if求值后的结果为
(gcd 40 (% 206 40))
;------------------------------------------->>>>
(if (= (% 206 40) 0)
    40
    (gcd (% 206 40) 
         (% 40 (% 206 40))))
;这里if谓词执行,调用一次%,最终结果为:
(gcd (% 206 40) 
     (% 40 (% 206 40)))
;------------------------------------------->>>>
(if (= (% 40 (% 206 40)) 0) ;(= 4 0)
    (% 206 40)
    (gcd (% 40 (% 206 40))
         (% (% 206 40)
            (% 40 (% 206 40)))  ;这里gcd的第二个参数有4个%,后面书写方便实用%_4符号表示,其值为2
    ))
;这里if谓词执行, 调用两次%后,结果为
(gcd (% 40 (% 206 40))
     %_4)
;------------------------------------------->>>>
(if (= %_4 0)  ; (= 2 0)
    (% 40 (% 206 40))
    (gcd %_4 (% (% 40 (% 206 40))
                %_4)) ;这里gcd的第二个参数有7个%,后面书写方便实用%_7符号表示,其值为0
    )
; 这里if谓词执行,调用四次%后,结果为
(gcd %_4 %_7)
;------------------------------------------->>>>
(if (= %_7 0) ;(= 0 0)
    %_4
    (gcd %_7 (% %_4 %_7)))
; 这里if谓词执行,调用七次%后,结果为
%_4
;------------------------------------------->>>>
; 经过四次%后,得到最终的结尾为2

累加上面的调用%的次数:1 + 2 + 4 + 7 + 4 = 18

下面再看应用序(先求参数,后代入)的求值过程:

(gcd 40 6) ;一次
(gcd 6 4)  ;一次
(gcd 4 2)  ;一次 
(gcd 2 0)  ;一次
2  

一共调用了4次

可以看到,正则序的求值方式,全部展开后在依次求值,重复计算了很多次,可见效率肯定比应用序要低。 但是正则序(也就是延迟求值)也有它的应用场景。我目前知道的应用有无穷序列,这在类C语言中是不存在的。

WiKI上面列出了三点:

  • Performance increases by avoiding needless calculations, and error conditions in evaluating compound expressions
  • The ability to construct potentially infinite data structures
  • The ability to define control flow (structures) as abstractions instead of primitive