如何設計一門語言（九）——類型

類型是了解編程語言的重要一環。就算是你喜歡動態類型語言，為了想實現一個靠譜的東西，那也必須了解類型。舉個簡單的例子，我們都知道+和-是對稱的——當然這只是我們的愿望了，在javascript里面，"1"+2和"1"-2就不是一回事。這就是由于不了解類型的操作而犯下的一些滑稽的錯誤。什么，你覺得因為"1"的類型是string所以"1"+2就應該是"12"？啐！"1"的類型是(string | number)，這才是正確的做法。

了解編程語言的基本原理并不意味著你一定要成為一名編譯器的前端，正如同學習Haskell可以讓你的C++寫得更好一樣，如果你知道怎么設計一門語言，那遇到語言里面的坑，你十有八九可以當場看到，不會跳進去。當然了，了解編程語言的前提是你是一個優秀的程序員，至少要寫程序，對吧。于是我這里推薦幾門語言是在此之前要熟悉的。編程語言有好多種，每一種都有其代表作，為了開開眼界，知道編程語言可以設計成什么樣子，你至少應該學會：

1. C++
2. C#
3. F#
4. Haskell
5. Ruby
6. Prolog

其實這一點也不多，因為只是學會而已，知道那些概念就好了，并不需要你成為一個精通xx語言的人。那為了了解類型你應該學會什么呢？沒錯——就是C++了！很多人可能不明白，為什么長得這么難看的C++竟然有這么重要的作用呢？其實如果詳細了解了程序設計語言的基本原理之后，你會發現，C++在除了兼容那個可憐的C語言之外的那些東西，是設計的非常科學的。當然現在講這些還太早，今天的重點是類型。

如果你們去看相關的書籍或者論文的話，你們會發現類型這個領域里面有相當多的莫名其妙的類型系統，或者說名詞。對于第一次了解這個方面的人來說，熟練掌握Haskell和C++是很有用的，因為Haskell可以讓你真正明白類型在程序里面的重要做喲的同時。幾乎所有流行的東西都可以在C++里面找到，譬如說：

1. 面向對象→class
2. polymorphic type→template
3. intersection type→union / 函數重載
4. dependent type→帶數字的模板類型
5. System F→在泛型的lambda表達式里面使用decltype（看下面的例子）
6. sub typing的規則→泛型lambda表達式到函數指針的隱式類型轉換

等等等等，因有盡有，取之不盡，用之不竭。你先別批判C++，覺得他東西多所以糟糕。事實是，只要編譯器不用你寫，那一門語言是不可能通過拿掉feature來使它對你來說變得更牛逼的。不知道為什么有那么多人不了解這件事情，需要重新去念一念《形式邏輯》，早日爭取做一個靠譜的人。

泛型lambda表達式是C++14（沒錯，是14，已經基本敲定了）的內容，應該會有很多人不知道，我在這里簡單地講一下。譬如說要寫一個lambda表達式來計算一個容器里所有東西的和，但是你卻不知道容器和容器里面裝的東西是什么。當然這種情況也不多，但是有可能你需要把這個lambda表達使用在很多地方，對吧，特別是你#include <algorithm>用了里面超好用的函數之后，這種情況就變得常見了。于是這個東西可以這么寫：

auto lambda = [](const auto& xs)
{
    decltype(*xs.begin()) sum = 0;
    for(auto x : xs)
    {
        sum += x;
    }
    return sum;
};

于是你就可以這么用了：

vector<int> a = { ... };
list<float> b = { ... };
deque<double> c = { ... };

int sumA = lambda(a);
float sumB = lambda(b);
double sumC = lambda(c);

然后還可以應用sub typing的規則把這個lambda表達式轉成一個函數指針。C++里面所有中括號不寫東西的lambda表達式都可以被轉成一個函數指針的，因為他本來就可以當成一個普通函數，只是你為了讓業務邏輯更緊湊，選擇把這個東西寫在了你的代碼里面而已：

doube(*summer)(const vector<double>&);
summer = lambda;

只要搞明白了C++之后，那些花里胡俏的類型系統的論文的概念并不難理解。他們深入研究了各種類型系統的主要原因是要做系統驗證，證明這個證明那個。其實編譯器的類型檢查部分也可以當成是一個系統驗證的程序，他要檢查你的程序是不是有問題，于是首先檢查系統。不過可惜的是，除了Haskell以外的其他程序語言，就算你過了類型系統檢查，也不見得你的程序就是對的。當然了，對于像javascript這種動態類型就罷了還那么多坑（ruby在這里就做得很好）的語言，得通過大量的自動化測試來保證。沒有類型的幫助，要寫出同等質量的程序，需要花的時間要更多。什么？你不關心質量？你不要當程序員了！是因為老板催得太緊？我們Microsoft最近有招聘了，快來吧，可以慢慢寫程序！

不過正因為編譯器會檢查類型，所以我們其實可以把一個程序用類型武裝起來，使得錯誤的寫法會變成錯誤的語法被檢查出來了。這種事情在C++里面做尤為方便，因為它支持dependent type——好吧，就是可以在模板類型里面放一些不是類型的東西。我來舉一個正常人都熟練掌握的例子——單位。

一、類型檢查（type rich programming）

我們都知道物理的三大基本單位是米、秒和千克，其它東西都可以從這些單位拼出來（大概是吧，我忘記了）。譬如說我們通過F=ma可以知道力的單位，通過W=FS可以知道功的單位，等等。然后我們發現，單位之間的關系都是乘法的關系，每個單位還帶有自己的冪。只要弄清楚了這一點，那事情就很好做了。現在讓我們來用C++定義單位：

template<int m, int s, int kg>
struct unit
{
    double value;

    unit():value(0){}
    unit(double _value):value(_value){}
};

好了，現在我們要通過類型系統來實現幾個操作的約束。對于乘除法我們要自動計算出單位的同時，加減法必須在相同的單位上才能做。其實這樣做還不夠完備，因為對于任何的單位x來講，他們的差單位Δx還有一些額外的規則，就像C#的DateTime和TimeSpan一樣。不過這里先不管了，我們來做出加減乘除幾個操作：

template<int m, int s, int kg>
unit<m, s, kg> operator+(unit<m, s, kg> a, unit<m, s, kg> b)
{
    return a.value + b.value;
}

template<int m, int s, int kg>
unit<m, s, kg> operator-(unit<m, s, kg> a, unit<m, s, kg> b)
{
    return a.value - b.value;
}

template<int m, int s, int kg>
unit<m, s, kg> operator+(unit<m, s, kg> a)
{
    return a.value;
}

template<int m, int s, int kg>
unit<m, s, kg> operator-(unit<m, s, kg> a)
{
    return -a.value;
}

template<int m1, int s1, int kg1, int m2, int s2, int kg2>
unit<m1+m2, s1+s2, kg1+kg2>operator*(unit<m1, s1, kg1> a, unit<m2, s2, kg2> b)
{
    return a.value * b.value;
}

template<int m1, int s1, int kg1, int m2, int s2, int kg2>
unit<m1-m2, s1-s2, kg1-kg2>operator/(unit<m1, s1, kg1> a, unit<m2, s2, kg2> b)
{
    return a.value / b.value;
}

但是這個其實還不夠，我們還需要帶單位的值乘以或除以一個系數的代碼。為什么不能加減呢？因為不同單位的東西本來就不能加減。系數其實是可以描寫成unit<0, 0, 0>的，但是為了讓代碼更緊湊，于是多定義了下面的四個函數：

template<int m, int s, int kg>
unit<m, s, kg> operator*(double v, unit<m, s, kg> a)
{
    return v * a.value;
}

template<int m, int s, int kg>
unit<m, s, kg> operator*(unit<m, s, kg> a, double v)
{
    return a.value * v;
}

template<int m, int s, int kg>
unit<m, s, kg> operator/(double v, unit<m, s, kg> a)
{
    return v / a.value;
}

template<int m, int s, int kg>
unit<m, s, kg> operator/(unit<m, s, kg> a, double v)
{
    return a.value / v;
}

我們已經用dependent type之間的變化來描述了帶單位的量的加減乘除的規則。這看起來好像很復雜，但是一旦我們加入了下面的新的函數，一切將變得簡單明了：

constexpr unit<1, 0, 0> operator""_meter(double value)
{
    return value;
}

constexpr unit<0, 1, 0> operator""_second(double value)
{
    return value;
}

constexpr unit<0, 0, 1> operator""_kilogram(double value)
{
    return value;
}

constexpr unit<1, -2,1> operator""_N(double value) // 牛不知道怎么寫-_-
{
    return value;
}

constexpr unit<2, -2,1> operator""_J(double value) // 焦耳也不知道怎么寫-_-
{
    return value;
}

然后我們就可以用來寫一些神奇的代碼了：

auto m = 16_kilogram; // unit<0, 0, 1>(16)
auto s = 3_meter; // unit<1, 0, 0>(3)
auto t = 2_second; // unit<0, 1, 0>(2)
auto a = s / (t*t); // unit<1, -2, 0>(3/4)
auto F = m * a; // unit<1, -2, 1>(12)

下面的代碼雖然也神奇，但因為違反了物理定律，所以C++編譯器決定不讓他編譯通過：

auto W = F * s; // unit<2, -2, 1>(36)
auto x = F + W; // bang!

這樣你還怕你在物理引擎里面東西倒騰來倒騰去然后公式手抖寫錯了嗎？類似的錯誤是不可能發生的！除非系數被你弄錯了……如果沒有unit，要用原始的方法寫出來：

double m = 16;
double s = 3;
double t = 2;
double a = s / (t*t);
double F = m * a;
double W = F * s;
double x = F + W; //????

時間過得久了以后，根本不知道是什么意思了。所以為了解決這個問題，我們得用應用匈牙利命名法（這個不是那個臭名昭著的你們熟悉的傻逼（系統）匈牙利命名法）。我舉個例子：

string dogName = "kula";
Person person;
person.name = dogName;

這個代碼大家一看就知道不對對吧，這就是應用匈牙利命名法了。我們通過給名字一個單位——狗的——來讓person.name = dogName;這句話顯得很滑稽，從而避免低級錯誤的發生。上面的unit就更進一步了，把這個東西帶進了類型系統里面，就算寫出來不滑稽，編譯器都會告訴你，錯誤的東西就是錯誤的。

然后大家可能會問，用unit這么寫程序的性能會不會大打折扣呀？如今已經是2013年了，靠譜的C++編譯器編譯出來的代碼，跟你直接用幾個double倒騰來倒騰去的代碼其實是一樣的。C++比起其他語言的抽象的好處就是，就算你要用來做高性能的程序，也不怕因為抽象而喪失性能。當然如果你使用了面向對象的技術，那就另當別論了。

注，上面這段話我寫完之后貼到了粉絲群里面，然后九姑娘跟我講了很多量綱分析的故事，然后升級到航空領域的check list，最后講到了醫院把這一技術引進了之后有效地阻止了手術弄錯人等嚴重事故。那些特別靠譜的程序還得用C++來寫，譬如說洛克希德馬丁的戰斗機，NASA的衛星什么的。

人的精力是有限的，需要一些錯誤規避來防止引進低級的錯誤或者負擔，保留精力解決最核心的問題。很多軟件都是這樣的。譬如說超容易配置的MSBuild、用起來巨爽無比的Visual Studio，出了問題反正用正版安裝程序點一下repair就可以恢復的windows，給我們帶來的好處就是——保留精力解決最核心的問題。編程語言也是如此，類型系統也是如此，人類發明出的所有東西，都是為了讓你可以把更多的精力放在更加核心的問題上，更少的精力放在周邊的問題上。

但是類型到處都出現其實也會讓我們程序寫起來很煩的，所以現代的語言都有第二個功能，就是類型推導了。

二、類型推導

這里講的類型推導可不是Go語言那個半吊子的:=賦值操作符。真正的類型推導，就要跟C++的泛型lambda表達式、C#的linq語法糖，或者Haskell的函數一樣，要可以自己計算出模板的類型參數的位置或者內容，才能全方位的實現什么類型都不寫，都還能使用強類型和type rich programming帶來的好處。C++的lambda表達式上面已經看到了，所以還是從Haskell一個老掉牙的demo開始講起吧。

今天，我們用Haskell來寫一個merge sort：

merge [] [] = []
merge [] xs = xs
merge xs [] = xs
merge (x:xs) (y:ys) = if x<y then x:(merge xs (y:ys)) else y:(merge (x:xs) ys)

mergeSort [] = []
mergeSort xs = merge (mergeSort a) (mergeSort b)
    where
        len = length xs
        a = take $ len `div` 2 $ xs
        b = drop $ len - len `div` 2 $ xs

我們可以很清楚的看出來，merge的類型是[a] –> [a] –> [a]，mergeSort的類型是[a] –> [a]。到底編譯器是怎么計算出類型的呢？

