今天在复习程序语言基础的考试，偶有所获，记录下来~

延迟求值相关

Thunk

首先，先看看函数式里面延迟求值的方式之一，Thunk。这里有一个函数，他的作用是用来取代原本的If判断，代码是这样的~

(define (my-if-bad x y z) (if x y z))

初步看上去，代码很不错，简单易懂，但，如果我们以这样的方式进行调用，就会出问题~

(define (factorial-wrong x)
	(my-if-bad (= x 0)
		1
		(* x (factorial-wrong (- x 1)))))

这里会出什么问题呢~程序会陷入无尽的递归中。这是因为以Racket为代表的大部分函数式编程语言的设定造成的，对于函数的参数，会在执行函数之前先进行求值。所以，my-if-bad的第三个参数，会先进行求值。而在求值的时候，就陷入了无限的递归求值当中。

那既然会有问题，该如何解决呢~方法也很简单，只需要修改下my-if-bad的定义~

(define (my-if x y z) (if x (y) (z)))

(define (factorial x)
(my-if (= x 0)
	(lambda () 1)
	(lambda () (* x (factorial (- x 1))))))

这里利用的是以Racket为代表的大部分函数式编程语言的另一设定，直到函数被调用的时候才对函数体进行求值。所以这样将原本的参数变成一个没有参数的匿名函数后，就不会在把它们作为参数传入函数的时候就进行求值，而是在使用到它的时候才进行求值。这样程序就可以正常工作了。所以这种方法就叫做Thunk，在这里我们把参数y和z给Thunk了。

Delay and Force

上面的Thunk，在某些情况下，不太能满足要求。比如，Thunk是将参数写成匿名函数，如果参数需要大量计算，那Thunk会使得每次调用的时候都要求值一次，会比较浪费资源，于是有了另外一种方式，利用Delay和Force，这种方法又被叫做Call by need，因为它既做到了延迟求值，有Call by name的性质，又只需要求值一次，有Call by value的性质。

(define (my-delay f)
	(mcons #f f))
(define (my-force th)
	(if (mcar th)
		(mcdr th)
		(begin 	(set-mcar! th #t)
				(set-mcdr! th ((mcdr th)))
				(mcdr th))))

这里用了Racket相比于SML的动态特性，其List中的元素不需要是同一类型。所以在delay函数中，把原本的Thunk与一个布尔变量构成一个List，或者说Pair更好一点，(False, Thunk)然后，在force的时候，如果该布尔变量取值为false，那就意味着Thunk还没有被求值，那就对其求值，并把这一对Pair的值变为(True, Evaluated value)，这样以后调用，就可以直接返回已经被求值过一次的值。

Stream

一个流是一个有无数个数值的序列，不知道翻译的对不对。Racket可以通过自己来实现按需生成的流，之所以能做到按需，还是用到了之前的Thunk。流的实现，基本是通过(Item in the stream, Thunk of the function which is responsible for generating new item)的方式来实现的。举个例子~

(define nats
	(letrec ([f (lambda (x) (cons x (lambda () (f (+ x 1)))))])
	(lambda () (f 1))))

这里f是一个接受参数x的函数，然后其产生一个形如(x, Thunk{f(x + 1)})的Pair。所以Nats就会产生(1, Thunk{f(2)}))，当继续展开这个Stream，((cdr (nats)))，就会产生(2, Thunk{f(3)})，通过这样的方式就可以假装产生了一个有无数个元素的序列。

Memo

Memo想做的事情，是对于那些，给定一样的参数，函数的返回值也是固定的这一些函数，缓存它们的(参数，结果)，然后在之后有同样参数的调用，那直接返回结果就可以了。实现这一点，需要对于每一个函数维护一个Pair类型的List，其实就是拿来模拟Map。然后每当调用函数的时候，都会先去列表中查看是否能找到之前的调用产生的Pair，有的话就直接返回Pair中的结果，没有的话就进行计算，然后把参数和结果组成一个Pair存入List中。看看示例代码~

(define fibonacci
	(letrec([memo null]
		[f (lambda (x)
			(let ([ans (assoc x memo)])
			(if ans
				(cdr ans)
				(let ([new-ans (if (or (= x 1) (= x 2))
									1
									(+ (f (- x 1)) (f (- x 2))))])
					(begin
					(set! memo (cons (cons x new-ans) memo)) newans)))))])
		f))

这门语言实在太丑了= =这段代码中用到了一个库函数，assoc。它接受一个参数，从一个Pair类型的List中找到第一个Pair的Key与传入的参数相等的Pair，正好用来查找是否已经缓存结果在Memo中。如果有，就直接返回这个Pair的cdr，否则就去计算答案，然后把答案存入Memo。

Macros

关于Racket的宏，让人印象最深的一点，就是它不会扩展宏到variable definitions中，比如说~

(let ([hd 0] [car 1]) hd) ; evaluates to 0
(let* ([hd 0] [car 1]) hd) ; evaluates to 0

如果有一个宏是把替换car为hd，同时宏定义可以扩展到variable definitions中，那第一条语句会报错，let: duplicate identifier in: hd。所以为了解决类似的问题，Racket的宏定义不会扩展到variable definitions中。variable definitions中的与宏定义中一样的字段会shadow住所有关于它的宏定义。

但是，需要注意的一点就是，不要把所有的函数都妄图写成宏定义。因为两者概念上的区别会导致一些情况下两者功能不是完全一样的。比方说，之前的Force函数，

(define-syntax my-force
	(syntax-rules ()
		[(my-force e)
			(if (mcar e)
				(mcdr e)
				(begin (set-mcar! e #t) 
						(set-mcdr! e ((mcdr e))) 
						(mcdr e)))]))

总之，我觉得如果函数可以实现，就不要用充满了谜的Macros。