The Way 2 Inner Peace.

欧拉项目第65题.

#lang racket

(define (k-con n f init)
  (let loop([i n] [r 0])
    (cond [(= 1 i) (+ init r)]
          [else (loop (sub1 i) (/ 1 (+ r (f i))))])))
          
;; ith convergent of sqrt(2)
(define (sqrt2 i)
  (k-con i (λ (x) 2) 1))

;; ith convergent of e
(define (con-e i)
  (k-con i (λ (x) 
             (let-values ([(q r) (quotient/remainder x 3)])
               (if (zero? r) (* 2 q) 1)))
         2))

(numerator (con-e 100))

 

scheme Scheme Comments(0) 2014年12月12日 22:22

得到Y组合子

我把Y组合子是什么给忘了.回顾了下手头的东西.发现还是the little schemer里讲的最明白.现整理如下.

有如下可获得list长度的函数length:

(define (length l)
    (cond
      [(null? l) 0]
      [else (add1 (length (cdr l)))]))

可以看到length的定义中调用了自身.如果现在我们没有define,那么我们该怎样得到length呢?

 

  1. 已知.如果一个列表为空.那么它的长度是0.所以毫无疑问.可以得到一个返回空列表长度0的函数(这是一句废话. -_-!).那么就给它取个名字length0.因为它的输入只能是空列表.对于其他的输入.随便给个什么.空值.错误.或者死循环都好.因为我们根本不会用它去求非空列表的长度.

     

    (λ(l)
  (cond
    [(null? l) 0]
    [else (add1 (void (cdr l)))]))

    那么有了length0,就可以得到length1.依次类推可以得到length2,length3....length1如下.

    (λ(l)
  (cond
    [(null? l) 0]
    [else (add1 ((λ(l)
                   (cond
                     [(null? l) 0]
                     [else (add1 (void))]))
                 (cdr l)))]))

    length1可以得到空列表或者只含一个元素的列表的长度.

     

  2. 现在再来看length0.可以将void作为参数传入,那么length0又可以写成.

     

    ((λ(length)
   (λ(l)
     (cond
       [(null? l) 0]
       [else (add1 (length (cdr l)))])))
 void)

    同理,length1可以写成

    ((λ(length)
   (λ(l)
     (cond
       [(null? l) 0]
       [else (add1 (length (cdr l)))])))
 ((λ(length)
    (λ(l)
      (cond
        [(null? l) 0]
        [else (add1 (length (cdr l)))])))
  void))

     

  3. 再抽象一抽.它还是length0

     

    ((λ (mk-length)
   (mk-length void))
 (λ(length)
   (λ(l)
     (cond
       [(null? l) 0]
       [else (add1 (length (cdr l)))]))))

    length1:

    ((λ (mk-length)
   (mk-length (mk-length void)))
 (λ(length)
   (λ(l)
     (cond
       [(null? l) 0]
       [else (add1 (length (cdr l)))]))))

     

  4. 既然void是期望中永远都不会用到的东西.那么把mk-length传入它自己也没有什么问题吧.得到下面这样的length0

     

    ((λ (mk-length)
   (mk-length mk-length))
 (λ(mk-length)
   (λ(l)
     (cond
       [(null? l) 0]
       [else (add1 (mk-length (cdr l)))]))))

    再调用一次.得到length1:

    ((λ (mk-length)
   (mk-length mk-length))
 (λ(mk-length)
   (λ(l)
     (cond
       [(null? l) 0]
       [else (add1 ((mk-length void) (cdr l)))]))))

    (notes:I dont know how to write length2)

     

  5. 让mk-length不停的调用自己.就得到了length:

     

    ((λ (mk-length)
   (mk-length mk-length))
 (λ(mk-length)
   (λ(l)
     (cond
       [(null? l) 0]
       [else (add1 ((mk-length mk-length)(cdr l)))]))))

     

  6. 如果将(mk-length mk-length)作为参数.即写为:

     

    ((λ (mk-length)
   (mk-length mk-length))
 (λ(mk-length)
   ((λ(length)
      (λ(l)
        (cond
          [(null? l) 0]
          [else 
           (add1 
            (length(cdr l)))])))
    (mk-length mk-length))))

    这样是不行的.这样mk-length 会不停的调用自己.陷入死循环.

     

  7. 因为

     

    (λ(x)
  ((mk-length mk-length)x))

    既是

    (mk-length mk-length)

    所以

    length可以写做:

    ((λ (mk-length)
   (mk-length mk-length))
 (λ(mk-length)
   (λ(l)
     (cond
       [(null? l) 0]
       [else
        (add1 
         ((λ(x)
            ((mk-length mk-length)x))(cdr l)))]))))

    此时.用lambda包装过(mk-length mk-length)的就可以写做参数传入了,即:

    ((λ (mk-length)
   (mk-length mk-length))
 (λ(mk-length)
   ((λ(length)
      (λ(l)
        (cond
          [(null? l) 0]
          [else
           (add1 
            (length
             (cdr l)))])))
    (λ(x)
      ((mk-length mk-length)x)))))

     

  8. 将最像length的那部分移出来,就得到了应用序的Y组合子.这就是不用define的length:

     

    ((λ(le)
   ((λ (mk-length)
      (mk-length mk-length))
    (λ(mk-length)
      (le
       (λ(x)
         ((mk-length mk-length)x))))))
 (λ(length)
   (λ(l)
     (cond
       [(null? l) 0]
       [else
        (add1 
         (length
          (cdr l)))]))))

    Y组合子就是这样的:

    (λ(le)
   ((λ (f)
      (f f))
    (λ(f)
      (le(λ(x)
           ((f f)x))))))

    改个名字.加个语法糖:

    (lambda (le)
  (let ([g (λ(f)
             (le(λ(x)
                  ((f f)x))))])
    (g g)))

    试试不用define的fact

    ((lambda (le)
  (let ([f (λ(f)
             (le(λ(x)
                  ((f f)x))))])
    (f f)))
   (λ(fact)
     (lambda (n)
    (if (< n 2) 1 (* n (fact (- n 1)))))))

 

参考: The Little Schemer

scheme Scheme Comments(1) 2012年12月09日 15:15

闭包

有下面一段代码:

(((λ(x)
    (λ(y)
      (+ x y)))
  4)
 5)

运行的结果是9.在第二个函数中有一个自由变量x,x的值是第一个函数的参数.即4.

若没有闭包,那么运行的结果就是错误:x未定义之类的.

如果将函数看作一个类型lamC,它有两部分组成,参数和函数体.其中参数是symbol,函数体是expression.即

[lamC (arg : symbol) (body : ExprC)]

那么闭包的类型看作做这样:

[closV (arg : symbol)
       (body : ExprC)
       (env : Env)]

Env即是环境.一个名与值对绑定的表.它取决于引用这个函数的外部.

上一篇博文中的例子写成下面这样就可以运行得到7了.

((λ(x)
   ((λ(y)
      (+ x y))
    4))
 3)

第二个匿名函数的外部环境中有x=4的这样的绑定.所以它在遇到自由变量x的时候.会去它的环境中查找得到x=4,所以可以正确运行了.

参考:

scheme Scheme Comments(0) 2012年12月03日 19:47

静态作用域与动态作用域

有如下一段scheme代码:

(define (f1 x) (f2 4))
(define (f2 y) (+ x y))
 
(f1 3)

若在一个为动态作用域的实现中,其结果是7,而在静态作用域的实现中,结果是错误.

动态作用域(dynamic scope)中,环境(environment)随着程序的运行而增长.这样的结果就是一个"变量"?(identifier)是否在环境中是否有值取决于它是否被执行过.

静态作用域(static scope),也叫词法作用域(lexical scope),词法是指"函数定义时的作用域",静态则是值"不随执行(调用)变化".一个变量是否有值则取决于1.它是否被绑定?2.如果绑定了.在哪个环境中?

大多数语言都使用静态作用域.如 Emacs Lisp,Common Lisp,Perl可使用动态作用域.

动态作用域的缺点比如阅读困难.结构控制复杂度的增加.

参考:

scheme Scheme Comments(0) 2012年12月01日 21:46

丘奇数

来自sicp练习2.6,题目是这样说的:

在一个可以对过程进行各种操作的语言里,我们可以完全没有数(至少在只考虑非负整数的情况下),可以将0和加一操作实现为:

(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
  (λ(f)
    (λ(x)
      (f ((n f) x)))))

这一表示形式称为Church计数,名字来源于其发明人数理逻辑学家Alonzo Church (丘奇),λ演算也是他发明的.

