递归 the little scheme y-combinator

#lang sicp
;什么是递归
;一言以蔽之：自己调用自己
;y-combinator就是递归，就是自己调用自己

(define add1
  (lambda (n)
    (+ n 1)))

(define length
  (lambda (ls)
    (cond
      ((null? ls) 0)
      (else (add1 (length (cdr ls)))))))

(newline)
(display (length '(a b c d)))
(newline)

;我们要去掉名字引用
;第一步将函数体绑定到变量上

(lambda (length)
  (lambda (ls)
    (cond
      ((null? ls) 0)
      (else (add1 (length (cdr ls)))))))


;因为递归是自己调用自己，所以让自己调用自己
;此处相当于the little scheme中
;(lambda (mk-length)
; (mk-length mk-length))

((lambda (length)
   (lambda (ls)
     (cond
       ((null? ls) 0)
       (else (add1 (length (cdr ls)))))))
 (lambda (length)
   (lambda (ls)
     (cond
       ((null? ls) 0)
       (else (add1 (length (cdr ls))))))))


;内部的length函数应该是它自己
;参考the little scheme中166和167页

((lambda (length)
   (lambda (ls)
     (cond
       ((null? ls) 0)
       (else (add1 ((length length) (cdr ls)))))))
 (lambda (length)
   (lambda (ls)
     (cond
       ((null? ls) 0)
       (else (add1 ((length length) (cdr ls))))))))

;到目前为止，这已经是一个y-combinator了，只不过目前只能适用于list，不能使用与其他的数据结构
;一个y-combinator就是实现自己调用自己，更确切的说法是不动点组合子，可参考维基百科

(newline)
(display (
((lambda (length)
   (lambda (ls)
     (cond
       ((null? ls) 0)
       (else (add1 ((length length) (cdr ls)))))))
 (lambda (length)
   (lambda (ls)
     (cond
       ((null? ls) 0)
       (else (add1 ((length length) (cdr ls))))))))

'(a b c d)
))
(newline)

;extract the pattern
;我们需要抽取公共的部分，因此需要把length函数部分排除掉
;里面有三个自调用
;先解决第一个
;消除公共子表达式
;参考the little scheme中第164页

((lambda (u)
   (u u))
 (lambda (length)
   (lambda (ls)
     (cond
       ((null? ls) 0)
       (else (add1 ((length length) (cdr ls))))))))

(newline)
(((lambda (u)
   (u u))
 (lambda (length)
   (lambda (ls)
     (cond
       ((null? ls) 0)
       (else (add1 ((length length) (cdr ls))))))))
 '(a b c d e)
 )


;factor out the inner self-appliction
;((lambda (u)
;   (u u))
; (lambda (length)
;   ((lambda (m)
;      (lambda (ls)
;        (cond
;          ((null? ls) 0)
;          (else (add1 (m (cdr ls)))))))
;    (length length))))

;中间部分就是length函数
;重点
;但是因为(length length)函数在ls参数的外面，所以会死循环，参考the little scheme中168和169页
;所以使用eta-规约，消除死循环
((lambda (u)
   (u u))
 (lambda (length)
   ((lambda (m)
      (lambda (ls)
        (cond
          ((null? ls) 0)
          (else (add1 (m (cdr ls)))))))
    (lambda (v) ((length length) v)))))

;将length函数抽出来
((lambda (f)
  ((lambda (u)
     (u u))
   (lambda (length)
     (f
      (lambda (v) ((length length) v))))))
 (lambda (m)
   (lambda (ls)
     (cond
       ((null? ls) 0)
       (else (add1 (m (cdr ls))))))))


(newline)
(((lambda (f)
  ((lambda (u)
     (u u))
   (lambda (length)
     (f
      (lambda (v) ((length length) v))))))
 (lambda (m)
   (lambda (ls)
     (cond
       ((null? ls) 0)
       (else (add1 (m (cdr ls))))))))
'(a b c))


;得到y-combinator
(lambda (f)
  ((lambda (u)
     (u u))
   (lambda (length)
     (f
      (lambda (v) ((length length) v))))))
;重新命名
(lambda (f)
  ((lambda (u) (u u))
   (lambda (x)
     (f
      (lambda (v) ((x x) v))))))

;扩展开
(lambda (f)
  ((lambda (x) (f (lambda (v) ((x x) v))))
   (lambda (x) (f (lambda (v) ((x x) v))))))


(((lambda (f)
  ((lambda (x) (f (lambda (v) ((x x) v))))
   (lambda (x) (f (lambda (v) ((x x) v))))))
 (lambda (length)
   (lambda (ls)
     (cond
       ((null? ls) 0)
       (else (add1 (length (cdr ls))))))))
'(a b c d e f g h i))

;不使用eat规约，对于传名的语言
(lambda (f)
  ((lambda (x) (f (x x)))
   (lambda (x) (f (x x)))))




     

运行结果：

4
#
#
#

4
#

5
#
#

3
#
#
#
9
#
>