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 = fold where
    fold (Number x) = x
    fold (Add x y) = fold x + fold y
    fold (Multiply x y) = fold x * fold y
    fold (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-gadt.hs

{-# LANGUAGE GADTs, ExistentialQuantification, ViewPatterns,
             DeriveDataTypeable, UnicodeSyntax
  #-}

import Data.Map
import Data.Maybe
import Data.Typeable

data Expr a where
    Const ∷ a → Expr a
    Add, Mul ∷ Num a ⇒ Expr a → Expr a → Expr a
    Var ∷ Typeable a ⇒ String → Expr a
    Equal ∷ Eq a ⇒ Expr a → Expr a → Expr Bool
    deriving (Typeable)

instance Num a ⇒ Num (Expr a) where
    fromInteger = Const . fromInteger
    (+) = Add
    (*) = Mul

data AnyExpr = ∀ a . (Typeable a, Show a) ⇒ AnyExpr (Expr a)

instance Num AnyExpr where fromInteger = AnyExpr . Const

type Environment = Map String AnyExpr

evaluate ∷ Environment → Expr a → a
evaluate env = fold where
    resolve = (env!)
    unbox (AnyExpr x) = fromJust (cast x)
    fold ∷ Expr a → a
    fold (Const x) = x
    fold (Add a b) = fold a + fold b
    fold (Mul a b) = fold a * fold b
    fold (Equal a b) = fold a == fold b
    fold (Var (resolve → unbox → e)) = fold e

testEnv = fromList [
        ("a", 1),
        ("b", 2),
        ("c", 3),
        ("result", AnyExpr (Var "a" + 2 * (Var "b") ∷ Expr Integer)),
        ("test", AnyExpr (Equal (Var "a") (5 ∷ Expr Integer)))
        ]

result = evaluate testEnv (Var "result") ∷ Integer
test = evaluate testEnv (Var "test") ∷ Bool

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

//Here's the Scala version...

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