完美

雖然偷看結局是不好的行為，不過昨天還是翻到 Stoy 正文的最後一頁。左邊是一幅全書意念圖 "Semantic Bridge"：

我現在還在橋左邊的底端慢慢往上爬，連 P_omega 都還沒到 XD。Stoy 的最後一段：

Much work remains to be done. In places this scheme of things is still very messy, sometimes because of the unwieldiness of existing languages, and sometimes because we have not yet found the ideal way of expressing some of our concepts. But perhaps this system of denotational semantics may provide the basis of a coherent and unified theory of "how to compute the computable", and thus help in the task of increasing the usefulness of computers and their programmers.

經典！完美！這不起立鼓掌是不行的！雖然我懷疑稍後 cpos 取代了 lattices 成為 domain theory 研究的主軸（這還要問問看莊老師），可是衝著 Stoy 如此具啟發性而且動人的文筆，我一定要讀完這本書！

--
這種結尾我寫不出來啊…

通識版 JPEG

為了讓多一點人認為這個 blog 有意義，我來寫一篇簡化的 JPEG 通識介紹好了 XD。

JPEG 是一種允許失真的圖片壓縮格式，但是它捨去的資訊是我們不太注意得到的，所以既能達到很好的壓縮效果（一般可以壓到原本的 1/10 左右），看起來又不會有明顯的差異。壓縮過程就是從電腦習慣的表達形式轉換為另一種「突顯較重要資訊」的形式，然後把不重要的部份丟掉。

一般我們都用 RGB 三個向度表達一個點的顏色，即紅、綠、藍三個顏色的混合。一張圖片就可視為紅、綠、藍三塊色版的疊合。

JPEG 壓縮的第一步是把每個色點的 RGB 值換成另一種形式 YCbCr，其中 Y 是亮度資訊，Cb 和 Cr 是彩度資訊。據說人對於亮度比較敏感，對於彩度就沒那麼敏感，所以對於 Cb 和 Cr 色版我們可以模糊處理，幾個鄰近色點視為同一個顏色就好。例如我們把一個 2x2 的方塊看成同一個顏色（即縮成一個點）的話，Cb 和 Cr 色版的資訊量馬上就減少為 1/4！

接下來這一步更厲害，是傳說中的 discrete cosine transform。我們先把一個色版分割為一堆 8x8 的方塊，然後對每個方塊套用 DCT。

一個 8x8 方塊經過 DCT 之後仍然是一個 8x8 方塊，但每個點的意義就不一樣了：一個點的值是某個對應頻率的振幅，偏左上角的點對應的變化頻率較低，愈往右下角對應的變化頻率較高。上圖顯示各點對應的頻率，最左上角的點會影響整個方塊，其下的點主要影響方塊的上半部，再下面一點主要影響方塊的上緣和下緣，依此類推。其中最左上角的點最為重要，我們稱之為 DC 值，其餘稱為 AC 值。經過 DCT 的 8x8 方塊可以透過 inverse transform 轉回原來的 8x8 方塊。（學過線性代數的人就知道 DCT 是從標準基底換到另外一組基底。）同樣地，據說人對於低頻變化比較敏感（例如變動 DC 就會變動整個方塊），對於高頻變化比較不敏感，所以我們可以模糊處理偏右下角的值。而且因為經過 DCT 之後，振幅會非常顯著地集中到左上角，所以我們往往可以只保留左上角一小部份的值，其餘捨棄，整張圖的大小可以縮減好幾倍。這一步的壓縮效果是最顯著的。

最後一步是用 Huffman coding、predictive coding、和 run-length coding 等無失真編碼技巧進一步壓縮。Huffman coding 根據符號的出現頻率給予不同長度的 bit patterns 加以編碼，能達到接近理論上最佳的壓縮效果。Predictive coding 則是針對「DC 值是整個方塊的平均值」以及「相鄰兩個方塊的平均值應該相差不遠」的特性，改而編碼兩方塊間的差值（cf. FTC!!）。因為差值會集中在絕對值較小的區間，這會使 Huffman coding 的壓縮效果更好。AC 的部份因為被我們模糊處理甚至捨棄，會產生很多 0，而很多 0 接在一起的時候，我們就不要說 0000000000000000，說「16 個 0」就好，這就是 run-length coding 的概念。把這三種手法融合起來，又可以把資料量再壓下一些。

