Struct programinduction::pcfg::Grammar

pub struct Grammar {
    pub start: Type,
    pub rules: HashMap<Type, Vec<Rule>>,
}

(representation) Probabilistic context-free grammar. Currently cannot handle bound variables or polymorphism.

Each nonterminal corresponds to a non-polymorphic Type.

Fields

start: Type

rules: HashMap<Type, Vec<Rule>>

Methods

impl Grammar

pub fn new(start: Type, all_rules: Vec<Rule>) -> Self

Rules are normalized according to their associated nonterminal proportional to the supplied probabilities.

So each rules' logprob is not treated as log-probability in this constructor, they are treated like un-normalized probabilities.

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) -> Box<Iterator<Item = (AppliedRule, f64)>>

Enumerate statements in the PCFG, including log-probabilities.

Examples

use programinduction::pcfg::{Grammar, Rule, AppliedRule};

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 exprs: Vec<AppliedRule> = g.enumerate()
    .take(8)
    .map(|(ar, _logprior)| ar)
    .collect();

assert_eq!(
    exprs,
    vec![
        g.parse("0").unwrap(),
        g.parse("1").unwrap(),
        g.parse("plus(0,0)").unwrap(),
        g.parse("plus(0,1)").unwrap(),
        g.parse("plus(1,0)").unwrap(),
        g.parse("plus(1,1)").unwrap(),
        g.parse("plus(0,plus(0,0))").unwrap(),
        g.parse("plus(0,plus(0,1))").unwrap(),
    ]
);

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_nonterminal(     &self,     nonterminal: Type ) -> Box<Iterator<Item = (AppliedRule, f64)>>

Enumerate subsentences in the Grammar for the given nonterminal.

pub fn update_parameters(     &mut self,     params: &EstimationParams,     sentences: &[AppliedRule] )

Set parameters based on supplied sentences. This is performed by Grammar::compress.

pub fn eval<V, E, F>(&self, ar: &AppliedRule, evaluator: &F) -> Result<V, E> where     F: Fn(&str, &[V]) -> Result<V, E>,

Evaluate a sentence using a evaluator.

Examples

use programinduction::pcfg::{Grammar, Rule, task_by_evaluation};

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 expr = g.parse("plus(1, plus(1, plus(1,1)))").unwrap();
assert_eq!(Ok(4), g.eval(&expr, &evaluator));

pub fn sample<R: Rng>(&self, tp: &Type, rng: &mut R) -> AppliedRule

Sample a statement of the PCFG.

#[macro_use] extern crate polytype;
extern crate programinduction;
extern crate rand;

use programinduction::pcfg::{Grammar, Rule};

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 ar = g.sample(&tp!(EXPR), &mut rand::thread_rng());
assert_eq!(&ar.0, &tp!(EXPR));
println!("{}", g.display(&ar));

pub fn likelihood(&self, ar: &AppliedRule) -> f64

Get the log-likelihood of an expansion for the given nonterminal.

Examples

use programinduction::pcfg::{Grammar, Rule};

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),
        Rule::new("zero?", tp!(@arrow[tp!(EXPR), tp!(BOOL)]), 1.0),
        Rule::new("if", tp!(@arrow[tp!(BOOL), tp!(EXPR), tp!(EXPR)]), 1.0),
        Rule::new("nand", tp!(@arrow[tp!(BOOL), tp!(BOOL), tp!(BOOL)]), 1.0),
    ]
);

let expr = g.parse("plus(0,0)").unwrap();
assert_eq!(g.likelihood(&expr), -4.1588830833596715);

let expr = g.parse("if( zero?(plus(0 , 0)), 1, 0)").unwrap();
assert_eq!(g.likelihood(&expr), -7.6246189861593985);

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

Parse a valid sentence in the Grammar. The inverse of display.

Non-terminating production rules are followed by parentheses containing comma-separated productions plus(0, 1). Extraneous white space is ignored.

pub fn parse_nonterminal(     &self,     inp: &str,     nonterminal: Type ) -> Result<AppliedRule, ParseError>

Parse a valid subsentence in the Grammar which is producible from the given nonterminal.

pub fn display(&self, ar: &AppliedRule) -> String

The inverse of parse.

Trait Implementations

impl Debug for Grammar

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

Formats the value using the given formatter.

impl Clone for Grammar

fn clone(&self) -> Grammar

Returns a copy of the value.

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

Performs copy-assignment from source.

impl EC for Grammar

type Expression = AppliedRule

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

type Params = EstimationParams

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

fn enumerate<F>(&self, tp: TypeSchema, termination_condition: F) where     F: FnMut(Self::Expression, f64) -> bool,

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

This is exactly the same as Grammar::update_parameters, but optimized to deal with frontiers.

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.

impl GP for Grammar

type Expression = AppliedRule

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

type Params = GeneticParams

Extra parameters for a representation go here.

Important traits for Vec<u8>

impl Write for Vec<u8>

fn genesis<R: Rng>(     &self,     _params: &Self::Params,     rng: &mut R,     pop_size: usize,     tp: &TypeSchema ) -> Vec<Self::Expression>

Create an initial population for a particular requesting type.

fn mutate<R: Rng>(     &self,     params: &Self::Params,     rng: &mut R,     prog: &Self::Expression ) -> Self::Expression

Mutate a single program.

Important traits for Vec<u8>

impl Write for Vec<u8>

fn crossover<R: Rng>(     &self,     params: &Self::Params,     rng: &mut R,     parent1: &Self::Expression,     parent2: &Self::Expression ) -> Vec<Self::Expression>

Perform crossover between two programs. There must be at least one child.

fn tournament<'a, R: Rng>(     &self,     rng: &mut R,     tournament_size: usize,     population: &'a [(Self::Expression, f64)] ) -> &'a Self::Expression

A tournament selects an individual from a population.

Important traits for Vec<u8>

impl Write for Vec<u8>

fn init<R: Rng, O: Sync>(     &self,     params: &Self::Params,     rng: &mut R,     gpparams: &GPParams,     task: &Task<Self, Self::Expression, O> ) -> Vec<(Self::Expression, f64)>

Initializes a population, which is a list of programs and their scores sorted by score. The most-fit individual is the first element in the population.

fn evolve<R: Rng, O: Sync>(     &self,     params: &Self::Params,     rng: &mut R,     gpparams: &GPParams,     task: &Task<Self, Self::Expression, O>,     population: &mut Vec<(Self::Expression, f64)> )

Evolves a population. This will repeatedly run a Bernoulli trial with parameter [mutation_prob] and perform mutation or crossover depending on the outcome until [n_delta] expressions are determined.