Language Compare F#, Ocaml, Scala, Clojure, Ruby and Haskell - Simple AST example

clojure-match.clj

(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)) 

clojure-protocol.clj

(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)) 
  

fsharp.ml

//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<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 = 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

haskell-case.hs

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

haskell-constructor.hs

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

ocaml.ml

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

ruby-jimweirich.rb

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)

ruby2-jimweirich.rb

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)

scala.scala

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))
}

ugly.java

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; }
}

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)));
}

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.

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.

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

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)```

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)

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)

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())
}

Another Java version

interface ExpressionVisitor<R, E> {
    R number(int value);
    R variable(String name);
    R multiply(E x, E y);
    R add(E x, E y);
}

interface Expression {
    <R> R accept(ExpressionVisitor<R, Expression> visitor);
}

class Number implements Expression {
    private final int value;

    public Number(int value) {
        this.value = value;
    }

    @Override
    public <R> R accept(ExpressionVisitor<R, Expression> visitor) {
        return visitor.number(value);
    }
}

class Variable implements Expression {
    private final String name;

    public Variable(int name) {
        this.name = name;
    }

    @Override
    public <R> R accept(ExpressionVisitor<R, Expression> 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> R accept(ExpressionVisitor<R, Expression> 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> R accept(ExpressionVisitor<R, Expression> visitor) {
        return visitor.add(x, y);
    }
}

class EvaluatorVisitor implements ExpressionVisitor<Integer, Expression> {
    private final Map<String, Integer> environment;

    public EvaluatorVisitor(Map<String, Integer> 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<String, Integer> environment, Expression expression) {
        return expression.accept(new EvaluatorVisitor(environment));
    }

    public static void main(String[] args) {
        Map<String, Integer> 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));
    }
}

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.

my C++ version:

#include <string>
#include <map>
#include <iostream>

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<std::string, int>& 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<std::string, int>& _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<std::string, int> 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)

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);
  }
}

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)

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))
}

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
}

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<String,Integer> 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
}

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.

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 <string>
#include <iostream>
#include <map>
#include <memory>

typedef std::map <std::string, int> Variables;

struct Expr
{
    virtual ~Expr() {}
    virtual int eval (Variables&) = 0;
};

struct Multiply   : public Expr
{
    std::unique_ptr<Expr> 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<Expr> 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;
}

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);

Java8

import java.util.*;
import java.util.functions.*;
import java.io.*;

public class Test {

    interface Expr  {
            int eval(Map<String, Integer> 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<String, Integer> env = new HashMap<String, Integer>(){{
         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();
    }
}

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<k,v,def> implemented.

#include <iostream>

#include <boost/mpl/int.hpp>
#include <boost/mpl/plus.hpp>
#include <boost/mpl/times.hpp>
#include <boost/mpl/arithmetic.hpp>

#include <boost/mpl/at.hpp>
#include <boost/mpl/map.hpp>
#include <boost/mpl/pair.hpp>

using namespace boost::mpl;

template <typename lhs, typename rhs> struct Add      {};
template <typename lhs, typename rhs> struct Multiply {};
template <int value>                  struct Number   {};
template <typename name>              struct Variable {};

template <class expr, class env> struct evaluate {};

template <typename lhs, typename rhs, typename env>
struct evaluate<Add<lhs,rhs>, env> {
    typedef typename plus< typename evaluate<lhs, env>::type
                         , typename evaluate<rhs, env>::type >::type type;
};

template <typename lhs, typename rhs, typename env>
struct evaluate<Multiply<lhs,rhs>, env> {
    typedef typename times< typename evaluate<lhs, env>::type
                          , typename evaluate<rhs, env>::type >::type type;
};

template <int value, typename env>
struct evaluate<Number<value>, env> {
    typedef int_<value> type;
};

template <typename name, typename env>
struct evaluate<Variable<name>, env> {
    typedef typename at<env, name>::type type;
};

struct a {};
struct b {};
struct c {};

typedef map< pair<a, int_<3> >
           , pair<b, int_<4> >
           , pair<c, int_<7> >
           > environment;
typedef Add<Variable<a>, Multiply<Number<2>, Variable<b> > > expression_tree;

typedef evaluate<expression_tree, environment>::type result;

int main() {
    std::cout << result::value << std::endl;
    return 0;
}

WOW, why are these C++ solutions so bad:

#include <iostream>
#include <unordered_map>

using data=std::unordered_map<char, double>;

template<int D> struct val { 
    double operator() (const data&) const { return D; } 
};
template<char I> struct mis {
    double operator()(const data& v) const { return v.at(I); } 
};
template<typename Expr1, typename Expr2> struct add {
    double operator()(const data& v) const { return Expr1()(v)+Expr2()(v);  }
};
template<typename Expr1, typename Expr2> 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;
}

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

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

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)

Also a Python version:

__init__ self self.__init__ eval self self.__init__ __init__ self

/jab

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

Terrible Java code above. Use inheritance, but then butcher it in the evaluate method.

import java.util.*;

public class Eval {
    Map<String, Integer> env;

    public Eval() {
        env = new HashMap<String, Integer>();
        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);
        }
    }
}

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.

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

How about some smaller java code:

import java.util.HashMap;
import java.util.Map;

public abstract class Eval<P> {
    abstract int get(P... params);

    static Eval<Integer> ADD = new Eval<Integer>() {
        @Override
        public int get(Integer... params) {
            return params[0] + params[1];
        };
    };
    static Eval<Integer> MULTIPLY = new Eval<Integer>() {
        @Override
        public int get(Integer... params) {
            return params[0] * params[1];
        }
    };
    static Map<String, Integer> variables = new HashMap<String, Integer>();
    static Eval<String> VARIABLE = new Eval<String>() {
        @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);
    }
}

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

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

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

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)

and brainfuck?

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

Copied from: http://www.reddit.com/r/programming/comments/zbc4e/interesting_language_comparison_building_a_simple/c638oro

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))
}

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

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

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

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]

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

Damn, you guys are C++ scrubs. Let the master show you how it's done.

#include <iostream>
#include <functional>
#include <unordered_map>
using namespace std;
int main() {
    map<string, int> vars = { { "a" , 3 }, { "b", 4 }, { "c", 5 } };
    auto tree = bind(plus<int>(), ref(variables["a"]), bind(multiplies<int>(), 2, ref(variables["b"])));
    cout << tree();
}

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 <string> either. Oh well. Close enough.

The K Semantic Framework:

module EXP is
    syntax Exp ::= Exp "+" Exp [strict]
                 | Exp "*" Exp [strict]
                 | Int
                 | Id

    syntax KResult ::= Int

    configuration
        <k> $PGM:K </k>
        <env> $ENV:Map </env>

    rule I1:Int + I2:Int => I1 +Int I2
    rule I1:Int * I2:Int => I1 *Int I2

    rule
        <k> X:Id => I ...</k>
        <env>... X |-> I:Int ...</env>

end module

Run it:

$ cat pgm.exp 
a + (2 * b)
$ krun --ENV="a |-> 3  b |-> 4" pgm.exp        
<k>                     
  11
</k>
<env>
  a |-> 3
  b |-> 4
</env>

Objective-C version using blocks (closures):

#import <Foundation/Foundation.h>

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;
}

More idiomatic Objective-C, using umbrella class instead of blocks:

#import <Foundation/Foundation.h>

@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;
}

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

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

In C++11, with std::function to do the type erasure

# include # include # include # include

typedef std::map<std::string, double> env_t;
typedef std::function<double(env_t&)> expr_t;

template <class A, class B>
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 <class A, class B>
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 <class A, class B>
add<A, B> make_add(const A &a, const B &b) {
return add<A, B>(a, b);
}

template <class A, class B>
multiply<A, B> make_multiply(const A &a, const B &b) {
return multiply<A, B>(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;
}


I'm sorry for prev comment, it's not formated.

C++11 with std::function to do type erasure.

#include <string>
#include <map>
#include <functional>
#include <iostream>

typedef std::map<std::string, double> env_t;
typedef std::function<double(env_t&)> expr_t;

template <class A, class B>
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 <class A, class B>
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 <class A, class B>
add<A, B> make_add(const A &a, const B &b) {
  return add<A, B>(a, b);
}

template <class A, class B>
multiply<A, B> make_multiply(const A &a, const B &b) {
  return multiply<A, B>(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;
}

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); }

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);
}

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

C++11 and C (even macros !) mix FTW ! ☺

#include <unordered_map>
#include <string>
#include <functional>
#include <iostream>
#include <cstdlib> // sue me

int main(int argc, char* argv[]){
  std::unordered_map<std::string, int> vars{{"a", 1},{"b",2},{"c",3}};
#define OP(c) { #c[0] , [](int o1, int o2){ return o1 c o2 ; } }
  std::unordered_map<char, std::function<int(int,int)> > 
    ops {OP(+), OP(-), OP(*), OP(/)};
#undef OP

  std::cout<< ops['+'](vars["a"], ops['*'](std::atoi("2") , vars["b"])) <<std::endl;
}

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));
  }
}

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
}

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)]

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

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));

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

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

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)

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);

quick & dirt PHP
LOL

<?php

function evaluate($env, $expr) {
    list($e, $v) = each($expr); 

    switch(strtolower($e)) {
        case "add":
            return evaluate($env, array_slice($v,0, 1)) + evaluate($env, array_slice($v, 1, 1));
        break;
        case "multiply":
            return evaluate($env, array_slice($v,0, 1)) * evaluate($env, array_slice($v, 1, 1));
        break;
        case "variable":
            return $env[$v];
        break;
        case "number":
            return $v;
        break;
    }
}

$environment = array("a" => 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);

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.

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

// c#, object-oriented

interface Expression { int Eval(Environment environment); }

sealed class Environment : System.Collections.Generic.Dictionary<string, int> { }

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();
    }
}

// c#, functional (concise)


using System;

sealed class Environment : System.Collections.Generic.Dictionary<string, int> { }

delegate int Expression(Environment environment);

class Program
{
    private static void Main(string[] args)
    {
        Func<int, Expression>                    number   = value         =>  env => value;
        Func<Expression, Expression, Expression> add      = (left, right) =>  env => left(env) + right(env);
        Func<Expression, Expression, Expression> multiply = (left, right) =>  env => left(env) * right(env);
        Func<string, Expression>                 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();
    }
}

// c#, runtime code generation using the LINQ expression library


using System;
using System.Linq.Expressions;

sealed class Environment : System.Collections.Generic.Dictionary<string, int> { }

class Program
{
    private static void Main(string[] args)
    {
        var environment = new Environment { { "a", 3 }, { "b", 4 }, { "c", 5 } };
        Expression<Func<Environment, int>> expression = env => env["a"] + (2*env["b"]);
        Console.WriteLine(expression.Compile()(environment));
        Console.ReadLine();
    }
}




// the expression: Expression<Func<Environment, int>> 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<string, int> { }

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<System.Func<Environment, int>>(
                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();
    }
}

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)

A bit more idiomatic C#

using System;

using Env = System.Collections.Generic.Dictionary<string, int>;

delegate int Expr(Env e);

public class Program
{
    public static void Main()
    {
        Func<string, Expr> Var = s => env => env[s];
        Func<int, Expr> Num = i => env => i;
        Func<Expr, Expr, Expr> Add = (x, y) => env => x(env) + y(env);
        Func<Expr, Expr, Expr> 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 } }));
    }
}

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}))");
  }
}

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()

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 })

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}))
}

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})

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

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 } }
}]

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)

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)

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

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

...

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

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

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<Expression>, Box<Expression>),
    Multiply(Box<Expression>, Box<Expression>),
    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.

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

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<string,int>) = 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  

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.

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

Crystal anyone ?

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

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

//PHP - arrow functions version:

<?php

$number = fn(int $n) => 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);