以上是最基本的 JPEG 壓縮簡介，解碼的時候就是反著做回去嘍。

--
JPEG 還有更複雜的版本，不過我就放棄啦…

編程樂

我之前到成功高中宣傳的時候提出一個「素材說」，最近重看《人月神話》（The Mythical Man-Month）才發覺這種說法八成是從裡面出來的。Brooks 提出五點「寫程式的樂趣」，其中最後一點是

[...] 在如此易於操控的介質（tractable medium）上工作的快樂。程式設計師就像詩人一樣，只動動腦筋就可以做事，運用想像力，便可以憑空造一個城堡出來，很少創造性工作的介質如此富於彈性、如此方便地讓你修修改改，並輕易地就可以把一個偉大的構想實現出來。（當然在後面我們會看到，這樣的易操控性也有它伴隨而來的問題。）

然而，程式又跟詩人所用的字詞不同，程式本身是沒什麼，但它可以製造出看得到的效果，讓你真實感受到它活生生地在動、在做事。它能夠列印、畫圖、發出聲響、移動機械手臂，只要在鍵盤上敲入適當的咒文，整個螢幕的畫面就生氣蓬勃起來，顯現出我們未曾見過、或在現實生活中不可能見到的事物，神話和傳說中的魔法在我們有生之年實現了。

後面跟著有「寫程式的苦難」，不過這當然不能在宣傳的時候講 XD。

最後我還是要再說一次（如果我先前說過的話）：《人月神話》內容當然是經典，中文版也譯得很不錯，絕對是必讀的一本書！任何關於 software engineering 的課程都應該研討這本書的內容才對嘛 XD。

--
這篇應該很通識了吧？XD

Basic Topics

逛到 Wikipedia 一個條目 List of basic computer science topics: Basic computer science concepts。雖然不是什麼權威、完整的清單，不過還是可以趁機檢驗一下 XD。裡面完全不認識的是 π-calculus。至於看過但最不熟的應該是 continuation 吧，第一次看到應該是在 scm 老師的〈Deriving a Virtual Machine〉。然後看到 recursion 就抖了一下 XD。

--
其他的應該都能簡單描述一下吧。

Minsky!

在床上隨便翻 Booch 的《Object-Oriented Analysis and Design with Applications》2/e，翻到 Third Section: Applications 的開場引言：

To build a theory, one needs to know a lot about the basic phenomena of the subject matter. We simply do not know enough about these, in the theory of computation, to teach the subject very abstractly. Instead, we ought to teach more about the particular examples we now understand thoroughly, and hope that from this we will be able to guess and prove more general principles.

說這番話的人是 M. Minsky，碰過 AI 的人都一定認識他。這番話本身則是從 Minsky 的 1969 年 Turing Award Lecture〈Form and Content in Computer Science〉出來的。這就是 program derivation 觸礁的原因嗎？我現在的感覺是 categorical approach 的理論很重，可是實用上卻沒發揮相稱的威力，感覺上捕捉到的原則還不夠。當然這可能只是我還沒上手才有的錯覺，也可能是演算法本質上就比較複雜 ─ 比較對象當然是數學主要探討的數與形。但 Minsky 講的也是很有可能的情況，畢竟數學發展了一兩千年才有今日的面貌，中間對概念的發掘與解析所下的工夫鐵定不少。

我順著看下去，馬上又看到一段很有趣的論述：

It is instructive to consider the analogy with physics, in which one can organize much of the basic knowledge as a collection of rather compact conservation laws. This, of course, is just one kind of description; [...] there are many ways to formulate things and it is risky to become too attached to one particular form or law and come to believe that it is the real basic principle.

