R·ex / Zeng

音遊狗、安全狗、攻城獅、業餘設計師、段子手、苦學日語的少年。

TypeScript 型別系統與函數語言程式設計

2020-02-04 20:37 開發
注意 本文釋出於 2331 天前，文中的一些內容可能已經過時。
AI 摘要

本文透過類比函數語言程式設計和 TypeScript 型別系統，展示瞭如何用 TypeScript 型別系統實現函數語言程式設計中的一些概念，例如斐波那契數列、最大公約數和超運算函式。文章從定義基本型別和代數系統開始，逐步構建了所需的工具型別，並討論了 TypeScript 型別系統在實現惰性計算和高階函式方面的侷限性，以及未來可能的解決方案。

背景

接觸 TypeScript 已經有一段時間了，這期間寫過一些複雜的型別（例如 這篇文章），我開始意識到：TypeScript 的型別系統寫起來就像函數語言程式設計一樣。去年某天，一個同事給我發了個連結，裡面講的是“TypeScript 型別系統的圖靈完備”，裡面的一些內容我還在努力理解到可以分享的程度，但一些程式碼差不多可以說明 TypeScript 型別系統跟函數語言程式設計的思想非常接近了。

前期知識

  • 掌握 TypeScript 的 基本型別，相信大家都瞭解；
  • 掌握 TypeScript 的 高階型別 和 泛型；
  • 非常熟悉 extends 和 infer 的使用；
  • “函數語言程式設計”的概念，相信大家都或多或少從公眾號裡面聽到過。
文中接下來所有跟 TypeScript 相關的部分，除非特殊說明，否則“函式”、“引數”均為新的概念，而非 TypeScript 中的“函式型別”、“引數列表”。

免責宣告

  1. 本文只是講述一個“理論上”可行的東西，並非推薦大家日常這樣寫。事實上，型別標註應當在適當精確的情況下儘可能簡潔（參考 @types/ramda 中對於 pipe 等函式的型別標註），因為需要提高效率；
  2. 本文的程式碼實現均只停留在實驗室階段，不考慮可能的效能問題。

從函數語言程式設計說起

函數語言程式設計有以下幾個特點：

  • 描述對映：函數語言程式設計並非描述解決問題的步驟，而是描述輸入與輸出的某種對映關係；
  • 不可變數：函數語言程式設計中沒有所謂的“變數賦值”，只有“引數繫結”，一旦某個引數綁定了一個值，則不能被重新繫結；
  • 無副作用：函式的輸出只依賴於輸入的引數，入參相同則返回值一定相同，函式執行過程中也不會對外界產生任何影響。
  • 惰性求值：只有真正用到的值才需要被計算；
  • 函式是一等公民：函式可以（甚至經常）作為另一個函式的引數和返回值，if 等語句也是函式；

例如下面的程式碼：

/**
 * 簡單的斐波那契數列
 */
function fibonacci(n) {
    return n <= 1 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}
/**
 * 簡單的歐幾里得演算法
 */
function gcd(x, y) {
    return y === 0 ? x : gcd(y, x % y);
}
/**
 * 超運算函式
 * https://en.wikipedia.org/wiki/Hyperoperation
 * n = 0: b+1（後繼）
 * n = 1: a+b（加法，即 b 次 a 的後繼）
 * n = 2: a*b（乘法，即 b 個 a 相加）
 * n = 3: a^b（乘方，即 b 個 a 相乘）
 * n = 4: a^a^a^...^a（超冪，即 b 個 a 不斷乘方）
 *        \_________/
 *          b 個 a
 * n = …………
 */
function hyperoperation(n, a, b) {
    return n === 0
        ? b + 1
        : n === 1 && b === 0
            ? a
            : n === 2 && b === 0
                ? b
                : n > 2 && b === 0
                    ? 1
                    : hyperoperation(n - 1, a, hyperoperation(n, a, b - 1));
}

由於函數語言程式設計經常出現遞迴，專門的語言（Haskell 等）會將尾遞迴轉換為迴圈，以提升執行效率；此外由於函數語言程式設計有“無副作用”的特性，也可以使用記憶化等方式避免重複計算。

TypeScript 泛型的例子

