Simple inefficient lambda calculus calculator on ES5

lambda.js

function array_union(a, b) {
    var cache = {};
    function store(item) {
        cache[item] = item;
    }

    a.forEach(store);
    b.forEach(store);

    return Object.keys(cache).map(function(key) { return cache[key]; });
}

function Var(name) {
    return [0, name];
}

function Abs(name, body) {
    return [1, [name, body]];
}

function App(callee, argument) {
    return [2, [callee, argument]];
}


function is_var(expr) {
    return expr[0] == 0;
}

function is_abs(expr) {
    return expr[0] == 1;
}

function is_app(expr) {
    return expr[0] == 2;
}


function fold_expr(var_case, abs_case, app_case, expr) {
    if (is_var(expr)) {
        return var_case(expr[1]);
    }
    else if (is_abs(expr)) {
        var name = expr[1][0];
        var body = expr[1][1];
        return abs_case(name, body);
    }
    else if (is_app(expr)) {
        var callee = expr[1][0];
        var argument = expr[1][1];
        return app_case(callee, argument);
    }
}

function is_free(name, expr) {
    function var_case(inner_name) {
        return inner_name == name;
    }

    function abs_case(inner_name, body) {
        return name != inner_name && is_free(name, body);
    }

    function app_case(callee, argument) {
        return is_free(name, callee) || is_free(name, argument);
    }

    return fold_expr(var_case, abs_case, app_case, expr);
}

function free_names(expr) {
    function iter(bound, expr) {
        function var_case(name) {
            if (bound.includes(name)) {
                return [];
            }
            else {
                return [name];
            }
        }

        function abs_case(name, body) {
            return iter([name] + bound, body);
        }

        function app_case(callee, argument) {
            return array_union(iter(bound, callee), iter(bound, argument));
        }

        return fold_expr(var_case, abs_case, app_case, expr);
    }

    return iter([], expr);
}

function make_new_name(name, names) {
    var index = 0;
    while (true) {
        var new_name = name + "_" + index;
        if (names.includes(new_name)) {
            index = index + 1;
        }
        else {
            return new_name;
        }
    }
}

function to_string(expr) {
    function var_case(name) {
        return name;
    }

    function abs_case(name, body) {
        return name + " -> " + to_string(body);
    }

    function app_case(callee, argument) {
        function bracket_abs(expr) {
            if (is_abs(expr)) {
                return "(" + to_string(expr) + ")";
            }
            else {
                return to_string(expr);
            }
        }

        if (is_app(argument)) {
            return bracket_abs(callee) + " (" + to_string(argument) + ")";
        }
        else {
            return bracket_abs(callee) + " " + bracket_abs(argument);
        }
    }

    return fold_expr(var_case, abs_case, app_case, expr);
}

function rename(name, new_name, expr) {
    function var_case(inner_name) {
        if (inner_name == name) {
            return Var(new_name);
        }
        else {
            return expr;
        }
    }

    function abs_case(inner_name, body) {
        if (inner_name == name) {
            return expr;
        }
        else {
            return Abs(inner_name, rename(name, new_name, body));
        }
    }

    function app_case(callee, argument) {
        return App(rename(name, new_name, callee), rename(name, new_name, argument));
    }

    return fold_expr(var_case, abs_case, app_case, expr);
}

function replace(name, new_expr, expr) {
    function var_case(inner_name) {
        if (inner_name == name) {
            return new_expr;
        }
        else {
            return expr;
        }
    }

    function abs_case(inner_name, body) {
        if (name == inner_name) {
            return expr;
        }
        else {
            return Abs(inner_name, replace(name, new_expr, body));
        }
    }

    function app_case(callee, argument) {
        return App(replace(name, new_expr, callee), replace(name, new_expr, argument));
    }

    return fold_expr(var_case, abs_case, app_case, expr);
}

function substitute(name, new_expr, expr) {
    function var_case(inner_name) {
        if (inner_name == name) {
            return new_expr;
        }
        else {
            return expr;
        }
    }

    function abs_case(inner_name, body) {
        if (name == inner_name) {
            return expr;
        }
        else if (is_free(inner_name, new_expr) && is_free(name, body)) {
            var new_expr_free_names = free_names(new_expr);
            var body_free_names = free_names(body);
            var free = array_union(new_expr_free_names, body_free_names);
            var new_name = make_new_name(inner_name, free);

            return Abs(new_name, substitute(name, new_expr, rename(inner_name, new_name, body)));
        }
        else {
            return Abs(inner_name, substitute(name, new_expr, body));
        }
    }

    function app_case(callee, argument) {
        return App(substitute(name, new_expr, callee), substitute(name, new_expr, argument));
    }

    return fold_expr(var_case, abs_case, app_case, expr);
}

function call_by_name(expr) {
    function var_case(_) {
        return expr;
    }

    function abs_case(_, _) {
        return expr;
    }

    function app_case(callee, argument) {
        var whnf_callee = call_by_name(callee);

        if (is_abs(whnf_callee)) {
            var name = whnf_callee[1][0];
            var body = whnf_callee[1][1];
            return substitute(name, argument, body);
        }
        else {
            return App(whnf_callee, argument);
        }
    }

    return fold_expr(var_case, abs_case, app_case, expr);
}

function normalise(expr) {
    function var_case(_) {
        return expr;
    }

    function abs_case(name, body) {
        return Abs(name, normalise(body));
    }

    function app_case(callee, argument) {
        var whnf_callee = call_by_name(callee);

        if (is_abs(whnf_callee)) {
            var name = whnf_callee[1][0];
            var body = whnf_callee[1][1];
            return normalise(substitute(name, argument, body));
        }
        else {
            return App(normalise(whnf_callee), normalise(argument));
        }
    }

    return fold_expr(var_case, abs_case, app_case, expr);
}

var one = Abs("next", Abs("init", App(Var("next"), Var("init"))));
var increment = Abs("num", Abs("next", Abs("init", App(Var("next"), App(App(Var("num"), Var("next")), Var("init"))))));
var expr = App(increment, one);

process.stdout.write(to_string(expr) + "\n");
process.stdout.write(to_string(normalise(expr)) + "\n");