1. 首先，[]告訴我們，這是一個空列表，但是類型是什么不知道，所以他是forall a –> [a]。所以merge [] [] = []告訴我們，merge的類型至少是[a] –> [b] –> [c]。
2. 其次，merge []  xs = xs告訴我們，merge的類型至少是[d] –> e –> e。這個類型跟[a]->[b]->[c]求一個交集就會得到merge的更準確的類型：[a] –> [b] –> [b]。
3. 然后，merge xs [] = []告訴我們，merge的類型至少是f –> [g] –> f。這個類型跟[a] –> [b] –> [b]求一個交集就會得到merge的更準確的類型：[a] –> [a] –> [a]。
4. 最后看到那個長長的式子，根據一番推導之后，會發現[a]->[a]->[a]就是我們要的最終類型了。
5. 只要把相同的技術放在mergeSort上面，就可以得到mergeSort的類型是[a]->[a]了。

當然對于Haskell這種Hindley-Milner類型系統來說，只要我們在代碼里面計算出所有類型的方程，然后一個一個去解，最后就可以收斂到一個最準確的類型上面了。倘若我們在迭代的時候發現收斂之后無解了，那這個程序就是錯的。這種簡單粗暴的方法很容易構造出一些只要人夠蛋定就很容易使用的語言，譬如說Haskell。

Haskell看完就可以來看C#了。C#的linq真是個好東西啊，只要不把它看成SQL，那很多事情都可以表達的。譬如說是個人都知道的linq to object啦，后面還有linq to xml，linq to sql，reactive programming，甚至是parser combinator等等。一個典型的linq的程序是長這個樣子的：

var w = 
    from x in xs
    from y in ys
    from z in zs
    select f(x, y, z);

光看這個程序可能看不出什么來，因為xs、ys、zs和f這幾個單詞都是沒有意義的。但是linq的魅力正在這里。如果from和select就已經強行規定了xs、ys、zs和f的意思的話。那可擴展性就全沒有了。因此當我們看到一個這樣的程序的時候，其實可以是下面這幾種意思：

W f(X x, Y y, Z z);

var /*IEnumerable<W>*/w = 
    from /*X*/x in /*IEnumerable<X>*/xs
    from /*Y*/y in /*IEnumerable<Y>*/ys
    from /*Z*/z in /*IEnumerable<Z>*/zs
    select f(x, y, z);

var /*IObservable<W>*/w = 
    from /*X*/x in /*IObservable<X>*/xs
    from /*Y*/y in /*IObservable<Y>*/ys
    from /*Z*/z in /*IObservable<Z>*/zs
    select f(x, y, z);

var /*IParser<W>*/w = 
    from /*X*/x in /*IParser<X>*/xs
    from /*Y*/y in /*IParser<Y>*/ys
    from /*Z*/z in /*IParser<Z>*/zs
    select f(x, y, z);

var /*IQueryable<W>*/w =
    from /*X*/x in /*IQueryable<X>*/xs
    from /*Y*/y in /*IQueryable<Y>*/ys
    from /*Z*/z in /*IQueryable<Z>*/zs
    select f(x, y, z);

var /*?<W>*/w = 
    from /*X*/x in /*?<X>*/xs
    from /*Y*/y in /*?<Y>*/ys
    from /*Z*/z in /*?<Z>*/zs
    select f(x, y, z);

相信大家已經看到了里面的pattern了。只要你有一個?<T>類型，而它又支持linq provider的話，你就可以把代碼寫成這樣了。

不過我們知道，把程序寫成這樣并不是我們編程的目的，我們的目的是要讓程序寫得讓具有同樣知識背景的人可以很快就看懂。為什么要看懂？因為總有一天你會不維護這個程序的，這樣就可以讓另一個合格的人來繼續維護了。一個軟件是要做幾十年的，那些只有一兩年甚至只有半年生命周期的，只能叫垃圾了。

那現在讓我們看一組有意義的linq代碼。首先是linq to object的，求一個數組里面出現最多的數字是哪個：

var theNumber = (
    from n in numbers
    group by n into g
    select g.ToArray() into gs
    order by gs.Length descending
    select gs[0]
    ).First()

其次是一個parser，這個parser用來得到一個函數調用表達式：

IParser<FunctionCallExpression> Call()
{
    return
        from name in PrimitiveExpression()
        from _1 in Text("(")
        from arguments in
            many(
                Expression().
                Text(",")
            )
        from _2 in Text(")")
        select new FunctionCallExpression
        {
            Name = name,
            Arguments = arguments.ToArray(),
        };
}

