2019/11/25

Scheme Tutorial 2

local variables

用 let 定義 local variable,body由任意多個S-表達式構成,變數的Scopebody,只在body 中有效。

(let binds body)

;binds的格式
[binds] → ((p1 v1) (p2 v2) ...)

ex:

(let ((i 1) (j 2))
  (+ i j))
;Value: 3

let 可以嵌套使用

(let ((i 1))
  (let ((j (+ i 2)))
    (* i j)))
;Value: 3

因變數的作用域僅在body中,下列代碼會產生錯誤,因為在變量j的作用域中沒有變數i的定義。

(let ((i 1) (j (+ i 2)))
  (* i j))
;Error

let*表達式可以用於引用定義在同一個綁定中的變量。實際上,let*只是嵌套的let表達式的 syntax sugar 而已。

(let* ((i 1) (j (+ i 2)))
  (* i j))
;Value: 3

ex: 計算一元二次方程式的解。它需要三個參數代表係數:abcax^2 + bx + c = 0),計算結果傳回一個存放答案的實數表。

(define (quadric-equation a b c)
  (if (zero? a)
      'error                                      ; 1 如果二次項係數 a為0,函數返回'error
      (let ((d (- (* b b) (* 4 a c))))            ; 2 如果a ≠ 0,則將變數d與判別式(b^2 - 4ac)的值綁定
        (if (negative? d)
            '()                                      ; 3 如果d為負數,則返回'()
            (let ((e (/ b a -2)))                    ; 4 如果d不為負數,則將變數 e 與-b/2a 綁定
                (if (zero? d)
                    (list e)                            ; 5 如果 d為0,則返回一個包含e的表
                    (let ((f (/ (sqrt d) a 2)))         ; 6 如果 d是正數,則將變數 f 與√(d/2a)綁定,並返回由(+ e f)和(- e f)> 構成的表
                    (list (+ e f) (- e f)))))))))

(quadric-equation 3 5 2)  ; solution of 3x^2+5x+2=0
;Value 12: (-2/3 -1)

let expression 實際上只是 lambda expression 的 syntax sugar

(let ((p1 v1) (p2 v2) ...) exp1 exp2 ...)
;⇒
((lambda (p1 p2 ...)
    exp1 exp2 ...) v1 v2)

因為 lambda 用來定義函數,同時定義了該變數的作用範圍

ex: 用一個初始速度v和與水平面所成夾角a來計算飛行距離

(define (throw v a)
  (let ((r (/ (* 4 a (atan 1.0)) 180)))  ; (define pi (* 4 (atan 1.0)))  r 可將 degree 轉換為 radian
    (/ (* 2 v v (cos r) (sin r)) 9.8)))  ; 初始水平、竪直分速度分別表示為:v*cos(theta1)和v*sin(theta1)  落地時瞬時竪直分速度為-Vy  自由落體時間 2Vy = g*t


(throw 40 30)
;Value: 141.39190265868385

在 scheme 中,變數的作用範圍由 source code 決定,這稱為 lexical closure

Looping 迴圈

在 scheme 通常用遞迴來處理 looping

Recursion 遞迴

在函數定義中呼叫函數本身,就稱為遞迴函數。

ex: 計算階乘

(define (fact n)
  (if (= n 1)
      1
      (* n (fact (- n 1)))))

過程如下

(fact 5)
⇒ 5 * (fact 4)
⇒ 5 * 4 * (fact 3)
⇒ 5 * 4 * 3 * (fact 2)
⇒ 5 * 4 * 3 * 2 * (fact 1)
⇒ 5 * 4 * 3 * 2 * 1
⇒ 5 * 4 * 3 * 2
⇒ 5 * 4 * 6
⇒ 5 * 24
⇒ 120

list 可以用遞迴的方式定義,例如讓 list 裡面所有元素都乘以2 可這樣寫

(define (list*2 ls)
  (if (null? ls)
      '()
      (cons (* 2 (car ls))
           (list*2 (cdr ls)))))

(list*2 (list 1 2 3 4 5))
;Value 8: (2 4 6 8 10)

ex:

; 1 計算 list 內元素的個數
(define (my-length ls)
  (if (null? ls)
      0
      (+ 1 (my-length (cdr ls)))))

; 2 加總 list 內所有元素
(define (my-sum ls)
  (if (null? ls)
      0
      (+ (car ls) (my-sum (cdr ls)))))

