-
-
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; } | |
} |
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
)
- 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);
Elixir version :)
The same as the erlang version, only using
case
pattern matching instead of pattern matching in the function declaration.