在 TypeScript 中，我們偶爾會用到泛型，比如下面的冷飯（你猜對了，這些都出自本文的第一個連結）：

type InstanceType<T> =
    T extends ConstructorType<infer R>
        ? R
        : T;
type RemovePropOptions<T> =
    NonNullable<
        T extends PropOptions<infer R>
            ? R
            : null
    >;
type OneOfTypePropOptions<T> =
    T extends ArrayType
        ? RemovePropOptions<ValueOf<T>>
        : T;
type ShapePropOptions<T> =
    T extends ShapeType
        ? { [K in keyof T]: RemovePropOptions<T[K]> }
        : T;

乍看上去，TypeScript 的泛型長得很像函式：定義泛型相當於定義一個函式，其中的 T、R 等型別變數可以被看作引數。但透過不斷嘗試外加查資料，我們最終都會意識到：在 TypeScript 的泛型定義中是無法自由的定義變數並賦值的，這意味著它跟我們日常寫的函式還有一些區別。

然鵝大家是否覺得這種寫法跟函數語言程式設計有點眼熟？有沒有可能用 TypeScript 型別系統來重寫上面的函數語言程式設計程式碼呢？

不管有沒有意義，我們先試著用易於理解、但是錯誤的語法寫一下（為了避免高亮出現混亂，這段程式碼就不加高亮了）：

type Fibonacci<N> =
    N <= 1 ? 1 : Fibonacci<N - 1> + Fibonacci<N - 2>;
type Gcd<X, Y> =
    Y = 0 ? X : Gcd<Y, X % Y>;
type Hyperoperation<N, A, B> =
    N = 0
        ? B + 1
        : N = 1 & B = 0
          ? A
          : N = 2 & B = 0
            ? B
            : N > 2 & B = 0
                ? 1
                : Hyperoperation<N - 1, A, Hyperoperation<N, A, B - 1>>;

從零開始的造輪子生活

Emmm……雖然看起來挺容易理解的，但這畢竟完全不是 TypeScript……為了用真正的 TypeScript 來編寫這段程式碼，我們來看看究竟需要哪些輪子（工具型別）。

定義“型別”

首先，為了能讓 TypeScript 允許我們對泛型引數做一些操作（例如取長度），我們需要先定義一些型別。在這裡我們拋開 JavaScript 的一切知識，因為在 TypeScript 型別系統的世界中，我們目前一無所有——這意味著我們要從最基礎的開始定義：

// 用字串來代替邏輯值
type Bool = 'true' | 'false';
// 用陣列的長度作為數字的大小
type Int = any[];
// 第一個數字
type _0 = [];

簡單的代數系統

除了“型別”以外，映入眼簾的就是 <=、+、- 等符號。我們需要先實現一個簡單的代數系統。為了簡單起見，我們假設所有的數字都是非負整數。

首先從“後繼”運算開始，期望的效果如下：

type Next<I extends Int> = Prepend<any, I>;

type _1 = Next<_0>; // [any]
type _2 = Next<_1>; // [any, any]
type _3 = Next<_2>; // [any, any, any]

這裡的 Prepend 該如何實現呢？有一個很 Tricky 的方法，我們構造一個函式，它的引數型別是 any + any[]，然後透過 extends 和 infer 將真正的引數型別提取出來：

type Prepend<E, T extends Int> =
    ((e: E, ...list: T) => any) extends ((...list: infer R) => any)
      ? R : T;

同理，我們需要一個 Prev 函式，它是 Next 函式的逆運算，我們可以用函數語言程式設計中常用的 Tail 來實現：

type Tail<T extends Int> =
    ((...t: T) => any) extends ((_: any, ...tail: infer R) => any)
    ? R : [];

type Prev<I extends Int> = Tail<I>;
type __2 = Prev<_3>; // [any, any]

加法就是不斷地呼叫 Next：

type Add<A extends Int, B extends Int> =
    B extends _0 ? A : Add<Next<A>, Prev<B>>;
//                     ^^^^^^^^^^^^^^^^^^^^^

然而如果這樣寫，TypeScript 在推導時會無法確定 Add 究竟是個什麼型別（報錯 ts(2456)，因為它在每一層都無法得到一個確定的結果），所以需要一點變通。下面一種寫法可以讓 TypeScript 在遞迴的每一層都有一個確定的結果：

