overview
contents
show-all
home
#+TITLE: 第三次見面 / 3rd-meeting
#+AUTHOR: 謝宇恆 / XIE Yuheng
#+EMAIL: xyheme@gmail.com
* ===================================
* 線串碼解釋器
** 題解
* 線串碼解釋器[threaded code interpreter]
常被 Forth 程序員稱作是內部解釋器[inner interpreter]
* "thread" 做名詞有線程意思
而 "threaded" 在這裏是動詞
意思是 "穿針" 的 "穿"
而 "threaded code" 就是 "被線穿起來的一串代碼" 的意思
* 我用 珠[jo] 來 比喻 "線串碼" 中的 "碼"
一串碼[a thread of code]
就是 一串珠子[珠珠][jojo]
** 控制複雜性
* 程序設計中的一大部分知識和技巧
是關於 *如何控制複雜性* 的
並且這裏所說的是關於 *表達* 的複雜性
想要度量的是 表達 與 理解 的難易程度
[而不是算法的時空消耗]
* 因此
正如 scheme 的設計者 在 SICP 這門課程中所說的
"計算機科學" 既不是科學
又不以機器爲主要研究對象
* 之所以說 "不是科學"
是因爲它不踐行科學的方法論
之所以說 "不以機器爲主要研究對象"
正如 天文學不以天文望遠鏡爲主要研究對象 一樣
* 而在我看來
好的程序語言之好
就在於它能夠爲我提供工具與機制
以使我能夠更好地控制複雜性
** 程序語言的關鍵
* 爲了學習一個程序語言我們需要知道三點
1. 基本的元素有那些
2. 如何用基本的元素來構造更複雜的東西
3. 當構造出來的東西變得更複雜之時
有哪些方法能用來控制這些複雜的東西
* 上面的觀點來自於 scheme 的設計者
他的表達是
1. primitive elements
2. means of combination
3. means of abstraction
* 比如
以匯編語言爲例
上面的三點分別是
1. 機器的基本指令
2. 把編碼好的指令 一個接一個地 寫在一起
機器就順着執行它們
3. 把一段指令視爲一個子程序
用這段指令開頭的地址來代表這個子程序
有了這個地址
就可以在別處調用它
* -----------------------------------
* *抽象的理論*
* 抽象的理論並不針對匯編語言
使用任何程序語言
都可以實現這裏所描述的 線串碼解釋器
* 珠珠
** 珠子能被穿成串
* 比如下面是三顆珠子穿成的一串珠子
#+begin_src return-stack
(dup)
(mul)
(end)
#+end_src
它所記錄的三個操作
能夠用來計算一個數的平方
* 函數的複合就是把兩個函數相繼作用
所以 穿珠子的過程就像是 製作複合函數的過程
所以 一串珠子就代表 一個函數[複合函數]的 *函數體*
** 有一串珠子 那麼可以製作一個新珠子 來對應於這一串珠子
* 給 函數的複合所形成的 函數體[一串珠子] 一個名字
就是用舊的函數定義新函數[一個新珠子]的過程
* 一顆珠子代表一個函數
一串珠子代表一些函數的複合做形成的函數體
一個函數體可以被給以名字
而定義爲一個新的函數
** 對應關係的建立過程就像是撰寫詞典
* 被對應的二者分別是
1. 代表函數體的 那一串珠子
2. 代表新定義的函數的 那一粒新珠子
建立這種對應關係的方式是
去編撰一本 "珠子的詞典" 來記錄其關係
* 每添加一個新的條目進去
就形成了一個新的對應關係
#+begin_src return-stack
例如 一顆珠子
(square)
對應於詞典中的一個詞條
而 一串珠子
(dup)
(mul)
(end)
對應於對這個詞條的解釋
#+end_src
* 不同的詞典或字典有不同的功用
比如說文解字中
一個字所形成的條目中可能包含
1. 對字義的解釋
2. 對字形之創造的解說
3. 對語音的標註
4. 等等
* 而一顆珠子所形成的條目中
函數體決定了函數的意義
定義 square 之後
再見到 square 就如同見到了 dup mul
dup mul 即爲 square 之義
#+begin_src return-stack
(square)
--------
(dup)
(mul)
(end)
#+end_src
** *代碼預覽*
* 在之後要講到的匯編語言中
具體的用來實現這些這種定義的代碼將是
#+begin_src fasm
define_function "square", square
xx dup
xx multiple
xx end
#+end_src
* 上面的 define_function 是一個 macro
而 xx 在 32bit 時 相當於 dd
在 64bit 時 相當於 dq
以 32bit 爲例上面的代碼等效於
#+begin_src fasm
dd (一個指向字符串 "square" 的指針)
dd (一個指向上一個珠子的的指針)
square:
dd explain$function dd dup
dd multiple
dd end
#+end_src
** 珠子的詞典
* 在一本詞典中
你可以通過一個詞的頁碼和行數[即詞的地址]
找到這個詞條 然後查閱其內容
* 在我們的 珠子的詞典 中也是一樣
每個被定義到詞典中的珠子也有一個地址
** 具體應該如何想像一粒珠子呢
*** 首先要知道
* 在每個珠子上
我們需要記錄一些信息
但是
如果想要 把作爲函數名字的字符串 刻在珠子上的話
那麼字符串將有長有短
進而珠子的大小也將有大有小
非常不方便
*** 然而
* 既然每個珠子都是在珠子的詞典中有記錄的
只要找到了一個珠子在詞典中的位置
那麼
代表這個珠子名字的字符串
還有 用來定義這個珠子的一串珠子[函數體]
就都能找到了
*** 所以
* 我們不必把珠子的名字刻在珠子上
只要把它在詞典中的地址刻在珠子上就行了
所以一個珠子上其實是一個數字
這個數字是 珠子的詞典中的一個地址
** 珠子的分類
* 素函數珠 [primitive-function-jo]
* 函數珠 [function-jo]
* 變量珠 [variable-jo]
** 素性
* 其中
素函數珠 就像是 *素數* 一樣
是不能再被分解爲其他珠子的
* 然而
其他的 函數珠 則可以再分解
#+begin_src return-stack
比如 (square)
可以被分解成
(dup) 和 (mul) 的複合
而 (end) 只是用來標記一串珠子的結束而已
並不算是分解出來的成分
#+end_src
** *代碼預覽*
* 在之後要講到的匯編語言中
具體的用來定義 dup 這個 素函數珠 的代碼將是
#+begin_src fasm
define_primitive_function "dup", dup
pop_argument_stack rax
push_argument_stack rax
push_argument_stack rax
next
#+end_src
* 如果把 define_primitive_function 這個 macro 展開的話
#+begin_src fasm
dd (一個指向字符串 "dup" 的指針)
dd (一個指向上一個珠子的的指針)
pop_argument_stack rax
push_argument_stack rax
push_argument_stack rax
next
#+end_src
* 棧
** 一摞東西
* 啥東西都行
** 這摞東西的特點是
* 放在下面[或前面]東西
必須等放在上面[或後面]東西
都被拿走之後
才能被拿走
** 對棧有兩個基本的操作
* 入棧 [push]
* 出棧 [pop]
** *代碼預覽*
* 在之後要講到的匯編語言中
用以實現兩個主要的棧的代碼將是
[以 64bit 的代碼爲例]
#+begin_src fasm
preserve 64 * jo_size
address$argument_stack labeling
preserve 1024 * 1024 * jo_size
define pointer$argument_stack r15
macro push_argument_stack register {
mov [pointer$argument_stack], register
add pointer$argument_stack, jo_size
}
macro pop_argument_stack register {
sub pointer$argument_stack, jo_size
mov register, [pointer$argument_stack]
}
define_primitive_function "dup", dup
pop_argument_stack rax
push_argument_stack rax
push_argument_stack rax
next
define_primitive_function "drop", drop
pop_argument_stack rax
next
#+end_src
* 函數語義之形成
** 參數棧與返回棧
* 參數棧 [argument-stack]
* 返回棧 [return-stack]
** 參數傳遞
* 利用 參數棧
* 你可以想像每個 素函數珠
能夠幫你召喚出一個小機器人[或者小精靈]
來爲你做一些計算和操作
* 計算的材料都要從 參數棧 中取 [即函數的參數]
並且計算的結果也要返回 棧參數 中 [即函數的返回值]
比如
#+begin_src return-stack
(mul) : 素函數珠
它召喚出來一個小精靈
幫你做乘法
(dup) : 素函數珠
它召喚出來一個小精靈
來把 參數棧 頂部的數複製一下
(square) : 複合函數珠
因爲它是被分解成
上面的兩個 素函數 的複合的
#+end_src
* 這樣 參數棧 就成了 小精靈們 傳遞計算結果的場所
一個 小精靈 計算成果
可以被作爲 另一個 小精靈 的參數
** 函數的 嵌套定義 與 嵌套調用
* 你可以把 返回棧 return-stack 想像成一個鉄棍子
棍子串着一溜圈子
#+begin_src return-stack
- [ . ] - [ . ] - [ . ] - [ . ] - [ . ]
#+end_src
圈子上可以卡珠子
一串珠子中的某個珠子 可以被卡在棍子的圈子上
#+begin_src return-stack
(666)
(22) (666)
- [ (22) ] - [ (33) ] - [ (666) ] - [ . ] - [ . ]
(22) (33)
(22) (33)
(33)
#+end_src
* 只要把一串珠子放到返回棧裏
然後啓動 線串碼解釋器
就能形成函數 調用 與 返回 的語義了
* 比如下面的例子所展示的
*** at the beginning
* argument-stack
<< 2 >>
* return-stack
#+begin_src return-stack
- [ (square) ]
(square)
(end)
#+end_src
*** next (1)
* argument-stack
<< 2 >>
* return-stack
#+begin_src return-stack
(square)
- [ (square) ] - [ (dup) ]
(end) (mul)
(end)
#+end_src
*** next (2)
* argument-stack
<< 2, 2 >>
* return-stack
#+begin_src return-stack
(square) (dup)
- [ (square) ] - [ (mul) ]
(end) (end)
#+end_src
*** next (3)
* argument-stack << 4 >>
* return-stack
#+begin_src return-stack
(dup)
(square) (mul)
- [ (square) ] - [ (end) ]
(end)
#+end_src
*** next (4)
* argument-stack << 4 >>
* return-stack
#+begin_src return-stack
(square)
- [ (square) ]
(end)
#+end_src
*** next (5)
* argument-stack << 4 >>
* return-stack
#+begin_src return-stack
(square)
(square)
- [ (end) ] - [ (dup) ]
(mul)
(end)
#+end_src
*** next (6)
* argument-stack
<< 4, 4 >>
* return-stack
#+begin_src return-stack
(square)
(square) (dup)
- [ (end) ] - [ (mul) ]
(end)
#+end_src
*** next (7)
* argument-stack
<< 16 >>
* return-stack
#+begin_src return-stack
(square) (dup)
(square) (mul)
- [ (end) ] - [ (end) ]
#+end_src
*** next (8)
* argument-stack
<< 16 >>
* return-stack
#+begin_src return-stack
(square)
(square)
- [ (end) ]
#+end_src
*** next (9)
* argument-stack
<< 16 >>
* return-stack
#+begin_src return-stack
- [ ]
#+end_src
* it is really simple
^-^
is it not ?
* -----------------------------------
* 具體計算機構架 之 x86 篇
** 回憶費恩曼的比喻
| 能比 | 所比 |
|----------------------+--------------------|
| 檔案館 | 一級存儲器 (內存) |
| 黑板 | 中央處理器的寄存器 |
| 檔案館員工一名 | 中央處理器 (CPU) |
| 檔案館員工的基本素養 | 處理器的指令集 |
** 32bit 與 64bit
* CPU 的寄存器的大小
[基本數學運算所能處理的數字的大小]
* 內存 的地址範圍
[CPU 的尋址能力]
[地址總線的寬度]
** 利慾薰心者引發的災難
* 三個模式
| 16bit | real-mode |
| 32bit | protect-mode |
| 64bit | long-mode |
* 當設 CPU 從 16bit 升級到 32bit
CPU 必須保持能夠運行 16bit 的老程序的能力
這種設計被成爲 "向後兼容"
"向後兼容"
1. 不利於 CPU 的設計師把 CPU 設計好
比如
若不考慮 "向後兼容" 的問題
32bit 的 CPU 就可以設計得更加優雅和精簡
2. 不利於 編碼者給 CPU 寫程序
因爲複雜而不易學習與理解
3. 有利於 CPU 公司 和 軟件公司 的短期利潤率
買了新硬件的人 也可能買老程序
買了老程序的人 也更願意買新硬件
* 這是典型的
因利慾薰心 而目光短淺
因目光短淺 而作出壞的決策
而壞的決策的積累 而產生了災難性的後果
* 三個模式的產生
只是這種災難的一方面而已
** 檔案館
* 以 32bit 爲例
32 根地址总线作爲二進制數
能夠編碼 2 的 32 次方 個數字
範圍是 0 到 2 的 32 次方 減 1
| | 簡記 | 實際 | 約 |
|--------------+------+--------------------+--------------|
| 2 的 10 次方 | 1K | 1024 | 1000 |
| 2 的 20 次方 | 1M | 1024 * 1024 | 1000 000 |
| 2 的 30 次方 | 1G | 1024 * 1024 * 1024 | 1000 000 000 |
* 所以 2 的 32 次方
也就是 4G 那麼多個抽屜
所以如果你使用 32bit 的操作系統
你的超過 4G 的內存就報廢了
* 每個抽屜裏都可以放一個 byte
也就是 8 bits 的數據
* 比如下面三個抽屜
| 抽屜 | 存放的數據 |
|------+------------|
| 1024 | 10010011 |
| 1025 | 00000001 |
| 1026 | 00001000 |
** 黑板
* 白板 ?
* 通用寄存器的表格
#+begin_src fasm
|--------+--------+---------------+-------------+---------------|
| 8bit | 16bit | 32bit | 64bit | naming note |
| [byte] | [word] | [double word] | [quad word] | |
|--------+--------+---------------+-------------+---------------|
| al, ah | ax | eax | rax | accumulator |
| bl, bh | bx | ebx | rbx | base |
| cl, ch | cx | ecx | rcx | counter |
| dl, dh | dx | edx | rdx | data |
| sil | si | esi | rsi | source |
| dil | di | edi | rdi | destination |
| spl | sp | esp | rsp | stack pointer |
| bpl | bp | ebp | rbp | stack base |
|--------+--------+---------------+-------------+---------------|
| r8b | r8w | r8d | r8 | |
| r9b | r9w | r9d | r9 | |
| r10b | r10w | r10d | r10 | |
| r11b | r11w | r11d | r11 | |
| r12b | r12w | r12d | r12 | |
| r13b | r13w | r13d | r13 | |
| r14b | r14w | r14d | r14 | |
| r15b | r15w | r15d | r15 | |
|--------+--------+---------------+-------------+---------------|
#+end_src
* 資料
** OSdev [社區]
* 一羣設計新的操作系統的人所做成的社區
有非常好的 維基 和 論壇
* ===================================