The Way 2 Inner Peace.

又十诫

来自The seasoned schemer

The Next Ten Commandments

 

The Eleventh Commandment

Use additional arguments when a function needs to know what other arguments to the function have been like so far.

 

 

The Twelfth Commandment

Use (letrec ...) to remove arguments that do not change for recursive applications.

 

 

The Thirteenth Commandment

Use(letrec ...) to hide and to protect functions.

 

 

The Fourteenth Commandment

Use(letcc1 ...) to return values abruptly and promptly.

 

 

The Fifteenth Commandment

Use (let ...) to name the values of repeated expressions in a function definition if they may be evaluated twice for one and t he same use of the function. And use (let...) to name the values of expressions(without set!) that are re-evaluated every time a function is used.

 

 

The Sixteenth Commandment

Use (set! ...)only with names defined in (let ...)s.

 

 

The Seventeenth Commandment

Use(set! x ...) for (let((x ...)) ...) only if there is at least one (lambda ... between it and the(let ...),or if the new value for x is a function that refers to x .

 

 

The Eighteenth Commandment

Use (set! x ...) only when the value that x refers to is no longer needed.

 

 

The Nineteenth Commandment

Use (set! ...) to remember valuable things between two distinct uses of a function.

 

 

The Twentieth Commandment

When thinking about a value created with (letcc ...),write down the function that is equivalent but does not forget. Then, when you use it, remember to forget.

 


1:letcc is call-with-current-continuation or call/cc in scheme

let,let*和letrec

在scheme中.let,let*和letrec的形式均写做:(id val-expr).即:

(let ([id val-expr] ...) body ...+),(let* ([id val-expr] ...) body ...+),(letrec ([id val-expr] ...) body ...+)

三者的不同在于,对id及val-expr的运算顺序不同.由此导致的结果也不同.

在let中.先依此所有的计算val-expr.在依此所有的计算id.

在let*中.先计算一个val-expr,将其赋值给id.在进行下一个(id val-expr)的计算.

在letrec中.id首先均为undefined.然后计算所有的val-expr.

由此:

(define foo 5)
;; foo 現在取值 5
(let ((foo 10))
  ;; foo 現在取值 10
  )
;; foo 現在取值 5

这三者的区别在于,let所绑定的变量仅在它的区块内有效,而let*所绑定的变量可以在以下的绑定中使用,例如,

(let* ((var1 10)
       (var2 (+ var1 5)))
  var1)
;; 返回 15
;; 如果僅使用 let,程式會出錯。

letrec所绑定的变量可以互相引用。因此,letrec通常被用于双重递归:

(letrec ((female (lambda(n)
                   (if (= n 0) 1
                       (- n (male (female (- n 1)))))))
         (male (lambda(n)
                 (if (= n 0) 0
                     (- n (female (male (- n 1))))))))
  (display "i male(i) female(i)")(newline)
  (do ((i 0 (+ i 1)))
      ((> i 8) #f)
    (display i) (display "   ")(display (male i))(display "         ")(display (female i))
    (newline)))

(via wikipedia)

 

同时 剥去语法糖.


(let ((x 1))
  (print x))
就是
((lambda (x) (print x)) 1)
 


(letrec ((fact (lambda (x)
                 (if (= x 1)
                    x
                    (* x (fact (- x 1)))))))
  (fact 5))

((lambda (fact x)
   (fact x fact))
(lambda (x fact)
   (if (= x 1)
      x
      (* x (fact (- x 1) fact))))
5)

 

也可以这样:

(letrec ((f (lambda ...))) ...)

就是

(let ((f <undefined>))   (set! f (lambda ...)) ...)

十诫

来自<the little schemer>

 

The First Commandment
When recurring on a list of atoms, lat, ask two questions about it: (null? lat) and else.
When recurring on a number, n, ask two questions about it: (zero? n) and else.
When recurring on a list of S-expressions, l,ask three question about it: (null? l), (atom?(car l)), and else.

 

The Second Commandment
Use cons to build lists.

 

The Third Commandment
When building a list, describe the first typical element, and then cons it onto the natu­ral recursion.

 

The Fourth Commandment
Always change at least one argument while recurring.
When recurring on a list of atoms,lat,use (cdr lat).
When recurring on a num­ .ber, n, use (sub1 n).
And when recurring on a list of S-expressions, l, use (car l) and (cdr l) if neither (null? l) nor (atom? (car l)) are true.
It must be changed to be closer to termina­tion. The changing argument must be tested in the termination condition:
when using test termination with cdr, test termination with null?
and when using sub1, test termination with zero?.

 

The Fifth Commandment
When building a value with + ,always use 0 for the value of the terminating line, for adding 0 does not change the value of an addition.
When building a value with x, always use 1 for the value of the terminating line, for multiplying by 1 does not change the value of a multiplication.
When building a value with cons, always consider '()  for the value of the terminating line.

 

The Sixth Commandment
Simplify only after the function is correct.

 

The Seventh Commandment
Recur on the subparts that are of the same nature:
 • On the sublists of a list.
 • On the subexpressions of an arithmetic expression.

 

The Eighth Commandment
Use help functions to abstract from represen­tations.

 

The Ninth Commandment
Abstract common patterns with a new func­tion.


The Tenth Commandment
Build functions to collect more than one value at a time.
 

尾递归改写为递归


做备忘用.
上代码

#lang racket

;;factorial 
;;non-tail recursion

(define (fact1 n)
  (if (= 0 n)
      1
      (* n (fact1 (- n 1)))))

;;factorial
;;tail recursion
(define (fact-aux n result)
  (if (= 0 n)
      result
      (fact-aux (- n 1)(* n result))))

(define (fact2 n)
  (fact-aux n 1))

(define (fact3 n)
  (let fact-aux ([s n][result 1])
    (if (= 0 s)
        result
        (fact-aux (- s 1)(* s result)))))


;;fibonacci
;;non-tail recursion
(define (fib1 n)
  (if (< n 2)
      n
      (+ (fib1 (- n 1))(fib1 (- n 2)))))

;;fibonacci 
;; tail recursion

(define (fib-aux n next result)
  (if (= n 0)
      result
      (fib-aux (- n 1) (+ next result) next)))

(define (fib2 n)
  (fib-aux n 1 0))

(define (fib3 n)
  (define (fib-aux n next result)
    (if (= 0 n)
        result
      (fib-aux (- n 1) (+ next result) next)))
  (fib-aux n 1 0))




when converting recursive functions to tail  recursive funcion.add a auxiliary parameter.

ps. python 没有尾递归优化.
lisp系有.解释器自动将尾递归转化为迭代.

参考:

http://www.csee.umbc.edu/~chang/cs202.f98/readings/recursion.html

 

20120101

 

本来想昨天就写这篇2011的总结的.可是昨天晚上一直无法打开www.is-programmer.com.翻墙也翻的极不稳定.只能作罢.
2011我都干了些啥呢?
一月二月都没啥记忆了.三月花三百块钱买了辆自行车.然后骑了两个星期.被偷了.四月五月貌似还去找了几个校园代理来做.然后也没有挣到什么钱.六月考试月.各种忙各种茫然.七月去一个工作室做兼职前端.无非就是css,html.做做淘宝的网店装修.偶尔还切切片.改改图什么的.那一个月也算学到了不少东西.起初的目的就是挣钱.但也没挣到多少钱.这一个月倒是仔细想了想自己以后到底干嘛.一个月下来倒是坚定了自己走技术学计算机的决心.八月回家.九月军训.开学.十月开始跟着how to design programs 这本书学习.然后就到现在了.期间间歇着折腾了emacs.ubuntu.aricrack-ng.bash.还跟了stanford网络课程的机器学习这门课.
说起来这一年真的没做成什么实事.挺惭愧的.对这个学校也很失望.感觉就是看透了大学的教育.老师教的东西越来越不上心.考试只求不挂就行.比如现在人人都在图书馆看书复习.就我一人还在寝室里上网.想想反正自己以后又不可能从事本专业想关的工作.那就不挂不花钱重修就行了.现在的自己和刚进大学的自己真是差别巨大.这算是堕落了么?我也不知道.我只是想在学校多混几年.有那么多空闲的时间可以做自己想做的事.毕业说不定还考个研什么的.再在学校多玩一会儿.这是不是对自己太不负责了?我也不知道.
好吧.今天是2012的第一天.也该有点愿望希望啥的.我只希望不要挂科.不要有人来阻碍我折腾电脑.一切顺顺利利.能用racket做点东西出来.
至于这个博客.我也不希望这个博客上的自己和现实的自己有交集.这里用来记一些笔记.记录点生活.写点自己的一些小情绪就好了.如果一个陌生人在这里可以找到他想要的东西.那也不错.但我记录的目的并不是为了分享.只是为了记录.为了让自己在很久以后能够看到当时的自己.
恩.就这样.2012快乐!