Struct programinduction::trs::Lexicon

pub struct Lexicon(/* private fields */);

(representation) Manages the syntax of a term rewriting system.

Implementations

impl Lexicon

pub fn new( operators: Vec<(u32, Option<String>, TypeScheme)>, deterministic: bool, ctx: TypeContext ) -> Lexicon

Construct a Lexicon with only background term_rewriting::Operators.

Example

See polytype::ptp for details on constructing polytype::TypeSchemes.

use polytype::{ptp, tp, Context as TypeContext};
use programinduction::trs::Lexicon;

let operators = vec![
    (2, Some("PLUS".to_string()), ptp![@arrow[tp!(int), tp!(int), tp!(int)]]),
    (1, Some("SUCC".to_string()), ptp![@arrow[tp!(int), tp!(int)]]),
    (0, Some("ZERO".to_string()), ptp![int]),
];
let deterministic = false;

let lexicon = Lexicon::new(operators, deterministic, TypeContext::default());

pub fn from_signature( signature: Signature, ops: Vec<TypeScheme>, vars: Vec<TypeScheme>, background: Vec<Rule>, templates: Vec<RuleContext>, deterministic: bool, ctx: TypeContext ) -> Lexicon

Convert a term_rewriting::Signature into a Lexicon:

• ops are types for the term_rewriting::Operators
• vars are types for the term_rewriting::Variables,
• background are term_rewriting::Rules that never change
• templates are term_rewriting::RuleContexts that can serve as templates during learning

Example

See polytype::ptp for details on constructing polytype::TypeSchemes.

use polytype::{ptp, tp, Context as TypeContext};
use programinduction::trs::Lexicon;
use term_rewriting::{Signature, parse_rule, parse_rulecontext};

let mut sig = Signature::default();

let vars = vec![];

let mut ops = vec![];
sig.new_op(2, Some("PLUS".to_string()));
ops.push(ptp![@arrow[tp!(int), tp!(int), tp!(int)]]);
sig.new_op(1, Some("SUCC".to_string()));
ops.push(ptp![@arrow[tp!(int), tp!(int)]]);
sig.new_op(0, Some("ZERO".to_string()));
ops.push(ptp![int]);

let background = vec![
    parse_rule(&mut sig, "PLUS(x_ ZERO) = x_").expect("parsed rule"),
    parse_rule(&mut sig, "PLUS(x_ SUCC(y_)) = SUCC(PLUS(x_ y_))").expect("parsed rule"),
];

let templates = vec![
    parse_rulecontext(&mut sig, "[!] = [!]").expect("parsed rulecontext"),
];

let deterministic = false;

let lexicon = Lexicon::from_signature(sig, ops, vars, background, templates, deterministic, TypeContext::default());

pub fn has_op(&self, name: Option<&str>, arity: u32) -> Option<Operator>

Return the specified operator if possible.

pub fn free_vars(&self) -> Vec<TypeVar>

All the free type variables in the lexicon.

pub fn context(&self) -> TypeContext

pub fn infer_context( &self, context: &Context, ctx: &mut TypeContext ) -> Result<TypeScheme, TypeError>

Infer the polytype::TypeScheme associated with a term_rewriting::Context.

Example

use polytype::{ptp, tp, Context as TypeContext};
use programinduction::trs::Lexicon;
use term_rewriting::{Context, Signature, parse_rule};

let mut sig = Signature::default();

let vars = vec![];

let mut ops = vec![];
sig.new_op(2, Some("PLUS".to_string()));
ops.push(ptp![@arrow[tp!(int), tp!(int), tp!(int)]]);
let succ = sig.new_op(1, Some("SUCC".to_string()));
ops.push(ptp![@arrow[tp!(int), tp!(int)]]);
sig.new_op(0, Some("ZERO".to_string()));
ops.push(ptp![int]);

let background = vec![];
let templates = vec![];

let deterministic = false;

let lexicon = Lexicon::from_signature(sig, ops, vars, background, templates, deterministic, TypeContext::default());

let context = Context::Application {
    op: succ,
    args: vec![Context::Hole]
};
let mut ctx = lexicon.context();

let inferred_scheme = lexicon.infer_context(&context, &mut ctx).unwrap();

assert_eq!(inferred_scheme, ptp![int]);

