Struct programinduction::lambda::Language

pub struct Language {
    pub primitives: Vec<(String, TypeSchema, f64)>,
    pub invented: Vec<(Expression, TypeSchema, f64)>,
    pub variable_logprob: f64,
    pub symmetry_violations: Vec<(usize, usize, usize)>,
}

(representation) A Language is a registry for primitive and invented expressions in a polymorphically-typed lambda calculus with corresponding production log-probabilities.

Fields

primitives: Vec<(String, TypeSchema, f64)>

invented: Vec<(Expression, TypeSchema, f64)>

variable_logprob: f64

symmetry_violations: Vec<(usize, usize, usize)>

Symmetry breaking prevents certain productions from being made. Specifically, an item (f, i, a) means that enumeration will not yield an application of f where the ith argument is a. This vec must be kept sorted — use via add_symmetry_violation and violates_symmetry.

Methods

impl Language

pub fn uniform(primitives: Vec<(&str, TypeSchema)>) -> Self

A uniform distribution over primitives and invented expressions, as well as the abstraction operation.

pub fn infer(&self, expr: &Expression) -> Result<TypeSchema, InferenceError>

Infer the type of an Expression.

Examples

let mut dsl = Language::uniform(vec![
    ("singleton", ptp!(0; @arrow[tp!(0), tp!(list(tp!(0)))])),
    (">=", ptp!(@arrow[tp!(int), tp!(int), tp!(bool)])),
    ("+", ptp!(@arrow[tp!(int), tp!(int), tp!(int)])),
    ("0", ptp!(int)),
    ("1", ptp!(int)),
]);
dsl.invent(
    // (+ 1)
    Expression::Application(
        Box::new(Expression::Primitive(2)),
        Box::new(Expression::Primitive(4)),
    ),
    0f64,
);
let expr = dsl.parse("(singleton ((λ (>= $0 1)) (#(+ 1) 0)))")
    .unwrap();
assert_eq!(dsl.infer(&expr).unwrap(), ptp!(list(tp!(bool))));

Important traits for Box<R>

impl<R> Read for Box<R> where
    R: Read + ?Sized, impl<W> Write for Box<W> where
    W: Write + ?Sized, impl<I> Iterator for Box<I> where
    I: Iterator + ?Sized,  type Item = <I as Iterator>::Item;

pub fn enumerate(     &self,     tp: TypeSchema ) -> Box<Iterator<Item = (Expression, f64)>>

Enumerate expressions for a request type (including log-probabilities and appropriately instantiated Types):

Examples

The following example can be made more effective using the approach shown with add_symmetry_violation.

use programinduction::lambda::{Expression, Language};

let dsl = Language::uniform(vec![
    ("0", ptp!(int)),
    ("1", ptp!(int)),
    ("+", ptp!(@arrow[tp!(int), tp!(int), tp!(int)])),
]);
let exprs: Vec<Expression> = dsl.enumerate(ptp!(int))
    .take(8)
    .map(|(expr, _log_prior)| expr)
    .collect();

assert_eq!(
    exprs,
    vec![
        Expression::Primitive(0),
        Expression::Primitive(1),
        dsl.parse("(+ 0 0)").unwrap(),
        dsl.parse("(+ 0 1)").unwrap(),
        dsl.parse("(+ 1 0)").unwrap(),
        dsl.parse("(+ 1 1)").unwrap(),
        dsl.parse("(+ 0 (+ 0 0))").unwrap(),
        dsl.parse("(+ 0 (+ 0 1))").unwrap(),
    ]
);

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

Update production probabilities and induce new primitives, with the guarantee that any changes to the language yield net lower prior probability for expressions in the frontier.

Primitives are induced using an approach similar to Cohn et. al. in the 2010 JMLR paper Inducing Tree-Substitution Grammars and in Tim O'Donnell's Fragment Grammars detailed in his 2015 MIT Press book, Productivity and Reuse in Language: A Theory of Linguistic Computation and Storage. However, instead of using Bayesian non-parametrics, we fully evaluate posteriors under each non-trivial fragment (because we already have a tractible space of expressions — the frontiers). We repeatedly select the best fragment and re-evaluate the posteriors until the DSL does not improve.

Examples

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

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

// this is equivalent to one iteration of EC:
let frontiers = dsl.explore(&ec_params, &tasks);
let (dsl, _frontiers) = dsl.compress(&params, &tasks, frontiers);

// there should have been inventions because we started with a non-expressive DSL:
assert!(!dsl.invented.is_empty());

pub fn eval<V, E>(     &self,     expr: &Expression,     evaluator: E,     inps: &[V] ) -> Result<V, E::Error> where     V: Clone + PartialEq + Send + Sync,     E: Evaluator<Space = V>,

Evaluate an expressions based on an input/output pair.

Inputs are given as a sequence representing sequentially applied arguments.

Examples

use programinduction::lambda::{Language, SimpleEvaluator};

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

let dsl = Language::uniform(vec![
    ("0", ptp!(int)),
    ("1", ptp!(int)),
    ("+", ptp!(@arrow[tp!(int), tp!(int), tp!(int)])),
]);
let eval = SimpleEvaluator::of(evaluate);
let expr = dsl.parse("(λ (λ (+ (+ 1 $0) $1)))").unwrap();
let inps = vec![2, 5];
let evaluated = dsl.eval(&expr, eval, &inps).unwrap();
assert_eq!(evaluated, 8);

pub fn eval_arc<V, E>(     &self,     expr: &Expression,     evaluator: &Arc<E>,     inps: &[V] ) -> Result<V, E::Error> where     V: Clone + PartialEq + Send + Sync,     E: Evaluator<Space = V>,