type Add<A extends Int, B extends Int> = {
    'true': A
    'false': Add<Next<A>, Prev<B>>
}[B extends _0 ? 'true' : 'false'];

type _4 = Add<_1, _3>; // [any, any, any, any]
type _5 = Add<_2, _3>; // [any, any, any, any, any]
注意：TypeScript 在遞迴超過 50 層之後，會強行推導為 any，所以實際上來講，我們目前的程式碼無法處理 50 以上的加法。

當然，其中的 B extends _0 ? 'true' : 'false' 可以抽成一個工具函式：

type Eq<A extends Int, B extends Int> = A extends B ? 'true' : 'false';

type Add<A extends Int, B extends Int> = {
    'true': A
    'false': Add<Next<A>, Prev<B>>
}[Eq<B, _0>];

減法也可以透過類似的方式寫出來：

type Sub<A extends Int, B extends Int> = {
    'true': A
    'false': Sub<Prev<A>, Prev<B>>
}[Eq<B, _0>];

type __3 = Sub<_5, _2>; // [any, any, any]

乘法我們需要寫一個輔助函式，因為我們要儲存一個累加器：

type _Mul<Counter extends Int, A extends Int, B extends Int> = {
    'true': Counter
    'false': _Mul<Add<Counter, A>, A, Prev<B>>
//           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
}[Eq<B, _0>];

type Mul<A extends Int, B extends Int> = _Mul<_0, A, B>;

看似很簡單的東西，但是 TypeScript 會報 ts(2589)，因為它認為這樣可能會遞迴非常深，所以直接拒絕推導。這裡可以用 infer 將未來需要的運算提前一些：

type _Mul<Counter extends Int, A extends Int, B extends Int> = {
    'true': Counter
    'false': Add<Counter, A> extends infer R ? _Mul<R, A, Prev<B>> : never
//                                                  ^
}[Eq<B, _0>];

報錯變成了 ts(2344)，說 R 不是一個 Int。因為 TypeScript 的 infer 是無法預先知道結果的，但我們知道它一定是個 Int，因此再寫一個轉換函式 Cast，相當於強制型別轉換（事實上根本沒轉）：

type Cast<X, Y> = X extends Y ? X : Y;

type _Mul<Counter extends Int, A extends Int, B extends Int> = {
    'true': Counter
    'false': Add<Counter, A> extends infer R ? _Mul<Cast<R, Int>, A, Prev<B>> : never
}[Eq<B, _0>];

type _6 = Mul<_2, _3>; // [any, any, any, any, any, any]

整除和取模透過目前已有的工具函式已經可以寫出來了，原理是迴圈相減，有興趣的同學可以自行實踐一下，開頭就用 Div<A extends Int, B extends Int> 和 Mod<A extends Int, B extends Int> 吧。

然後是一些針對布林值的邏輯運算 And、Or、Not：

type And<A extends Bool, B extends Bool> =
    A extends 'false' ? 'false' : B extends 'false' ? 'false' : 'true';

type _and_true_true = And<'true', 'true'>;     // 'true'
type _and_true_false = And<'true', 'false'>;   // 'false'
type _and_false_true = And<'false', 'true'>;   // 'false'
type _and_false_false = And<'false', 'false'>; // 'false'

type Or<A extends Bool, B extends Bool> =
    A extends 'true' ? 'true' : B extends 'true' ? 'true' : 'false';

type _or_true_true = Or<'true', 'true'>;     // 'true'
type _or_true_false = Or<'true', 'false'>;   // 'true'
type _or_false_true = Or<'false', 'true'>;   // 'true'
type _or_false_false = Or<'false', 'false'>; // 'false'

type Not<A extends Bool> = A extends 'true' ? 'false' : 'true';

type _not_true = Not<'true'>;   // 'false'
type _not_false = Not<'false'>; // 'true'

最後是比較運算子，我們先從小於號開始，首先判斷 A 是否是 0，然後 B 是否是 0，最後是一個遞迴。這是一個三叉路口，但對於 TypeScript 來說不在話下：

