Jserv's blog

以 C 語言模擬 Lisp/Scheme 語法

傍晚與一位六月份見過面的朋友通訊，我們聊到機器人設計，他問說為何不考慮用 Lisp 來建構系統平台，問題一出，讓我這個「慣 C 魔人」想到新題目：

「能否用 C 語言模擬 Lisp 語法？」

筆者選定 Scheme 作為主要的模擬對象，發展於 1975 年的 MIT 人工智慧實驗室 (是的，就是 Richard M. Stallman 早年服務所在)、衍生自 Lisp，作為一種 functional programming languages，以 lambda calculus 為理論基礎。現有 Scheme 語言的標準，依據 2007 年制訂 Scheme 語法規則的第六次修正，特稱 [R6RS] (Revised(6) Report on the algorithmic language Scheme)，基本上就是 Lisp 的方言 (dialect)，伴隨豐富的函式庫資源。[朱孝國的筆記本] 有一份簡要的 [中文簡介]，引述其中關於語法的段落：

• 整個 scheme 可以說是 read-eval-print loop 的運作方式：即「讀取、計算，印出」的過程
• scheme 沒有大小寫之分
• 由函數組合所構成，可以巢狀組合，沒有 main 這個主函數進入點，以小括號將運算式括起來，函數名稱或運算元在左括號的右邊，運算子彼此以空白為間隔，如 3+4*5 這個運算式，以 Sheme 語法撰寫如： (+ 3 (* 4 5)) ，類似資料結構中的前序運算式
• 基本的資料型態為原子 (atom) 及字串 (list)：
  • 原子 (atom) 包含符號 (symbol) 及數值 (number)
  • 串列 (list) 則是以小括號括起來的一串資料

Wikipedia 的 [Scheme] 詞目給了一個遞迴式階層運算的範例：

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

考量到 C 語言的關鍵字，我們「模仿」成以下的風格： (factorial.c)

define(int, factorial, (int n),
       if(eq(n, 0),
          1,
          mul(n, factorial(sub(n, 1)))))

define(int, main, (void),
       (printf("10! = %d\n", factorial(10)), EXIT_SUCCESS))

由上可見，「形式」上，保有括號與原子 (atom) 的呈現，不過，這就不是 C 語言了呀？沒關係，只要在編譯器那邊動點手腳即可，以下是編撰的 Makefile 內容：

CFLAGS = -Wall \
  -D'define(ret, name, args, block) = ret name args { return block; }' \
  -D'if(expr, block1, block2) = expr ? block1 : block2' \
  -D'eq(a, b) = a == b' \
  -D'sub(a, b) = a - b' \
  -D'mul(a, b) = a * b' \                                                                  
  -include "stdio.h" -include "stdlib.h"

TARGET=factorial
all:
	gcc -o $(TARGET) $(TARGET).c $(CFLAGS)
clean:
	rm -f $(TARGET)

編譯並執行：

$ make >/dev/null && ./factorial
10! = 3628800

結果符合我們預期。由上述 macro 定義 (即 -D'name(args...)=definition' 的那五行)，特意將 Scheme 語法的 atom 轉變成 C 語言的語法，原本 Scheme 的語法是：

define(型別 函數名稱 (引數串列), (函數 ...))

做了小量的挪移，恰好符合。同樣地，以上僅示範「模擬」語法的可能性，實際尚須考量到 Scheme/Lisp 在處理運算，本質上採用 prefix (前序運算式) 的設計。

取得本文打包的程式碼 [scheme-in-c.tar.bz2]。
由 jserv 發表於 August 1, 2008 08:54 PM