這基本上就是我先前簡單討論「正式與直覺的二元論」以及 "introspection framework of theories" 想講的東西。Minsky 看來就比較擅長哲學論述，概念刻畫的粒度夠細，這篇 lecture 值得一讀 XD。

如果對照一下我比較早期和大三以來的 blog posts，會發現我的這種哲學論述少了很多。這其實不代表我對此類議題的思考變少了，而是我覺得這種抽象的討論必然奠基於實際的經驗上，而我顯然還很欠缺後者。沒有基礎的抽象論述我覺得其實就平淡無奇，稍微多想一點大概就想得到，所以把它們當寶寫出來有點愚蠢。例如我剛剛說「抽象討論奠基於實際經驗」，這句話根本（差不多）是最簡單的 tautology：「抽象」依定義就是「從具象萃取出來的」。我現在其實又覺得大學部的不用想太多，乖乖把功課讀好就行，等經驗累積夠多之後想一下就通了。不然像我現在看一套理論，一下子就覺得它只是一種表述形式（或許是很美的一種），不會賦予它什麼特別地位。啊算了，我懶得整理思緒了 XD。

--
形上觀等幾十年後再來談吧 XD。

Computable Functions are Monotonic

往 Nottingham 的公車上，我問 scm 老師 Intro. to FP 9.2.2 節的一個敘述：computable functions 必定是 monotonic。這裡採用的 ordering 在書上稱為 approximation ordering，是一種 (complete) partial ordering。以 Peano (natural) numbers 為例，Peano numbers 要嘛是零（zero），要嘛是某個自然數的後繼者（suc n）。在計算的世界裡，每個型別下都還有一個值 bottom（就是 _|_ 這個符號），代表「算不出來」。Approximation ordering x <= y 的意思是 x 是 y 的一個「近似值」。對於 Peano numbers，approximation ordering <= 可以這麼定義：

• bottom <= n for all n;
• zero <= zero;
• suc m <= suc n if m <= n.

（Hope it's reflexive, transitive, and anti-symmetric.）所以 bottom 是這個 ordering 之下的最小元素，suc (suc bottom) <= suc (suc (suc (suc zero))) = 4，但 3 和 4 之間沒有次序。Monotonicity of computable functions 說，當 f 是個可計算的自然數函數，我們就有

x <= y implies f x <= f y

直覺地講，approximation ordering 衡量的是我們能掌握的資訊量。Monotonicity 告訴我們，輸入的資訊愈多，輸出的資訊就愈多。

怎麼證明這件事情呢？我想到曾經在 Planet Haskell 上面看到一篇文章〈How many functions are there from () to ()?〉，談的正是類似的主題，不過裡面只處理了最簡單的 unit type。Peano numbers 似乎難一點。首先不妨假設 x = bottom，因為倘若 x <= y，我們一定可以不斷把兩邊最外側的 suc 拆掉，讓左邊露出 bottom。（x = zero 的情況是簡單的。）假設找得到 y 使得 f x > f y，我們想導出矛盾。

接下來是在車上的想法，但我在旅館裡面要把它寫下來的時候發現錯了。我試圖證明，因為 f bottom = non-bottom（f x > f y >= bottom），f 必為常函數，否則 Turing-recognizable & co-Turing-recognizable implies decidable，用 f 就能讓 halting problem 變為 decidable。如果 f 的確是常函數，f x 就不可能嚴格地大於 f y，得到矛盾。可惜證明「f 是常函數」那一步是錯的，f 並沒有使 halting problem 變成 co-Turing-recognizable。現在我暫時想不到比上面引用的那篇文章更好的方法證明整件事情，而那篇文章主要是在 Haskell 底下談的。

--
我還是先多寫一點中文吧，讓附近的人比較容易看…

大三上回顧 ─ Current View about Computer Science

FLOLAC '07 對我顯然是個重大的轉捩點。幸好成行了，不然我不知道會浪費多少時間。那感覺就好像是突然往後一看，一大片閃閃發光的領域就在那裡等著我。之前我雖然對學校教的 CS 有親近之意（相對於其他學門），但始終達不到完全的共鳴。這次不一樣，我看到 program derivation、Curry-Howard isomorphism，馬上就叫出來 "it should be done this way!" 沒意外的話，我就要朝這個方向走下去了。

