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

Implementations

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.

pub fn enumerate(&self) -> Box<dyn Iterator<Item = (AppliedRule, f64)>>

Enumerate statements in the PCFG, including log-probabilities.

Examples

use polytype::tp;
use programinduction::pcfg::{AppliedRule, 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 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(),
    ]
);

pub fn enumerate_nonterminal( &self, nonterminal: Type ) -> Box<dyn 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 polytype::tp;
use programinduction::pcfg::{task_by_evaluation, Grammar, Rule};

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.

use polytype::tp;
use programinduction::pcfg::{Grammar, Rule};
use rand::{rngs::SmallRng, SeedableRng};

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 SmallRng::from_seed([1u8; 32]));
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 polytype::tp;
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 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 Debug for Grammar

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

Formats the value using the given formatter.

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

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

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

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: TypeScheme, termination_condition: F)

where F: FnMut(Self::Expression, f64) -> bool,

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.

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.

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.

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.

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.

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.

fn genesis<R: Rng>( &self, _params: &Self::Params, rng: &mut R, pop_size: usize, tp: &TypeScheme ) -> 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, _obs: &() ) -> Vec<Self::Expression>

Mutate a single program, potentially producing multiple offspring

fn crossover<R: Rng>( &self, params: &Self::Params, rng: &mut R, parent1: &Self::Expression, parent2: &Self::Expression, _obs: &() ) -> 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.

fn init<R: Rng>( &self, params: &Self::Params, rng: &mut R, gpparams: &GPParams, task: &impl Task<Observation, Representation = Self, Expression = Self::Expression> ) -> 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 validate_offspring( &self, _params: &Self::Params, _population: &[(Self::Expression, f64)], _children: &[Self::Expression], _offspring: &mut Vec<Self::Expression> )

This should be a filter-like operation on offspring. The intended semantics is that validate_offspring reduces the set of newly created individuals in offspring to just those viable for consideration as part of the total population, taking into account other children that are part of the current generation. This allows you to do things like ensure a population of unique individuals.

fn evolve<R: Rng>( &self, params: &Self::Params, rng: &mut R, gpparams: &GPParams, task: &impl Task<Observation, Representation = Self, Expression = Self::Expression>, 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.