Skip to content

Latest commit

 

History

History
200 lines (135 loc) · 7.72 KB

期中.md

File metadata and controls

200 lines (135 loc) · 7.72 KB

前言

  • rui314 的 minilisp 專案，是一個九百多行的 LISP 解譯器，包含垃圾蒐集 gc，去掉 gc 的版本只有 668 行，除了 cons, car, cdr, print 之外，函式庫完全自己從頭開始寫，所以打算以此翻譯做為報告，從翻譯的過程中深入了解這個經過半個世紀卻還在使用的語言

MiniLisp

MiniLisp 是個用 1000 行 C 語言寫的 Lisp 解釋器，其支持：

  • 整數、符號、構造函數
  • 全域變數
  • 局部變數
  • 閉包:閉包可以用來在一個函式與一組「私有」變數之間建立關聯關係。在給定函式被多次呼叫的過程中，這些私有變數能夠保持其永續性。變數的作用域僅限於包含它們的函式，因此無法從其它程式碼部分進行存取。不過，變數的生存期是可以很長，在一次函式呼叫期間所建立所生成的值在下次函式呼叫時仍然存在。
  • if 條件句
  • 原始函數，例如 +、=、< 或 list
  • 使用者自訂函數
  • 巨集系統
  • 垃圾回收

總共1000行的C寫成，作者沒有因為大小而犧牲可讀性，相反的作者認為有大量註解讓使用者好理解

編譯器

$ make

MiniLisp 已經在 Linux x86/x86-64 和 64 位 macOS 上進行了測試。代碼與體系結構無關，因此應該能夠在其他類 Unix 操作系統上編譯和運行。

測試

MiniLisp 帶有一個全面的測試套件。為了運行測試，給出 “test” 參數。 $ make test

語言特徵

MiniLisp 是一個傳統的 Lisp 解釋器。它一次從標準輸入中讀取一個表達式，對其求值，然後打印出表達式的返回值。這是有效輸入的示例。

(+ 1 2)

上述結果是 "3".

定數

MiniLisp 支援整數定數, (), t, 符號, 串列定數.

  • Integer literals are positive or negative integers.
  • () 是唯一假值. 也代表空值.
  • t是對自身求值的預定變義量。這是表示真值的首選方式，而任何非()值都被認為是真值。
  • 符號是有獨立名字的物件. 他們通常代表識別字，由於 MiniLisp 沒有字串類別，所以符號有時候被當字串使用
  • 串列定數是構造函數. 它的cdr元素會是ˋ()ˋ，或是一個點狀列表沒有任何ˋ()ˋ值，一個點狀列表會這樣表示 (a . b)

運算子表

cons 接受兩個參數並得出新的串列定數，使第一個參數為car，第二個參數為 cdr。

(cons 'a 'b)   ; -> (a . b)
(cons 'a '(b)) ; -> (a b)

car and cdr are accessors for cons cells. car returns the car, and cdr returns the cdr.

