program-induction

程序归纳和学习表示的库。

实现了贝叶斯程序学习和遗传编程。有关更多信息，请参阅 文档。

安装

安装 rust 并确保您已更新 (rustup update)。在一个新项目或现有项目中，将以下内容添加到您的 Cargo.toml

[dependencies]
programinduction = "0.9"
# many examples also depend on polytype for the tp! and ptp! macros:
polytype = "7.0"

该文档需要自定义 HTML 标头以包含 KaTeX 以支持数学。这不被 cargo doc 支持，因此要构建文档，您可以使用

cargo rustdoc -- --html-in-header rustdoc-include-katex-header.html

用法

指定一个概率上下文无关文法（PCFG；参见 pcfg::Grammar）并归纳出一个与示例匹配的句子

use polytype::tp;
use programinduction::pcfg::{task_by_evaluation, Grammar, Rule};
use programinduction::{ECParams, EC};

fn evaluate(name: &str, inps: &[i32]) -> Result<i32, ()> {
    match name {
        "0" => Ok(0),
        "1" => Ok(1),
        "plus" => Ok(inps[0] + inps[1]),
        _ => unreachable!(),
    }
}

fn main() {
    let g = Grammar::new(
        tp!(EXPR),
        vec![
            Rule::new("0", tp!(EXPR), 1.0),
            Rule::new("1", tp!(EXPR), 1.0),
            Rule::new("plus", tp!(@arrow[tp!(EXPR), tp!(EXPR), tp!(EXPR)]), 1.0),
        ],
    );
    let ec_params = ECParams {
        frontier_limit: 1,
        search_limit_timeout: None,
        search_limit_description_length: Some(8.0),
    };
    // task: the number 4
    let task = task_by_evaluation(&evaluate, &4, tp!(EXPR));

    let frontiers = g.explore(&ec_params, &[task]);
    let sol = &frontiers[0].best_solution().unwrap().0;
    println!("{}", g.display(sol));
}

探索-压缩（EC）算法通过在归纳程序中找到共同结构来迭代地学习更好的表示。我们可以在布尔电路域中使用多态类型 lambda 计算表示 lambda::Language 运行 EC 算法

use polytype::{ptp, tp};
use programinduction::{domains, lambda, ECParams, EC};

fn main() {
    // circuit DSL
    let dsl = lambda::Language::uniform(vec![
        // NAND takes two bools and returns a bool
        ("nand", ptp!(@arrow[tp!(bool), tp!(bool), tp!(bool)])),
    ]);
    // parameters
    let lambda_params = lambda::CompressionParams::default();
    let ec_params = ECParams {
        frontier_limit: 1,
        search_limit_timeout: Some(std::time::Duration::new(1, 0)),
        search_limit_description_length: None,
    };
    // randomly sample 250 circuit tasks
    let rng = &mut rand::thread_rng();
    let tasks = domains::circuits::make_tasks(rng, 250);

    // one iteration of EC:
    let (new_dsl, _solutions) = dsl.ec(&ec_params, &lambda_params, &tasks);
    // print the new concepts it invented, based on common structure:
    for (expr, _, _) in &new_dsl.invented {
        println!("invented {}", new_dsl.display(expr))
        // one of the inventions was "(λ (nand $0 $0))",
        // which is the common and useful NOT operation!
    }
}

您可能已经注意到了上面的 domains::circuits 使用。一些域已经为您实现。目前，这仅包括 电路 和 字符串。

待办事项

(你可能是完成其中之一的人！)

• Rust 中的第一类函数评估（并删除 Lisp 解释器）。
• 在 domains::strings 中添加任务生成函数
• 可能评估（例如，查看 domains::strings 如何处理 slice）。
• 惰性评估。
• impl GP for pcfg::Grammar 尚未完成。
• 长跳过（因此 f 被枚举，而不是 (λ (f $0))）
• 合并惰性/非惰性评估（为了使用便捷性）。
• 允许非 &'static str 命名的 Type/TypeScheme。
• 能够在 lambda 表示中包含递归原语。
• 更快的 lambda 演算评估（更少的克隆；上升是否发生了 beta 规约而不是最终的相等比较）。
• PCFG 压缩目前仅估计参数，实际上并未学习程序的片段。似乎采用 适配器语法 的方法是一个不错的方向，也许可以去掉贝叶斯非参数。
• 添加更多学习特性（如 EC 或 GP）
• 添加更多表示
• 添加更多领域