pub fn infer_rulecontext( &self, context: &RuleContext, ctx: &mut TypeContext ) -> Result<TypeScheme, TypeError>

Infer the TypeScheme associated with a RuleContext.

pub fn infer_rule( &self, rule: &Rule, ctx: &mut TypeContext ) -> Result<TypeScheme, TypeError>

Infer the TypeScheme associated with a Rule.

pub fn infer_rules( &self, rules: &[Rule], ctx: &mut TypeContext ) -> Result<TypeScheme, TypeError>

Infer the TypeScheme associated with a collection of Rules.

pub fn infer_op(&self, op: &Operator) -> Result<TypeScheme, TypeError>

Infer the TypeScheme associated with a Rule.

pub fn sample_term<R: Rng>( &mut self, rng: &mut R, scheme: &TypeScheme, ctx: &mut TypeContext, atom_weights: (f64, f64, f64), invent: bool, variable: bool, max_size: usize ) -> Result<Term, SampleError>

Sample a term_rewriting::Term.

Example

use polytype::{ptp, tp, Context as TypeContext};
use programinduction::trs::Lexicon;
use rand::{rngs::SmallRng, SeedableRng};

let operators = vec![
    (2, Some("PLUS".to_string()), ptp![@arrow[tp!(int), tp!(int), tp!(int)]]),
    (1, Some("SUCC".to_string()), ptp![@arrow[tp!(int), tp!(int)]]),
    (0, Some("ZERO".to_string()), ptp![int]),
];
let deterministic = false;
let mut lexicon = Lexicon::new(operators, deterministic, TypeContext::default());

let scheme = ptp![int];
let mut ctx = lexicon.context();
let invent = true;
let variable = true;
let atom_weights = (0.5, 0.25, 0.25);
let max_size = 50;

let rng = &mut SmallRng::from_seed([1u8; 32]);
let term = lexicon.sample_term(rng, &scheme, &mut ctx, atom_weights, invent, variable, max_size).unwrap();

pub fn sample_term_from_context<R: Rng>( &mut self, rng: &mut R, context: &Context, ctx: &mut TypeContext, atom_weights: (f64, f64, f64), invent: bool, variable: bool, max_size: usize ) -> Result<Term, SampleError>

Sample a Term conditioned on a Context rather than a TypeScheme.

pub fn sample_rule<R: Rng>( &mut self, rng: &mut R, scheme: &TypeScheme, ctx: &mut TypeContext, atom_weights: (f64, f64, f64), invent: bool, max_size: usize ) -> Result<Rule, SampleError>

Sample a Rule.

pub fn sample_rule_from_context<R: Rng>( &mut self, rng: &mut R, context: RuleContext, ctx: &mut TypeContext, atom_weights: (f64, f64, f64), invent: bool, max_size: usize ) -> Result<Rule, SampleError>

Sample a Rule conditioned on a Context rather than a TypeScheme.

pub fn logprior_term( &self, term: &Term, scheme: &TypeScheme, ctx: &mut TypeContext, atom_weights: (f64, f64, f64), invent: bool ) -> Result<f64, SampleError>

Give the log probability of sampling a Term.

pub fn logprior_rule( &self, rule: &Rule, scheme: &TypeScheme, ctx: &mut TypeContext, atom_weights: (f64, f64, f64), invent: bool ) -> Result<f64, SampleError>

Give the log probability of sampling a Rule.

pub fn logprior_utrs( &self, utrs: &UntypedTRS, schemes: &[TypeScheme], p_rule: f64, ctx: &mut TypeContext, atom_weights: (f64, f64, f64), invent: bool ) -> Result<f64, SampleError>

Give the log probability of sampling a TRS.

pub fn combine<R: Rng>( &self, rng: &mut R, trs1: &TRS, trs2: &TRS ) -> Result<TRS, TypeError>

merge two TRS into a single TRS.

Trait Implementations

impl Clone for Lexicon

fn clone(&self) -> Lexicon

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for Lexicon

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

Formats the value using the given formatter.

impl Display for Lexicon

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

Formats the value using the given formatter.

impl GP<[Rule]> for Lexicon

type Expression = TRS

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, trs: &Self::Expression, _obs: &[Rule] ) -> 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: &[Rule] ) -> Vec<Self::Expression>

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

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

impl PartialEq for Lexicon

fn eq(&self, other: &Lexicon) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.