Trait EC

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>> { ... }
}

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

type Expression: Clone + Send + Sync

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

type Params

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

Required Methods

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

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

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

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.

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

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

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

type Expression = Expression

type Params = CompressionParams

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

type Expression = AppliedRule

type Params = EstimationParams