Skip to content

Instantly share code, notes, and snippets.

@davidad
Last active January 25, 2020 18:58
Show Gist options
  • Save davidad/402c0e09a723e0f53e94da69ff83ca15 to your computer and use it in GitHub Desktop.
Save davidad/402c0e09a723e0f53e94da69ff83ca15 to your computer and use it in GitHub Desktop.
"Closed" AST implementation vs "extensible" implementation using dynamic dispatch
#![feature(test)]
mod expr_adt {
pub enum Expr {
Var(String),
Const(f64),
Plus(Box<Expr>, Box<Expr>),
Times(Box<Expr>, Box<Expr>),
}
pub fn gen_evaluator<'a, F : 'a + Fn(&str) -> f64> (env: F) -> Box<dyn 'a + Fn(&Expr) -> f64> {
fn rec<F : Fn(&str) -> f64>(env: &F, e: &Expr) -> f64 {
match e {
Expr::Var(v) => env(v),
Expr::Const(x) => *x,
Expr::Plus(e1, e2) => rec(env,e1) + rec(env,e2),
Expr::Times(e1, e2) => rec(env,e1) * rec(env,e2),
}
}
Box::new(move |e| rec(&env,e))
}
pub fn x_evaluator(x: f64) -> Box<dyn Fn(&Expr) -> f64> {
gen_evaluator(move |v: &str| match v { "x" => x, _ => panic!("No such variable {}", v) })
}
pub use self::Expr::*;
}
mod expr_trait {
pub trait Expr {
fn eval(&self, env: &dyn Fn(&str) -> f64) -> f64;
}
pub struct Var(pub String);
pub struct Const(pub f64);
pub struct Plus(pub Box<dyn Expr>, pub Box<dyn Expr>);
pub struct Times(pub Box<dyn Expr>, pub Box<dyn Expr>);
impl Expr for Var {
fn eval(&self, env: &dyn Fn(&str) -> f64) -> f64 {
match self { Var(v) => env(v) }
}
}
impl Expr for Const {
fn eval(&self, _: &dyn Fn(&str) -> f64) -> f64 {
match self { Const(c) => *c }
}
}
impl Expr for Plus {
fn eval(&self, env: &dyn Fn(&str) -> f64) -> f64 {
match self { Plus(e1, e2) => e1.eval(env) + e2.eval(env) }
}
}
impl Expr for Times {
fn eval(&self, env: &dyn Fn(&str) -> f64) -> f64 {
match self { Times(e1, e2) => e1.eval(env) * e2.eval(env) }
}
}
pub fn gen_evaluator<'a, F : 'a + Fn(&str) -> f64> (env: F) -> Box<dyn 'a + Fn(&dyn Expr) -> f64> {
Box::new(move |e| e.eval(&env))
}
pub fn x_evaluator(x: f64) -> Box<dyn Fn(&dyn Expr) -> f64> {
gen_evaluator(move |v: &str| match v { "x" => x, _ => panic!("No such variable {}", v) })
}
}
pub fn main() {
let example_expr_adt = expr_adt::Plus(Box::new(expr_adt::Times(Box::new(expr_adt::Times(Box::new(expr_adt::Const(2.0)),Box::new(expr_adt::Var("x".to_string())))),Box::new(expr_adt::Var("x".to_string())))),Box::new(expr_adt::Const(4.0)));
let x_evaluator_2_adt = expr_adt::x_evaluator(2.0);
println!("{}", x_evaluator_2_adt(&example_expr_adt));
let example_expr_trait = expr_trait::Plus(Box::new(expr_trait::Times(Box::new(expr_trait::Times(Box::new(expr_trait::Const(2.0)),Box::new(expr_trait::Var("x".to_string())))),Box::new(expr_trait::Var("x".to_string())))),Box::new(expr_trait::Const(4.0)));
let x_evaluator_2_trait = expr_trait::x_evaluator(2.0);
println!("{}", x_evaluator_2_trait(&example_expr_trait));
struct Div(Box<dyn expr_trait::Expr>, Box<dyn expr_trait::Expr>);
impl expr_trait::Expr for Div {
fn eval(&self, env: &dyn Fn(&str) -> f64) -> f64 {
match self { Div(e1, e2) => e1.eval(env) / e2.eval(env) }
}
}
let div_example = expr_trait::Plus(Box::new(expr_trait::Const(1.0)), Box::new(Div(Box::new(expr_trait::Plus(Box::new(expr_trait::Times(Box::new(expr_trait::Times(Box::new(expr_trait::Const(2.0)),Box::new(expr_trait::Var("x".to_string())))),Box::new(expr_trait::Var("x".to_string())))),Box::new(expr_trait::Const(4.0)))),Box::new(expr_trait::Const(3.0)))));
println!("{}", x_evaluator_2_trait(&div_example));
}
extern crate test;
#[cfg(test)]
mod tests {
use test::Bencher;
use super::*;
#[bench]
fn bench_adt_eval(b: &mut Bencher) {
let example_expr_adt = expr_adt::Plus(Box::new(expr_adt::Times(Box::new(expr_adt::Times(Box::new(expr_adt::Const(2.0)),Box::new(expr_adt::Var("x".to_string())))),Box::new(expr_adt::Var("x".to_string())))),Box::new(expr_adt::Const(4.0)));
let x_evaluator_2_adt = expr_adt::x_evaluator(2.0);
b.iter(|| {
let adt = test::black_box(&example_expr_adt);
x_evaluator_2_adt(adt)
});
}
#[bench]
fn bench_trait_eval(b: &mut Bencher) {
let example_expr_trait = expr_trait::Plus(Box::new(expr_trait::Times(Box::new(expr_trait::Times(Box::new(expr_trait::Const(2.0)),Box::new(expr_trait::Var("x".to_string())))),Box::new(expr_trait::Var("x".to_string())))),Box::new(expr_trait::Const(4.0)));
let x_evaluator_2_trait = expr_trait::x_evaluator(2.0);
b.iter(|| {
let adt = test::black_box(&example_expr_trait);
x_evaluator_2_trait(adt)
});
}
}
[package]
name = "AST_eval"
authors = ["davidad"]
edition = "2018"
version = "0.0.2"
[[bin]]
name = "AST_eval"
path = "AST_eval.rs"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment