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, ¶ms, &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§
Sourcetype Expression: Clone + Send + Sync
type Expression: Clone + Send + Sync
An Expression is a sentence in the representation. Tasks are solved by Expressions.
Required Methods§
Sourcefn enumerate<F>(&self, tp: TypeScheme, termination_condition: F)
fn enumerate<F>(&self, tp: TypeScheme, termination_condition: F)
Iterate over Expression
s 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).
Sourcefn compress(
&self,
params: &Self::Params,
tasks: &[impl Task<Observation, Representation = Self, Expression = Self::Expression>],
frontiers: Vec<ECFrontier<Self::Expression>>,
) -> (Self, Vec<ECFrontier<Self::Expression>>)
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 Task
s.
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§
Sourcefn ec(
&self,
ecparams: &ECParams,
params: &Self::Params,
tasks: &[impl Task<Observation, Representation = Self, Expression = Self::Expression>],
) -> (Self, Vec<ECFrontier<Self::Expression>>)
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, ¶ms, &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))
}
Sourcefn 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 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.
Sourcefn explore(
&self,
ec_params: &ECParams,
tasks: &[impl Task<Observation, Representation = Self, Expression = Self::Expression>],
) -> Vec<ECFrontier<Self::Expression>>
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());
Sourcefn explore_with_recognition(
&self,
ec_params: &ECParams,
tasks: &[impl Task<Observation, Representation = Self, Expression = Self::Expression>],
representations: &[Self],
) -> 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>>
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.