Scheme/Scheme slide

From YuntechWiki

Jump to: navigation, search

Contents

Program by Design

  • http://programbydesign.org/
  • 一個有效的、迥異於傳統方式的程式設計教學資源網站
  • 15年以上的課程規劃(curriculum)經驗
  • 提供初中、高中、大學、公司內部程式設計訓練的教材
  • 引導了一系列程式開發環境、程式語言及程式設計方法的創新
  • 經費來源:美國國家科學基金會(NSF)、美國教育部、Exxon、Microsoft、Google等
  • 獎勵與肯定
    • 創辦人Matthias Felleisen得到了:
      • 2009 Karl V. Karlstrom Outstanding Educator Award
      • 這個獎代表Association for Computing Machinery(ACM)對資訊教育人員的最高肯定
      • 獲獎原因:對程式設計教材、教法與課程設計的創見,使得學生程式設計與學習程式語言的能力均獲得提升與改進

計畫緣起

  • 教授大學基礎程式設計課程非常挫折
  • 高中程式設計課程的品質很差
  • 學過程式的學生更難教

解決問題的作法

  • 問題:
    • 學生碰到程式設計的作業,不知如何下手
    • 學生不知如何除錯
  • 提供數個設計的步驟,幫助學生下手;在出錯時,也容易知道是那個步驟出錯:
    1. Data Analysis and Design: 將需求中的資訊描述為,程式可處理的資料
    2. Signature and header: 描述程式的輸入與輸出的型態
    3. Examples: 提供測試案例
    4. Template: 使用前面步驟中的資料型態與案例,設計程式樣版
    5. Body: 完成程式
    6. Test: 測試
  • 使用動畫讓學習更有趣
  • 強調測試
  • 使用複雜度逐步增加的語言系列
  • 設計課程與課程之間的過渡方式
  • 課程規劃:向上沿展到大學與研究所,向下沿展到初中

什麼是程式設計

  • 知道程式語言的語法、語意與如何寫它的句子
  • 知道如何寫指令
  • 知道library中有哪些程序
  • 以上都還不算是程式設計
  • 程式設計是
    • Programming is far more than the mechanics of language acquisition. It is about reading problem statements, extracting the important concepts. It is about figuring out what is really wanted. It is about exploring examples to strengthen your intuitive understanding of the problem. It is about organizing knowledge and it is about knowing what you don’t know yet. It is about filling those last few gaps. It is about making sure that you know how and why your code works, and that you and your readers will do so in the future. In short, it is really about solving problems systematically. (How to Design Program 2nd Edition)

程式設計思考力的作法

  • 訓練程式設計所需的關鍵能力
  • 幫助其他程式語言的學習
  • 以「練習就是學習」的方式,訓練程式設計的思考能力
  • 使用Scheme語言,但不是教Scheme
  • PLWeb配合,提供一百多題循序漸進,訓練程式設計思考能力的題目:
    • 布林邏輯與條件判斷
    • 遞迴式的資料與遞迴程式
    • 遞迴程式的轉換與迴圈
    • 抽象設計:相似程式的樣版設計
    • 物件導向的核心語意

於 PLWeb 使用此份教材,請先安裝 JDK (或JRE) 及 ChezScheme,相關說明請參考ChezScheme安裝說明

資訊、資料、處理與程式設計

資訊與資料

  • 資訊(Information):人能解釋、理解
    • 通常出現在需求分析或程式設計的問題描述中,例如:
    • 星期三、3PM或3公里等
    • A級的產品、A這個字母等
  • 資料(Data): 電腦能讀能寫,例如:3或A的字元代碼
  • 程式設計師要將資訊表示成(represent)資料給程式來處理,並產出人能夠解譯(interpret)的資訊。

程式 = 資料 + 處理

  • 程式的目的是為了處理資料
  • 處理資料分成「處理」與「資料」兩部分
  • 程式 = 資料 + 處理
  • 如何寫「資料」
  • 如何寫「處理」

「資料」如何寫呢?

  • 資料有「基本(basic)」與「複和(compond)」兩大類
  • 基本類資料的結構單純;而複和類資料的結構則相對複雜
  • 一個程式的邏輯結構,與其所處理之資料的結構息息相關
  • 以Scheme為例:
    • 基本類:number(數字)、symbol(符號)、boolean(布林)、character(字元)、string(字串);
    • 複和類:list(串列)、struct及vector(陣列)。

資料值(又稱constant,常數)的寫法

<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)

「處理」如何寫

define

syntax: (define var exp)
Returns: unspecified(不指定)
  • Returns標示某「語法」(syntax)的傳回值(return value)
  • 定義var的值是exp在evaluate(執行)後的return value(傳回值)
  • var是variable(變數)的縮寫
  • exp是expression(式子)的縮寫

變數(Variable)

  • Variable是程式語言的專有名詞
  • 每一個變數都有一個「名字」
  • 這個「名字」對應一個記憶體的「地址」
  • 這個「地址」存放該變數的值
  • 這個值又屬於一個「資料型態」

式子(Expression)

  • Expression也是程式語言的專有名詞
  • 所有的資料值(data value)都是一種expression
  • 變數也是一種expression
  • 其他的expression會依序介紹
  • 一個expression在evaluate後會傳回一個傳回值(return value)。

範例:變數的定義與「'」與不「'」的差異

  •  ; 之後的文字為註解,不會被執行
  •  ;=> 代表傳回(return)