; 3 從 ls 中刪除 x 後得到的表
(define (remove x ls)
  (if (null? ls)
      '()
      (let ((h (car ls)))
        ((if (eqv? x h)
            (lambda (y) y)
            (lambda (y) (cons h y)))
         (remove x (cdr ls))))))

; 4 傳回 x 在 ls 中首次出現的位置。索引從0開始。如果 x 不在ls中,函數傳回 #f
(define (position x ls)
  (position-aux x ls 0))

(define (position-aux x ls i)
  (cond
   ((null? ls) #f)
   ((eqv? x (car ls)) i)
   (else (position-aux x (cdr ls) (1+ i)))))

尾遞迴

普通的遞迴並不高效因為它既浪費儲存空間又具有呼叫函數的開銷。尾遞迴函數包含了計算結果,當計算結束時直接將其回傳。另外由於Scheme規範中要求尾遞迴呼叫轉化為循環,因此尾遞迴呼叫就不存在呼叫函數的開銷。

ex: 階乘的尾遞迴版本

(define (fact-tail n)
  (fact-rec n n))

(define (fact-rec n p)
  (if (= n 1)
      p
      (let ((m (- n 1)))
  (fact-rec m (* p m)))))

計算過程如下

(fact-tail 5)
⇒ (fact-rec 5 5)
⇒ (fact-rec 4 20)
⇒ (fact-rec 3 60)
⇒ (fact-rec 2 120)
⇒ (fact-rec 1 120)
⇒ 120

Scheme將尾遞迴轉化為循環,Scheme就無需提供循環的語法來實現 looping。

ex:

; 1 翻轉 list 元素的順序
(define (my-reverse ls)
  (my-reverse-rec ls ()))

(define (my-reverse-rec ls0 ls1)
  (if (null? ls0)
      ls1
      (my-reverse-rec (cdr ls0) (cons (car ls0) ls1))))

;-------------------
; 2 加總 list
(define (my-sum-tail ls)
  (my-sum-rec ls 0))

(define (my-sum-rec ls n)
  (if (null? ls)
      n
      (my-sum-rec (cdr ls) (+ n (car ls)))))

;--------------------
; 3 將一個代表正整數的字串轉化為對應整數。 例如 "1232" 轉換為 1232,不檢查非法的字元
; 字元到整數的轉化是通過將字元 #\0 …… #\9 的ASCII減去48,可以使用函數char->integer來獲得字符的ASCII碼。
; 函數 string->list 可以將字串轉化為由字元構成的 list。
(define (my-string->integer str)
  (char2int (string->list str) 0))

(define (char2int ls n)
  (if (null? ls)
      n
      (char2int (cdr ls)
    (+ (- (char->integer (car ls)) 48)
       (* n 10)))))

named let 有命名的 let

named let 可用來處理 looping

ex: 用 named let 實作階乘

(define (fact-let n)
  (let loop((n1 n) (p n))     ; 1  將參數 n1 與 p 都初始化為 n
    (if (= n1 1)
      p
      (let ((m (- n1 1)))
      (loop m (* p m))))))    ; 2  每一次循環時,n1 會減 1, p 會乘以 (n1-1)

ex:

; 1  從 ls 中刪除 x 後得到的表
(define (remove x ls)
  (let loop( (ls0 ls) (ls1 ()) )
    (if (null? ls0)
      (reverse ls1)
      (loop
        (cdr ls0)
        (if (eqv? x (car ls0))
            ls1
            (cons (car ls0) ls1) )))))

; 2  傳回 x 在 ls 中首次出現的位置。索引從0開始。如果 x 不在ls中,函數傳回 #f
(define (position x ls)
  (let loop((ls0 ls) (i 0))
    (cond
     ((null? ls0) #f)
     ((eqv? x (car ls0)) i)
     (else (loop (cdr ls0) (1+ i))))))

; 3  翻轉 list 元素的順序
(define (my-reverse-let ls)
  (let loop( (ls0 ls) (ls1 ()) )
    (if (null? ls0)
      ls1
      (loop (cdr ls0) (cons (car ls0) ls1)))))

; 4  加總 list
(define (my-sum-let ls)
  (let loop((ls0 ls) (n 0))
    (if (null? ls0)
  n
  (loop (cdr ls0) (+ (car ls0) n)))))

; 5  將一個代表正整數的字串轉化為對應整數
(define (my-string->integer-let str)
  (let loop((ls0 (string->list str)) (n 0))
    (if (null? ls0)
  n
  (loop (cdr ls0)
        (+ (- (char->integer (car ls0)) 48)
     (* n 10))))))

; 6  range函數:傳回一個從0到n的表(但不包含n)
(define (range n)
  (let loop((i 0) (ls1 ()))
    (if (= i n)
      (reverse ls1)
      (loop (1+ i) (cons i ls1)))))

letrec

letrec 類似let,但允許一個名字遞迴呼叫自己。通常用來定義複雜的遞迴函數 recursive local functions。

; 階乘的 letrec 版本
(define (fact-letrec n)
  (letrec ((iter (lambda (n1 p)
       (if (= n1 1)
           p
           (let ((m (- n1 1)))  (iter m (* p m))) ))))     ; iter 可在定義中引用自己
       (iter n n) ))

letrec 的語法,前面是變數定義區塊,<body> 是執行區塊

(letrec ((<variable> <init>) ...) <body>) 

letrec最常見的用法就是用於綁定函數對象,讓變數定義區塊V裡面定義的所有變量可以在執行時相互引用,不受位置前後的限制

(letrec ((x (lambda () (+ y y)))
         (y 100))
    (+ (x) y))

; 執行(+ (x) y)時,雖然 y在x之後才綁定的,函數對象x可以讀取y對象的值

(define x (lambda () (+ y y)))

(define y 100)

(+ (x) y)

ex:

; 1  翻轉 list 元素的順序
(define (my-reverse-letrec ls)
  (letrec ((iter (lambda (ls0 ls1)
       (if (null? ls0)
           ls1
           (iter (cdr ls0) (cons (car ls0) ls1))))))
    (iter ls ())))

; 2  加總 list
(define (my-sum-letrec ls)
  (letrec ((iter (lambda (ls0 n)
       (if (null? ls0)
           n
           (iter (cdr ls0) (+ (car ls0) n))))))
    (iter ls 0)))

; 3  將一個代表正整數的字串轉化為對應整數。
(define (my-string->integer-letrec str)
  (letrec ((iter (lambda (ls0 n)
       (if (null? ls0)
           n
           (iter (cdr ls0)
           (+ (- (char->integer (car ls0)) 48)
        (* n 10)))))))
    (iter (string->list str) 0)))

do

不常用,但 do 也可以處理 looping,語法如下:

(do binds (predicate value)
    body)

變數在 binds 部份被綁定,如果 predicate 為 #t,則函數由循環中 escape,並回傳 value,否則繼續 looping

binds 的格式如下,變量p1p2,…被分別初始化為i1i2,…並在循環後分別被更新為u1u2,…。

[binds] → ((p1 i1 u1) (p2 i2 u2) ... )

ex:

; 變數n1和p分別被初始化為n和n,在每次循環後,分別被 減去1 和 乘以(n1 - 1)。當n1變為1時,函數返回p。
(define (fact-do n)
  (do ((n1 n (- n1 1)) (p n (* p (- n1 1)))) ((= n1 1) p)))
; 1  翻轉 list 元素的順序
(define (my-reverse-do ls)
  (do ((ls0 ls (cdr ls0))  (ls1 () (cons (car ls0) ls1)))
      ((null? ls0) ls1)))

; 2  加總 list
(define (my-sum-do ls)
  (do ((ls0 ls (cdr ls0))  (n 0 (+ n (car ls0))))
      ((null? ls0) n)))

; 3  將一個代表正整數的字串轉化為對應整數。
(define (my-string->integer-do str)
  (do ((ls0 (string->list str) (cdr ls0))
       (n 0 (+ (- (char->integer (car ls0)) 48)
         (* n 10))))
      ((null? ls0) n)))

通常來說,named let 用於簡單的循環,而letrec則是用來寫複雜的局部遞歸函數。

高階函數 higher order function

高階函數 higher order function 是一種以函數為參數的函數,用於 mapping, filtering, folding, sorting list。高階函數增加了程式的模組特性。例如使用高階函數實作 sorting,可將排序條件與過程分離。

例如 sort 有兩個參數:一個是待排序的 list,一個是 Ordering function

(sort '(7883 9099 6729 2828 7754 4179 5340 2644 2958 2239) <)
;Value 12: (2239 2644 2828 2958 4179 5340 6729 7754 7883 9099)

; 改以數字末兩位排序
(sort '(7883 9099 6729 2828 7754 4179 5340 2644 2958 2239)
      (lambda (x y) (< (modulo x 100) (modulo y 100))))
;Value 13: (2828 6729 2239 5340 2644 7754 2958 4179 7883 9099)

映射 Mapping

map

procedure是個與某個過程或lambda表達式相綁定的符號。作為參數的表的個數,視procedure需要的參數而定。

(map procedure list1 list2 ...)

ex:

; Adding each item of '(1 2 3) and '(4 5 6).
(map + '(1 2 3) '(4 5 6))
;Value 14: (5 7 9)

; Squaring each item of '(1 2 3)
(map (lambda (x) (* x x)) '(1 2 3))
;Value 15: (1 4 9)
for-each

for-each的格式與map一致。但for-each並不返回一個具體的值,只是用於副作用。

ex:

(define sum 0)

(for-each (lambda (x) (set! sum (+ sum x))) '(1 2 3 4))

sum
;Value: 10

ex: 將 list 裡所有元素 *2

(define (double list)
    (map (lambda (x) (* x 2)) list) )

(double '(1 2 3))
;Value 16: (2 4 6)

(double (list 1 2 3))
;Value 17: (2 4 6)

ex: 將兩個表中對應位置元素相減的函數

(define (minus list1 list2)
    (map - list1 list2) )

(minus '(1 2 3) '(4 5 6))
;Value 18: (-3 -3 -3)

filtering

R5RS 沒有定義 filtering 函數,但 scheme 提供了 keep-matching-items 與 delete-matching-item

(keep-matching-items '(1 2 -3 -4 5) positive?)
;Value 19: (1 2 5)

ex:

; 過濾出偶數
(keep-matching-items '(1 2 -3 -4 5) (lambda (x) (= (modulo x 2) 0)))
;Value 20: (2 -4)

; 濾出 不滿足10 ≤ x ≤ 100 的數
(keep-matching-items '(1 10 20 50 100 150) (lambda (x) (not (<= 10 x 100))))
;Value 23: (1 150)

Folding

R5RS 沒有定義 folding 函數,但 scheme 提供了 reduce

(reduce + 0 '(1 2 3 4))                 ;⇒  10
(reduce + 0 '(1 2))                     ;⇒  3
(reduce + 0 '(1))                       ;⇒  1
(reduce + 0 '())                        ;⇒  0
(reduce + 0 '(foo))                     ;⇒  foo
(reduce list '() '(1 2 3 4))            ;⇒  (4 (3 (2 1)))

ex: 撰寫將表中所有元素平方的函數,然後求取它們的和,最後求和的平方根

(define (fun list)
    (sqrt (reduce + 0 (map (lambda (x) (* x x)) list))))

(fun '(3 4))
;Value: 5

Sorting

R5RS中沒有定義排序函數,但 scheme 提供了 sort (merge-sort 實作) 與 quick-sort

(sort '(3 5 1 4 -1) <)
;Value 26: (-1 1 3 4 5)

ex:

; 以sin(x)的大小升序排序
(define (sort-sin ls)
  (sort ls (lambda (x y) (< (sin x) (sin y)))))

; 以list長度降序排序
(define (sort-length ls)
  (sort ls (lambda (x y) (> (length x) (length y)))))

apply

將一個過程應用於一個表(將表展開,作為過程的參數),函數可有多個參數,但首參數和末參數分別應該是一個過程和一個表

(apply max '(1 3 2))      ;⇒   3
(apply + 1 2 '(3 4 5))    ;⇒  15
(apply - 100 '(5 12 17))  ;⇒  66

ex: 撰寫將表中所有元素平方的函數,然後求取它們的和,最後求和的平方根

(define (sqrt-sum-sq-a ls)
  (sqrt (apply + (map (lambda (x) (* x x)) ls))))

編寫高階函數

member-if, member

member-if, member

member-if函數使用一個謂詞和一個表作為參數,返回一個子表,該子表的car部分即是原列表中首個滿足該謂詞的元素。

(define (member-if proc ls)
  (cond
   ((null? ls) #f)
   ((proc (car ls)) ls)
   (else (member-if proc (cdr ls)))))

(member-if positive? '(0 -1 -2 3 5 -7))
;⇒  (3 5 -7)

member函數檢查特定元素是否在表中,使用三個參數,其一為用於比較的函數,其二為特定項,其三為待查找表。

(define (member proc obj ls)
  (cond
   ((null? ls) #f)
   ((proc obj (car ls)) ls)
   (else (member proc obj (cdr ls)))))

(member string=? "hello" '("hi" "guys" "bye" "hello" "see you"))
;⇒  ("hello" "see you")

References

mit-scheme user doc

Yet Another Scheme Tutorial 中文版

Yet Another Scheme Tutorial

2019/11/18

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+bia稱為實部,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. 計算 (1+39) * (53-45)

    (* (+ 1 39) (- 53 45))      ;320
  2. 計算 (1020 / 39) + (45 * 2)

    (+ (/ 1020 39) (* 45 2))  ;1510/13
  3. 求和:39, 48, 72, 23, 91

    (+ 39 48 72 23 91)            ;273
  4. 求平均值: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 以後的predicatesclauses不會被求值。如果所有的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/11

LISP

Lisp 就是 LISt Processing,誕生於 1958 年 John McCarthy 的設計,是目前年紀第二老的高階程式語言,最老的 Fortran 比它早一年,擅長資料處理。目前 LISP 已經衍生出許多方言,但最通用的是 Common LispScheme (目前比較常用的 scheme compiler 是 chicken)。現今流行的高階程式語言,都有 Lisp 功能的影子,在 1958 年 John McCarthy 設計的 Lisp,其提出的設計概念,普遍用在許多高階程式語言中。

Lisp 一開始只是數學理論,跟 Fortran 不同,Fortran 一開始就是以程式語言的概念設計出來的,也就是說,Fortran 是適應了計算機,刻意設計出來的程式語言。

Lisp 一開始就提出了一些概念,其中有很多概念,已經是大家習慣且接受的概念

  1. 條件結構 if-then-else
  2. 遞迴函數
  3. Functional language,函數也是一種資料型別,可當作參數傳入另一個function,function 也可以回傳 function
  4. 動態資料型別,Lisp 的變數都是 pointer,指向的值有資料型別的分別,但變數本身,只是儲存 pointer
  5. 自動記憶體管理、垃圾回收機制
  6. expression 與 statement,Lisp 程式是許多 expression 的集合,但 fortran 是由 expression 以及 statement 組成,expression 是用來運算,statement 用來控制程式執行的順序
  7. Symbol y 資料型別,這是一種指向 hash 的 string,比較 symbol 時,就只要比較 pointer 是不是一樣就好了,不用做字串比較
  8. 程式用符號跟常數組成 tree structure
  9. REPL: Read-Eval-Print Loop

LISP 並不是一個單純的程式語言,而是一個程式語言家族,一開始發展的 LISP 現在已經不存在了,而是衍生為其他不同的方言,繼續存活下去,這些方言的共通點只有語法,也就是 S expression,s-expression 既可當作程式,也可以當作資料。

scheme 跟 common lisp 的差異是, scheme 比較簡潔,這表示在不同 scheme implementation 之間,會遇到不相容的問題,這不完全是缺點,學習時,會比較瞭解 LISP 的核心概念。Common Lisp 則是以實用為主,目前已經有一個龐大的生態系統,如果要運用在實際的商業環境,要選擇用 Common Lisp,選用 Common Lisp 能夠比較容易切換到不同的實作上。

一般建議是先了解 scheme 語法,入門後,再轉換到 Common Lisp

References

為什麼Lisp語言如此先進

Chicken

ANSI Common LISP 中文

2019/11/04

BPMN: Business Process Model and Notation

BPM(Business Process Modeling) 是將企業運作流程建模,標準化,讓系統整合的層次由 IT 進入商業領域。關於 BPM 的標準很多:

  • OASIS 的WS-BPEL(Business Process Execution Language for Web Services)
  • BPMI協會的BPML(Business Process Modeling Language)和BPMN(Business Process Modeling Notation)
  • W3C的WS-CDL(Web Services Choreography Description Language)
  • WfMC協會的XPDL(XML Process Definition Language)
  • OMG的MDA(Model-Driven Architecture)

業務流程模型和標記法(BPMN: Business Process Model and Notation)是以圖形及符號描述業務流程的示意圖。最初由 BPMI, Business Process Management Initiative 發展,後來與 OMG 合併,2011/1 發布 BPMN 2.0 版。

BPMN 跟 UML 的 Activity Diagram 及傳統的 Flow Chart 很接近,可將特定的業務流程圖形化,讓大家能快速了解複雜的業務流程。BPMN 有圖形化標記規範,同時可轉換為 BPEL (Business Process Execution Language),這是一種描述業務流程的 XML。

BPMN

BPMN 僅限於支援業務流程方面的 Modeling,以下這些項目,不屬於 BPMN 的範圍:

  • 組織架構
  • 職能分析
  • 資料建模
基本要素
  1. Flow Object
    Events, Activities, Gateways
  2. Connecting Object
    Sequence Flow, Message Flow, Association
  3. Swimlane Pool, Lane
  4. Artifact Data Object, Group, Annotation

NPMN 允許在 BPD 中建立自訂的 Flow Object 及 Artifact。

Flow Object
  1. Events
    事件以圓環表示,代表發生的事件,圓環內可加上該事件的圖示,例如信封代表訊息,時鐘代表時間。

    事件也分為 catching / throwing 兩種,catching 是捕抓輸入的事件,因而開始一個事件處理流程,throwing 是流程結束,往外丟出結束事件。

    • Start Event: 流程的觸發,是空心的圓環
    • Intermediate Event: 在事件開始與結束之間,雙線圓環,可以是 catching/throwing event
    • End Event: 流程結束,是實心圓環,只能 throwing
  2. Activity
    以圓角矩形表示,描述要做的工作內容。

    • Task: task 表示一個工作單元,不能被分解為深層次的業務流程細節
    • Sub-Process: 用來隱藏/顯示深層業務流程細節,隱藏時,用 + 標記這是子流程

    • Transaction: 這是一種子流程,裡面包含的所有活動,都必須要全部完成,結束後,才算是完成工作,只要有失敗,就必須要 rollback。用雙線環繞標記。

  3. Gateway
    用菱形表示,基於描述的條件,決定路徑的分流或合併

Connecting Object

Flow Object 是以 Connecting Object 互相連接,Connecting Object 有三種:

  1. Sequence Flow
    實心線及箭頭表示,描述活動進行的順序,可在開始端帶有符號,增加一個小菱形,變成 conditional flow,或是以對角斜線,標記發自活動,帶有條件的 default flow

    由上而下分別是 Normal Flow, Conditional Flow, Default Flow

  2. Message Flow
    以空心圓圈開始,最後是空心的箭頭,用來表示有訊息跨過 pool 邊界,Message Flow 不能用在同一個 Pool 裡面連接活動或事件

  3. Association
    用點狀的線表示的箭頭,用來建立 artifact 到 flow object 的關係,可使用空心箭頭,表示方向性,指向 artifact 表示結果,源自 artifact 表示輸入,兩者都有,表示有讀取跟更新。

Swimlane

在視圖上用來分類的機制,有兩種類型

  1. Pool
    表示流程中的主要參與者,通常用來區分不同的組織,一個 Pool 可有多個 Lane,當 Pool 展開是大矩形,裡面有流程細節,收合後是一個空的矩形。

  2. Lane
    依照工作職能,或是角色分類,繪製成矩形,裡面包含 Flow Object, Connecting Object, Artifact

Artifact

在 Pool 裡面,增加更多資訊,增加視圖可讀性。預設 Artifact 有三種

  1. Data Object
    在活動中需要或產生的資料

  2. Group
    虛線園角矩形,可將不同的活動分組

  3. Annotation
    註解,增加可讀性

Example

以下是一個議題討論流程的實例,花7天進行 email 討論,結束的1天前,會發送 deadline 警告,另外在過程中,會協調 conf call 時間進行討論。討論後,會評估此次討論過程的有效性,最終決定討論的結果是否有效。

References

BUSINESS PROCESS MODEL AND NOTATION SPECIFICATION VERSION 2.0 spec

BPM提升營運的智慧

業務流程模型和標記法

BPMN 2.0 by Example: non-normative OMG document with BPMN 2.0 examples)

BPMN符號與BPMN的關係

BPMN規範中的三種視圖

業務流程建模標注(BPMN)詳細介紹

BPMN