Content Preview: rss
441 days ago
Section 4.3.3 当初上数分课，傅里叶级数把我们搞的欲仙欲死，过后到了常微分方程，课上老韩笑着说到了轻松的部分了，就像他爬泰山时候那个“快活三里”。这小节这几个小题是为了巩固amb-eval基础的，4.3整节的最后出现，实在有点“快活三里”的感觉。 4.50 主要不同之处就是amb中的序列是从左到右依次抽取，用的是car cdr，而这里用的是random-choose。 (define (analyze-ramb exp) (let ((cprocs (map analyze (amb-choices exp)))) (lambda (env succeed fail) (define (try-next choices) (if (null? choices) (fail) (let ((random-pick (random-choose choices))) (let ((the-right-one (car random-pick)) (rest-ones (cdr random-pick))) (the-right-one env succeed (lambda() (try-next rest-ones))))))) (try-next cprocs)))) random-choose参数为一个list，结果是一个序对，car为抽取的元素，cdr为其余的。 (define (random-choose seq) (define (random-integer-between low high) (+ low (random (+ (- high low) 1)))) (let ((ref (random-integer-between 1 (length seq)))) (define (foo k items) (if (= k 1) ...
441 days ago
Section 4.3.2 4.38 此处中译版出错：原文"Modify the multiple-dwelling procedure to omit the requirement that Smith and Fletcher do not live on adjacent floors." 翻译"增加斯迈尔和弗莱舍不住相邻层的要求。" 把omit翻译成了"增加"。 题目答案明显：去掉(require (not (= (abs (- fletcher smith)) 1)))这一句即可。 结果有5条： ((baker 1) (cooper 2) (fletcher 4) (miller 3) (smith 5)) ((baker 1) (cooper 2) (fletcher 4) (miller 5) (smith 3)) ((baker 1) (cooper 4) (fletcher 2) (miller 5) (smith 3)) ((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1)) ((baker 3) (cooper 4) (fletcher 2) (miller 5) (smith 1)) 4.39 有关系。题目中一共会通过一系列require检测5^5种情况。改变require语句的顺序就可以调节每次检测的速度，也就是把限制性强、检测起来快的原则放在前面，其余放在后面。比如(require (distinct? (list baker cooper fletcher miller smith)))这条语句就应该放在后面。 通过实验验证：把current-inexact-milliseconds放入求解过程中，用来观测运行时间。 (define (multiple-dwelling) (let ((former-time (current-inexact-milliseconds)) (baker (amb 1 2 3 4 5)) (cooper (amb 1 2 3 4 5)) (fletcher (amb 1 2 3 4 5)) (miller ...
441 days ago
Section 4.3.1 由于前两小节的习题需要amb-evaluator去测试，所以需要先把4.3.3中的求值器实现。 amb-eval相比之前两个求值器要复杂，郁闷的看了n遍。其中比较麻烦的事情就是succeed和fail过程传来传去，还有succeed的调用也让人一上来觉得不太适应。 所谓的succeed和fail，可以理解为运行过程中的两个分叉，之前接触的eval-apply循环、lazy-eval可以看做是全程succeed的情况。相类似的analyze-self-evaluating/analyze-quoted等过程，都只是传递succeed和fail过程而涉及不到运行的分叉。 处理if语句时，由于if-predict中可能有amb语句(可以造成fail)，所以要进行判断：如果if-predict是"成功的"，那么分情况考虑if-consequent或者if-alternative；若是"失败"的，就调用fail过程。书中analyze-if中的fail2只是为了在名字上与fail区分开来，实际的值也是fail，而不会存在两个不同的fail过程。 set!过程又与上面不同，由于需要消除赋值带来的副作用，所以求值assignment-value的fail过程和外层set!的fail过程是不同的，不可以像if那样直接调用过来。 个人感觉最难理解的是过程应用中的get-args过程。它的作用大概就是把apply的参数值提取出来(由于这些值都是(lambda(env succeed fail)(...)之类的东西，所以需要另写get-args而不是直接用map))。其中递归调用get-args时，增量是get-args的参数succeed的val部分。可以这么看: succeed过程实际是(lambda(args fail) (succeed args fail))，仔细观察程序可以发现，递归调用中的succeed部分是这样的：(lambda(args fail) (succeed (cons arg args) fail))，增加的那个arg就是提取出来的value。 ...
444 days ago
1. 书上提到Y combinator是在Ex 4.21中，用来实现一些不用函数名称的递归方法。 这里！有一个构造Y的过程，最后可以以一个单个参数的过程为参数(比如阶乘，fibnacci不行)，得到一个不用函数名来实现递归的过程。 其中分了6个step，个人感觉Step2--6都是中规中距的做一些文字游戏，而Step1做的工作是创造性的(也就是书中4.21给出的例子)。 Step1 中构造了一个fact-maker： (define fact-maker (lambda (procedure) (lambda (n) (if (zero? n) 1 (* n ((procedure procedure) (- n 1))))))) 然后通过(fact-maker fact-maker)来成功构造fact过程。 而后面的工作就是抽象、组合，最后形成一个有一般意义的Y combinator，不过只能形成单个参数的过程。 (define Y (lambda(X) ((lambda(proc) (X (lambda(arg) ((proc proc) arg)))) (lambda(proc) (X (lambda(arg) ((proc proc) arg))))))) 2. 视频Lecture-7a中也提到Y combinator，是在讲到求不动点的策略的时候，仿佛这个Y除了完成一些上述的小技巧之外，还有些更深层次的东西。 这里的不动点，不是狭义的指一个数值，它还包括函数过程。比如factorial过程就是 (lambda (proc) (lambda (n) (if (zero? n) 1 (* n (proc (- n 1)))))) 的fixed-point。而这里求fixed-point的方法就是无限的迭代执行，就像拿起计算器随便取一个值然后狂按cos，最后得到0.73左右的一个数。这种方法可能得到正确结果，也可能得不到，结果取决与具体问题，就像线性方程组的解的情况（唯一/无限多个/无解）。而其原理的证明据说很复杂。 所以我们需要构造一个过程，使其能表达出无限的迭代。 ...
457 days ago
Section 4.2.1 4.25 用非特殊形式的unless计算factorial会出现死循环，这是由于(factorial n)会不断的计算(factorial (- n 1))、(factorial (- (- n 1) 1))...而在此之前不会考虑过程体里面的if过程。 在正则序语言中可以。其实所谓正则序语言，并不是全部过程都不优先对参数求值(那样就永远得不到结果了...)，也是要有一些严格的基本过程做基础如if/cond等。这样在调用unless时对condition/usual-value/exception-value都会延迟求值，直到(= n 1)的判断时才会对n求值进而做判断是要执行usual-value还是exception-value。这样(factorial n)就能正常工作了。 4.26 实现： (define (eval-unless exp env) (eval (make-if (unless-pred exp) (unless-exception exp) (unless-usual exp)) env)) (define (unless-pred exp) (cadr exp)) (define (unless-exception exp) (cadddr exp)) (define (unless-usual exp) (caddr exp)) 然后加入安装包(put 'eval 'unless eval-unless) 但是如此生成为特殊形式，在环境中是不会有unless这个变量的。 比如定义这个过程，定义一个unless过程就是必要的： (define (if-or-unless operator pred consequent alternative) (operator pred consequent alternative)) 这里operator可以取if或者unless(可能把if生成表达式也是件麻烦事)。 Section 4.2.2 4.27 ;;; L-Eval input: count ;;; L-Eval output: 1 ;;; L-Eval input: w ;;; L-Eval output: 10 ;;; L-Eval input: count ;;; L-Eval ...
