向量和结构体

简介

本章中，我将讲解向量和结构体。

向量是一组通过整数索引的数据。与C语言中的数组不同，一个向量可以储存不同类型的数据。与表相比，向量更加紧凑且存取时间更短。但从另外一方面来说，向量是通过副作用来操作的，这样会造成负担。

Scheme中的结构体与C语言中的结构体类似。但Scheme中的结构体比C语言中的更容易使用，因为Scheme为结构体自动创建了读取函数和写入函数，这受益于Lisp/Scheme中的宏。

向量

字面值

向量通过闭合的#(和)表示，例如#(1 2 3)。作为字面值（literals）时，它们应该被引用（be quoted），例如：

  1. '#(1 2 3)             ; 整数向量
  2. '#(a 0 #\a)           ; 由符号、整数和字符构成的向量

向量函数

下面的函数都是R5RS规定的函数：

(vector? obj)

如果obj是一个向量则返回#t。

(make-vector k)

(make-vector k fill)

返回有k个元素的向量。如果指定了第二个参数(fill)，那么所有的元素都会被初始化为fill。

(vector obj …)

返回由参数列表构成的向量。

(vector-length vector)

返回向量vector的长度。

(vector-ref vector k)

返回向量vector的索引为k的元素。（译注：和C语言类似，向量从0开始索引。）

(vector-set! vector k obj)

将向量vector的索引为k的元素修改为obj。

(vector->list vector)

将vector转换为表。

(list->vector list)

将list转换为向量。

(vector-fill! vector fill)

将向量vector的所有元素设置为fill。

例：一个对向量中元素求和的函数。

  1. (define (vector-add v1 v2)
  2.   (let ((lenv1 (vector-length v1))
  3.           (lenv2 (vector-length v2)))
  4.     (if (= lenv1 lenv2)
  5.           (let ((v (make-vector lenv1)))
  6.             (let loop ((i 0))
  7.               (if (= i lenv1)
  8.                     v
  9.                     (begin
  10.                       (vector-set! v i (+ (vector-ref v1 i) (vector-ref v2 i)))
  11.                       (loop (+ 1 i))))))
  12.         (error "different dimensions."))))

练习1

编写一个用于计算两向量内积的函数。

结构体

大体功能

虽然R5RS中没有定义结构体，但是在很多Scheme实现中，都实现了类似于Common Lisp中的结构体。

这些结构体本质上来说都是向量。每一个槽（slot）都通过使用一个宏来命名，我将会在下一章（十五章）中讲解这个问题。结构体通过不同的属性清楚地表示数据。定义结构体的宏自动为结构体创建取值器（accessor）和赋值器（setter）。你可以通过“程序”来写程序，这被认为是Lisp/Scheme最好之处之一。通过这个功能，你可以很快写出漂亮的程序。

MIT-Scheme中的结构体

在MIT-Scheme中，结构体通过函数define-structure来定义。为了使你更加容易理解，我会用一个实例来讲解。请考虑书籍。书籍都有下列属性：

  • 标题
  • 作者
  • 出版商
  • 出版年份
  • ISBN号

因此结构体book就可以像下面这样定义：

  1. (define-structure book title authors publisher year isbn)

下面演示了如何注册“大教堂与市集（The Cathedral and Bazaar）”。

  1. (define bazaar 
  2.   (make-book 
  3.    "The Cathedral and the Bazaar"
  4.    "Eric S. Raymond"
  5.    "O'Reilly"
  6.    1999
  7.    0596001088))

