20121231
2012又要结束了.也不是非得等到2012的最后一天才来写这个总结.太早了没想好.太晚了2012该做的事情不该放到2013.去找了我写的那篇对去年总结的20120101来看,想看看今年对计划的完成有没有达到预期.顺便回顾下去年的自己.结果真是..怎么就对自己的写的东西这么嫌弃呢.对这个.真的没有什么好说的.那里面本来也就没什么计划什么的.小情绪而已.好吧.都是记录而已.
是不是又要写流水帐呢.想到哪里写到哪里好了.
通过豆瓣统计工具.我在2012年读了37本书.其中有11本是技术相关的.剩下的都是小说历史等等.还是太懒惰了...
这一年变化还是颇多.从二月份开始在跟Udacity的课.但是到现在也才真正的完成了4门课.不过.好歹会用python写hello world了.九月份写了一个查单词的火狐扩展.addons.mozilla.org的审核没有通过.因为我直接修改了innerHTML.到现在为止.用户应该只有我一个人.那我就自己用呗.反正写的动机就是满足自用.不接着折腾了.九月份还参加了两个开源项目.一个是GAE上的聊天室.一个是微盘的命令行操作.基本的功能完成后也没有动力接着参与进去了..呃.这都算是自己的第一二三项目吧.有些虎头蛇尾的.十月份的时候对学校对自己相当不满.把自己以前翻译的文章,找来看了看.大学真的不是当初想的那个样子.每天都是没用的课.以及身边的蠢货.和莫名其妙的来自学校的要求.所以我萌生了退学的愿望.纠结了两天.看知乎上的问答.以及别人关于退学的讨论.以及和朋友的聊天.冷静下来了.退学并不能解决问题.然后看了sicp.没看完.看了大概三四章.习题也都做了.影响很大.
看这一年的自己和去年的自己.变化应该是有的吧.没变的还是一个人在自学编程.铁了心的是要做一个程序员吧.说的是 On the way to inner peace.我也不知道到底什么时候才能真正的达到内心宁静.对好多诱惑还是不能抵挡....
至于前半年.实在没什么好说的.暑假反正是被完完全全的浪费掉了.哦.对了.暑假还有个实习的面试.相当不成功.
2013.我想好好把Udacity和Coursera已经选了的课好好上了.重新学习emacs和elisp.自己做点东西出来.找个实习.不考研了
还有.这个博客已经完全的变成笔记本了.某天就搬个家也说不定.
其实以上都是我的胡言乱语,只有这句是我想说的:
再见,我的2012.
得到Y组合子
我把Y组合子是什么给忘了.回顾了下手头的东西.发现还是the little schemer里讲的最明白.现整理如下.
有如下可获得list长度的函数length:
(define (length l)
(cond
[(null? l) 0]
[else (add1 (length (cdr l)))]))
可以看到length的定义中调用了自身.如果现在我们没有define,那么我们该怎样得到length呢?
-
已知.如果一个列表为空.那么它的长度是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可以得到空列表或者只含一个元素的列表的长度.
-
现在再来看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)) -
再抽象一抽.它还是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)))])))) -
既然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)
-
让mk-length不停的调用自己.就得到了length:
((λ (mk-length) (mk-length mk-length)) (λ(mk-length) (λ(l) (cond [(null? l) 0] [else (add1 ((mk-length mk-length)(cdr l)))])))) -
如果将(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 会不停的调用自己.陷入死循环.
-
因为
(λ(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))))) -
将最像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)))))))
闭包
有下面一段代码:
(((λ(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代码:
(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可使用动态作用域.
动态作用域的缺点比如阅读困难.结构控制复杂度的增加.
参考:
丘奇数
来自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))))))
参考:
