Trait programinduction::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.

Object Safety

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