{{ message }}

Instantly share code, notes, and snippets.

# ckirkendall/clojure-match.clj

Forked from bkyrlach/Expression.fs
Created Jun 15, 2012
Language Compare F#, Ocaml, Scala, Clojure, Ruby and Haskell - Simple AST example
 (use '[clojure.core.match :only [match]]) (defn evaluate [env [sym x y]] (match [sym] ['Number] x ['Add] (+ (evaluate env x) (evaluate env y)) ['Multiply] (* (evaluate env x) (evaluate env y)) ['Variable] (env x))) (def environment {"a" 3, "b" 4, "c" 5}) (def expression-tree '(Add (Variable "a") (Multiply (Number 2) (Variable "b")))) (def result (evaluate environment expression-tree))
 (defprotocol Expression (evaluate [e env] )) (deftype Number1 [x]) (deftype Add [x y] ) (deftype Multiply [x y]) (deftype Variable [x]) (extend-protocol Expression Number1 (evaluate [e env] (.x e ) ) Add (evaluate [e env] (+ (evaluate (.x e) env) (evaluate (.y e) env))) Multiply (evaluate [e env] (* (evaluate (.x e) env) (evaluate (.y e) env))) Variable (evaluate [e env] (env (.x e)))) (def environment {"a" 3, "b" 4, "c" 5}) (def expression-tree (Add. (Variable. "a") (Multiply. (Number1. 2) (Variable. "b")))) (def result (evaluate expression-tree environment))
 //Here's some F# code... type Expression = | Number of int | Add of Expression * Expression | Multiply of Expression * Expression | Variable of string let rec Evaluate (env:Map) exp = match exp with | Number n -> n | Add (x, y) -> Evaluate env x + Evaluate env y | Multiply (x, y) -> Evaluate env x * Evaluate env y | Variable id -> env.[id] let environment = Map.ofList [ "a", 1 ; "b", 2 ; "c", 3 ] // Create an expression tree that represents // the expression: a + 2 * b. let expressionTree1 = Add(Variable "a", Multiply(Number 2, Variable "b")) // Evaluate the expression a + 2 * b, given the // table of values for the variables. let result = Evaluate environment expressionTree1
 import Data.Map data Expression = Number Int | Add Expression Expression | Multiply Expression Expression | Variable String evaluate :: Map String Int -> Expression -> Int evaluate env exp = case exp of Number x -> x Add x y -> evaluate env x + evaluate env y Multiply x y -> evaluate env x * evaluate env y Variable x -> findWithDefault 0 x env environment = fromList([("a",3), ("b",4), ("c",7)]) expressionTree = Add (Variable "a") (Multiply (Number 2) (Variable "b")) result = evaluate environment expressionTree
 import Data.Map data Expression = Number Int | Add Expression Expression | Multiply Expression Expression | Variable String evaluate :: Map String Int -> Expression -> Int evaluate env (Number x) = x evaluate env (Add x y) = evaluate env x + evaluate env y evaluate env (Multiply x y) = evaluate env x * evaluate env y evaluate env (Variable x) = findWithDefault 0 x env environment = fromList([("a",3), ("b",4), ("c",7)]) expressionTree = Add (Variable "a") (Multiply (Number 2) (Variable "b")) result = evaluate environment expressionTree
 type expression = Number of int | Add of expression * expression | Multiply of expression * expression | Variable of string let rec evaluate (env: string->int) exp = match exp with Number n -> n | Add (x, y) -> evaluate env x + evaluate env y | Multiply (x, y) -> evaluate env x * evaluate env y | Variable id -> env id let environment (str: string) : 'a = match str with "a" -> 3 | "b" -> 4 | "c" -> 5 let expressiontree1 = Add(Variable "a", Multiply(Number 2, Variable "b")) let result = evaluate environment expressiontree1
 def evaluate(env, exp) keyword, a, b = exp case keyword when :number; a when :variable; env[a] when :add; evaluate(env, a) + evaluate(env, b) when :multiply; evaluate(env, a) * evaluate(env, b) end end ExpressionTree = [:add, [:variable, :a], [:multiply, [:number, 2], [:variable, :b]]] Env = { a: 3, b: 4, c: 5 } puts evaluate(Env, ExpressionTree)
 Number = lambda { |env, num| num } Variable = lambda { |env, var| env[var] } Add = lambda { |env, a, b| evaluate(env, a) + evaluate(env, b) } Multiply = lambda { |env, a, b| evaluate(env, a) * evaluate(env, b) } def evaluate(env, exp) op, *args = exp op.(env, *args) end ExpressionTree = [Add, [Variable, :a], [Multiply, [Number, 2], [Variable, :b]]] Env = { a: 3, b: 4, c: 5 } puts evaluate(Env, ExpressionTree)
 abstract class Expression case class Number(i: Int) extends Expression case class Add(x: Expression, y: Expression) extends Expression case class Multiply(x: Expression, y: Expression) extends Expression case class Variable(id: Symbol) extends Expression object Maths extends App { val environment = Map('a -> 1, 'b -> 2, 'c -> 3) def evaluate(env: Map[Symbol, Int], exp: Expression): Int = exp match { case Number(n: Int) => n case Add(x, y) => evaluate(env, x) + evaluate(env, y) case Multiply(x, y) => evaluate(env, x) * evaluate(env, y) case Variable(id: Symbol) => env(id) } val expressionTree1 = Add(Variable('a), Multiply(Number(2), Variable('b))) println(evaluate(environment, expressionTree1)) }
 import java.util.*; public class Eval { static int evaluate(Map env, Expression exp){ if(exp instanceof Variable){ return (Integer)env.get(((Variable)exp).x); } else if(exp instanceof Number){ return ((Number)exp).x; } else if(exp instanceof Multiply){ return evaluate(env, ((Multiply)exp).x)*evaluate(env, ((Multiply)exp).y); } else if(exp instanceof Add){ return evaluate(env, ((Add)exp).x)+evaluate(env, ((Add)exp).y); } return 0; } public static void main(String[] args){ Map env=new HashMap(); env.put("a", 3); env.put("b", 4); env.put("c", 5); Expression expressionTree=new Add(new Variable("a"), new Multiply(new Number(2), new Variable("b"))); System.out.println(evaluate(env, expressionTree)); } } abstract class Expression {} class Number extends Expression{ int x; Number(int x){ this.x=x; } } class Add extends Expression{ Expression x; Expression y; Add(Expression x, Expression y){ this.x=x; this.y=y; } } class Multiply extends Add{ Multiply(Expression x, Expression y){ super(x, y); } } class Variable extends Expression{ String x; Variable(String x){ this.x=x; } }

### z0w0 commented Sep 4, 2012

 In Rust: ```use std; import std::map; enum Expression { Number(int), Add(@Expression, @Expression), Multiply(@Expression, @Expression), Variable(~str) } fn evaluate(env: map::hashmap<~str, int>, exp: Expression) -> int { match exp { Number(num) => num, Add(x, y) => evaluate(env, *x) + evaluate(env, *y), Multiply(x, y) => evaluate(env, *x) * evaluate(env, *y), Variable(id) => env.get(id) } } fn main() { let env = map::hash_from_strs([(~"a", 1), (~"b", 2), (~"c", 3)]); let tree = Add(@Variable(~"a"), @Multiply(@Number(2), @Variable(~"b"))); io::println(#fmt("%d", evaluate(env, tree))); }```

### VictorNicollet commented Sep 4, 2012

 A more idiomatic OCaml version : ``````type expression = Number of int | Add of expression * expression | Multiply of expression * expression | Variable of string let rec evaluate env = function | Number n -> n | Add (x, y) -> evaluate env x + evaluate env y | Multiply (x, y) -> evaluate env x * evaluate env y | Variable id -> env id let environment = function "a" -> 3 | "b" -> 4 | "c" -> 5 let expressiontree1 = Add(Variable "a", Multiply(Number 2, Variable "b")) let result = evaluate environment expressiontree1 `````` OCaml code almost never annotates the types of parameters, and uses the `function` syntax instead of `match` when pattern-matching a function argument.

### VictorNicollet commented Sep 4, 2012

 And a shorter OCaml variant, which uses polymorphic variants : ``````let rec evaluate env = function | `Number n -> n | `Add (x, y) -> evaluate env x + evaluate env y | `Multiply (x, y) -> evaluate env x * evaluate env y | `Variable id -> env id let environment = function "a" -> 3 | "b" -> 4 | "c" -> 5 let expressiontree1 = `Add(`Variable "a", `Multiply(`Number 2, `Variable "b")) let result = evaluate environment expressiontree1 `````` This lets the type inference algorithm check whether the pattern-matched type is correct, instead of having the programmer write down the type specification.

### VictorNicollet commented Sep 4, 2012

 And a third OCaml version, inspired by a comment on the Reddit thread : ``````module Expr = struct let c n = `Number n let ( + ) a b = `Add (a,b) let ( * ) a b = `Multiply (a,b) let v k = `Variable k end let rec evaluate env = function | `Number n -> n | `Add (x, y) -> evaluate env x + evaluate env y | `Multiply (x, y) -> evaluate env x * evaluate env y | `Variable id -> env id let environment k = List.assoc [ "a",3 ; "b",4 ; "c",5 ] let expressiontree1 = Expr.( v "a" + n 2 * v "b") let result = evaluate environment expressiontree1 ``````

### brotchie commented Sep 4, 2012

 Basic Python implementation: ``````class Expression(object): def eval(self, env): raise NotImplementedError('Subclasses must override.') class Number(Expression): def __init__(self, value): self.value = value def eval(self, env): return self.value class Add(Expression): def __init__(self, lhs, rhs): self.lhs = lhs self.rhs = rhs def eval(self, env): return self.lhs.eval(env) + self.rhs.eval(env) class Multiply(Expression): def __init__(self, lhs, rhs): self.lhs = lhs self.rhs = rhs def eval(self, env): return self.lhs.eval(env) * self.rhs.eval(env) class Variable(Expression): def __init__(self, name): self.name = name def eval(self, env): return env.get(self.name, 0) environment = dict(a=3, b=4, c=7) expression_tree = Add(Variable('a'), Multiply(Number(2), Variable('b'))) result = expression_tree.eval(environment)``` ``````

### rtaycher commented Sep 4, 2012

 number, variable, add, multiply = "number", "variable", "add", "multiply" def evaluate(env, exp): if len(exp) == 2: keyword, x = exp elif len(exp) == 3: keyword, x, y = exp else: raise Exception("Invalid expression") eval_map = dict(number=lambda: x, variable=lambda: env[x], add=lambda: evaluate(env, x) + evaluate(env, y), multiply=lambda: evaluate(env, x) * evaluate(env, y)) return eval_mapkeyword expression_tree = [add, [variable, "a"], [multiply, [number, 2], [variable, "b"]]] env = { "a": 3, "b": 4, "c": 5 } print evaluate(env, expression_tree)

### brotchie commented Sep 4, 2012

 Another Python approach ``````from collections import namedtuple as nt Number = nt('Number' , 'value') Add = nt('Add' , 'lhs rhs') Multiply = nt('Multiply', 'lhs rhs') Variable = nt('Variable', 'name') def eval(expr, env): return HANDLERS[expr.__class__](env, expr) HANDLERS = { Number : lambda env, e: e.value, Add : lambda env, e: eval(e.lhs, env) + eval(e.rhs, env), Multiply : lambda env, e: eval(e.lhs, env) * eval(e.rhs, env), Variable : lambda env, e: env.get(e.name, 0) } environment = dict(a=3, b=4, c=7) expression_tree = Add(Variable('a'), Multiply(Number(2), Variable('b'))) result = eval(expression_tree, environment) ``````

### Canop commented Sep 4, 2012

 In Go package main import ( "fmt" ) var env = make(map[string]int) type Expression interface { Eval() int } type Variable string func (e Variable) Eval() int { return env[string(e)] } type Number int func (n Number) Eval() int { return int(n) } type Add struct { a Expression b Expression } func (e Add) Eval() int { return e.a.Eval()+e.b.Eval() } type Multiply struct { a Expression b Expression } func (e Multiply) Eval() int { return e.a.Eval()*e.b.Eval() } func main() { env["a"]=3 env["b"]=4 env["c"]=5 ast := Add{Variable("a"), Multiply{Number(2), Variable("b")}} fmt.Println(ast.Eval()) }

### sviperll commented Sep 4, 2012

 Another Java version ``````interface ExpressionVisitor { R number(int value); R variable(String name); R multiply(E x, E y); R add(E x, E y); } interface Expression { R accept(ExpressionVisitor visitor); } class Number implements Expression { private final int value; public Number(int value) { this.value = value; } @Override public R accept(ExpressionVisitor visitor) { return visitor.number(value); } } class Variable implements Expression { private final String name; public Variable(int name) { this.name = name; } @Override public R accept(ExpressionVisitor visitor) { return visitor.variable(name); } } class Multiply implements Expression { private final Expression x; private final Expression y; public Multiply(Expression x, Expression y) { this.x = x; this.y = y; } @Override public R accept(ExpressionVisitor visitor) { return visitor.multiply(x, y); } } class Add implements Expression { private final Expression x; private final Expression y; public Add(Expression x, Expression y) { this.x = x; this.y = y; } @Override public R accept(ExpressionVisitor visitor) { return visitor.add(x, y); } } class EvaluatorVisitor implements ExpressionVisitor { private final Map environment; public EvaluatorVisitor(Map environment) { this.environment = environment; } @Override public Integer number(int value) { return value; } @Override public Integer variable(String name) { return environment.get(name); } @Override public Integer multiply(Expression x, Expression y) { return x.accept(this) * y.accept(this); } @Override public Integer add(Expression x, Expression y) { return x.accept(this) + y.accept(this); } } class Main { public static int evaluate(Map environment, Expression expression) { return expression.accept(new EvaluatorVisitor(environment)); } public static void main(String[] args) { Map environment = new TreeMap<>(); environment.put("a", 3); environment.put("b", 4); environment.put("c", 5); Expression expression = new Add(new Variable("a"), new Multiply(new Number(2), new Variable("b"))); System.out.println(evaluate(env, expressionTree)); } } ``````

### masak commented Sep 4, 2012

 A Perl 6 version: ``````multi ev(['number', \$n]) { \$n } multi ev(['add', \$x, \$y]) { ev(\$x) + ev(\$y) } multi ev(['multiply', \$x, \$y]) { ev(\$x) * ev(\$y) } multi ev(['variable', \$name]) { %*env{\$name} } my %*env = a => 3, b => 4, c => 5; my \$tree = ['add', ['variable', 'a'], ['multiply', ['number', 2], ['variable', 'b']]]; say ev(\$tree); `````` Could pass the environment along with every call, like most other solutions, but it seemed more p6-ish to just define it as a contextual variable.

### martinus commented Sep 4, 2012

 my C++ version: ``````#include #include #include class Cmd { public: virtual int eval() const = 0; }; class CmdNumber : public Cmd { public: CmdNumber(int val) : _val(val) { } virtual int eval() const { return _val; } private: int _val; }; class CmdVariable : public Cmd { public: CmdVariable(const char* var, const std::map& variable_map) : _var(var), _variable_map(variable_map) { } virtual int eval() const { return _variable_map.find(_var)->second; } private: const std::string _var; const std::map& _variable_map; }; class CmdAdd : public Cmd { public: CmdAdd(const Cmd* a, const Cmd* b) : _a(a), _b(b) { } ~CmdAdd() { delete _a; delete _b; } virtual int eval() const { return _a->eval() + _b->eval(); } private: const Cmd* _a; const Cmd* _b; }; class CmdMultiply : public Cmd { public: CmdMultiply(const Cmd* a, const Cmd* b) : _a(a), _b(b) { } ~CmdMultiply() { delete _a; delete _b; } virtual int eval() const { return _a->eval() * _b->eval(); } private: const Cmd* _a; const Cmd* _b; }; int main(int argc, char** argv) { std::map vm; const Cmd* tree = new CmdAdd(new CmdVariable("a", vm), new CmdMultiply(new CmdNumber(2), new CmdVariable("b", vm))); vm["a"] = 3; vm["b"] = 4; vm["c"] = 5; std::cout << tree->eval() << std::endl; // cleanup delete tree; } `````` Also, the ruby version did not run. I had to change it into this: ``````def evaluate(env, exp) keyword, a, b = exp case keyword when :number; a when :variable; env[a] when :add; evaluate(env, a) + evaluate(env, b) when :multiply; evaluate(env, a) * evaluate(env, b) end end ExpressionTree = [:add, [:variable, :a], [:multiply, [:number, 2], [:variable, :b]]] Env = { :a => 3, :b => 4, :c => 5 } puts evaluate(Env, ExpressionTree) ``````

### frabbit commented Sep 4, 2012

 In Haxe: ```enum Expression { Number(x:Int); Add(e1:Expression, e2:Expression); Multiply(e1:Expression, e2:Expression); Variable (x:String); } class Main { static function evaluate (env:Hash, e:Expression) return switch (e) { case Number(x): x; case Add(x,y): evaluate(env, x) + evaluate(env, y); case Multiply(x,y): evaluate(env, x) * evaluate(env, y); case Variable(x): if (env.exists(x)) env.get(x) else 0; } static function main () { var environment = new Hash(); environment.set("a", 3); environment.set("b", 4); environment.set("c", 7); var expressionTree = Add(Variable("a"), Multiply(Number(2),Variable("b"))); var result = evaluate(environment, expressionTree); } } ```

### prophile commented Sep 4, 2012

 Minimal python implementation: ``````Number = lambda env, n: n Add = lambda env, a, b: evaluate(env, a) + evaluate(env, b) Multiply = lambda env, a, b: evaluate(env, a) * evaluate(env, b) Variable = lambda env, x: env[x] evaluate = lambda env, expr: expr[0](env, *expr[1:]) expression_tree = (Add, (Variable, 'a'), (Multiply, (Number, 2), (Variable, 'b'))) environment = {'a': 3, 'b': 4, 'c': 5} print evaluate(environment, expression_tree) ``````

### slvmnd commented Sep 4, 2012

 Go OO-version: ```package main import "fmt" type Env map[string]int type Exp interface {Eval(Env) int} type Var string func (v Var) Eval(e Env) int {return e[string(v)]} type Num int func (n Num) Eval(e Env) int {return int(n)} type Add struct {a, b Exp} func (ex Add) Eval(e Env) int {return ex.a.Eval(e) + ex.b.Eval(e)} type Mul struct {a, b Exp} func (ex Mul) Eval(e Env) int {return ex.a.Eval(e) * ex.b.Eval(e)} func main() { ast := Add{Var("a"), Mul{Num(2), Var("b")}} fmt.Println(ast.Eval(Env{"a":3, "b":4, "c":5})) }``` Go type matching version: ```package main import "fmt" type Add struct{a, b interface{}} type Mul struct{a, b interface{}} func eval(env map[string]int, e interface{}) int { switch v := e.(type) { case int: return v case string: return env[v] case Add: return eval(env, v.a) + eval(env, v.b) case Mul: return eval(env, v.a) * eval(env, v.b) } return 0 } func main() { env := map[string]int{"a":3, "b":4, "c":5} ast := Add{"a", Mul{2, "b"}} fmt.Println(eval(env, ast)) }```

### dslmeinte commented Sep 4, 2012

 In Xtend: ```import java.util.Map import org.eclipse.xtext.xbase.lib.Pair class Eval { def static void main(String...args) { new Eval().run() } // run inside an instance instead of statically so we can operator overloading (and use extensions) def evaluate(Map env, Expression exp) { switch exp { Variable: (env.get(exp.name) as Integer).intValue Number: exp.value Multiply: evaluate(env, exp.x) * evaluate(env, exp.y) Add: evaluate(env, exp.x) + evaluate(env, exp.y) } } def operator_doubleArrow(String key, Integer value) { new Pair(key, value) } // for convenient map construction // for convenient AST construction: def \$(String varName) { new Variable(varName) } def \$(int value) { new Number(value) } def operator_plus(Expression left, Expression right) { new Add(left, right) } def operator_multiply(Expression left, Expression right) { new Multiply(left, right) } def run() { val env = newHashMap("a" => 3, "b" => 4, "c" => 5) val expressionTree = \$('a') + \$(2) * \$('b') println(evaluate(env, expressionTree)) } } abstract class Expression {} @Data class Number extends Expression { @Property int value } @Data class Add extends Expression { @Property Expression x @Property Expression y } @Data class Multiply extends Add {} @Data class Variable extends Expression { @Property String name } ```

### svenefftinge commented Sep 4, 2012

 Another Xtend version: ``````import java.util.Map class Eval { def static void main(String...args) { new Eval().run } def run() { newHashMap('a' -> 3, 'b' -> 4) => [ if ( 3 + 2 * 4 != evaluate('a' + 2 * 'b') ) throw new Exception println("success!") ] } def int evaluate(Map it, Object exp) { switch exp { String: get(exp) Integer: exp Op case exp.operator == '+': evaluate(exp.left) + evaluate(exp.right) Op case exp.operator == '*': evaluate(exp.left) * evaluate(exp.right) } } // overload + and * for convenient AST construction: def operator_plus(String left, Object right) { new Op('+', left ,right) } def operator_plus(int left, Object right) { new Op('+', left ,right) } def operator_plus(Object left, Object right) { new Op('+', left ,right) } def operator_multiply(String left, Object right) { new Op('*', left ,right) } def operator_multiply(int left, Object right) { new Op('*', left ,right) } def operator_multiply(Object left, Object right) { new Op('*', left ,right) } } @Data class Op { String operator Object left Object right } ``````

### regularfry commented Sep 4, 2012

 Simple conversion of the original into Common Lisp: ```(setq *environment* '(("a" . 3) ("b" . 4) ("c" . 5))) (setq *expression-tree* '(add (variable "a") (multiply (number 2) (variable "b")))) (defun evaluate (env tree) (let ((sym (car tree)) (x (cadr tree)) (y (caddr tree))) (case sym ('number x) ('add (+ (evaluate env x) (evaluate env y))) ('multiply (* (evaluate env x) (evaluate env y))) ('variable (cdr (assoc x *environment* :test 'string=)))))) (setq result (evaluate *environment* *expression-tree*))``` Suffers slightly from not having a simple destructuring bind, and could probably be macro'd shorter if anyone wants a try.

### julianstorer commented Sep 4, 2012

 Gah.. Was the poster of the C++ example above deliberately trying to make the language look bad!? I feel compelled to try to defend its reputation: ```#include #include #include #include typedef std::map Variables; struct Expr { virtual ~Expr() {} virtual int eval (Variables&) = 0; }; struct Multiply : public Expr { std::unique_ptr e1, e2; Multiply (Expr* lhs, Expr* rhs) : e1 (lhs), e2 (rhs) {} int eval (Variables& env) { return e1->eval (env) * e2->eval (env); } }; struct Add : public Expr { std::unique_ptr e1, e2; Add (Expr* lhs, Expr* rhs) : e1 (lhs), e2 (rhs) {} int eval (Variables& env) { return e1->eval (env) + e2->eval (env); } }; struct Constant : public Expr { int value; Constant (int val) : value (val) {} int eval (Variables&) { return value; } }; struct Variable : public Expr { std::string varName; Variable (const std::string& name) : varName (name) {} int eval (Variables& env) { return env [varName]; } }; int main (int argc, char** argv) { Variables env; env["a"] = 3; env["b"] = 4; env["c"] = 5; Add tree (new Variable ("a"), new Multiply (new Constant (2), new Variable ("b"))); std::cout << tree.eval (env) << std::endl; }```

### ionoy commented Sep 4, 2012

 Nemerle version: ```#pragma indent using Nemerle.Extensions; using System.Collections.Generic; variant Ast | Number { val : int } | Add { left : Ast; right : Ast } | Multiply { left : Ast; right : Ast } | Variable { name : string } def eval(env, expr) match(expr) | Ast.Number(val) => val | Add(l, r) => eval(env, l) + eval(env, r) | Multiply(l, r) => eval(env, l) * eval(env, r) | Variable(name) => env[name] def environment = Dictionary() <- ["a" = 3, "b" = 4, "c" = 5]; def expr = Ast.Add(Ast.Variable("a"), Ast.Multiply(Ast.Number(2), Ast.Variable("b"))); def result = eval(environment, expr);```

### msx80 commented Sep 4, 2012

 Java8 ``````import java.util.*; import java.util.functions.*; import java.io.*; public class Test { interface Expr { int eval(Map env); } public Expr add(Expr a, Expr b) { return env -> ( a.eval(env) + b.eval(env) ); } public Expr mul(Expr a, Expr b) { return env -> ( a.eval(env) * b.eval(env) ); } public Expr num(int i) { return env -> ( i ); } public Expr var(String name) { return env -> ( env.get(name)).intValue(); } public Test() { Map env = new HashMap(){{ put("a", 3); put("b", 4); put("b", 5); // still no literal :( }}; Expr e = add(var("a"), mul(num(2),var("b"))); System.out.println(e.eval(env)); } public static void main(final String [] args) { new Test(); } } ``````

### brotchie commented Sep 4, 2012

 How about a compile time implementation with boost::mpl? It fails to compile if the asked for variable doesn't exist in the environment, my version of boost doesn't have the three argument boost::mpl::at implemented. ``````#include #include #include #include #include #include #include #include using namespace boost::mpl; template struct Add {}; template struct Multiply {}; template struct Number {}; template struct Variable {}; template struct evaluate {}; template struct evaluate, env> { typedef typename plus< typename evaluate::type , typename evaluate::type >::type type; }; template struct evaluate, env> { typedef typename times< typename evaluate::type , typename evaluate::type >::type type; }; template struct evaluate, env> { typedef int_ type; }; template struct evaluate, env> { typedef typename at::type type; }; struct a {}; struct b {}; struct c {}; typedef map< pair > , pair > , pair > > environment; typedef Add, Multiply, Variable > > expression_tree; typedef evaluate::type result; int main() { std::cout << result::value << std::endl; return 0; } ``````

### dobson156 commented Sep 4, 2012

 WOW, why are these C++ solutions so bad: ``````#include #include using data=std::unordered_map; template struct val { double operator() (const data&) const { return D; } }; template struct mis { double operator()(const data& v) const { return v.at(I); } }; template struct add { double operator()(const data& v) const { return Expr1()(v)+Expr2()(v); } }; template struct mul { double operator()(const data& v) const { return Expr1()(v)*Expr2()(v); } }; int main() { add< mis<'a'>, mul< val<2>, mis<'b'> > > expression; double a=1, b=2; //or whatever std::cout << expression({ { 'a', a }, { 'b', b } }) << '\n'; return 0; } ``````

### NicolasT commented Sep 4, 2012

 A more elaborate Haskell version, removing some type restrictions (using GADTs). Note this contains some more types of Expression, and more demonstrations. It uses Monoid to handle lookup failures, similar to the original version, although I'd use some kind of error handling (Either?) myself. ```{-# LANGUAGE GeneralizedNewtypeDeriving, GADTs #-} import Prelude hiding (lookup) import qualified Prelude as P import Data.Maybe (fromMaybe) import Data.Monoid (Monoid, mempty, mappend) data Expression a where Constant :: a -> Expression a Add :: Num a => Expression a -> Expression a -> Expression a Multiply :: Num a => Expression a -> Expression a -> Expression a Append :: Monoid a => Expression a -> Expression a -> Expression a Variable :: Monoid a => String -> Expression a evaluate :: (String -> Maybe a) -> Expression a -> a evaluate _ (Constant a) = a evaluate lookup (Add a b) = evaluate lookup a + evaluate lookup b evaluate lookup (Multiply a b) = evaluate lookup a * evaluate lookup b evaluate lookup (Append a b) = evaluate lookup a `mappend` evaluate lookup b evaluate lookup (Variable name) = fromMaybe mempty (lookup name) result1 :: (Num a, Monoid a) => a result1 = evaluate lookup tree where lookup = flip P.lookup bindings bindings = [("a", 3), ("b", 4), ("c", 7)] tree = Add (Add (Variable "a") (Multiply (Constant 2) (Variable "b"))) (Variable "nada") -- This makes use of the Monoid instance of [] for Variable and Append result2 :: String result2 = evaluate lookup tree where lookup = flip P.lookup bindings bindings = [("name", "ast")] tree = Append (Append (Variable "name") (Constant " ")) (Constant "test") -- For result1, we need a type with Num and Monoid instances due to the -- usage of Add, Multiply and Variable newtype MyInt = MyInt Int deriving (Show, Eq, Num) -- Custom Monoid instance, similar to Sum instance Monoid MyInt where mempty = MyInt 0 mappend (MyInt a) (MyInt b) = MyInt \$ a + b data MyType = MyType deriving (Show) -- This example shows, despite using Expression and evaluate, we don't need -- Monoid or Num instances, since all we use is Constant result3 :: MyType result3 = evaluate (const Nothing) (Constant MyType) main :: IO () main = do putStrLn \$ "result1 = " ++ show (result1 :: MyInt) putStrLn \$ "result2 = " ++ result2 putStrLn \$ "result3 = " ++ show result3 {- - Output: - - result1 = MyInt 11 - result2 = ast test - result3 = MyType -}```

### onektwenty4 commented Sep 4, 2012

 %in prolog ```eval(number(X), X). eval(add(X,Y), Val) :- eval(X, Xval), eval(Y, Yval), Val is Xval+Yval. eval(multiply(X,Y), Val) :- eval(X, Xval), eval(Y, Yval), Val is Xval*Yval. eval(variable(V), Val) :- env(V, Val). env(a, 3). env(b, 4). env(c, 5). test_expression( add(variable(a), multiply(number(2), variable(b))) ). result(ValueOut) :- test_expression(Expr), eval(Expr, ValueOut).```

### pmarreck commented Sep 4, 2012

 Ruby variant which is fairly concise: ``````def Number(num) ->(env){ num } end def Variable(var) ->(env){ env[var] } end def Add(f1, f2) ->(env){ f1.(env)+f2.(env) } end def Multiply(f1, f2) ->(env){ f1.(env)*f2.(env) } end ExpressionTree = Add(Variable(:a), Multiply(Number(2), Variable(:b))) Env = { a: 3, b: 4, c: 5 } p ExpressionTree.(Env) ``````

### pmarreck commented Sep 4, 2012

 Also a Python version: ``````__init__ self self.__init__ eval self self.__init__ __init__ self `````` /jab

### ordovician commented Sep 4, 2012

 In the Nu programming language (LISP/Ruby on top of Objective-C): ```(load "Nu:match") (function evaluate (env exp) (match exp (('Number x ) x) (('Add x y) (+ (evaluate env x) (evaluate env y))) (('Multiply x y) (* (evaluate env x) (evaluate env y))) (('Variable x ) (env x)))) (set environment (dict "a" 3 "b" 4 "c" 5)) (set expression-tree '(Add (Variable "a") (Multiply (Number 2) (Variable "b")))) (set result (evaluate environment expression-tree))```

### beders commented Sep 4, 2012

 Terrible Java code above. Use inheritance, but then butcher it in the evaluate method. ``````import java.util.*; public class Eval { Map env; public Eval() { env = new HashMap(); env.put("a", 3); env.put("b", 4); env.put("c", 5); Expression expressionTree = new Add(new Variable("a"), new Multiply(new Number(2), new Variable("b"))); System.out.println(expressionTree.eval()); } public static void main(String[] args) { new Eval(); } abstract class Expression { abstract int eval(); } class Number extends Expression { int x; Number(int x) { this.x = x; } @Override int eval() { return x; } } class Add extends Expression { Expression x,y; Add(Expression x, Expression y) { this.x = x; this.y = y; } @Override int eval() { return x.eval() + y.eval(); } } class Multiply extends Add { Multiply(Expression x, Expression y) { super(x, y); } @Override int eval() { return x.eval() * y.eval(); } } class Variable extends Expression { String x; Variable(String x) { this.x = x; } @Override int eval() { return env.get(x); } } } ``````

### dslmeinte commented Sep 4, 2012

 A mixed Xtend/Java version: Java: ```public interface Expr { int eval(Map env); } ``` Xtend: ```class Eval { def static void main(String...args) { new Eval().run() } // run inside an instance instead of statically so we can operator overloading (and use extensions) // for convenient AST construction: def Expr \$(String varName) { [ get(varName) ] } def Expr \$(int value) { [ value ] } def Expr operator_plus(Expr left, Expr right) { [ left.eval(it) + right.eval(it) ] } def Expr operator_multiply(Expr left, Expr right) { [ left.eval(it) * right.eval(it) ] } def run() { println( ( \$('a') + \$(2) * \$('b') ).eval( newHashMap("a" -> 3, "b" -> 4, "c" -> 5) ) ) } } ``` The mixing is required because Xtend doesn't do interfaces (inner or no). This version is inspired by the Java8 example but also philosophically quite close to the Haskell-/FP-type solutions.

### q66 commented Sep 4, 2012

 Lua: ```local gm, sm = getmetatable, setmetatable local new_exprt = function() return sm({}, { __call = function(et, ...) return sm({ ... }, et) end }) end local Num, Add, Mul, Var = new_exprt(), new_exprt(), new_exprt(), new_exprt() local eval eval = function(env, exp) if gm(exp) == Num then return exp[1] elseif gm(exp) == Add then return eval(env, exp[1]) + eval(env, exp[2]) elseif gm(exp) == Mul then return eval(env, exp[1]) * eval(env, exp[2]) elseif gm(exp) == Var then return env[exp[1]] end end local env = { a = 1, b = 2, c = 3 } local expr_tree = Add(Var("a"), Mul(Num(2), Var("b"))) print(eval(env, expr_tree))```

### demodude4u commented Sep 4, 2012

 How about some smaller java code: ```import java.util.HashMap; import java.util.Map; public abstract class Eval

{ abstract int get(P... params); static Eval ADD = new Eval() { @Override public int get(Integer... params) { return params[0] + params[1]; }; }; static Eval MULTIPLY = new Eval() { @Override public int get(Integer... params) { return params[0] * params[1]; } }; static Map variables = new HashMap(); static Eval VARIABLE = new Eval() { @Override public int get(String... params) { return variables.get(params[0]); }; }; public static void main(String[] args) { variables.put("a", 3); variables.put("b", 4); variables.put("c", 5); int result = ADD.get(VARIABLE.get("a"), MULTIPLY.get(2, VARIABLE.get("b"))); System.out.println("Result: " + result); } }```

### DanBurton commented Sep 4, 2012

 Racket: (I took some artistic license with how the "ast" is expressed) ```#lang racket (define (evaluate env exp) (match exp [(? number? x) x ] [`(+ ,x ,y) (+ (evaluate env x) (evaluate env y))] [`(* ,x ,y) (* (evaluate env x) (evaluate env y))] [(? symbol? v) (hash-ref env v) ])) (define environment (hash 'a 3 'b 4 'c 5)) (define expression-tree '(+ a (* 2 b))) (define result (evaluate environment expression-tree))```

### DanBurton commented Sep 4, 2012

 Racket, using structs instead of s-expressions ```#lang racket (struct num (val)) (struct add (l r)) (struct mul (l r)) (struct id (sym)) (define (evaluate env exp) (match exp [(num x) x ] [(add x y) (+ (evaluate env x) (evaluate env y))] [(mul x y) (* (evaluate env x) (evaluate env y))] [(id v) (hash-ref env v) ])) (define environment (hash 'a 3 'b 4 'c 5)) (define expression-tree (add (id 'a) (mul (num 2) (id 'b)))) (define result (evaluate environment expression-tree))```

### DanBurton commented Sep 4, 2012

 And finally, Typed Racket using structs ```#lang typed/racket (struct: num ([val : Number])) (struct: add ([l : AST] [r : AST])) (struct: mul ([l : AST] [r : AST])) (struct: id ([sym : Symbol])) (define-type AST (U num add mul id)) (define-type Env (HashTable Symbol Number)) (: evaluate (Env AST -> Number)) (define (evaluate env exp) (match exp [(num x) x ] [(add x y) (+ (evaluate env x) (evaluate env y))] [(mul x y) (* (evaluate env x) (evaluate env y))] [(id v) (hash-ref env v) ])) (: environment Env) (define environment (make-hash '((a . 3) (b . 4) (c . 5)))) (: expression-tree AST) (define expression-tree (add (id 'a) (mul (num 2) (id 'b)))) (: result Number) (define result (evaluate environment expression-tree))```

### pmarreck commented Sep 4, 2012

 Added a divide object and made add/multiply take variable numbers of args. ``````def Number(num) ->(env){ num } end def Variable(var) ->(env){ env[var] } end def Add(*args) ->(env){ (n=args.pop) ? n.(env)+Add(*args).(env) : Number(0).(env) } end def Multiply(*args) ->(env){ (n=args.pop) ? n.(env)*Multiply(*args).(env) : Number(1).(env) } end def Divide(num,dem) ->(env){ num.(env) / dem.(env) } end ExpressionTree = Add(Variable(:a), Variable(:c), Multiply(Number(2), Variable(:b), Number(6), Divide(Number(4), Variable(:d)))) Env = { a: 3, b: 4, c: 5, d: 2 } p ExpressionTree.(Env) ``````

### channingwalton commented Sep 4, 2012

 and brainfuck?

### TristanAllwood commented Sep 4, 2012

 Tagless, Monadic, Inferred Haskell. ``````import Data.Map import Control.Monad number = return add = liftM2 (+) multiply = liftM2 (*) variable = findWithDefault 0 environment = fromList [("a",3), ("b",4), ("c",7)] expressionTree = add (variable "a") (multiply (number 2) (variable "b")) main = print \$ expressionTree environment ``````

### oscarryz commented Sep 4, 2012

 `````` import "fmt" type env map[string]int type expr func(e env) int func number(i int) expr { return func(e env) int { return i } } func variable(s string) expr { return func(e env) int { return e[s] } } func add(i, j expr) expr { return func(e env) int { return i(e) + j(e) } } func multiply(i, j expr) expr { return func(e env) int { return i(e) \* j(e) } } func main() { e := env{"a": 3, "b": 4, "c": 5} tree := add(variable("a"), multiply(number(2), variable("b"))) fmt.Println(tree(e)) } ``````

### mikeivanov commented Sep 4, 2012

 Emacs Lisp: ``````;; -*- lexical-binding: t; -*- (defun Add (x y) (lambda (env) (+ (funcall x env) (funcall y env)))) (defun Mul (x y) (lambda (env) (* (funcall x env) (funcall y env)))) (defun Var (x) (lambda (env) (cdr (assoc x env)))) (defun Num (x) (lambda (env) x)) (defvar ast (Add (Var "a") (Mul (Num 2) (Var "b")))) (defvar env '(("a" . 3) ("b" . 4) ("c" . 5))) (message (format "result=%s" (funcall ast env))) ``````

### sebbu2 commented Sep 4, 2012

 I had to replace using data=std::unordered_map; by typedef std::unordered_map data; in https://gist.github.com/2934374#gistcomment-531711 to get it to compile in g++ 4.6.2

### darkf commented Sep 5, 2012

 Erlang: ```-module(ast). -export([start/0]). eval({number, N}, _) -> N; eval({add, L, R}, Env) -> eval(L, Env) + eval(R, Env); eval({mul, L, R}, Env) -> eval(L, Env) * eval(R, Env); eval({variable, Id}, Env) -> dict:fetch(Id, Env). start() -> Env = dict:from_list([{a, 1}, {b, 2}, {c, 3}]), Tree = {add, {variable, a}, {mul, {number, 2}, {variable, b}}}, Result = eval(Tree, Env), io:format("result: ~p~n", [Result]).```

### ixid commented Sep 5, 2012

 A version in the D language: [code] module main; import std.stdio; alias int[string] env; alias int delegate(env) expr; auto number = (int i) => (env x) => i; auto variable = (string s) => (env x) => x[s]; auto add = (expr i, expr j) => (env x) => i(x) + j(x); auto multiply = (expr i, expr j) => (env x) => i(x) * j(x); void main() { auto e = ["a": 3, "b": 4, "c": 5]; auto tree = number(2).multiply("b".variable).add("a".variable); tree(e).writeln; } [/code]

### gvx commented Sep 5, 2012

 Since we're all joining in: a version in my own stack-based toy language, Déjà Vu: ``````Number: & :num Add: & :add & Multiply: & :mul & Variable: & :var num: drop add e t: + eval e &< t eval e &> t mul e t: * eval e &< t eval e &> t var: get-from eval env tree: call &< tree env &> tree print eval { :a 3 :b 4 :c 7 } Add Variable :a Multiply Number 2 Variable :b ``````

### DeadMG commented Sep 5, 2012

 Damn, you guys are C++ scrubs. Let the master show you how it's done. ``````#include #include #include using namespace std; int main() { map vars = { { "a" , 3 }, { "b", 4 }, { "c", 5 } }; auto tree = bind(plus(), ref(variables["a"]), bind(multiplies(), 2, ref(variables["b"]))); cout << tree(); } ``````

### DeadMG commented Sep 5, 2012

 Of course, I renamed the map from the sample I was originally shown, then didn't update the variables, making me look like a complete nubcake. And I didn't `#include ` either. Oh well. Close enough.

### davidlazar commented Sep 5, 2012

 ``````module EXP is syntax Exp ::= Exp "+" Exp [strict] | Exp "*" Exp [strict] | Int | Id syntax KResult ::= Int configuration \$PGM:K \$ENV:Map rule I1:Int + I2:Int => I1 +Int I2 rule I1:Int * I2:Int => I1 *Int I2 rule X:Id => I ... ... X |-> I:Int ... end module `````` Run it: ``````\$ cat pgm.exp a + (2 * b) \$ krun --ENV="a |-> 3 b |-> 4" pgm.exp 11 a |-> 3 b |-> 4 ``````

### ordovician commented Sep 5, 2012

 Objective-C version using blocks (closures): ```#import typedef int (^Expression)(NSDictionary *env); Expression number(int x) { return ^(NSDictionary *env) { return x;}; } Expression add(Expression x, Expression y) { return ^(NSDictionary *env) { return x(env) + y(env);}; } Expression multiply(Expression x, Expression y) { return ^(NSDictionary *env) { return x(env) * y(env);}; } Expression variable(NSString *x) { return ^(NSDictionary *env) { return [[env objectForKey:x] intValue];}; } int main(int argc, const char * argv[]) { @autoreleasepool { NSDictionary *environment = @{@"a" : @3, @"b" : @4, @"c" : @5}; Expression expressionTree = add(variable(@"a"), multiply(number(2), variable(@"b"))); NSLog(@"%d", expressionTree(environment)); } return 0; }```

### ordovician commented Sep 5, 2012

 More idiomatic Objective-C, using umbrella class instead of blocks: ```#import @interface Expression : NSObject + (Expression *)number:(int)x; + (Expression *)add:(Expression *)x to:(Expression *)y; + (Expression *)multiply:(Expression *)x with:(Expression *)y; + (Expression *)variable:(NSString *)x; - (int)eval:(NSDictionary *)env; @end @interface Number : Expression @property int x; @end @interface Add : Expression @property Expression *x; @property Expression *y; @end @interface Multiply : Expression @property Expression *x; @property Expression *y; @end @interface Variable : Expression @property NSString *x; @end @implementation Expression + (Expression *)number:(int)x { Number *obj = [Number new]; obj.x = x; return obj; } + (Expression *)add:(Expression *)x to:(Expression *)y { Add *obj = [Add new]; obj.x = x; obj.y = y; return obj; } + (Expression *)multiply:(Expression *)x with:(Expression *)y { Multiply *obj = [Multiply new]; obj.x = x; obj.y = y; return obj; } + (Expression *)variable:(NSString *)x { Variable *obj = [Variable new]; obj.x = x; return obj; } - (int)eval:(NSDictionary *)env { NSAssert(NO, @"Abstract class", nil); return -1; } @end @implementation Number - (int)eval:(NSDictionary *)env { return self.x; } @end @implementation Add - (int)eval:(NSDictionary *)env { return [_x eval:env] + [_y eval:env]; } @end @implementation Multiply - (int)eval:(NSDictionary *)env { return [_x eval:env] * [_y eval:env]; } @end @implementation Variable - (int)eval:(NSDictionary *)env { return [[env objectForKey:_x] intValue]; } @end int main(int argc, const char * argv[]) { @autoreleasepool { NSDictionary *environment = @{@"a" : @3, @"b" : @4, @"c" : @5}; Expression *expressionTree = [Expression add:[Expression variable:@"a"] to:[Expression multiply:[Expression number:2] with: [Expression variable:@"b"]]]; NSLog(@"%d", [expressionTree eval:environment]); } return 0; }```

### sirarthurnell commented Sep 6, 2012

 In Visual Basic ``````MustInherit Class Expression Public MustOverride Function Evaluate() As Integer End Class Class Number Inherits Expression Public Sub New(ByVal value As Integer) _value = value End Sub Private ReadOnly _value As Integer Public Overrides Function Evaluate() As Integer Return _value End Function End Class Class Variable Inherits Expression Private ReadOnly _environment As Dictionary(Of String, Integer) Private ReadOnly _name As String Public Sub New(ByVal name As String, ByVal environment As Dictionary(Of String, Integer)) _name = name _environment = environment End Sub Public Overrides Function Evaluate() As Integer Return _environment(_name) End Function End Class Class Add Inherits Expression Private ReadOnly _leftExpression As Expression Private ReadOnly _rightExpression As Expression Public Sub New(ByVal leftExpression As Expression, ByVal rightExpression As Expression) _leftExpression = leftExpression _rightExpression = rightExpression End Sub Public Overrides Function Evaluate() As Integer Return _leftExpression.Evaluate() + _rightExpression.Evaluate() End Function End Class Class Multiply Inherits Expression Private ReadOnly _leftExpression As Expression Private ReadOnly _rightExpression As Expression Public Sub New(ByVal leftExpression As Expression, ByVal rightExpression As Expression) _leftExpression = leftExpression _rightExpression = rightExpression End Sub Public Overrides Function Evaluate() As Integer Return _leftExpression.Evaluate() * _rightExpression.Evaluate() End Function End Class Module ExpressionsTest Sub Main() Dim environment = New Dictionary(Of String, Integer) From {{"a", 1}, {"b", 2}, {"c", 3}} '(a + b) * 5 Dim varA As New Variable("a", environment) Dim varB As New Variable("b", environment) Dim add As New Add(varA, varB) Dim number5 As New Number(5) Dim multiply As New Multiply(add, number5) Dim result As Integer = multiply.Evaluate() End Sub End Module ``````

### martinus commented Sep 6, 2012

 @julianstorer, so you have just removed a few newlines and use unique_ptr. I'd say the code still is awful, it is conceptionally exactly the same. Also you are not const correct any more.

### zuoyan commented Dec 10, 2012

 In C++11, with std::function to do the type erasure ``` # include # include # include # include typedef std::map env_t; typedef std::function expr_t; template struct multiply { A a; B b; multiply(A a, B b) : a(a), b(b) {} double operator()(env_t & env) const { return a(env) * b(env); } }; template struct add { A a; B b; add(A a, B b) : a(a), b(b) {} double operator()(env_t & env) const { return a(env) + b(env); } }; struct var { std::string name; var(const std::string &n) : name(n) {} double operator()(env_t & env) const { return env[name]; } }; struct val { double v; val(double v_) : v(v_) {} double operator()(env_t & env) const { return v; } }; template add make_add(const A &a, const B &b) { return add(a, b); } template multiply make_multiply(const A &a, const B &b) { return multiply(a, b); } int main(int argc, char *argv[]) { env_t env; env["a"] = 3; env["b"] = 4; env["c"] = 5; auto expr = make_add(var("a"), make_multiply(val(2), var("b"))); // or expr_t expr = ... ``````std::cout << expr(env) << std::endl; return 0; } ```

### zuoyan commented Dec 10, 2012

 I'm sorry for prev comment, it's not formated. C++11 with std::function to do type erasure. ``````#include #include #include #include typedef std::map env_t; typedef std::function expr_t; template struct multiply { A a; B b; multiply(A a, B b) : a(a), b(b) {} double operator()(env_t & env) const { return a(env) * b(env); } }; template struct add { A a; B b; add(A a, B b) : a(a), b(b) {} double operator()(env_t & env) const { return a(env) + b(env); } }; struct var { std::string name; var(const std::string &n) : name(n) {} double operator()(env_t & env) const { return env[name]; } }; struct val { double v; val(double v_) : v(v_) {} double operator()(env_t & env) const { return v; } }; template add make_add(const A &a, const B &b) { return add(a, b); } template multiply make_multiply(const A &a, const B &b) { return multiply(a, b); } int main(int argc, char *argv[]) { env_t env; env["a"] = 3; env["b"] = 4; env["c"] = 5; auto expr = make_add(var("a"), make_multiply(val(2), var("b"))); // or expr_t expr = ... std::cout << expr(env) << std::endl; return 0; } ``````

### zombified commented Dec 20, 2012

 Maybe a little late to the party, but here's a Javascript version: ``````function evaluate(env, exp) { if('Number' in exp) { return exp['Number']; } if('Variable' in exp) { return env[exp['Variable']]; } if('Add' in exp) { return evaluate(env, exp['Add'][0]) + evaluate(env, exp['Add'][1]); } if('Multiply' in exp) { return evaluate(env, exp['Multiply'][0]) * evaluate(env, exp['Multiply'][1]); } } environment = {a:3, b:4, c:5}; expression_tree = {Add:[{Variable:'a'}, {Multiply:[{'Number':2}, {Variable:'b'}]}]}; function result() { return evaluate(environment, expression_tree); } ``````

### megakorre commented Jan 4, 2013

 pew pew ``````#include "stdio.h" #include "string.h" #define NUMBER 1 #define ADD 2 #define MULTIPLY 3 #define VARIABLE 4 typedef struct { char ** keys; int * vals; } env; typedef struct { int type; void * arg_1; void * arg_2; } expr; int evaluate(env* e, expr * ex) { unsigned int i; switch(ex->type) { case NUMBER: return *(int*)ex->arg_1; case ADD: return evaluate(e, ex->arg_1) + evaluate(e, ex->arg_2); case MULTIPLY: return evaluate(e, ex->arg_1) * evaluate(e, ex->arg_2); case VARIABLE: for (i = 0; e->keys[i] != NULL; i++) { if(strcmp(e->keys[i], (char*)ex->arg_1) == 0) { return e->vals[i]; } } } } int main() { char * keys[] = {"a", "b", "c", NULL}; int vals[] = {3, 4, 5}; env e = { .keys = keys, .vals = vals }; int i = 1; expr numb_1 = {.type=NUMBER, &i}; expr dref_a = {.type=VARIABLE,.arg_1="a"}; expr dref_b = {.type=VARIABLE,.arg_1="b"}; expr add_b_1 = { .type=MULTIPLY, .arg_1=&numb_1, .arg_2=&dref_b }; expr ex = { .type = ADD, .arg_1 = &dref_a, .arg_2 = &add_b_1 }; int x = evaluate(&e, &ex); printf("answer i:%i\n", x); } ``````

### javazquez commented Jan 4, 2013

 Groovy Version ```enum Special { Add, Variable, Multiply, Numb } import static Special.* def evaluate(env,tree){ def ( kword, x ,y ) = tree switch (kword){ case Numb: x ;break; case Add: evaluate(env, x) + evaluate(env, y);break; case Multiply: evaluate(env, x) * evaluate(env, y);break; case Variable: env[x];break; } } def environment =[a:3, b:4, c: 5] def expressionTree =[Add ,[Variable ,'a'] ,[Multiply , [Numb, 2], [Variable, 'b']]] assert evaluate(environment,expressionTree) == 11```

### scientific-coder commented Jan 4, 2013

 C++11 and C (even macros !) mix FTW ! ☺ ```#include #include #include #include #include // sue me int main(int argc, char* argv[]){ std::unordered_map vars{{"a", 1},{"b",2},{"c",3}}; #define OP(c) { #c[0] , [](int o1, int o2){ return o1 c o2 ; } } std::unordered_map > ops {OP(+), OP(-), OP(*), OP(/)}; #undef OP std::cout<< ops['+'](vars["a"], ops['*'](std::atoi("2") , vars["b"])) <

### VladD2 commented Jan 5, 2013

 Nemerle (using quasiquotation) ```using Nemerle.Collections; using Nemerle.Compiler; using System.Console; class CompilerHost : ManagerClass { public this() { base(CompilationOptions()); InitCompiler(); LoadExternalLibraries(); } } module Program { Main() : void { def _compiler = CompilerHost(); def env = Hashtable([("a", 3), ("b", 4), ("c", 5)]); def expressionTree = <[ a + 2 * b]>; def eval(expr) { | <[ \$x + \$y ]> => eval(x) + eval(y) | <[ \$x * \$y ]> => eval(x) * eval(y) | <[ \$(x : int) ]> => x | <[ \$x ]> => env[x.ToString()] } WriteLine(eval(expressionTree)); } }```

### jbransen commented Jan 30, 2013

 Using Attribute Grammars we can write in in a compositional way. Of course a more concise version is possible, but this way the code is nicely split up into separate aspects. Syntax is that of UUAGC, a preprocessor for Haskell. ```imports { import Data.Map } -- Constants and addition data Expression | Number n :: Integer | Add l, r :: Expression attr Expression syn eval :: Integer sem Expression | Number lhs.eval = @n | Add lhs.eval = @l.eval + @r.eval -- Add multiplication data Expression | Multiply l, r :: Expression sem Expression | Multiply lhs.eval = @l.eval * @r.eval -- Add variables and environment data Expression | Variable var :: String {type Env = Map String Integer} attr Expression inh env :: Env sem Expression | Variable lhs.eval = findWithDefault 0 @var @lhs.env -- Testing code { environment :: Env environment = fromList [("a",3), ("b",4), ("c",7)] expressionTree :: Expression expressionTree = Add (Variable "a") (Multiply (Number 2) (Variable "b")) -- General interface to get the "eval" attribute from the expression, -- given the "env" inherited attribute result :: Integer result = eval_Syn_Expression \$ wrap_Expression (sem_Expression expressionTree) \$ Inh_Expression { env_Inh_Expression = environment } -- Simple interface, since there is only 1 inherited and only 1 synthesized attribute result2 :: Integer result2 = sem_Expression expressionTree environment }```

### doaitse commented Jan 31, 2013

 using overloading of numeric operators and strings in Haskell we get: ```import Data.String import Data.Maybe import Control.Monad type Expr = ([(String, Integer)] -> Integer) instance Num Expr where (+) = liftM2 (+) (*) = liftM2 (*) fromInteger = const instance IsString Expr where fromString x = fromJust . lookup x main = print \$ ("a" + 2 * "b" :: Expr) [("a",3), ("b",4), ("c",7)]```

### marcosomarviera commented Feb 5, 2013

 Using AspectAG, a Haskell library of strongly typed Attribute Grammars. The code is similar to the UUAGC code posted before, but it's written directly in Haskell (+ extensions). ```-- In this example implementation we have placed all different aspects -- in a single file. -- Notice however that the code for e.g. the addition, the multiplication -- and the variable case could have been distributed over three different -- files which can be compiled separately {-# OPTIONS -fcontext-stack=100 #-} {-# LANGUAGE TemplateHaskell, EmptyDataDecls, NoMonomorphismRestriction #-} module Expr where import Language.Grammars.AspectAG import Language.Grammars.AspectAG.Derive import Data.HList.Label4 import Data.HList.TypeEqGeneric1 import Data.HList.TypeCastGeneric1 import Control.Applicative import Data.Map -- --------------------------------------------------------------------------------------- -- We start by defining what should happen for Constants and Addition -- --------------------------------------------------------------------------------------- data Expression = Number {n :: Integer} | Add {l,r :: Expression} \$(deriveAG ''Expression) \$(attLabels ["eval"]) evalNT = nt_Expression .*. hNil -- the attribute which carries the result of the evaluation is introduced for the Expression non-terminal evalNumber = syn eval \$ at ch_n evalAdd = syn eval \$ (+) <\$> ch_l `attr` eval <*> ch_r `attr` eval -- --------------------------------------------------------------------------------------- -- We extend the data type at hand and add multiplication -- --------------------------------------------------------------------------------------- data EXT_Expression = Multiply {ml, mr :: Expression} \$(extendAG ''EXT_Expression [''Expression]) evalMultiply = syn eval \$ (*) <\$> ch_ml `attr` eval <*> ch_mr `attr` eval -- --------------------------------------------------------------------------------------- -- Finally we extend the system once more to be able to deal with variables, -- add the needed environment attribute. -- Note that none of the above code had to be adapted -- --------------------------------------------------------------------------------------- data EXT2_Expression = Variable {var :: String} \$(extendAG ''EXT2_Expression [ ]) type Env = Map String Integer \$(attLabels ["env"]) envNT = nt_Expression .*. hNil -- the list of non-terminals which carry an env attribute envRule = copy env envNT -- copy rule, makes that the environment is automatically copied to the children evalVariable = syn eval \$ (findWithDefault 0) <\$> at ch_var <*> lhs `attr` env -- --------------------------------------------------------------------------------------- -- In the main module we combine the grammar fragments defined above, -- and construct the semantic functions by combining the attribute definitions -- --------------------------------------------------------------------------------------- sem_Number = semP_Number evalNumber -- the semP functions know about the children of the production sem_Add = semP_Add (envRule `ext` evalAdd) sem_Multiply = semP_Multiply (envRule `ext` evalMultiply) sem_Variable = semP_Variable evalVariable -- Testing code environment :: Env environment = fromList [("a",3), ("b",4), ("c",7)] expressionTree = sem_Add (sem_Variable \$ sem_Lit "a") (sem_Multiply (sem_Number \$ sem_Lit 2) (sem_Variable \$ sem_Lit "b")) result :: Integer result = expressionTree (env .=. environment .*. emptyRecord) # eval```

### asajeffrey commented Feb 8, 2013

 A JavaScript version that uses prototype-based method dispatch: ```function Var(x) { this.x = x; } function Plus(x,y) { this.x = x; this.y = y; } function Times(x,y) { this.x = x; this.y = y; } function Const(k) { this.k = k; } Var.prototype.eval = function(env) { return env[this.x]; } Plus.prototype.eval = function(env) { return this.x.eval(env) + this.y.eval(env); } Times.prototype.eval = function(env) { return this.x.eval(env) * this.y.eval(env); } Const.prototype.eval = function(env) { return this.k; } var environment = { a:3, b:5, c:5 }; var expression = new Plus(new Var("a"),new Times(new Const(2),new Var("b"))); console.log(expression.eval(environment));```

### Gonzih commented Feb 18, 2013

 Clojure With Multimethods ```(defmulti evaluate (fn [_ [sym _ _]] sym)) (defmethod evaluate 'Number [_ [_ x _]] x) (defmethod evaluate 'Add [env [_ x y]] (+ (evaluate env x) (evaluate env y))) (defmethod evaluate 'Multiply [env [_ x y]] (* (evaluate env x) (evaluate env y))) (defmethod evaluate 'Variable [env [_ x _]] (env x)) (def environment {"a" 3, "b" 4, "c" 5}) (def expression-tree '(Add (Variable "a") (Multiply (Number 2) (Variable "b")))) (def result (evaluate environment expression-tree)) ```

### leikind commented Feb 18, 2013

 Elixir version :) The same as the erlang version, only using `case` pattern matching instead of pattern matching in the function declaration. ```defmodule Ast do def eval(tree, env) do case tree do {:number, n} -> n {:add, l, r} -> eval(l, env) + eval(r, env) {:mul, l, r} -> eval(l, env) * eval(r, env) {:variable, id} -> Dict.get(env, id) end end def start do env = HashDict.new [a: 1, b: 2, c: 3] tree = {:add, {:variable, :a}, {:mul, {:number, 2}, {:variable, :b}}} IO.puts Ast.eval(tree, env) end end Ast.start```

### abdonn commented Feb 19, 2013

 clojure with eval ```(defn evaluate [tree env] (eval (clojure.walk/prewalk-replace {'add +, 'multiply *, 'number identity, 'variable env} tree))) (def environment {:a 3, :b 4, :c 5}) (def expression-tree '(add (variable :a) (multiply (number 2) (variable :b)))) (evaluate expression-tree environment)```

### markoutso commented Feb 21, 2013

 Another javascript... ```var Number = function(n) { return function(env) { return n }}; var Add = function(e1, e2) { return function(env) { return e1(env) + e2(env) }}; var Variable = function(s) { return function(env) { return env[s] }}; var Multiply = function(e1, e2) { return function(env) { return e1(env) * e2(env) }}; var env = {a: 3, b: 4}; var result = Add(Variable("a"), Multiply(Number(2), Variable("b")))(env);```

### wstucco commented Mar 31, 2013

 quick & dirt PHP LOL ``` 3, "b" => 4, "c" => 7); \$expression_tree = array( "add" => array( "variable" => "a", "multiply" => array( "number" => 2, "variable" => "b" ) ) ); // OR function number(\$n) { return function(\$env) use (\$n) { return \$n; }; } function variable(\$a) { return function(\$env) use (\$a) { return \$env[\$a]; }; } function add(\$a, \$b) { return function(\$env) use (\$a, \$b) { return \$a(\$env) + \$b(\$env); }; } function mul(\$a, \$b) { return function(\$env) use (\$a, \$b) { return \$a(\$env) * \$b(\$env); }; } function evaluate2(\$env, \$tree) { return \$tree(\$env); } \$tree = add(variable("a"), mul(number(2), variable("b"))); \$result = evaluate(\$environment, \$expression_tree); \$result2 = evaluate2(\$environment, \$tree);```

### dalewking commented May 16, 2013

 Slight nitpick, but in the scala and F# versions, the definition of environment is needlessly broken into 3 lines, while in other languages it is done in one line. That artificially inflates the number of lines. The F# version also includes comments while none of the others do. You should be consistent for more direct comparison.

### ehaliewicz commented Jun 13, 2013

 Common Lisp with eval ```(setf (symbol-function 'add) #'+ (symbol-function 'multiply) #'* (symbol-function 'number) #'identity) (defmacro variable (var) (intern var)) (defun evaluate (expr env) (eval `(let ,(mapcar (lambda (a) (cons (intern (car a)) (cdr a))) env) ,expr))) (evaluate '(Add (Variable "a") (Multiply (Number 2) (Variable "b"))) '(("a" 3) ("b" 4) ("c" 5))) => 11```

### janderit commented Jul 3, 2013

 ```// c#, object-oriented interface Expression { int Eval(Environment environment); } sealed class Environment : System.Collections.Generic.Dictionary { } static class Expressions { sealed class ConstantExpression : Expression { private readonly int _value; public ConstantExpression(int value) { _value = value; } public int Eval(Environment environment) { return _value; } } sealed class AdditionExpression : Expression { private readonly Expression _left; private readonly Expression _right; public AdditionExpression(Expression left, Expression right) { _left = left; _right = right; } public int Eval(Environment environment) { return _left.Eval(environment) + _right.Eval(environment); } } sealed class MultiplicationExpression : Expression { private readonly Expression _left; private readonly Expression _right; public MultiplicationExpression(Expression left, Expression right) { _left = left; _right = right; } public int Eval(Environment environment) { return _left.Eval(environment) * _right.Eval(environment); } } sealed class VariableExpression : Expression { private readonly string _symbol; public VariableExpression(string symbol) { _symbol = symbol; } public int Eval(Environment environment) { return environment[_symbol]; } } public static Expression Add(Expression left, Expression right) { return new AdditionExpression(left,right); } public static Expression Multiply(Expression left, Expression right) { return new MultiplicationExpression(left,right); } public static Expression Variable(string symbol) { return new VariableExpression(symbol); } public static Expression Number(int value) { return new ConstantExpression(value); } } class Program { private static void Main(string[] args) { var environment = new Environment {{"a", 3}, {"b", 4}, {"c", 5}}; var expressionTree = Expressions.Add(Expressions.Variable("a"), Expressions.Multiply(Expressions.Number(2), Expressions.Variable("b"))); System.Console.WriteLine(expressionTree.Eval(environment)); System.Console.ReadLine(); } } ```

### janderit commented Jul 3, 2013

 ```// c#, functional (concise) using System; sealed class Environment : System.Collections.Generic.Dictionary { } delegate int Expression(Environment environment); class Program { private static void Main(string[] args) { Func number = value => env => value; Func add = (left, right) => env => left(env) + right(env); Func multiply = (left, right) => env => left(env) * right(env); Func variable = symbol => env => env[symbol]; var environment = new Environment {{"a", 3}, {"b", 4}, {"c", 5}}; var expressionTree = add(variable("a"), multiply(number(2), variable("b"))); Console.WriteLine(expressionTree(environment)); Console.ReadLine(); } } ```

### janderit commented Jul 3, 2013

 ```// c#, runtime code generation using the LINQ expression library using System; using System.Linq.Expressions; sealed class Environment : System.Collections.Generic.Dictionary { } class Program { private static void Main(string[] args) { var environment = new Environment { { "a", 3 }, { "b", 4 }, { "c", 5 } }; Expression> expression = env => env["a"] + (2*env["b"]); Console.WriteLine(expression.Compile()(environment)); Console.ReadLine(); } } // the expression: Expression> expression = env => env["a"] + (2*env["b"]); // is only compiled at run time. // The c# compiler only translates the expression into an expression tree data structure. // If this feels like cheating (it isn't), this is the de-sugared full equivalent: using System.Linq.Expressions; sealed class Environment : System.Collections.Generic.Dictionary { } class Program { private static void Main(string[] args) { var environment = new Environment { { "a", 3 }, { "b", 4 }, { "c", 5 } }; var parameter = Expression.Parameter(typeof (Environment)); var expression = Expression.Lambda>( Expression.Add( Expression.Call(parameter, "get_Item", null, Expression.Constant("a")), Expression.Multiply( Expression.Constant(2), Expression.Call(parameter, "get_Item", null, Expression.Constant("b")) ) ), parameter ); System.Console.WriteLine(expression.Compile()(environment)); System.Console.ReadLine(); } } ```

### pkukielka commented Nov 14, 2013

 Another Scala approach: ```object ExprEval extends App { type Expr = Map[Symbol, Int] => Int def number (value: Int): Expr = env => value def variable (sym: Symbol): Expr = env => env(sym) def multiply (a: Expr, b: Expr): Expr = env => a(env) * b(env) def add (a: Expr, b: Expr): Expr = env => a(env) + b(env) val environment = Map('a -> 1, 'b -> 2, 'c -> 3) val expressionTree = add(variable('a), multiply(number(2), variable('b))) println(expressionTree(environment)) }``` Also with scalaz and Reader Monad we can bind our symbols to real variables and then write whole equation inside yield like we would normally do using language constructs: ```import scalaz._, Scalaz._ object ExprEval extends App { def variable(symbol: Symbol) = Reader((env: Map[Symbol, Int]) => env(symbol)) val environment = Map('a -> 1, 'b -> 2, 'c -> 3) val expressionTree = for { a <- variable('a) b <- variable('b) } yield a + (2 * b) println(expressionTree(environment)) }``` What is worth noting is that we are not limited to + and * operations, but we get all other language constructs for free: ```val expressionTree = for { a <- variable('a) b <- variable('b) c <- variable('c) } yield math.pow(a + (2 * b) % c * 0.4f, 2)```

### chrisdavies commented Jan 3, 2014

 A bit more idiomatic C# ``````using System; using Env = System.Collections.Generic.Dictionary; delegate int Expr(Env e); public class Program { public static void Main() { Func Var = s => env => env[s]; Func Num = i => env => i; Func Add = (x, y) => env => x(env) + y(env); Func Mul = (x, y) => env => x(env) * y(env); var expr = Add(Var("a"), Mul(Num(2), Var("b"))); Console.WriteLine(expr(new Env { { "a", 3 }, { "b", 4 }, { "c", 5 } })); } } ``````

### ghost commented Feb 9, 2014

 Using Star: ``````package exp{ type Exp is Var(string) or Num(integer) or Add(Exp,Exp) or Mul(Exp,Exp); Eval(Var(Nm),env) is env[Nm]; Eval(Num(I),_) is I; Eval(Add(L,R),env) is Eval(L,env) + Eval(R,env) Eval(Mul(L,R),env) is Eval(L,env) * Eval(R,env) main() do { logMsg(info,"Answer \$(Eval(Add(Var("a"),Mul(Num(2),Var("b"))), map of {"a"->3; "b"->4; "c"->5}))"); } } ``````

### slimane commented Mar 7, 2014

 Vim Script ```function! s:eval(env, exp) let l:type = a:exp[0] if l:type == "Number" return a:exp[1] elseif l:type == "Variable" return a:env[a:exp[1]] elseif l:type == "Add" return s:eval(a:env, a:exp[1]) + s:eval(a:env, a:exp[2]) elseif l:type == "Multiply" return s:eval(a:env, a:exp[1]) * s:eval(a:env, a:exp[2]) endif echoerr "Arguments Error" endfunction function! s:run() let exp_tree = ["Add", ["Variable", "a"], ["Multiply", ["Number", 2], ["Variable", "b"]]] let env = {"a":3, "b" : 4, "c" : 5 } echomsg s:eval(env, exp_tree) endfunction call s:run()```

### gmarik commented Apr 13, 2014

 Ruby function/proc based ```Mul = ->(e1, e2){ ->(env){ e1.(env) * e2.(env) }} Add = ->(e1, e2){ ->(env){ e1.(env) + e2.(env) }} Var = ->(e) { ->(env){ env[e] }} Num = ->(e) { ->(env){ e }} ast = Add.(Var.(:a), (Mul.(Num.(2), Var.(:b)))) puts ast.({ a: 3, b: 4, c: 5 })```

### gmarik commented Apr 13, 2014

 Go function based ```package main type Env map[string]int type Expr func(Env) int func Add(a, b Expr) Expr { return func(env Env) int { return a(env) + b(env) } } func Mul(a, b Expr) Expr { return func(env Env) int { return a(env) * b(env) } } func Var(name string) Expr { return func(env Env) int { return env[name] } } func Num(val int) Expr { return func(env Env) int { return val } } func main() { ast := Add(Var("a"), (Mul(Num(2), Var("b")))) println(ast(Env{"a": 3, "b": 4, "c": 5})) }```

### gmarik commented Apr 13, 2014

 Ruby OO dynamic dispatch ```class Expr def initialize(*args); @args = args end def self.call(*args); new(*args) end end class Mul < Expr def eval(env); @args[0].eval(env) * @args[1].eval(env) end end class Add < Expr def eval(env); @args[0].eval(env) + @args[1].eval(env) end end class Var < Expr def eval(env); env[@args[0]] end end class Num < Expr def eval(env); @args[0] end end ast = Add.(Var.(:a), (Mul.(Num.(2), Var.(:b)))) puts ast.eval({a: 3, b:4, c:5})```

### gmarik commented Apr 13, 2014

 Ruby OO static dispatch ```class Expr attr_accessor :args def initialize(*args); @args = args end def self.call(*args); new(*args) end end class Mul < Expr; end class Add < Expr; end class Var < Expr; end class Num < Expr; end class Env def initialize(env); @env = env end def eval(ast) case ast when Num then ast.args[0] when Var then @env[ast.args[0]] when Mul then self.eval(ast.args[0]) * self.eval(ast.args[1]) when Add then self.eval(ast.args[0]) + self.eval(ast.args[1]) end end end Env. new({a: 3, b:4, c:5}). eval(ast = Add.(Var.(:a), (Mul.(Num.(2), Var.(:b)))))```

### dbohdan commented Jun 10, 2015

 Tcl ```namespace eval ::ast { namespace export evaluate namespace ensemble create namespace path ::tcl::mathop proc evaluate { env exp } { lassign \$exp token arg1 arg2 switch -exact -- \$token { Number { return \$arg1 } Add { return [+ [evaluate \$env \$arg1] [evaluate \$env \$arg2]] } Multiply { return [* [evaluate \$env \$arg1] [evaluate \$env \$arg2]] } Variable { return [dict get \$env \$arg1] } default { error "Unknown token: \$token" } } } } set environment { a 3 b 4 c 5 } puts [ast evaluate \$environment { Add { Variable a } { Multiply { Number 2 } { Variable b } } }]```

### comfly commented Aug 1, 2015

 Swift 2.0: ```indirect enum Expression { case Number(Int) case Add(Expression, Expression) case Multiply(Expression, Expression) case Variable(String) } func evaluate(env: [String: Int], _ expression: Expression) -> Int { switch expression { case let .Number(n): return n case let .Add(l, r): return evaluate(env, l) + evaluate(env, r) case let .Multiply(l, r): return evaluate(env, l) * evaluate(env, r) case .Variable(let name): return env[name] ?? 0 } } let expressionTree: Expression = .Add(.Variable("a"), .Multiply(.Number(2), .Variable("b"))) let result = evaluate(["a": 3, "b": 4, "c": 7], expressionTree)```

### danielhenrymantilla commented Aug 17, 2015

 Back to Ocaml, to show a comparison between OOP and FP (and show that this language may also be decent at OOP) So the objective is writing some code so that the following lines will do their job : (For aesthetic purposes I'll be using infix operators (e.g. `|+|` instead of `add`)) ```let expr = (variable "a") |+| ((number 2) |*| (variable "b")) let env = function "a" -> 3 | "b" -> 4 | "c" -> 7 | c -> failwith ("Unbound variable " ^ c) let result = eval env expr``` Note that the idea behind the `env` parameter is to be able to define the expression without it, and only use it when evaluating the actual value of the expression. I point this out because some of the proposed solutions do not follow that idea. So, now with the actual solution. I have decided to keep it more generalised with polymorphic expressions (`'a expr`) and allowing any 2-ary operator (`'a -> 'a -> 'a`) FP classical and elegant Ocaml : ```type 'a expr = | Number of 'a | Variable of string | Node of 'a expr * ('a -> 'a -> 'a) * 'a expr let eval env = let rec go = function (*auxiliary 'go' function to avoid having to pass the 'env' argument*) | Number n -> n | Variable v -> env v | Node(e1,op,e2) -> op (go e1) (go e2) in go let mk_op op = fun e1 e2 -> Node(e1,op,e2) let (|+|) = mk_op (+) and (|+.|) = mk_op (+.) and (|*|) = mk_op ( * ) and (|*.|) = mk_op ( *.) let expr = (Variable "a") |+| ((Number 2) |*| (Variable "b")) let env = function "a" -> 3 | "b" -> 4 | "c" -> 7 | c -> failwith ("Unbound variable " ^ c) let result = eval env expr``` Object-Oriented Version 2.1) with an Interface : type definition and type force cast ```type 'a expr = < eval : (string -> 'a) -> 'a > (* Interface : object with method 'eval' *) let number x : 'a expr = object method eval _ = x end (* Placeholder : no need to bind the input arg *) and variable c : 'a expr = object method eval env = env c end let mk_op op = fun e1 e2 -> object method eval env = op (e1#eval env) (e2#eval env) end let (|+|) = mk_op (+) and (|+.|) = mk_op (+.) and (|*|) = mk_op ( * ) and (|*.|) = mk_op ( *.) let expr = (variable "a") |+| ((number 2) |*| (variable "b")) let env = function "a" -> 3 | "b" -> 4 | "c" -> 7 | c -> failwith ("Unbound variable " ^ c) let result = expr#eval env``` 2.2) with an abstract class : object inheritance ```class virtual ['a] expr = object method virtual eval : (string -> 'a) -> 'a end let number (x : 'a) = object inherit ['a] expr method eval _ = x end and variable c = object inherit ['a] expr method eval env = env c end ...``` Ok, now that we got the main idea, let's work the abstraction (why? for instance, in the second example, any object with a "valid" `eval` method would be implementing the `'a expr` interface, which could be dangerous) We will be using the famous Ocaml Modules and explicit signatures to do so (A module type (kind of a module interface) is defined so that any module forced to that type therefore has to satisfy its abstracted signature) ```module type AST_type = sig (* some unspecified type 'a expr => Abstract type *) type 'a expr val eval : (string -> 'a) -> 'a expr -> 'a (* we need expr makers now that the expr type is abstract *) val number : 'a -> 'a expr val variable : string -> 'a expr val mk_op : ('a ->'a ->'a) -> 'a expr -> 'a expr -> 'a expr val (|+|) : int expr -> int expr -> int expr val (|+.|) : float expr -> float expr -> float expr val (|*|) : int expr -> int expr -> int expr val (|*.|) : float expr -> float expr -> float expr end``` So our two previous examples are two implementations of that signature : (Forced by the initial module type cast `: AST_type`) ```module AST_Object : AST_type = struct type 'a expr = < eval : (string -> 'a) -> 'a > let eval env e = e#eval env (* Dummy definition to match the signature and stay in the abstraction *) let number x : 'a expr = object method eval _ = x end and variable c : 'a expr = object method eval env = env c end let mk_op op = fun e1 e2 -> object method eval env = op (e1#eval env) (e2#eval env) end let (|+|) = mk_op (+) and (|+.|) = mk_op (+.) and (|*|) = mk_op ( * ) and (|*.|) = mk_op ( *.) end module AST_Functional : AST_type = struct type 'a expr = | Number of 'a | Variable of string | Node of 'a expr * ('a -> 'a -> 'a) * 'a expr let variable s = Variable s and number x = Number x (* Same here *) let eval env = let rec go = function | Number n -> n | Variable v -> env v | Node(e1,op,e2) -> op (go e1) (go e2) in go let mk_op op = fun e1 e2 -> Node(e1,op,e2) let (|+|) = mk_op (+) and (|+.|) = mk_op (+.) and (|*|) = mk_op ( * ) and (|*.|) = mk_op ( *.) end``` And finally we choose our desired implementation (e.g. AST_Object) and use it : ```open AST_Object (* or 'open AST_Functional' *) let expr = (variable "a") |+.| ((number 2.) |*.| (variable "b")) let env = function "a" -> 3. | "b" -> 4. | "c" -> 7. | c -> failwith ("Unbound variable " ^ c) let result = eval env expr```

### cljfun commented Oct 19, 2015

 Shorter Clojure: ```(defn Add [x y] #(+ (x %) (y %))) (defn Mul [x y] #(* (x %) (y %))) (defn Var [x] #(x %)) (defn Num [x] (fn [_] x)) (def ast (Add (Var 'a) (Mul (Num 2) (Var 'b)))) (def env '{a 3 b 4 c 5}) (def result (ast env))```

### alecroy commented Feb 12, 2016

 Rust 1.6.0 (updated z0w0's example): ```use std::collections::HashMap; use std::iter::FromIterator; use Expression::{Number, Add, Multiply, Variable}; enum Expression { Number(i32), Add(Box, Box), Multiply(Box, Box), Variable(&'static str) } fn evaluate(env: &HashMap<&str, i32>, exp: Expression) -> i32 { match exp { Number(num) => num, Add(x, y) => evaluate(env, *x) + evaluate(env, *y), Multiply(x, y) => evaluate(env, *x) * evaluate(env, *y), Variable(id) => *env.get(id).expect(&format!("variable not found: {}", id)), } } fn main() { let e: HashMap<&str, i32> = HashMap::from_iter(vec![("a", 1), ("b", 2)]); let tree = Add(Box::new(Variable("a")), Box::new(Multiply(Box::new(Number(2)), Box::new(Variable("b"))))); println!("{}", evaluate(&e, tree)); }``` I don't really know much about Rust, to be honest with you. It seems much has changed since 2012.

### ghost commented May 4, 2016

 JavaScript ES2015 ```let Number = (n) => (env) => n let Add = (e1, e2) => (env) => e1(env) + e2(env) let Variable = (s) => (env) => env[s] let Multiply = (e1, e2) => (env) => e1(env) * e2(env) let environment = {a: 3, b: 4} let expression = Add(Variable('a'), Multiply(Number(2), Variable('b'))) console.log(expression(environment))```

### royalstream commented May 4, 2016 • edited

 Question (regarding several implementations I just read): I would have thought the AST had to be a data expression that can be traversed with different purposes (evaluating, printing, transforming, etc). I don't know if declaring functions/lambdas/etc called Add, Multiply, etc, still qualifies as an Abstract Syntax Tree. I mean, it obviously leads to very compact code (no kidding) but it's no longer a data structure and you can't do anything with it (except evaluating it). Unrelated to the previous question, here's a slightly shorter F# version using `function` instead of `match` (à la OCaml) ```type Expression = | Number of int | Add of Expression * Expression | Multiply of Expression * Expression | Variable of string let rec Evaluate (env:Map) = function | Number n -> n | Add (x, y) -> Evaluate env x + Evaluate env y | Multiply (x, y) -> Evaluate env x * Evaluate env y | Variable id -> env.[id] let environment = Map.ofList [ "a", 1 ; "b", 2 ; "c", 3 ] let expressionTree1 = Add(Variable "a", Multiply(Number 2, Variable "b")) let result = Evaluate environment expressionTree1 ```

### jdh30 commented Apr 4, 2017

 As others have noted: you don't need any type annotations in either the OCaml or the F# and you don't even need a type definition in the OCaml because you can use polymorphic variants. Reminds me of these OCaml examples I wrote about 12 years ago: http://www.ffconsultancy.com/ocaml/benefits/examples.html and this comparison we did a few years back: http://shenlanguage.org/lambdassociates/htdocs/studies/study10.htm and this: http://codereview.stackexchange.com/questions/11804/symbolic-derivative-in-c Some of the responses have inverted the problem. To help stop that you can pose a problem for which more than one function over the expression type is required. For example, you might multiply out brackets or compute the symbolic derivative before evaluating. You've also chosen a problem for which dispatch is trivial so pattern matching doesn't help. If you did, for example, symbolic simplification then a big gap would appear between languages without pattern matching and those with. I'd love to see a similar comparison with a fuller interpreter such as the one I linked to above.

### thetrung commented Apr 23, 2020

 FSharp implementation is still the clearest one, while 1st Ruby & JS implementation are my favorite ! Crystal anyone ?

### paytonrules commented Apr 23, 2020

 Funny nobody has mentioned this - but the extension should be `fsharp.fs` not `ml`. Gonna guess you did the OCaml one first?

### thetrung commented Nov 2, 2020 • edited

 in my own fantasy language : ``````func Add ( a b ) push ( a + b ) ret -- return topmost node on stack func Mul ( a b ) push ( a * b ) ret func Var ( env name val ) push [ name val ] -- push an array to stack local _ -- make local variable end local expr = { [a b], Mul, [a 3], Var, [b 4], Var } func Eval ( expr ) load expr -- load all elements in List to stack Loop : nil? -- check if stack nil? jmp? Exit -- jump if true call _ -- call whatever on stack jmp Loop -- jump to Loop Exit : call print -- print whatever remaining on stack end push expr call Eval ``````

### kapitancho commented Jan 22, 2021

 //PHP - arrow functions version: ``` fn(array \$env) => \$n; \$variable = fn(string \$a) => fn(array \$env) => \$env[\$a] ?? 0; \$add = fn(\$a, \$b) => fn(array \$env) => \$a(\$env) + \$b(\$env); \$mul = fn(\$a, \$b) => fn(array \$env) => \$a(\$env) * \$b(\$env); \$evaluate = fn(array \$env, \$tree) => \$tree(\$env); \$environment = ["a" => 3, "b" => 4, "c" => 7]; \$tree = \$add(\$variable("a"), \$mul(\$number(2), \$variable("b"))); \$result = \$evaluate(\$environment, \$tree);```