Maxkit: Scheme Tutorial 1

通常要了解 Scheme 會建議要閱讀 SICP: Structure and Interpretation of Computer Programs 這本書，這是 MIT 的一個課程，以 Scheme 為程式語言，不過在閱讀 SICP 以前，我們先閱讀另一個 Yet Another Scheme Tutorial，目的是能夠在閱讀 SICP，有一些先備知識。

Why Scheme

雖然 Common Lisp 比較適合建構商業環境的軟體，但還是建議先學習 scheme，因為 scheeme 的語法簡單，學習 scheme 會讓 programmer 對程式語言更有感覺。由於 scheme compiler 很多，為了學習 SICP，這邊建議安裝 mit-scheme，mit scheme 符合 Revised5 Report on the Algorithmic Language Scheme (R5RS) 的規範。

mit-scheme編譯速度很快，但並不完全符合 R5RS 的規範。

在 mac 可直接用 macport 安裝

sudo port install mit-scheme

也可參考這些安裝方法:

Mac 安裝 mit-scheme 配置筆記

How to install MIT Scheme on Mac?

在 windows 就下載安裝套件安裝就好了。

安裝後就可使用 scheme

$ scheme
MIT/GNU Scheme running under OS X
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 2014 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO warranty; not even for
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Monday October 29, 2018 at 11:43:21 PM
  Release 9.2 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118 || Edwin 3.116

1 ]=>

安裝完成後，可另外設定 scheme 的啟動工作環境，這是一個初始化的檔案，裡面是 scheme 的程式，在 unix 系統為 .scheme.init，在 windows 為 scheme.ini，該檔案要放在 HOME 環境變數的位置，unix 為 /Users/username，windows 為 \Document and Setting\username

新增檔案 /Users/username/.scheme.init，內容為

(cd "~/Downloads/scheme")
(define call/cc call-with-current-continuation)

第一行是切換目錄，第二行是定義 call-with-current-continuation 的縮寫

執行 scheme 後，會多看到這一行載入初始設定檔

;Loading "/Users/username/.scheme.init"... done

1 ]=> (pwd)

;Value 2: #[pathname 2 "/Users/username/Downloads/scheme/"]

ref: Running Scheme

Edwin 是 scheme text editor，可用此 command line 進入 Edwin

$ mit-scheme --edit

離開 Edwin 要用Ctrl-x z，回到 mit-scheme command line ，再用 Ctrl-c q 離開 mit-scheme

因為 mit-scheme 的 REPL 介面，預設沒有 history 的功能，藉由 readline wrapper: rlwrap 這個工具可以解決這個問題。

在 mac 可使用 macport 安裝 rlwrap

sudo port install rlwrap

透過 rlwrap 執行 scheme，就可以用 arrow 上下，取得輸入過的 command history

rlwrap scheme

基本四則運算

1 ]=> (+ 1 2)

;Value: 3

括號代表一次計算 (+ 1 2) 就是 1+2
左括號後面是函數名稱，然後是參數，scheme 中大部分的 operator 都是函數
可用 space, tab, newline 做為分隔符號，逗號和分號不是分隔符號

在這個函數中，當所有的參數被求值後，就開始進行計算。但對參數的求值順序是沒有被規範的，也就是說，參數並不是總是會從左到右求值。以下為計算過程：

符號+被求值，確認為加法。僅在前端輸入+，解釋器會返回：[arity-dispatched-procedure 1] 這表示+是代表「過程1」的一個符號
對1求值得到1。通常對 boolean, number, char, string 求值的結果就是它們本身。對符號求值的結果可能是一些其他的東西。
對2求值得到2。
最後，對(+ 1 2)求值得到3並跳出括號。在 scheme 中，求得的值會跳出括號外，並且這個值（expression 的最終值）會被列印到前端。

+ 後面可接多個參數

(+)
(+ 1)
(+ 1 2)
(+ 1 2 3)

scheme 可以處理分數，也可以處理複數 (a+bi，a稱為實部，b稱為虛部)。函數exact->inexact 可把分數轉換為浮點數