type Lt<A extends Int, B extends Int> = {
    'A = 0': Not<Eq<B, _0>>
    'B = 0': 'false'
    'other': Lt<Prev<A>, Prev<B>>
}[
    A extends _0
        ? 'A = 0'
        : B extends _0
            ? 'B = 0'
            : 'other'
];

type _lt_1_2 = Lt<_1, _2>; // 'true'
type _lt_5_3 = Lt<_5, _3>; // 'false'
type _lt_4_4 = Lt<_4, _4>; // 'false'

其它的符號，其實可以透過 Lt、Eq 配合 And、Or、Not 來實現：

type Lte<A extends Int, B extends Int> =
    // 使用 `extends` 和 `infer` 來提前計算 a<b
    Lt<A, B> extends infer R
        ? Or<Cast<R, Bool>, Eq<A, B>>
        : never;
type Gt<A extends Int, B extends Int> = Not<Lte<A, B>>;
type Gte<A extends Int, B extends Int> = Or<Gt<A, B>, Eq<A, B>>;

一個比較完美的實現

有了之前的積累，上面的幾個函式就比較好寫了：

type Fibonacci<N extends Int> = {
    'true': _1
    // 使用 `extends` 和 `infer` 來提前計算 f[n-1] 和 f[n-2]
    'false': Fibonacci<Sub<N, _1>> extends infer F_N_1
        ? Fibonacci<Sub<N, _2>> extends infer F_N_2
            ? Add<Cast<F_N_1, Int>, Cast<F_N_2, Int>>
            : never
        : never
}[Lte<N, _2>];

type _fibonacci_1 = Fibonacci<_1>; // [any]
type _fibonacci_2 = Fibonacci<_2>; // [any]
type _fibonacci_3 = Fibonacci<_3>; // [any, any]
type _fibonacci_4 = Fibonacci<_4>; // [any, any, any]
type _fibonacci_5 = Fibonacci<_5>; // [any, any, any, any, any]
type _fibonacci_6 = Fibonacci<_6>; // [any, any, any, any, any, any, any, any]

type Gcd<X extends Int, Y extends Int> = {
    'true': X
    'false': Gcd<Y, Mod<X, Y>>
}[Eq<Y, _0>]

type H<N extends Int, A extends Int, B extends Int> = {
    'N = 0': Next<B>
    'N = 1 & B = 0': A
    'N = 2 & B = 0': _0
    'N > 2 & B = 0': _1
    // 使用 `extends` 和 `infer` 來提前計算 h(n, a, b-1)
    'other': H<N, A, Prev<B>> extends infer R ? H<Prev<N>, A, Cast<R, Int>> : never
}[
    Eq<N, _0> extends 'true'
        ? 'N = 0'
        : And<Eq<N, _1>, Eq<B, _0>> extends 'true'
            ? 'N = 1 & B = 0'
            : And<Eq<N, _2>, Eq<B, _0>> extends 'true'
                ? 'N = 2 & B = 0'
                : And<Gt<N, _2>, Eq<B, _0>> extends 'true'
                    ? 'N > 2 & B = 0'
                    : 'other'
]

type _h_0_0_3 = H<_0, _0, _3>; // 3+1=4,  [any, any, any, any]
type _h_1_5_6 = H<_1, _5, _6>; // 5+6=11, [any, any, any, any, any, any, any, any, any, any, any]
type _h_2_4_2 = H<_2, _4, _2>; // 4*2=8,  [any, any, any, any, any, any, any, any]
type _h_3_3_3 = H<_3, _3, _3>; // 3^3=27, [any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any, any]

無法實現的問題，以及未來的解決方案

上面的例子看起來很完美、很符合邏輯，但畢竟 TypeScript 型別系統並不是為了函數語言程式設計而服務的，因此也有一些思想是它暫時無法實現的。

注意：只是思想無法實現。TypeScript 型別系統在理想狀態下是圖靈完備的。

惰性計算

這其實是 TypeScript 目前的定位和設計所導致的。本文的“函式”只是 TypeScript 中普通的“工具型別”，並沒有真正的“函式”的功能，所謂的“返回值”也只是跟這個定義的內容等價的“TypeScript 型別”而已。雖然每個工具型別本身寫起來是函數語言程式設計，但不同的工具型別卻是按照命令式逐一定義並推導的。

