Skip to content

Instantly share code, notes, and snippets.

@ony
Forked from bkyrlach/Expression.fs
Last active August 29, 2015 14:08
Show Gist options
  • Save ony/5fc2560fb6e2b0dc3227 to your computer and use it in GitHub Desktop.
Save ony/5fc2560fb6e2b0dc3227 to your computer and use it in GitHub Desktop.
(use '[clojure.core.match :only [match]])
(defn evaluate [env [sym x y]]
(match [sym]
['Number] x
['Add] (+ (evaluate env x) (evaluate env y))
['Multiply] (* (evaluate env x) (evaluate env y))
['Variable] (env x)))
(def environment {"a" 3, "b" 4, "c" 5})
(def expression-tree '(Add (Variable "a") (Multiply (Number 2) (Variable "b"))))
(def result (evaluate environment expression-tree))
(defprotocol Expression
(evaluate [e env] ))
(deftype Number1 [x])
(deftype Add [x y] )
(deftype Multiply [x y])
(deftype Variable [x])
(extend-protocol Expression
Number1 (evaluate [e env] (.x e ) )
Add (evaluate [e env] (+ (evaluate (.x e) env) (evaluate (.y e) env)))
Multiply (evaluate [e env] (* (evaluate (.x e) env) (evaluate (.y e) env)))
Variable (evaluate [e env] (env (.x e))))
(def environment {"a" 3, "b" 4, "c" 5})
(def expression-tree (Add. (Variable. "a") (Multiply. (Number1. 2) (Variable. "b"))))
(def result (evaluate expression-tree environment))
//Here's some F# code...
type Expression =
| Number of int
| Add of Expression * Expression
| Multiply of Expression * Expression
| Variable of string
let rec Evaluate (env:Map<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
import Data.Map
data Expression =
Number Int
| Add Expression Expression
| Multiply Expression Expression
| Variable String
evaluate :: Map String Int -> Expression -> Int
evaluate env exp =
case exp of
Number x -> x
Add x y -> evaluate env x + evaluate env y
Multiply x y -> evaluate env x * evaluate env y
Variable x -> findWithDefault 0 x env
environment = fromList([("a",3), ("b",4), ("c",7)])
expressionTree = Add (Variable "a") (Multiply (Number 2) (Variable "b"))
result = evaluate environment expressionTree
import Data.Map
data Expression =
Number Int
| Add Expression Expression
| Multiply Expression Expression
| Variable String
evaluate :: Map String Int -> Expression -> Int
evaluate env = 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
{-# 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
type expression =
Number of int
| Add of expression * expression
| Multiply of expression * expression
| Variable of string
let rec evaluate (env: string->int) exp =
match exp with
Number n -> n
| Add (x, y) -> evaluate env x + evaluate env y
| Multiply (x, y) -> evaluate env x * evaluate env y
| Variable id -> env id
let environment (str: string) : 'a = match str with "a" -> 3 | "b" -> 4 | "c" -> 5
let expressiontree1 = Add(Variable "a", Multiply(Number 2, Variable "b"))
let result = evaluate environment expressiontree1
def evaluate(env, exp)
keyword, a, b = exp
case keyword
when :number; a
when :variable; env[a]
when :add; evaluate(env, a) + evaluate(env, b)
when :multiply; evaluate(env, a) * evaluate(env, b)
end
end
ExpressionTree = [:add, [:variable, :a], [:multiply, [:number, 2], [:variable, :b]]]
Env = { a: 3, b: 4, c: 5 }
puts evaluate(Env, ExpressionTree)
Number = lambda { |env, num| num }
Variable = lambda { |env, var| env[var] }
Add = lambda { |env, a, b| evaluate(env, a) + evaluate(env, b) }
Multiply = lambda { |env, a, b| evaluate(env, a) * evaluate(env, b) }
def evaluate(env, exp)
op, *args = exp
op.(env, *args)
end
ExpressionTree = [Add, [Variable, :a], [Multiply, [Number, 2], [Variable, :b]]]
Env = { a: 3, b: 4, c: 5 }
puts evaluate(Env, ExpressionTree)
//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))
}
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; }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment