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

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

Elixir version :)

The same as the erlang version, only using case pattern matching instead of pattern matching in the function declaration.

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

clojure with eval

(defn evaluate [tree env] 
  (eval (clojure.walk/prewalk-replace
          {'add +, 'multiply *, 'number identity, 'variable env} tree)))

(def environment {:a 3, :b 4, :c 5})

(def expression-tree '(add (variable :a) (multiply (number 2) (variable :b))))

(evaluate expression-tree environment)

Another javascript...

var Number = function(n) { return function(env) { return n }};
var Add = function(e1, e2) { return function(env) { return e1(env) + e2(env) }};
var Variable = function(s) { return function(env) { return env[s] }};
var Multiply = function(e1, e2) { return function(env) { return e1(env) * e2(env) }};
var env = {a: 3, b: 4};
var result = Add(Variable("a"), Multiply(Number(2), Variable("b")))(env);

quick & dirt PHP
LOL

<?php

function evaluate($env, $expr) {
    list($e, $v) = each($expr); 

    switch(strtolower($e)) {
        case "add":
            return evaluate($env, array_slice($v,0, 1)) + evaluate($env, array_slice($v, 1, 1));
        break;
        case "multiply":
            return evaluate($env, array_slice($v,0, 1)) * evaluate($env, array_slice($v, 1, 1));
        break;
        case "variable":
            return $env[$v];
        break;
        case "number":
            return $v;
        break;
    }
}

$environment = array("a" => 3, "b" => 4, "c" => 7);

$expression_tree = array(
   "add" => array(
       "variable" => "a",
       "multiply" => array(
           "number" => 2,
           "variable" => "b"
       )
    )
);

// OR

function number($n) {
    return function($env) use ($n) {
        return $n;
    };
}
function variable($a) {
    return function($env) use ($a) {
        return $env[$a];
    };
}
function add($a, $b) {
    return function($env) use ($a, $b) {
        return $a($env) + $b($env);
    };
}
function mul($a, $b) {
    return function($env) use ($a, $b) {
        return $a($env) * $b($env);
    };
}

function evaluate2($env, $tree) {
    return $tree($env);
}

$tree = add(variable("a"), mul(number(2), variable("b")));


$result = evaluate($environment, $expression_tree);
$result2 = evaluate2($environment, $tree);

Slight nitpick, but in the scala and F# versions, the definition of environment is needlessly broken into 3 lines, while in other languages it is done in one line. That artificially inflates the number of lines. The F# version also includes comments while none of the others do. You should be consistent for more direct comparison.

Common Lisp with eval

(setf (symbol-function 'add) #'+
      (symbol-function 'multiply) #'*
      (symbol-function 'number) #'identity)

(defmacro variable (var)
  (intern var))

(defun evaluate (expr env)
  (eval `(let ,(mapcar (lambda (a) (cons (intern (car a)) (cdr a))) env)
           ,expr)))

(evaluate '(Add (Variable "a") (Multiply (Number 2) (Variable "b")))
                   '(("a" 3) ("b" 4) ("c" 5)))
=> 11

// c#, object-oriented

interface Expression { int Eval(Environment environment); }

sealed class Environment : System.Collections.Generic.Dictionary<string, int> { }

static class Expressions
{
    sealed class ConstantExpression : Expression
    {
        private readonly int _value;
        public ConstantExpression(int value) { _value = value; }
        public int Eval(Environment environment) { return _value; }
    }

    sealed class AdditionExpression : Expression
    {
        private readonly Expression _left;
        private readonly Expression _right;
        public AdditionExpression(Expression left, Expression right) { _left = left; _right = right; }
        public int Eval(Environment environment) { return _left.Eval(environment) + _right.Eval(environment); }
    }

    sealed class MultiplicationExpression : Expression
    {
        private readonly Expression _left;
        private readonly Expression _right;
        public MultiplicationExpression(Expression left, Expression right) { _left = left; _right = right; }
        public int Eval(Environment environment) { return _left.Eval(environment) * _right.Eval(environment); }
    }

    sealed class VariableExpression : Expression
    {
        private readonly string _symbol;
        public VariableExpression(string symbol) { _symbol = symbol; }
        public int Eval(Environment environment) { return environment[_symbol]; }
    }

    public static Expression Add(Expression left, Expression right) { return new AdditionExpression(left,right); }
    public static Expression Multiply(Expression left, Expression right) { return new MultiplicationExpression(left,right); }
    public static Expression Variable(string symbol) { return new VariableExpression(symbol); }
    public static Expression Number(int value) { return new ConstantExpression(value); }
}


class Program
{
    private static void Main(string[] args)
    {
        var environment = new Environment {{"a", 3}, {"b", 4}, {"c", 5}};
        var expressionTree = Expressions.Add(Expressions.Variable("a"), Expressions.Multiply(Expressions.Number(2), Expressions.Variable("b")));
        System.Console.WriteLine(expressionTree.Eval(environment));
        System.Console.ReadLine();
    }
}

// c#, functional (concise)


using System;

sealed class Environment : System.Collections.Generic.Dictionary<string, int> { }

delegate int Expression(Environment environment);

class Program
{
    private static void Main(string[] args)
    {
        Func<int, Expression>                    number   = value         =>  env => value;
        Func<Expression, Expression, Expression> add      = (left, right) =>  env => left(env) + right(env);
        Func<Expression, Expression, Expression> multiply = (left, right) =>  env => left(env) * right(env);
        Func<string, Expression>                 variable = symbol        =>  env => env[symbol];

        var environment = new Environment {{"a", 3}, {"b", 4}, {"c", 5}};
        var expressionTree = add(variable("a"), multiply(number(2), variable("b")));
        Console.WriteLine(expressionTree(environment));
        Console.ReadLine();
    }
}

// c#, runtime code generation using the LINQ expression library


using System;
using System.Linq.Expressions;

sealed class Environment : System.Collections.Generic.Dictionary<string, int> { }

class Program
{
    private static void Main(string[] args)
    {
        var environment = new Environment { { "a", 3 }, { "b", 4 }, { "c", 5 } };
        Expression<Func<Environment, int>> expression = env => env["a"] + (2*env["b"]);
        Console.WriteLine(expression.Compile()(environment));
        Console.ReadLine();
    }
}




// the expression: Expression<Func<Environment, int>> expression = env => env["a"] + (2*env["b"]);
// is only compiled at run time. 
// The c# compiler only translates the expression into an expression tree data structure.
// If this feels like cheating (it isn't), this is the de-sugared full equivalent:


using System.Linq.Expressions;

sealed class Environment : System.Collections.Generic.Dictionary<string, int> { }

class Program
{
    private static void Main(string[] args)
    {
        var environment = new Environment { { "a", 3 }, { "b", 4 }, { "c", 5 } };

        var parameter = Expression.Parameter(typeof (Environment));
        var expression =
            Expression.Lambda<System.Func<Environment, int>>(
                Expression.Add(
                    Expression.Call(parameter, "get_Item", null, Expression.Constant("a")),
                    Expression.Multiply(
                        Expression.Constant(2),
                        Expression.Call(parameter, "get_Item", null, Expression.Constant("b"))
                        )
                    ), parameter
                );

        System.Console.WriteLine(expression.Compile()(environment));
        System.Console.ReadLine();
    }
}

Another Scala approach:

object ExprEval extends App {
  type Expr = Map[Symbol, Int] => Int

  def number    (value: Int): Expr        = env => value
  def variable  (sym: Symbol): Expr       = env => env(sym)
  def multiply  (a: Expr, b: Expr): Expr  = env => a(env) * b(env)
  def add       (a: Expr, b: Expr): Expr  = env => a(env) + b(env)

  val environment = Map('a -> 1, 'b -> 2, 'c -> 3)
  val expressionTree = add(variable('a), multiply(number(2), variable('b)))

  println(expressionTree(environment))
}

Also with scalaz and Reader Monad we can bind our symbols to real variables and then write whole equation inside yield like we would normally do using language constructs:

import scalaz._, Scalaz._

object ExprEval extends App {
  def variable(symbol: Symbol) = Reader((env: Map[Symbol, Int]) => env(symbol))

  val environment = Map('a -> 1, 'b -> 2, 'c -> 3)
  val expressionTree = for {
    a <- variable('a)
    b <- variable('b)
  } yield a + (2 * b)

  println(expressionTree(environment))
}

What is worth noting is that we are not limited to + and * operations, but we get all other language constructs for free:

val expressionTree = for { 
  a <- variable('a)
  b <- variable('b)
  c <- variable('c) 
} yield math.pow(a + (2 * b) % c * 0.4f, 2)

A bit more idiomatic C#

using System;

using Env = System.Collections.Generic.Dictionary<string, int>;

delegate int Expr(Env e);

public class Program
{
    public static void Main()
    {
        Func<string, Expr> Var = s => env => env[s];
        Func<int, Expr> Num = i => env => i;
        Func<Expr, Expr, Expr> Add = (x, y) => env => x(env) + y(env);
        Func<Expr, Expr, Expr> Mul = (x, y) => env => x(env) * y(env);

        var expr = Add(Var("a"), Mul(Num(2), Var("b")));

        Console.WriteLine(expr(new Env { { "a", 3 }, { "b", 4 }, { "c", 5 } }));
    }
}

Using Star:

package exp{
  type Exp is Var(string)
                or Num(integer)
                or Add(Exp,Exp)
                or Mul(Exp,Exp);
  Eval(Var(Nm),env) is env[Nm];
  Eval(Num(I),_) is I;
  Eval(Add(L,R),env) is Eval(L,env) + Eval(R,env)
  Eval(Mul(L,R),env) is Eval(L,env) * Eval(R,env)

  main() do {
    logMsg(info,"Answer $(Eval(Add(Var("a"),Mul(Num(2),Var("b"))),
                                                 map of {"a"->3; "b"->4; "c"->5}))");
  }
}

Vim Script

function! s:eval(env, exp)
    let l:type = a:exp[0]
    if l:type == "Number"
        return a:exp[1]
    elseif l:type == "Variable"
        return a:env[a:exp[1]]
    elseif l:type == "Add"
        return s:eval(a:env, a:exp[1]) + s:eval(a:env, a:exp[2])
    elseif l:type == "Multiply"
        return s:eval(a:env, a:exp[1]) * s:eval(a:env, a:exp[2])
    endif
    echoerr "Arguments Error"
endfunction

function! s:run()
    let exp_tree = ["Add", ["Variable", "a"], ["Multiply", ["Number", 2], ["Variable", "b"]]]
    let env = {"a":3, "b" : 4, "c" : 5 }
    echomsg s:eval(env, exp_tree)
endfunction

call s:run()

Ruby function/proc based

Mul  = ->(e1, e2){ ->(env){ e1.(env) * e2.(env) }}
Add  = ->(e1, e2){ ->(env){ e1.(env) + e2.(env) }}
Var  = ->(e)     { ->(env){ env[e]              }}
Num  = ->(e)     { ->(env){ e                   }}

ast = Add.(Var.(:a), (Mul.(Num.(2), Var.(:b))))
puts ast.({ a: 3, b: 4, c: 5 })

Go function based

package main

type Env map[string]int
type Expr func(Env) int

func Add(a, b Expr) Expr {
    return func(env Env) int { return a(env) + b(env) }
}

func Mul(a, b Expr) Expr {
    return func(env Env) int { return a(env) * b(env) }
}

func Var(name string) Expr {
    return func(env Env) int { return env[name] }
}

func Num(val int) Expr {
    return func(env Env) int { return val }
}

func main() {
    ast := Add(Var("a"), (Mul(Num(2), Var("b"))))
    println(ast(Env{"a": 3, "b": 4, "c": 5}))
}

Ruby OO dynamic dispatch

class Expr
  def initialize(*args); @args = args end
  def self.call(*args); new(*args) end
end

class Mul < Expr
  def eval(env); @args[0].eval(env) * @args[1].eval(env) end
end

class Add < Expr
  def eval(env); @args[0].eval(env) + @args[1].eval(env) end
end

class Var < Expr
  def eval(env); env[@args[0]] end
end

class Num < Expr
  def eval(env); @args[0] end
end

ast = Add.(Var.(:a), (Mul.(Num.(2), Var.(:b))))
puts ast.eval({a: 3, b:4, c:5})

Ruby OO static dispatch

class Expr
  attr_accessor :args
  def initialize(*args); @args = args end
  def self.call(*args); new(*args) end
end

class Mul < Expr; end
class Add < Expr; end
class Var < Expr; end
class Num < Expr; end

class Env
  def initialize(env); @env = env end
  def eval(ast)
    case ast
    when Num then ast.args[0]
    when Var then @env[ast.args[0]]
    when Mul then self.eval(ast.args[0]) * self.eval(ast.args[1])
    when Add then self.eval(ast.args[0]) + self.eval(ast.args[1])
    end
  end
end

Env.
  new({a: 3, b:4, c:5}).
  eval(ast = Add.(Var.(:a), (Mul.(Num.(2), Var.(:b)))))

Tcl

namespace eval ::ast {
    namespace export evaluate
    namespace ensemble create
    namespace path ::tcl::mathop

    proc evaluate { env exp } {
        lassign $exp token arg1 arg2
        switch -exact -- $token {
            Number { return $arg1 }
            Add { return [+ [evaluate $env $arg1] [evaluate $env $arg2]] }
            Multiply { return [* [evaluate $env $arg1] [evaluate $env $arg2]] }
            Variable { return [dict get $env $arg1] }
            default { error "Unknown token: $token" }
        }
    }
}

set environment { a 3 b 4 c 5 }
puts [ast evaluate $environment {
    Add { Variable a } { Multiply { Number 2 } { Variable b } }
}]

Swift 2.0:

indirect enum Expression {
    case Number(Int)
    case Add(Expression, Expression)
    case Multiply(Expression, Expression)
    case Variable(String)
}

func evaluate(env: [String: Int], _ expression: Expression) -> Int {
    switch expression {
    case let .Number(n): return n
    case let .Add(l, r): return evaluate(env, l) + evaluate(env, r)
    case let .Multiply(l, r): return evaluate(env, l) * evaluate(env, r)
    case .Variable(let name): return env[name] ?? 0
    }
}

let expressionTree: Expression = .Add(.Variable("a"), .Multiply(.Number(2), .Variable("b")))
let result = evaluate(["a": 3, "b": 4, "c": 7], expressionTree)

Back to Ocaml, to show a comparison between OOP and FP
(and show that this language may also be decent at OOP)

So the objective is writing some code so that the following lines will do their job :
(For aesthetic purposes I'll be using infix operators (e.g. |+| instead of add))

let expr = (variable "a") |+| ((number 2) |*| (variable "b"))
let env = function "a" -> 3 | "b" -> 4 | "c" -> 7
| c -> failwith ("Unbound variable " ^ c)
let result = eval env expr

Note that the idea behind the env parameter is to be able to define the expression without it, and only use it when evaluating the actual value of the expression. I point this out because some of the proposed solutions do not follow that idea.

So, now with the actual solution. I have decided to keep it more generalised with polymorphic expressions
('a expr) and allowing any 2-ary operator ('a -> 'a -> 'a)

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