rabbot

Rabbot 生成抽象绑定树（ABT）的接口。它是 SML 的 Abbot 到 Rust 的移植。

什么是 ABT？

抽象绑定树是一种类似于抽象语法树的数据结构，但它允许您愉快且正确地处理符号的声明和绑定。为了说明这一点，让我们考虑一个简单伪语言的语法树。对于表达式 2 + 1，这将生成一个语法树 Plus(Number(2), Number(1))。对于表达式 let x = 1 in x + 2，这将生成 Let(Var("x"), Number(1), Plus(Var("x"), Number(2))。对于这些示例，使用正常的抽象语法树即可。

然而，如果我们引入多个同名绑定，我们就会遇到麻烦。例如，在表达式 let x = 1 in (let x = 2 in x) + x 中，我们现在需要某种作用域分析的概念。每个实例的 x 指的是什么？ABTs 通过提供处理变量绑定和替换的结构来消除这个问题。前面的表达式大致可以翻译为 Let(1, x . (Let(2, x . x) + x))，其中点 . 表示一个绑定点。有关更多信息，请参阅 Bob Harper 的 《程序设计语言的实际基础》 第一章。

Rabbot 做什么？

创建抽象语法的通常方式是定义一个枚举，其中每个分支对应于语法的一部分，例如。

enum Expression {
    Number(i32),
    Plus(Box<Expression>, Box<Expression>),
    ...
}

然而，ABTs 的工作方式不同。从本质上讲，ABT 是一个由一组操作符参数化的固定树数据结构，其中每个操作符描述了像 Number 或 Plus 这样的功能。有关数据类型的定义，请参阅 rabbot/src/abt.rs。这使您能够轻松地为不同类型的程序重用 ABT 结构，但在实际使用中需要更多的样板代码和更多的代码。

为了减轻使用 ABTs 的冗长性，Rabbot 采取了对抽象绑定树的描述，并为程序员生成了一个更简洁的接口。例如，可以在几行代码中实现带有佩亚诺数和其解释器的lambda演算。

#![feature(plugin, box_syntax)]
#![plugin(rabbot_plugin)]

#[macro_use] extern crate rabbot;

rabbot! {
    sort Term {
        Z,
        S(Term),
        Lam(Binding<Term> . Term),
        App((Term, Term))
    }
}

use rabbot::var::Var;
use term::*;
fn interpret(t: Term) -> Term {
    match out(t) {
        v @ View::Z | v @ View::Lam(_) => into(v),
        View::S(t) => {
            bind!(View::S{v} = out(interpret(t)));
            into(View::S(v))
        },
        View::App((fun, arg)) => {
            bind!(View::Lam{(var, body)} = out(interpret(fun)));
            subst(arg, var, body)
        },
        View::Var(_) => unreachable!()
    }
}

#[test]
fn test() {
    let x = Var::new("x".to_string());
    let term = into(View::App((
        into(View::Lam((
            x.clone(), into(View::S(into(View::Var(x.clone()))))))),
        into(View::Z))));

    println!("{:?}", interpret(term)); // prints S(Z)
}

注意事项

这仍在积极开发中，如果您想使用它，请与我联系（邮箱：[email protected]）。代码生成器作为一个编译器插件工作，所以它只适用于 nightly，尽管这不是一个硬性要求。