Trait programinduction::EC[−][src]

pub trait EC: Send + Sync + Sized {
    type Expression: Clone + Send + Sync;
    type Params;
    fn enumerate<F>(&self, tp: TypeSchema, termination_condition: F)
    where
        F: Fn(Self::Expression, f64) -> bool + Send + Sync;

    fn compress<O: Sync>(
        &self, 
        params: &Self::Params, 
        tasks: &[Task<Self, Self::Expression, O>], 
        frontiers: Vec<ECFrontier<Self>>
    ) -> (Self, Vec<ECFrontier<Self>>);

    fn ec<O: Sync>(
        &self, 
        ecparams: &ECParams, 
        params: &Self::Params, 
        tasks: &[Task<Self, Self::Expression, O>]
    ) -> (Self, Vec<ECFrontier<Self>>) { ... }

    fn ec_with_recognition<O: Sync, R>(
        &self, 
        ecparams: &ECParams, 
        params: &Self::Params, 
        tasks: &[Task<Self, Self::Expression, O>], 
        recognizer: R
    ) -> (Self, Vec<ECFrontier<Self>>)
    where
        R: FnOnce(&Self, &[Task<Self, Self::Expression, O>]) -> Vec<Self>,
    { ... }

    fn explore<O: Sync>(
        &self, 
        ec_params: &ECParams, 
        tasks: &[Task<Self, Self::Expression, O>]
    ) -> Vec<ECFrontier<Self>> { ... }

    fn explore_with_recognition<O: Sync>(
        &self, 
        ec_params: &ECParams, 
        tasks: &[Task<Self, Self::Expression, O>], 
        representations: &[Self]
    ) -> Vec<ECFrontier<Self>> { ... }
}

A kind of representation suitable for exploration-compression.

For details on the EC algorithm, see the module-level documentation here.

Implementors of EC need only provide an enumerate and compress methods. By doing so, we provide the ec, ec_with_recognition, and explore methods.

Typically, you will interact with this trait via existing implementations, such as with lambda::Language or pcfg::Grammar.

Examples

Using an existing domain in the lambda calculus representation lambda::Language:

extern crate programinduction;
use programinduction::{lambda, ECParams, EC};
use programinduction::domains::circuits;

fn main() {
    let mut dsl = circuits::dsl();
    let tasks = circuits::make_tasks(250);
    let ec_params = ECParams {
        frontier_limit: 10,
        search_limit_timeout: None,
        search_limit_description_length: Some(9.0),
    };
    let params = lambda::CompressionParams::default();

    let mut frontiers = Vec::new();
    for _ in 0..5 {
        let (new_dsl, new_frontiers) = dsl.ec(&ec_params, &params, &tasks);
        dsl = new_dsl;
        frontiers = new_frontiers;
    }
    let n_invented = dsl.invented.len();
    let n_hit = frontiers.iter().filter(|f| !f.is_empty()).count();
    println!("hit {} of {} using {} invented primitives", n_hit, tasks.len(), n_invented);
}

Associated Types

An Expression is a sentence in the representation. Tasks are solved by Expressions.

Many representations have some parameters for compression. They belong here.

Required Methods

Iterate over Expressions for a given type, with their corresponding log-priors, until a condition is met. This enumeration should be best-first: the log-prior of enumerated expressions should generally increase, so simple expressions are enumerated first.

The termination_condition acts as a callback for each enumerated (Expression, f64). If it responds with true, enumeration must stop (i.e. this method call should terminate).

Update the representation based on findings of expressions that solve Tasks.

The frontiers argument, and similar return value, must always be of the same size as tasks. Each frontier is a possibly-empty list of expressions that solve the corresponding task, and the log-prior and log-likelihood for that expression.

Provided Methods

The entry point for one iteration of the EC algorithm.

Returned solutions include the log-prior and log-likelihood of successful expressions.

Examples

use programinduction::{lambda, ECParams, EC};
use programinduction::domains::circuits;

let mut dsl = circuits::dsl();
let tasks = circuits::make_tasks(250);
let ec_params = ECParams {
    frontier_limit: 10,
    search_limit_timeout: None,
    search_limit_description_length: Some(8.0),
};
let params = lambda::CompressionParams::default();

let mut frontiers = Vec::new();
for i in 1..6 {
    println!("running EC iteration {}", i);

    let (new_dsl, new_frontiers) = dsl.ec(&ec_params, &params, &tasks);
    dsl = new_dsl;
    frontiers = new_frontiers;

    let n_hit = frontiers.iter().filter(|f| !f.is_empty()).count();
    println!("hit {} of {}", n_hit, tasks.len());
}
assert!(!dsl.invented.is_empty());
for &(ref expr, _, _) in &dsl.invented {
    println!("invented {}", dsl.display(expr))
}

The entry point for one iteration of the EC algorithm with a recognizer, very similar to ec.

The recognizer supplies a representation for every task which is then used for exploration-compression.

Returned solutions include the log-prior and log-likelihood of successful expressions.

ⓘImportant traits for Vec<u8>

Enumerate solutions for the given tasks.

Considers a "solution" to be any expression with finite log-probability according to a task's oracle.

Each task will be associated with at most params.frontier_limit many such expressions, and enumeration is stopped when params.search_limit valid expressions have been checked.

Examples

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

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

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: Some(std::time::Duration::new(1, 0)),
    search_limit_description_length: None,
};
// task: the number 4
let task = task_by_evaluation(&evaluator, &4, tp!(EXPR));

let frontiers = g.explore(&ec_params, &[task]);
assert!(frontiers[0].best_solution().is_some());
ⓘImportant traits for Vec<u8>

Like explore, but with specific "recognized" representations for each task.

Implementors