長久以來困擾 (theoretical) computer scientists 的一個問題，就是 Mathematics 和 Computer Science 的關係。（或許稱後者為 "Computing Science" 更恰當，不過我就先把它們當作同義詞用了。）Knuth 在《Selected Papers on Computer Science》裡面曾經用他獨特的方法尋找這個問題的解答，但也沒能把兩者異同說得足夠清楚。（感覺上 Knuth 對於哲學式論證並不在行 XD。）對一個剛入門的小朋友而言，有時候 CS 和 Math 分得很開，有時候又會出現像 "Mathematics of Program Construction" 這種混合的詞彙，非常混淆。我當然還沒找到終極的答案，不過我發現若採用某種二元論的思維，很多問題就能解釋清楚。正常的大學生應該都已經對「正式與直覺」、「語法和語意」這類的二元概念有一些體會，我這裡想強調的是「純粹概念」和「操作工具、方法」之間的交互關係。從這種觀點來看，CS 和 Math 在「方法工具」上沒有什麼區別（deduction, abstraction, ...），但是兩者操作的「純粹概念」我認為是可以區分的。數學所探討的純粹概念恐怕數學家也很難給一個內涵上（intensional）的界定，但他們顯然不只專注於「有窮的機械式計算步驟」。CS 的各個分支就比較清楚，理路上（至少實作上）大都可以從 "algorithm" 發展出去。（這樣的說法或許是受了 Knuth 的影響。）"Algorithm" 的相關概念是不是數學概念的子集還有待爭辯，不過數學家發展的工具縱深真的很夠，拿過來 CS 這邊試著套套看一定很有意思。

最後以一點關於「證明格式」的討論作結。這學期我寫的圖論證明比較偏向白話敘述和畫圖示意，比較少用 set comprehension 或其他的符號來寫。我個人不覺得這樣比較不嚴謹，因為「嚴謹」應該是在「純粹概念」那邊講的，不一定要訴諸符號（這是「方法工具」的一部份），只是有些時候符號確實能表達得比較好。更何況，如果把嚴謹定義成 "formal"，每篇數學論文都該用 theorem prover 來寫才對，至少也該用 Leslie Lamport 提倡的那種 structural proof 格式，那才有點 "formal" 的味道。我以後會遇到的、要寫的符號顯然不會太少，一般的證明還是寫得白話一點吧。

--
以後記得要趁文思泉湧的時候（i.e., 期末考）一口氣把回顧寫完 XD。

Model Checking

2007 年的 Turing Award 得主前幾天剛剛公佈，這次頒給三個人 Edmund M. Clarke, E. Allen Emerson, and Joseph Sifakis，他們做的是 model checking。這門神奇的學問剛好在去年 FLOLAC '07 王老師開了一門課介紹。我們玩的第一套軟體是 Spin，可以用指定的程式語言描述一個 protocol，然後自動驗證這套 protocol 是否滿足給定的 linear temporal logic formulae。Temporal logic 是一類帶有時間描述與推論的邏輯，在這類邏輯下我們可以表示「永遠」、「終會」、「在某事成真前」的概念，所以就可以表述像「永遠不可能有兩個以上的 processes 都在 critical region 裡面」、「永遠都有 process 終究能夠進入 critical region」的陳述。我們試了 Peterson's algorithm 和 bakery algorithm（among others），後者的一般實作還被抓出錯誤（這時會把導致錯誤的執行方式顯示出來！），因為原始的 bakery algorithm 用的號碼牌必須是 unbounded integers。總之真的是很神奇（也很難，我把它封為 FLOLAC'07-hard XD），拿個 Turing Award 滿正常的 XD。

--
底層用到 automata theory 喔！

Computational Modeling

This course seems to be extremely interesting (and philosophical, I guess)!

--
And of course it is not an NTU course...

Algebraic Information Systems

讀資訊系統工程的東西讀了幾年，大部分人應該都已經發現其中類似的情境、原則、解法很多，一副很適合用代數方法 ¹ 去統合的樣子。我可以想像前述的情境、原則、解法就分別對應到代數系統的假設、定理、和概念定義，然後 Fundamental Theorem of Software Engineering ² 在這個代數系統內就真的成為一個基本定理（after reformulation, of course）。有志之士可以試試看這條進路，當然必須冒著被後世所有資訊系學生在期考時痛罵的風險 XD。

註：

1. 我會在大三上回顧裡面很簡單地描述 squiggolists 把代數方法運用在 algorithm design 上面的成果，覺得代數和編程沒什麼關係的人屆時可以看看。
2. 順帶一提，FTSE 這篇 blog 很有趣，例如可以看到那時候我已經察覺到 Curry-Howard isomorphism 了。屆時可以和回顧對照一下。

--
衷心希望我可以修到代數導論（i.e., 不要延畢）XD。

The Church-Turing Thesis

Stanford Encyclopedia of Philosophy 收錄的條目品質都很不錯（這是 by induction XD，關於歸納法的問題可參考我寫的〈Hume's Dilemma〉或 SEP 上處理更為細緻的〈The Problem of Induction〉）。其中對 Church-Turing Thesis 的描述與澄清相當值得一讀 ─ 如果你想知道這個 thesis 到底說了什麼，以及沒說什麼。

--
《Gödel, Escher, Bach》最後面也用滿多篇幅處理 Church-Turing Thesis。

Nonuniformity

After the frustration of two times of rewriting subsides, I feel more confident of being a Computer Science student now. Knuth said these in his article Algorithms in Modern Mathematics and Computer Science:

One of the most striking differences that I have observed between the habits of computer scientists and traditional mathematicians is that a computer scientist tends to be much more willing to deal with a multitude of quite different cases. Data structures in computer science needn't be homogeneous, and algorithms can involve many different kinds of steps. [...] Sometimes this tolerance for diversity is a weakness of computer scientists, because we don't try as hard as we should to find uniform laws. But sometimes it is a strength, because we can deal fluently with concepts that are inherently nonuniform.

If you look into the literate program of TOY86 assembler, you'll find that there are many, many case analyses. I think it's partly because of the ad hoc nature of this program. The hardest time is when writing documentation for these case analyses, since I just have to say "if... otherwise... and if... otherwise...," quite annoying. XD

--
I've sent a letter to cyy while keeping finding and fixing bugs.

解答

趕在今天下午五、六節把解答寫完了。七、八節及時把整年的 C++ Programming 收尾，交付「考題」，就結束嘍。

--
經驗值上升 XD。

考題

我自己出的 XD。範圍是 C++ 的 data abstraction、object-oriented programming、generic programming，以及 TOY slides，其實就是這學期的全部內容。TOY slides 不知不覺佔了 30 分 XD。因為是 written exam，我就不特別考實作（那留給上機考），著重在概念與其間連結，rather philosophical XD。

切換到學生角度：這份考卷寫起來可能會很痛苦，因為每一題好像都要寫不少字 XD。

--
出過一次就知道好題目有多難出了 XD。

熱血對話

昨晚與 Yen3 有一番熱血賁張的對話，摘錄重點句於下（額外加入標點，並適度省略 "XD" XD）：

• 如果以後寫教科書，記得提供投影片，這樣就會賣了，然後習題多出一點 XD。Primer 就是沒提供投影片，才那麼少人用 XD。
• 教 C 就用 K&R，教 C++ 就用 C++ Primer，這是完美的選擇 XD。
• C++ 要教到適當程度，應該要一年，只用半年會噎死 ─ 吃太快就噎死了 XD。C 的話，半年剛剛好。有 C 的基礎，半年也可以把 Java 精要教完，前提是 C 的基礎夠穩，不用一直回頭補強 XD。
• 計概改成一年，教 CS 各個學門的核心概念，並著重其間的有機聯繫，這樣大二開始，讀每一門課都知道這片拼圖在整幅 CS big picture 的哪個方位。喔，實在有夠理想 XD。
• 所以像 cyy 上半學期講的東西就拿到計概去講，TOY 拿到計概去。組合語言就和系統程式一起上就好了（JK 注：我心中想的系統程式是講 assembler、linker 的那種系統程式），合併成一門課。（Yen3：這在我們系是一起上的。）是啊，有先例，顯然很合理 XD。
• 而且計概的角色非常重要，脈要讓他通，大一就通 XD。（Yen3：重點是計概上那麼難，對於完全沒碰過電腦的人是否有辦法吸收？）不用進到 detail，核心概念就行了，像 pipeline 一定是留到計算機結構專門去上。又一個很好的例證就是，cyy 所教有關 TOY machine 的部分，都是 Princeton 的計概內容（JK 注：其實不完全是，後面的 assembly 部份是 cyy 自己做的 XD）。（Yen3：但是可以稍微提一下。）嗯，exactly XD。
• （Yen3：事實上這要建立在一個假設之上 ─ 學生回家都要很認真才行。）也沒空去顧不認真的學生？XD（Yen3：是很沒空。上到最後剩幾個認真的？）反正上課內容就是這樣，最後要不要請調分大神，端看老師如何決定。基本上就是隨機客的做法：上課就上他應該上的，考試考他認為應該考的，最後調分就是了，所以不是大問題 XD。
• 我知道一般的計概課為什麼效率不彰了 ─ 不夠具體。引進 TOY machine 這種東西會特別有效。
• 計概可以講得讓人熱血賁張的啊，很多概念其實都很漂亮的。看，從 TOY machine 那麼簡單的 model，手動輸入程式，馬上就看到 OS 的第一個功能：把程式載入記憶體。然後 multi-process 進來，我們又不想把事情弄複雜，所以 context-switch 讓 process 以為 CPU 是他一個人的，virtual memory system 讓 process 以為 memory 整塊都是他的。這都是 OS 在做的嘛，一層很漂亮的 ABSTRACTION 啊！喔，我想到這裡就一陣 thrilled XD。
• 他們（JK 注：指 Princeton）看起來是先把 programming（JK 注：Java programming）教完才開始計概，從 TOY 開始。不過我還是認為從 C 下手比較好，Java VM 其實很難解釋，不夠單純。他（JK 注：指 C language）直接溝通高階語言和計算機架構，所以從那個點切入很自然。（Yen3：C 真是一個美麗的東西。）是啊，我現在感到熱血沸騰 XD。（Yen3：兄弟兩點了 XD。）
• 我好像比較基本的課都想教教看，比較專業的就留給內行。天啊，我好想上我自己開的計概 XD。
• 概論課如果教得好，總是一種享受，因為不用顧慮細節，專心欣賞那些核心概念之美就好了。
• 這一切都是 cyy 觸發的 XD。
• 最大問題恐怕就是制度問題，還有你剛剛說的，有沒有老師願意推。而且那些熱血老師如果沒得到適當回應，苦撐在那裡也是很辛苦。

--
計概最完美的形式恐怕就是聰明那種熱血沸騰的風格了 XD。

音樂與程式

古典樂與流行樂雖然同樣帶給人快樂，但前者的元素豐富、組織精巧，而成其為經典。一般流行樂相較之下結構單純，雖然能讓聽者不花什麼力氣就能享受，卻也無法流傳太久。

程式亦如是。Knuth 曾說：

Some programs are elegant, some are exquisite, some are sparkling. My claim is that it is possible to write grand programs, noble programs, truly magnificent ones!

我相信 TeX typesetting system 就是這樣的程式。程式乃演算法之具體表述，是抽象的計算理論與實體計算機架構交會之處。真正優雅精緻、堂皇高貴壯麗的程式，是將涉及的演算法化為迎合實體機器效率需求的具體實作，並以有條不紊、充滿美感的方式組織成一個整體。當然，理論上無法確保一個程式全無臭蟲，所以測試仍是必要的，然而在那之前若能以邏輯推演證明程式（i.e. underlying algorithm）正確，那會使人對這個程式更加有信心。曾有人問 Knuth "what distinguishes a computer scientist and a computer programmer"，Knuth 的前半段回答是

