I want to rewrite all recursive function in my lisp in JavaScript with trampoline. I have two examples I don't know how to rewrite:
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);
};
This is the trampoline code:
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;
}
The problem is that it don't work, it overload the stack if called trampolined function the value returned from trampoline call, and when I'm calling named function expression I got: (1 #<Thunk>)
. I've tried to put unwind(pair_to_string(pair.cdr, quote, true))
but that also overload the stack.
Can this function be written with trampoline so it convert lisp list into a string?
Here is Stack snippet with both functions. I know that I need to write function that will look like tail recursive but return Thunk but how can I do that if I in the middle of creating expression.
// ----------------------------------------------------------------------
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());
NOTE: The above code have refactored original functions without any trampoline (trampoline code is included but not used).
PS: I'm also fine with other solution that will allow to traverse binary tree without using recursion and consume the stack. I'm also fine with explanation why it's not possible, if you can't use trampoline to traverse the binary tree. But prefer the actual solution.
nested trampolines
You have highlighted the issue -
Pair.fromArray
istrampoline(function() { ... })
, and the recursive calls toPair.fromArray
create a nested process -As you can see, each element nests another frame of
unwind
that cannot be closed until the end of the input array is encountered.possible implementation
Let's outline a small program to create a Lisp-style list of 100 elements -
Expected output -
We can write
List
in any fashion. Here's one way -Here's the
Pair
module -And the
TailRec
module -Run the snippet below to construct a Lisp-style list with 100,000 elements -
continued reading...
As you can see this works for enormous lists however there is still a possibility to blow the stack if you need to create a very deeply nested list. You can make any recursive program stack-safe without requiring a change in how you think about it. Learn more about such a technique in this Q&A. To see
Loop
andRecur
demonstrated in other ways, see these Q&As.robust, like lisp
As explained, the code above will overflow the stack when calling
fromArray
on a very deeply nested array. the same is true fortoString
if it tries to convert a deeply nested list to a string. Lisp lists don't have these limitations so let's make some improvements -We expect to see
(...)
nested 20,000 levels deep -This time we will implement our
List
module using a more sophisticatedTailRec
module -Taking the technique presented in this Q&A, we implement a
TailRec
module. It's important to note this can solve your specific problem without requiring changes to the original module -And finally the
Pair
module used to build our lists -Expand the snippet below to verify the result in your browser -