(car '(a . b)) ; -> a
(cdr '(a . b)) ; -> b

setcar 改變一個 cons cell. setcar 接受兩個參數並假設第一個參數為 cons cell. It sets the second argument's value to the cons cell's car.

(define cell (cons 'a 'b))
cell  ; -> (a . b)
(setcar cell 'x)
cell  ; -> (x . b)

運算子

+操作域裡的總和 (+ 1) ; -> 1 (+ 1 2) ; -> 3 (+ 1 2 3) ; -> 6

- 如果操作域裡只有一個參數則否定操作域裡的參數 (- 3) ; -> -3 (- -5) ; -> 5

如果操作域裡不只一個參數，則由第一個參數減去後面的參數

(- 5 2)    ; -> 3
(- 5 2 7)  ; -> -4

=接受兩個參數，如果兩者是相同的整數則輸出 t ，不是則輸出()。

(= 11 11)  ; -> t
(= 11 6)   ; -> ()

< 接受兩個參數，如果第一個參數小於第二個參數，則輸出 t 。

(< 2 3)    ; -> t
(< 3 3)    ; -> ()
(< 4 3)    ; -> ()

條件句

(if cond then else) 是語言中唯一的條件。首先執行cond。如果結果為真值，執行then不然就是執行else 。

迴圈

(while cond expr ...) 執行 expr ... 直到 cond 得出為(). 這是 MiniLisp 唯一支持的循環

如果您熟悉 Scheme，您可能想知道是否可以在 MiniLisp 中通過尾呼叫編寫循環。答案是不。尾呼叫會消耗 MiniLisp 中的堆疊空間，因此將會因為內存耗盡錯誤而失敗。

Equivalence test operators

eq 執行兩格參數如果兩個參數一樣則輸出 t 。 而 eq比較的是地址，用它對symbols(符號)快速地比較，測試兩個cons cells是否物理上是同一個對象。

Output operators

println 將指定對象輸出.

(println 3)               ; prints "3"
(println '(hello world))  ; prints "(hello world)"

Definitions

MiniLisp s支持變量跟函數 可以用 define來定義

(define a (+ 1 2))
(+ a a)   ; -> 6

定義函數有兩種方式。一種方法是使用特殊形式 lambda。(lambda (args ...) expr ... 輸出得函數可以使用ˊdefineˊ指定變數

(define double (lambda (x) (+ x x)))
(double 6)                ; -> 12
((lambda (x) (+ x x)) 6)  ; 沒有指定也是同樣的結果

另一個則是 defun. (defun fn (args ...) expr ...) 比起(define fn (lambda (args ...) expr ...)比較短

;; Define "double" using defun
(defun double (x) (+ x x))

(defun fn (expr . rest) rest)
(fn 1)     ; -> ()
(fn 1 2 3) ; -> (2 3)

Variables are lexically scoped and have indefinite extent. References to "outer" variables remain valid even after the function that created the variables returns.

;; A countup function. We use lambda to introduce local variables because we
;; do not have "let" and the like.
(define counter
  ((lambda (count)
     (lambda ()
       (setq count (+ count 1))
       count))
   0))

(counter)  ; -> 1
(counter)  ; -> 2

;; This will not return 12345 but 3. Variable "count" in counter function
;; is resolved based on its lexical context rather than dynamic context.
((lambda (count) (counter)) 12345)  ; -> 3

setq 為現有變量設置新值。如果未定義變量，則出現錯誤。

(define val (+ 3 5))
(setq val (+ val 1))  ; increment "val"

巨集

巨集與函數的功能相同，但在編譯時，編譯時會以巨集取代原來的敘述，而函數則是一個跳躍敘述；在程式執行期間，由於巨集已經展開為它所代表的敘述，程式會一行一行執行下去，而碰到函數則是跳到函數定義的副程式去執行。 (defmacro macro-name (args ...) body ...) 下面是定義巨集的示範

(defmacro unless (condition expr)
  (list 'if condition () expr))

上述的 defmacro 定義一個新巨集 unless. unless 是expr新的執行條件除非條件是真值。函數不能做同樣的事因為所有參數會在控件傳給函數前被執行

(define x 0)
(unless (= x 0) '(x is not 0))  ; -> ()
(unless (= x 1) '(x is not 1))  ; -> (x is not 1)

macroexpand 是一個方便的特殊形式看到巨集的擴充

(macroexpand (unless (= x 1) '(x is not 1)))
;; -> (if (= x 1) () (quote (x is not 1)))

gensym 建立一個新的符號 gensym經常在Lisp 巨集中用於代碼生成，當巨集需要創建新標識符時，這些標識符不會與現有標識符發生衝突。

(gensym)   ; -> a new symbol

注釋

與傳統的 Lisp 語法一樣， ; （分號）開始單行註釋。持續到行尾。

參考資料