54 lines
1019 B
JavaScript
54 lines
1019 B
JavaScript
import { serialize } from "./serialize.mjs";
|
|
|
|
export function reduce (expr, max_steps = 1000) {
|
|
if (!is_application(expr)) {
|
|
return expr;
|
|
}
|
|
|
|
let result = reduce_single(expr);
|
|
const visited = new Map();
|
|
|
|
// trampoline
|
|
for (let step = 0; step < max_steps; step++) {
|
|
const key = serialize(result);
|
|
|
|
if (visited.has(key)) return result;
|
|
visited.set(key, true);
|
|
result = reduce_single(result);
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
function reduce_single (expr) {
|
|
if (!is_application(expr)) {
|
|
return expr;
|
|
}
|
|
|
|
return apply(reduce_single(expr[0]), reduce_single(expr[1]));
|
|
}
|
|
|
|
function is_application (expr) {
|
|
return expr.length === 2
|
|
&& !is_function(expr);
|
|
}
|
|
|
|
function is_function (expr) {
|
|
return expr[0] === 0;
|
|
}
|
|
|
|
function apply (fn, arg) {
|
|
const body = fn[1];
|
|
return replace(body, arg);
|
|
}
|
|
|
|
function replace (expr, val, depth = 1) {
|
|
const next_depth = is_function(expr) ? depth + 1 : depth;
|
|
|
|
return Array.isArray(expr)
|
|
? expr.map((item) => replace(item, val, next_depth))
|
|
: expr === depth
|
|
? val
|
|
: expr;
|
|
}
|