基于 Trampoline 的链表（lisp 树）与循环字符串

Question

我对 lisp 列表进行字符串化的基于蹦床的函数有问题。这是代码：

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");

问题是最后一个括号丢失了，我不确定我应该如何在 trampoline 中使用 continuation 来解决这个问题。

这是在没有蹦床的情况下工作的代码：

// ----------------------------------------------------------------------
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('');
};

我有两种情况，第一种是大列表（8000 个元素），另一种是小循环。使用堆栈片段中的代码，它可以处理长列表，但不能处理没有蹦床的循环，它会溢出大列表上的堆栈。它也是 lisp，所以它需要处理任何树，而不仅仅是链表。

编辑：如果您尝试回答，请至少不要更改数据结构。它需要与 car 和 cdr 配对 class，并且在将它们转换为字符串之前需要计算周期。所以它与多个函数一起工作，检查内存中的数据是否是循环的。

Answer 1

这就是我要做的。

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());

希望对您有所帮助。

基于 Trampoline 的链表（lisp 树）与循环字符串

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

javascript

recursion

continuations

trampolines