🌳应用序和正则序

有以下代码

#lang sicp
(define (square x) (* x x))
(define (sum-of-squares x y) (+ (square x) (square y)))
(define (f a) (sum-of-squares (+ a 1) (* a 2)))

什么是应用序/Application order

定义是:先求值参数,后应用

当解释器看到一个组合式(函数调用)的时候,他会把所有的操作数,也就是参数,都计算出具体的值,然后代入到过程中去

比如

(f 5) ;;->
(sum-of-squares (+ 5 1) (* 5 2));; ->
(sum-of-squares 6 10);;  (在代入前，先算出了 6 和 10) ->
(+ (square 6) (square 10));; ->
(+ 36 100);; ->
136

这也是现在主流的语言 python, java 等求值方式

什么是正则序/Normal order

定义是:先完全展开,然后规约

其实就是遇到参数,先不求值.“展开”仅仅是指把函数调用替换为函数体，并将形参替换为原封不动、未求值的实参表达式,等需要这个参数的时候,再去求值

这是一种偷懒的方式,但缺点是会出现重复计算某一个表达式

案例:

(f 5);; ->
(sum-of-squares (+ 5 1) (* 5 2));; (不求值，直接代入) ->
(+ (square (+ 5 1)) (square (* 5 2)));; (继续展开 square) ->
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)));;(直到遇到基本的乘法 *，才开始真正计算) ->
(+ (* 6 6) (* 10 10)) ;;->
(+ 36 100) ;;->
136

但这里 (+ 5 1)被计算了两次

检测机器是正则序还是应用序

SICP 的练习 1.5 中，Ben Bitdiddle 发明了一个巧妙的测试，用来检测解释器使用的是应用序还是正则序

#lang sicp

(define (p) (p))

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

(test 0 (p))

我对 (test 0 (p)) 这个练习的分析有点问题。 我看正则序的定义是先完全展开而后规约，所以，我觉得 (test 0 (p))，会把test,p两个运算符展开，在对p展开的时候，会无限循环。所以正则序也会实现机器陷入死循环的停滞状态

在正则序中，“展开”仅仅是指把函数调用替换为函数体，并将形参替换为原封不动、未求值的实参表达式，而不是无脑地向下递归展开所有的参数 。

;;正则序下
(test 0 (p)) ;;->
;;参数原封不动代入
(if (= 0 0)
   0
   (p))

在正则序中，传入的实际参数只有在有需要时才会被求值，因此，在使用正则序的解释器里运行 (test 0 (p)) 时， 0 和 (p) 都不会立即被求值，当解释进行到 if 语句时，形式参数 x 的实际参数(也即是 0)会被求值(求值结果也是为 0 )，然后和另一个 0 进行对比((= x 0))，因为对比的值为真(#t),所以 if 返回 0 作为值表达式的值，而这个值又作为 test 函数的值被返回。