The difference between a computer programmer and a computer scientist is a job-title thing. ... To me, "computer programmer" is an honorable term, but to some people a computer programmer is somebody who just follows instructions without understanding what he’s doing, one who just knows how to get through the idiosyncrasies of some language. ...

我想，要成為一位 "real" programmer，必要條件就是 CS 任督二脈通行無礙。我所說的任脈就是當代電腦的發展脈絡，督脈則是計算理論及衍生而出的演算法設計與分析。一般程式員寫的一般程式雖然有其實用價值，但無法成為經典，情況和古典樂 vs. 流行樂差不多。

Knuth 下面這句充滿霸氣的話就很有「得道程式員」的風範，我很希望哪天也能信心滿滿地說出這種話 XD：

Beware of bugs in the above code; I have only proved it correct, not tried it.

In some way，「資訊系就是學寫程式」這個述句被證成了，不過箇中道理實非外人所想的那麼單純，情況或許和畢派教義「萬事萬物皆可共度」被量子物理證成有類似之處。

--
我記得 Dijkstra 好像也有此類論述，不過我目前的焦點都放在 Knuth 身上，暫時顧不到 Dijkstra XD。

Fundamental Theorem of Software Engineering

系統程式下星期考試，基本上就是拿內功出來硬拚 XD。程式寫了幾年，最重要的原則大概就是 principle of abstraction 和 principle of indirection，後者 Andrew Koenig 稱之為 Fundamental Theorem of Software Engineering: "All problems can be solved by introducing an extra level of indirection"。一個重要例子大概就是 OO polymorphism，abstraction 不用說，因為多型延伸自 data "abstraction"，而 indirection 出現在 dynamic binding 的實作（一般是 pointer indirection）。然而，principle of abstraction 似乎可由 principle of indirection 證成，所以稱後者為 FTSE 或許十分恰當。

數學處理的 entity，本質其實和 program 很像（相對於自然科學處理的東西），也因此 principle of abstraction 和 principle of indirection 都可以在數學的脈絡中找到，例如定理的運用即 principle of abstraction ─ 召喚 Arzela-Ascoli 定理時，我們可不需要重新把定理證明一次，雖然我們知道怎麼證。然而，數學不像 CS 必須把事情教給機器，CS 無論在哪個抽象層都必須以某種方式把所有細節展開（因為機器永遠在最底層的細節上運算），數學不需要。因此 CS 任脈通往 software engineering，但數學沒有 theorem engineering，也不需要發展此類學問。（當然，數學系學生很重要的工作就是確定「必要時」也能把細節展開。）

我們現在把「計算」定義在 Turing machine 上，即某種形式符號操作（formal symbol manipulation）。接著我們造出實際操作符號的機器，即當代電腦，computer architecture 研究的就是如何造出這部機器，並使這部機器在效能與開銷間取得平衡。接著任脈往軟體工程發展，從組合語言到軟體工程方法論，因為我們需要可靠的方法處理規模急遽增大但不缺失細節的符號操作（到這裡 universal Turing machine 的精神還在：「符號操作」（program）可以用「符號」（data）表示）。而居於軟體工程核心地位的原則，我（目前）相信就是 FTSE。

--
數位電子學期中考就靠外功硬撐了 Orz。

---

摘錄一小段 Knuth〈Algorithms in Modern Mathematics and Computer Science〉支持上述論調：

At times when I try to come to grips with this question, I find myself almost convinced that algorithmic thinking is really like mathematical thinking, only it concentrates on more "difficult" things. But at other times I have just the opposite impression, that somehow algorithms hit only the "simpler" kinds of mathematics. Clearly such an approach leads only to confusion and gets me nowhere.