(- 10 3)    ; 7

(- 10 3 5)  ; 2

(* 2 3)     ; 6

(* 2 3 4)   ; 24

(/ 29 3)    ; 29/3

(/ 29 3 7)  ; 29/21

(/ 9 6)     ; 3/2

(exact->inexact (/ 29 3 7)) ; 1.380952380952381

可以套嵌 nesting

(* (+ 2 3) (- 5 3)) ;10

(/ (+ 9 1) (+ 2 3)) ;2

練習

計算 (1+39) * (53-45)
```
(* (+ 1 39) (- 53 45))      ;320
```
計算 (1020 / 39) + (45 * 2)
```
(+ (/ 1020 39) (* 45 2))  ;1510/13
```
求和：39, 48, 72, 23, 91
```
(+ 39 48 72 23 91)            ;273
```
求平均值：39, 48, 72, 23, 91 (結果取為浮點數)
```
(exact->inexact (/ (+ 39 48 72 23 91) 5))     ;54.6
```

quotient 求商數
remainder 與 modulo 求餘數
sqrt 求平方根

(quotient 7 3) ;2

(modulo 7 3)   ;1

(sqrt 8)       ;2.8284271247461903

三角函數 sin, cos, tan, asin, acos, atan

(atan y x) 就等同於(angle (make-rectangular x y))

(atan 1)   ;0.7853981633974483

(* 2 (asin 1))      ;pi

(* 4 (atan 1))      ;pi

指數 exp，對數 log，(expt a b) 是 a^b

;4的3次方
(expt 4 3)

;exp(2/3)
(exp (/ 2 3))

;1000的對數
(log 1000)

list

包含 cons, car, cdr, list, quote

list 的元素是 cons cell，每一個 cell 存放兩個 addresses，可用 cons 函數產生一個cons cell。

