Language Compare F#, Ocaml, Scala, Clojure, Ruby and Haskell - Simple AST example

clojure-match.clj

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

clojure-protocol.clj

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

fsharp.ml

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

haskell-case.hs

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

haskell-constructor.hs

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

ocaml.ml

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

ruby-jimweirich.rb

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)

ruby2-jimweirich.rb

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)

scala.scala

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

ugly.java

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

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

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

...

3. 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);