(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; } | |
} |
This comment has been minimized.
This comment has been minimized.
A more idiomatic OCaml version :
OCaml code almost never annotates the types of parameters, and uses the |
This comment has been minimized.
This comment has been minimized.
And a shorter OCaml variant, which uses polymorphic variants :
This lets the type inference algorithm check whether the pattern-matched type is correct, instead of having the programmer write down the type specification. |
This comment has been minimized.
This comment has been minimized.
And a third OCaml version, inspired by a comment on the Reddit thread :
|
This comment has been minimized.
This comment has been minimized.
Basic Python implementation:
|
This comment has been minimized.
This comment has been minimized.
number, variable, add, multiply = "number", "variable", "add", "multiply" def evaluate(env, exp): eval_map = dict(number=lambda: x, expression_tree = [add, [variable, "a"], [multiply, [number, 2], [variable, "b"]]] print evaluate(env, expression_tree) |
This comment has been minimized.
This comment has been minimized.
Another Python approach
|
This comment has been minimized.
This comment has been minimized.
In Go package main import ( var env = make(map[string]int) type Expression interface { type Variable string type Number int type Add struct { type Multiply struct { func main() { |
This comment has been minimized.
This comment has been minimized.
Another Java version
|
This comment has been minimized.
This comment has been minimized.
A Perl 6 version:
Could pass the environment along with every call, like most other solutions, but it seemed more p6-ish to just define it as a contextual variable. |
This comment has been minimized.
This comment has been minimized.
my C++ version:
Also, the ruby version did not run. I had to change it into this:
|
This comment has been minimized.
This comment has been minimized.
In Haxe: enum Expression { Number(x:Int); Add(e1:Expression, e2:Expression); Multiply(e1:Expression, e2:Expression); Variable (x:String); } class Main { static function evaluate (env:Hash, e:Expression) return switch (e) { case Number(x): x; case Add(x,y): evaluate(env, x) + evaluate(env, y); case Multiply(x,y): evaluate(env, x) * evaluate(env, y); case Variable(x): if (env.exists(x)) env.get(x) else 0; } static function main () { var environment = new Hash(); environment.set("a", 3); environment.set("b", 4); environment.set("c", 7); var expressionTree = Add(Variable("a"), Multiply(Number(2),Variable("b"))); var result = evaluate(environment, expressionTree); } } |
This comment has been minimized.
This comment has been minimized.
Minimal python implementation:
|
This comment has been minimized.
This comment has been minimized.
Go OO-version: package main
import "fmt"
type Env map[string]int
type Exp interface {Eval(Env) int}
type Var string
func (v Var) Eval(e Env) int {return e[string(v)]}
type Num int
func (n Num) Eval(e Env) int {return int(n)}
type Add struct {a, b Exp}
func (ex Add) Eval(e Env) int {return ex.a.Eval(e) + ex.b.Eval(e)}
type Mul struct {a, b Exp}
func (ex Mul) Eval(e Env) int {return ex.a.Eval(e) * ex.b.Eval(e)}
func main() {
ast := Add{Var("a"), Mul{Num(2), Var("b")}}
fmt.Println(ast.Eval(Env{"a":3, "b":4, "c":5}))
} Go type matching version: package main
import "fmt"
type Add struct{a, b interface{}}
type Mul struct{a, b interface{}}
func eval(env map[string]int, e interface{}) int {
switch v := e.(type) {
case int: return v
case string: return env[v]
case Add: return eval(env, v.a) + eval(env, v.b)
case Mul: return eval(env, v.a) * eval(env, v.b)
}
return 0
}
func main() {
env := map[string]int{"a":3, "b":4, "c":5}
ast := Add{"a", Mul{2, "b"}}
fmt.Println(eval(env, ast))
} |
This comment has been minimized.
This comment has been minimized.
In Xtend: import java.util.Map import org.eclipse.xtext.xbase.lib.Pair class Eval { def static void main(String...args) { new Eval().run() } // run inside an instance instead of statically so we can operator overloading (and use extensions) def evaluate(Map env, Expression exp) { switch exp { Variable: (env.get(exp.name) as Integer).intValue Number: exp.value Multiply: evaluate(env, exp.x) * evaluate(env, exp.y) Add: evaluate(env, exp.x) + evaluate(env, exp.y) } } def operator_doubleArrow(String key, Integer value) { new Pair(key, value) } // for convenient map construction // for convenient AST construction: def $(String varName) { new Variable(varName) } def $(int value) { new Number(value) } def operator_plus(Expression left, Expression right) { new Add(left, right) } def operator_multiply(Expression left, Expression right) { new Multiply(left, right) } def run() { val env = newHashMap("a" => 3, "b" => 4, "c" => 5) val expressionTree = $('a') + $(2) * $('b') println(evaluate(env, expressionTree)) } } abstract class Expression {} @Data class Number extends Expression { @Property int value } @Data class Add extends Expression { @Property Expression x @Property Expression y } @Data class Multiply extends Add {} @Data class Variable extends Expression { @Property String name } |
This comment has been minimized.
This comment has been minimized.
Another Xtend version:
|
This comment has been minimized.
This comment has been minimized.
Simple conversion of the original into Common Lisp: (setq *environment* '(("a" . 3) ("b" . 4) ("c" . 5)))
(setq *expression-tree* '(add (variable "a") (multiply (number 2) (variable "b"))))
(defun evaluate (env tree)
(let ((sym (car tree))
(x (cadr tree))
(y (caddr tree)))
(case sym
('number x)
('add (+ (evaluate env x) (evaluate env y)))
('multiply (* (evaluate env x) (evaluate env y)))
('variable (cdr (assoc x *environment* :test 'string=))))))
(setq result (evaluate *environment* *expression-tree*)) Suffers slightly from not having a simple destructuring bind, and could probably be macro'd shorter if anyone wants a try. |
This comment has been minimized.
This comment has been minimized.
Gah.. Was the poster of the C++ example above deliberately trying to make the language look bad!? I feel compelled to try to defend its reputation: #include <string>
#include <iostream>
#include <map>
#include <memory>
typedef std::map <std::string, int> Variables;
struct Expr
{
virtual ~Expr() {}
virtual int eval (Variables&) = 0;
};
struct Multiply : public Expr
{
std::unique_ptr<Expr> e1, e2;
Multiply (Expr* lhs, Expr* rhs) : e1 (lhs), e2 (rhs) {}
int eval (Variables& env) { return e1->eval (env) * e2->eval (env); }
};
struct Add : public Expr
{
std::unique_ptr<Expr> e1, e2;
Add (Expr* lhs, Expr* rhs) : e1 (lhs), e2 (rhs) {}
int eval (Variables& env) { return e1->eval (env) + e2->eval (env); }
};
struct Constant : public Expr
{
int value;
Constant (int val) : value (val) {}
int eval (Variables&) { return value; }
};
struct Variable : public Expr
{
std::string varName;
Variable (const std::string& name) : varName (name) {}
int eval (Variables& env) { return env [varName]; }
};
int main (int argc, char** argv)
{
Variables env;
env["a"] = 3;
env["b"] = 4;
env["c"] = 5;
Add tree (new Variable ("a"),
new Multiply (new Constant (2),
new Variable ("b")));
std::cout << tree.eval (env) << std::endl;
} |
This comment has been minimized.
This comment has been minimized.
Nemerle version: #pragma indent
using Nemerle.Extensions;
using System.Collections.Generic;
variant Ast
| Number { val : int }
| Add { left : Ast; right : Ast }
| Multiply { left : Ast; right : Ast }
| Variable { name : string }
def eval(env, expr)
match(expr)
| Ast.Number(val) => val
| Add(l, r) => eval(env, l) + eval(env, r)
| Multiply(l, r) => eval(env, l) * eval(env, r)
| Variable(name) => env[name]
def environment = Dictionary() <- ["a" = 3, "b" = 4, "c" = 5];
def expr = Ast.Add(Ast.Variable("a"), Ast.Multiply(Ast.Number(2), Ast.Variable("b")));
def result = eval(environment, expr); |
This comment has been minimized.
This comment has been minimized.
Java8
|
This comment has been minimized.
This comment has been minimized.
How about a compile time implementation with boost::mpl? It fails to compile if the asked for variable doesn't exist in the environment, my version of boost doesn't have the three argument boost::mpl::at<k,v,def> implemented.
|
This comment has been minimized.
This comment has been minimized.
WOW, why are these C++ solutions so bad:
|
This comment has been minimized.
This comment has been minimized.
A more elaborate Haskell version, removing some type restrictions (using GADTs). Note this contains some more types of Expression, and more demonstrations. It uses Monoid to handle lookup failures, similar to the original version, although I'd use some kind of error handling (Either?) myself. {-# LANGUAGE GeneralizedNewtypeDeriving, GADTs #-}
import Prelude hiding (lookup)
import qualified Prelude as P
import Data.Maybe (fromMaybe)
import Data.Monoid (Monoid, mempty, mappend)
data Expression a where
Constant :: a -> Expression a
Add :: Num a => Expression a -> Expression a -> Expression a
Multiply :: Num a => Expression a -> Expression a -> Expression a
Append :: Monoid a => Expression a -> Expression a -> Expression a
Variable :: Monoid a => String -> Expression a
evaluate :: (String -> Maybe a) -> Expression a -> a
evaluate _ (Constant a) = a
evaluate lookup (Add a b) = evaluate lookup a + evaluate lookup b
evaluate lookup (Multiply a b) = evaluate lookup a * evaluate lookup b
evaluate lookup (Append a b) = evaluate lookup a `mappend` evaluate lookup b
evaluate lookup (Variable name) = fromMaybe mempty (lookup name)
result1 :: (Num a, Monoid a) => a
result1 = evaluate lookup tree
where
lookup = flip P.lookup bindings
bindings = [("a", 3), ("b", 4), ("c", 7)]
tree = Add (Add (Variable "a") (Multiply (Constant 2) (Variable "b"))) (Variable "nada")
-- This makes use of the Monoid instance of [] for Variable and Append
result2 :: String
result2 = evaluate lookup tree
where
lookup = flip P.lookup bindings
bindings = [("name", "ast")]
tree = Append (Append (Variable "name") (Constant " ")) (Constant "test")
-- For result1, we need a type with Num and Monoid instances due to the
-- usage of Add, Multiply and Variable
newtype MyInt = MyInt Int
deriving (Show, Eq, Num)
-- Custom Monoid instance, similar to Sum
instance Monoid MyInt where
mempty = MyInt 0
mappend (MyInt a) (MyInt b) = MyInt $ a + b
data MyType = MyType
deriving (Show)
-- This example shows, despite using Expression and evaluate, we don't need
-- Monoid or Num instances, since all we use is Constant
result3 :: MyType
result3 = evaluate (const Nothing) (Constant MyType)
main :: IO ()
main = do
putStrLn $ "result1 = " ++ show (result1 :: MyInt)
putStrLn $ "result2 = " ++ result2
putStrLn $ "result3 = " ++ show result3
{-
- Output:
-
- result1 = MyInt 11
- result2 = ast test
- result3 = MyType
-} |
This comment has been minimized.
This comment has been minimized.
%in prolog eval(number(X), X).
eval(add(X,Y), Val) :-
eval(X, Xval),
eval(Y, Yval),
Val is Xval+Yval.
eval(multiply(X,Y), Val) :-
eval(X, Xval),
eval(Y, Yval),
Val is Xval*Yval.
eval(variable(V), Val) :-
env(V, Val).
env(a, 3).
env(b, 4).
env(c, 5).
test_expression(
add(variable(a), multiply(number(2), variable(b)))
).
result(ValueOut) :-
test_expression(Expr),
eval(Expr, ValueOut). |
This comment has been minimized.
This comment has been minimized.
Ruby variant which is fairly concise:
|
This comment has been minimized.
This comment has been minimized.
Also a Python version:
/jab |
This comment has been minimized.
This comment has been minimized.
In the Nu programming language (LISP/Ruby on top of Objective-C): (load "Nu:match")
(function evaluate (env exp)
(match exp
(('Number x ) x)
(('Add x y) (+ (evaluate env x) (evaluate env y)))
(('Multiply x y) (* (evaluate env x) (evaluate env y)))
(('Variable x ) (env x))))
(set environment (dict "a" 3 "b" 4 "c" 5))
(set expression-tree '(Add (Variable "a") (Multiply (Number 2) (Variable "b"))))
(set result (evaluate environment expression-tree)) |
This comment has been minimized.
This comment has been minimized.
Terrible Java code above. Use inheritance, but then butcher it in the evaluate method.
|
This comment has been minimized.
This comment has been minimized.
A mixed Xtend/Java version: Java: public interface Expr { int eval(Map env); } Xtend: class Eval { def static void main(String...args) { new Eval().run() } // run inside an instance instead of statically so we can operator overloading (and use extensions) // for convenient AST construction: def Expr $(String varName) { [ get(varName) ] } def Expr $(int value) { [ value ] } def Expr operator_plus(Expr left, Expr right) { [ left.eval(it) + right.eval(it) ] } def Expr operator_multiply(Expr left, Expr right) { [ left.eval(it) * right.eval(it) ] } def run() { println( ( $('a') + $(2) * $('b') ).eval( newHashMap("a" -> 3, "b" -> 4, "c" -> 5) ) ) } } The mixing is required because Xtend doesn't do interfaces (inner or no). This version is inspired by the Java8 example but also philosophically quite close to the Haskell-/FP-type solutions. |
This comment has been minimized.
This comment has been minimized.
Lua: local gm, sm = getmetatable, setmetatable
local new_exprt = function()
return sm({}, { __call = function(et, ...) return sm({ ... }, et) end })
end
local Num, Add, Mul, Var = new_exprt(), new_exprt(), new_exprt(), new_exprt()
local eval
eval = function(env, exp)
if gm(exp) == Num then return exp[1]
elseif gm(exp) == Add then return eval(env, exp[1]) + eval(env, exp[2])
elseif gm(exp) == Mul then return eval(env, exp[1]) * eval(env, exp[2])
elseif gm(exp) == Var then return env[exp[1]] end
end
local env = { a = 1, b = 2, c = 3 }
local expr_tree = Add(Var("a"), Mul(Num(2), Var("b")))
print(eval(env, expr_tree)) |
This comment has been minimized.
This comment has been minimized.
How about some smaller java code: import java.util.HashMap;
import java.util.Map;
public abstract class Eval<P> {
abstract int get(P... params);
static Eval<Integer> ADD = new Eval<Integer>() {
@Override
public int get(Integer... params) {
return params[0] + params[1];
};
};
static Eval<Integer> MULTIPLY = new Eval<Integer>() {
@Override
public int get(Integer... params) {
return params[0] * params[1];
}
};
static Map<String, Integer> variables = new HashMap<String, Integer>();
static Eval<String> VARIABLE = new Eval<String>() {
@Override
public int get(String... params) {
return variables.get(params[0]);
};
};
public static void main(String[] args) {
variables.put("a", 3);
variables.put("b", 4);
variables.put("c", 5);
int result = ADD.get(VARIABLE.get("a"),
MULTIPLY.get(2, VARIABLE.get("b")));
System.out.println("Result: " + result);
}
} |
This comment has been minimized.
This comment has been minimized.
Racket: (I took some artistic license with how the "ast" is expressed) #lang racket
(define (evaluate env exp)
(match exp
[(? number? x) x ]
[`(+ ,x ,y) (+ (evaluate env x) (evaluate env y))]
[`(* ,x ,y) (* (evaluate env x) (evaluate env y))]
[(? symbol? v) (hash-ref env v) ]))
(define environment (hash 'a 3 'b 4 'c 5))
(define expression-tree '(+ a (* 2 b)))
(define result (evaluate environment expression-tree)) |
This comment has been minimized.
This comment has been minimized.
Racket, using structs instead of s-expressions #lang racket
(struct num (val))
(struct add (l r))
(struct mul (l r))
(struct id (sym))
(define (evaluate env exp)
(match exp
[(num x) x ]
[(add x y) (+ (evaluate env x) (evaluate env y))]
[(mul x y) (* (evaluate env x) (evaluate env y))]
[(id v) (hash-ref env v) ]))
(define environment (hash 'a 3 'b 4 'c 5))
(define expression-tree (add (id 'a) (mul (num 2) (id 'b))))
(define result (evaluate environment expression-tree)) |
This comment has been minimized.
This comment has been minimized.
And finally, Typed Racket using structs #lang typed/racket
(struct: num ([val : Number]))
(struct: add ([l : AST] [r : AST]))
(struct: mul ([l : AST] [r : AST]))
(struct: id ([sym : Symbol]))
(define-type AST (U num add mul id))
(define-type Env (HashTable Symbol Number))
(: evaluate (Env AST -> Number))
(define (evaluate env exp)
(match exp
[(num x) x ]
[(add x y) (+ (evaluate env x) (evaluate env y))]
[(mul x y) (* (evaluate env x) (evaluate env y))]
[(id v) (hash-ref env v) ]))
(: environment Env)
(define environment (make-hash '((a . 3) (b . 4) (c . 5))))
(: expression-tree AST)
(define expression-tree (add (id 'a) (mul (num 2) (id 'b))))
(: result Number)
(define result (evaluate environment expression-tree)) |
This comment has been minimized.
This comment has been minimized.
Added a divide object and made add/multiply take variable numbers of args.
|
This comment has been minimized.
This comment has been minimized.
and brainfuck? |
This comment has been minimized.
This comment has been minimized.
Tagless, Monadic, Inferred Haskell.
|
This comment has been minimized.
This comment has been minimized.
Copied from: http://www.reddit.com/r/programming/comments/zbc4e/interesting_language_comparison_building_a_simple/c638oro
|
This comment has been minimized.
This comment has been minimized.
Emacs Lisp:
|
This comment has been minimized.
This comment has been minimized.
I had to replace |
This comment has been minimized.
This comment has been minimized.
Erlang: -module(ast).
-export([start/0]).
eval({number, N}, _) -> N;
eval({add, L, R}, Env) -> eval(L, Env) + eval(R, Env);
eval({mul, L, R}, Env) -> eval(L, Env) * eval(R, Env);
eval({variable, Id}, Env) -> dict:fetch(Id, Env).
start() ->
Env = dict:from_list([{a, 1}, {b, 2}, {c, 3}]),
Tree = {add, {variable, a}, {mul, {number, 2}, {variable, b}}},
Result = eval(Tree, Env),
io:format("result: ~p~n", [Result]). |
This comment has been minimized.
This comment has been minimized.
A version in the D language: [code] alias int[string] env; auto number = (int i) => (env x) => i; void main() { |
This comment has been minimized.
This comment has been minimized.
Since we're all joining in: a version in my own stack-based toy language, Déjà Vu:
|
This comment has been minimized.
This comment has been minimized.
Damn, you guys are C++ scrubs. Let the master show you how it's done.
|
This comment has been minimized.
This comment has been minimized.
Of course, I renamed the map from the sample I was originally shown, then didn't update the variables, making me look like a complete nubcake. And I didn't |
This comment has been minimized.
This comment has been minimized.
The K Semantic Framework:
Run it:
|
This comment has been minimized.
This comment has been minimized.
Objective-C version using blocks (closures): #import <Foundation/Foundation.h>
typedef int (^Expression)(NSDictionary *env);
Expression number(int x) {
return ^(NSDictionary *env) { return x;};
}
Expression add(Expression x, Expression y) {
return ^(NSDictionary *env) { return x(env) + y(env);};
}
Expression multiply(Expression x, Expression y) {
return ^(NSDictionary *env) { return x(env) * y(env);};
}
Expression variable(NSString *x) {
return ^(NSDictionary *env) { return [[env objectForKey:x] intValue];};
}
int main(int argc, const char * argv[])
{
@autoreleasepool {
NSDictionary *environment = @{@"a" : @3, @"b" : @4, @"c" : @5};
Expression expressionTree = add(variable(@"a"), multiply(number(2), variable(@"b")));
NSLog(@"%d", expressionTree(environment));
}
return 0;
} |
This comment has been minimized.
This comment has been minimized.
More idiomatic Objective-C, using umbrella class instead of blocks: #import <Foundation/Foundation.h>
@interface Expression : NSObject
+ (Expression *)number:(int)x;
+ (Expression *)add:(Expression *)x to:(Expression *)y;
+ (Expression *)multiply:(Expression *)x with:(Expression *)y;
+ (Expression *)variable:(NSString *)x;
- (int)eval:(NSDictionary *)env;
@end
@interface Number : Expression
@property int x;
@end
@interface Add : Expression
@property Expression *x;
@property Expression *y;
@end
@interface Multiply : Expression
@property Expression *x;
@property Expression *y;
@end
@interface Variable : Expression
@property NSString *x;
@end
@implementation Expression
+ (Expression *)number:(int)x {
Number *obj = [Number new];
obj.x = x;
return obj;
}
+ (Expression *)add:(Expression *)x to:(Expression *)y {
Add *obj = [Add new];
obj.x = x; obj.y = y;
return obj;
}
+ (Expression *)multiply:(Expression *)x with:(Expression *)y {
Multiply *obj = [Multiply new];
obj.x = x; obj.y = y;
return obj;
}
+ (Expression *)variable:(NSString *)x {
Variable *obj = [Variable new];
obj.x = x;
return obj;
}
- (int)eval:(NSDictionary *)env {
NSAssert(NO, @"Abstract class", nil);
return -1;
}
@end
@implementation Number
- (int)eval:(NSDictionary *)env {
return self.x;
}
@end
@implementation Add
- (int)eval:(NSDictionary *)env {
return [_x eval:env] + [_y eval:env];
}
@end
@implementation Multiply
- (int)eval:(NSDictionary *)env {
return [_x eval:env] * [_y eval:env];
}
@end
@implementation Variable
- (int)eval:(NSDictionary *)env {
return [[env objectForKey:_x] intValue];
}
@end
int main(int argc, const char * argv[])
{
@autoreleasepool {
NSDictionary *environment = @{@"a" : @3, @"b" : @4, @"c" : @5};
Expression *expressionTree =
[Expression add:[Expression variable:@"a"]
to:[Expression multiply:[Expression number:2]
with: [Expression variable:@"b"]]];
NSLog(@"%d", [expressionTree eval:environment]);
}
return 0;
} |
This comment has been minimized.
This comment has been minimized.
In Visual Basic
|
This comment has been minimized.
This comment has been minimized.
@julianstorer, so you have just removed a few newlines and use unique_ptr. I'd say the code still is awful, it is conceptionally exactly the same. Also you are not const correct any more. |
This comment has been minimized.
This comment has been minimized.
In C++11, with std::function to do the type erasure
# include
# include
# include
# include
|
This comment has been minimized.
This comment has been minimized.
I'm sorry for prev comment, it's not formated. C++11 with std::function to do type erasure.
|
This comment has been minimized.
This comment has been minimized.
Maybe a little late to the party, but here's a Javascript version:
|
This comment has been minimized.
This comment has been minimized.
pew pew
|
This comment has been minimized.
This comment has been minimized.
Groovy Version enum Special { Add, Variable, Multiply, Numb }
import static Special.*
def evaluate(env,tree){
def ( kword, x ,y ) = tree
switch (kword){
case Numb: x ;break;
case Add: evaluate(env, x) + evaluate(env, y);break;
case Multiply: evaluate(env, x) * evaluate(env, y);break;
case Variable: env[x];break;
}
}
def environment =[a:3, b:4, c: 5]
def expressionTree =[Add ,[Variable ,'a'] ,[Multiply , [Numb, 2], [Variable, 'b']]]
assert evaluate(environment,expressionTree) == 11 |
This comment has been minimized.
This comment has been minimized.
C++11 and C (even macros !) mix FTW ! #include <unordered_map>
#include <string>
#include <functional>
#include <iostream>
#include <cstdlib> // sue me
int main(int argc, char* argv[]){
std::unordered_map<std::string, int> vars{{"a", 1},{"b",2},{"c",3}};
#define OP(c) { #c[0] , [](int o1, int o2){ return o1 c o2 ; } }
std::unordered_map<char, std::function<int(int,int)> >
ops {OP(+), OP(-), OP(*), OP(/)};
#undef OP
std::cout<< ops['+'](vars["a"], ops['*'](std::atoi("2") , vars["b"])) <<std::endl;
} |
This comment has been minimized.
This comment has been minimized.
Nemerle (using quasiquotation) using Nemerle.Collections;
using Nemerle.Compiler;
using System.Console;
class CompilerHost : ManagerClass
{
public this()
{
base(CompilationOptions());
InitCompiler();
LoadExternalLibraries();
}
}
module Program
{
Main() : void
{
def _compiler = CompilerHost();
def env = Hashtable([("a", 3), ("b", 4), ("c", 5)]);
def expressionTree = <[ a + 2 * b]>;
def eval(expr)
{
| <[ $x + $y ]> => eval(x) + eval(y)
| <[ $x * $y ]> => eval(x) * eval(y)
| <[ $(x : int) ]> => x
| <[ $x ]> => env[x.ToString()]
}
WriteLine(eval(expressionTree));
}
} |
This comment has been minimized.
This comment has been minimized.
Using Attribute Grammars we can write in in a compositional way. Of course a more concise version is possible, but this way the code is nicely split up into separate aspects. Syntax is that of UUAGC, a preprocessor for Haskell. imports
{
import Data.Map
}
-- Constants and addition
data Expression
| Number n :: Integer
| Add l, r :: Expression
attr Expression
syn eval :: Integer
sem Expression
| Number lhs.eval = @n
| Add lhs.eval = @l.eval + @r.eval
-- Add multiplication
data Expression
| Multiply l, r :: Expression
sem Expression
| Multiply lhs.eval = @l.eval * @r.eval
-- Add variables and environment
data Expression
| Variable var :: String
{type Env = Map String Integer}
attr Expression
inh env :: Env
sem Expression
| Variable lhs.eval = findWithDefault 0 @var @lhs.env
-- Testing code
{
environment :: Env
environment = fromList [("a",3), ("b",4), ("c",7)]
expressionTree :: Expression
expressionTree = Add (Variable "a") (Multiply (Number 2) (Variable "b"))
-- General interface to get the "eval" attribute from the expression,
-- given the "env" inherited attribute
result :: Integer
result = eval_Syn_Expression $ wrap_Expression (sem_Expression expressionTree)
$ Inh_Expression { env_Inh_Expression = environment }
-- Simple interface, since there is only 1 inherited and only 1 synthesized attribute
result2 :: Integer
result2 = sem_Expression expressionTree environment
} |
This comment has been minimized.
This comment has been minimized.
using overloading of numeric operators and strings in Haskell we get: import Data.String
import Data.Maybe
import Control.Monad
type Expr = ([(String, Integer)] -> Integer)
instance Num Expr where
(+) = liftM2 (+)
(*) = liftM2 (*)
fromInteger = const
instance IsString Expr where
fromString x = fromJust . lookup x
main = print $ ("a" + 2 * "b" :: Expr)
[("a",3), ("b",4), ("c",7)] |
This comment has been minimized.
This comment has been minimized.
Using AspectAG, a Haskell library of strongly typed Attribute Grammars. -- In this example implementation we have placed all different aspects
-- in a single file.
-- Notice however that the code for e.g. the addition, the multiplication
-- and the variable case could have been distributed over three different
-- files which can be compiled separately
{-# OPTIONS -fcontext-stack=100 #-}
{-# LANGUAGE TemplateHaskell, EmptyDataDecls, NoMonomorphismRestriction #-}
module Expr where
import Language.Grammars.AspectAG
import Language.Grammars.AspectAG.Derive
import Data.HList.Label4
import Data.HList.TypeEqGeneric1
import Data.HList.TypeCastGeneric1
import Control.Applicative
import Data.Map
-- ---------------------------------------------------------------------------------------
-- We start by defining what should happen for Constants and Addition
-- ---------------------------------------------------------------------------------------
data Expression
= Number {n :: Integer}
| Add {l,r :: Expression}
$(deriveAG ''Expression)
$(attLabels ["eval"])
evalNT = nt_Expression .*. hNil -- the attribute which carries the result of the evaluation is introduced for the Expression non-terminal
evalNumber = syn eval $ at ch_n
evalAdd = syn eval $ (+) <$> ch_l `attr` eval <*> ch_r `attr` eval
-- ---------------------------------------------------------------------------------------
-- We extend the data type at hand and add multiplication
-- ---------------------------------------------------------------------------------------
data EXT_Expression
= Multiply {ml, mr :: Expression}
$(extendAG ''EXT_Expression [''Expression])
evalMultiply = syn eval $ (*) <$> ch_ml `attr` eval <*> ch_mr `attr` eval
-- ---------------------------------------------------------------------------------------
-- Finally we extend the system once more to be able to deal with variables,
-- add the needed environment attribute.
-- Note that none of the above code had to be adapted
-- ---------------------------------------------------------------------------------------
data EXT2_Expression
= Variable {var :: String}
$(extendAG ''EXT2_Expression [ ])
type Env = Map String Integer
$(attLabels ["env"])
envNT = nt_Expression .*. hNil -- the list of non-terminals which carry an env attribute
envRule = copy env envNT -- copy rule, makes that the environment is automatically copied to the children
evalVariable = syn eval $ (findWithDefault 0) <$> at ch_var <*> lhs `attr` env
-- ---------------------------------------------------------------------------------------
-- In the main module we combine the grammar fragments defined above,
-- and construct the semantic functions by combining the attribute definitions
-- ---------------------------------------------------------------------------------------
sem_Number = semP_Number evalNumber -- the semP functions know about the children of the production
sem_Add = semP_Add (envRule `ext` evalAdd)
sem_Multiply = semP_Multiply (envRule `ext` evalMultiply)
sem_Variable = semP_Variable evalVariable
-- Testing code
environment :: Env
environment = fromList [("a",3), ("b",4), ("c",7)]
expressionTree = sem_Add (sem_Variable $ sem_Lit "a") (sem_Multiply (sem_Number $ sem_Lit 2) (sem_Variable $ sem_Lit "b"))
result :: Integer
result = expressionTree (env .=. environment .*. emptyRecord) # eval |
This comment has been minimized.
This comment has been minimized.
A JavaScript version that uses prototype-based method dispatch: function Var(x) { this.x = x; }
function Plus(x,y) { this.x = x; this.y = y; }
function Times(x,y) { this.x = x; this.y = y; }
function Const(k) { this.k = k; }
Var.prototype.eval = function(env) { return env[this.x]; }
Plus.prototype.eval = function(env) { return this.x.eval(env) + this.y.eval(env); }
Times.prototype.eval = function(env) { return this.x.eval(env) * this.y.eval(env); }
Const.prototype.eval = function(env) { return this.k; }
var environment = { a:3, b:5, c:5 };
var expression = new Plus(new Var("a"),new Times(new Const(2),new Var("b")));
console.log(expression.eval(environment)); |
This comment has been minimized.
This comment has been minimized.
Clojure With Multimethods (defmulti evaluate (fn [_ [sym _ _]] sym))
(defmethod evaluate 'Number [_ [_ x _]] x)
(defmethod evaluate 'Add [env [_ x y]] (+ (evaluate env x) (evaluate env y)))
(defmethod evaluate 'Multiply [env [_ x y]] (* (evaluate env x) (evaluate env y)))
(defmethod evaluate 'Variable [env [_ x _]] (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))
|
This comment has been minimized.
This comment has been minimized.
Elixir version :) The same as the erlang version, only using defmodule Ast do
def eval(tree, env) do
case tree do
{:number, n} -> n
{:add, l, r} -> eval(l, env) + eval(r, env)
{:mul, l, r} -> eval(l, env) * eval(r, env)
{:variable, id} -> Dict.get(env, id)
end
end
def start do
env = HashDict.new [a: 1, b: 2, c: 3]
tree = {:add, {:variable, :a}, {:mul, {:number, 2}, {:variable, :b}}}
IO.puts Ast.eval(tree, env)
end
end
Ast.start |
This comment has been minimized.
This comment has been minimized.
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) |
This comment has been minimized.
This comment has been minimized.
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); |
This comment has been minimized.
This comment has been minimized.
quick & dirt PHP <?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); |
This comment has been minimized.
This comment has been minimized.
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. |
This comment has been minimized.
This comment has been minimized.
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 |
This comment has been minimized.
This comment has been minimized.
// 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();
}
}
|
This comment has been minimized.
This comment has been minimized.
// 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();
}
}
|
This comment has been minimized.
This comment has been minimized.
// 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();
}
}
|
This comment has been minimized.
This comment has been minimized.
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) |
This comment has been minimized.
This comment has been minimized.
A bit more idiomatic C#
|
This comment has been minimized.
This comment has been minimized.
Using Star:
|
This comment has been minimized.
This comment has been minimized.
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() |
This comment has been minimized.
This comment has been minimized.
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 }) |
This comment has been minimized.
This comment has been minimized.
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}))
} |
This comment has been minimized.
This comment has been minimized.
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}) |
This comment has been minimized.
This comment has been minimized.
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))))) |
This comment has been minimized.
This comment has been minimized.
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 } }
}] |
This comment has been minimized.
This comment has been minimized.
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) |
This comment has been minimized.
This comment has been minimized.
Back to Ocaml, to show a comparison between OOP and FP So the objective is writing some code so that the following lines will do their job : 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 So, now with the actual solution. I have decided to keep it more generalised with polymorphic expressions
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
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
...
We will be using the famous Ocaml Modules and explicit signatures to do so 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 : 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 |
This comment has been minimized.
This comment has been minimized.
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)) |
This comment has been minimized.
This comment has been minimized.
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. |
This comment has been minimized.
This comment has been minimized.
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)) |
This comment has been minimized.
This comment has been minimized.
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 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 |
This comment has been minimized.
This comment has been minimized.
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. |
This comment has been minimized.
This comment has been minimized.
FSharp implementation is still the clearest one, Crystal anyone ? |
This comment has been minimized.
This comment has been minimized.
Funny nobody has mentioned this - but the extension should be |
This comment has been minimized.
This comment has been minimized.
in my own fantasy language :
|
This comment has been minimized.
This comment has been minimized.
//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); |
This comment has been minimized.
In Rust: