Scheme/Activate Thinking in Scheme/Chapter

From YuntechWiki

Jump to: navigation, search

Contents

資料 + 處理 = 程式

寫程式的目的是為了處理資料,而「處理資料」又可以被分成「處理」及「資料」兩個部分。因此,「程式 = 資料 + 處理」,而學寫程式也就必須學習如何寫「資料」與如何寫「處理」。

「資料」如何寫呢?

第一步要知道資料是如何分類的?由於資料需要分類,因此資料的類別就稱為資料型態(data types)。不同的程式語言有不同的資料分類規則,這些規則多半大同小異。以Scheme而言,最簡單的分類方法是將資料型態分成「基本(simple)」與「複和(compond)」兩大類。「基本」類的資料型態有number(數字)、symbol(符號)、boolean(布林)、character(字元)、string(字串);複和類的資料型態則包括list(串列)及vector(陣列)。以下的單元將依序介紹這幾類的資料型態。

資料型態是程式語言的一個專有名詞,它有數學上集合(set)的含意。例如:number這個資料型態,是一個由所有Scheme可處理的數字所組成的集合。這幾種資料型態的個別「資料值(data value)」(又稱constant「常數」)該如何寫呢?由於本書的主要目的是以Scheme為工具開啟讀者的程式設計思考力,因此我們不會介紹關於資料型態的所有細節,以節省讀者閱讀的負擔。我們以<data type>代表某個資料型態,以下是<number>、<boolean>、<symbol>及<list>中的幾個資料值的範例:

<number>

1.0 3/4  1.35  -3

<boolean>

#t   #f

<symbol>

'a   'abc   'x3b   'c3

<list>

'()   '(+ 2 a)   '((1 2) (a) (()))   '(x y (z))

在以上的範例中,特別要注意的是:「'」符號,這個符號在英文稱作:quote。使用它的目的是用來標示其後的字元是「資料」,若沒有被「'」則那些字元便會被當作是處理資料用的「處理」了。此外,'abc也可以寫作(quote abc)

「處理」如何寫呢?

我們先介紹最簡單的「處理」,並以範例的方式逐步說明。我們用Returns來標示某特定處理「語法」(syntax)的傳回值;而以「=>」代表執行某段程式碼後的傳回值。

syntax: (define var exp)
Returns: unspecified(不指定或沒有傳回值)

定義var的值是exp在evaluate(執行)後的return value(傳回值)。其中var是variable(變數)的縮寫,而exp是expression(式子)的縮寫。Variable是程式語言的專有名詞。定義一個變數時,會自動佔用記憶體,而每一個變數都有一個「名字」,這個「名字」對應一個記憶體的「地址」,這個「地址」存放該變數的值,而這個值又屬於一個「資料型態」。Expression也是程式語言的專有名詞。所有的資料值(data value)都是一種expression,變數也是一種expression,除此之外,還有其他的expression會依序介紹。一個expression在evaluate後會傳回一個傳回值(return value)。 以下的幾個範例特別強調使用「'」與不使用「'」的差異。

(define a 1.35)  ; 沒有傳回值(以後將省略不寫)
a => 1.35
'a => a
 
