ANSI Common Lisp 学习笔记 第五章

scinart posted @ 2013年5月06日 20:28 in Lisp , 2462 阅读

#+STARTUP: content

;; #+TODO: TODO(t!) | DONE(d!) CANCELED(c@/!)

;; created at 2013-04-23 Tuesday 16:20:37

;; Time-stamp: <2013-05-06 20:25:24 scinart>

;; by scinart

* 第五章:控制流

2.2 节介绍过 Common Lisp

的求值规则,现在你应该很熟悉了。本章的操作符都有一个共同点,就是它们都违反了求值规则。这些操作符让你决定在程序当中何时要求值。如果普通的函数调用是 Lisp 程序的树叶的话,那这些操作符就是连结树叶的树枝。 ** 5.1 区块 (Blocks)

Common Lisp 有三个构造区块(block)的基本操作符: progn 、 block 以及 tagbody 。

*** progn 我们已经看过 progn 了。在 progn 主体中的表达式会依序求值,并返回最後一个表达式的值:

(progn
  (format t "a")
  (format t "b")
  (+ 11 12))

由於只返回最後一个表达式的值,代表著使用 progn (或任何区块)涵盖了副作用。

*** block

一个 block 像是带有名字及紧急出口的 progn 。第一个实参应为符号。这成为了区块的名字。在主体中的任何地方,可以停止求值,并通过使用 return-from 指定区块的名字,来立即返回数值:

(block head
  (format t "Here we go.")
  (return-from head 'idea)
  (format t "We'll never see this."))

Here we go.

IDEA

调用 return-from 允许你的程序,从代码的任何地方,突然但优雅地退出。第二个传给 return-from 的实参,用来作为以第一个实参为名的区块的返回值。在 return-from 之後的表达式不会被求值。

*** nil 区块

许多接受一个表达式主体的 Common Lisp 操作符,皆隐含在一个叫做 nil 的区块里。比如,所有由 do 构造的迭代函数:

(dolist (x '(a b c d e))
    (format t "~A " x)
    (if (eql x 'c)
        (return 'done)))

A B C

DONE

也有一个 return 宏,它把传入的参数当做封闭区块 nil 的返回值:

(block nil
  (return 27))

*** defun 区块

使用 defun 定义的函数主体,都隐含在一个与函数同名的区块,所以你可以:

(defun foo ()
  (return-from foo 27))

*** tip: 在一个显式或隐式的 block 外,不论是 return-from 或 return 都不会工作。

*** 例子: read-integer

(defun read-integer (str)
  (let ((accum 0))
    (dotimes (pos (length str))
      (let ((i (digit-char-p (char str pos))))
        (if i
            (setf accum (+ (* accum 10) i))
            (return-from read-integer nil))))
    accum))

*** tagbody 略

** 5.2 语境 (Context)

*** let

*** let*

** 5.3 条件 (Conditionals)

*** if

*** when

*** unless

*** cond

*** case

当你想要把一个数值与一系列的常量比较时,有 case 可以用。我们可以使用 case 来定义一个函数,返回每个月份中的天数:

(defun month-length (mon)
  (case mon
    ((jan mar may jul aug oct dec) 31)
    ((apr jun sept nov) 30)
    (feb (if (leap-year) 29 28))
    (otherwise "unknown month")))

一个 case 表达式由一个实参开始,此实参会被拿来与每个子句的键值做比较。接着是零个或多个子句,每个子句由一个或一串键值开始,跟随着零个或多个表达式。键值被视为常量;它们不会被求值。第一个参数的值被拿来与子句中的键值做比较 (使用 eql )。如果匹配时,子句剩馀的表达式会被求值,并将最後一个求值作为 case 的返回值。

缺省子句的键值可以是 t 或 otherwise 。如果没有子句符合时,或是子句只包含键值时,

*** typecase

typecase 宏与 case 相似,除了每个子句中的键值应为类型修饰符 (type specifiers),以及第一个实参与键值比较的函数使用 typep 而不是 eql (一个 typecase 的例子在 107 页)。 译注: 6.5 小节。

** 5.4 迭代 (Iteration)

*** do

最基本的迭代操作符是 do ,在 2.13 小节介绍过。由於 do 包含了隐式的 block 及 tagbody ,我们现在知道是可以在 do 主体内使用 return 、 return-from 以及 go 。

(do (/variable-definition*/)
    (/end-test-form result-form*/)
  /statement*/)

每一个variable-definition引入了一个将存在于循环体作用域之内的变量。单一变量定义的完整形式是一个含有三个元素的列表

(var init-form step-form)

(defun fib (x)
  "calculate nth fibonacci number"
  (do ((n 0 (1+ n))
       (cur 0 next)
       (next 1 (+ cur next)))
      ((= x n) (format t "ends here") cur)
    (format t "n is ~s now~%" n)))
(fib 11)

*** do 与 do*

当同时更新超过一个变量时,问题来了,如果一个 update 形式,引用到一个拥有自己的 update 形式的变量时,它会被更新呢?或是获得前一次迭代的值?使用 do 的话,它获得後者的值:

(let ((x 'a))
  (do ((x 1 (+ x 1))
       (y x x))
      ((> x 5))
    (format t "(~A ~A)  " x y)))

;;(1 A) (2 1) (3 2) (4 3) (5 4)

每一次迭代时, x 获得先前的值,加上一; y 也获得 x 的前一次数值。

但也有一个 do* ,它有着和 let 与 let* 一样的关系。任何 initial 或 update 形式可以参照到前一个子句的变量,并会获得当下的值:

(do* ((x 1 (+ x 1))
      (y x x))
     ((> x 5))
  (format t "(~A ~A) " x y))

;; (1 1) (2 2) (3 3) (4 4) (5 5)

*** THE POINT OF do

注解

do 的重点 (THE POINT OF do)

在 “The Evolution of Lisp” 里,Steele 与 Garbriel 陈述了 do 的重点, 表达的实在太好了,值得整个在这里引用过来:

撇开争论语法不谈,有件事要说明的是,在任何一个编程语言中,一个循环若一次只能更新一个变量是毫无用处的。 几乎在任何情况下,会有一个变量用来产生下个值,而另一个变量用来累积结果。如果循环语法只能产生变量, 那么累积结果就得藉由赋值语句来“手动”实现…或有其他的副作用。具有多变量的 do 循环,体现了产生与累积的本质对称性,允许可以无副作用地表达迭代过程:

(defun factorial (n)
  (do ((j n (- j 1))
       (f 1 (* j f)))
    ((= j 0) f)))

当然在 step 形式里实现所有的实际工作,一个没有主体的 do 循环形式是较不寻常的。

*** dolist

(dolist (x '(a b c d) 'done)
    (format t "~A " x))

A B C D

DONE

*** dotimes

(dotimes (x 5 x)
  (format t "~A " x))

0 1 2 3 4

5

*** mapc

函数 mapc 和 mapcar 很像,但不会 cons 一个新列表作为返回值,所以使用的唯一理由是为了副作用。它们比 dolist 来得灵活,因为可以同时遍历多个列表:

(mapc #'(lambda (x y)
	  (format t "~A ~A  " x y))
      '(hip flip slip)
      '(hop flop slop))

HIP HOP FLIP FLOP SLIP SLOP

(HIP FLIP SLIP)

总是返回第二个参数。

** 5.5 多值 (Multiple Values)

*** values 函数返回多个数值。它一个不少地返回你作为数值所传入的实参:

(values 'a nil (+ 2 4))

然而若只预期一个返回值时,第一个之外的值会被舍弃:

(let ((x (values 1 2)))
  x)

*** multiple-value-bind

要接收多个数值,我们使用 multiple-value-bind :

如果变量的数量大於数值的数量,剩馀的变量会是 nil 。如果数值的数量大於变量的数量,多馀的值会被舍弃。

(multiple-value-bind (x y z) (values 1 2)
    (list x y z))
(1 2 NIL)
(get-decoded-time)

*** multiple-value-call

你可以藉由 multiple-value-call 将多值作为实参传给第二个函数:

(multiple-value-call #'+ (values 1 2 3))

*** 还有一个函数是 multiple-value-list :

(multiple-value-list (values 'a 'b 'c))

看起来像是使用 #'list 作为第一个参数的来调用 multiple-value-call 。

** TODO 5.6 中止 (Aborts)

** TODO 5.7 示例:日期运算 (Example: Date Arithmetic)

** Chapter 5 练习 (Exercises)

*** 将下列表达式翻译成没有使用 let 与 let* ,并使同样的表达式不被求值 2 次。

(let ((x (car y)))
  (cons x x))
(let* ((w (car x))
       (y (+ w z)))
  (cons w y))
((lambda (x) (cons x x)) (car y))
((lambda (w) ((lambda (y) (cons w y))
	      (+ w z)))
 (car x))

*** 使用 cond 重写 29 页的 mystery 函数。(译注: 第二章的练习第 5 题的 (b) 部分)

(defun mystery (x y)
  (if (null y)
      nil
      (if (eql (car y) x)
	  0
	  (let ((z (mystery x (cdr y))))
	    (and z (+ z 1))))))

;; 我原来的注释

;; find if y contains x and return position

(defun mystery (x y)
  (cond ((null y) nil)
	((eql (car y) x) 0)
	(t (let ((z (mystery x (cdr y))))
	     (and z (+ z 1))))))

;; test (mystery 6 '(4 6 8))

*** 定义一个返回其实参平方的函数,而当实参是一个正整数且小於等於 5 时,不要计算其平方。

(defun mysquare (x)
  (cond ((integerp x)
	 (cond ((= x 1) 10)
	       ((= x 2) 40)
	       ((= x 3) 90)
	       ((= x 4) 160)
	       ((= x 5) 250)
	       (t (* x x))))
	(t (* x x))))

;; test (mysquare 6)

*** TODO 使用 case 与 svref 重写 month-num (图 5.1)。

*** 定义一个迭代与递归版本的函数,接受一个对象 x 与向量 v ,并返回一个列表,包含了向量 v 当中,所有直接在 x 之前的对象:

(precedes #\a "abracadabra")
(#\c #\d #\r)

;; recursion

(defun precedes (e v)
  (if (< (length v) 2)
      nil
      (if (equal e (aref v 1))
	  (union (list (aref v 0))
		 (precedes e (subseq v 1)))
	  (precedes e (subseq v 1)))))

;; tail recursion

(defun precedes (e v &optional (index 1) (lst nil))
  (if (= index (length v))
      lst
      (if (equal e (aref v index))
	  (precedes e
		    v
		    (+ 1 index) 
		    (nunion (list (aref v (- index 1))) lst))
	  (precedes e
		    v
		    (+ 1 index)
		    lst))))

;; iteration

(defun precedes (e v)
  (let ((len (length v))
	(result nil))
    (dotimes (i len result)
      (if (and (> i 0)
	       (equal (aref v i) e))relust
	  (setf result (nunion result (list (aref v (- i 1)))))))))

*** 定义一个迭代与递归版本的函数,接受一个对象与列表,并返回一个新的列表,在原本列表的对象之间加上传入的对象:

(intersperse '- '(a b c d))
(A - B - C - D)

;; recursion

(defun intersperse (e lst)
  (if (null (cdr lst))
      lst
      (cons (car lst) (cons e (intersperse e (cdr lst))))))

;; what's the difference?

*** 定义一个接受一系列数字的函数,并在若且唯若每一对(pair)数字的差为一时,返回真,使用

(a) 递归

(b) do

(c) mapc 与 return

(defun siblings (&rest lst)
  "if null, all test completed.
   if odd parameters, nil.
   test the first two pairs and recursively call the rest
   seems to work
   2013-05-05 Sunday 23:23:58 by Scinart"
  (if (null lst)
      t
      (if (null (cdr lst))
	  nil
	  (and (= 1 (abs (- (car lst) (cadr lst))))
	       (apply #'siblings (cddr lst))))))
(defun siblings (&rest lst)
  "seems to work
   2013-05-05 Sunday 23:47:10 by Scinart
   guarantee length of list > 2
   and validify two elements at one time"
  (if (or (null lst) (null (cdr lst)))
      nil
      (do ((a (car lst) (car c))
	   (b (cadr lst) (cadr c))
	   (c lst))
	  ((or (null c) (null (cdr c)))
	   (if (null c)
	       t
	       nil))
	(if (not (= 1 (abs (- a b))))
	    (return nil)
	    (setf c (cddr c))))))
(defun siblings (p &rest others)
  "难道我理解错题意了,用mapc怎么做?
   此题的测试用例 (siblings '(1 2) '(4 8) '(6 5))
   2013-05-05 Sunday 23:57:30 by Scinarta"
  (mapc #'(lambda (p)
	    (if (not (= 1 (abs (- (car p) (cadr p)))))
		(return-from siblings nil))) (cons p others)))

*** TODO 定义一个单递归函数,返回两个值,分别是向量的最大与最小值。

*** TODO 图 3.12 的程序在找到一个完整的路径时,仍持续遍历伫列。在搜索范围大时,这可能会产生问题。

(a) 使用 catch 与 throw 来变更程序,使其找到第一个完整路径时,直接返回它。

(b) 重写一个做到同样事情的程序,但不使用 catch 与 throw。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter