Smallfuck 语言
Smallfuck 是一门最小的图灵完备的编程语言, 其可以看成最基本的图灵机的一种变体, 其将计算机看成一条无限长的纸带, 纸带每一格存储 0 或 1, 存在一个指针指向纸带的某一格.
其语法只包含五种操作:
<: 左移指针>: 右移指针*: 翻转指针所指向的格子中的 bit[: 跳转, 与另一个字符]对应. 若指针指向的格子为0, 则跳转到对应的], 否则继续执行.]
元编程
元编程可以粗泛地看作是利用语言提供的元编程能力, 调度编译器生成代码的过程, 从而达到减少代码、编译期计算等目的. C++ 的模板编程被看作是一种典型的元编程, 通过创建模板类并传入不同的类型参数, 用户可以达到控制编译器生成对应的类型的目的.
当提及 Rust 的元编程能力时, 人们一般会谈论 Rust 的宏. Rust 的宏是一种从语法和代码层面生成代码的元编程模式, 但它不涉及 Rust 的类型系统. 本篇文章则是从 Rust 的类型系统讨论如何完成元编程.
类型编程
当谈到一门语言可以编程时, 其实其可以抽象为可以做到三件事情:
- 状态存储: 对应纸带上的每个格子
- 状态识别: 指针可以识别当前格子是0还是1
- 状态转换: 指针可以左右移动, 可以反转当前格子的 bit
状态存储
从运行期来看, 状态存储很简单, 就是定义变量. 但是从类型系统/编译器来看, 其只能识别不同的类型. 因此在编译期, 我们使用类型进行状态存储:
struct Zero;
struct One;
上面的代码分别定义了0和1, 在编译器看来上面两个类型显然是不同的, 因此我们完成了最基本的状态存储.
运行期的状态通常具有某种类型, 在编译期可以利用 trait 为类型添加“类型”:
trait Bit {}
impl Bit for Zero {}
impl Bit for One {}
经过上面的代码, Zero 和 One 都有了相同的"类型": Bit, 表示它们都是 Bit 类型的变量.
至此, 我们可以做到只使用类型表示一个格子的状态, 但是如何表示纸带呢?
在运行期我们直接使用一个数组表示一条无限长的纸带(内存足够的话), 但是在编译期没有内存的概念, 也就没有数组的概念. 我们只能另辟蹊径.
struct A<B>(PhantomData<B>);
在上面的代码中, 利用了rust 类型系统的泛型参数的特性. 类型 A包含了一个类型参数 B. B 也是一个类型. PhantomData 的运用只是因为 rust 不允许泛型参数没有在成员变量中使用, 实际并不占用任何内存.
通过在类型中定义泛型参数, 我们竟然发现可以达到定义如同运行期的 类的成员变量的效果.
struct Hex<A: Bit, B: Bit, C: Bit, D: Bit>(PhantomData<(A, B, C, D)>);
上面的代码中,Hex 可以做到表示一个 16 进制数的变量的效果, 例如: Hex<One, Zero, Zero, Zero> 可以表示 0x1000, 即数字8.
接着设想类型 B 中也包含了一个类型参数 C, 并由此类推, 所有类型包裹起来是不是就相当于一条无限长的纸带? (这里的无限长是指理论上长度没有限度, 不是实际长度无限) 由此我们定义数组:
trait List {}
struct Cons<B: Bit, L: List> (PhantomData<(B, L)>);
struct Nil;
impl<B: Bit, L: List> List for Cons<B, L> {}
impl List for Nil {}
上面的代码定义了一个数组, 牵扯了两个看起来不相关的类型. 实际上这就是 Haskell 中的数组的定义方式, 如果你熟悉 Haskell 的话, 其本质上是一个栈.
第一个类型 Nil 表示纸带终止, 第二个类型则用于表示纸带的一个格子, 其定义了两个 "成员变量":
B: 表示格子的 bitL: 表示下一格, 本质上是一种递归的思想.
如果我们需要表示 |0|1|1| 的数组, 则可以定义类型 Cons<Zero, Cons<One, Cons<One>>>.
然而, 上述定义的数组和我们需要的纸带相差甚远, 虽然其理论上可以表示无限长的纸带, 但是其始终只能表示当前 bit 以及往右或往左的格子.
为此, 我们引入双栈: 第一个栈表示指针左边的所有格子, 第二个栈表示指针右边的所有格子.
struct State<L: List, C: Bit, R: List>(
PhantomData<(L, C, R)>
);
上面的类型就可以表示整个纸带或者说图灵机的状态:
L: 左边的所有的格子, 展开形式为Cons<P, L>,P表示左边第一个bit,L表示左边第二格及往前的所有格子;C: 当前指针的bitR: 右边的所有格子, 展开形式为Cons<N, R>,N表示右边第一个bit,R表示右边第二格及往后的所有格子.
若指针向右移动一格, 则状态转换可表示为对应的类型状态: State<L, C, Cons<N, R>> -> State<Cons<C, L>, N, R>. (这个状态转换的过程是理解下面的关键).
状态识别
状态识别通常是状态转换的前奏, 无副作用和状态转换的状态识别是没有意义的, 就像你不会写一个空的 if 语句一样.
类型编程中状态识别并不需要我们做什么, 因为这是类型系统提供的特性. 状态识别不只是编译器可以区分不同的类型, 同时也包含 trait 可以区分不同类型的能力, 例如同一个 trait 对于不同的类型可以有不同的实现. 在状态转换中你会见识到这一点有多么重要.
类型推导
提到状态识别则不得不提编译器的另一个重要特性: 类型推导. 类型推导是指基于已有的具体类型参数推导未知的泛型参数, 就如同求解线性方程组一样. 结果要么存在唯一解, 要么编译器报错存在 “ ambiguous ” 实现.
例如对于下面的代码:
Foo<X, Bar<u16, Z>> == Foo<Baz, Y>
假定上述两个类型相同, 其中单大写字母表示泛型参数, 则编译器可以推导出 X = Baz, Y = Bar<u16, Z> , Z 依然未定.
状态转换
至此, 距离实现 Smallfuck 只差最后一步, 也是最难的一步. 要讨论如何进行状态转换, 首先要讨论什么是类型层面的状态转换.
其实很简单, 前面我们已经确定了使用类型表示状态, 那么状态转换无非就是完成类型到类型的映射.
“类型映射” 听起来好像很厉害, 但是我们可以借助 Rust 的一个特性简单实现, 即 trait 的 “关联类型(Associated Type)".
众所周知, Rust 的 trait 可以同时定义若干泛型参数和若干关联类型, 两者的使用区别也一直为很多初学者所迷惑. 这里指出两者在类型层面最大的一个差别: 可以通过泛型参数区分对同一个类型对 trait 的不同实现, 但不能通过关联类型进行区分. 泛型参数就如同 trait 的入口, 关联类型则是出口, 不同入口可以有不同的出口, 也可以有同一个出口, 但是同一个入口不能对应不同出口.
说回类型映射, 如果我们需要完成类型映射: A -> B, 则只需要将 A 作为泛型参数, B 作为关联类型就可以完成这种类型映射. 定义完成类型映射的 trait:
trait Transform<S> {
type To;
}
上面的类型映射 trait 可以看成一个函数, 而且是 纯函数. 输入特定的类型组合, 总能得到相同的输出类型组合.
状态转换是基于基于具体动作进行的, 我们定义 Smallfuck 语言的第一个基本的动作: 指针左移. 同样使用类型表示.
struct Left;
至此我们可以正式迈出状态转换的第一步:
impl<P: Bit, L: List, C: Bit, R: List>
Transform<State<Cons<P, L>, C, R>> for Left {
type To = State<L, P, Cons<C, R>>;
}
对于任何状态 S = State<Cons<P, L>, C, R>, 通过调用 <Left as Transform<S>>::To 就可以得到指针左移后的状态 S' = State<L, P, Cons<C, R>>. 是不是很神奇?
程序的连续性
上面定义的状态转换过程实际只完成了单步的状态转换, 但是程序是由连续的多步转换来实现的. 如果我们要定义左移两次, 按照上面的写法, 只能写成:
<Left as Transform<<Left as Transform<State<L, C, R>>>::To>::To;
显然我们不会想要这样来做类型编程. 因此需要修改表示动作的类型:
struct Left<T: Transform>(PhantomData<T>);
上面的定义为动作 Left 添加了一个类型参数, 其表示当前动作的下一个动作. 于是
Left<Left<...>>;
可以表示连续左移两次. 这本质上也是一种递归的思想, 因此我们需要定义一个递归的终止处, 定义:
struct Empty;
表示程序终止, 当一个动作携带的类型为 Empty 时表示接下来没有其它动作.
顺势定义其它动作:
struct Right<T>(PhantomData<T>); //右移指针
struct Flip<T>(PhantomData<T>); //翻转bit
struct Judge<P, Q>(PhantomData<(P, Q)>); //跳转
其中跳转需要携带两个类型参数, 分别表示当前bit为0和当前bit为1情况下的下一个动作.
连续状态转换的基本思想: 下一个动作的输入状态是当前动作完成状态转换之后得到的状态, 当前动作的最终状态(即所有动作执行完成后得到的状态)等于下一个动作的最终状态.
据此重新为 Left 实现状态转换:
impl<P: Bit, L: List, C: Bit, R: List, T>
Transform<State<Cons<P, L>, C, R>> for Left<T> {
type To = <T as Transform<State<L, P, Cons<C, R>>>::To;
}
实际上上面的代码无法编译, 因为在没有说明 T 满足 Transform bound 的情况下, 直接使用 T as Transform, 这在 Rust 中是不允许的.
因此需要改成:
impl<P: Bit, L: List, C: Bit, R: List, T: Transform<State<L, P, Cons<C, R>>>
Transform<State<Cons<P, L>, C, R>> for Left<T> {
type To = <T as Transform<State<L, P, Cons<C, R>>>::To;
}
原作者采用了一种更简洁的形式:
trait Transform<S = Empty> {
type Output;
}
impl<P: Bit, C: Bit, L: List, R: List, T: Transform>
Transform<State<Cons<P, L>, C, R>> for Left<T>
where T: Transform<State<L, P, Cons<C, R>>> {
type Output = <T as Transform<State<L, P, Cons<C, R>>>>::Output;
}
至此, 关于类型编程的内容已经结束, 基于上面的内容已经足以实现 Smallfuck 语言(完整代码在结尾). 而根据图灵等价性, 如果一门语言P可以完全模拟另一门图灵完备的语言Q, 则P也是图灵完备的. 因此, 我们费劲巴脑地用 Rust 实现一门图灵完备的语言, 潜在目的正是证明 Rust的类型系统是图灵完备的.
完整代码:
use std::marker::PhantomData;
trait Bit {}
struct One;
struct Zero;
impl Bit for One {}
impl Bit for Zero {}
trait List {}
struct Cons<B: Bit, L: List> (PhantomData<(B, L)>);
struct Nil;
impl<B: Bit, L: List> List for Cons<B, L> {}
impl List for Nil {}
struct State<L: List, C: Bit, R: List>(
PhantomData<(L, C, R)>
);
struct Empty;
struct Left<T>(PhantomData<T>);
struct Right<T>(PhantomData<T>);
struct Flip<T>(PhantomData<T>);
struct Judge<P, Q>(PhantomData<(P, Q)>);
/// The input type parameter is the State
trait Transform<S = Empty> {
type Output;
}
impl<P: Bit, C: Bit, L: List, R: List, T: Transform>
Transform<State<Cons<P, L>, C, R>> for Left<T>
where T: Transform<State<L, P, Cons<C, R>>> {
type Output = <T as Transform<State<L, P, Cons<C, R>>>>::Output;
}
impl<N: Bit, C: Bit, L: List, R: List, T: Transform>
Transform<State<L, C, Cons<N, R>>> for Right<T>
where T: Transform<State<Cons<C, L>, N, R>> {
type Output = <T as Transform<State<Cons<C, L>, N, R>>>::Output;
}
impl<L: List, R: List, T: Transform>
Transform<State<L, One, R>> for Flip<T>
where T: Transform<State<L, Zero, R>> {
type Output = <T as Transform<State<L, Zero, R>>>::Output;
}
impl<L: List, R: List, T: Transform>
Transform<State<L, Zero, R>> for Flip<T>
where T: Transform<State<L, One, R>> {
type Output = <T as Transform<State<L, One, R>>>::Output;
}
/// Jump to P if the current bit is One
/// Otherwise jump to Q
impl<L: List, R: List, P: Transform, Q: Transform>
Transform<State<L, One, R>> for Judge<P, Q>
where P: Transform<State<L, One, R>> {
type Output = <P as Transform<State<L, One, R>>>::Output;
}
impl<L: List, R: List, P: Transform, Q: Transform>
Transform<State<L, Zero, R>> for Judge<P, Q>
where Q: Transform<State<L, Zero, R>> {
type Output = <Q as Transform<State<L, Zero, R>>>::Output;
}
impl<L: List, C: Bit, R: List>
Transform<State<L, C, R>> for Empty {
type Output = State<L, C, R>;
}