我們可以看到，一旦linq表達式里面的元素都有了自己的名字，就不會跟上面的xyz的例子一樣莫名其妙了。那這兩個例子到底為什么要用linq呢？

第一個例子很簡單，因為linq to object就是設計來解決這種問題的。

第二個例子就比較復雜一點了，為什么好好地parser要寫成這樣呢？我們知道，parser時可能會parse失敗的。一個大的parser，里面的一些小部件失敗了，那么大parser就要回滾，token stream的當前光標也要回滾，等等需要類似的一系列的操作。如果我們始終都讓這些邏輯都貫穿在整個parser里面，那代碼根本不能看。于是我們可以寫一個linq provider，讓SelectMany函數來處理所有的回滾操作，然后把parser寫成上面這個樣子。上面這個parser的所有的in左邊是臨時變量，所有的in右邊剛好組成了一個EBNF文法：

PrimitiveExpression "(" [Expression {"," Expression}] ")"

最后的select語句告訴我們在所有小parser都parse成功之后，如何用parse得到的臨時變量來返回一顆語法樹。整個parsing的代碼就會非常的容易看懂。當然，前提是你必須要懂的EBNF。不過一個不懂EBNF的人，又如何能寫語法分析器呢。

那這跟類型推導有什么關系呢？我們會發現上面的所有linq的例子里面，除了函數簽名以外，根本沒有出現任何類型的聲明。而且更重要的是，這些類型盡管沒有寫出來，但是每一個中間變量的類型都是自明的。當然這有一部分歸功于好的命名方法——也就是應用匈牙利命名法了。剩下的部分是跟業務邏輯相關的。譬如說，一個FunctionCallExpression所調用的函數當然也是一個Expression了。如果這是唯一的選擇，那為什么要寫出來呢？

我們可以看到，正是因為有了類型推導，我們可以在寫出清晰的代碼的同時，還不需要花費那么多廢話來指定各種類型。程序員都是怕麻煩的，無論復雜的方法有多好，他總是會選擇簡單的（廢話，用復雜的那個不僅要加班修bug，還沒有漲工資。用簡單的那個，先讓他過了，bug留給下一任程序員去頭疼就好了——某web程序員如是說）。類型推導讓type rich programming的程序寫起來簡單了許多。所以我們一旦有了類型推導，就可以放心大膽的使用type rich programming了。

三、大道理

有了type rich programming，就可以讓編譯器幫我們檢查一些模式化的手都會犯的錯誤。讓我們重溫一下這篇文章前面的一段話：

人的精力是有限的，需要一些錯誤規避來防止引進低級的錯誤或者負擔，保留精力解決最核心的問題。很多軟件都是這樣的。譬如說超容易配置的MSBuild、用起來巨爽無比的Visual Studio，出了問題反正用正版安裝程序點一下repair就可以恢復的windows，給我們帶來的好處就是——保留精力解決最核心的問題。編程語言也是如此，類型系統也是如此，人類發明出的所有東西，都是為了讓你可以把更多的精力放在更加核心的問題上，更少的精力放在周邊的問題上。

這讓我想起了一個在微博上看到的故事：NASA的員工在推一輛裝了衛星的小車的時候，因為忘記看check list，沒有固定號衛星，結果衛星一推倒在了地上摔壞了，一下子沒了兩個億的美元。

寫程序也一樣。一個代表力的變量，只能跟另一個代表力的變量相加，這就是check list。但是我們知道，每一個程序都相當復雜，check list需要檢查的地方遍布所有文件。那難道我們在code review的時候可以一行一行仔細看嗎？這是不可能的。正因為如此，我們要把程序寫成“讓編譯器可以檢查很多我們可能會手抖犯的錯誤”的形式，讓我們從這些瑣碎的事情里面解放出來。

銀彈這種東西是不存在的，所以type rich programming能解決的事情就是防止手抖而犯錯誤。有一些錯誤不是手抖可以抖出來的，譬如說錯誤的設計，這并不是type rich programming能很好地處理的范圍。為了解決這些事情，我們就需要更多可以遵守的best practice了。

當然，其中的一個將是DSL——domain specific language，領域特定語言了。敬請關注下一篇，《如何設計一門語言（十）——DSL與建模》。