Using trampoline to create tree from nested arrays and covert that to string

Question

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.

Answer 1

nested trampolines

You have highlighted the issue -

Pair.fromArray = trampoline(function(array) {
  if ...
    return ...
  else
    return new Thunk(() => {
      if ...
        ...
      else
        return new Pair(car, Pair.fromArray(array.slice(1))) // !
      })
  }
});

Pair.fromArray is trampoline(function() { ... }), and the recursive calls to Pair.fromArray create a nested process -

Pair.fromArray([1, 2, 3])
unwind(fn.apply(this, [1, 2, 3]))
unwind(new Thunk(() => ...))
unwind(new Pair(1, Pair.fromArray([2, 3])))
unwind(new Pair(1, unwind(fn.apply(this, [2, 3]))))
unwind(new Pair(1, unwind(new Thunk(() => ...))))
unwind(new Pair(1, unwind(new Pair(2, Pair.fromArray([3])))))
unwind(new Pair(1, unwind(new Pair(2, unwind(fn.apply(this, [3]))))))
unwind(new Pair(1, unwind(new Pair(2, unwind(new Thunk(() => ...))))))
unwind(new Pair(1, unwind(new Pair(2, unwind(new Pair(3, nil))))))
unwind(new Pair(1, unwind(new Pair(2, new Pair(3, nil)))))
unwind(new Pair(1, new Pair(2, new Pair(3, nil))))
new Pair(1, new Pair(2, new Pair(3, nil)))

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 -

import { fromArray, toString } from "./List"


console.log(toString(fromArray([[1,[2,3],4,[],5]])))
console.log(toString(fromArray(Array.from(Array(100), (_, v) => v))))

Expected output -

((1 (2 3) 4 () 5))
(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100)

We can write List in any fashion. Here's one way -

// List.js

import { Pair } from "./Pair"
import { Loop, Recur } from "./TailRec"

function push(r, v)
{ r.push(v)
  return r
}

const Nil =
  Symbol()

const fromArray = (a = []) =>
  Loop(function(r = Nil, i = 0) {
    if (i >= a.length)
      return reverse(r)
    else if (Array.isArray(a[i]))
      return Recur(Pair(fromArray(a[i]), r), i + 1) 
    else
      return Recur(Pair(a[i], r), i + 1)
  })

const toString = (t = Nil) =>
  Loop(function(r = [], m = t) {
    if (m === Nil)
      return "(" + r.join(" ") + ")"
    else if (m.car === Nil || m.car instanceof Pair)
      return Recur(push(r, toString(m.car)), m.cdr)
    else 
      return Recur(push(r, m.car), m.cdr)
  })

const reverse = (t = Nil) =>
  Loop(function(r = Nil, m = t) {
    if (m === Nil)
      return r
    else
      return Recur(Pair(m.car, r), m.cdr)
  })

export { fromArray, reverse, toString }

Here's the Pair module -

// Pair.js

function Pair (car, cdr)
{ return Object.create
    ( Pair.prototype
    , { constructor: { value: Pair }
      , car: { value: car }
      , cdr: { value: cdr }
      }
    )
}

export { Pair }

And the TailRec module -

// TailRec.js

function Loop (f, ...init)
{ let r = f(...init)
  while (r instanceof Recur)
    r = f(...r)
  return r
}

function Recur (...v)
{ return Object.create
    ( Recur.prototype
    , { constructor: { value: Recur }
      , [Symbol.iterator]: { value: _ => v.values() }
      }
    )
}

export { Loop, Recur }

Run the snippet below to construct a Lisp-style list with 100,000 elements -

function push(r, v)
{ r.push(v)
  return r
}

function Pair (car, cdr)
{ return Object.create
    ( Pair.prototype
    , { constructor: { value: Pair }
      , car: { value: car }
      , cdr: { value: cdr }
      }
    )
}

function Loop (f, ...init)
{ let r = f(...init)
  while (r instanceof Recur)
    r = f(...r)
  return r
}

function Recur (...v)
{ return Object.create
    ( Recur.prototype
    , { constructor: { value: Recur }
      , [Symbol.iterator]: { value: _ => v.values() }
      }
    )
}

const Nil =
  Symbol()

const fromArray = (a = []) =>
  Loop(function(r = Nil, i = 0) {
    if (i >= a.length)
      return reverse(r)
    else if (Array.isArray(a[i]))
      return Recur(Pair(fromArray(a[i]), r), i + 1) 
    else
      return Recur(Pair(a[i], r), i + 1)
  })

