First example of Harrison's "Handbook of Practical Logic and Automated Reasoning" in Julia.

harr1.jl

abstract Expr

type Const <: Expr; value::Int end
type Var <: Expr; name::String end
type Add <: Expr; left::Expr; right::Expr end
type Mult <: Expr; left::Expr; right::Expr end

add(x::Const, y::Const) = Const(x.value + y.value)
add(x::Const, y::Expr) = x.value == 0? y : Add(x, y)
add(x::Expr, y::Const) = add(y, x)
add(x::Expr, y::Expr) = Add(x, y)

multiply(x::Const, y::Const) = Const(x.value * y.value)
multiply(x::Const, y::Expr) = x.value == 1? y : (x.value == 0? Const(0) : Mult(x, y))
multiply(x::Expr, y::Const) = multiply(y, x)
multiply(x::Expr, y::Expr) = Mult(x, y)

simplify1(a::Add) = add(a.left, a.right)
simplify1(m::Mult) = multiply(m.left, m.right)
simplify1(e::Expr) = e

simplify(a::Add) = simplify1(add(simplify(a.left), simplify(a.right)))
simplify(m::Mult) = simplify1(multiply(simplify(m.left), simplify(m.right)))
simplify(e::Expr) = e

expr1 = Add(Mult(Add(Const(1), Mult(Const(0), Var("x"))), Const(3)), Const(12))
print(string(expr1, '\n'))
print(string(simplify(expr1), '\n'))