-
-
Save ckirkendall/2934374 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 (Number x) = x | |
evaluate env (Add x y) = evaluate env x + evaluate env y | |
evaluate env (Multiply x y) = evaluate env x * evaluate env y | |
evaluate env (Variable x) = findWithDefault 0 x env | |
environment = fromList([("a",3), ("b",4), ("c",7)]) | |
expressionTree = Add (Variable "a") (Multiply (Number 2) (Variable "b")) | |
result = evaluate environment expressionTree |
type expression = | |
Number of int | |
| Add of expression * expression | |
| Multiply of expression * expression | |
| Variable of string | |
let rec evaluate (env: string->int) exp = | |
match exp with | |
Number n -> n | |
| Add (x, y) -> evaluate env x + evaluate env y | |
| Multiply (x, y) -> evaluate env x * evaluate env y | |
| Variable id -> env id | |
let environment (str: string) : 'a = match str with "a" -> 3 | "b" -> 4 | "c" -> 5 | |
let expressiontree1 = Add(Variable "a", Multiply(Number 2, Variable "b")) | |
let result = evaluate environment expressiontree1 |
def evaluate(env, exp) | |
keyword, a, b = exp | |
case keyword | |
when :number; a | |
when :variable; env[a] | |
when :add; evaluate(env, a) + evaluate(env, b) | |
when :multiply; evaluate(env, a) * evaluate(env, b) | |
end | |
end | |
ExpressionTree = [:add, [:variable, :a], [:multiply, [:number, 2], [:variable, :b]]] | |
Env = { a: 3, b: 4, c: 5 } | |
puts evaluate(Env, ExpressionTree) |
Number = lambda { |env, num| num } | |
Variable = lambda { |env, var| env[var] } | |
Add = lambda { |env, a, b| evaluate(env, a) + evaluate(env, b) } | |
Multiply = lambda { |env, a, b| evaluate(env, a) * evaluate(env, b) } | |
def evaluate(env, exp) | |
op, *args = exp | |
op.(env, *args) | |
end | |
ExpressionTree = [Add, [Variable, :a], [Multiply, [Number, 2], [Variable, :b]]] | |
Env = { a: 3, b: 4, c: 5 } | |
puts evaluate(Env, ExpressionTree) |
abstract class Expression | |
case class Number(i: Int) extends Expression | |
case class Add(x: Expression, y: Expression) extends Expression | |
case class Multiply(x: Expression, y: Expression) extends Expression | |
case class Variable(id: Symbol) extends Expression | |
object Maths extends App { | |
val environment = Map('a -> 1, | |
'b -> 2, | |
'c -> 3) | |
def evaluate(env: Map[Symbol, Int], exp: Expression): Int = exp match { | |
case Number(n: Int) => n | |
case Add(x, y) => evaluate(env, x) + evaluate(env, y) | |
case Multiply(x, y) => evaluate(env, x) * evaluate(env, y) | |
case Variable(id: Symbol) => env(id) | |
} | |
val expressionTree1 = Add(Variable('a), Multiply(Number(2), Variable('b))) | |
println(evaluate(environment, expressionTree1)) | |
} |
import java.util.*; | |
public class Eval { | |
static int evaluate(Map env, Expression exp){ | |
if(exp instanceof Variable){ return (Integer)env.get(((Variable)exp).x); } | |
else if(exp instanceof Number){ return ((Number)exp).x; } | |
else if(exp instanceof Multiply){ return evaluate(env, ((Multiply)exp).x)*evaluate(env, ((Multiply)exp).y); } | |
else if(exp instanceof Add){ return evaluate(env, ((Add)exp).x)+evaluate(env, ((Add)exp).y); } | |
return 0; | |
} | |
public static void main(String[] args){ | |
Map env=new HashMap(); | |
env.put("a", 3); | |
env.put("b", 4); | |
env.put("c", 5); | |
Expression expressionTree=new Add(new Variable("a"), new Multiply(new Number(2), new Variable("b"))); | |
System.out.println(evaluate(env, expressionTree)); | |
} | |
} | |
abstract class Expression {} | |
class Number extends Expression{ | |
int x; | |
Number(int x){ this.x=x; } | |
} | |
class Add extends Expression{ | |
Expression x; Expression y; | |
Add(Expression x, Expression y){ this.x=x; this.y=y; } | |
} | |
class Multiply extends Add{ | |
Multiply(Expression x, Expression y){ super(x, y); } | |
} | |
class Variable extends Expression{ | |
String x; | |
Variable(String x){ this.x=x; } | |
} |
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);
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 ofmatch
(à la OCaml)