(define a 1.35) ;定義變數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」指 a 這個symbol
  • 「(+ 2 a)」代表程序呼叫,將2與a的值相加,並傳回結果
  • 「'(+ 2 a)」指(+ 2 a)這個list
  • 程式碼與資料值,是以同一種方式表達的優點:
    • 程式的語法可以很簡潔
    • 能夠方便的將程式碼當成資料來處理
    • 適合作為研究程式語言新功能的工具

程序呼叫(procedure call)

syntax: (proc exp*)
Returns: 將執行exp*得到的0或多個傳回值,
傳入執行proc得到的procedure,
然後傳回執行該procedure的結果。
  • procedure(程序)是程式語言的專有名詞
  • 一個procedure有0或多個傳入值或輸入參數(input parameter)
  • exp* 的 * 代表 exp 可以重複 0 或多次
  • proc 及 exp* 都先被執行,並得到它們的傳回值
  • 這些 exp 的傳回值,傳入執行 proc 所得到的 procedure;執行後,便得到一個傳回值為程序呼叫的結果
  • 程序是放在傳入值的左邊

程序呼叫的範例

(define a 1.35)
(+ 2 a) => 3.35
(define subtract -)
(subtract 4 1) => 3
(+ (- a 0.35) 10) => 11
  • '- 這個符號與 - 這個變數,意義不同
  • - 這個變數的值,是一個能夠做減法的程序
  • Scheme將這個程序,存放在 - 這個變數中

資料存取與運算的程序

在上一個單元,我們介紹也使用了=、+、─等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。
 