函式是一等公民

考慮到這樣一個函式，它的輸入和輸出都是函式：

function compose(...f) {
    return f.length === 0
        ? undefined
        : f.length === 1
          ? f[0]
          : (...args) => f[0](compose(...f.slice(1))(args));
}

如果用 TypeScript 型別系統來寫，會是什麼樣的呢？

注意：從這裡開始，所有的 TypeScript 程式碼在本文釋出的時期都是錯誤的，不要模仿。
type Compose<F> =
    F['length'] extends 0
        ? undefined
        : F['length'] extends 1
            ? F[0]
            : ########

井號的部分寫起來並沒有那麼直觀。事實上，TypeScript 目前不支援高階工具型別（Higher order types），因此我們沒有辦法把“函式”作為輸入和輸出。

未來的解決方案

目前 TypeScript 有這樣一個 Proposal：Higher Order, Lamda, Reference types，目前的狀態是 Backlog（待辦）。它的語法有點類似於 C 裡面的函式指標：

type A<T extends string> = { 0: T }
type B<T extends string> = [T]
type C<T extends number> = 42

// Here's our lamda
type Referer<*Ref<X extends string>, T extends string> = Ref<T>

type testA = Referer<A, 'hi'> // { 0: 'hi' }
type testB = Referer<B, 'hi'> // ['hi']
type testC = Referer<C, 'hi'> // ERROR

唯一需要做的就是在“引數”前面加一個星號，表示這個“引數”是一個泛型，這樣我們就能將“函式”作為“引數”傳進去了。如果用普通的程式碼來寫，大概是這樣：

const a = (t: string) => ({ 0: t });
const b = (t: string) => [t];
const c = (t: number) => 42;

// Here's our lamda
const referer = (ref: (x: string) => any, t: string) => ref(t)

const testA = referer(a, 'hi') // { 0: 'hi' }
const testB = referer(b, 'hi') // ['hi']
const testC = referer(c, 'hi') // type mismatch

先不管它以後會不會被實現，至少可以確定的是：如果有了這個功能，上面兩個問題就都能解決了：第二個問題無需多講；對於第一個問題，由於需要支援傳入一個泛型，那麼支援傳入泛型的那個泛型（上文的 Referer）在傳入之前是無法被推導的。作者也說了：In this context, we can say that * "protects" against immediate evalutation.

做個腦力遊戲吧

假如真的有了這個功能，我們該怎麼實現 Compose 呢？

type Compose<
    F extends Array<*Ref<T extends any>>
> =
    F['length'] extends 0
        ? undefined
        : F['length'] extends 1
            ? F[0]
            : ########

這個特性依舊無法讓我們在井號的地方直接用 type xxx = yyy 這種方式來定義“函式”。

方法總比困難多，不是不能在定義中定義嗎，我在之前先定義好不就可以了？我把井號部分抽成一個輔助函式 P：

type P<F extends Array<*Ref<T extends any>>> = *(F[0])<Compose<Tail<F>>>;

那麼井號的部分就可以直接寫 *(P<F>) 了！

然而這有個問題：P 要在 Compose 之前定義，但 P 裡面又用到了 Compose。在函數語言程式設計中有一個方法可以解決：我們可以將 Compose 作為引數傳入 P，就像這樣：

type P<
  *H<*F extends Array<*Ref<T extends any>>>,
  F extends Array<*Ref<T extends any>>
> = *(F[0])<H<Tail<F>>>;
type Compose<
    F extends Array<*Ref<T extends any>>
> =
    F['length'] extends 0
        ? undefined
        : F['length'] extends 1
            ? F[0]             // is a generic
            : *(P<Compose, F>) // is also a generic

更進一步，我們可能可以推出函數語言程式設計中的 Y-組合子，從而從另一個方向上證明了它是圖靈等價的。

參考資料

TypeScript 型別系統與函數語言程式設計
https://blog.rexskz.info/typescript-type-system-and-functional-programming.html
作者
Rex Zeng
最後更新
2020-02-04 20:37
許可協議
BY 4.0
Disqus 載入中……如未能載入，請將 disqus.com 和 disquscdn.com 加入白名單。

這是我們共同度過的

第 3866 天♥