Trampoline based linked list (lisp tree) to string with cycles

Question

I have problem with my trampoline based function that stringify lisp list. Here is the code:

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;
}

// ----------------------------------------------------------------------
// original function have different data types here
// with simplified version this is fine
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);
}

// ----------------------------------------------------------------------------
function markCycles(pair) {
    var seen_pairs = [];
    var cycles = [];
    var refs = [];
    function visit(pair) {
        if (!seen_pairs.includes(pair)) {
            seen_pairs.push(pair);
        }
    }
    function set(node, type, child, parents) {
        if (child instanceof Pair) {
            if (parents.includes(child)) {
                if (!refs.includes(child)) {
                    refs.push(child);
                }
                if (!node.cycles) {
                    node.cycles = {};
                }
                node.cycles[type] = child;
                if (!cycles.includes(node)) {
                    cycles.push(node);
                }
                return true;
            }
        }
    }
    const detect = trampoline(function detect_thunk(pair, parents) {
        if (pair instanceof Pair) {
            delete pair.ref;
            delete pair.cycles;
            visit(pair);
            parents.push(pair);
            var car = set(pair, 'car', pair.car, parents);
            var cdr = set(pair, 'cdr', pair.cdr, parents);
            var thunks = [];
            if (!car) {
                detect(pair.car, parents.slice());
            }
            if (!cdr) {
                const cdr_args = [pair.cdr, parents.slice()];
                return new Thunk(() => {
                    return detect_thunk(...cdr_args);
                });
            }
        }
    });
    function mark_node(node, type) {
        if (node.cycles[type] instanceof Pair) {
            const count = ref_nodes.indexOf(node.cycles[type]);
            node.cycles[type] = `#${count}#`;
        }
    }
    detect(pair, []);
    var ref_nodes = seen_pairs.filter(node => refs.includes(node));
    ref_nodes.forEach((node, i) => {
        node.ref = `#${i}=`;
    });
    cycles.forEach(node => {
        mark_node(node, 'car');
        mark_node(node, 'cdr');
    });
}
// ----------------------------------------------------------------------
// this works fine
//console.log(Pair.fromArray([[[range(8000), range(10)]]]).toString());
var data = new Pair(1, new Pair(new Pair(2, nil), new Pair(3, nil)));
data.cdr.car.cdr = data.cdr;
data.cdr.cdr.cdr = data;
markCycles(data)
console.log(data.toString());
console.log("#0=(1 . #1=((2 . #1#) 3 . #0#)) - valid");

The problem is the last parenthesis is missing, I'm not sure how I should use continuation in trampoline to fix the issue.

Here is the code that was working without trampoline:

// ----------------------------------------------------------------------
Pair.prototype.toString = function(quote, rest) {
    var arr = [];
    if (this.ref) {
        arr.push(this.ref + '(');
    } else if (!rest) {
        arr.push('(');
    }
    var value;
    if (this.cycles && this.cycles.car) {
        value = this.cycles.car;
    } else {
        value = toString(this.car, quote, true);
    }
    if (value !== undefined) {
        arr.push(value);
    }
    if (this.cdr instanceof Pair) {
        if (this.cycles && this.cycles.cdr) {
            arr.push(' . ');
            arr.push(this.cycles.cdr);
        } else {
            if (this.cdr.ref) {
                arr.push(' . ');
            } else {
                arr.push(' ');
            }
            const cdr = this.cdr.toString(quote, true);
            arr.push(cdr);
        }
    } else if (this.cdr !== nil) {
        arr = arr.concat([' . ', toString(this.cdr, quote, true)]);
    }
    if (!rest || this.ref) {
        arr.push(')');
    }
    return arr.join('');
};

I have two cases that should work first big list (8000 elements) and small cycle. With the code in stack snippet it work with long list but not with cycles without the trampoline it overflow the stack on big list. Also it's lisp so it need to work any any tree not only linked list.

EDIT: if you try to answer please at least don't change the data structures. It need to be Pair class with car and cdr and cycles need to be calculated before they are converted to string. So it work with multiple functions that check if data in memory is cycle.

Answer 1

This is what I would do.

const pure = value => ({ constructor: pure, value });

const bind = (monad, arrow) => ({ constructor: bind, monad, arrow });

const thunk = eval => ({ constructor: thunk, eval });

function evaluate(expression) {
    let expr = expression;
    let stack = null;

    while (true) {
        switch (expr.constructor) {
            case pure:
                if (stack === null) return expr.value;
                expr = stack.arrow(expr.value);
                stack = stack.stack;
                break;
            case bind:
                stack = { arrow: expr.arrow, stack };
                expr = expr.monad;
                break;
            case thunk:
                expr = expr.eval();
        }
    }
}

const monadic = func => thunk(() => {
    const gen = func();

    function next(data) {
        const { value, done } = gen.next(data);
        return done ? value : bind(value, next);
    }

    return next(undefined);
});

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

    static fromArray(array) {
        const loop = (array, index) => monadic(function* () {
            if (index === array.length) return pure(null);
            const item = array[index];
            const car = Array.isArray(item) ? yield loop(item, 0) : item;
            const cdr = yield loop(array, index + 1);
            return pure(new Pair(car, cdr));
        });

        return evaluate(loop(array, 0));
    }

    duplicates() {
        const visited = new WeakSet();
        const result = new WeakSet();

        const loop = pair => monadic(function* () {
            if (visited.has(pair)) {
                result.add(pair);
            } else {
                visited.add(pair);
                const { car, cdr } = pair;
                if (car instanceof Pair) yield loop(car);
                if (cdr instanceof Pair) yield loop(cdr);
            }

            return pure(result);
        });

        return evaluate(loop(this));
    }

    toString() {
        let result = "";

        const duplicates = this.duplicates();
        const visited = [];

        const loop = (pair, end) => monadic(function* () {
            const index = visited.indexOf(pair);

            if (index < 0) {
                const duplicate = duplicates.has(pair);

                if (duplicate) {
                    const last = visited.push(pair) - 1;
                    result += end ? ` . #${last}=(` : `#${last}=(`;
                } else result += end ? " " : "(";

                const { car, cdr } = pair;

                if (car instanceof Pair) yield loop(car, false);
                else result += JSON.stringify(car);

                if (cdr instanceof Pair) yield loop(cdr, true);
                else if (cdr === null) result += ")";
                else result += ` . ${JSON.stringify(cdr)})`;

                if (duplicate && end) result += ")";
            } else {
                result += end ? ` . #${index}#)` : `#${index}#`;
            }

            return pure(result);
        });

        return evaluate(loop(this, false));
    }
}

const data = new Pair(1, new Pair(new Pair(2, null), new Pair(3, null)));
data.cdr.car.cdr = data.cdr;
data.cdr.cdr.cdr = data;

console.log(data.toString());

const range = length => Array.from({ length }, (x, i) => i);

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

Hope that helps.