Simple expression evaluator comparison between Haskell, Rust, and Common Lisp

Consider a simple expression language that consists only of the four basic mathematical operations – addition, subtraction, multiplication, and division. The idea of this exercise is to implement an evaluator for such a language in Haskell, and then compare it with literal translations (as far as possible) into Rust and Common Lisp. This should be interesting.

First off, the Haskell version:

module Main where

data Expr = Val Int
          | App Op Expr Expr
          deriving (Eq, Show, Ord)

data Op = Add | Sub | Mul | Div deriving (Eq, Show, Ord)


eval :: Expr -> Maybe Int
eval (Val n) = Just n
eval (App o e1 e2) = do m <- eval e1
                        n  Just (m + n)
                            Sub -> Just (m - n)
                            Mul -> Just (m * n)
                            Div -> safediv m n
                            

safediv :: Int -> Int -> Maybe Int
safediv m 0 = Nothing
safediv m n = Just $ m `div` n


e1 :: Expr 
e1 = App Add (Val 2) (App Mul (Val 3) (Val 6))


e2 :: Expr
e2 = App Mul (App Add (Val 1) (Val 3)) (App Div (Val 10) (Val 0))


main :: IO ()
main = do putStrLn $ show (eval e1)
          putStrLn $ show (eval e2)        

As simple as it gets! The `safediv` idea is directly implemented from Professor Graham Hutton’s book, “Programming in Haskell” (2nd Edition) from the chapter on “Functors, Applicatives, and Monads”. We simply use the `Maybe` monad to indicate potential for failure.

Let’s run it:

$ghc -O2 --make *.hs -o main -threaded -rtsopts
[1 of 1] Compiling Main             ( main.hs, main.o )
Linking main ...
$main
Just 20
Nothing

Excellent. For the expression `1 + 3 * 6`, we get `Just 20`, and for `10 / 0`, we get `Nothing`. As expected.

Now let’s see the Rust version:

#[derive(Debug, PartialEq, PartialOrd)]
pub enum Op {
    Add,
    Sub,
    Mul,
    Div
}

use self::Op::*;


#[derive(Debug, PartialEq, PartialOrd)]
pub enum Expr {
    Val(isize),
    App(Op, Box, Box)
}

use self::Expr::*;

impl Expr {
    fn eval(&self) -> Option {
        match *self {
            Val(ref n) => Some(*n),
            App(ref o, ref e1, ref e2) => {
                if let Some(m) = e1.eval() {
                    if let Some(n) = e2.eval() {
                        match *o {
                            Add => return Some(m + n),
                            Sub => return Some(m - n),
                            Mul => return Some(m * n),
                            Div => if n == 0 { 
                                        return None; 
                                    } else { 
                                        return Some (m / n) 
                                   }
                        }
                    } 
                }   
                None
            }
        }
    }
}

fn main() {
    let e1 = Box::new(App(Add, Box::new(Val(2)), 
                      Box::new(App(Mul, Box::new(Val(3)), Box::new(Val(6))))));
    
    let e2 = Box::new(App(Div, Box::new(Val(10)), Box::new(Val(0))));
    
    println!("{:?}, {:?}", e1.eval(), e2.eval());
}

As can be seen, it is an almost identical translation from Haskell into Rust. Algebraic Data Type (ADT) support in Rust makes it a very powerful language, and pattern matching in Rust is as (if not more) powerful as in Haskell. The only difference is the syntax, and I must say that the Haskell version has a lot less noise than the Rust version, even though they are conceptually identical.

Running it:

   Compiling playground v0.0.1 (file:///playground)
    Finished dev [unoptimized + debuginfo] target(s) in 1.02s
     Running `target/debug/playground`

Some(20), None

Excellent!

And finally, for the fun part – Common Lisp. Of course, this is not idiomatic Common Lisp by any stretch of the imagination, and the idea is to try and preserve the essence of the Haskell version whilst still being runnable Lisp. Common Lisp is, of course, a dynamically-typed language, and it doesn’t have a real equivalent of ADTs. However, the bigger discomfort, in my opinion, is that
Common Lisp’s pattern matching is almost non-existent (unlike Racket).

Nevertheless, this is a simple enough example that it does not cause any real problems. The interesting part is how the representation of the expression changes here – due to the lack of a sort of “schema” for the structure of the data, I am forced to include a dummy `nil` argument for the `Val` constructor.
Of course, I could have used varargs to handle that, but that would have led to more verbose code for little ROI. In any case, here is the code:

(defun evaluate (e)
    (let ((op (car e)))
        (cond ((eql op 'Val) (cadr e))
              (t (let ((e1 (evaluate (cadr e)))
                       (e2 (evaluate (caddr e))))
                (cond ((eql op 'Add) (+ e1 e2))
                    ((eql op 'Sub) (- e1 e2))
                    ((eql op 'Mul) (* e1 e2))
                    ((eql op 'Div) (if (= e2 0)
                                    nil
                                    (/ e1 e2)))
                    (t (error "invalid operation"))))))))                    
           
(defun main ()
    (format t "~s~%" (evaluate '(Add (Val 2 nil) (Mul (Val 3 nil) (Val 6 nil)))))
    (format t "~s~%" (evaluate '(Div (Val 10 nil) (Val 0 nil)))))
    

(main)    

And running it:

CL-USER> (main)
20
NIL
NIL