-
-
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; } | |
} |
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
)
- FP classical and elegant Ocaml :
type 'a expr =
| Number of 'a | Variable of string
| Node of 'a expr * ('a -> 'a -> 'a) * 'a expr
let eval env =
let rec go = function (*auxiliary 'go' function to avoid having to pass the 'env' argument*)
| Number n -> n | Variable v -> env v
| Node(e1,op,e2) -> op (go e1) (go e2) in go
let mk_op op = fun e1 e2 -> Node(e1,op,e2)
let (|+|) = mk_op (+) and (|+.|) = mk_op (+.)
and (|*|) = mk_op ( * ) and (|*.|) = mk_op ( *.)
let expr = (Variable "a") |+| ((Number 2) |*| (Variable "b"))
let env = function "a" -> 3 | "b" -> 4 | "c" -> 7
| c -> failwith ("Unbound variable " ^ c)
let result = eval env expr
- Object-Oriented Version
2.1) with an Interface : type definition and type force cast
type 'a expr = < eval : (string -> 'a) -> 'a > (* Interface : object with method 'eval' *)
let number x : 'a expr = object method eval _ = x end (* Placeholder : no need to bind the input arg *)
and variable c : 'a expr = object method eval env = env c end
let mk_op op = fun e1 e2 ->
object method eval env = op (e1#eval env) (e2#eval env) end
let (|+|) = mk_op (+) and (|+.|) = mk_op (+.)
and (|*|) = mk_op ( * ) and (|*.|) = mk_op ( *.)
let expr = (variable "a") |+| ((number 2) |*| (variable "b"))
let env = function "a" -> 3 | "b" -> 4 | "c" -> 7
| c -> failwith ("Unbound variable " ^ c)
let result = expr#eval env
2.2) with an abstract class : object inheritance
class virtual ['a] expr = object method virtual eval : (string -> 'a) -> 'a end
let number (x : 'a) = object inherit ['a] expr method eval _ = x end
and variable c = object inherit ['a] expr method eval env = env c end
...
- Ok, now that we got the main idea, let's work the abstraction
(why? for instance, in the second example, any object with a "valid"eval
method would be implementing the'a expr
interface, which could be dangerous)
We will be using the famous Ocaml Modules and explicit signatures to do so
(A module type (kind of a module interface) is defined so that any module forced to that type therefore has to satisfy its abstracted signature)
module type AST_type = sig
(* some unspecified type 'a expr => Abstract type *)
type 'a expr
val eval : (string -> 'a) -> 'a expr -> 'a
(* we need expr makers now that the expr type is abstract *)
val number : 'a -> 'a expr
val variable : string -> 'a expr
val mk_op : ('a ->'a ->'a) -> 'a expr -> 'a expr -> 'a expr
val (|+|) : int expr -> int expr -> int expr
val (|+.|) : float expr -> float expr -> float expr
val (|*|) : int expr -> int expr -> int expr
val (|*.|) : float expr -> float expr -> float expr
end
So our two previous examples are two implementations of that signature :
(Forced by the initial module type cast : AST_type
)
module AST_Object : AST_type = struct
type 'a expr = < eval : (string -> 'a) -> 'a >
let eval env e = e#eval env (* Dummy definition to match the signature and stay in the abstraction *)
let number x : 'a expr = object method eval _ = x end
and variable c : 'a expr = object method eval env = env c end
let mk_op op = fun e1 e2 ->
object method eval env = op (e1#eval env) (e2#eval env) end
let (|+|) = mk_op (+) and (|+.|) = mk_op (+.)
and (|*|) = mk_op ( * ) and (|*.|) = mk_op ( *.)
end
module AST_Functional : AST_type = struct
type 'a expr =
| Number of 'a | Variable of string
| Node of 'a expr * ('a -> 'a -> 'a) * 'a expr
let variable s = Variable s and number x = Number x (* Same here *)
let eval env =
let rec go = function
| Number n -> n | Variable v -> env v
| Node(e1,op,e2) -> op (go e1) (go e2) in go
let mk_op op = fun e1 e2 -> Node(e1,op,e2)
let (|+|) = mk_op (+) and (|+.|) = mk_op (+.)
and (|*|) = mk_op ( * ) and (|*.|) = mk_op ( *.)
end
And finally we choose our desired implementation (e.g. AST_Object) and use it :
open AST_Object (* or 'open AST_Functional' *)
let expr = (variable "a") |+.| ((number 2.) |*.| (variable "b"))
let env = function "a" -> 3. | "b" -> 4. | "c" -> 7.
| c -> failwith ("Unbound variable " ^ c)
let result = eval env expr
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);
Tcl