请直接定义one和two(不用zero和add-1)(提示:利用代换去求值(add-1 zero)).请给出加法过程 + 的一个直接定义(不要通过反复应用add-1)

在做题之前,先来看看其他用λ算子的有趣实现.

1.表示布尔值

(define true 
  (λ (x) 
    (λ (y) x)))

(define false
  (λ (x) 
    (λ (y) y)))

(define if 
  (λ (v) 
    (λ (t) 
      (λ (f) ((v t) f)))))

true是一个接受一个参数x的函数.此函数返回一个接受参数y的函数.此函数返回true接受的参数x.

现在我们希望 (if true 1 0) 返回1,来看下是不是这样的.归约过程如下:

(((if true)1)0)

((((λ (v) 
    (λ (t) 
      (λ (f) 
        ((v t) f))))
 (λ (x) 
    (λ (y) x)))1)0)

(((λ (t) 
    (λ (f) 
      (((λ (x) 
          (λ (y) x)) t) f)))1)0)

(((λ (x) 
    (λ (y) x))
  1) 0)

 ((λ (y) 1)0)
 
 1

应用(λ (v) (λ (t) (λ (f) ((v t) f)))) == (λ (v t f)((v t) f))

if可以简写为:

(define if
  (λ (v t f)
    ((v t) f)))

这样就可以直接用 (if true 1 0) 而不是 (((if true)1)0) 了.

2.表示序对

用过程表示序对在sicp里已经有了.这里是另一个版本.

(define mkpair
  (λ (x)
    (λ (y)
      (λ (s)
        ((s x) y)))))

(define fst
  (λ(p)
    (p true)))

(define snd 
  (λ(p)
    (p false)))

调用:

> (fst ((mkpair 1) 2))
1

3.现在来看丘奇数

已经定义了zero和add-1,那么我们希望(add-1 zero)就能得到one的第一定义:

(add-1 zero)

(add-1 (λ(f)
         (λ(x) x)))

;α relation:
;different name means nothing
((λ(n)
   (λ(f)
     (λ(x)
       (f ((n f) x)))))
 (λ(b)
   (λ(a) a)))

(λ(f)
  (λ(x)
    (f 
     (((λ(b)
         (λ(a) a)) f) x))))

(λ(f)
  (λ(x)
    (f 
     ((λ(a) a) x))))

(λ(f)
  (λ(x)
    (f x)))

那么one的定义就是:

(define one
  (λ(f)
    (λ(x)
      (f x))))

同理,two的定义就是:

(define two
  (λ(f)
    (λ (x)
      (f (f x)))))

由此可见.丘奇数中的数字n就是一个以一个函数f为参数的一个高阶函数.它返回一个函数,此函数有一个参数x,它将f作用在x上n次.

由此,add接受两个丘奇数n和m.返回的丘奇数n+m是将f作用于x上n+m次的函数,由此.可将add定义如下:

(define add
  (λ(m)
    (λ(n)
      (λ(f)
        (λ(x)
          ???)))))

现在来做填空题了.先来观察题目中已经定义的add-1:

(define (add-1 n)
  (λ(f)
    (λ(x)
      (f ((n f) x)))))

其中的((n f) x)得到的是什么?回想n的定义是将f作用于x n次,那么((n f) x)得到的就是将f作用于x n次后的值.

那么(f ((n f) x))就是将得到的这个值在作用一次f,而f和x都是不知道的,因为它们是函数的参数.如此就得到了n+1的定义.

那么add中的问号就应该是得到f作用于x n次后的值.再将这个值当作x,并它作用m次f,于是,add的定义得到:

(define add
  (λ(m)
    (λ(n)
      (λ(f)
        (λ(x)
          ((m f)
           ((n f) x)))))))

验证下:

> ((((add one) two) add1) 4)
7

正确~

可以得到乘法mult和sub-1的定义.mult接受m和n,将(n f)作为新的f,并传入m.sub-1则是先判断n是不是0,是则返回0,否则返回n-1.

(define mult
  (λ(m)
    (λ(n)
      (λ(f)
        (m(n f))))))

(define sub1
  (λ(n)
    (λ(f)
      (λ(x)
        (((n (λ(g)
               (λ(h)
                 (h (g f)))))
         (λ(u)
           x))
         (λ(u)
           u))))))

参考:

scheme lambda Scheme Comments(1) 2012年11月17日 21:45