(cons 1 (cons 1 2)
;Value 5: (1 . 2)

cons 分別把 1 放在 car (Contents of the Address part of the Register)，2 放在 cdr (Contents of the Decrement part of the Register)。這個名稱來自於他們一開始被實現的硬體的內存記憶體的名稱，也代表 cons cell 就是記憶體的空間。cons 也是 construction 的簡稱。

(cons 3 (cons 1 2))
;Value 6: (3 1 . 2)

cons 可儲存不同的資料類型，也可以套嵌，也就是說，cons 可透過 address 處理所有資料

(cons #\a (cons 3 "hello"))
;Value 7: (#\a 3 . "hello")

(cons (cons 0 1) (cons 1 2))
;Value 8: ((0 . 1) 1 . 2)

其中 #\a 代表一個字元 a

cons cell 是透過 cdr 連接到下一個 cell 的開頭，'() 代表空的 list，下圖表示了 (1 2 3) 的記憶體資料結構

如果 ls 是一個 list，obj 是某種類型的資料，因為 list 是被遞迴定義的資料結構，所以(cons obj ls) 也會是一個 list

quote: '，以下這兩個都是空 list

'()
()

atom

非 cons cell 的資料結構就稱為 atom，number, char, string, '() 都是 atom

'() 既是 atom 也是 list

(cons "hi" "everybody")
;("hi" . "everybody")

(cons 0 ())
;(0)

(cons 1 (cons 10 100))
;(1 10 . 100)

(cons 1 (cons 10 (cons 100 ())))
;(1 10 100)

(cons 1 (cons 10 ()))
;(1 10)

(cons #\I (cons "saw" (cons 3 (cons "girls" ()))))
;(#\I "saw" 3 "girls")

(cons "Sum of" (cons (cons 1 (cons 2 (cons 3 (cons 4 ())))) (cons "is" (cons 10 ()))))
;("Sum of" (1 2 3 4) "is" 10)

quote

因為所有符號都會根據 scheme 的求值規則運算求值，由最內層的括號開始，依次向外面的括號求值，最外層的括號回傳的值，會成為 s-expression 的值。

quote 可阻止符號被求值，可將符號傳給程式，而不是求值後的結果。

(+ 2 3)會被求值為5，然而(quote (+ 2 3))則向程序返回(+ 2 3)本身。因為quote的使用頻率很高，他被簡寫為'。

'(+ 2 3) 就是(+ 2 3)
'+ 就是 +
'() 是空的 list，雖然 interpreter 會回傳 () 代表空 list，但還是要寫成 '()

scheme 有兩種不同類型的 operator，第一個是函數，函數會對所有參數求值，並計算回傳值。另一個operator 是特殊形式，特殊形式不會對所有參數求值。

quote, lambda, define, if , set! 這些都是特殊形式

car cdr 函數

car, cdr 可回傳一個 cons cell 的 car 或 cdr 部分

1 ]=> (car '(1 2 3 4))

;Value: 1

1 ]=> (cdr '(1 2 3 4))

;Value 2: (2 3 4)

1 ]=> (car '(0))

;Value: 0

1 ]=> (cdr '(0))

;Value: ()

1 ]=> (car '((1 2 3) (4 5 6)))

;Value 3: (1 2 3)

1 ]=> (cdr '(1 2 3 . 4))

;Value 4: (2 3 . 4)

1 ]=> (cdr (cons 3 (cons 2 (cons 1 '()))))

;Value 5: (2 1)

list 函數

可建構多個元素的 list，list 有任意個數的參數，會回傳這些參數產生的 list

1 ]=> (list)

;Value: ()

1 ]=> (list 1)

;Value 6: (1)

1 ]=> (list '(1 2) '(3 4))

;Value 7: ((1 2) (3 4))

1 ]=> (list 0)

;Value 8: (0)

1 ]=> (list 1 2)

;Value 9: (1 2)

Defining Functions

可用 define 綁定一個符號及一個值，可用 define 定義任何 global variables

首先在 ~/scheme 目錄產生一個 hello.scm 檔案，內容為

; Hello world as a variable
(define vhello "Hello world")     ;1

; Hello world as a function
(define fhello (lambda ()         ;2
     "Hello world"))

進入 scheme cli

(cd "~/Downloads/scheme")

(load "hello.scm")
;Loading "hello.scm"... done
;Value: fhello

vhello
;Value 6: "Hello world"

fhello
;Value 7: #[compound-procedure 7 fhello]

(fhello)
;Value 8: "Hello world"

定義有參數的函數

另外產生 farg.scm

; hello with name
(define hello
  (lambda (name)
    (string-append "Hello " name "!")))

; sum of three numbers
(define sum3
  (lambda (a b c)
    (+ a b c)))

載入後，呼叫函數，這些函數都需要參數

(load "farg.scm")
;Loading "farg.scm"... done
;Value: sum3

(hello "Lucy")
;Value 9: "Hello Lucy!"

(sum3 10 20 30)
;Value: 60

note: string-append 可處理任意數量的參數，回傳所有參數連接在一起的字串

除了用 lambda ，也可以用以下的形式定義函數，可讓程式碼更精簡

; hello with name
(define (hello name)
  (string-append "Hello " name "!"))

; sum of three numbers
(define (sum3 a b c)
  (+ a b c))

範例：計算丟出一個小球的水平位移距離

; definition of pi
(define pi (* 4 (atan 1.0)))

; 將 角度 轉換為 弧度
; degree -> radian
(define (radian deg)
  (* deg (/ pi 180.0)))

; free fall time
; 計算自由落體的時間
; 重力加速度 g 為 9.8 m/s^2
; 落地時瞬時竪直分速度為-Vy
; 自由落體的時間 2Vy = g*t
; t = 2Vy/g
(define (ff-time vy)
  (/ (* 2.0 vy) 9.8))

; horizontal distance
; 計算水平的位移距離 = vx(x 軸的速度) * t (自由落體時間)
(define (dx vx t)
  (* vx t))

; distance
; 利用 v 速度 及丟出去的角度，可計算水平位移的距離
(define (distance v ang)
  (dx
   (* v (cos (radian ang)))                     ; vx
   (ff-time (* v (sin (radian ang))))))         ; t


(distance 40 30)
;Value: 141.39190265868385

branching 分支 (條件判斷)

if

語法為

(if predicate then_value else_value)

true 為 #t

false 為 #f

note:

在 R5RS 規格中，false(#f) 跟 ('()) 是不同的物件，但在 MIT-scheme 是同一個物件。因為 R4RS 規格中，(#f) 跟 ('()) 是相同的物件。

從相容性的角度來看，不應該用 '() 判斷是否為 null，而是應該使用 null?

not 是相反

(null? '())
;Value: #t

(null? '(a b c))
;Value: #f

(not #f)
;Value: #t

ex: 等比級數總和

(1) r = 1, n 為項數
S = a0 * n
(2) r ≠ 1, n 為項數
S = a0 * (1 - r^n)/(1-r)

; 用 r 是否為 1 判斷 a0 要乘以 n 或是 (1 - r^n)/(1-r)
(define (sum-gp a0 r n)
  (* a0
     (if (= r 1)
       n
       (/ (- 1 (expt r n)) (- 1 r)) )))

(sum-gp 2 1 10)
;Value: 20

(sum-gp 2 2 10)
;Value: 2046

ex:

; 求絕對值
; positive? 判斷是否為 正數，用結果分別乘以 1 或 -1
(define (my-abs n)
  (* n
     (if (positive? n) 1 -1)))


; 求倒數，如參數為 0 就回傳 #f
; zero? 判斷是否為 0
; 不是 0 就除以 n
(define (inv n)
  (if (not (zero? n))
      (/ n) #f))


; 將一個整數轉化為ASCII碼字符的函數
; 整數可以被轉化為33-126號之間的ASCII碼。使用integer->char可以將整數轉化為字符。
; 如果給定的整數不能夠轉化為 char ，那麼就返回#f
(define (i2a n)
  (if (<= 33 n 126)
      (integer->char n) #f))

(i2a 100)
;Value: #\d

and or

scheme 的 and or 跟 C 語言不同，不回傳 #f #t，而是回傳給定的參數之一。

and 可傳入多個參數，如果某個參數為 #f，就回傳 #f，不對剩下的參數求值，如果所有參數都不是 #f，就回傳最後一個參數的值。

(and #f 0)
;Value: #f

(and 1 2 3)
;Value: 3

(and 1 2 3 #f)
;Value: #f

or 可傳入多個參數，他會回傳第一個不是 #f 的參數，不對剩下的參數求值，如果所有參數都是 #f，就回傳最後一個參數的值。

(or #f 0)
;Value: 0

(or 1 2 3)
;Value: 1

(or #f 1 2 3)
;Value: 1

(or #f #f #f)
;Value: #f

ex:

; 一個接受三個實數作為參數的函數，若參數皆為正數則返回它們的乘積。
(define (pro3and a b c)
  (and (positive? a)
       (positive? b)
       (positive? c)
       (* a b c)))

(pro3and 1 -1 2)
;Value: #f

(pro3and 1 4 2)
;Value: 8

; 一個接受三個實數作為參數的函數，若參數至少一個為負數則返回它們的乘積。
(define (pro3or a b c)
  (if (or (negative? a)
    (negative? b)
    (negative? c))
      (* a b c) #f))

(pro3or 1 -1 2)
;Value: -2

(pro3or 1 4 2)
;Value: #f

cond 表達式

雖然所有條件判斷都可以用 if 處理，但當條件中有多個可能性時，就需要嵌套的 if，這會使程式變得很複雜，這種情況可改用 cond

cond 中，predicates_i是按照從上到下的順序求值，而當predicates_i為真時，clause_i會被求值並返回。i 以後的predicates和clauses不會被求值。如果所有的predicates_i都是假的話，則返回cluase_else。在一個子句中，你可以寫數條S-表達式，而clause的值是最後一條S-表達式。

(cond
  (predicate_1 clauses_1)
  (predicate_2 clauses_2)
    ......
  (predicate_n clauses_n)
  (else        clauses_else))

ex: 收費機制

如果 age ≤ 3 或者 age ≥ 65 則 免費；
如果 介於 4 ≤ age ≤ 6 則 0.5美元；
如果 介於 7 ≤ age ≤ 12 則 1.0美元；
如果 介於 13 ≤ age ≤ 15 則 1.5美元；
如果 介於 16 ≤ age ≤ 18 則 1.8美元；
其它 則 2.0美元；

則收費的計算函數為

(define (fee age)
  (cond
   ((or (<= age 3) (>= age 65)) 0)
   ((<= 4 age 6) 0.5)
   ((<= 7 age 12) 1.0)
   ((<= 13 age 15) 1.5)
   ((<= 16 age 18) 1.8)
   (else 2.0)))

(fee 65)
;Value: 0

(fee 10)
;Value: 1

ex: 成績等第計算規則：(1) A 如果 score ≥ 80 (2) B 如果 60 ≤ score ≤ 79 (3) C 如果 40 ≤ score ≤ 59 (4) D 如果 score < 40

(define (score n)
  (cond
   ((>= n 80) 'A)
   ((<= 60 n 79) 'B)
   ((<= 40 n 59) 'C)
   (else 'D)))

用在判斷的函數

這些函數都是以 ? 結尾

eq? eqv? equal?

eq? 是比較兩個參數的位址，相同就回傳 #t。

注意不能用 eq? 比較數字，要以 eqv? 比較數字。

(define str "hello")
;Value: str

(eq? str str)
;Value: #t

; 雖然都是 "hello"，但儲存在不同的位址，所以為 #f
(eq? "hello" "hello")
;Value: #f

(eq? 1 1)
;Value: #t

(eq? 1.0 1.0)
;Value: #f

eqv? 會比較儲存在兩個參數的資料型別與值，如果資料型別跟值都一樣，就回傳 #t

(eqv? 1.0 1.0)
;Value: #t

; 資料型別不同
(eqv? 1 1.0)
;Value: #f

; 不能用來比較 list
(eqv? (list 1 2 3) (list 1 2 3))
;Value: #f

(eqv? "hello" "hello")
;Value: #f

(eqv? (lambda(x) x) (lambda (x) x))
;Value: #f

equal? 用來比較 list, 字串的序列

(equal? (list 1 2 3) (list 1 2 3))
;Value: #t

(equal? "hello" "hello")
;Value: #t

用來檢查資料型別的函數

這些函數都只有一個參數。

pair? 如果對象為序對則返回#t；
list? 如果對象是一個表則返回#t。要小心的是空表’()是一個表但是不是一個序對。
null? 如果對象是空表’()的話就返回#t。
symbol? 如果對象是一個符號則返回#t。
char? 如果對象是一個字符則返回#t。
string? 如果對象是一個字符串則返回#t。
number? 如果對象是一個數字則返回#t。
complex? 如果對象是一個複數則返回#t。
real? 如果對象是一個實數則返回#t。
rational? 如果對象是一個有理數則返回#t。
integer? 如果對象是一個整數則返回#t。
exact? 如果對象不是一個浮點數的話則返回#t。
inexact? 如果對象是一個浮點數的話則返回#t。

用在比較數字的函數

=  >  <  <=  >=
odd?  even?  postitive?  negative?  zero?

(= 1 1 1.0)
;Value: #t

(< 1 2 3)
;Value: #t
(< 1)
;Value: #t
(<)
;Value: #t

(= 2 2 2)
;Value: #t

(< 2 3 3.1)
;Value: #t

(> 4 1 -0.2)
;Value: #t

(<= 1 1 1.1)
;Value: #t

(>= 2 1 1.0)
;Value: #t

(< 3 4 3.9)
;Value: #f

用來比較字元的函數

char=?  char<?  char>?  char<=?  char>=?

用來比較字串的函數

string=?  string-ci=?

References

mit-scheme user doc

Yet Another Scheme Tutorial 中文版

Yet Another Scheme Tutorial

2019/11/18

Scheme Tutorial 1