我想用蹦床用 JavaScript 重写我的 lisp 中的所有递归函数。我有两个例子我不知道如何重写：
Pair.fromArray = trampoline(function fromArray(array) {
if (array.length === 0) {
return nil;
} else {
return new Thunk(() => {
var car;
if (array[0] instanceof Array) {
car = Pair.fromArray(array[0]);
} else {
car = array[0];
}
if (typeof car === 'string') {
car = LString(car);
}
if (array.length === 1) {
return new Pair(car, nil);
} else {
// this overload the stack
return new Pair(car, Pair.fromArray(array.slice(1)));
}
});
}
});
// ----------------------------------------------------------------------
var pair_to_string = trampoline(function pair_to_string(pair, rest) {
var arr = [];
if (!rest) {
arr.push('(');
}
var value = toString(pair.car, true);
if (value !== undefined) {
arr.push(value);
}
return new Thunk(() => {
if (pair.cdr instanceof Pair) {
arr.push(' ');
const cdr = pair_to_string(pair.cdr, true);
arr.push(cdr);
} else if (pair.cdr !== nil) {
arr = arr.concat([' . ', toString(pair.cdr, true)]);
}
if (!rest) {
arr.push(')');
}
return arr.join('');
});
});
// ----------------------------------------------------------------------
Pair.prototype.toString = function(quote, rest) {
return pair_to_string(this, quote, rest);
};
这是蹦床代码：
function Thunk(fn) {
this.fn = fn;
}
// ----------------------------------------------------------------------
Thunk.prototype.toString = function() {
return '#<Thunk>';
};
// ----------------------------------------------------------------------
function trampoline(fn) {
return function(...args) {
return unwind(fn.apply(this, args));
};
}
// ----------------------------------------------------------------------
function unwind(result) {
while (result instanceof Thunk) {
result = result.fn();
}
return result;
}
问题是它不起作用，如果调用 trampolined 函数，它会重载堆栈，从 trampoline 调用返回的值，当我调用命名函数表达式时，我得到：(1 #<Thunk>)。我试过放unwind(pair_to_string(pair.cdr, quote, true))，但这也会使堆栈超载。
这个函数可以用 trampoline 编写，以便将 lisp 列表转换为字符串吗？
这是具有这两个功能的堆栈片段。我知道我需要编写看起来像尾递归但返回 Thunk 的函数，但如果我在创建表达式的过程中该怎么做。
// ----------------------------------------------------------------------
function Thunk(fn) {
this.fn = fn;
}
// ----------------------------------------------------------------------
Thunk.prototype.toString = function() {
return '#<Thunk>';
};
// ----------------------------------------------------------------------
function trampoline(fn) {
return function(...args) {
return unwind(fn.apply(this, args));
};
}
// ----------------------------------------------------------------------
function unwind(result) {
while (result instanceof Thunk) {
result = result.fn();
}
return result;
}
// ----------------------------------------------------------------------
function toString(obj, ...arg) {
if (obj instanceof Pair) {
return obj.toString(...arg);
}
return obj.toString();
}
// ----------------------------------------------------------------------
function Pair(car, cdr) {
this.cdr = cdr;
this.car = car;
}
// ----------------------------------------------------------------------
var nil = new function Nil() {};
// ----------------------------------------------------------------------
Pair.fromArray = trampoline(function fromArray(array) {
if (array.length === 0) {
return nil;
} else {
var car;
if (array[0] instanceof Array) {
car = Pair.fromArray(array[0]);
} else {
car = array[0];
}
if (array.length === 1) {
return new Pair(car, nil);
} else {
return new Pair(car, Pair.fromArray(array.slice(1)));
}
}
});
// ----------------------------------------------------------------------
var pair_to_string = function pair_to_string(pair, rest) {
var arr = [];
if (!rest) {
arr.push('(');
}
var value = toString(pair.car, true);
if (value !== undefined) {
arr.push(value);
}
if (pair.cdr instanceof Pair) {
arr.push(' ');
const cdr = pair_to_string(pair.cdr, true);
arr.push(cdr);
} else if (pair.cdr !== nil) {
arr = arr.concat([' . ', toString(pair.cdr, true)]);
}
if (!rest) {
arr.push(')');
}
return arr.join('');
};
// ----------------------------------------------------------------------
Pair.prototype.toString = function(rest) {
return pair_to_string(this, rest);
};
// ----------------------------------------------------------------------
function range(n) {
const range = new Array(n).fill(0).map((_, i) => i);
return Pair.fromArray(range);
}
// ----------------------------------------------------------------------
console.log(range(40).toString());
var l = range(8000);
console.log(l.toString());注意：上面的代码已经重构了没有任何蹦床的原始功能（蹦床代码包含但未使用）。
PS：我也可以使用其他解决方案，它允许在不使用递归和消耗堆栈的情况下遍历二叉树。如果您不能使用蹦床遍历二叉树，我也可以解释为什么这是不可能的。但更喜欢实际的解决方案。