Trait programinduction::lambda::Evaluator

source ·

pub trait Evaluator: Sized + Sync {
    type Space: Clone + PartialEq + Send + Sync;
    type Error: Clone + Sync;

    // Required method
    fn evaluate(
        &self,
        primitive: &str,
        inps: &[Self::Space]
    ) -> Result<Self::Space, Self::Error>;

    // Provided method
    fn lift(&self, _f: LiftedFunction<Self::Space, Self>) -> Option<Self::Space> { ... }
}

Expand description

A specification for evaluating lambda calculus expressions in a domain.

Use Language::eval to invoke.

In many simple domains, using SimpleEvaluator::from where you need an Evaluator should suffice. A custom implementation should be done if the domain has first-class functions, so that an Abstraction may by “lifted” into the domain’s value space.

The associated type Space of an Evaluator is the value space of the domain. Evaluators serve as a bridge from Types and Expressions manipulated by this library to concrete values in Rust. It is, therefore, best practice for Space to be an enum with as many variants as there are constructed types, plus one variant for functions. It is guaranteed that evaluation will correspond to whatever the constraints of your types are. In other words, if "plus" takes two numbers and "concat" takes two strings according to the Language, then they will never be called with arguments that aren’t two numbers or two strings respectively. To help illustrate this, note that none of the this library’s example evaluators can panic.

When an Abstraction is encountered and passed into a function, a lift is attempted to bring the abstraction into the domain’s Space. For example, if "map" takes a function from an int to an int, and it gets passed λx.(+ 1 x), then an evaluator for that abstraction is wrapped into a LiftedFunction and passed into lift to bring the function into the value space, before finally being used on evaluate with the "map" primitive. An example below features "map" calling a lifted function.

Examples

An evaluator for a domain that doesn’t have first-class functions:

use polytype::{ptp, tp};
use programinduction::lambda::{Language, SimpleEvaluator};

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

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

// Evaluator<Space = i32>
let eval = SimpleEvaluator::from(evaluate);

A slightly more complicated domain, but still without first-class functions:

use polytype::{ptp, tp};
use programinduction::lambda::{Language, SimpleEvaluator};

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

#[derive(Clone, PartialEq)]
enum ArithSpace {
    Bool(bool),
    Num(i32),
}
use ArithSpace::*;

fn evaluate(primitive: &str, inps: &[ArithSpace]) -> Result<ArithSpace, ()> {
    match primitive {
        "0" => Ok(Num(0)),
        "1" => Ok(Num(1)),
        "+" => match (&inps[0], &inps[1]) {
            (&Num(x), &Num(y)) => Ok(Num(x + y)),
            _ => unreachable!(),
        },
        "eq" => match (&inps[0], &inps[1]) {
            (&Num(x), &Num(y)) => Ok(Bool(x == y)),
            _ => unreachable!(),
        },
        "not" => match inps[0] {
            Bool(b) => Ok(Bool(!b)),
            _ => unreachable!(),
        },
        _ => unreachable!(),
    }
}

// Evaluator<Space = ArithSpace>
let eval = SimpleEvaluator::from(evaluate);

For a domain with first-class functions, things get more complicated:

use polytype::{ptp, tp};
use programinduction::lambda::{Evaluator, Language, LiftedFunction};

let dsl = Language::uniform(vec![
    ("0", ptp!(int)),
    ("1", ptp!(int)),
    ("+", ptp!(@arrow[tp!(int), tp!(int), tp!(int)])),
    ("singleton", ptp!(@arrow[tp!(int), tp!(list(tp!(int)))])),
    ("chain", ptp!(0; @arrow[
        tp!(list(tp!(0))),
        tp!(list(tp!(0))),
        tp!(list(tp!(0))),
    ])),
    ("map", ptp!(0, 1; @arrow[
        tp!(@arrow[tp!(0), tp!(1)]),
        tp!(list(tp!(0))),
        tp!(list(tp!(0))),
    ])),
]);
// note: the only constructable lists in this dsl are of ints.

#[derive(Clone)]
struct ListError(&'static str);

#[derive(Clone, PartialEq)]
enum ListSpace {
    Num(i32),
    NumList(Vec<i32>),
    Func(LiftedFunction<ListSpace, ListsEvaluator>),
}
use ListSpace::*;

#[derive(Copy, Clone)]
struct ListsEvaluator;
impl Evaluator for ListsEvaluator {
    type Space = ListSpace;
    type Error = ListError;
    fn evaluate(&self, primitive: &str, inps: &[Self::Space]) -> Result<Self::Space, Self::Error> {
        match primitive {
            "0" => Ok(Num(0)),
            "1" => Ok(Num(1)),
            "+" => match (&inps[0], &inps[1]) {
                (&Num(x), &Num(y)) => Ok(Num(x + y)),
                _ => unreachable!(),
            },
            "singleton" => match inps[0] {
                Num(x) => Ok(NumList(vec![x])),
                _ => unreachable!(),
            },
            "chain" => match (&inps[0], &inps[1]) {
                (&NumList(ref xs), &NumList(ref ys)) => {
                    Ok(NumList(xs.into_iter().chain(ys).cloned().collect()))
                }
                _ => unreachable!(),
            },
            "map" => match (&inps[0], &inps[1]) {
                (&Func(ref f), &NumList(ref xs)) => Ok(NumList(xs.into_iter()
                    .map(|x| {
                        f.eval(&[Num(x.clone())]).and_then(|v| match v {
                            Num(y) => Ok(y),
                            _ => Err(ListError("map given invalid function")),
                        })
                    })
                    .collect::<Result<_, _>>()?)),
                _ => unreachable!(),
            },
            _ => unreachable!(),
        }
    }
    fn lift(&self, f: LiftedFunction<Self::Space, Self>) -> Option<Self::Space> {
        Some(Func(f))
    }
}

// Evaluator<Space = ListSpace, Error = ListError>
let eval = ListsEvaluator;