**Update:** I found a way to encode closed recursive ADTs in Julia and benchmarked this solution against a naive solution. Unfortunately, it performs worse (4.7μs vs 3.3μs for the naive solution), probably due to having to do more allocations.

If anyone finds a better way, please tell me!

### Naive solution

```
abstract type Expression end
struct Const <: Expression
value :: Int
end
struct Var <: Expression
varname ::String
end
struct Add <: Expression
lhs :: Expression
rhs :: Expression
end
evaluate(e::Const, env) = e.value
evaluate(e::Var, env) = env[e.varname]
evaluate(e::Add, env) = evaluate(e.lhs, env) + evaluate(e.rhs, env)
function sum_of_ints(n)
if n == 1
return Const(1)
else
return Add(Const(n), sum_of_ints(n - 1))
end
end
using BenchmarkTools
@btime evaluate(sum_of_ints(100), Dict{String, Int}())
```

```
3.228 μs (202 allocations: 5.23 KiB)
```

### Solution that encodes recursive closed ADTs

```
struct Const
value :: Int
end
struct Var
varname ::String
end
struct Add{E}
lhs :: E
rhs :: E
end
struct Expression
ctor :: Union{Const, Var, Add{Expression}}
end
mkConst(value) = Expression(Const(value))
mkAdd(lhs, rhs) = Expression(Add{Expression}(lhs, rhs))
mkVar(var) = Expression(Var(var))
evaluate(e::Expression, env) = evaluate(e.ctor, env)
evaluate(e::Const, env) = e.value
evaluate(e::Var, env) = env[e.varname]
evaluate(e::Add, env) = evaluate(e.lhs, env) + evaluate(e.rhs, env)
function sum_of_ints(n)
if n == 1
return mkConst(1)
else
return mkAdd(mkConst(n), sum_of_ints(n - 1))
end
end
using BenchmarkTools
@btime evaluate(sum_of_ints(100), Dict{String, Int}())
```

```
4.681 μs (396 allocations: 8.25 KiB)
```