(define x3b '(+ 2 a))
x3b => (+ 2 a)
'x3b => x3b
(+ 2 a) => 3.35
 
(define nval (+ 2 a))
nval => 3.35
 
(define x '())
x => ()

如何區分「資料」與「處理」

比較「a」(使用變數a並傳回其值)與 「'a」(指a這個symbol) 及 「(+ 2 a)」(代表程序呼叫) 與 「'(+ 2 a)」(指(+ 2 a)這個list)可以幫助我們在寫程式時小心的以「'」來區分「資料」與「處理」。Scheme的主要特色之一是它的程式碼與資料值,是以同一種方式表達,因此程式的語法可以很簡潔。而這個特色也能夠比較方便的將程式碼也當成資料來處理,因此適合寫很富有變化的程式。

以上的程式碼都夾雜了說明文字。一個程式檔案除了「資料」與「處理」兩個部分外,還可以有「註解」。在Scheme中「;」之後的文字,直到換行為止,都是註解。(為了美觀起見=>之前的「;」省略)

syntax: (proc exp*)
Returns: 將執行exp*得到的0或多個傳回值傳入執行proc得到的procedure,
然後執行該procedure之後所得到的結果。

Procedure(程序)是程式語言的專有名詞。一個procedure有0或多個傳入值(exp* 代表可以有0或多個exp),這些exp在執行後的傳回值在傳入procedure並經過執行之後,便傳回一個傳回值為結果。以(- 4 1)這個例子來看,4 與 1 均為 exp,-(減號)的傳回值是減法這個procedure,因此(- 4 1)的結果為3。以下加、減與乘法的程序呼叫,是將程序放在左刮號的右邊,接著是傳入的參數,程序在呼叫後便會傳回執行的結果,而這個結果又可能成為另一個程序的傳入值:

(define a 1.35)
(+ 2 a) => 3.35
(- 4 1) => 3
(+ (- a 0.35) 10) => 11

資料存取與運算的程序

教材講解

在上一個單元,我們介紹了<number>、<boolean>、<symbol>及<list>四種data types。也使用了=、+、─等procedure。這一單元我們將介紹其他常用的幾個處理<number>、<symbol>及<list>的程序。

<number>

procedure: (+ num1 num2)
returns: (num1 + num2)
 
procedure: (- num1 num2)
returns: (num1 - num2)
 
procedure: (* num1 num2)
returns: (num1 * num2)
 
procedure: (/ num1 num2)
returns: (num1 / num2)
 
(define c 3)
(+ 2 c) => 5
(+ 1/2 2/3 c) => 25/6
 
(- c 1) => 2
(- 2 5) => -3
 
(* 2 c) => 6
(* 4 3) => 12
 
(/ 12 c) => 4
(/ 16 2) => 8
procedure: (= num1 num2)
returns: 如果num1 = num2則傳回#t,要不則傳回#f。
 
procedure: (> num1 num2)
returns: 如果num1 > num2則傳回#t,要不則傳回#f。
 
procedure: (< num1 num2)
returns: 如果num1 < num2則傳回#t,要不則傳回#f。
 
procedure: (>= num1 num2)
returns: 如果num1 >= num2則傳回#t,要不則傳回#f。
 
procedure: (<= num1 num2)
returns: 如果num1 <= num2則傳回#t,要不則傳回#f。
 
(define c 3)
(= 2 2) => #t
(= c 4) => #f
(> 4 c) => #t
(< 4 c) => #f
(>= 3 c) => #t
(<= 2 c) => #t
procedure: (number? obj)
returns: 如果obj是一個number則傳回#t,要不則傳回#f。
 
(define c 3)
(number? c) => #t
(number? 3) => #t
(number? 'c) => #f

<symbol>

procedure: (eq? obj1 obj2)
returns: 如果obj1與obj2是相同的symbol則傳回#t,要不則傳回#f。
eq?的另一個功能是比較obj1與obj2的記憶體位置是否相同,相同則傳回#t,要不則傳回#f。
(equal? obj1 obj2) 則比obj1與obj2的值是否相同,相同則傳回#t,要不則傳回#f。)
 
(define name 'paul)
(eq? 'a 'a) => #t
(eq? 'a 'b) => #f
(eq? 'a name) => #f
(eq? 'paul name) => #t
procedure: (symbol? obj)
returns: 如果obj是symbol則傳回#t,要不則傳回#f。
 
(define name 'paul)
(symbol? name) => #t
(symbol? 3) => #f
(symbol? 'a) => #t

<list>

一個list是由一對一對的pairs所構成。一對(pair)有兩個部分,分別稱為:car與cdr。以下這張圖說明了pair如何的用來建構這幾個list:(a)、(a b)、((a) b c)、((a) (b c))、(a . 1)及(a b . c)。其中(a)的car是a,而其cdr是()。(a b)的car是a,而其cdr是(b),請對照下圖依序類推。 List-diagram.jpg

List有以下幾種寫法:

  • null list(空串列): list內沒有任何的資料
'()
  • flat list(平串列):list內沒有其他的list
'(1)  '(1 a)  '(a b c)  '(1 2 3 4)
  • deep list(深串列):list內含有其他的list
'(())  '((1) ())  '((a b (1)) (1 2 3) (3))
  • improper list(反常串列):最後一對pair的cdr不是()
'(a . 1)  '(1 2 3 . 4)  '((a b) . 1)

cons是一個建構list的程序:

procedure: (cons obj1 obj2)
returns: 一個新的pair,這個pair的car是obj1,cdr是obj2。
 
(cons 'a '()) => (a)
(cons 'a '(b c)) => (a b c)
(cons 'x 1) => (x . 1)

以下則是取出list中資料的程序:

procedure: (car pair)
returns: pair的car
 
(car '(a)) => a
(car '((a) b c)) => (a)
(car (cons 'x 1)) => x
procedure: (cdr pair)
returns: pair的cdr
 
(cdr '((a))) => ()
(cdr '(a b c)) => (b c)
(cdr (cons 'x 1)) => 1
procedure: (caar pair) 
returns: (car (car pair))
 
procedure: (cadr pair)
returns: (car (cdr pair))

procedure: (cddddr pair)
returns: (cdr (cdr (cdr (cdr pair))))
 
(caar '((x) y)) => x
(cadr '(x y z)) => y
(cdddr '(1 2 3 4)) => (4)
(cadadr '(1 (2 3))) => 3

以下是幾個與list有關的條件判斷程序:

procedure: (null? obj)
returns: 若obj是一個空串列則傳回#t,要不則傳回#f
 
(null? '()) => #t
(null? '(a)) => #f
(null? (cdr '(a))) => #t
(null? 'a) => #f
procedure: (list? obj)
returns:若obj是一個串列(不可是反常串列)則傳回#t,
要不則傳回#f
 
(list? '()) => #t
(list? '(x y z)) => #t
(list? 'a) => #f
(list? 3) => #f
(list? (cons 2 3)) => #f
procedure: (pair? obj)
returns:若obj是一個pair則傳回#t,要不則傳回#f
 
(pair? (cons 2 3)) => #t
(pair? '()) => #f
(pair? '(x y z)) => #t
(pair? 3) => #f

布林與條件式

教材講解

Boolean(布林值)與conditional(條件式)的主要目的是能夠表達「如果某種條件成立,則進行某種處理;若不成立,則另行處理」的程式邏輯。它們的主要構成單元除了上一單元介紹的傳回布林值的程序之外,還包括if、and、or、not、cond等式子。

syntax: (if test consequent alternative) 
returns: 若test的值為true則傳回consequent,
要不然則傳回alternative的值。
 
syntax: (if test consequent)
returns: 若test的值為true則傳回consequent,
要不然則不指定傳回值(如void)。
 
(define l '(a b c))
(if (null? l)
'()
(cdr l)) => (b c)
 
(define l '())
(if (null? l)
'()
(cdr l)) => ()
 
(define x -4)
(if (< x 0)
(cons 'minus (- 0 x))
(cons 'plus 4)) => (minus . 4)
(if (< x 0)
'minus) => minus
procedure: (not obj) 
returns: 若obj是false則傳回#t,要不則傳回#f。
 
(not #f) => #t
(not #t) => #f
(not '())=> #f
(not (< 4 5)) => #f
syntax: (and exp ...) 
returns: and 由左而右依序 evaluate exp ...,
若有一個 exp 的值為 false,則立即傳回 #f(不繼
續evaluate exp)。<span style="color:red">若全部的 exp 都不是 false,
則傳回最後一個 exp 的值</span>。
 
(define x 3)
(and (> x 2) (< x 4)) => #t
 
(define x 5)
(and (> x 2) (< x 4)) => #f
 
(and #f '(a b) '(c d)) => #f
(and '(a b) '(c d) '(e f)) => (e f)
syntax: (or exp ...) 
returns: or 由左而右依序 evaluate exp ...,若有
一個 exp 的值為 true,則立即傳回那個 exp 的值(不繼
續evaluate exp)。若全部的exp都不是 true,則傳回#f。
 
(define x 3)
(or (< x 2) (> x 4)) => #f
 
(define x 5)
(or (< x 2) (> x 4)) => #t
 
(or #f '(a b) '(c d)) => (a b)

and、or與if之間有個有趣的關係:它們可以互相表達。這個關係請參考以下的真值表(A與B代表任何可以傳回布林值的式子,包括and、or、not本身):由該表可知,(and A B)與(if A B #f)的含意完全相同;而(or A B)與(if A #t B)的含意完全相同。這個真值表也使用if解釋了and、or的含意。

A B (and A B) (if A B #f) (or A B) (if A #t B) (not A)
#t #t #t #t #t #t #f
#t #f #f #f #t #t #f
#f #t #f #f #t #t #t
#f #f #f #f #f #f #t

那麼cond的含意是什麼呢?一個cond的式子可以完全的以另一個單層或多層次的if式子表達,例如:

syntax: (cond (A exp1))
returns: (if A exp1)的傳回值
 
syntax: (cond (A exp1)
(else exp2))
returns: (if A exp1 exp2)的傳回值
 
syntax: (cond (A exp1)
(B exp2))
returns: (if A exp1 (if B exp2))的傳回值
 
syntax: (cond (A exp1)
(B exp2)
(else exp3))
returns: (if A exp1 (if B exp2 exp3))的傳回值
依此類推。
 
(define x 0)
(cond
((< x 0) (cons 'minus (abs x)))
((> x 0) (cons 'plus x))
(else (cons 'zero x)))) => (zero . 0)

撰寫簡易的程序

教材講解

Procedure(程序)的主要功用是處理資料。procedure有內建的procedure,例如:+、-、*、/、car、cdr、cons、number?、list?、pair?等等;而程式設計師也可以自行撰寫新的procedure。

Scheme procedure是以 lambda 這個保留字產生的。例如:

(lambda (x y z) (/ (+ x y z) 3))

是一個計算三個傳入之數字的平均數的procedure。Procedure被撰寫之後便可以被「呼叫」(call),呼叫一個procedure便是將資料傳入這個procedure,然後執行procedure內的程式碼,並傳回結果。例如:

((lambda (x y z) (/ (+ x y z) 3)) 1 2 3) => 2 
(+ 3 ((lambda (x y z)
(/ (+ x y z) 3)) 1 2 3)) => 5

上一行計算三個數字的平均數的procedure,有三個參數分別是x、y、z,因此需要傳入三個資料分別是1、2、3。呼叫procedure只需要將procedure與傳入的資料用刮號刮在一起便可以了。由此可知,Scheme的程式碼本身也使用串列所使用的刮號來表示,因此需要以「'」來分別list資料或程式碼。

Procedure也可以存入變數之中,然後使用這個變數便可以得到這個procedure並呼叫之。例如:

(define avg3 (lambda (x y z) (/ (+ x y z) 3))) 
(avg3 1 2 3) => 2
(+ 6 (avg3 2 4 6)) => 10

Procedure也可以當作參數傳入其他的procedure:

(define foo (lambda (p a g) (g (p a)))) 
(foo (lambda (x) (+ 3 x))
4
(lambda (x) (* x 5))) => 35

procedure也還可以傳出procedure為執行的結果,這個部分的應用將會在以後的單元介紹。

到此我們已經介紹了幾個足夠用來訓練「程式設計思考力」的語法,這些語法再加上尚未介紹的begin, set!構成了任何電腦程式的核心。這些語法主要是以「刮號( )」來區別式子的不同部分。由於都是用刮號,所以讓語法相當的簡化。但是我們必須注意同樣的刮號出現在不同地方的時候會有不同的意義,如此才能得到這個「簡單」語法的好處,要不充滿了刮號的程式會看起來更「複雜」。

現在我們就來回顧一下這些語法及傳回值的精簡說明,在以下的說明中「*」代表前面的<expression>可以重複出現0或多次;「+」代表前面的<expression>可以重複出現1或多次。Scheme的程式碼可以分為兩種:

  1. <definition>
    1. (define <variable> <expression>):這個式子定義一個變數,其語意是執行<expression>並將其傳回值存入該變數使用的記憶體的地址中。define本身沒有指定的傳回值。例如:
      (define a 3)
      (define b (+ 2 (* a a)))
      (define c '(1 2))
      (define d (cadr c))
  2. <expression>
    1. <constant>:包括<number>、<symbol>、<list>等,它們的傳回值是本身。例如:
      2  3  4.5  3.14  'abc   'xyz  'ab3 
      '(a b c) '(1 2 3) '((1 2 3) (a b))
    2. <variable>:變數傳回儲存在其地址內的值。
    3. (lambda (<variable>*) <definition>* <expression>+):傳回一個程序。這個程序可以有0或多個變數為輸入參數。例如:
      (define a 3)
      (define b (+ 2 (* a a)))
      (define f1 (lambda (x) (+ a x)))
      (define f2 (lambda (a b) (if a 3 b)) )
      (define f3
      (lambda (x y z)
      (define a 0)
      (if x y (+ z a b))))
    4. (<expression> <expression>*):procedure call(程序呼叫)。每一個<expression>都會先被執行與傳回一個值,然後才將這些值傳入第一個<expression>所傳回的procedure中。此特性稱為「傳值呼叫」(call-by-value)。值的個數與procedure的輸入參數的個數必須相同,將數值傳入之後,這些值會儲存在一塊新分派的記憶區塊中以與該procedure中輸入參數的名字共同的用來生成該procedure的區域變數。procedure call傳回procedure內最後一個式子的值。例如:
      (f1 4) => 7
      (f2 #f 4) => 4
      (f3 #f b a) => 14
      觀看程式執行的步驟 (file size: 25 KB, MIME TYPE: text/plain)
      ((lambda (a b c) (cons a (cons b (cons c '())))) 1 2 3) => (1 2 3)
      (cons 'a '()) => (a)
      ((lambda (a b) (+ a b))
      (+ 1 2) (* 3 2)) => 9
    5. (if <expression1> <expression2> <expression3>):若<expression1>的值不是#f,則執行<expression2>,且傳回它的值;要不然則執行<expression3>,且傳回它的值。
    6. (if <expression1> <expression2>):若<expression1>的值不是#f,則執行<expression2>,且傳回它的值;要不然則不指定傳回的值(void)。
    7. (cond (<expression1> <expression2>)+):若<expression1>的值不是#f,則執行<expression2>,且傳回它的值;依此類推。若所有的<expression1>的值均為#f,則不指定傳回值(void)。
    8. (cond (<expression1> <expression2>)+ (else <expressionN>)):若<expression1>的值不是#f,則執行<expression2>,且傳回它的值;依此類推。若所有的<expression1>的值均為#f,則執行<expressionN>,且傳回它的值。

關於刮號的使用,我們可以歸納出如下的規則:

  1. 如果左刮號左邊沒有「'」:
    • 左刮號右邊是define, lambda, if, cond。這時要注意每種語法有幾個部件,並且要將右刮號正確的與左刮號「關(close)好」,你的編輯器可以協助你看到左右刮號是否有close好。
    • 如果左刮號右邊不是define, lambda, if, cond(或是其他還沒有介紹的begin, set!, let及不會在本書介紹的其他特殊保留字),那麼便是程序呼叫。
  2. 如果如果左刮號左邊有「'」,則它是一個list。

簡易的遞迴程序

教材講解

在上一個lesson中,我們曾經使用car, cdr撰寫procedure and2。而以下是呼叫and2的範例:

(and2 '(#t #t)) => #t 
(and2 '(#t #f)) => #f
(and2 '(#f #t)) => #f
(and2 '(#f #f)) => #f

and2這個範例程序的特性是,它的參數中的兩個資料值都要是#t結果才是#t,要不然結果就是#f。

現在我們試著將and2的功能擴充,並將擴充後的程序命名為all-t?而all-t?可以判斷一個list中的值是否都是#t,這個list可以有不止兩個資料值。以下是呼叫all-t?的範例:

(all-t? '()) => #t 輸入參數中沒有一個#f的值,所以結果是#t。
(all-t? '(#t #t #t)) => #t
(all-t? '(#t #t #t #t)) => #t
(all-t? '(#t #t #f #t #f)) => #f

以下是all-t?的寫法,這個例子中的cond以很誇張的方式撰寫,為的是強調cond後的每一行都是由兩個部分所組成:條件判斷及執行的式子。如果其中一行多於或少於兩部分,便與語法的規定不符:

(define all-t?
(lambda (ls)
(cond
( (null? ls) #t )
( (car ls) (all-t? (cdr ls)) )
( else #f ) )))

(all-t? '(#t #t #t))的執行過程可trace如下:

(all-t? '(#t #t #t))
=> (all-t? '(#t #t))
=> (all-t? '(#t))
=> (all-t? '())
=> #t

(all-t? '(#t #t #f #t))的執行過程可trace如下:

(all-t? '(#t #t #f #t))
=> (all-t? '(#t #f #t))
=> (all-t? '(#f #t))
=> #f

觀察all-t?這個程序以及它的執行過程,我們發現:

  1. all-t?內有三個執行的可能(cond後的三行式子)。
  2. 其中一行呼叫all-t?自己。這個呼叫自己的遞迴呼叫,傳入少了頭一筆資料值的串列(cdr ls)。另外兩行沒有遞迴呼叫,而程式執行到這兩行之後便傳回#t或#f,然後結束。
  3. cond中的條件式,控制程式執行哪個式子。
  4. all-t?這個程式的輸出入型態是:list -> boolean,也就是傳入一個list、傳出一個布林值的意思。

一般而言,遞迴程式都有類似的模式:

  1. 有終止條件(termination condition)如:(null? ls)及else。
  2. 有遞迴呼叫,而遞迴呼叫所傳入的資料一定會趨近終止條件(例如使用cdr使ls愈來愈縮短)。

這很合理,因為這樣程式才能結束。

這個單元的練習都是 list -> boolean 型態的程序。我們還會在後續的單元,陸續的介紹遞迴程式的其他型式。另外,在撰寫程式的過程中,最簡單的除錯工具是把變數的值印出來。(display <expression>)與(newline)是可以顯示一個式子的傳回值與換行的兩個程序:

(define all-t?
(lambda (ls)
(display ls)
(cond
((null? ls) #t)
((car ls) (all-t? (cdr ls)))
(else #f))))
 
(all-t? '(#t #t #t))

執行以上的程式碼會列印與傳回以下的內容:

(#t #t #t)(#t #t)(#t)() 
#t

這兩行分別顯示了每次呼叫all-t?的輸入參數的值與最後的執行結果。另外,在你的編輯器中加入(import debugging)與(trace 'all-t?)或將(lambda (<variable>) <expression>)改為(trace-lambda name (<variable>) <expression>)之後(註:name可以是all-t?或其他的名字),也可以看到參數傳入與傳出的狀況,這個功能可以協助你瞭解程式碼與除錯。

累計答案值的遞迴程序

上一單元我們練習了幾個傳回#t或#f的程序。這些程序的執行只要能判斷答案是什麼便可傳出結果。這些答案的產生不需要經過累計(例如:累加、累乘、或累cons)的過程。這個單元我們將練習要經過累計才能傳出答案的遞迴程序。

假設我們需要撰寫一個能夠計算一個list中有幾個#t的程序。我們將這個程序命名為count-t:

(count-t '()) => 0 
(count-t '(#t #t #f #t)) => 3

很顯然的,在程序執行的過程中如果遇到#t則需要將1加入結果之中。寫法如下:

(define count-t 
(lambda (ls)
(cond
((null? ls) 0)
((car ls) (+ 1 (count-t (cdr ls))))
(else (count-t (cdr ls))))))

我們可以追蹤這個程式是怎麼執行的:

(count-t '()) => 0     '()使(null? ls)成立因此傳回0
 
(count-t '(#t)) '(#t)使(car ls)成立因此傳回:
=> (+ 1 (count-t '()))
=> (+ 1 0)
=> 1
 
(count-t '(#f #t)) '(#f #t)使else成立因此傳回:
=> (count-t '(#t)))
=> 1
 
(count-t '(#t #f #t)) '(#t #f #t)使(car ls)成立因此傳回:
=> (+ 1 (count-t '(#f #t)))
=> (+ 1 1)
=> 2

接下來,我們可以追蹤將一個有四個資料值的list傳入count-t的執行狀況:

(count-t '(#t #t #f #t)) 
=> (+ 1 (count-t '(#t #f #t)))
=> (+ 1 (+ 1 (count-t '(#f #t))))
=> (+ 1 (+ 1 (count-t '(#t))))
=> (+ 1 (+ 1 (+ 1 (count-t '()))))
=> (+ 1 (+ 1 (+ 1 0)))
=> 3

另外,count-t的型態是: list -> number。

知道一個程序的輸出入型態可以在寫這個程序的程式碼時,得到一些重要的提示,例如:

  1. 輸入參數是list,那麼程式的終止條件多半是使用null?,而且遞迴呼叫時會使用cdr、car以取出該串列中的資料值。
  2. 輸入參數是number,那麼程式的終止條件多半是該數字是否等於0,而且遞迴呼叫時會將該數字減1。
  3. 輸入參數多於一個時,首先便需要辨認哪一個參數是用來控制程序的執行次數,如果這個參數是一個數字則使用規則2,串列則使用規則1。有時這幾個參數要一起簡化(數字變小、list變短),有時只有一個參數會簡化。
  4. 輸出參數是list,那麼程式在終止時多半會回傳'()。而在遞迴呼叫後或遞迴呼叫的外一層,則會使用cons來累計答案值。
  5. 輸出參數是number,那麼程式在終止時多半會回傳0或1。而在遞迴呼叫後或遞迴呼叫的外一層,則會使用使用*或+來累計答案值。

以上這些只是一般性的原則,許多時候也有例外。

程式偵錯

在撰寫程式的過程中,常常需要找出程式的錯誤,然後修改直到正確為止。常用的偵錯方法有:

  • 輸出變數的值。例如:
(define ls '(x y))
(define n 3)
(printf "ls: ~s n: ~s ~n" ls n)
 
;印出:ls: (x y) n: 3
~s代表在"ls: ..."這個字串中需要印出一個值的位置。上例中有兩個~s因此需要傳入ls, n兩個變數的值。
~n代表換行。
  • 使用程式語言或開發工具提供的偵錯工具。以PLWeb使用的Chez Scheme而言,可以使用trace-lambda取代lambda,例如:
(define count-t 
(trace-lambda count-t (ls)
(cond
((null? ls) 0)
((car ls) (+ 1 (count-t (cdr ls))))
(else (count-t (cdr ls))))))
 
; 執行時會輸出:
 
|(count-t (#t #t #f #t))
| (count-t (#t #f #t))
| |(count-t (#f #t))
| |(count-t (#t))
| | (count-t ())
| | 0
| |1
| 2
|3
3

將遞迴程序轉換成迴圈程序

教材講解1 教材講解2

階乘(factorial)是一個標準的遞迴程序的例子。如果「!」代表階乘的符號,則

0! = 1
N! = N * (N – 1)!

在這一個單元,我們將以階乘為範例說明階乘程序的幾種不同的寫法。

內涵式遞迴

階乘的定義可以用Scheme改寫如下,我們將之命名為factorial,意思是階乘程序(procedure)的第一個版本:

(define factorial 
(lambda (n)
(if (= n 0)
1
(* n (factorial (- n 1))))))
 
(factorial 3)
=> (* 3 (factorial 2))
=> (* 3 (* 2 (factorial 1)))
=> (* 3 (* 2 (* 1 (factorial 0))))
=> (* 3 (* 2 (* 1 1)))
=> 6

觀察以上的執行狀況,呼叫factorial的遞迴呼叫是內涵(embedded)在乘法算式(* n ...)之內。而程式的執行結果是在最後一個遞迴呼叫(factorial 0)完成後才依序累乘(* 3 (* 2 (* 1 1)))而得的。這種類型的遞迴程序稱為內涵式遞迴(embedded recursion)。

觀察factorial的執行 (file size: 17 KB, MIME TYPE: text/plain)


下圖是一張以色彩來幫助讀者瞭解factorial的程式碼追尋(trace)圖。

Fac.jpg

尾端式的遞迴

第二種形式的遞迴程序是尾端式的遞迴(tail recursion)。尾端遞迴的特色是遞迴呼叫沒有內涵在任何一個尚未執行完成的式子(expression)內。以下面的例子而言,呼叫tail-fac的遞迴呼叫是在if expression之內,但是該if expression的條件判斷式已經執行完畢。

(define tail-fac
(lambda (m n)
(if (= m 0)
n
(tail-fac (- m 1) (* n m)))))
 
(tail-fac 3 1)
=> (tail-fac 2 3)
=> (tail-fac 1 6)
=> (tail-fac 0 6)
=> 6

以上程序的執行狀況是「平的」。尾端遞迴在執行的過程中不會像內涵式遞迴累積一層又一層如同樓梯般的式子。從以下的追尋圖中,也可以看出在執行到(tail-fac 0 6)時,environments並沒有如同factorial的追蹤圖是一個樹狀的結構,原因是前面遞迴呼叫時所產生的黃、粉紅與綠色的區域變數區內的變數值,並不需要被保留,因此下一次遞迴呼叫的區域變數區可以直接的覆蓋上一次遞迴呼叫時所使用的遞迴變數區。

Tail-fac.JPG

將某些內涵式遞迴程序轉換成尾端遞迴程序的技巧是增加傳入的參數。以fac2來說我們增加了一個能夠儲存累乘值的參數m。增加這個參數後便不需要以累積乘法算式的方式來計算階乘的值了。

迴圈

第三種計算階乘的方式是使用一般的程式語言常常使用的「迴圈」。一個內涵式遞迴程序在轉換成尾端式遞迴程序後,再將參數「提出」程序之外成為全域變數(即golbal variable意指定義在程式碼的最外層;而定義在procedure之內的變數則稱為區域變數即local variable),並且使用begin與set!執行改變或累計數值的步驟後,便可以轉換成迴圈的程式了。

begin是一種語法,其意義是依照順序一個式子、一個式子的執行之後的所有式子,並傳回在begin內最後一個式子的值(功用類似C與Java的{ })。set!也是一個語法,其意義是更改一個變數的值。例如:

(define n 3)
(begin
(set! n (+ n 3))
(+ n n)) => 8

有了begin與set!之後,便可以以改變變數值的方式,將內涵式遞迴程式,改變成迴圈的程式。

(define n 3) 
(define m 1)
 
(define fac3
(lambda ()
(if (= n 0)
m
(begin
(set! m (* m n))
(set! n (- n 1))
(fac3)))))
(fac3)
=> 6

上面的程序不能隨意的計算其他數字的階乘。加入以下的程序然後透過傳入參數並且重新設定n與m的值便可以解決這個問題:

(define fac 
(lambda (num)
(set! n num)
(set! m 1)
(fac3)))
(fac 3) => 6
(fac 4) => 24

觀察上面fac與fac3兩個procedure的遞迴呼叫(fac3),(fac3)是一個沒有參數的呼叫,其作用與一些程式語言(如BASIC或C)中的goto無異。

處理集合的程序

在這一個單元,我們將撰寫一系列處理集合的procedure。這些procedure包括交集、聯集、子集等。這些練習可以幫助我們對遞迴程序(procedure)的撰寫更加熟練。這些程式有一個共同的特性:它們都需要用到一個稱為member的內建程序。Member判斷某個資料值是否是一個list的一員,例如:

(member 'a '(b c a d))    => (a d), (a d)也是true值
(member 'c '(b a c a d)) => (c a d), (c a d)也是true值
(member 'a '(b c d)) => #f
(member 'a '()) => #f

判斷一個串列是否是一個set的procedure,需要判斷該串列是否有重複的元素。而兩個集合的交集則需要使用member選出兩個集合中共有的元素。其他處理集合的procedure大多也需要用到member。

深層串列的處理

Deep list(深層串列)是list中還有list的list。例如:

'((a b) c (d ((a) f)))

就是一個deep lisp。

如何寫處理deep lisp的procedure呢?以下是一個計算上面的list中有幾個a的 的範例:

(define count-a
(lambda (ls)
(cond
((null? ls) 0) ; cond1
((symbol? (car ls)) ; cond2
(if (eq? 'a (car ls))
(+ 1 (count-a (cdr ls))) ; cond2.1
(count-a (cdr ls)))) ; cond2.2
(else (+ (count-a (car ls))
(count-a (cdr ls))))))) ; cond3
 
(count-a '((a b) (a a)))
=> (+ (count-a '(a b)) (count-a '((a a)))) by cond2
=> (+ (+ 1 (count-a '(b))) (count-a '((a a)))) by cond3
=> (+ (+ 1 (count-a '())) (count-a '((a a)))) by cond4
=> (+ (+ 1 0) (count-a '((a a)))) by cond1
=> (+ 1 (count-a '((a a))))
=> (+ 1 (+ (count-a '(a a)) (count-a '()))) by cond2
=> (+ 1 (+ (+ 1 (count-a '(a))) (count-a '()))) by cond3
=> (+ 1 (+ (+ 1 (+ 1 (count-a '())))) (count-a '()))by cond3
=> (+ 1 (+ (+ 1 (+ 1 0)) (count-a '()))) by cond1
=> (+ 1 (+ (+ 1 (+ 1 0)) 0)) by cond1
=> 3

這個處理deep lisp的procedure與處理flat list的procedure的最大差異是多了(pair? (car ls))的條件判斷。如果這個判斷成立,則分別對(car ls)及(cdr ls)做共兩次的遞迴呼叫,並將兩次的結果加總,便得到答案;如果不成立,則繼續判斷(eq? 'a (car ls))是否成立,並繼續執行即可。這個procedure的傳回值是一個數字。如果一個處理deep lisp的procedure的傳回值是list,則需要將「+」改為「cons」,以便在執行過程中逐步累積答案值成為一個list。

高階程序與「去異求同」程序的撰寫

Higher-order procedures(高階程序)可以將procedure當作參數傳入或傳出procedure。以下是一個將procedure傳入另一個procedure的例子:

(define compute 
(lambda (op num1 num2)
(op num1 num2)))
 
(compute + 1 2) => 3
(compute – 5 3) => 2
(compute * 3 4) => 12

compute的型態之一是:

(((number x number) -> number) x number x number) -> number

也就是它有三個以「x」區隔的參數:第一個參數的type(型態)是一個procedure,它的type是((number x number) -> number);第二、三個參數的type則都是number。

然而另一個呼叫compute的方式是:

(compute cons 1 2) => (1 . 2)
(compute cons 'a '(2 3)) => (a 2 3)

這次compute的type則可以是:

(((any x any) -> pair) x any x any) -> pair

在此any代表任意type,也就是它有三個以「x」區隔的參數:第一個參數的type(型態)是一個procedure,它的type是((any x any) -> pair);第二、三個參數的type則都是any。

不過any的使用並不足以表達compute的各種可能。比較完整一點的表達方式應該是這樣:

(((T1 x T2) -> T3) x T1 x T2) -> T3

T1, T2, T3是三個type variables, 也就是T1, T2, T3都可以對應某個真實的type,而compute的輸出入參數間的關係只要符合

(((T1 x T2) -> T3) x T1 x T2) -> T3

也就是在上式中的兩個T1都有一樣的type,兩個T2都有一樣的type及兩個T3都有一樣的type,便不會在執行時產生type error。

什麼是type呢?比較嚴謹一點的說法是:A type describes a set of Scheme values and every Scheme value has a type.

另一個higher-order procedure的例子是procedure是傳回值:

(define add 
(lambda (a)
(lambda (b)
(+ a b))))
(define add3 (add 3))
(define add4 (add 4))
 
(add3 4) => 7
(add4 3) => 7
(add4 6) => 10

add的型態是:

number -> (number -> number)

也就是add會傳回另一個型態是(number -> number)的procedure。因此,add3與add4,便分別是一個將某數加3或加4的procedure了。add3與add4的特色是:它們各有一個區域變數區儲存a的值,而add3的a的值是3、add4的a的值則是4。這兩個區域變數區可以說是分別屬於add3與add4的記憶區。因此高階程式的特色之一是可以生成有專屬記憶區的程序,這種程序在某些程式語言又稱作closure。

觀察Add的執行過程 (file size: 18 KB, MIME TYPE: text/plain)


Closure可以被用來儲存物件導向程式語言中的物件。以下程式碼中的makeBox procedure便是一個可以用來製造「物件」的procedure:

(define makeBox
(lambda (value)
(lambda (msg)
(cond
((eq? msg 'get) value)
((eq? msg 'set) (lambda (new) (set! value new)))
(else (error "Bad message"))))))
(define box3 (makeBox 3))
(box3 'get) => 3
((box3 'set) 0)
(box3 'get) => 0
 
(define box4 (makeBox 4))
(box4 'get) => 4
((box4 'set) 8)
(box4 'get) => 8

box3與box4都是closures,都是procedures,也可說都是「物件」。box3的記憶區內存放的value變數的值先是3,然後被改成0;box4的記憶區內存放的value變數的值則先是4,然後被改成8。

觀察makeBox的執行過程 (file size: 27 KB, MIME TYPE: text/plain)

抽象設計

  • 我們寫過的許多程序,看起來都相當類似
  • 這些類似的程序,有許多重複的程式碼
  • 如何避免這些重複的程式碼?

合併相似的程式碼,將差異以參數傳入

  • 以下的兩個程序相當的類似,他們都傳入一串數字,然後將大於或小於某數的數字以串列輸出:
(define above
  (lambda (n lon)
    (cond
      ((null? lon) '())
      ((> n (car lon)) (cons (car lon) (above n (cdr lon))))
      (else (above n (cdr lon))))))
(above 4 '(0 2 5 3 6)) => (5 6)
(define below
  (lambda (n lon)
    (cond
      ((null? lon) '())
      ((< n (car lon)) (cons (car lon) (below n (cdr lon))))
      (else (below n (cdr lon))))))
(below 4 '(0 2 5 3 6)) => (0 2 3)
  • 將兩者合併後,將>或<以參數傳入
;; filter: (number number -> boolean) number lon -> lon
;; lon means list of number
(define filter
  (lambda (op n lon)
    (cond
      ((null? lon) '())
      ((op n (car lon)) (cons (car lon) (filter op n (cdr lon))))
      (else (filter op n (cdr lon))))))
(filter > 4 '(0 2 5 3 6)) => (5 6)
(filter < 4 '(0 2 5 3 6)) => (0 2 3)
  • 用filter定義above, below
(define above
  (lambda (n lon)
    (filter > n lon)))
(define below
  (lambda (n lon)
    (filter < n lon)))
  • 更具彈性的版本
;; filter2: (any -> boolean) list -> list
(define filter2
  (lambda (op lon)
    (cond
      ((null? lon) '())
      ((op (car lon)) (cons (car lon) (filter op (cdr lon))))
      (else (filter op (cdr lon))))))
  • op: any -> boolean
(define >4
  (lambda (n)
    (> n 4)))
(filter2 >4 '(0 2 5 3 6)) => (5 6)

(define a?
  (lambda (s)
    (eq? s 'a)))
(filter2 a? '(a b a c d)) => (a a)

設計抽象程序的步驟

第一步:比較

  • 比較以下兩個程序:
;; us$->nt$: list-of-number -> list-of-number
(define us$->nt$
  (lambda (ls)
    (cond
      ((null? ls) '())
      (else (cons (* 30 (car ls))
                  (us$->nt$ (cdr ls)))))))
(equal? (us$->nt$ '(3 4 5 8 9) '(90 120 150 240 270))
;; names: list-of-worker -> list-of-symbol
(define names
  (lambda (ls)
    (cond
      ((null? ls) '())
      (else (cons (worker-name (car ls))
                  (names (cdr ls)))))))

(define-struct worker (name age salary))
(define w1 (make-worker 'peter 34 36000))
(define w2 (make-worker 'john 28 30000))
(define w3 (make-worker 'mary 26 28000))
(equal? (names (list w1 w2 w3)) '(peter john mary))

第二步:合併、傳入程序參數並取代差異的部分

(define map
  (lambda (f ls)
    (cond
      ((null? ls) '())
      (else (cons (f (car ls))
                  (map f (cdr ls)))))))

第三步:使用新的抽象程序定義舊程序,進行測試

(define us$->nt$
  (lambda (ls)
    (map (lambda (n) (* 30 n)) '(3 4 5 8 9))))
(equal? (us$->nt$ '(3 4 5 8 9)) '(90 120 150 240 270))

(define names
  (lambda (ls)
    (map worker-name ls)))
(equal? (names (list w1 w2 w3)) '(peter john mary))

第四步:確認抽象程序的型態

  • 這一行程式得到map的型態是:
    (map (lambda (n) (* 30 n)) '(3 4 5 8 9))
    map: (number -> number) list-of-number -> list-of-number
  • 這一行程式得到map的型態是:
    (map worker-name ls)
    map: (worker -> symbol) list-of-worker -> list-of-symbol
  • map的型態是:
    map: (A -> B) list-of-A -> list-of-B

以回傳程序的方式設計抽象程序

第一種方式:多層次的lambda

(define map2
  (lambda (f)
    (lambda (ls)
      (cond
        ((null? ls) '())
        (else (cons (f (car ls))
                    ((map2 f) (cdr ls))))))))

(define us$->nt$ (map2 (lambda (n) (* 30 n))))
(equal? (us$->nt$ '(3 4 5 8 9)) '(90 120 150 240 270))

(define names (map2 worker-name))
(equal? (names (list w1 w2 w3)) '(peter john mary))

第二種方式:回傳定義為區域變數的程序

(define map3
  (lambda (f)
    (letrec
      ((re-map
         (lambda (ls)
           (cond
             ((null? ls) '())
             (else (cons (f (car ls))
                         (re-map (cdr ls))))))))
      re-map)))

(define us$->nt$ (map3 (lambda (n) (* 30 n))))
(equal? (us$->nt$ '(3 4 5 8 9)) '(90 120 150 240 270))

(define names (map3 worker-name))
(equal? (names (list w1 w2 w3)) '(peter john mary))
  • (letrec ((<variable> <exp>) ...) <exp>)
的語意是<variable>的值是<exp>的值,而其可見範圍(scope)僅限於letrec之內
  • 如果定義在letrec外層的變數與定義在letrec內的變數同名,則內層的變數遮蓋住外層的變數。例如:
    (define v1 3)
    (+ 1
    (letrec ((v1 4))
    (+ v1 5)))
的回傳值是(+ 1 4 5) => 10

註:Scheme另有一個let語法適合定義一般的區域變數,但變數值不能是遞迴程序。

幾種類型的型態

  1. 基本型態(basic type),例如:number, symbol, boolean等
  2. 被定義的型態(defined type),例如:worker, list of numbers等
  3. 程序型態(function type),例如:number -> number, number -> boolean等
  4. 泛型(generic type),也就是有型態變數的type,例如:A -> B

區域變數與區域程序

let

  • let可用於定義區域變數,例如:
    (define foo
    (lambda (a)
    (let ([x 2]
    [y 3])
    (+ a x y)))
    (foo 1) ;=> 6
  • 上面的程式也可改寫成:
    (define foo
    (lambda (a)
    ((lambda (x y) (+ a x y)) 2 3)))
    (foo 1) ;=> 6
  • (let ([v1 e1] ...) exp) == ((lambda (v1 ...) exp) e1 ...)
  • 另一個範例:
    (define counter
    (let ([count 0])
    (lambda ()
    (begin
    (set! count (+ count 1))
    count))))
    (counter) ;=> 1
    (counter) ;=> 2

用於定義區域程序的define

  • define 亦可用於lambda, let之內以定義區域變數,但必須位於其它的式子之前,例如:
    (define f (lambda (x) (* x x)))
    (let ([x 3])
    (define f (lambda (y) (+ y x)))
    (f 5)) ;=> 8
    (f 5) ;=> 25
  • 使用define定義的區域程序可以是遞迴程序,例如:
    (let ()
    (define even?
    (lambda (x)
    (or (= x 0)
    (odd? (- x 1)))))
    (define odd?
    (lambda (x)
    (and (not (= x 0))
    (even? (- x 1)))))
    (even? 10)) ;=> #t

同名變數與變數的可見範圍

  • 在同樣的區域內,不可以有同名的變數,例如:
    (let ([x 3]
    [x 4])
    x) ;=> error
  • 不同的區域,可以有同名的變數,例如:
    (let ([x 3) x) ;=> x
    (let ([x 4) x) ;=> x
  • 全域變數與區域變數彼此同名,則區域變數遮住了全域變數,例如:
    (define x 3)
    (define f +)
    (let ([x 4])
    (define f *)
    (f 5 x)) ;=> 20
  • 外層的變數與內層的變數彼此同名,則內層的變數遮住了外層的變數

陣列

Vector(陣列)在某些程式語言中被稱為arrry。對某些應用來說,Vector要比list快速而且方便。要存取list中的某一個元素,一定需要從頭找起直到找到目標為止,因此存取list中元素的時間是不固定的。Vector則是一段連續的記憶體位置,因此可以透過index來存取,所以存取元素的時間是固定的。

一個Vector的長度(length)是該vector中可以存入元素的個數。Vector的index是從0起算,而最大的index是該vector的length - 1。存在一個vector中的元素可以是任何型態,而且可以存不同的型態。

Vector資料值的寫法如下:

#(2 3 4 5 6)
#(1 a 3 b)

Vector有以下的procedure可以使用:

procedure: (vector obj ...)
returns: 一個由obj而組成的vector
 
(vector) => #()
(vector 1 'b 2) => #(1 b 2)
procedure: (make-vector n)
returns: 一個長度是n的vector, 其元素的值不指定。
 
(make-vector 0) => #()
 
procedure: (make-vector n obj)
returns: 一個長度是n的vector, 其元素的值都是obj。
 
(make-vector 3 'b) #(b b b)
procedure: (vector-length vector) 
returns: 傳回vector的長度
 
(vector-length '#()) => 0
(vector-length '#(a b c)) => 3
(vector-length (vector 3 4)) => 2
(vector-length (make-vector 20)) => 20
procedure: (vector-ref vector n) 
returns: 存在vector中的第n個(以0為底且要小於vector的長度)元素。
 
(vector-ref '#(a b c) 0) => a
(vector-ref '#(a b c) 1) => b
(vector-ref '#(x y z w) 3) => w
procedure: (vector-set! vector n obj) 
returns: 不指定。
 
n要介於0vector(length - 1)之間,將obj儲存在這個vector中的
第n個元素內。
 
(let ((v (vector 1 2 3 4)))
(vector-set! v 2 'x)
v) => #(1 2 x 4)

以區域遞迴程序處理陣列

(define vector-fill
(lambda (v x)
(let ([n (vector-length v)])
(define loop
(lambda (i)
(if (< i n)
(begin
(vector-set! v i x)
(loop (+ i 1))))))
; 呼叫 loop
(loop 0))))
(define v (make-vector 4))
(vector-fill v 'a)
v => #(a a a a)

排序

Sorting(排序)有許多方法。在這一單元中將介紹兩個排序的方法。第一個方法使用的是list,主要的構想是先寫一個能夠將某一個元素insert進入一個已經排序過的list中的procedure:

(insert 2 '()) => (2)
(insert 3 '(1 2 5 6)) => (1 2 3 5 6)

然後再利用insert撰寫sort。其主要技巧如下:

(sort '()) => ()
(sort '(2)) => (insert 2 (sort '())
(sort '(3 2)) => (insert 3 (sort '(2))
=> (insert 3 (insert 2 (sort '())))

以上是sort以遞迴呼叫自己及insert的執行次序。

第二個方法是selection sort。這個方法可以將一個vector中的儲存值排序。方法如下:

  1. 先找出vector中由index 0至length - 1的最小值的index,
  2. 再將這個最小值與index 0中的值對調;
  3. 再找出vector中由index 1至length - 1的最小值的index,
  4. 再將這個次小值與index 1中的值對調;
  5. 依此類推直到length - 1前的值都對調完畢。

例如某vector內的儲存值如下:

index 0 1 2 3
儲存值 76 43 80 17

經過第一次對調後得到:

index 0 1 2 3
儲存值 17 43 80 76

經過第二次對調後得到:

index 0 1 2 3
儲存值 17 43 80 76

經過第三次對調後得到:

index 0 1 2 3
儲存值 17 43 76 80

二元搜尋樹

如下圖所示,一棵二元搜尋樹(Binary Search Tree)是由一或多個節點(node)所組成,而每一個節點及其子節點又都是一棵個別的BST。將一個節點加入一棵BST,必須要符合:新節點內的值如果小於根節點則要加在該根節點的左邊;新節點內的值如果大於根節點則要加在該根節點的右邊。二元搜尋樹的特性是一棵BST在被「採平」後,可以明顯的看出其所有的節點都剛剛好由小而大的排好。

Bst.jpg

二元搜尋樹有以下的特性:

  1. 一棵沒有節點的BST是一個empty tree;
  2. 一棵BST根節點的值要大於其left subtree內各個節點的值,而其根節點的值要小於其right subtree內各個節點的值;
  3. 此外,一棵BST的left subtree與right subtree,也都一定要是一棵BST。

實做BST的方法是使用vector:

(define make-node
(lambda (value)
(vector value '() '())))
 
(define node-value (lambda (node) (vector-ref node 0)))
 
(define node-left (lambda (node) (vector-ref node 1)))
 
(define set-node-left!
(lambda (node new-left)
(vector-set! node 1 new-left)))
 
(define node-right (lambda (node) (vector-ref node 2)))
 
(define set-node-right!
(lambda (node new-right)
(vector-set! node 2 new-right)))

一個節點是由一個有三個儲存格的vector構成,第一個儲存格是用來存放該節點的value;而第二、三個儲存格則是用來存放指向該節點左與右subtree的指標(pointer)。

關連式資料庫簡介

構成關連式資料庫的資料結構是表格(table)。一個表格內可以有一或多個欄位,而每個欄位都可以儲存資料。這個單元將以list來模擬表格,然後實做能夠對表格作資料查詢的程序,藉以進一步的練習高階及遞迴程序的撰寫,並透過這些練習讓學習者對關連式資料庫的基本構想有初步的認識。

舉例而言,以下是一個儲存學生姓名及國、英、數三科成績的表格:

name chi eng math
tim 90 80 70
mary 60 80 90
john 70 60 55
paul 50 80 80

以上的表格可以用list表達如下:

((name chi eng math)
(tim 90 80 70)
(mary 60 80 90)
(john 70 60 55)
(paul 50 80 80))

以以上的單一表格為例,關連式資料庫可以提供使用者找出在該表格「橫列」中符合某些條件的資料,例如:

  1. 找出姓名是john的學生資料;
  2. 找出國文成績>=60分的學生資料;

除了找出「橫列」當中符合某種條件的資料外,關連式資料庫也提供將某個表格中的某幾個「直行」抽出以產出另一個表格的功能,這個功能稱為project。例如:將以上的表格中的姓名欄及英文欄抽後,可以得到以下的表格:

name eng
tim 80
mary 80
john 60
paul 80

此外,兩個表格的某個欄位相同的話還可以合併(join)。例如:addresses與final-grades在以no為基準合併後的表格(以list表示),如下:

(define addresses
'((name no address city)
(Adams 123 123-elm-st Richmond)
(Baker 417 47a-computron Bellevne)
(Boxes 603 78014-larch-st langley)
(Dunne 618 8086-river-rd victoria)
(Edger 801 1885-hemlock new-ork)))
(define final-grades
'((course no gr)
(cs124 123 a-)
(ma120 123 b+)
(en100 618 a-)
(cs124 618 b-)
(cs124 618 b+)
(ma221 801 a+)))
 
(join addresses final-grades 'no)
=> ((course no gr name address city)
(cs124 123 a- Adams 123-elm-st Richmond)
(ma120 123 b+ Adams 123-elm-st Richmond)
(en100 618 a- Dunne 8086-river-rd victoria)
(cs124 618 b- Dunne 8086-river-rd victoria)
(cs124 618 b+ Dunne 8086-river-rd victoria)
(ma221 801 a+ Edger 1885-hemlock new-ork))


OOP:類別、物件、物件變數與方法

「物件導向程式設計」比起傳統的程式設計方式有許多的優點。簡單的說:「類別(class)」可以生成「物件(instance or object)」,而「物件 = 物件變數(instance variable) + 程序方法(method)」。其中「物件變數」負責資料的儲存,而「程序方法」則負責資料的處理。以下是一個以傳統方式撰寫的計數器物件。count負責儲存資料,而add1及get-count程序則負責更改及讀取count的值:

(define count 0) 
 
(define add1
(lambda () (set! count (+ count 1))))
 
(define get-count
(lambda () count))
 
(add1)
(add1)
(get-count) => 2

這種寫法的缺點是一個物件需要對應一套程式碼。如果程式中需要兩個計數器,則上面的程式碼便需複製兩次,而且物件變數及程序方法的名稱還不能重複。

使用區域變數來包裝物件

改進變數名稱不能重複的方式是將以上的程式碼包裝在以let宣告的區域變數之內:

(define counter 
(let ([count 0]) ; 注意雙刮號的使用可以在let內宣告多個區域變數
(define add1
(lambda () (set! count (+ count 1))))
(define get-count
(lambda () count))
(lambda (method-name)
(cond
((eq? method-name 'add1) add1)
((eq? method-name 'get-count) get-count)
(else (error "Method ~s not found:" method-name))
))))
 
((counter 'add1))
((counter 'add1))
((counter 'get-count)) ;=> 2

Scheme可以使用:

(let ([var1 exp1] ...) exp ...)

來宣告區域變數,而區域變數的「可見範圍」(scope)為exp起始的區域。以上例來說是從(define add1 ...)之後的式子。如果在以let定義的區域變數的外層,還有與var1, ...同名的區域變數或全域變數,那麼內層的區域變數遮蓋(overide)了外層的變數。

使用這個方法可以使用複製程式碼的方式定義新的counter,而且可以不用更改add1, init, get-count, set-count等程序方法的名稱:

(define counter2 
(let ([count 0])
(define add1
(lambda () (set! count (+ count 1))))
...
(lambda (method-name)
...)))
((counter2 'add1))
((counter2 'add1))
((counter2 'get-count)) ;=> 2

但是若一個程式在執行時(run time)需要不定數量或成百上千的counter,這個過早在程式編譯時(compile time)就必須預備好所有counter的方式,就不可行了。

以程序來包裝物件

一個改進的方式是利用Scheme高階程序的功能,將上面的的程式碼(增加了一個set-count方法) 包在一個能夠製造物件的程序內:

(define -make-counter- 
(lambda (count)
(define add1
(lambda () (set! count (+ count 1))))
(define get-count
(lambda () count))
(define set-count
(lambda (n)
(set! count n)))
(lambda (method-name)
(cond
((eq? method-name 'add1) add1)
((eq? method-name 'get-count) get-count)
((eq? method-name 'set-count) set-count)
(else (error "Method ~s not found:" method-name))
))))
(define c0 (-make-counter- 0))
((c0 'add1)) ; (c0 'add1)傳回add1,因此需要雙刮號才呼叫的到
((c0 'get-count)) => 1
((c0 'add1))
((c0 'get-count)) => 2
(define c1 (-make-counter- 0))
((c1 'add1))
((c1 'get-count)) => 1
((c1 'set-count) 3)
((c1 'get-count)) => 3

由於每一次呼叫(-make-counter- 0)都會產生一塊區域變數區來儲存count的值,這些區域變數區可以說是在每一次呼叫(-make-counter- 0)之後所產生之物件的物件變數區。以上例而言,c0, c1各有一個區域變數區(也等於是這兩個物件的物件變數區),而裡面也個別儲存了屬於c0的count及屬於c1的count。因此,個別的執行c0與c1的add1與get-count的方法便會分別更改屬於c0的count及屬於c1的count。至於c0與c1的方法是什麼呢?事實上他們的方法如下:

(lambda (method-name) 
(cond
((eq? method-name 'add1) add1)
((eq? method-name 'get-count) get-count)
((eq? method-name 'set-count) set-count)
(else (error "Method ~s not found:" method-name))))

而屬於以上程式碼的區域變數區包含了add1, get-count及其儲存值。當然,每一個經由呼叫-make-counter-所生成的物件都有一個這樣的區域變數區,而這個區域變數區內所儲存的也就是該物件的物件變數與方法。由於-make-counter-可以用來製造類似功用的counter,因此make-counter也被稱為一個「類別」(class)。

為了改進上述「雙刮號」的呼叫方式,我們另行定義以下的程序,其目的是讓參數個數不同的方法,都能將參數傳入, 而且也讓方法的呼叫較為簡潔:

(define call 
(lambda (obj method-name . args)
(apply (obj method-name) args)))
 
(call c1 'get-count) => 1
(call c1 'set-count 3)
(call c1 'get-count) => 3

以下的語法可以讓一個程序能夠接受變動個數的參數:

(lambda (arg1+ . args) ...)
 
((lambda (a . b) a) 1) => 1
((lambda (a . b) b) 1) => ()
((lambda (a . b) b) 1 2) => (2)
((lambda (a b . c) (+ a b)) 2 3 4 10) => 5
((lambda (a b . c) c) 2 3 4 10) => (4 10)
((lambda (a b . c) (cons (+ a b) c)) 2 3 4 10) => (5 4 10)

apply這個程序的第一個參數必定是另一個程序,其餘的參數則是其第一個參數的輸入參數。Apply的功用是將其餘的參數傳入其第一個參數並進行呼叫:

(apply + ’(2 3 4)) => 9 
(apply (lambda (x y) (cons x y))(2 3)) => (2 . 3)

上面介紹的apply及lambda的特殊語法可以不用深究,知道如何使用call便可以了。

請開始做練習題第一、二題。

繼承

如果我們要擴充-make-counter-的功能,使其能支援add2也就是將count加2的方法,那麼該如何做呢?方法一是直接改-make-counter-的程式碼。方法二是寫一個「繼承」-make-counter-的-make-counter2-的「類別」:

(define -make-counter2- 
(lambda ()
(define super (-make-counter- 0))
(define add2
(lambda ()
(call super 'add1)
(call super 'add1)))
(lambda (method-name)
(cond
((eq? method-name 'add2) add2)
(else (super method-name))
))))

在以上的程式碼中super是一個-make-counter-所製造的物件。以下是製造及呼叫一個-make-counter2-的範例:

(define c0 (-make-counter- 0))
(call c0 'add1)
(call c0 'get-count) => 1
(define c2 (-make-counter2-))
(call c2 'add2)
(call c2 'get-count) => 2

當呼叫c2的get-count方法時,由於get-count不是定義在-make-counter2-中,因此會執行cond式子的else部分,也就是將get-count傳入super中。由於super是一個-make-counter-所製造的物件,因此會傳回定義在-make-counter-中的get-count方法。Call呼叫這個方法,傳回0。

觀看make-counter的執行過程 (file size: 32 KB, MIME TYPE: text/plain)


(call c2 ’get-cunt) => ???

如果程式設計師將方法的名字拼錯了會怎麼樣呢?顯然我們的程式碼沒有抓到這個錯誤。以下是改良的-make-counter-:

(define -object- 
(lambda ()
(lambda (method-name)
(error "method ~s not found:" method-name))))
 
(define -make-counter-
(lambda (count)
(define super (-object-))
...
(lambda (method-name)
(cond
((eq? method-name 'add1) add1)
...
(else (super method-name))
))))

這個-make-counter-「繼承」一個名叫-object-的類別。當這個類別被遇到時就「到頂了」,表示使用者呼叫了一個沒有被定義的方法。因此會呼叫error並傳回錯誤的信息。

請開始做練習題第三、四題。

this的妙用

一個物件的方法可不可以呼叫自己(this)的方法呢?答案是可以的,但是需要將自己(this)也當作參數傳入自己的方法中。因此,call的定義需要將obj也傳入apply中。而每一個方法也要增加一個this參數。以下的範例增加了add3這個方法,而add3藉著呼叫add1三次來完成將count加3的動作:

(define call 
(lambda (obj method-name . args)
(apply (obj method-name) obj args)))
 
(define –object-
(lambda ()
(lambda (method-name)
(error "method ~s not found:" method-name))))
 
(define -make-counter-
(lambda (count)
(define super (-object-))
(define add1
(lambda (this) (set! count (+ count 1))))
(define add3
(lambda (this)
(call this 'add1)
(call this 'add1)
(call this 'add1)))
(define get-count
(lambda (this) count))
(lambda (method-name)
(cond
((eq? method-name 'add1) add1)
((eq? method-name 'add3) add3)
((eq? method-name 'get-count) get-count)
(else (super method-name))
))))
 
(define -make-counter2-
(lambda ()
(define super (-make-counter- 0))
(define add2
(lambda (this)
(call super 'add1)
(call super 'add1)))
(lambda (method-name)
(cond
((eq? method-name 'add2) add2)
(else (super method-name))
))))
 
(define c2 (-make-counter2-))
(call c2 'add2)
(call c2 'add3)
(call c2 'get-count) => 5
(define c0 (-make-counter- 0))
(call c0 'add3)
(call c0 'get-count) => 3

一個類別中的方法不但可以使用this呼叫自己類別的方法,它還可以使用this呼叫子類別的方法。例如:我們可以將add3改寫成呼叫自己的add1及-make-counter2-的add2:

(define -make-counter- 
(lambda (count)
(define super (-object-))
(define add1
(lambda (this) (set! count (+ count 1))))
(define add3
(lambda (this)
(call this 'add1)
(call this 'add2)))
(define get-count
(lambda (this) count))
(lambda (method-name)
(cond
((eq? method-name 'add1) add1)
((eq? method-name 'add3) add3)
((eq? method-name 'get-count) get-count)
(else (super method-name))
))))
 
(define -make-counter2-
(lambda ()
(define super (-make-counter- 0))
(define add2
(lambda (this)
(call super 'add1)
(call super 'add1)))
(lambda (method-name)
(cond
((eq? method-name 'add2) add2)
(else (super method-name))
))))
 
(define c2 (-make-counter2-))
(call c2 'add2)
(call c2 'add3)
(call c2 'get-count) => 5
(define c0 (-make-conter-))
(call c0 'add3) => error

(call c0 'add3)之所以會產生錯誤是因為c0沒有add2這個方法。那麼如何能正確的應用使用this呼叫子類別方法的功能呢?這會在下一小節介紹。

觀察make-counter與this的執行過程 (file size: 30 KB, MIME TYPE: text/plain)


請開始做練習題第五、六題。

抽象類別(abstract class)

以上-make-counter-及-make-counter2-的功能還可以增強。例如:我們可以提供addn這個方法,放入讓-make-counter-繼承的一個abstract class中:

(define -make-abs-counter- 
(lambda ()
(define super (-object-))
(define addn
(lambda (this n)
(if (not (= n 0))
(begin
(call this 'add1)
(call this 'addn (- n 1))))))
(lambda (method-name)
(cond
((eq? method-name 'addn) addn)
(else (super method-name))))))
 
(define -make-counter-
(lambda (count)
(define super (-make-abs-counter-))
(define add1
(lambda (this) (set! count (+ count 1))))
(define add3
(lambda (this)
(call this 'add1)
(call this 'add1)
(call this 'add1)))
(define get-count
(lambda (this) count))
(lambda (method-name)
(cond
((eq? method-name 'add1) add1)
((eq? method-name 'add3) add3)
((eq? method-name 'get-count) get-count)
(else (super method-name))
))))
 
(define -make-counter2-
(lambda ()
(define super (-make-counter- 0))
(define add2
(lambda (this)
(call super 'add1)
(call super 'add1)))
(lambda (method-name)
(cond
((eq? method-name 'add2) add2)
(else (super method-name))
))))
 
(define c0 (-make-counter- 0))
(call c0 'addn 7)
(call c0 'get-count) => 7

但是,(define cc (-make-abs-counter-))所製造的cc物件,卻是一個虛的物件,因為呼叫它的addn一定會產生錯誤。

-make-abs-counter-是一個抽象類別(abstract class),它的功用是為它的子類別提供共用的方法,這些方法不能獨立使用,而需要使用this呼叫其子類別的方法才能適當的運作。

以上的許多範例說明了物件導向程式語言的重要特色。簡單的說,物件導向程式設計及分析,就是使用這些特色,並以增加程式碼的再利用性及維護的方便性為目標,而將一個軟體所需要達成的眾多功能的程式碼分門別類,並將其類別、方法及繼承的結構做適當的設計與配置的一門學問。

以上的幾個製造counter類別中的方法有的執行的很沒效率,例如:addn,但是這些例子的目的是以最簡短的程式碼說明super、this、abstract class的許多有趣的特色。

請開始做練習題第七題。

OOP:以List存放物件及方法

除了將物件一層層的包在一個個程序中的方式實做類別及物件之外,在這一單元我們會以將程序方法存放在list中的方式,來實做物件。以下是一個沒有繼承功能的陽春式類別,呼叫這個類別後會傳回一個存放程序方法的物件:

(define -make-counter- 
(lambda ()
(let ([count 0])
(list
(cons 'add1
(lambda () (set! count (+ count 1))))
(cons 'get-count
(lambda () count))))))
 
(-make-counter-)
=> ((add1 . #<procedure>) (get-count . #<procedure>))

以下則是用來呼叫一個物件的call程序。call之內的find-method的功用是找到要被呼叫的方法:

(define call
(lambda (obj method . args)
(define find-method
(lambda (obj method)
(cond
((null? obj) (error "Method ~a not found." method))
((eq? (caar obj) method) (cdar obj))
(else (find-method (cdr obj) method)))))
(apply (find-method obj method) args)))
 
(define c1 (-make-counter-))
c1 => ((add1 . #<procedure>) (get-count . #<procedure>))
(call c1 'add1)
(call c1 'get-count) => 1

我們可以利用增加this及super的方式,更完整的支援物件導向程式語言的功能:

(define call 
(lambda (obj method . args)
(define find-method
(lambda (obj method)
(cond
((null? obj) (error "Method ~a not found." method))
((eq? (caar obj) method) (cdar obj))
(else (find-method (cdr obj) method)))))
(apply (find-method obj method) obj args)))
 
(define –object- (lambda () '()))
 
(define -make-abs-counter-
(lambda ()
(let ([super (-object-)])
(let ()
(append
(list
(cons 'addn
(lambda (this n)
(if (not (= n 0))
(begin
(call this 'add1)
(call this 'addn (- n 1))))))
(cons 'subn
(lambda (this n)
(if (not (= n 0))
(begin
(call this 'sub1)
(call this 'subn (- n 1)))))))
super)))))
 
(define -make-counter-
(lambda ()
(let ([super (-make-abs-counter-)])
(let ([count 0])
(append
(list
(cons 'add1
(lambda (this) (set! count (+ count 1))))
(cons 'get-count
(lambda (this) count))
(cons 'set-count
(lambda (this n)
(set! count n))))
super)))))
 
(define -make-sub-counter-
(lambda ()
(let ([super (-make-counter-)])
(let ()
(append
(list
(cons 'sub1
(lambda (this)
(call super 'set-count
(- (call super 'get-count) 1)))))
super)))))
 
(define c1 (-make-sub-counter-))
c1 => ((sub1 . #<procedure>)
(add1 . #<procedure>)
(get-count . #<procedure>)
(set-count . #<procedure>)
(addn . #<procedure>)
(subn . #<procedure>))
(call c1 'add1)
(call c1 'get-count) => 1
(call c1 'subn 3)
(call c1 'get-count) => -2
(call c1 'set-count 9)
(call c1 'get-count) => 9

OOP:實做練習一

這個單元將使用 inheritance, super, this 及 abstract class,實做幾個在功能上逐漸擴充的 stack。這些 stack 有以下的繼承圖:

                  -object-
                     |
                   -stack-
                  /      \
                 /        \
     -bounded-stack-  -unbounded-stack-
                       /          \
                      /            \
     -sized-unbounded-stack-   -multi-unbounded-stack-

OOP:實做練習二

這個單元將使用 inheritance, super, this 及 abstract class,實做幾個 dictionary。這些 dictionary 有以下的繼承圖:

                   -object-
                      |
                 -dictionary-
                 /           \
       -bounded-dic-      -unbounded-dic-

此外,我們還會為某資管系設計有 IT 與 IM 兩個學程的的類別圖:

                   -object-
                      |
                    -mis-
                   /     \
                -it-     -im-

最後,我們會使用 -dictionary- 為某資管系班級的同學建置一班級資料庫。

執行程式的程式

這一個單元將透過一系列的練習題組,實做一個可以執行其他程式的程式:解譯器。這些練習不但可以對程式語言的語法、語意、實做方式及程式語言的設計有一比較完整的瞭解,而且還可以幫助程式設計師對程式語言的諸多可能及限制提供更寬廣的認識。

本單元系參考 http://icampustutor.csail.mit.edu/6.001-public/ 的第17、18章。

語法與語意的變化

這一組練習將撰寫幾個在語法與語意上有不同變化的解譯器。

Personal tools