Trait EC

Source
pub trait EC<Observation: ?Sized>: Sync + Sized {
    type Expression: Clone + Send + Sync;
    type Params;

    // Required methods
    fn enumerate<F>(&self, tp: TypeScheme, termination_condition: F)
       where F: Fn(Self::Expression, f64) -> bool + Sync;
    fn compress(
        &self,
        params: &Self::Params,
        tasks: &[impl Task<Observation, Representation = Self, Expression = Self::Expression>],
        frontiers: Vec<ECFrontier<Self::Expression>>,
    ) -> (Self, Vec<ECFrontier<Self::Expression>>);

    // Provided methods
    fn ec(
        &self,
        ecparams: &ECParams,
        params: &Self::Params,
        tasks: &[impl Task<Observation, Representation = Self, Expression = Self::Expression>],
    ) -> (Self, Vec<ECFrontier<Self::Expression>>) { ... }
    fn ec_with_recognition<T, R>(
        &self,
        ecparams: &ECParams,
        params: &Self::Params,
        tasks: &[T],
        recognizer: R,
    ) -> (Self, Vec<ECFrontier<Self::Expression>>)
       where T: Task<Observation, Representation = Self, Expression = Self::Expression>,
             R: FnOnce(&Self, &[T]) -> Vec<Self> { ... }
    fn explore(
        &self,
        ec_params: &ECParams,
        tasks: &[impl Task<Observation, Representation = Self, Expression = Self::Expression>],
    ) -> Vec<ECFrontier<Self::Expression>> { ... }
    fn explore_with_recognition(
        &self,
        ec_params: &ECParams,
        tasks: &[impl Task<Observation, Representation = Self, Expression = Self::Expression>],
        representations: &[Self],
    ) -> Vec<ECFrontier<Self::Expression>> { ... }
}
Expand description

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:

use programinduction::domains::circuits;
use programinduction::{lambda, ECParams, EC};
use rand::{rngs::SmallRng, SeedableRng};

let mut dsl = circuits::dsl();

let rng = &mut SmallRng::from_seed([1u8; 32]);
let tasks = circuits::make_tasks(rng, 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,
);

Required Associated Types§

Source

type Expression: Clone + Send + Sync

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

Source

type Params

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

Required Methods§

Source

fn enumerate<F>(&self, tp: TypeScheme, termination_condition: F)
where F: Fn(Self::Expression, f64) -> bool + Sync,

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).

Source

fn compress( &self, params: &Self::Params, tasks: &[impl Task<Observation, Representation = Self, Expression = Self::Expression>], frontiers: Vec<ECFrontier<Self::Expression>>, ) -> (Self, Vec<ECFrontier<Self::Expression>>)

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§

Source

fn ec( &self, ecparams: &ECParams, params: &Self::Params, tasks: &[impl Task<Observation, Representation = Self, Expression = Self::Expression>], ) -> (Self, Vec<ECFrontier<Self::Expression>>)

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::domains::circuits;
use programinduction::{lambda, ECParams, EC};
use rand::{rngs::SmallRng, SeedableRng};

let mut dsl = circuits::dsl();

let rng = &mut SmallRng::from_seed([1u8; 32]);
let tasks = circuits::make_tasks(rng, 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 (expr, _, _) in &dsl.invented {
    println!("invented {}", dsl.display(expr))
}
Source

fn ec_with_recognition<T, R>( &self, ecparams: &ECParams, params: &Self::Params, tasks: &[T], recognizer: R, ) -> (Self, Vec<ECFrontier<Self::Expression>>)
where T: Task<Observation, Representation = Self, Expression = Self::Expression>, R: FnOnce(&Self, &[T]) -> Vec<Self>,

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.

Source

fn explore( &self, ec_params: &ECParams, tasks: &[impl Task<Observation, Representation = Self, Expression = Self::Expression>], ) -> Vec<ECFrontier<Self::Expression>>

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 polytype::tp;
use programinduction::pcfg::{Grammar, Rule, task_by_evaluation};
use programinduction::{EC, ECParams};

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());
Source

fn explore_with_recognition( &self, ec_params: &ECParams, tasks: &[impl Task<Observation, Representation = Self, Expression = Self::Expression>], representations: &[Self], ) -> Vec<ECFrontier<Self::Expression>>

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

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§

Source§

impl<Observation: ?Sized> EC<Observation> for Language

Source§

impl<Observation: ?Sized> EC<Observation> for Grammar