如何将同步和异步递归函数转换为JavaScript中的迭代 [英] How to convert sync and async recursive function to iteration in JavaScript
问题描述
正在寻找同步和异步递归函数的特定实现，这些实现可以用作将将来的递归函数转换为平面迭代的起点。
以下是两个递归函数的示例：同步和异步。
我要寻找的是使用无递归堆栈。
例如，也许可以这样工作：
var输出= syncStack（myRecursiveFunctionTurnedIterative，[]）
或如果那是不可能的，那么只需使用堆栈重新实现下面的两个函数，那应该是一个很好的开始。例如，
var stack = []
函数CircularReferences（object，reference，stack）{
var输出= {}
如果（object .__ circularid__）返回true
Object.defineProperty（object，'__circularid__'，{value：id ++}）
for（var key in object） {
var value = object [key]
if（value&& typeof value =='object'）{
console.log（value）
stack.push（ ???）
CircularReferences（）
stack.pop（）
if（is）output [key] ='[Circular]'
} else {
输出[键] =值
}
}
}
出现此问题的原因是，多年来，我一直在尝试学习如何做到这一点，但从未找到一种系统（a）易于记忆的方法和（b）实用的系统。
同步
var引用= {} var对象= {a：{b：{c：{d：{e：10，f：11 ，g：12}}}}}} object.abcdx = objectobject.abcdy = object.a.bvar id = 1var x = circleReferences（object，reference）console.log（x）function CircularReferences（object，reference）{var output = {} if（object .__ circularid__）返回true Object.defineProperty（object，'__circularid__'，{value：id ++}）for（var key in object）{var value = object [key] if（value&& typeof值=='对象'）{console.log（值）var is = circleReferences（值，引用）if（is）output [key] ='[Circular]'} else {output [key] = value}}}
异步
var items = [async1a，async1b，async1c // ...] asynca（items，function（）{console.log（ 'done'）}）函数asynca（items，callback）{var i = 0 function next（）{var item = items [i ++] if（！item）return callback（）item（next）}}函数async1a（callback） {//一些东西... setTimeout（function（）{if（true）{var items = [async2a，// ...] asynca（items，callback）} else {callback（null，true）}}，200 ）} function async1b（callback）{//一些东西... setTimeout（function（）{if（true）{ var items = [async2a，// ...] asynca（items，callback）} else {callback（null，true）}}，200）} function async1c（callback）{//一些东西... setTimeout（function（ ）{if（true）{var items = [async2a，// ...] asynca（items，callback）} else {callback（null，true）}}，200）}函数async2a（callback）{返回callback（） }
例如，
p>
var个项= [
async1a，
async1b，
async1c
// //。 ..
]
asynca（items，function（）{
console.log（'done'）
}，[]）
函数asynca（项，回调，堆栈）{
var i = 0
函数next（）{
var item = items [i ++]
if（ ！item）返回callback（）
stack.push（item）
}
}
但这就是我迷路的地方。不确定如何绕过堆栈以及一般应如何设置功能。
想知道如何在实践中，将它们写为非递归函数。我见过从递归到迭代的方法，但是它们是都是非常理论性的。
为了使我们能够将带有某个函数的过程转换为另一个函数（无论是否具有该函数）它是相同的函数，也称为递归，没有区别），我们需要将其分为在调用之前发生的过程和调用之后的任何过程。如果出站调用之后没有任何过程，并且出站调用到同一个函数，则可以将其描述为尾递归，这可以使转换为迭代过程变得更加简单，只需将调用参数推入堆栈即可（示例）。实际上，将尾递归转换为迭代堆栈过程已帮助我克服了多个实际实例中浏览器的递归深度限制。
转换为尾递归
为了将递归转换为尾递归，我们必须考虑如何处理从递归调用传递的信息，以及是否可以转换此过程以利用参数中的参数。递归本身。由于在您的特定示例中，呼出结果唯一发生的是本地变量 output 和 output 是一个对象，在JavaScript中它是通过引用传递的，我们可以进行此转换。因此，这是一个简单的重构，使我们能够使用简洁的堆栈（我将尾递归代码跳过了堆栈实现；留给读者练习）：
var引用= {} var对象= {a：{b：{c：{d：{e：10，f：11 ，g：12}}}}}} object.abcdx = objectobject.abcdy = object.a.bvar id = 1 // var x = circleReferences（object，reference）// console.log（x）//功能circleReferences（object ，引用）{// =>添加参数，'输出'和'键'var stack = [[object，reference，null，null]];而（stack.length）{[_object，_references，_callerOutput，_key] = stack.pop（）var output = {} if（_object .__ circularid __）{_callerOutput [_key] ='[Circular]'//登录我们的示例console.log（'OUTPUT VALUE：'+ JSON.stringify（_callerOutput））//退出继续； } Object.defineProperty（_object，'__circularid__'，{value：id ++}）for（_object中的var键）{var value = _object [key] if（value&&&typeof value =='object'）{控制台。 log（value）// var is = CircularReferences（value，references）//如果（is）output [key] ='[Circular]'stack.push（[value，_references，output，key]）} else {output [键] =值}}}
$ p
$ b
概括堆栈和排序操作
由于将递归转换为尾递归可能并不总是那么容易和直接，所以让我们考虑如何使用堆栈以类似于原始的递归。我们还将概括一下我们的堆栈，这将有助于您完成第二个异步示例。除了存储调用参数外，还存储要调用的函数和参数。像这样的东西：
（堆栈）[
[函数A，用于此A调用的参数，为此的其他引用调用A]，
[函数B，调用B的参数，调用B的其他引用]
]
我们知道，栈操作是后进先出，这意味着，如果我们有一个函数在调用另一个函数之后进行操作，则这些后续操作将需要在调用之前 推入堆栈，以便从堆栈进行处理的顺序如下：
（堆栈）[first_call]
弹出堆栈
=> first_call：out_call
之前的
处理过程out_call
=>之后的推送过程（堆栈）[out_call之后的过程]
push out_call
=> （堆栈）[out_call，
out_call之后的过程]
pop stack
=> out_call
（可能之后还有其他一系列堆栈交互）
pop stack
=> out_call之后的过程（也许使用存储的结果）
（所有这些都有点利用堆栈概念来订购我们的操作如果您想获得真正的幻想（甚至更复杂），请对每个指令进行编码，并将其作为函数，并模拟实际的调用堆栈，可以在主程序中的其他函数被压入时暂停下一条指令。）
现在让我们将此想法应用于您的示例：
同步示例
我们不仅在这里有呼叫后程序，而且还有一个带有此类调用的完整for循环。 （请注意，直接在代码段查看器中查看的控制台日志不完整。请查看您浏览器的JS控制台中的完整日志。）
var引用= {}; var对象= {a：{b：{c：{d：{e：10，f：11，g：12}}}}}} ; object.abcdx = object; object.abcdy = object.ab; var id = 1; let iterativeProcess = {堆栈：[]，currentResult：undefined，start：function（）{//垃圾收集器:) iterativeProcess.currentResult = undefined console.log（'Starting stack process'）//用于调试，以避免无限循环let keep_going = 100; while（iterativeProcess.stack.length&& keep_going-）{让[func_name，func，params，refs] = iterativeProcess.stack.pop（）; console.log（’\npopped：[’+ func_name +’，‘+ params +’，’+ JSON.stringify（refs）+’]’）; params.unshift（refs）; func.apply（func，params）; }返回堆栈过程已完成\n\n； }};让CircularReferences = {preOutCall：function（refs，_object，_references）{var output = {}; if（_object .__ circularid __）{console.log（’preOutCall：_object的__circularid__设置currentResult为true’）iterativeProcess.currentResult = true; //退出return; } Object.defineProperty（_object，'__circularid__'，{value：id ++}）//将出站后调用过程推入堆栈console.log（'推入堆栈postOutCall'+ Object.keys（_object）[0]） iterativeProcess.stack.push（[['postOutCall'，CircularReferences.postOutCall，[]，输出]）; //反向调用for循环让钥匙= Object.keys（_object）; for（让i = keys.length-1; i> = 0; i--）circleReferences.subroutineA（output，_object，keys [i]，_references）; }，子例程A：function（refs，_object，key，_references）{var value = _object [key]; if（value&& typeof value ==‘object’）{console.log（’subroutineA：key：’+ key +’; value is a object：‘+ value）; console.log（'推入堆叠postSubroutineA的+键）iterativeProcess.stack.push（[[postSubroutineA'，CircularReferences.postSubroutineA，[key]，refs]）; //将呼叫推送到堆栈console.log（将堆栈推送到preOutCall- +键）iterativeProcess.stack.push（[[preOutCall- +键，circularReferences.preOutCall，[值，_references，refs]））； } else {console.log（’subroutineA：key：’+ key +’； value不是对象：’+ value）； console.log（'Pushing to stack subroutineA1'+ key）iterativeProcess.stack.push（[['subroutineA1，，circleReferences.subroutineA1，[key，value]，refs]）; }}，subroutineA1：函数（引用，键，值）{console.log（’subroutineA1：将键 +键+设置为 +值）； refs [key] = value; }，postSubroutineA：function（refs，key）{let is = iterativeProcess.currentResult; // circularReferences（value，_references）if（is）{refs [key] =‘[Circular]’; console.log（’postSubroutineA：对象键： +键+是圆形；输出： + JSON.stringify（refs））； } else {console.log（’postSubroutineA：key：’+ key +’； currentResult：’+ iterativeProcess.currentResult +’；输出：’+ JSON.stringify（refs））; }}，postOutCall：function（）{//原始函数中没有return语句//因此，我们将当前结果设置为undefined iterativeProcess.currentResult = undefined; }}; //将递归调用转换为迭代// var x = CircularReferences（object，reference）// console.log（x）console.log（'Pushing to stack'）iterativeProcess.stack.push（['preOutCall' ，circleReferences.preOutCall，[对象，引用]]）; console.log（iterativeProcess.start（））;
异步示例
（我随意地给 next（）添加了呼叫在 asynca 的末尾，我想您已经忘记了。）
如果有多个交织的函数调用，则复杂的是调用是异步的，这基本上意味着将有多个堆栈过程。由于在此特定示例中，堆栈过程不会在时间上重叠，因此我们将仅使用一个堆栈，依次调用。 （请注意，直接在代码段查看器中查看的控制台日志不完整。请查看您浏览器的JS控制台中的完整日志。）
let async = {asynca：function（refs，items，callback）{让我= 0;函数next（refs）{console.log（‘next：i：’+ i）;让item = items [i ++]; if（！item）{console.log（‘未定义项，推送到堆栈：回调’）； iterativeProcess.stack.push（[[callback]，callback，[]，refs]）; } else {console.log（已定义项目，推送到堆栈：项目）； iterativeProcess.stack.push（[[item]，item，[next]，refs]）; }} console.log（‘asynca：推送到堆栈：next’）； iterativeProcess.stack.push（['next'，next，[]，refs]）; }，async1a：function（refs，callback）{//一些东西... setTimeout（function（）{if（true）{var items = [async.async2a，// ...] console.log（'async1a：推送到堆栈：asynca'）; iterativeProcess.stack.push（['asynca'，async.asynca，[items，callback]，refs]）;} else {console.log（'async1a：推送到堆栈：callback'） ; iterativeProcess.stack.push（[['callback'，callback，[null，true]，refs]）;} //由于存在超时，我们必须重新启动堆栈过程以模拟// //另一个线程iterativeProcess.start（ ）;}，200）}，async1b：function（refs，callback）{//一些东西... setTimeout（function（）{if（true）{var items = [async.async2a，// ...]控制台.log（'async1b：推送到堆栈：asynca'）; iterativeProcess.stack.push（['asynca'，async.asynca，[items，callback]，refs]）;} else {console.log（'as ync1b：推送至堆栈：回调’）； iterativeProcess.stack.push（[['callback'，callback，[null，true]，refs]）}} //由于存在超时，我们必须重新启动堆栈进程以模拟//另一个线程console.log（iterativeProcess。开始（））; }，200）}，async1c：function（refs，callback）{//一些东西... setTimeout（function（）{if（true）{var items = [async.async2a，// ...] console.log （'async1c：推送至堆栈：asynca'）; iterativeProcess.stack.push（['asynca'，async.asynca，[items，callback]，refs]）;} else {console.log（'async1c：推送至堆栈：callback'）; iterativeProcess.stack.push（[['callback'，callback，[null，true]，refs]）;} //由于超时，我们必须重新启动堆栈过程以模拟//另一个线程console.log（iterativeProcess.start（））;}，200）}，async2a：function（refs，callback）{console.log（'async2a：push to stack：callback'）; iterativeProcess.stack.push（[[callback]，callback，[]，refs]）; }} let iterativeProcess = {stack：[]，currentResult：undefined，start：function（）{//垃圾收集器:) iterativeProcess.currentResult = undefined console.log（'Starting stack process'）//用于调试，以避免无限循环让keep_going = 100; while（iterativeProcess.stack.length&& keep_going-）{让[func_name，func，params，refs] = iterativeProcess.stack.pop（）; console.log（’\npopped：[’+ func_name +’，[’+ params.map（x => typeof x）+’]，’+ JSON.stringify（refs）+’]’）; params.unshift（refs）; func.apply（func，params）; }返回堆栈过程已完成\n\n； }}; let _items = [async.async1a，async.async1b，async.async1c // ...]; console.log（'推送到堆栈：asynca'）; iterativeProcess.stack.push（['asynca'，async .asynca，[_items，function（）{console.log（'\ndone'）}]））; console.log（iterativeProcess.start（））;
调用堆栈仿真
我不确定是否会有时间解决这个问题，但是这里有一些通用模板的想法。将其他功能调用为相关的较小功能的单独功能，以使执行暂停，也许将它们编码为具有一系列操作和键的对象，以模拟局部变量。
然后编写一个控制器和接口，该控制器和接口可以区分对另一个函数的调用（如果它也具有出站调用，则类似地编码），将该函数的对象（或堆栈框架）推入堆栈，记住下一个的位置符合指令。使用对象键作为被调用函数的返回地址，例如，可以使控制器知道，可以使用JavaScript来完成许多创造性的方法。
正如其他人在这里指出的那样，每个调用另一个函数的函数都提出了自己的挑战，即将其转换为迭代序列。但是可能有许多功能可能适合这种方案，并使我们从执行限制和排序的附加控制中受益。
Looking for a specific implementation for both sync and async recursive functions that could be used as a starting point to turn future recursive functions into flat iteration.
Below are two examples of recursive functions: Synchronous and Asynchronous.
What I am looking for is an implementation of both using a stack without recursion.
For example, maybe it would work like this:
var output = syncStack(myRecursiveFunctionTurnedIterative, [])
Or if that's not possible, then just a reimplementation of the two functions below using a stack, and that should be a good enough start. E.g.
var stack = []
function circularReferences(object, references, stack) {
var output = {}
if (object.__circularid__) return true
Object.defineProperty(object, '__circularid__', { value: id++ })
for (var key in object) {
var value = object[key]
if (value && typeof value == 'object') {
console.log(value)
stack.push(???)
circularReferences()
stack.pop()
if (is) output[key] = '[Circular]'
} else {
output[key] = value
}
}
}
The reason for this question is, I have tried over the years to learn how to do this, but have never found a system that is (a) easy to remember how to do, and (b) practical.
Synchronous
var references = {}
var object = {
a: {
b: {
c: {
d: {
e: 10,
f: 11,
g: 12
}
}
}
}
}
object.a.b.c.d.x = object
object.a.b.c.d.y = object.a.b
var id = 1
var x = circularReferences(object, references)
console.log(x)
function circularReferences(object, references) {
var output = {}
if (object.__circularid__) return true
Object.defineProperty(object, '__circularid__', { value: id++ })
for (var key in object) {
var value = object[key]
if (value && typeof value == 'object') {
console.log(value)
var is = circularReferences(value, references)
if (is) output[key] = '[Circular]'
} else {
output[key] = value
}
}
}
Asychronous
var items = [
async1a,
async1b,
async1c
// ...
]
asynca(items, function(){
console.log('done')
})
function asynca(items, callback) {
var i = 0
function next() {
var item = items[i++]
if (!item) return callback()
item(next)
}
}
function async1a(callback) {
// Some stuff...
setTimeout(function(){
if (true) {
var items = [
async2a,
// ...
]
asynca(items, callback)
} else {
callback(null, true)
}
}, 200)
}
function async1b(callback) {
// Some stuff...
setTimeout(function(){
if (true) {
var items = [
async2a,
// ...
]
asynca(items, callback)
} else {
callback(null, true)
}
}, 200)
}
function async1c(callback) {
// Some stuff...
setTimeout(function(){
if (true) {
var items = [
async2a,
// ...
]
asynca(items, callback)
} else {
callback(null, true)
}
}, 200)
}
function async2a(callback) {
return callback()
}
For example, that may start looking something like:
var items = [
async1a,
async1b,
async1c
// ...
]
asynca(items, function(){
console.log('done')
}, [])
function asynca(items, callback, stack) {
var i = 0
function next() {
var item = items[i++]
if (!item) return callback()
stack.push(item)
}
}
But that's where I get lost. Not sure how to pass around the stack and how the functions should be setup in general.
Wondering how to in practice write those as non-recursive functions. I've seen Way to go from recursion to iteration but they are all very theoretical.
In order for us to convert a procedure with a function that calls out to another function (whether or not it's the same function, aka 'recursive', makes no difference), we will need to separate it into the procedure that occurs before such a call and any procedures subsequent to the call. If there are no procedures after the out-call and the out-call is to the same function, we can describe it as "tail recursive," which can make the conversion to iterative much much simpler, simply pushing the call parameters to the stack (Example). In fact, converting tail-recursion to an iterative stack process has helped me overcome browsers' recursion-depth limits in more than one real instance.
Converting to tail-recursive
In order to convert a recursion to tail-recursive, we must consider how the information delivered from the recursive call is processed and whether we can transform this process to utilize parameters in the recursion itself. Since in your particular example, the only thing that happens with the out-call result is the setting of the local variable, output, and output is an object, which in JavaScript is passed by reference, we are in a position to make this transformation. So here's a simple refactor that will enable us to use a succinct stack (I skipped over the tail-recursive code to the stack implementation; left as an exercise for the reader):
var references = {}
var object = {
a: {
b: {
c: {
d: {
e: 10,
f: 11,
g: 12
}
}
}
}
}
object.a.b.c.d.x = object
object.a.b.c.d.y = object.a.b
var id = 1
//var x = circularReferences(object, references)
//console.log(x)
//function circularReferences(object, references) {
// => add parameters, 'output' and 'key'
var stack = [[object, references, null, null]];
while (stack.length){
[_object, _references, _callerOutput, _key] = stack.pop()
var output = {}
if (_object.__circularid__){
_callerOutput[_key] = '[Circular]'
// Log our example
console.log('OUTPUT VALUE: ' + JSON.stringify(_callerOutput))
// Exit
continue;
}
Object.defineProperty(_object, '__circularid__', { value: id++ })
for (var key in _object) {
var value = _object[key]
if (value && typeof value == 'object') {
console.log(value)
//var is = circularReferences(value, references)
// if (is) output[key] = '[Circular]'
stack.push([value, _references, output, key])
} else {
output[key] = value
}
}
}
Generalizing the stack and ordering operations
Since it may not always be easy and straightforward to transform a recursion to tail-recursive, let's consider how we can use the stack to order operations iteratively in a way similar to the original recursion. We'll also generalize our stack a bit, which will help us with your second, "Asynchronous," example. Rather than only the call parameters, let's store both which function to call as well as the parameters. Something like:
(stack) [
[function A, parameters for this call of A, additional refs for this call of A],
[function B, parameters for this call of B, additional refs for this call of B]
]
As we know, a stack operates "last in, first out," which means if we have a function with operations subsequent to an out-call to another function, those subsequent operations will need to be pushed to the stack before the out-call so that the order of processing from the stack will be something like:
(stack) [first_call]
pop stack
=> first_call:
process procedure before out_call
push procedure after out_call
=> (stack) [procedure after out_call]
push out_call
=> (stack) [procedure after out_call,
out_call]
pop stack
=> out_call
(maybe followed by a whole other series of stack interactions)
pop stack
=> procedure after out_call (maybe use stored result)
(All of this is a bit of a hack to utilize the stack concept to order our operations. If you want to get real fancy (and even more complicated), code each instruction as a function and simulate an actual call stack with the ability to pause the next instruction in the main program as calls to other functions are pushed to it.)
Now let's apply this idea to your examples:
Synchronous example
Not only do we have after-out-call procedures here, but we have an entire for-loop with such calls. (Please note that the console logs viewed directly in the snippet viewer are incomplete. Observe your browser's JS console for the complete logs.)
var references = {};
var object = {
a: {
b: {
c: {
d: {
e: 10,
f: 11,
g: 12
}
}
}
}
};
object.a.b.c.d.x = object;
object.a.b.c.d.y = object.a.b;
var id = 1;
let iterativeProcess = {
stack: [],
currentResult: undefined,
start: function(){
// Garbage collector :)
iterativeProcess.currentResult = undefined
console.log('Starting stack process')
// Used for debugging, to avoid an infinite loop
let keep_going = 100;
while (iterativeProcess.stack.length && keep_going--){
let [func_name, func, params, refs] = iterativeProcess.stack.pop();
console.log('\npopped: [' + func_name + ', ' + params + ', ' + JSON.stringify(refs) + ']');
params.unshift(refs);
func.apply(func, params);
}
return 'Stack process done\n\n';
}
};
let circularReferences = {
preOutCall: function(refs, _object, _references){
var output = {};
if (_object.__circularid__){
console.log('preOutCall: _object has __circularid__ setting currentResult true')
iterativeProcess.currentResult = true;
// Exit
return;
}
Object.defineProperty(_object, '__circularid__', { value: id++ })
// Push post-out-call-procedure to stack
console.log('Pushing to stack postOutCall ' + Object.keys(_object)[0])
iterativeProcess.stack.push(['postOutCall', circularReferences.postOutCall, [], output]);
// Call for-loop in reverse
let keys = Object.keys(_object);
for (let i=keys.length-1; i >=0; i--)
circularReferences.subroutineA(output, _object, keys[i], _references);
},
subroutineA: function(refs, _object, key, _references){
var value = _object[key];
if (value && typeof value == 'object'){
console.log('subroutineA: key: ' + key + '; value is an object: ' + value);
console.log('Pushing to stack postSubroutineA ' + key)
iterativeProcess.stack.push(['postSubroutineA', circularReferences.postSubroutineA, [key], refs]);
// Push out-call to stack
console.log('Pushing to stack preOutCall-' + key)
iterativeProcess.stack.push(['preOutCall-' + key, circularReferences.preOutCall, [value, _references], refs]);
} else {
console.log('subroutineA: key: ' + key + '; value is not an object: ' + value);
console.log('Pushing to stack subroutineA1 ' + key)
iterativeProcess.stack.push(['subroutineA1', circularReferences.subroutineA1, [key, value], refs]);
}
},
subroutineA1: function(refs, key, value){
console.log('subroutineA1: setting key ' + key + ' to ' + value);
refs[key] = value;
},
postSubroutineA: function(refs, key){
let is = iterativeProcess.currentResult; //circularReferences(value, _references)
if (is){
refs[key] = '[Circular]';
console.log('postSubroutineA: Object key: ' + key + ' is circular; output: ' + JSON.stringify(refs));
} else {
console.log('postSubroutineA: key: ' + key + '; currentResult: ' + iterativeProcess.currentResult + '; output: ' + JSON.stringify(refs));
}
},
postOutCall: function(){
// There is no return statement in the original function
// so we'll set current result to undefined
iterativeProcess.currentResult = undefined;
}
};
// Convert the recursive call to iterative
//var x = circularReferences(object, references)
//console.log(x)
console.log('Pushing to stack')
iterativeProcess.stack.push(['preOutCall', circularReferences.preOutCall, [object, references]]);
console.log(iterativeProcess.start());
Asychronous example
(I took the liberty to add a call to next() at the end of asynca, which I think you forgot.)
Here, in addition to multiple, interweaving function calls, we have the complication that calls are asynchronous, which basically means there will be more than one stack process. Since in this particular example stack-processes won't overlap in time, we'll just use one stack, called sequentially. (Please note that the console logs viewed directly in the snippet viewer are incomplete. Observe your browser's JS console for the complete logs.)
let async = {
asynca: function(refs, items, callback){
let i = 0;
function next(refs){
console.log('next: i: ' + i);
let item = items[i++];
if (!item){
console.log('Item undefined, pushing to stack: callback');
iterativeProcess.stack.push(['callback', callback, [], refs]);
} else {
console.log('Item defined, pushing to stack: item');
iterativeProcess.stack.push(['item', item, [next], refs]);
}
}
console.log('asynca: pushing to stack: next');
iterativeProcess.stack.push(['next', next, [], refs]);
},
async1a: function(refs, callback) {
// Some stuff...
setTimeout(function(){
if (true) {
var items = [
async.async2a,
// ...
]
console.log('async1a: pushing to stack: asynca');
iterativeProcess.stack.push(['asynca', async.asynca, [items, callback], refs]);
} else {
console.log('async1a: pushing to stack: callback');
iterativeProcess.stack.push(['callback', callback, [null, true], refs]);
}
// Since there was a timeout, we have to restart the stack process to simulate
// another thread
iterativeProcess.start();
}, 200)
},
async1b: function(refs, callback) {
// Some stuff...
setTimeout(function(){
if (true) {
var items = [
async.async2a,
// ...
]
console.log('async1b: pushing to stack: asynca');
iterativeProcess.stack.push(['asynca', async.asynca, [items, callback], refs]);
} else {
console.log('async1b: pushing to stack: callback');
iterativeProcess.stack.push(['callback', callback, [null, true], refs])
}
// Since there was a timeout, we have to restart the stack process to simulate
// another thread
console.log(iterativeProcess.start());
}, 200)
},
async1c: function(refs, callback) {
// Some stuff...
setTimeout(function(){
if (true) {
var items = [
async.async2a,
// ...
]
console.log('async1c: pushing to stack: asynca');
iterativeProcess.stack.push(['asynca', async.asynca, [items, callback], refs]);
} else {
console.log('async1c: pushing to stack: callback');
iterativeProcess.stack.push(['callback', callback, [null, true], refs]);
}
// Since there was a timeout, we have to restart the stack process to simulate
// another thread
console.log(iterativeProcess.start());
}, 200)
},
async2a: function(refs, callback) {
console.log('async2a: pushing to stack: callback');
iterativeProcess.stack.push(['callback', callback, [], refs]);
}
}
let iterativeProcess = {
stack: [],
currentResult: undefined,
start: function(){
// Garbage collector :)
iterativeProcess.currentResult = undefined
console.log('Starting stack process')
// Used for debugging, to avoid an infinite loop
let keep_going = 100;
while (iterativeProcess.stack.length && keep_going--){
let [func_name, func, params, refs] = iterativeProcess.stack.pop();
console.log('\npopped: [' + func_name + ', [' + params.map(x => typeof x) + '], ' + JSON.stringify(refs) + ']');
params.unshift(refs);
func.apply(func, params);
}
return 'Stack process done\n\n';
}
};
let _items = [
async.async1a,
async.async1b,
async.async1c
// ...
];
console.log('Pushing to stack: asynca');
iterativeProcess.stack.push(['asynca', async.asynca, [_items, function(){console.log('\ndone')}]]);
console.log(iterativeProcess.start());
Call stack emulation
I'm not sure if I'll have time to get to this but here are some ideas for a general template. Separate functions that call other functions into relevant smaller functions to enable a pause in execution, perhaps code them as an object with an array of operations and keys to simulate local variables.
Then write a controller and interface that can distinguish a call to another function (similarly coded if it also has out-calls), push that "function"'s object (or stack-frame) onto the stack, remembering the place of the next instruction in line. There are many creative ways this can be accomplished with JavaScript, using object keys for the "return address" of the called function, for example, that the controller can be made aware of.
As others have noted here, each function with a call to another function presents its own challenge to convert it to an iterative sequence. But there may be many functions that could be amenable to such a scheme, and allow us to benefit from the added control of execution limits and sequencing.
这篇关于如何将同步和异步递归函数转换为JavaScript中的迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