While pondering these things recently, I suddenly remembered the collection of expository works called Mathematics: Its Content, Methods, and Meaning, so I reread what A. D. Aleksandrov had to say in his excellent introductory essay. Interestingly enough, I found that he made prominent mention of al-Khwârizmî. Aleksandrov listed the following characteristic features of mathematics:

• Abstractness, with many levels of abstraction.
• Precision and logical rigor.
• Quantitative relations.
• Broad range of applications.

Unfortunately, however, all four of these features seem to be characteristic also of computer science. Is there really no difference between computer science and mathematics?

A Plan

...

演算之美

喔喔，這標題和介紹很吸引我啊！而且天時地利人和，下星期五上完高等微積分吃個中餐剛好到系館免費入場，I see no reason not to go！XD

--
不過 103 會塞爆吧 XD。

Bernstein Polynomial

雖然 Bernstein polynomial 看起來已經是很真實、「可以摸到」的函數了，但是用數學家的方式看 Bernstein polynomial 還是有點飄渺 XD。給一個閉區間上的連續函數和誤差 epsilon，若要造出一個每一點誤差都小於 epsilon 的 Bernstein polynomial，首先要確定 n 的值，而 n 的值取決於 uniform continuous 的 delta 值（among other values），這個 delta 值是用「[a, b] 為 compact」造出 finite subcovering 得到，而促成「[a, b] 為 compact」的 Heine-Borel 定理完全是存在式的定理。這個狀況和 Knuth 在〈Computer Science and its Relation to Mathematics〉（《Selected Papers on Computer Science》，p.8）描述的真實故事如出一轍：

The following true story is perhaps the best way to explain the distinction I have in mind. Some years ago I had just learned a mathematical theorem from which it followed that any two n \times n matrices A and B of integers have a "greatest common right divisor" D. This means that D is a right divisor of A and of B, i.e., A = A' D and B = B' D for some integer matrices A' and B', and that every common right divisor of A and B is a right divisor of D. So I wondered how to calculate the greatest common right divisor of two given matrices. A few days later I happened to be attending a conference where I met the mathematician H. B. Mann, and I felt that he would know how to solve this problem. I asked him and he did indeed know the correct answer; but it was a mathematician's answer, not a computer scientist's answer! He said, "Let R be the ring of of n \times n integer matrices; in this ring, the sum of two principal left ideals is principal, so let D be such that

  RA + RB = RD.

Then D is the greatest common right divisor of A and B." This formula is certainly the simplest possible one; we need only eight symbols to write it down. And it relies on rigorously-proved theorems of mathematical algebra. But from the standpoint of a computer scientist, it is worthless, since it involves constructing the infinite sets RA and RB, taking their sum, then searrching through infinitely many matrices D until finding one for which this sum matches the infinite set RD.

Knuth 後來倒有找到解決這個問題的 "computer scientist's answer"。Bernstein polynomial 在圖學的 Bézier curve 上好像也有一些應用，according to Wikipedia。（然後才突然想到，Bernstein polynomial 的形式的確和 Bézier curve 有點像，都有二項式的痕跡 XD。）

--
其實我之前很多關於 CS 的想法都可以在 Knuth 這本書裡看到類似敘述 XD。

CiFM

Computation is formal manipulation.

Form 與 semantics 之間看似有道不可跨越的鴻溝。這對於相信心智只是「某種複雜計算」的唯物論者是個重擊，但堅持這道鴻溝不可跨越的人也得設法說明這道鴻溝為何（如何）存在。

很快就找到一篇持反論的文章：〈Computation Is Just Interpretable Symbol Manipulation: Cognition Isn't〉。才剛看完 abstract，看完有立刻的感想再說 XD。

--
然後我的數位電子學現在都只能支離破碎地從形式上去操作 Orz。

---

簡單看完幾段，Harnad 這篇文章是用哲學的論證方式去寫的，有些地方我覺得還可以再質疑 XD。不過這是快速反應下的感想 XD。Dijkstra 也有一篇〈What Computing Science is about〉，也可以看看。其中有一句 "During its first decade, Computing Science suffered, in fact, from an 'identity crisis' " 還滿貼切的 XD。