作業系統之前的 scheme

the 1st edition: 20141127 (4)
the 2nd edition: 20210327 (6)

會選擇 c++ 來開發 scheme, 最主要是因為 c++ 的標準程式庫有很多好用的 class: string, vector, map, list ... 不用為了這些基本的東西傷腦筋; 但這次要開發的是 - 在作業系統之前的 scheme (開發平台是 stm32f4discovery), 這些好東西通通派不上用場, 沒有 malloc/new, 又怎麼能用這些東西呢! 甚至連 global object 都不能用, 所以幾乎和使用 c 一樣, 不過還是能用上點 c++ 的特性。

原本程式中用到 list, vector, map 的部份, 通通要改, 全部改用 array, 不夠彈性, 但容易實作, 至於 input/output function, 需改用 uart 這部份的程式碼, 所以直接把之前搞定的 uart 程式碼複製一份過來修改。

getline 我得換成 getchar uart 的版本, cout 也要換成 myprint uart 的版本, 這之前都做過了, 把以前的努力都集合起來就可以, scanner 的作法則改為一次讀一個 byte 來轉成 token, s-express 不複雜, 但我覺得還是不容易, 沒想到花點時間竟然搞定, 感謝两周自制脚本语言的 scanner 這節提供的知識。

再來是 malloc Cell* 的部份, 由於在重寫 struct Cell 時, 我就考慮到在 stm32f4discovery 開發板上執行, 也就是沒有 os 的環境, 所以才使用了 array pool 來得到一個 Cell 的記憶體。雖然沒有彈性, 但能簡化問題, 再搭配一些人工手法, 可以減低 pool 可能會不夠用的問題。

我先在 qemu stm32 p103 emulator 上測試, 等成功了再上到 stm32f4discovery, 減少 flash 讀寫次數。也的確有必要, 光在模擬器上就測試了無數次, 減少了多次的 flash 讀寫。

在製作 p103 emulator 的版本階段, 出了一個 link 問題:

git@github.com:descent/stm32_p103_demos.git stm32_p103_demos/demos/uart_echo git commit: 6b2df2c6e62f3c48a6c6dc20c76367124c1ca447

bss_to_big

1 /home/descent/arm-cs-tools/lib/gcc/arm-none-eabi/4.7.3/../../../../arm-none-eabi/bin/ld: mymain.elf section `.bss' will not fit in region `RAM'
2 /home/descent/arm-cs-tools/lib/gcc/arm-none-eabi/4.7.3/../../../../arm-none-eabi/bin/ld: region `RAM' overflowed by 34085848 bytes
3 collect2: error: ld returned 1 exit status

我以為我已經很了解 link 的問題了, 這應該難不倒我, 就是哪個 section 太大, 整個記憶體空間不足嘛! 嚇不了我的。但隨著時間的過去, 我還是無法處理這問題, 亂 google 找問題, 我 - 開始緊張了, 原來我還有沒搞懂的東西。

當然最後還是搞定了, 原因是: bss 竟然需要 34M 的記憶體空間, 嚇壞我了, p103 只有 20K ram, 把 main.ld 的 RAM 從 20K 改成 48M 就可以編過, 但想也知道, 放入 flash 執行, 一定掛掉。

main.ld

 MEMORY {   FLASH (rx) : ORIGIN = 0x00000000, LENGTH = 128K   RAM (rwx) : ORIGIN = 0x20000000, LENGTH = 20K -> 48M } ... ...

我當然是不會用這麼蠢的改法。程式中用到相當多的 global variable (global variable 不一定佔據 bss, 得找對才行), 來把他們減少, shorten_bss L32 的效果最好,

/bin/ld: region `RAM' overflowed by 877288 bytes collect2: error: ld returned 1 exit status

從 34M 降到 877K, 效果不錯, 可是還不夠 ...

shorten_bss

 1 diff --git a/cell.h b/cell.h
 2 index d7238ea..eb36b5c 100644
 3 --- a/cell.h
 4 +++ b/cell.h
 5 @@ -11,7 +11,7 @@
 6  
 7  using namespace std;
 8  
 9 -const int MAX_POOL = 1000;
10 +const int MAX_POOL = 70;
11  
12  enum PairAttr {HEAD, FIRST, SECOND};
13  enum CellType {STRING, SYMBOL, NUMBER, PAIR, PRIMITIVE_PROC, NULL_CELL, INVALID};
14 @@ -21,7 +21,7 @@ struct Environment;
15  struct Cell;
16  typedef Cell *(*ProcType)(Cell *);
17  
18 -const int MAX_SIZE = 256;
19 +const int MAX_SIZE = 20;
20  // a variant that can hold any kind of lisp value
21  struct Cell 
22  {
23 diff --git a/s_eval.h b/s_eval.h
24 index 37048ac..2da9ae5 100644
25 --- a/s_eval.h
26 +++ b/s_eval.h
27 @@ -4,14 +4,14 @@
28  #include "cell.h"
29  #include "token_container.h"
30  
31 -const int MAX_ENVIRONMENT_POOL = 1000;
32 +const int MAX_ENVIRONMENT_POOL = 10;
33  
34  #ifdef USE_CPP_MAP
35  typedef std::map<std::string, Cell*> Frame;
36  #else
37 -const int FRAME_LEN = 128;
38 +const int FRAME_LEN = 56;
39  
40 -const int LINE_SIZE = 256;
41 +const int LINE_SIZE = 128;
42  
43  struct EnvElement
44  {
45 @@ -29,7 +29,7 @@ struct Environment
46  
47      Frame frame_;
48  
49 -    char name_[255]; // for debug
50 +    char name_[12]; // for debug
51      int free_frame_index_;
52    private:
53  };

胡亂修改後, 總算 link 成功。

機器上的記憶體有 20K, 程式本身有 19K, 載入到記憶體後, 可以正常執行的嗎? 不一定, bss 區域不會佔據程式本身, 但是會佔用載入時的記憶體位址, 所以還得加上 bss 佔用的記憶體, 若 bss 佔據了 2K, 19k+2k = 21k, 記憶體就不夠用了。

這便是 link 不過的原因。

還有問題二:

高興的將程式載入模擬器後, 準備欣賞自己的傑作, 發現:

repl 的第一個參數 prompt, 不知道為什麼會被 TokenContainer tc 所影響 (傳進來的參入位址會變成 0), 我把 TokenContainer tc 改成 global variable 才正常 (原本是 auto variable)。

我猜測是 stack 被覆蓋了, 不過沒有認真追, 也有可能是其他問題。

再來還有一些後續的小問題, 克服他們後, 就是下面影片的成果。



應該離成功不遠了 ...

真實機器篇 - stm32f4discovery

事情果然沒那麼順利, 在我將模擬器的程式移植到 stm32f4discovery 後, 沒什麼問題, 提示符號出來了, 但是打下 (+ 1 2) 之後, 程式沒有印出預期的 3, 而是停止不動。猜測是 stack 問題 (又是 stack), 將 stack 改大一點就正常執行了。在 x86 記憶體很大, 不太容易遇到 stack 太小的問題, 但在 stm32f4discovery, 記憶體不大, 只有 192k, 考驗我的程式能力。

下面影片是在 minicom 的執行結果:



後來知道了 ccm 這東西, 把 stack 移到 ccm, 成功擠出更多記憶體。

支援 backspace

這個常見的的功能還真沒那麼簡單, call library 果然比較舒服, 思考良久之後, 決定使用 deque 來完成這個功能, 我參考了 c++ 的 std::deque, 實作了一個 MyDeque, 雖然我用的是 c++, 不過作業系統之前沒有 std::deque 可以用。

MyDeque 提供以下 member function:
push_front() 給 ungetch() 用
pop_front() 在 getchar() return 時傳最前頭的 char
push_back() 把輸入的 char 存到這個 deque
pop_back() 提供了 backspace 的功能

因為這個 mydeque 需要成為一個 global variable, 所以沒有提供 ctor, 避免 compile 不過的問題 (你很疑惑為什麼吧?), 不過這不是什麼難題, 我使用了 init() 來變通, 得自己呼叫 mydeque.init(); 來作初使化的動作, 也如你預期的, 我老是忘記 call .init(), 每每在驚呼「為什麼?」之後才想到自己的疏忽。

使用了一大堆 global variable, 完全不是 c++ 哲學, 就跟你說了, 這是一個長的很像 c 的 c++ 程式。

為了支援 backspace 沒想到要多做一個 class, 這是經過深思熟慮後的想法, 也才決定用 deque (念做 deck), 這還真是個神奇的資料結構。

下面影片顯示支援 backspace 的操作:



不過這個實作還有點問題, 超過 MyDeque 的大小, 就會有問題, 所以我把 MyDeque 設到 128 個 int 大小, 暫時躲避這問題。

line edit history

20141115 我加上了 line edit history 的功能, 按下 up/down 就會把之前打過的指令取出來, 很基本的功能吧! 但要實作這個功能可花了我好大的力氣。

我寫了一個 deque 的 template 的版本, 一個 CString class 用來支援這樣的功能, 所以前面那個 MyDeque 被移除了。我第一次覺得 c++ template 這麼好用, 感動到痛哭流涕。雖然 c++ 現在複雜的不像話, 不過程式員只要選擇自己要用的部份就好了, 重點是把程式寫出來, 而不是用上什麼新特性。這個程式沒有 malloc/free 還不是照樣可以完成。

偵測 up/down key 是個小問題, 答案分別是: up: 27 '[' 'A' down: 27 '[' 'B' right: 27 '[' 'C' left: 27 '[' 'D'

要抓出 3 bytes 才能判斷是哪一個方向鍵。

而 scanner 程式整個重新改寫。辛苦完成的 MyDeque 派不上用場了, 以下影片示範這個功能:



當做出 history 功能時, 自己都覺得很酷, 這個功能真是無敵好用。

這個程式集 os 觀念和 scheme interpreter 之大成。是繼 simple os 之後的心血, 所有的東西都自己打造, 很有成就感。

這裡有篇履歷的文章: How the HR department and a programmer reads your resume? 我結合 os, interpreter, 可以加 20 分嗎?



疑, 這次怎麼沒有提供 source code, 因為這次的 souce code 分佈在 3 個地方, 太麻煩就不列了。有興趣的朋友一定會自己發問的。

寫下這篇文章很久之後, 我終於整合好所有程式碼,

source code:
https://github.com/descent/simple_scheme

可以使用 p103 這個平台編譯, 這是跑在 qemu 模擬器上。

好久沒做烘焙產品了, 該來做一個蛋糕慶祝一下, 犒賞自己。

porting simple c++ library 的 x86 16bit 版本

博學之、審問之、慎思之、明辨之、篤行之。

先把 cs, ds, es, ss 指到同一個值, 再把 sp 暫存器設定好完成 stack 設定就可以順利完成 x86 16 bit mode 的 c runtime, 這裡都要用上組合語言, 而從這之後, 就可以用 c 語言了, 開心吧, bss 初始化就用 c 來撰寫了, 當然也可以開始用 c++ 了。再把 read/write bios call 加入就擁有了 input/output 的能力, x86 自然是從鍵盤 input, output 到螢幕上。這樣就完成整個移植了, 說起來很簡單, 而過程就很刺激, 遇到不少問題, 紀錄如下:

1. x86/start.s bios_print_char
   
   這是用組合語言寫的 function, 讓 c++ call, 用途是在螢幕上印出一個字元。return 時必須要用 retl 而不是 ret, 差個 l 差很多。我本來打算用 inline assembly 寫這個 function 的, 不過寫不出來, 只好用純組合語言寫, inline assembly 可參考《Writing a 16-bit dummy kernel in C/C++》。
   
   
   inline assembly bios_call 範例

   
   

    1 /* io functions */
    2 /* this function is used to get a chara*/
    3 /* cter from keyboard with no echo     */
    4 void getch() {
    5      __asm__ __volatile__ (
    6           "xorw %ax, %ax\n"
    7           "int $0x16\n"
    8      );
    9 }
   10 
   11 /* this function is same as getch()    */
   12 /* but it returns the scan code and    */
   13 /* ascii value of the key hit on the   */
   14 /* keyboard                            */
   15 short getchar() {
   16      short word;
   17 
   18      __asm__ __volatile__(
   19           "int $0x16" : : "a"(0x1000)
   20      );
   21 
   22      __asm__ __volatile__(
   23           "movw %%ax, %0" : "=r"(word)
   24      );
   25 
   26      return word;
   27 }
   28 
   29 /* this function is used to display the*/
   30 /* key on the screen                   */
   31 void putchar(short ch) {
   32      __asm__ __volatile__(
   33           "int $0x10" : : "a"(0x0e00 | (char)ch)
   34      );
   35 }
   

   
   retl 會讓 sp + 4
   ret 會讓 sp + 2
   
   +4 才是我要的值, 這樣 stack 才不會亂掉。
   
   
2. 在這個組合語言寫的 function 要保存 ebx/eax register, 否則以下程式碼
   
   

   char cc='A';
   cout << ": " << cc << endl;
   

   
   會錯誤。
   
   原因就是沒保存 ebx/eax, 我很辛苦的從組合語言去除錯, 找到問題後, 覺得自己還蠻厲害的。這段程式碼有用到 ebx, 而印出到螢幕的程式碼也用到 ebx, 呼叫印出到螢幕的程式碼後, ebx 就不是原來的值了, 所以造成錯誤。
   
   
3. 縮小 heap 空間, 因為整個執行環境的記憶體只有 64 k (明明有 640k 記憶體可以用, 你有點疑惑吧! 參考: 深入认识 Turbo C 编译器 ), 包含執行檔案的大小, 若執行檔佔了 10k, 我只剩下 56 k 可用, 包含 bss, stack。這已經比 stm32f4discovyer 的 192k ram 還小了。
   
   
4. 另外是 bss type 的問題, 紀錄在 linker script symbol type R_386_16, R_386_32
   

有兩個版本, 一個是透過 boot loader 載入, 一個是 dos 下的 .com 檔案。

完成後我把 simple scheme 也移植過來, 畢竟已經有了 dos 平台的標準程式庫, 照裡來說應該要很容易, 不過只能使用 64k 的 ram, 實在太小, 我又很辛苦的縮到 64k, 才算移植成功, 參考以下影片:



64k 實在大小, 該怎麼辦? 有一個方法是使用 big real mode, 另外一個是使用不同的節區, 我不打算搞 big real mode 這樣的方法, 來試試看不同節區的方法吧!

把 es, ds, ss 指到另外的地方, 可以再增加 64k, 所以把 start.s (這是 x86 simple c++ library 程式進入點) 改成以下的樣子:

mov $0x8000,%ax
  mov %ax,%ds
  mov %ax,%es
  mov %ax, %ss

這樣就可以了嗎? 當然沒那麼簡單, 這樣是會出事的。還要把 data section 複製到 0x8000 這個 segment, ex:

0x9000:data_section_addr_begin ~ 0x9000:data_section_addr_end -> 0x8000:data_section_addr_begin ~ 0x8000:data_section_addr_end

init_data_asm 就是在做這樣的事情。為什麼我會知道呢? 因為我把反組譯的程式碼看過後, 發現補上這樣的行為, 就可以符合 c 語言的正確行為, 否則在函式參數傳遞會有問題, 可能會在傳遞指標時發生問題。

再來是 ctor 的位址我在 linker script 這邊沒處理好, x86_16.ld.error L37 ~ 39 會抓到錯誤的 call_ctor address, x86_16.ld 的版本才是對的。

因為 align 的問題, ex:
00 01 02 00
本來應該要抓到 01 02, 結果抓到 00 01,
調整 linker script alignment, 就變成
01 02 00 00
就可以正確抓到 01 02。

你一定好奇我怎麼找到這問題, 使用 bochs 內建除錯器, 慢慢和組合語言搏鬥, dump 記憶體位址來觀察, 很辛苦的。

x86_16.ld.error

 1 ENTRY(begin)
 2 
 3 SECTIONS
 4 {
 5   . = 0x100;
 6 
 7   .text :
 8   {
 9     KEEP(*(booting))
10     KEEP(*(.isr_vector))
11     *(.text)
12     *(.text.*)
13     _etext = .;
14     _sidata = .;
15   } 
16   .bss : 
17   {
18     _bss = .;
19     _sbss = .;
20     *(.bss)         /* Zero-filled run time allocate data memory */
21     _ebss = .;
22   } 
23 
24 
25   .= ALIGN(32);
26 
27   /* Initialized data will initially be loaded in FLASH at the end of the .text section. */
28   /* .data : AT(0x5000) */
29   .data : 
30   {
31     _data = .;
32 
33     *(.ccm)
34     *(.rodata)
35     *(.rodata.*)

36     _sdata = .;
37     __start_global_ctor__ = .;
38     *(.init_array)
39     __end_global_ctor__ = .;
40 
41     *(.data)  /* Initialized data */
42     _edata = .;
43   } 
44 
45   .myheap (NOLOAD):
46   {
47     . = ALIGN(8);
48     *(.myheap)
49     . = ALIGN(8);
50   }
51 
80 }  

x86_16.ld

 1 ENTRY(begin)
 2 
 3 SECTIONS
 4 {
 5   . = 0x100;
 6 
 7   .text :
 8   {
 9     KEEP(*(booting))
10     KEEP(*(.isr_vector))
11     *(.text)
12     *(.text.*)
13     _etext = .;
14     _sidata = .;
15   } 
16   .bss : 
17   {
18     _bss = .;
19     _sbss = .;
20     *(.bss)         /* Zero-filled run time allocate data memory */
21     _ebss = .;
22   } 
23 
24 
25   .= ALIGN(32);
26 
27   /* Initialized data will initially be loaded in FLASH at the end of the .text section. */
28   /* .data : AT(0x5000) */
29   .data : 
30   {
31     _data = .;
32 
33     _sdata = .;
34     __start_global_ctor__ = .;
35     *(.init_array)
36     __end_global_ctor__ = .;
37     *(.ccm)
38     *(.rodata)
39     *(.rodata.*)
40 
41     *(.data)  /* Initialized data */
42     _edata = .;
43   } 
44 
45   .myheap (NOLOAD):
46   {
47     . = ALIGN(8);
48     *(.myheap)
49     . = ALIGN(8);
50   }
51 
80 }  

那要怎麼像 turbo c 做到 huge mode 的記憶體模式呢? 這我就不知道了, 我不想再去研究過時的東西了。

git url:
https://github.com/descent/simple_stdcpplib
branch: x86_16_support_diff_segment

考古一下, 在 ms dos real mode 上, sizeof int 是 2byte, 有玩過 dos 程式設計的人應該都知道, 不過一定都是這樣嗎?

以下 fig1, fig2 是在 dos real mode 測試 borland c++ 和 g++ sizeof int 的結果。

fig 1 bc 31 sizeof int: 2

fig 2 g++ sizeof int: 4

g++ 的 int 是 4 bytes, 而 borland c 是 2 bytes, 很不一樣吧?

borland c 是 dos 下開發的霸主, 很好用, gcc 比較少人使用, c 的 type 不只和 os 有關, 就算在同一個 os 下, 不同編譯器也有著不同的結果。

ref:
深入认识Turbo C编译器

scheme interpreter by c++

看完 sicp 4.1 時, 真是興奮, 原來 scheme interpreter 就是這樣完成的, 我辛苦搞懂了 scheme 的程式碼 (我整理了一系列看懂 sicp 4.1 的《心得》), 想用 c/c++ 實作一個簡單版本, 畢竟 c++ 一直以來是我很喜歡的語言。

由於 scheme 語法很簡單 (對比 c 語法之流), 給了我信心, 我深信我一定做的出來, 但這只是錯覺, 寫 compiler/interpreter 真的比較難, 是有他的道理的。

c++ 的版本比我想得還難, 我一下子就遇到 scanner 的困難, 沒想到我特地找了 s-expression 來練習, 還是無法實作 scanner, s-expression 已經算是很簡單的了。

把 (+ 1 2) 變成

(
+
1
2
)

產生這樣的 token list 不難, 難的是怎麼把它變成 scheme 的 list 資料結構。
ex: (+ ( * 2 3) 1) => + * 2 3 1
而 car + * 2 3 1
得到 +

(car (cdr + * 2 3 1) )
要得到 * 2 3
這樣的資料結構。

ref:
https://github.com/descent/simple_scheme/blob/master/s_eval.cpp
Cell *read(TC &tokens)

這裡需要用到 recursive 的觀念, 並不是很好想。

sicp 4.1 的實作並沒有以 BNF 的形式來處理, 似乎不需要用 BNF 的方式, 直接就可以寫出整個 parser, 沒有符號表, 沒有 AST, 當然那個 recursive 一樣很複雜。

(How to Write a (Lisp) Interpreter (in Python)) 內文給我了一些提示, 真難得有繁體中文翻譯: http://reborn2266.blogspot.tw/2011/11/how-to-write-lisp-interpreter-in-python.html

可惜的是我還不夠聰明到可以用 python code 推出 c++ 的版本, 直到 Lisp interpreter in 90 lines of C++ 這篇文章的 source code 一舉為我解除疑惑。

除了幫我解決 scanner 的疑惑外, 還幫我解決了 Cell 這個資料結構的問題, 我想了好幾天, 總是卡在某個地方無法突破。不過最後我重新改寫成較類似 scheme cons 的 pair, 不需要使用 std::list, c++ 標準程式庫的東西我得慢慢移掉才行, 這次的改寫讓我一次完成兩個功能; std::map 則是我下階段要移掉的東西。

完成一個 interpreter 並沒有想像中的容易, 光是最簡單的計算機, 就得使用上編譯器教科書上的理論, 否則應該是很難寫出來, 如果你靠自己克服了這難題, 想必你一定是個聰明的傢伙。

UNIX 编程环境 (Brian W.Kernighan, Rob Pike) 第八章在談一個計算機怎麼寫, 其中使用了 lex, yacc。

Stroustrup Programming: Principles and Practice using C++ (這本有 Second Edition, 談及 c++11, c++14) 6, 7 章也在談怎麼寫一個計算機, 沒有使用 lex/yacc。C++ 程序设计原理与实践 (Programming: Principles and Practice using C++ 的簡體中文版本 - 第一版) p 109 提到: 「這是 50 年來的經驗, 想要一夜打破 50 年來的經驗不是個好主意。」

1+2*3 也許很難處理, 我本來以為 (+ 1 (* 2 3)) 會好一點, 是好一點, 不過依然不是件簡單的事情。

一開始的目的就只打算完成四則運算, (+ 1 2 3), (+ (* 2 3) 6) 之類的, 沒想到也花了好大一番功夫才搞定。

這是兩階段的學習, 我先把 scheme 的實作版搞懂, 才來實作 c++ 版本的四則運算。

https://github.com/descent/simple_scheme
tag three_op

在 branch origin/new_cell 我重新實作了 Cell, 使用 Cell *get_cell(const char *val, ProcType proc) 來從 array 得到一個 Cell, 而不是用 malloc/new 來得到一個 Cell, 這是為什麼呢? 容我賣個關子, 若你大概看了這個版本, 應該會覺得這是個很像 c 的 c++ 程式, 事實上, 這是刻意的, 因為我不想使用太多 c++ 的特性, 怕到時候會有問題。

在這個版本之後, 我有了 cdr, car, cons 可以用, 後來的程式碼幾乎就是把 sicp 的 code 抄過來。為什麼要改寫 struct Cell? 因為我被 car, cdr 整個搞亂了, 套用原來的 Cell 結構, 我很難做到 car, cdr 的功能, 老是把 car, cdr 的結果搞錯, 我並沒有完全使用 Lisp interpreter in 90 lines of C++ 的程式碼, 我只需要 scanner 和 Cell 這部份, 打通之後就可以繼續下去; 新的 Cell 幾乎大量使用指標操作, 沒有 std::list, 整個速度應該提升不少。

再來的困難是環境, 有點複雜, 和 sicp metacircular evaluator 的實作不同, 我有 std::map 可以用, 實作環境輕鬆多了。

lambda 的實作我認為最困難, 只要過了這關, 後面的 define, if, cond, set!, begin　根本就是照抄 sicp 的 code。

我就是照著 sicp metacircular evaluator 這系列, 一步步完成 c++ 版本。其中花了不少精神, 總算小有所成。

這個程式在 linux 平台開發/測試, 再來的版本就有點挑戰性, 我滿懷能量, 準備完成它, 這是個集我所學大成的計劃, 取名為作業系統之前的 scheme。

後來在開發了《simple c++ 標準程式庫》後, 我總共有了

1. linux
2. bare-metal rpi2
3. bare-metal stm32f407
4. bare-metal p103 模擬器
5. x86 16bit mode bare-metal
6. x86 16bit mode ms dos
7. uefi

這麼多的實作版本。

uefi scheme

這是其他人開發的 c++ 版本:
http://www.open-open.com/lib/view/open1352593340668.html

其 soure code:
https://github.com/zoowii/SchemeRuntime

我的版本:
https://github.com/descent/simple_scheme

ref:

• Scheme from Scratch - Introduction
• Write a Scheme Interpreter in Ruby(2): THE Interpreter

sicp metacircular evaluator (0) - map/car/cdr

sicp 4.1 要寫一個 Metacircular Evaluator, 有個部份在處理 environment。把 car, cdr, +, - 這些 primitive procedure 定義在這環境裡, 是很重要的一步。不過 scheme cons pair 資料結構實在難倒我, 把這些部份獨立出來測試。

t1.scm

 1 (define primitive-procedures
 2   (list (list '- -)
 3         (list '+ +)
 4         (list 'car car)
 5         (list 'cdr cdr)
 6         (list 'cons cons)
 7         (list 'null? null?) 
 8         ))
 9 (display primitive-procedures)
10 (newline)
11 (display (car primitive-procedures))
12 (newline)
13 (display (map car primitive-procedures))
14 (newline)

t1.scm L13 是最主要的部份, 結果是 res L5, 把 symbol -, + , car, cdr, cons, null? 集合成一個 list。

res

1 1 ]=> (load "t1.scm")
2 
3 ;Loading "t1.scm"...((- #[arity-dispatched-procedure 11]) (+ #[arity-dispatched-procedure 12]) (car #[compiled-procedure 19 (list #x1) #xf #x3218d3]) (cdr #[compiled-procedure 14 (list #x2) #xf #x321917]) (cons #[compiled-procedure 16 (list #x3) #xc #x32195c]) (null? #[compiled-procedure 18 (list #x5) #xc #x3219b8]))
4 (- #[arity-dispatched-procedure 11])
5 (- + car cdr cons null?)
6 ;... done
7 ;Unspecified return value
8 
9 1 ]=> 

t2.scm 這個複雜一點, res2 L23 是要達成的效果。

t2.scm

 1 (define primitive-procedures
 2   (list (list '- -)
 3         (list '+ +)
 4         (list 'car car)
 5         ))
 6 
 7 
 8 (define (primitive-procedure-objects)
 9   (map (lambda (proc) (newline) (display proc) (newline) (newline) (display (cdr proc)) (newline)  (newline) (display (cadr proc)) (newline) (list 'primitive (cadr proc)))
10        primitive-procedures))
11 
12 (newline)
13 (display primitive-procedures)
14 (newline)
15 (display (primitive-procedure-objects))
16 (newline)

res2 L4 的 list 由 t2.scm L1~5 構成。L9 的 map 難倒我, proc 可以想成 res2 L4 的 list 裡頭的 list, 就是 L6, L12, L18, 把他們 cdr 後, 就變成 L8, L14, L20, 再 car 後, 就是 L10, L16, L22, 因為 (a) 其實是用 'a, nil 構成的 pair, car 取前面 ('a), cdr 取後面 (nil)。

res2

 1 1 ]=> (load "t2.scm")
 2 
 3 ;Loading "t2.scm"...
 4 ((- #[arity-dispatched-procedure 11]) (+ #[arity-dispatched-procedure 12]) (car #[compiled-procedure 13 (list #x1) #xf #x3218d3]))
 5 
 6 (- #[arity-dispatched-procedure 11])
 7 
 8 (#[arity-dispatched-procedure 11])
 9 
10 #[arity-dispatched-procedure 11]
11 
12 (+ #[arity-dispatched-procedure 12])
13 
14 (#[arity-dispatched-procedure 12])
15 
16 #[arity-dispatched-procedure 12]
17 
18 (car #[compiled-procedure 13 (list #x1) #xf #x3218d3])
19 
20 (#[compiled-procedure 13 (list #x1) #xf #x3218d3])
21 
22 #[compiled-procedure 13 (list #x1) #xf #x3218d3]
23 ((primitive #[arity-dispatched-procedure 11]) (primitive #[arity-dispatched-procedure 12]) (primitive #[compiled-procedure 13 (list #x1) #xf #x3218d3]))
24 ;... done
25 ;Unspecified return value
26 
27 1 ]=> 

sicp: 開發工具 - mit-scheme

這本書使用的語言是 scheme, 是 lisp 的一種方言, scheme 有很多實作品, 書是 mit press, 我自然找了 mit-scheme 來用, 也是 gnu 的產品之一, 在 ms windows, linux 都可以使用; guile 也是 gnu 的 scheme 實作品。

據聞在最後一堂課時, 使用的 scheme 是 DrScheme (目前已更名為 Racket), 我沒有特別研究那個好, 只是這本書是 mit press, 我當然找 mit-scheme 來用, 書上也多少會提到 mit-scheme 有哪些 feature, 正好也是這本書的範例可以使用的功能。

其他的 Scheme implementations: http://community.schemewiki.org/?scheme-faq-standards#implementations

雖然有很多的 scheme 實作, 不過 4.1 的 metacircular evaluator 範例我在 guile, chicken 的 scheme 實作品上都無法順利執行, 若不想修改程式碼, 還是跑在 mit-scheme 比較保險。

這篇不是 scheme 的教學, 我都還不會怎麼可能寫得出教學文, 這只是在說明如何使用 mit-scheme 的開發環境和比較常用的功能。

想學 lisp 很久了, 這次就靠這本書來學習吧, scheme 也可以啦, 反正都是那種很多小括弧的東西。本書並不是專門用來教學 scheme, 只會提到範例程式中所需要的語法, 不過這樣也算夠用, 要深入的話還得參考相關 scheme 書籍。

如果要編譯 mit-scheme 可以從 http://www.gnu.org/software/mit-scheme/ 下載 Portable C 的版本, 我希望你不需要用到這招, 我在 gentoo 上需要這麼做, http://www.gnu.org/software/mit-scheme/liarc-build.html 這裡有編譯方法。

linux/debian 安裝還是用 apt-get:

apt-get install mit-scheme

windows 的安裝應該難不倒你, 你都挑了這麼冷門的東西來學, 應該和我一樣, 是個品味很特別的程式員。

最好也安裝一下說明文件, 這東西很冷門的, 幾乎找不到什麼網路教學文章, 自己 K 文件吧!

apt-get install mit-scheme-doc

執行: mit-scheme

descent@debian-vm:~$ mit-scheme

會跑出一個 mit-scheme 環境, 可以輸入程式碼, 結果會立刻跑出來, 很像 dos 下的 etbasic。

mit-scheme

 1 descent@deb64:/media/sdb1/descent/git/blog_articles/lisp$ mit-scheme
 2 MIT/GNU Scheme running under GNU/Linux
 3 Type `^C' (control-C) followed by `H' to obtain information about interrupts.
 4 
 5 Copyright (C) 2011 Massachusetts Institute of Technology
 6 This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or
 7 FITNESS FOR A PARTICULAR PURPOSE.
 8 
 9 Image saved on Friday August 30, 2013 at 4:37:34 PM
10   Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/x86-64 4.118 || Edwin 3.116
11 
12 1 ]=> (+ 1 2 3)
13 
14 ;Value: 6
15 
16 1 ]=> 

L12 就是我輸入的程式碼。

說真的, 我還真不習慣在一個 interpretation 環境下開發程式, 。

文件上建議使用 Edwin 來輸入 scheme 程式, edwin 很類似 emacs, 有除錯器的功能。
file:///usr/share/doc/mit-scheme-doc/html/mit-scheme-user/Edwin.html#Edwin
說明如何使用 edwin。

我敢打賭, 你要是沒用過 emacs, 絕對恨透了 edwin 這東西, 難用到暴。還是先回到 interpretation 環境下。

mit-scheme document
file:///usr/share/doc/mit-scheme-doc/html/mit-scheme-user/index.html
這文件最好先看一下, 要不然還真的不知道怎麼使用 interpretation 環境下的操作方式。

ctrl+c q exit mit-scheme
(exit) 也可以離開 mit-scheme。

(quit) 不是離開, 而是在背景執行 mit-scheme, fg 就可以把畫面叫回來。

(load "filename.scm")
可以載入一個 scheme 檔案。

4.1 Compilation Procedures
file:///usr/share/doc/mit-scheme-doc/html/mit-scheme-user/Compilation-Procedures.html#Compilation-Procedures
(cf "foo")

不像 c compiler 一樣, 可以很乾脆的產生一個執行檔。他產生的 binary 只是讓 interpretation 環境載入用。

再回到開頭的 edwin, 它很難用, 不過我還是比較常用這個, 因為那個 interpretation 環境我覺得更難用。

file:///usr/share/doc/mit-scheme-doc/html/mit-scheme-user/Edwin-Scheme-Evaluation.html#Edwin-Scheme-Evaluation
會說明如何執行在 edwin 敲入的程式碼。簡單點就是在你要執行的程式碼後面按下 ctrl+x ctrl+e。

M-o 會計算檔案中所有的 express。

edwin 很類似 emacs, 所以連按鍵都很類似。

ctrl+x ctrl+f 可以載入檔案。
ctrl+x ctrl+c 離開 edwin。
ctrl+x ctrl+s 存檔。

C-@ mark
C-x C-x 可以查看 mark 的位置, 不知道意思的話, mark 完之後一直按 C-x
M-w copy
C-w delete

C-x b switch buffer
C-x k kill buffer

C-x o 切換 window
C-x 2 分割成兩個 window
C-x 0 (數字0) 關掉游標在的那個 window

edwin REPL mode:
M-x repl 可進入 REPL mode

這東西太冷門了, 希望有人因為我這篇文章一起來學習 scheme。

scheme compiler: CHICKEN Scheme, 這東西可以產生一個獨立的執行檔, 真是太酷了。

用 apt-get 搞定它。

apt-get install chicken-bin

編譯用法:
http://wiki.call-cc.org/man/4/Using%20the%20compiler

最簡單的用法, 來個階乘測試:

factorial_1.scm

 1 (define (factorial n)
 2   (define (iter product counter)
 3     (if (> counter n)
 4       product
 5       (iter (* counter product)
 6             (+ counter 1))))
 7     (iter 1 1))
 8 
 9 (write (factorial 5))
10 (newline)

csc factorial_1.scm

descent@deb64:3.1.3$ ./factorial_1 
120

要先產生出 c souce code 也行, 文件拉到最下方, 麻煩多了。

mit-scheme 教學:

1. http://faculty.csie.ntust.edu.tw/~ywu/cs4001301/MITScheme_tutorial.pdf
2. http://faculty.csie.ntust.edu.tw/~ywu/cs4001301/Scheme_tutorial.pdf
3. Simply Scheme, second edition
4. The Little Schemer book
5. http://www.cs.rpi.edu/academics/courses/fall05/ai/scheme/starting.html
6. Scheme 語言概要(上/下):
   http://www.ibm.com/developerworks/cn/linux/l-schm/index1.html
   http://www.ibm.com/developerworks/cn/linux/l-schm/index2.html
7. http://blog.csdn.net/zzulp/article/category/682234
8. MIT Scheme 的基本使用:
   http://www.math.pku.edu.cn/teachers/qiuzy/progtech/scheme/mit_scheme.htm

ref:
as script:
http://snippets.dinduks.com/mit-scheme-run-a-script
http://vepa.in/technology/mit-scheme-unix-scripts-and-cgi

scheme < script.scm | grep ";Value:" | sed "s/;Value: /Result: /" 
scheme-run () { scheme < $1 | grep ";Value:" | sed "s/;Value: /Result: /" } 

Petite Chez Scheme (從 Scheme 编程环境的设置得知, 據說效能很好):
http://scheme.com/download/index.html#sec:petitechezscheme