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. Evaluator
s
serve as a bridge from Type
s and Expression
s 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;