const toString = (t = Nil) =>
  Loop(function(r = [], m = t) {
    if (m === Nil)
      return "(" + r.join(" ") + ")"
    else if (m.car === Nil || m.car instanceof Pair)
      return Recur(push(r, toString(m.car)), m.cdr)
    else 
      return Recur(push(r, m.car), m.cdr)
  })

const reverse = (t = Nil) =>
  Loop(function(r = Nil, m = t) {
    if (m === Nil)
      return r
    else
      return Recur(Pair(m.car, r), m.cdr)
  })

console.log(toString(fromArray([[1,[2,3],4,[]]])))
console.log(toString(fromArray(Array.from(Array(100000), (_, v) => v))))

---

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 and Recur 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 for toString 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 -

// Main.js

import { fromArray, toString } from "./List"

// create a deeply nested list!
let r = ["hi"]
for (let i = 0; i < 20000; i++)
  r = [r]

console.log(toString(fromArray(r)))

We expect to see (...) nested 20,000 levels deep -

((((((((...((((((((hi))))))))...))))))))

This time we will implement our List module using a more sophisticated TailRec module -

// List.js

import { loop, recur, call } from "./TailRec"
import { pair, isPair } from "./Pair"

const nil =
  Symbol("nil")

const isNil = t =>
  t === nil

const isList = t =>
  isNil(t) || isPair(t)

const push = (r, v) =>
  (r.push(v), r)

const fromArray = (a = []) =>
  loop
    ( ( m = a
      , i = 0
      ) =>
        i >= m.length
          ? nil
          : call
              ( pair
              , Array.isArray(m[i])
                  ? recur(m[i], 0)
                  : m[i]
              , recur(m, i + 1)
              )
    )

const toString = (t = nil) =>
  loop
    ( ( m = t
      , r = []
      ) =>
        isNil(m)
          ? "(" + r.join(" ") + ")"
      : recur
          ( m.cdr
          , call
              ( push
              , r
              , isList(m.car)
                  ? recur(m.car, [])
                  : String(m.car)
              )
          )
    )

export { fromArray, toString }

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 -

// TailRec.js

const call = (f, ...values) => ...

const recur = (...values) => ...

const loop = f => ...

const run = r => ...

export { loop, recur, call }

And finally the Pair module used to build our lists -

// Pair.js

class Pair
{ constructor (car, cdr)
  { this.car = car
  ; this.cdr = cdr
  }
}

const pair = (car, cdr) =>
  new Pair(car, cdr)

const isPair = t =>
  t instanceof Pair

const toString = t =>
  `(${t.car} . ${t.cdr})`

export { pair, isPair, toString }

Expand the snippet below to verify the result in your browser -

const call = (f, ...values) =>
  ({ type: call, f, values })

const recur = (...values) =>
  ({ type: recur, values })

const identity = x =>
  x

const loop = f =>
{ const aux1 = (expr = {}, k = identity) =>
    expr.type === recur
      ? call (aux, expr.values, values => call (aux1, f (...values), k))
  : expr.type === call
      ? call (aux, expr.values, values => call (aux1, expr.f (...values), k))
  : call (k, expr)

  const aux = (exprs = [], k) =>
    call
      ( exprs.reduce
          ( (mr, e) =>
              k => call (mr, r => call (aux1, e, x => call (k, [ ...r, x ])))
          , k => call (k, [])
          )
      , k
      )

  return run (aux1 (f ()))
}

const run = r =>
{ while (r && r.type === call)
    r = r.f (...r.values)
  return r
}

class Pair
{ constructor (car, cdr)
  { this.car = car
  ; this.cdr = cdr
  }
}

const pair = (car, cdr) =>
  new Pair(car, cdr)

const isPair = t =>
  t instanceof Pair

const nil =
  Symbol("nil")

const isNil = t =>
  t === nil

const isList = t =>
  isNil(t) || isPair(t)

const push = (r, v) =>
  (r.push(v), r)

const fromArray = (a = []) =>
  loop
    ( ( m = a
      , i = 0
      ) =>
        i >= m.length
          ? nil
          : call
              ( pair
              , Array.isArray(m[i])
                  ? recur(m[i], 0)
                  : m[i]
              , recur(m, i + 1)
              )
    )

const toString = (t = nil) =>
  loop
    ( ( m = t
      , r = []
      ) =>
        isNil(m)
          ? "(" + r.join(" ") + ")"
      : recur
          ( m.cdr
          , call
              ( push
              , r
              , isList(m.car)
                  ? recur(m.car, [])
                  : String(m.car)
              )
          )
    )


let a = ["hi"]
for (let i = 0; i < 20000; i++)
  a = [a]

document.body.textContent = toString(fromArray(a))
// ((((((((...((((((((hi))))))))...))))))))

body { overflow-wrap: anywhere; }

Answer 2

This is what I would do.

// range :: Number -> List Number
const range = n => enumFromTo(0, n - 1);

// enumFromTo :: (Number, Number) -> List Number
const enumFromTo = (m, n) => m > n ? null : {
    head: m,
    get tail() {
        return enumFromTo(m + 1, n);
    }
};

// showList :: List Number -> String
const showList = xs => xs === null ? "()" :
    `(${showListElements(xs.head, xs.tail)})`;

// (Number, List Number) -> String
const showListElements = (x, xs) => {
    let string = `${x}`;
    let variant = xs;

    while (variant !== null) {
        const { head, tail } = variant;
        string = `${string} ${head}`;
        variant = tail;
    }

    return string;
};

console.log(showList(range(40)));
console.log(showList(range(8000)));

As you can see, you don't really need trampolines at all. The only thing you do need is laziness.

You might also find the following Stack Overflow thread interesting.

How to encode corecursion/codata in a strictly evaluated setting?

Answer 3

I was able to create solution for recursive function that need to do something after recursion in trampoline by using continuations. Without continuation in Thunk there is no way to have ) as closing for the list. That need to be called when trampoline end but the code need to be specified in when Thunk is returned.

This will probably throw stack overflow error when nesting of list is very bing, but I think that for my case it's fine. It will work with range(8000) and will work for nested lists, so this is fine.

function Pair(car, cdr) {
  this.car = car;
  this.cdr = cdr;
}
const nil = new function Nil() {};

// ----------------------------------------------------------------------
Pair.fromArray = function(array) {
    var result = nil;
    var i = array.length;
    while (i--) {
        let car = array[i];
        if (car instanceof Array) {
            car = Pair.fromArray(car);
        }
        result = new Pair(car, result);
    }
    return result;
};

// ----------------------------------------------------------------------
function Thunk(fn, cont = () => {}) {
    this.fn = fn;
    this.cont = cont;
}

// ----------------------------------------------------------------------
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) {
        const thunk = result;
        result = result.fn();
        if (!(result instanceof Thunk)) {
            thunk.cont();
        }
    }
    return result;
}

// ----------------------------------------------------------------------
function toString(x) {
  return x.toString();
}

// ----------------------------------------------------------------------
const pair_to_string = (function() {
    const prefix = (pair, rest) => {
        var result = [];
        if (pair.ref) {
            result.push(pair.ref + '(');
        } else if (!rest) {
            result.push('(');
        }
        return result;
    };
    const postfix = (pair, rest) => {
        if (!rest || pair.ref) {
            return [')'];
        }
        return [];
    };
    return trampoline(function pairToString(pair, quote, extra = {}) {
        const {
            nested,
            result = [],
            cont = () => {
                result.push(...postfix(pair, nested));
            }
        } = extra;
        result.push(...prefix(pair, nested));
        let car;
        if (pair.cycles && pair.cycles.car) {
            car = pair.cycles.car;
        } else {
            car = toString(pair.car, quote, true, { nested: false, result, cont });
        }
        if (car !== undefined) {
            result.push(car);
        }
        return new Thunk(() => {
            if (pair.cdr instanceof Pair) {
                if (pair.cycles && pair.cycles.cdr) {
                    result.push(' . ');
                    result.push(pair.cycles.cdr);
                } else {
                    if (pair.cdr.ref) {
                        result.push(' . ');
                    } else {
                        result.push(' ');
                    }
                    return pairToString(pair.cdr, quote, {
                        nested: true,
                        result,
                        cont
                    });
                }
            } else if (pair.cdr !== nil) {
                result.push(' . ');
                result.push(toString(pair.cdr, quote));
            }
        }, cont);
    });
})();

// ----------------------------------------------------------------------
Pair.prototype.toString = function(quote) {
    var result = [];
    pair_to_string(this, quote, {result});
    return result.join('');
};

// ----------------------------------------------------------------------
function range(n) {
    return new Array(n).fill(0).map((_, i) => i);
}

// ----------------------------------------------------------------------
console.log(Pair.fromArray([[[range(8000), range(10)]]]).toString());