R·ex / Zeng


音游狗、安全狗、攻城狮、业余设计师、段子手、苦学日语的少年。 MUGer, hacker, developer, amateur UI designer, punster, Japanese learner.

TypeScript 类型系统与函数式编程

背景

接触 TypeScript 已经有一段时间了,这期间写过一些复杂的类型(例如 这篇文章),我开始意识到:TypeScript 的类型系统写起来就像函数式编程一样。去年某天,一个同事给我发了个链接,里面讲的是“TypeScript 类型系统的图灵完备”,里面的一些内容我还在努力理解到可以分享的程度,但一些代码差不多可以说明 TypeScript 类型系统跟函数式编程的思想非常接近了。

前期知识

  • 掌握 TypeScript 的 基本类型,相信大家都了解;
  • 掌握 TypeScript 的 高级类型泛型
  • 非常熟悉 extendsinfer 的使用;
  • “函数式编程”的概念,相信大家都或多或少从公众号里面听到过。

文中接下来所有跟 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 的泛型长得很像函数:定义泛型相当于定义一个函数,其中的 TR 等类型变量可以被看作参数。但通过不断尝试外加查资料,我们最终都会意识到:在 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[],然后通过 extendsinfer 将真正的参数类型提取出来:

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> 吧。

然后是一些针对布尔值的逻辑运算 AndOrNot

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'

其它的符号,其实可以通过 LtEq 配合 AndOrNot 来实现:

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-组合子,从而从另一个方向上证明了它是图灵等价的。

参考资料

版权声明:除文章开头有特殊声明的情况外,所有文章均可在遵从 CC BY 4.0 协议的情况下转载。
上一篇: 从前端组件库引出的计算几何问题
下一篇: Redirect attack - Shadowsocks 流密码的不安全因素

这是我们共同度过的

第 1553 天