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.