然而，这样做多少有点不便，因为属性与值的关联并不清楚。参量keyword-constructor可以用于解决这个问题。下面的代码就是使用这个参量的重写版，这个版本中，属性与值的关联就非常清楚了。此外，制定这个参量后，参数的顺序就不重要了。参量copier可用于为结构体创建一个拷贝（copier）函数。

  1. (define-structure (book keyword-constructor copier) 
  2.   title authors publisher year isbn)
  4. (define bazaar 
  5.   (make-book 
  6.    'title "The Cathedral and the Bazaar"
  7.    'authors "Eric S. Raymond"
  8.    'publisher "O'Reilly"
  9.    'year 1999    
  10.    'isbn 0596001088))
  • 一个名字形如[the name of structure]?的函数用于检查某对象是否为特定结构体。例如，可使用函数book?来检查bazaar是否为book结构体的一个实例。
  1. (book? bazaar)
  2. ;Value: #t
  • 一个名字形如copy-[structure name]的函数用于拷贝结构体。例如，下面的代码演示了将bazaar拷贝到cathedral。
  1. (define cathedral (copy-book bazaar))
  • 一个名字形如[structure name]-[attribute name]的函数用于读取结构体某属性的值。例如，下面的代码演示了如何读取bazaar的title属性。
  1. (book-title bazaar)
  2. ;Value 18: "The Cathedral and the Bazaar"
  • 一个名字形如set-[结构体名称]-[属性名称]!用于将某属性设定为特定值。下面的代码演示了如何将bazaar的year字段更新到2001（《大教堂与市集》2001年再版）。
  1. (set-book-year! bazaar 2001)
  2. ;Unspecified return value
  4. (book-year bazaar)
  5. ;Value: 2001

请参阅MIT/GNU Scheme Reference: 2.10 Structure Definitions以获得关于结构体的跟多信息。

The Mastermind — 一个简单的密码破解游戏

作为向量的示例，我会演示一个简单的密码破解游戏。这是一个猜对手密码的游戏。密码是由0到9中四个不同的数组成的四位数。对手要通过使用bulls和cows的数量告知猜谜者猜测的准确程度。

  1. bull的数量（Nbull）是指值和位置都正确的数字的数量。
  2. cow的数量（Ncow）是指值正确但位置错误的数字的数量。

例如，密码是5601，猜测是1685，那么bull和cow和数分别是1和2。

计算机和用户相互猜测对方的密码。更少尝试次数的选手为胜利者。如果用户和电脑在相同的尝试次数中破解了密码就是平局。

表示四个数字

四位数字可以通过向量和计算bull以及cow的数量高效地表示。这种表达方法需要构成密码的数字都不相同。

创建长度为10的向量，每个索引（k）的值被设为k在密码中的数位。四个数位从低到高被计为1，2，3和4。如果数字没有出现，索引的值为0。例如，5601和1685可以表示如下：

  1. 5601 → #(2 1 0 0 0 4 3 0 0 0)
  2. 1685 → #(0 4 0 0 0 1 3 0 2 0)

5601这个例子中，数字0，1，5，和6分别出现在第2，第1，第4和第3位，那么在这个密码的向量表达式里索引0，1，5，6的值分别2是2，1，4和3，其他索引位都是0。

这种表达可以快速比较两个数字。如果两个向量的相同索引位的值都是正数情况下，如果值相等，就计为bull，如果值不相等，就计为cow。5601和1685这个例子的情况下，索引位6的值都为3，索引位1和索引位5的值都是正数，bull和cow的值为1和2。

程序的设计

程序的设计如下：

  1. 程序生成一个表，该表包含了所有不同四位数的向量表示。
  2. 程序从表中随机选取一个数字。
  3. 重洗步骤（1）产生的表。
  4. 程序首次猜用户的密码，用户给出bull和cow的数量。然后用户猜程序的密码，程序给出Nnull和Ncow。
  5. 重复步骤（3）直到电脑或者程序的bull数量变为4为止。如果在同一次双方的数量都变为4，就是平局。

源代码

[代码1]展示了源代码。代码很长但并不十分复杂。游戏由一个递归函数mastermind-rec执行。

[代码1]

  1.  01:     ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  2.  02:     ;;;
  3.  03:     ;;; mastermind.scm
  4.  04:     ;;; by T.Shido
  5.  05:     ;;;
  6.  06:     ;;; User and computer try to locate the four-digit integer set by the opponents each other.
  7.  07:     ;;; One who locates the integer with fewer question is the winner.
  8.  08:     ;;; The four-digit integer contains four of numerals 0--9, like 0123, 3749 etc.
  9.  09:     ;;; The opponents should tell the guesser
  10.  10:     ;;; (1) number of numerals that are shared by the guessed and set numbers
  11.  11:     ;;; at wrong position (cows)
  12.  12:     ;;; and (2) number of numerals at collect position (bulls).
  13.  13:     ;;; 
  14.  14:     ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  15.  15:     ;;;
  16.  16:     ;;; The four-digit integers are represented by 10-cell vectors in the program
  17.  17:     ;;; The value of n-th cell is the number of column that n appears in the integer.
  18.  18:     ;;; in n is not appears the value is 0.
  19.  19:     ;;; for example, 1234 is represented as #(0 4 3 2 1 0 0 0 0 0) and
  20.  20:     ;;; 3916 as #(0 2 0 4 0 0 1 0 0 3).
  21.  21:     ;;; With this inner representation, the score of the guess can be calculated faster.
  22.  22:     ;;;
  23.  23:     ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  24.  24:     
  25.  25:     
  26.  26:     ;;;
  27.  27:     (define (1- x) (- x 1))
  28.  28:     
  29.  29:     ;;;
  30.  30:     (define (char2int c)
  31.  31:       (- (char->integer c) (char->integer #\0)))
  32.  32:     
  33.  33:     ;;; converting a list of 4 numbers to the vector notation
  34.  34:     (define (ls2nvec ls)
  35.  35:       (let ((vec (make-vector 10 0)))
  36.  36:         (let loop ((i (length ls)) (ls ls))
  37.  37:           (if (> i 0)
  38.  38:           (begin
  39.  39:                (vector-set! vec (car ls) i)
  40.  40:                (loop (1- i) (cdr ls)))
  41.  41:             vec))))
  42.  42:     
  43.  43:     ;;; converting the vector notation to string
  44.  44:     (define (nvec2int vec)
  45.  45:       (let loop ((i 0) (n 0))
  46.  46:         (if (= i 10)
  47.  47:             n
  48.  48:         (let ((j (vector-ref vec i)))
  49.  49:           (loop (1+ i) (+ n (if (> j 0)
  50.  50:                                     (* i (expt 10 (1- j)))
  51.  51:                                   0)))))))
  52.  52:     
  53.  53:     ;;;
  54.  54:     (define (int2str i)
  55.  55:       (string-append
  56.  56:        (if (< i 1000) "0" "")
  57.  57:        (number->string i)))
  58.  58:     
  59.  59:     ;;; reading integer from stdin
  60.  60:     (define (read-integer str)
  61.  61:       (string->number (read-from-stdin str)))
  62.  62:     
  63.  63:     ;;;
  64.  64:     (define (read-from-stdin str)
  65.  65:       (display str)
  66.  66:       (newline)
  67.  67:       (read-line))
  68.  68:     
  69.  69:     ;;;
  70.  70:     (define (write-to-stdout . ls)
  71.  71:       (for-each (lambda (obj) (display obj)) ls)
  72.  72:       (newline))
  73.  73:     
  74.  74:     ;;; convert numeral string to the vector representation.
  75.  75:     (define (str2nvec str)
  76.  76:       (let ((vec (make-vector 10 0)))
  77.  77:         (let loop ((i (string-length str)) (ls (string->list str)))
  78.  78:           (if (pair? ls)
  79.  79:           (begin
  80.  80:                (vector-set! vec (char2int (car ls)) i)
  81.  81:                (loop (1- i) (cdr ls)))
  82.  82:             vec))))
  83.  83:     
  84.  84:     ;;; calculating the score of guess
  85.  85:     (define (scoring vec0 vec1)
  86.  86:       (let ((n (vector-length vec0)))
  87.  87:         (let loop ((i 0) (score 0))
  88.  88:           (if (< i n)
  89.  89:           (let ((d0 (vector-ref vec0 i))
  90.  90:                    (d1 (vector-ref vec1 i)))
  91.  91:                 (loop (1+ i)
  92.  92:               (+ score (if (and (< 0 d0) (< 0 d1))
  93.  93:                                    (if (= d0 d1) 5 1)
  94.  94:                                    0))))
  95.  95:             score))))
  96.  96:     
  97.  97:     ;;; show bulls and cows calculated from the score of user's guess
  98.  98:     (define (show-user-score score)
  99.  99:       (write-to-stdout "Number of bulls and cows in your guess:" )
  100. 100:       (write-to-stdout "bulls: " (quotient score 5))
  101. 101:       (write-to-stdout "cows: " (modulo score 5))
  102. 102:       (newline))
  103. 103:     
  104. 104:     ;;; calculating the score of computer's guess from bulls and cows
  105. 105:     (define (read-my-score gu0)
  106. 106:       (write-to-stdout "My guess is: " (int2str (nvec2int gu0)))
  107. 107:       (write-to-stdout "Give number of bulls and cows in my guess." )
  108. 108:       (let ((na5 (* 5 (read-integer "bulls: "))))
  109. 109:         (+ na5 (read-integer "cows: ")))) ; the score is calculated by (5 * bull + cow)
  110. 110:     
  111. 111:     ;;; reading the user guess
  112. 112:     (define (read-user-guess)
  113. 113:       (newline)
  114. 114:       (str2nvec (read-from-stdin "Give your guess.")))
  115. 115:     
  116. 116:     ;;; shuffling the list of four-digit numbers
  117. 117:     (define (shuffle-numbers ls0)
  118. 118:       (let ((vec (list->vector ls0)))
  119. 119:         (let loop ((n (vector-length vec)) (ls1 '()))
  120. 120:           (if (= n 0)
  121. 121:               ls1
  122. 122:           (let* ((r (random n))
  123. 123:              (v (vector-ref vec r)))
  124. 124:             (vector-set! vec r (vector-ref vec (1- n)))
  125. 125:             (loop (1- n) (cons v ls1)))))))
  126. 126:     
  127. 127:     ;;; making a list of four-digit numbers in which numeral 0--9 appear once
  128. 128:     (define (make-numbers)
  129. 129:       (let ((ls1 '()))
  130. 130:         (letrec ((rec (lambda (i num ls)
  131. 131:                 (if (= i 4)
  132. 132:                 (set! ls1 (cons (ls2nvec ls) ls1))
  133. 133:                 (for-each 
  134. 134:                  (lambda (n)
  135. 135:                    (rec (1+ i) (delv n num) (cons n ls)))
  136. 136:                  num)))))
  137. 137:           (rec 0 '(0 1 2 3 4 5 6 7 8 9) '()))
  138. 138:         ls1))
  139. 139:     
  140. 140:     ;;;
  141. 141:     (define (game-over sc0 sc1)
  142. 142:       (write-to-stdout
  143. 143:        (cond
  144. 144:         ((= sc0 sc1) "Draw")
  145. 145:         ((> sc0 sc1) "I won.")
  146. 146:         (else "You won.")))
  147. 147:       'game-over)
  148. 148:     
  149. 149:     (define (scoring-user-guess an0 gu1)
  150. 150:       (let ((sc1 (scoring an0 gu1)))
  151. 151:         (show-user-score sc1)
  152. 152:         sc1))
  153. 153:     
  154. 154:     ;;; Practical main function. tail recursive.
  155. 155:     (define (mastermind-rec an0 candidates)
  156. 156:       (if (null? candidates)
  157. 157:           (error "Error. You gave wrong score for my guess, probably.")
  158. 158:           (let ((gu0 (car candidates)))
  159. 159:         (let ((sc1 (scoring-user-guess an0 (read-user-guess)))
  160. 160:               (sc0 (read-my-score gu0)))
  161. 161:           (if (or (= sc0 20) (= sc1 20))
  162. 162:               (game-over sc0 sc1)
  163. 163:               (mastermind-rec an0 
  164. 164:                    (keep-matching-items 
  165. 165:                     (cdr candidates)
  166. 166:                     (lambda (x) (= (scoring gu0 x) sc0)))))))))
  167. 167:     
  168. 168:     ;;; The main function called from the top-level
  169. 169:     (define (mastermind)
  170. 170:       (let ((ls0 (make-numbers)))
  171. 171:         (mastermind-rec (list-ref ls0 (random (length ls0))) (shuffle-numbers ls0))))
行数 函数 说明
27 (1- x) x减一
30 (char2int c) 将字符c(#\0 — #\9)转换为整数（0 — 9）。
34 (ls2nvec ls) 将四个数字的表（ls）转换为向量表达式。'(5 3 6 0)->#(1 0 0 3 0 4 2 0 0 0)
44 (nvec2int vec) 将向量表达式vec转换为普通整数。
54 (int2str i) 将一个四位数i转换为字符串。如果i小于1000，’0’被置于高位。
64 (read-from-stdin str) 将str显示于标准输出，并返回用户从标准输入输入的字符串。
70 (write-to-stdout . ls) 将ls的每个元素都输出到标准输出，并在行尾插入行结束符。
75 (str2nvec str) 将用户输入的表示四位数的字符串str转换为向量表达式。
86 (scoring vec0 vec1) 以（5*Nnull + Ncow）计算两个整数（向量表达式）vec0和vec1的相似程度。
98 (show-user-score score) 通过相似度score计算Nbull和Ncow，并将它们显示在标准输出。
105 (read-my-score gu0) 显示计算机的猜测（gu0），让用户输入Nnull和Ncow，返回相似度score。
112 (read-user-guess) 返回用户猜测的向量表达式。
116 (shuffle-numbers ls0) 随机排序ls0。由于有随机读取的需求，将ls0转换为向量，然后随机读取向量的元素，以创建一个重排过的表。
128 (make-numbers) 返回由所有不同四位数构成的表。
141 (game-over sc0 sc1) 通过比较计算机的得分（sc0）和用户的得分(sc1)确定胜利者。
149 (scoring-user-guess an0 gu1) 计算计算机的密码（an0）和用户的猜测（gu1）的相似度，使用show-uuser-score输出Nbull和Ncow。
155 (mastermind-rec an0 candidates) 实际的主程序，它有两个参数；计算机密码（an0）和 猜测的表（candidate）。它计算计算机的得分（sc0）和用户的得分（sc1），如果sc0或者sc1为20，调用 (game-over sc0 sc1)。如果没有值为20，它根据sc0过滤猜测的表（candidate），并继续游戏。
169 (mastermind) 在控制台调用该函数以开始游戏。

如何玩

输入如下代码启动游戏。最好在玩之前编译（你需要编译一次）。即使程序很简单，也很难取胜。

  1. (compile-file "mastermind.scm")
  2. (load "mastermind")
  3. (mastermind)

小结

这一章，我通过玩mastermind游戏讲解了向量和结构体。附上mastermind的源代码。

我将在下一章讲自定义语法。自定义语法是Lisp/Scheme的一个优点。

习题解答

答案1

  1. (define (inner-product vec1 vec2)
  2.   (let ((len1 (vector-length vec1))
  3.           (len2 (vector-length vec2)))
  4.     (if (= len1 len2)
  5.         (let loop ((i 0) (pro 0))
  6.           (if (= i len1)
  7.               pro
  8.               (loop (+ 1 i)
  9.                   (+ pro (* (vector-ref vec1 i) (vector-ref vec2 i))))))
  10.         (error "different dimensions."))))