Like eval, but useful in settings with a shared evaluator.

pub fn lazy_eval<V, E>(     &self,     expr: &Expression,     evaluator: E,     inps: &[V] ) -> Result<V, E::Error> where     V: Clone + PartialEq + Send + Sync,     E: LazyEvaluator<Space = V>,

Like eval, but for lazy evaluation with a LazyEvaluator.

pub fn lazy_eval_arc<V, E>(     &self,     expr: &Expression,     evaluator: &Arc<E>,     inps: &[V] ) -> Result<V, E::Error> where     V: Clone + PartialEq + Send + Sync,     E: LazyEvaluator<Space = V>,

Like eval_arc, but for lazy evaluation with a LazyEvaluator.

pub fn likelihood(&self, request: &TypeSchema, expr: &Expression) -> f64

Get the log-likelihood of an expression normalized with other expressions with the given request type.

Examples

let dsl = Language::uniform(vec![
    ("0", ptp!(int)),
    ("1", ptp!(int)),
    ("+", ptp!(@arrow[tp!(int), tp!(int), tp!(int)])),
]);
let req = ptp!(@arrow[tp!(int), tp!(int), tp!(int)]);

let expr = dsl.parse("(λ (λ (+ $0 $1)))").unwrap();
assert_eq!(dsl.likelihood(&req, &expr), -5.545177444479561);

let expr = dsl.parse("(λ (λ (+ (+ $0 1) $1)))").unwrap();
assert_eq!(dsl.likelihood(&req, &expr), -8.317766166719343);

pub fn invent(     &mut self,     expr: Expression,     log_probability: f64 ) -> Result<usize, InferenceError>

Register a new invented expression. If it has a valid type, this will be Ok(num).

Examples

let mut dsl = Language::uniform(vec![
    ("0", ptp!(int)),
    ("1", ptp!(int)),
    ("+", ptp!(@arrow[tp!(int), tp!(int), tp!(int)])),
]);
let expr = dsl.parse("(+ 1)").unwrap();
dsl.invent(expr.clone(), -0.5).unwrap();
assert_eq!(
    dsl.invented.get(0),
    Some(&(expr, ptp!(@arrow[tp!(int), tp!(int)]), -0.5))
);

pub fn add_symmetry_violation(     &mut self,     primitive: usize,     arg_index: usize,     arg: usize )

Introduce a symmetry-breaking pattern to the Language.

Examples

let mut dsl = Language::uniform(vec![
    ("0", ptp!(int)),
    ("1", ptp!(int)),
    ("+", ptp!(@arrow[tp!(int), tp!(int), tp!(int)])),
]);
// disallow (+ 0 _) and (+ _ 0)
dsl.add_symmetry_violation(2, 0, 0);
dsl.add_symmetry_violation(2, 1, 0);
// disallow (+ (+ ..) _), so effort isn't wasted with (+ _ (+ ..))
dsl.add_symmetry_violation(2, 0, 2);

let exprs: Vec<Expression> = dsl.enumerate(ptp!(int))
    .take(6)
    .map(|(expr, _log_prior)| expr)
    .collect();

// enumeration can be far more effective with symmetry-breaking:
assert_eq!(
    exprs,
    vec![
        Expression::Primitive(0),
        Expression::Primitive(1),
        dsl.parse("(+ 1 1)").unwrap(),
        dsl.parse("(+ 1 (+ 1 1))").unwrap(),
        dsl.parse("(+ 1 (+ 1 (+ 1 1)))").unwrap(),
        dsl.parse("(+ 1 (+ 1 (+ 1 (+ 1 1))))").unwrap(),
    ]
);

pub fn violates_symmetry(     &self,     f: &Expression,     index: usize,     x: &Expression ) -> bool

Check whether expressions break symmetry.

Examples

let mut dsl = Language::uniform(vec![
    ("0", ptp!(int)),
    ("1", ptp!(int)),
    ("+", ptp!(@arrow[tp!(int), tp!(int), tp!(int)])),
]);
dsl.add_symmetry_violation(2, 0, 0);
dsl.add_symmetry_violation(2, 1, 0);
dsl.add_symmetry_violation(2, 0, 2);

let f = &Expression::Primitive(2); // +
let x = &Expression::Primitive(0); // 0
assert!(dsl.violates_symmetry(f, 0, x));
let x = &dsl.parse("(+ 1 1)").unwrap();
assert!(dsl.violates_symmetry(f, 0, x));
assert!(!dsl.violates_symmetry(f, 1, x));

pub fn strip_invented(&self, expr: &Expression) -> Expression

Remove all invented expressions by pulling out their underlying expressions.

pub fn parse(&self, inp: &str) -> Result<Expression, ParseError>

The inverse of display.

Lambda expressions take the form (lambda BODY) or (λ BODY), where BODY is an expression that may use a corresponding De Bruijn Index.

pub fn display(&self, expr: &Expression) -> String

The inverse of parse.

pub fn lispify(     &self,     expr: &Expression,     conversions: &HashMap<String, String> ) -> String

Like display, but in a format ready for lisp interpretation.

Trait Implementations

impl Debug for Language

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl Clone for Language

fn clone(&self) -> Language

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl EC for Language

type Expression = Expression

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

type Params = CompressionParams

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

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

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.

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

Update the representation based on findings of expressions that solve [Task]s.

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

The entry point for one iteration of the EC algorithm.

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>,

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

Important traits for Vec<u8>

impl Write for Vec<u8>

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

Enumerate solutions for the given tasks.

Important traits for Vec<u8>

impl Write for Vec<u8>

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

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