Lisp 语法

表达式

先写一个操作符，再写值。

(+ 1 2) // 结果为 3
(+ 1 2 3 4) // 结果为 10
(+ (* 3 3) (* 4 4)) // 结果为 25

较长的表达式

(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))

// 可读性推荐加上空格以及换行
(+ (* 3)
 			(+ (* 2 4))
   				(+ 3 5)))
		(+ (- 10 7)
      6))

命名（也叫定义，不叫赋值）

定义一个变量，就是 define 然后 接变量名，然后再接变量的值

(define size 5)
(* size 2) // 结果为 10

复合过程（函数定义）

(define (fn a b) (+ a b))
(fn 1 2) // 结果为 3
(define (fn2 x) (* x x))
(fn2 4) // 结果为 16

Lisp 求值

递归求值

Lisp 求值可以理解为递归求值，Lisp 表达式求值就是把操作法右侧的作用于操作符来计算求值，如果还有操作符，再把值作用于操作符，如果还有操作符，以此类推。

(+
 (*2
  (+ 7 8))
 (+3
  (- 10 6))
)

上面表达式的求值，可以拆分为两个表达式：表达式一 (*2 (+ 7 8)) 和表达式二 (+3 (-10 6)) 以及操作符 +；表达式一再拆分为表达式 A 2 和表达式 B (+7 8) 以及操作符 *；同理表达式二再拆分为表示 C 3 和表达式 D (-10 6) 以及操作符 +。

此时可以计算 表达式 B 值为 15，表达式 A 值为 2，作用于操作符 *，2*15 值为 30，所以得到表达式一的值为 30。

同理可以计算表达式 D 值为 4，表达式 C 值为 3，作用于操作符 +，3+4 值为 7，所以得到的表达式二的值为 7。

表达式一的值为 30，表达式二的值为 7，作用于操作符 +，所以得到的结果为 37

代入求值

递归求值是对具体的值的求值，代入求值是对定义的函数的求值。

定义三个函数：

(define (sq x) (* x x))
(define (sqsum a b) (+ (sq a) (sq b)))
(define (f z) (sqsum z (+ z 1)))

求 (f 5)

(f 5) = (sqsum 5 (+ 5 1))
			= (sqsum 5 6)
			= (+ (sq 5) (sq 6))
			= (+ (* 5 5) (* 6 6))
			= (+ 25 36)
			= 61

任何一个函数的值，一直代入函数，直到没有函数了，再递归求出来。

if

写一个求绝对值的函数

(define (abs a)
  (if (> a 0)
      a
      (-a)))

递归

求一个正整数的阶乘 f(n) = n!，不完全归纳法得到 f(n) = f(n -1)*n （n > 1）。

(define (f n)
 (if (= n 1)
			1
			(* n * (f (- n 1))))
)

😂 某著名程序是 Lisp 写的，它的最后一页被间谍盗取了，结果全部是反括号。

求 (f 6)

(f 6) = (* 6 (f 5))
			= (* 6 (* 5 (f 4)))
			= (* 6 (* 5 (* 4 (f 3))))
			= (* 6 (* 5 (* 4 (* 3 (f 2)))))
			= (* 6 (* 5 (* 4 (* 3 (* 2 (f 1))))))
			= (* 6 (* 5 (* 4 (* 3 (* 2 (* 1))))))
			= (* 6 (* 5 (* 4 (* 3 (* 2 1)))))
			= (* 6 (* 5 (* 4 (* 3 2))))
			= (* 6 (* 5 (* 4 6)))
			= (* 6 (* 5 24))
			= (* 6 120)
			= 720

整个求值过程就是先递进（展开）然后再回归（求值），这就是递归之所以叫递归。

迭代

迭代求 6 的阶乘。先求 1 的阶乘，1 的阶乘 乘以 2 得到 2 的阶乘 再乘以 3 得到 3 的阶乘 再乘以 4 得到 4 的阶乘 再乘以 5 得到 5 的阶乘 再乘以 6 得到 6 的阶乘。

(f 6) = (j 1 1 6) // (j result n max-n) result 表示这次的计算结果，n 是第几次计算，max-n 是最多计算的次数
			= (j 2 2 6)
			= (j 6 3 6)
			= (j 24 4 6)
			= (j 120 5 6)
			= (j 720 6 6)
			= (j  7 6) // 到第 7 次，7 大于 6 所以直接返回结果不再计算

每次 n + 1 进行计算，n > max-n 时直接返回结果不再计算。

(define (factorial n)
	fact-iter 1 1 n)
(define (fact-iter result n max-n)
	(if (> n max-n)
		result 
		(fact-iter (* n result)
								(+ n 1)
								max-n )))

从一个状态到下一个状态（每个状态是用固定数目的变量表示的）

高阶函数

假设有三个函数：

(define (sum-int a b)
	(if (< a b)
		0
		(+ a (sum-int (+ a 1) b))))
(define (sum-cube a b)
	(if (< a b)
		0
		(+ (cube a) (sum-cube (+ a 1) b))))
(define (sum-square a b)
	(if (< a b)
		0
		(+ square a) (sum-square (+ a 1) b))))

然后抽象这三个函数：

(define (???1??? a b)
  (if (> a b)
      0
      (+ (???2??? a)
         (???1??? (???3??? a) b))))

套入变量

(define (sum fn a next b)
  (if (> a b)
      0
      (+ (fn a)
         (sum fn (next a) next b))))

重写三个函数

(define (plus n) (+n 1))
(define (sum-cube a b)
  (sum cube a plus b))

(define (nothing n) n)
(define (sum-int a b)
  (sum nothing a plus b))

(define (sum-square a b)
  (sum square a plus b))

高阶函数是指一个函数操作了其他函数，那么这个函数就是高阶函数。