#运算符 #类型 #类型级别 #

type-operators

Rust 中创建类型运算符并编写类型级别逻辑的宏系统

9 个版本

使用旧的 Rust 2015

0.3.5 2017 年 3 月 8 日
0.3.4 2016 年 12 月 1 日
0.2.1 2016 年 11 月 25 日
0.1.3 2016 年 11 月 24 日

1111Rust 模式

每月 31 次下载
type-level-logic 中使用

MIT/Apache

71KB
664

Build Status Docs Status On crates.io

type-operators

type_operators 宏 - 一个用于在 Rust 中声明类型运算符和类型级别逻辑的 DSL。

该软件包包含一个用于在 Rust 中声明类型运算符的宏。类型运算符类似于在类型级别上执行的操作的函数。《code>type_operators 宏通过将 LISP-y DSL 转换为具有关联类型的 traits 和 impls 的大杂烩来工作。

DSL

让我们看看这个相当小的例子

type_operators! {
    [A, B, C, D, E]

    data Nat {
        P,
        I(Nat = P),
        O(Nat = P),
    }
}

在这个例子中有两个需要注意的基本要点。第一个是“生成符号列表”——Rust 目前还没有生成唯一标识符的方法,所以我们必须自己提供。这取决于你避免这些伪生成符号与涉及的结构的名称之间发生冲突!如果我们把 PIO 放入生成符号列表中,事情可能会变得非常糟糕!我们将在编译时由于类型运算符的定义中出现的 trait 约束而获得类型错误。幸运的是,生成符号列表可以相当小,通常不会使用超过两个或三个符号。

第二点是 data 声明。这声明了一组属于标记特质的结构体。在我们的例子中,Nat 是生成的标记特质,而 PIO 是生成的结构体。这个例子展示了一个自然数(包括零的正整数)的实现,这些自然数被表示为类型。因此,P 表示自然数的末尾 - 可以将其视为一种 nil;我们在类型级别上使用链表。因此,I<P> 表示 "P 加上两次" 的结果,这当然等于 1O<P> 表示 "P 的两倍",这当然等于零。如果我们把 IO 视为一个二进制数的位,我们得到一种倒序的二进制表示,其中最左边的 "位" 是最低有效位。因此,O<O<I>> 表示 4I<O<O<I>>> 表示 9,依此类推。

当我们编写 I(Nat = P) 时,= P 表示默认值。这使得我们可以编写 I,并让它被推断为 I<P>,如果你只写 I,这可能是你想要的意思。 Nat 提供了一个特质界限。为了更好地说明,以下是大致上 type_operators 调用的展开。

pub trait Nat {}

pub struct P;
impl Nat for P {}

pub struct I<A: Nat = P>(PhantomData<(A)>);
impl<A: Nat> Nat for I<A> {}

pub struct O<A: Nat = P>(PhantomData<(A)>);
impl<A: Nat> Nat for O<A> {}

Undefined 值看起来有些奇怪,但它允许以使用类型级比较和分支的方式定义除法。关于这一点,稍后会详细介绍。

上述定义有一个问题。我们不能将我们的类型级表示折叠到数值表示中。这使得我们的类型级自然数变得毫无用处!这就是为什么 type_operators 提供了另一种定义类型级表示的方法,即 concrete 声明。

type_operators! {
    [A, B, C, D, E]

    concrete Nat => usize {
        P => 0,
        I(N: Nat = P) => 1 + 2 * N,
        O(N: Nat = P) => 2 * N,
        Undefined => panic!("Undefined type-level arithmetic result!"),
    }
}

这为 Nat 特质添加了一个关联函数 reify,它允许你将你的类型级表示转换为类型 usize 的具体值(在这种情况下)。如果你曾经见过原语递归函数,那么这应该对你来说有点熟悉 - 它类似于一个递归方案,这是一种递归到值并将它映射到其他东西的方法。(也请参见 "catamorphism"。)这应该很清楚如何工作,但如果不是,以下是一个分析:

  • P 总是代表零,所以我们说 P => 0。很简单。
  • I 表示其参数的两倍加一。如果我们用变量 N 注释宏的定义,那么 type_operators 将会自动调用 N::reify() 并用这个值替换掉你在表达式中给出的 N。因此,这样我们定义了 I 的具体化,即 N 具体化后的值的两倍加一。
  • O 表示其参数的两倍,所以这个比较简单——就像 I,但是没有 1 +

好的。既然我们已经掌握了这些,那么让我们深入研究一些更复杂的内容:定义一个用于加法的类型操作符。

type_operators 允许你定义递归函数。一般来说,无论你做什么,你都需要这个。更准确地说,整个方法都受到了原始递归的启发。那么,让我们考虑如何从最低有效位开始加两个二进制数。

  • 显然,P + P 应该是 P,因为零加零等于零。
  • 那么,对于任何自然数 NP + O<N> 呢?嗯,那应该是 O<N>。同样,I<N> 也是这样。事实上,现在看起来很显然,只要我们在一边有 P,我们就可以说另一边的结果就是所求。因此,我们现在的小操作表看起来是这样的
[P, P] => P
[P, (O N)] => (O N)
[P, (I N)] => (I N)
[(O N), P] => (O N)
[(I N), P] => (I N)

你现在可能想说,“哇!这看起来根本不像 Rust!等一下!”这是因为它确实不是。我为了这个项目创建了一个小小的 LISP 式方言来描述 Rust 类型,因为它使得宏中的解析变得容易得多;具体来说,每个小的原子类型都可以被括号包裹起来,而 Rust 需要将它们解析为单独的标记。在这个配置中,(O N) 表示 O<N>,仅仅 P 代表 P 等等。等等。表示法 [X, Y] => Z 表示“给定输入 XY,产生输出 Z。”因此,它是一种模式匹配。

现在让我们来看看更复杂的情况。我们需要涵盖所有 O<N>I<N> 组合相加的部分。

  • O<M> + O<N> 的结果应该是 O<M + N>。这是一个相当直观的结果,但我们可以用数学表达式来描述它,即 2 * m + 2 * n == 2 * (m + n)。所以,这是分配律,最重要的是,它简化了参数的结构——我们从将 O<M>O<N> 相加转换为 MN,无论它们是什么,而 MN 显然比 O<M>O<N> 更简单。如果我们总是看到我们的输出比输入更简单,那么我们离证明我们的小类型运算符总是终止得到结果就更近一步了!
  • I<M> + O<N>O<M> + I<N> 的结果应该是 I<M + N>。同样,这也是相当直观的。我们有 1 + 2 * m + 2 * n,我们可以将其封装为 1 + 2 * (m + n)
  • I<M> + I<N> 是这里最复杂的一部分。我们有 1 + 2 * m + 1 + 2 * m == 2 + 2 * m + 2 * n == 2 * (1 + m + n)。我们可以将其实现为 I<I + M + N>,但我们可以做得更好。关于这一点,我们稍后再讨论,现在我们先使用简单的实现。

让我们将这些添加到表中

[P, P] => P
[P, (O N)] => (O N)
[P, (I N)] => (I N)
[(O N), P] => (O N)
[(I N), P] => (I N)
// New:
[(O M), (O N)] => (O (# M N))
[(I M), (O N)] => (I (# M N))
[(O M), (I N)] => (I (# M N))
[(I M), (I N)] => (O (# (# I M) N))

这里有一些新内容:(# ...) 符号。这告诉宏,“嘿,我们想要递归。”这实际上是稍微复杂一些的符号的简写,但它们有一个共同点——当 type_operators 处理 (# ...) 符号时,它会用它来计算 trait 约束。这是因为除非你的类型运算符能够确保 (# M N) 实际上有一个定义的结果,否则它不会编译。在更高的层面上,这也是我希望 Rust 有“闭合类型族”的原因——如果 PIONat 类型族中,Rust 就可以在编译时检查并绝对确信 (# M N)Nat 类型族中的所有 MN 都存在。

那么,让我们将它加载到 type_operators 的一个调用中,看看它的样子。它与表格非常相似,但有一些添加(我现在省略了 Undefined,因为它还不相关)

type_operators! {
    [A, B, C, D, E]

    concrete Nat => usize {
        P => 0,
        I(N: Nat = P) => 1 + 2 * N,
        O(N: Nat = P) => 2 * N,
    }

    (Sum) Adding(Nat, Nat): Nat {
        [P, P] => P
        forall (N: Nat) {
            [(O N), P] => (O N)
            [(I N), P] => (I N)
            [P, (O N)] => (O N)
            [P, (I N)] => (I N)
        }
        forall (N: Nat, M: Nat) {
            [(O M), (O N)] => (O (# M N))
            [(I M), (O N)] => (I (# M N))
            [(O M), (I N)] => (I (# M N))
            [(I M), (I N)] => (O (# (# M N) I))
        }
    }
}

有几个需要注意的地方。首先,定义 (Sum) Adding(Nat, Nat): Nat。这意味着,“这个类型运算符接受两个 Nat 作为输入,并输出一个 Nat。”由于加法是在底层实现为一个递归特质,这意味着我们得到一个形如的特质定义

pub trait Adding<A: Nat>: Nat {
    type Output: Nat;
}

(Sum) 部分为我们声明了一个方便的别名,所以我们可以不用输入 <X as Adding<Y>>::Output 来获取两个数的和,而是输入 Sum<X, Y>。更简洁。

首先,“量词”部分(包含forall的部分)可以避免Rust在类型变量未声明时发出警告。在任何特定的泛型impl中,我们必须考虑在该impl中可以使用的类型变量/泛型类型参数。forall部分修改了impl的序言。例如,forall (N: Nat)使得其内部的所有impl都被声明为impl<N: Nat> ...,而不是impl...,这样我们就可以在那些表达式中使用N作为变量。

这就是我们简短介绍的结束。最后,这里是一些我们这个小LISP方言特有的符号,它们只能在DSL规则右侧使用。

  • (@TypeOperator ...)调用另一个类型操作符(可以是原始调用者!)并生成适当的特性界限。
  • (% ...)类似于(# ...),但不会生成任何特性界限。
  • (& <type> where (<where_clause>) (<where_clause>) ...)允许为特定的impl定义自定义的where子句。它可以在DSL规则右侧的任何位置出现,但通常应该始终在顶层编写,以确保一致性。

此外,还可以在dataconcrete定义以及它们内部的各个元素上使用属性,如#[derive(...)]#[cfg(...)]。此外,还可以为规则的impl添加属性。例如

type_operators! {
    [A, B, C, D, E]

    data Nat: Default + Debug where #[derive(Default, Debug)] {
        P,
        I(Nat = P),
        O(Nat = P),
        #[cfg(features = "specialization")]
        Error,
        #[cfg(features = "specialization")]
        DEFAULT,
    }

    (Sum) Adding(Nat, Nat): Nat {
        [P, P] => P
        forall (N: Nat) {
            [(O N), P] => (O N)
            [(I N), P] => (I N)
            [P, (O N)] => (O N)
            [P, (I N)] => (I N)
        }
        forall (N: Nat, M: Nat) {
            [(O M), (O N)] => (O (# M N))
            [(I M), (O N)] => (I (# M N))
            [(O M), (I N)] => (I (# M N))
            [(I M), (I N)] => (O (# (# M N) I))

            #[cfg(features = "specialization")] {
                {M, N} => Error
            }
        }
    }
}

注意以下代码块:#[cfg(features = "specialization")] { ... }. 这告诉 type_operators! 将属性 #[cfg(features = "specialization")] 添加到内部声明的每一个 impl。还值得注意的是,可以通过上面的类似 where 子句结构将 derives 添加到 concretedata 声明中的每个语句中。我们必须这样做的原因是,如果我们允许以直观的方式定义它,那么将无法轻松提取组特质的文档注释(感谢宏解析歧义。)

当前存在的问题/改进

  • 类型操作符中的界限目前仅限于标识符 - 应该使用类似于宏系统其余部分的 LISP 样式方言进行扩展。

如果有问题,我可能在我的电子邮件(在 GitHub 上列出)或 #rust IRC 上,我用昵称 sleffy

许可

根据您的要求,许可方式如下:

任选其一。

贡献

除非您明确说明,否则您有意提交以包含在您的工作中的任何贡献,根据 Apache-2.0 许可证定义,将按上述方式双许可,没有其他条款或条件。

无运行时依赖