(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>與<pair>

一個list是由一對一對的pairs所構成。一對(pair)有兩個部分,分別稱為:car與cdr。以下這張圖說明了pair如何的用來建構這幾個list:(a)、(a b)、((a) b c)、((a) (b c)) 及 (a . 1)、 (a b . c)兩個 pairs。其中(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)

List 與 pair 有何差異?

  • 除了null list也就是()之外,所有的 list 都至少有一個 pair.
  • pair 的主要功用是用來建構 list
  • 一個 improper list 也至少有一個 pair
  • improper list 的結尾不是 ()

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
procedure: (equal? obj1 obj2)
returns:若obj1與obj2的結構與儲存值都相同則傳回#t,要不則傳回#f
 
(equal? (cons 2 3) '(2 . 3)) => #t
(define l1 '(a (b)))
(equal? l1 '(a (b))) => #t
(eq? l1 '(a (b))) => #f
 
** 注意:equal? 可以用來比較obj1與obj2的結構與儲存值是否相同,
若相同則傳回#t;若不同則傳回#f, obj1與obj2可以儲存在不同的記憶
體位址。而eq?則只在obj1與obj2是指向相同的記憶體位址時,才傳回#t

布林與條件式

  • 表達「如果某種條件成立,則進行某種處理;若不成立,則另行處理」的程式邏輯
  • 包括:if、and、or、not、cond等式子

if

syntax: (if test consequent alternative) 
 
returns: 若test的值為true則傳回consequent的值,
要不然則傳回alternative的值。
 
(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)
 
syntax: (if test consequent)
 
returns: 若test的值為true則傳回consequent的值,
要不然則不傳回指定的傳回值(例如:void)。
 
(define x -4)
(if (< x 0)
'minus) => minus

and、or與if之間的關係

  1. 它們可以互相表達
  2. (and A B)與(if A B #f)的值完全相同
  3. (or A B)與(if A #t B)的值完全相同
  4. 可以使用 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

and

syntax: (and exp ...) 
returns: and 由左而右依序 evaluate exp ...,
若有一個 exp 的值為 false,則立即傳回 #f(不繼
續evaluate exp)。若全部的 exp 都不是 false,
則傳回最後一個 exp 的值。
 
(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)

or

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)

not

procedure: (not obj) 
returns: 若obj是false則傳回#t,要不則傳回#f。
 
(not #f) => #t
(not #t) => #f
(not '())=> #f
(not (< 4 5)) => #f

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)

  • 主要功用是處理資料
  • 內建的程序,例如:+、-、*、/、car、cdr、cons、number?、list?、pair?等等
  • 程式設計師自行撰寫的程序

lambda

  • 程序是以 lambda 這個保留字產生的
  • 計算三個傳入數字的平均:
(lambda (x y z) (/ (+ x y z) 3))

程序呼叫(procedure call)

  1. 將資料傳入程序
  2. 然後執行程序內的程式碼
  3. 傳回結果
  • 例如:
    ((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
  1. 有三個參數分別是x、y、z
  2. 傳入三個資料值分別是1、2、3
  3. 呼叫一個程序只需要將程序與傳入的資料用刮號刮起來
  4. 程序執行時,x 的值是 1, y 的值是 2, z 的值是 3
  5. 程序傳回它的執行結果: 2

將程序存入變數中

(define avg3 (lambda (x y z) (/ (+ x y z) 3))) 
 
(avg3 1 2 3) => 2
 
(+ 6 (avg3 2 4 6)) => 10
  • avg3便成為程序的名字
  • 方便重複使用

語法回顧

  • 「*」代表前面的<expression>可以重複出現0或多次
  • 「+」代表前面的<expression>可以重複出現1或多次。

Scheme的程式碼可以分為兩種:

  • <definition>
    1. (define <variable> <expression>):例如:
      (define a 3)
      (define b (+ 2 (* a a)))
      (define c '(1 2))
      (define d (cadr c))
  • <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>)
    6. (if <expression1> <expression2>)
    7. (cond (<expression1> <expression2>)+)
    8. (cond (<expression1> <expression2>)+ (else <expressionN>))

以上的語法已經足夠用來訓練「程式設計思考力」,這些語法再加上尚未介紹的begin, set!構成了任何電腦程式的核心。 參考:[1]

刮號的使用規則

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

處理單層遞迴性資料的遞迴程序

處理資料量固定的程序

(and2 '(#t #t)) => #t 
(and2 '(#t #f)) => #f
(and2 '(#f #t)) => #f
(and2 '(#f #f)) => #f
  • 輸入參數是一個list
  • 這個list固定有兩個布林值
  • 需使用car, cadr將兩個資料值取出
  • 程式碼不需要使用遞迴或迴圈

處理單層但資料量任意的程序

  • all-t? 檢查一個list中的所有元素是否均為#t
  • all-t? 的輸入是一個有限但有任意數量布林值的list
    (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?是一個處理單層flat list的程式

程序的設計步驟

第一步:定義輸入資料的格式

  • 將all-t?之輸入資料的格式稱為lob(list-of-boolean)
  • lob可以定義如下:
    1. '():是一個lob
    2. (cons <boolean> lob) <boolean>為#t或#f:也是一個lob.
    • 注意:這個資料定義有遞迴的特性──紅色部分顯示lob的定義,也提及lob自己。
    • 遞迴資料的定義中,至少要有一個條件不提及自己。
  • 例如:
    '() => ()
    (cons #t '()) => (#t)
    (cons #f (cons #t '())) => (#f #t)
    (cons #f (cons #f (cons #t '()))) => (#f #f #t)
  • 測試一筆資料是否是lob,需要null?及pair?:
    (null? '()) => #t
    (pair? (cons #t '())) => #t
  • 若另外定義cons?為pair?,則更貼切:
    (define cons? pair?)
    (cons? (cons #f '())) => #t
    (cons? (cons #f (cons #t '()))) => #t

第二步:撰寫輸入、輸出的型態並描述程序的功能

  • all-t?這個程式的輸出入型態是:lob -> boolean
    • 傳入一個lob、傳出一個布林值
  • all-t?這個程式的輸入一個含有0或多個布林值的list,判斷list中的值是否都為ture
    ;; all-t?: lob -> boolean
    ;; 輸入一個含有0或多個布林值的list,判斷這個list中的值是否都為ture值
    (define all-t? (lambda (ls) ...))

第三步:設計測試用案例

  • 為每一個資料定義的條件提供測試案例
    (eq? (all-t? '()) #t)  => #t
    (eq? (all-t? '(#t)) #t) => #t
    (eq? (all-t? '(#f)) #f) => #t
    (eq? (all-t? '(#t #t #t)) #t) => #t
    (eq? (all-t? '(#t #t #f #t)) #f) => #t

第四步:設計樣版

  • all-t?必須處理lob的兩類資料
  • 因此cond內有此兩類資料的條件判斷式:
    (define all-t?
    (lambda (ls)
    (cond
    ((null? ls) ...)
    ((cons? ls) ...))))
  • 當(null? ls)成立時,不需要取出ls內資料的程式碼
  • 當(cons? ls)成立時,需要(car ls)及(cdr ls)擷取ls內的資料進行處理
    (define all-t?
    (lambda (ls)
    (cond
    ((null? ls) ...)
    ((cons? ls) ...(car ls) ... (cdr ls)))))

第五步:設計完整的程式

  • (cons? ls)成立時(car ls)有兩種可能:#t或#f
  • 當(car ls)是#f時,(all-t? ls)的答案是#f
    (define all-t?
    (lambda (ls)
    (cond
    ((null? ls) #t)
    ((cons? ls) (cond
    ((eq? #t (car ls)) ...(cdr ls)...)
    ((eq? #f (car ls)) #f))))))
  • 當(eq? #t (car ls))成立時,(all-t? ls)的值與(all-t? (cdr ls))的值相等
  • 完整的程式:
    (define all-t?
    (lambda (ls)
    (cond
    ((null? ls) #t)
    (else (cond
    ((eq? #t (car ls)) (all-t? (cdr ls)))
    ((eq? #f (car ls)) #f))))))
  • 可以簡化成:
    (define all-t?
    (lambda (ls)
    (cond
    ((null? ls) #t)
    ((car ls) (all-t? (cdr ls)))
    (else #f))))

第六步:測試

  • 輸入all-t?及以下的程式碼進行測試:
    ;; all-t?: lob -> boolean
    ;; 輸入一個含有0或多個布林值的list,判斷這個list中的值是否都為ture值
     
    (define all-t?
    (lambda (ls)
    (cond
    ((null? ls) #t)
    ((car ls) (all-t? (cdr ls)))
    (else #f))))
     
    (eq? (all-t? '()) #t)
    (eq? (all-t? '(#t)) #t)
    (eq? (all-t? '(#f)) #f)
    (eq? (all-t? '(#t #t #t)) #t)
    (eq? (all-t? '(#t #t #f #t)) #f)

Trace (all-t? '(#t #t #t))的執行過程

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

追蹤 (all-t? '(#t #t #f #t))的執行過程

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

all-t?的特色

  1. 有終止條件(termination condition)如:(null? ls)及else。
  2. 有遞迴呼叫,而遞迴呼叫所傳入的資料一定會趨近終止條件(例如使用cdr使ls愈來愈縮短)。
  3. 這很合理,因為這樣程式才能結束。
  4. 程序結構與資料結構(lob)高度相關。

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

追蹤與除錯

  • 在撰寫程式的過程中,最簡單的除錯工具是把變數的值印出來
  • (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?的輸入參數的值,及最後的執行結果
  • 在程式碼中加入
    1. (import debugging)與(trace 'all-t?)
    2. 將(lambda (<variable>) <expression>)改為(trace-lambda name (<variable>) <expression>)(註:name可以是all-t?或其他的名字)
  • 這兩種方式也可以看到參數傳入與傳出的狀況

累計單層遞迴性資料的遞迴程序

  • 答案的產生需要經過累計(例如:累加、累乘、或累cons)的過程

傳回數字的遞迴程序:計算一個list內有幾個#t

  • count-t:
;; count-t: lob -> number
;; count-t這個程式輸入一個含有0或多個布林值的list,
;; 計算list中有幾個#t
 
(define count-t
(lambda (ls) ...))
 
(= (count-t '()) 0)
(= (count-t '(#t #t #f #t)) 3)
(= (count-t '(#f #t #t) 2)
  • 很顯然的,在程序執行的過程中如果遇到#t,則需要將1加入結果之中。寫法與all-t?相當類似:
(define count-t
  (lambda (ls)
    (cond
      ((null? ls) 0)
      (else (cond
              ((eq? #t (car ls)) (+ 1 (count-t (cdr ls))))
              ((eq? #f (car ls)) (count-t (cdr ls))))))))
  • 也可以簡化成
(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

程式的輸入、輸出的型態與程式的邏輯高度相關

  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

傳回list的遞迴程序:將list內的#t傳回

  • select-t
;; select-t: lob -> lob
;; select-t這個程式輸入一個含有0或多個布林值的list,
;; 將list中的#t放入另一個list並傳回

(define select-t 
  (lambda (ls) 
    (cond 
      ((null? ls) '()) 
      ((car ls) (cons #t (select-t (cdr ls)))) 
      (else (select-t (cdr ls))))))

(equal? (select-t '()) '())
(equal? (select-t '(#t #t #f #t)) '(#t #t #t))
(equal? (select-t '(#f #t #t)) '(#t #t))

儲存資料紀錄的list

資料記錄(record)

  • 假設某公司的員工資料有四個欄位:name, age, salary
  • 一種表示Peter這位員工的資料是使用list:(peter 34 36000)
  • 使用list模擬一個製造員工資料紀錄及存取欄位值的程序:
    ;; make-worker
    ;; symbol number number -> list-of-worker
    ;; 模擬製造員工資料紀錄及存取欄位值的程序
     
    (define make-worker
    (lambda (name age salary)
    (list name age salary)))
    (define worker-name car)
    (define worker-age cadr)
    (define worker-salary caddr)
  • Scheme有一個define-record的語法,可以自動定義這些程序
    (define-record worker (name age salary))
  • DrRacket使用define-struct自動定義這些程序
    (define-struct worker (name age salary))
    • 以上的定義自動產生:
      ;; 製造worker的程序
      make-worker
       
      ;; 取出一個worker中的欄位值的程序
      worker-name
      worker-age
      worker-salary
       
      ;; 更改一個worker中的欄位值的程序
      set-worker-name!
      set-worker-age!
      set-worker-salary!

計算某公司員工的總薪資

  • 某公司有三位員工:
    (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))
  • 以list存放公司員工的資料:list-of-worker
  • 計算某公司員工的總薪資的程式:
    ;; total-salary: list-of-worker -> number
    ;; total-salary計算list內員工薪資的總和
     
    (define total-salary
    (lambda (ls)
    (cond
    ((null? ls) 0)
    (else (+ (worker-salary (car ls))
    (total-salary (cdr ls)))))))
     
    (= (total-salary '()) 0)
    (= (total-salary (list w1 w2 w3)) 94000)

處理自然數的程序

  • 自然數可以任意的大
  • 自然數的資料定義:
  • 一個自然數是:
    1. 0, 或
    2. (add1 n), n 是一個自然數
  • 一個自然數是由 add1 逐步的累加而來,因此,要能夠處理 n 便需要逐步的使用(sub1 n), (sub1 (sub1 n)), ...
    • 因為 (sub1 (add1 n)) = n
  • 這與cdr, cons有這樣的關係類似:
    • (cdr (cons a-value a-list)) = a-list

處理自然數的範例

;; gen-list
;; gen-list: symbol number -> list
;; 如果 s 與 n 是gen-list的輸入參數,則其輸出是一個有 n 個 s 的 list

(define gen-list
  (lambda (s n)
    (cond
      ((= n 0) '())
      (else (cons s (gen-list s (- n 1)))))))

(equal? (gen-list 'a 0) '())
(equal? (gen-list 'b 3) '(b b b))

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

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

內涵式遞迴

  • 階乘的定義可以用Scheme改寫如下,我們將之命名為factorial,意思是階乘程序(procedure)的第一個版本:
;; factorial
;; factorial: number -> number
;; 計算一個一個自然數的階乘
 
(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的執行
  • 以色彩追尋factorial的執行:

Fac.jpg

尾端式的遞迴

  • 尾端遞迴(tail-recursion)的特色是遞迴呼叫沒有內涵在任何一個尚未執行完成的式子(expression)內。
  • 以下面的例子而言,呼叫tail-fac的遞迴呼叫是在if expression之內,但是該if expression的條件判斷式已經執行完畢。
(define tail-fac
(lambda (n m)
(if (= n 0)
m
(tail-fac (- n 1) (* n m)))))
 
(tail-fac 3 1)
=> (tail-fac 2 3)
=> (tail-fac 1 6)
=> (tail-fac 0 6)
=> 6
  • 以上程序的執行狀況是「平的」
  • 不像內涵式遞迴累積一層又一層如同樓梯般的式子
  • 將內涵式遞迴程序轉換成尾端遞迴程序的技巧是增加傳入的參數
  • 以tail-fac來說我們增加了一個能夠儲存累乘值的參數m
  • 增加這個參數後便不需要以累積乘法算式的方式來計算階乘的值

迴圈

  • 遞迴轉迴圈的步驟:
    1. 將內涵式遞迴程序轉換成尾端式遞迴程序
    2. 將尾端式遞迴程序之輸入參數「提出」程序之外成為全域變數
      • golbal variable: 意指定義在程式碼最外層的變數;
      • local variable: 定義在procedure之內的變數則稱為區域變數
    3. 使用begin與set!執行改變或累計數值的步驟
      • begin是一種語法,其意義是依照順序一個式子、一個式子的執行之後的所有式子,並傳回在begin內最後一個式子的值(功用類似C與Java的{ })
      • set!也是一個語法,其意義是更改一個變數的值。例如:(set! n (+ n 3))的作用是將n的值改成n + 3(功用與其他程式語言的n = n + 3相同)。例如:
        (define n 3)
        (begin
        (set! n (+ n 3))
        (+ n n)) => 12
  • 有了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
  • 上面的fac3程序不能隨意的計算其他數字的階乘
  • 加入以下的fac程序然後傳入參數,並且重新設定n與m的值便可以解決這個問題:
(define fac 
(lambda (num)
(set! n num)
(set! m 1)
(fac3)))
(fac 3) => 6
(fac 4) => 24
  • 觀察上面fac與fac3兩個procedure的遞迴呼叫(fac3),(fac3)是一個沒有參數的呼叫,其作用與一些程式語言中的goto無異,而以上的程式也與一般程式語言的foo-loop, while-loop的運算邏輯相同,只是語法的表達方式不同而已。以下是 VB 與 C 計算階乘的程式可以參考對照:
Module Module1
Dim m = 1 'm為全域變數
Sub Main()
Call fac(3) '呼叫fac
End Sub
Function fac(ByVal n As Integer) As Integer
If n = 0 Then
Console.Write(m)
Console.Read() '讓主控台暫停,方便設計者看輸出狀況
Else
m = m * n
n = n - 1
Call fac(n)
End If
End Function
End Module

以下是另一種寫法:

Module Module1
Sub Main()
Dim m = 1
While n <> 0
m = m * n
n = n - 1
End While
Console.Write(m)
Console.Read()
End Sub

以下是 C 語言的版本:

#include <stdio.h>
 
int main(){
int n;
int m = 1;
 
printf("輸入階層數:");
scanf("%d", &n);
 
while (n != 0){
m = m * n;
n = n - 1;
}
 
printf("%d\n", m);
return 0;
}

全域變數與區域變數

(define n 0) ; 全域變數
(define m 0) ; 全域變數
 
(define fac3
(lambda ()
(if (= n 0)
m
(begin
(set! m (* m n))
(set! n (- n 1))
(fac3)))))
 
(define tail-fac
(lambda (n m) ; 區域變數
(if (= n 0)
m
(tail-fac (- n 1) (* n m)))))
 
(define fac
(lambda (num) ; 區域變數
(set! n num)
(set! m 1)
(fac3)))
 
(fac 3) => 6
(fac 4) => 24
(tail-fac 3 1) => 6
(tail-fac 4 1) => 24

處理集合的程序

  • 包括交集、聯集、子集等
  • 這些程序需要用到一個稱為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

深層串列的處理

  • Deep list(深層串列)是list中還有list的list。例如:
    '((a b) c (d ((a) f)))

深層串列的資料定義

  • 一個由symbol構成的深層串列SL, 可以是:
    1. ():空串列;
    2. (cons s slist):s 是一個symbol, sllist 是一個 SL;
      • 例如:(cons 'abc '()) = (abc)
    3. (cons slist slist2):slist與slist2都是SL。
      • 例如:(cons (cons 'abc '()) '(x y)) = ((abc) x y)

處理深層串列的程序樣版

(define deep
(lambda (ls)
(cond
((null? ls) ...)
((pair? (car ls)) (... (deep (car ls)) (deep (cdr ls))))
((... (car ls)) (... (deep (cdr ls))))
(else (deep (cdr ls))))))
(define deep
(lambda (ls)
(cond
((null? ls) ...)
((... (car ls)) (... (car ls) (deep (cdr ls))))
(else (... (deep (car ls)) ... (deep (cdr ls)))))))

計算一個deep list中有幾個a的範例

;; count-a
;; count-a: LS -> number
;; 計算一個symbol的深層串列中有幾個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 cond3
=> (+ (+ 1 (count-a '(b))) (count-a '((a a)))) by cond2.1
=> (+ (+ 1 (count-a '())) (count-a '((a a)))) by cond2.2
=> (+ (+ 1 0) (count-a '((a a)))) by cond1
=> (+ 1 (count-a '((a a))))
=> (+ 1 (+ (count-a '(a a)) (count-a '()))) by cond3
=> (+ 1 (+ (+ 1 (count-a '(a))) (count-a '()))) by cond2.1
=> (+ 1 (+ (+ 1 (+ 1 (count-a '())))) (count-a '()))by cond2.1
=> (+ 1 (+ (+ 1 (+ 1 0)) (count-a '()))) by cond1
=> (+ 1 (+ (+ 1 (+ 1 0)) 0)) by cond1
=> 3
  • 這個處理deep lisp的procedure與處理flat list的procedure的最大差異是else部分的程式碼
  • 這部分的程式碼代表(pair? (car ls))的條件判斷成立
  • 這時便分別對(car ls)及(cdr ls)做共兩次的遞迴呼叫,並將兩次的結果加總,便得到答案

高階程序

  • Higher-order procedures(高階程序)可以將procedure當作參數傳入或傳出procedure

程序可以是其他程序的參數

例如:

(define foo (lambda (p a g) (g (p a)))) 
 
(define a 5)
 
(foo (lambda (x) (+ 3 a x))
4
(lambda (x) (* x a 5))) => 300
  • 以下是另一個將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 number -> number) number number -> number
  • 也就是它有三個參數:
    • 第一個參數是一個procedure,它的型態是number number -> number
    • 第二、三個參數則都是number
  • 另一個呼叫compute的方式是:
    (compute cons 1 2) => (1 . 2)
    (compute cons 'a '(2 3)) => (a 2 3)
  • 這時compute的型態則是:
(any any -> pair) any any -> pair
  • any代表任意型態
  • compute有三個參數
    • 第一個參數的型態是一個procedure,它的型態是any any -> pair
    • 第二、三個參數的型態,都是any。
  • any的使用並不足以表達compute的各種可能。比較完整一點的表達方式應該是這樣:
(T1 T2 -> T3) T1 T2 -> T3
  • T1, T2, T3是三個型態變數(type variables), 也就是T1, T2, T3都可以對應某個真實的type
  • compute的輸出入參數間的關係只要符合
(T1 T2 -> T3) T1 T2 -> T3
  • 上式中的兩個T1都有一樣的型態,兩個T2都有一樣的型態及兩個T3都有一樣的型態,便不會在執行時產生型態錯誤(type error)
  • 這種含有更具彈性的型態變數的程序稱為polymorphic or generic functions.

程序可以傳回程序

另一個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的執行過程

程序的「位階」

  • Scheme程序的「位階」與一般的值,例如:number, list, boolean一樣,意思是:它可以存放在變數內,可以從程序傳入與傳出,也可以存放在資料結構,如list內。這個特性是Scheme與一般的程式語言相比,語意特別豐富的主要原因。

Closure

  • 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的執行過程

抽象設計

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

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

  • 以下的兩個程序相當的類似,他們都傳入一串數字,然後將大於或小於某數的數字以串列輸出:
(define above
  (lambda (n lon)
    (cond
      ((null? lon) '())
      ((> (car lon) n) (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) '())
      ((< (car lon) n) (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) (filter2 op (cdr lon))))
      (else (filter2 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)) ls)))
(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) ;=> 3
    (let ([x 4]) x) ;=> 4
  • 全域變數與區域變數彼此同名,則區域變數遮住了全域變數,例如:
    (define x 3)
    (define f +)
    (let ([x 4])
    (define f *)
    (f 5 x)) ;=> 20
  • 外層的變數與內層的變數彼此同名,則內層的變數遮住了外層的變數

陣列

  • Vector(陣列)在某些程式語言中被稱為array
  • 對某些應用來說,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)

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

  • 「類別(class)」可以生成「物件(instance or object)」
  • 「物件 = 物件變數(instance variable) + 程序方法(method)」
    • 「物件變數」負責資料的儲存
    • 「程序方法」則負責資料的處理

以傳統方式撰寫的計數器物件

(define count 0) 
 
(define add1
(lambda () (set! count (+ count 1))))
 
(define get-count
(lambda () count))
 
(add1)
(add1)
(get-count) => 2
  • count負責儲存資料
  • add1及get-count則可以更改及讀取count的值
  • 缺點:一個物件需要對應一套程式碼
  • 如果程式中需要兩個計數器,則上面的程式碼便需複製兩次,而且物件變數及程序方法的名稱還不能重複。

使用區域變數來包裝物件

  • 改進方式:將以上的程式碼包裝在以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
  • 可以使用複製程式碼的方式定義新的counter,而且可以不用更改add1, get-count等程序方法的名稱:
(define counter2 
(let ([count 0])
(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))
))))
((counter2 'add1))
((counter2 'add1))
((counter2 'get-count)) ;=> 2
  • 缺點:若一個程式在執行時(run time)需要不定數量或成百上千的counter,那麼這個方式需要重複複製成百上千次相同的程式碼,所以就不可行了。

以程序來包裝物件

  • 改進方式:利用高階程序,將上面的的程式碼及新增的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的值
    • 這塊區域變數區也是物件的物件變數區
    • c0, c1各有一個物件變數區:裡面分別儲存了屬於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))))
  • 由於-make-counter-可以用來製造類似功用的counter,因此make-counter也被稱為一個「類別」(class)。

方法的呼叫:call

  • 為了改進上述「雙刮號」的呼叫方式,我們另行定義以下的call程序
  • call可以接受變動數目的參數,以滿足不同方法的參數個數會不同的需要
(define call 
(lambda (obj method-name . args)
(apply (obj method-name) args)))
 
(call c1 'get-count) => 1 ; get-count 有0個參數
(call c1 'set-count 3) ; set-count 有1個參數
(call c1 'get-count) => 3

參數數目可變動的程序

  • 語法:(lambda (arg1+ . args) exp ...)
((lambda (a . b) a) 1) => 1      ; a is 1
((lambda (a . b) b) 1) => () ; b is ()
((lambda (a . b) b) 1 2) => (2) ; b is (2)
((lambda (a b . c) (+ a b)) 2 3 4 10) => 5 ; a is 2, b is 3
((lambda (a b . c) c) 2 3 4 10) => (4 10) ; c is (4 10)
((lambda (a b . c) (cons (+ a b) c)) 2 3 4 10) => (5 4 10)

apply:將參數以list傳入程序中

  • apply這個程序的第一個參數必定是另一個程序
  • 第二個參數則是其第一個參數的輸入參數
  • apply的功用是可以將參數包在list中,然後傳入其第一個參數並進行呼叫:
(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-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方法

-object-類別

  • -make-counter-沒有繼承類別
  • 定義-object-為最上層的類別,讓-make-counter-繼承
  • Java的最上層的類別稱為Object
  • -object-讓上層類別的寫法格式與下層類別的一致
  • 可以定義OO的高階語法,讓OO的高階程式碼被翻譯成Scheme的原始程式碼
  • 以下是繼承-object-的-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))
))))

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

this的妙用

  • 將物件本身(this)也當作參數傳入方法中,能夠讓物件呼叫this中所有方法
(define call 
  (lambda (obj method-name . args) 
    (apply (obj method-name) obj args))) 
  • this能夠讓一個物件中的方法,呼叫自己這個物件的方法。
  • 以下是一個長方體的類別cuboid。這個類別有兩個方法:area, volume,分別用來計算面積及體積,而 volume 會使用 this 來呼叫 area 以計算體積。:
(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 -cuboid-
(lambda (w l h)
(define super (-object-))
(define volume
(lambda (this)
(* h (call this 'area))))
(define area
(lambda (this)
(* w l)))
(lambda (method-name)
(cond
((eq? 'volume method-name) volume)
((eq? 'area method-name) area)
(else (super method-name))))))
 
(define r1 (-cuboid- 2 3 4))
(call r1 'area) ;=> 6
(call r1 'volume) ;=> 24
  • 我們可以用類似的寫法來撰寫圓柱體的類別cylinder。這個類別同樣有兩個方法:area, volume,分別用來計算面積及體積,而 volume 會使用 this 來呼叫 area 以計算體積。
(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 -cylinder-
(lambda (r h)
(define super (-object-))
(define volume
(lambda (this)
(* h (call this 'area))))
(define area
(lambda (this)
(* r r 3.14)))
(lambda (method-name)
(cond
((eq? 'volume method-name) volume)
((eq? 'area method-name) area)
(else (super method-name))))))
 
(define c1 (-cylinder- 3 4))
(call c1 'area) ;=> 28.26
(call c1 'volume) ;=> 113.04

觀察以上兩個類別的程式碼,可以發現 volume 的寫法完全相同。這時我們可以新增一個 -shape- 類別,來讓 -rectangle- 及 -cylinder- 繼承,如此可以讓 volume 同時被 -rectangle- 及 -cylinder- 共用,因此 -rectangle- 及 -cylinder- 內的 volume 便可以刪除了:

(define -shape-
(lambda (h)
(define super (-object-))
(define volume
(lambda (this)
(* h (call this 'area))))
(lambda (method-name)
(cond
((eq? 'volume method-name) volume)
(else (super method-name))))))
 
(define -rectangle-
(lambda (w l h)
(define super (-shape- h))
(define area
(lambda (this) (* w l)))
(lambda (method-name)
(cond
((eq? 'area method-name) area)
(else (super method-name))))))
 
(define -circle-
(lambda (r h)
(define super (-shape- h))
(define area
(lambda (this) (* 3.14 r r)))
(lambda (method-name)
(cond
((eq? 'area method-name) area)
(else (super method-name))))))

注意:-shape- 這個類別,不能單獨的存在。因為,它必須要有子類別所提供的 area 方法才能正常運作,具備這種特質的類別叫做「抽象類別」(abstract class)。

請開始做練習題第5, 6, 7, 8題。

抽象類別(abstract class)

需求一:設計一個更新時加4,並且能為產生的物件命名的計數器類別

(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-counter4-
(lambda (count name)
(define super (-object-))
(define get-count (lambda (this) count))
(define get-name (lambda (this) name))
(define update
(lambda (this)
(set! count (+ count 4))))
(lambda (method-name)
(cond
((eq? method-name 'get-count) get-count)
((eq? method-name 'get-name) get-name)
((eq? method-name 'update) update)
(else (super method-name))))))
 
(define c4 (-make-counter4- 3 'race))
(call c4 'update)
(call c4 'get-count) ;=> 7
(call c4 'get-name) ;=> 'race

需求二:設計一個更新時加5,且能記錄製造物件日期的計數器類別

(define -make-counter5- 
(lambda (count date)
(define super (-make-abs-counter-))
(define get-count (lambda (this) count))
(define get-date (lambda (this) date))
(define update
(lambda (this)
(set! count (+ count 5))))
(lambda (method-name)
(cond
((eq? method-name 'get-count) get-count)
((eq? method-name 'get-date) get-date)
((eq? method-name 'update) update)
(else (super method-name))))))
 
(define c5 (-make-counter5- 0 20110201))
(call c5 'update)
(call c5 'get-count) ;=> 5
(call c5 'get-date) ;=> 20110201

需求三:為前二種計數器增加能一次執行數個更新的功能

  • 因為兩種計數器都需要這個功能,所以可以為他們共同設計一個具有這個功能的父類別
(define -make-abs-counter- 
(lambda ()
(define super (-object-))
(define update-n-times
(lambda (this n)
(if (not (= n 0))
(begin
(call this 'update)
(call this 'update-n-times (- n 1)))
(call this 'get-count))))
(lambda (method-name)
(cond
((eq? method-name 'update-n-times) update-n-times)
(else (super method-name))))))
 
(define -make-counter4-
(lambda (count name)
(define super (-make-abs-counter-))
(define get-count (lambda (this) count))
(define get-name (lambda (this) name))
(define update
(lambda (this)
(set! count (+ count 4))))
(lambda (method-name)
(cond
((eq? method-name 'get-count) get-count)
((eq? method-name 'get-name) get-name)
((eq? method-name 'update) update)
(else (super method-name))))))
 
(define c4 (-make-counter4- 3 'race))
(call c4 'update-n-times 7) ;=> 31
 
(define -make-counter5-
(lambda (count date)
(define super (-make-abs-counter-))
(define get-count (lambda (this) count))
(define get-date (lambda (this) date))
(define update
(lambda (this)
(set! count (+ count 5))))
(lambda (method-name)
(cond
((eq? method-name 'get-count) get-count)
((eq? method-name 'get-date) get-date)
((eq? method-name 'update) update)
(else (super method-name))))))
 
(define c5 (-make-counter5- 0 20110201))
(call c5 'update-n-times 3) ;=> 15
  • (-make-abs-counter-)所製造的物件,是一個虛的物件,因為呼叫它的update-n-times方法一定會產生錯誤
  • -make-abs-counter-是一個抽象類別(abstract class),它的功用是為它的子類別提供共用的方法,這些方法不能獨立使用,而需要使用this呼叫其子類別的方法才能適當的運作,例如:
    • update-n-times呼叫update及get-count

程式可以更簡化:沒有重複的程式碼

  • 簡化之後的父類別已經不再是abstract,因此更名為-make-counter-
(define -make-counter- 
(lambda (count incre)
(define super (-object-))
(define get-count (lambda (this) count))
(define update (lambda (this) (set! count (+ count incre))))
(define update-n-times
(lambda (this n)
(if (not (= n 0))
(begin
(call this 'update)
(call this 'update-n-times (- n 1)))
count)))
(lambda (method-name)
(cond
((eq? method-name 'get-count) get-count)
((eq? method-name 'update) update)
((eq? method-name 'update-n-times) update-n-times)
(else (super method-name))))))
 
(define -make-counter4-
(lambda (count name incre)
(define super (-make-counter- count incre))
(define get-name (lambda (this) name))
(lambda (method-name)
(cond
((eq? method-name 'get-name) get-name)
(else (super method-name))))))
 
(define c4 (-make-counter4- 3 'race 4))
(call c4 'update-n-times 7) ;=> 31
 
(define -make-counter5-
(lambda (count date incre)
(define super (-make-counter- count incre))
(define get-date (lambda (this) date))
(lambda (method-name)
(cond
((eq? method-name 'get-date) get-date)
(else (super method-name))))))
 
(define c5 (-make-counter5- 0 20110201 5))
(call c5 'update-n-times 3) ;=> 15

OOP:以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>))
; #<procedure> is procedure's 的列印表示(printable representation)

呼叫物件的call程序

(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
  • find-method的功用是找到要被呼叫的方法:

增加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-counter- 
  (lambda (count incre) 
    (let ([super (-object-)]) 
      (append  ; 將 (list ...) 及 super 合併;super的值是()
       (list 
        (cons 'get-count (lambda (this) count)) 
        (cons 'update (lambda (this) (set! count (+ count incre))))
        (cons 'update-n-times
              (lambda (this n) 
                (if (not (= n 0)) 
                    (begin 
                      (call this 'update) 
                      (call this 'update-n-times (- n 1)))
                    count))))
       super)))) 

(define -make-counter4- 
  (lambda (count name) 
    (let ([super (-make-counter- count 4)])
      ; super的值是
      ; ((get-count . #<procedure>)
      ;  (update . #<procedure>) 
      ;  (update-n-times . #<procedure>)) 
      (append 
       (list 
        (cons 'get-name (lambda (this) name)))
       super))))

(define -make-counter5- 
  (lambda (count date) 
    (let ([super (-make-counter- count 5)]) 
      (append 
       (list 
        (cons 'get-date (lambda (this) date))) 
       super)))) 

(define c4 (-make-counter4- 3 'race))
(call c4 'update-n-times 7) ;=> 31
(define c5 (-make-counter5- 0 20110201))
(call c5 'update-n-times 3) ;=> 15
c4 ;=>
((get-name . #<procedure>)
 (get-count . #<procedure>)
 (update . #<procedure>)
 (update-n-times . #<procedure>))

排序

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 1)))
 
(define node-left (lambda (node) (vector-ref node 0)))
 
(define set-node-left!
(lambda (node new-left)
(vector-set! node 0 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))
Personal tools