Skip to content

Instantly share code, notes, and snippets.

@ckirkendall
Forked from bkyrlach/Expression.fs
Created June 15, 2012 02:26
Show Gist options
  • Save ckirkendall/2934374 to your computer and use it in GitHub Desktop.
Save ckirkendall/2934374 to your computer and use it in GitHub Desktop.
Language Compare F#, Ocaml, Scala, Clojure, Ruby and Haskell - Simple AST example
(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; }
}
@chrisdavies
Copy link

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 } }));
    }
}

Copy link

ghost commented Feb 9, 2014

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}))");
  }
}

@slimane
Copy link

slimane commented Mar 7, 2014

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()

@gmarik
Copy link

gmarik commented Apr 13, 2014

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 })

@gmarik
Copy link

gmarik commented Apr 13, 2014

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}))
}

@gmarik
Copy link

gmarik commented Apr 13, 2014

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})

@gmarik
Copy link

gmarik commented Apr 13, 2014

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)))))

@dbohdan
Copy link

dbohdan commented Jun 10, 2015

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 } }
}]

@comfly
Copy link

comfly commented Aug 1, 2015

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)

@danielhenrymantilla
Copy link

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)

  1. 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
  1. 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

...
  1. 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

@cljfun
Copy link

cljfun commented Oct 19, 2015

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))

@alecroy
Copy link

alecroy commented Feb 12, 2016

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.

Copy link

ghost commented May 4, 2016

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))

@royalstream
Copy link

royalstream commented May 4, 2016

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  

@jdh30
Copy link

jdh30 commented Apr 4, 2017

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.

@thetrung
Copy link

FSharp implementation is still the clearest one,
while 1st Ruby & JS implementation are my favorite !

Crystal anyone ?

@paytonrules
Copy link

Funny nobody has mentioned this - but the extension should be fsharp.fs not ml. Gonna guess you did the OCaml one first?

@thetrung
Copy link

thetrung commented Nov 2, 2020

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

@kapitancho
Copy link

//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);

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment