Первоклассные переменные в JavaScript

Question

Я реализую алгоритм объединения в JavaScript, чтобы вычислить наиболее общий объединитель двух заданных терминов. Короче говоря, объединение - это процесс принятия двух терминов t1 а также t2 и объединяя их в новый термин t которая является специализацией обоих t1 а также t2, Рассмотрим (обратите внимание, что переменные пишутся с большой буквы):

t1 := foo(jane, A, B)
t2 := foo(X, Y, rocks)

Оператор специализации ⊏ обозначает, что "а является специализацией б" в a ⊏ b, Например:

foo(jane, doe, X)   ⊏ t1
foo(on, the, rocks) ⊏ t2

Объединитель двух терминов - это термин, который специализирует оба эти термина. Например:

foo(jane, street, rocks) ⊏ t1
foo(jane, street, rocks) ⊏ t2

Наиболее общий объединитель двух терминов - это объединитель этих двух терминов, который обобщает все остальные объединители этих двух терминов (т.е. все остальные объединители специализируются на самом общем объединителе). Например:

foo(jane, street, rocks) ⊏ foo(jane, M, rocks)

следовательно foo(jane, M, rocks) является наиболее общим объединителем t1 а также t2, Следующий алгоритм может быть использован для вычисления наиболее общего объединителя для терминов логики предикатов первого порядка.

1. Если оба t1 а также t2 являются константами, то они объединяются тогда и только тогда, когда они являются одной и той же константой (например, jane, street а также rocks являются постоянными).
2. Если t1 переменная и t2 является не переменным (то есть постоянным или комплексным термином), то t1 инстанцируется в t2 если и только если t1 не происходит в t2,
3. Если t2 переменная и t1 является не переменным (то есть постоянным или комплексным термином), то t2 инстанцируется в t1 если и только если t2 не происходит в t1,
4. Если t1 а также t2 Обе переменные, то они оба созданы друг для друга и, как говорят, разделяют значения.
5. Если оба t1 а также t2 являются сложными терминами, то они объединяются тогда и только тогда, когда они представляют собой один и тот же вид комплексного термина и соответствующие им аргументы объединяются.
6. Два термина объединяют, если и только если они объединяют, следуя приведенным выше пяти правилам.

Во всяком случае, вот как я хотел решить эту проблему:

function variable(name) {
    return {
        type: "variable",
        name: name,
        term: null
    };
}

function constant(name) {
    return {
        type: "non_variable",
        name: name,
        args: []
    };
}

function complex(name, args) {
    return {
        type: "non_variable",
        name: name,
        args: args
    };
}

Теперь мы можем определить t1 а также t2 следующее:

var t1 = complex("foo", [constant("jane"), variable("A"), variable("B")]);
var t2 = complex("foo", [variable("X"), variable("Y"), constant("rocks")]);

Затем мы реализуем алгоритм унификации:

function unify(a, b) {
    var x = resolve(a);
    var y = resolve(b);

    var operation = 0;

    if (x.type === "non_variable") operation += 2;
    if (y.type === "non_variable") operation += 1;

    switch (operation) {
    case 0:
        return x.term = y.term = variable(x.name);
    case 1:
        if (occurs(x, y)) throw new Error(x.name + " occurs in " + show(y));
        return x.term = y;
    case 2:
        if (occurs(y, x)) throw new Error(y.name + " occurs in " + show(x));
        return y.term = x;
    case 3:
        if (x.name !== y.name) throw new
            Error(x.name + " and " + y.name + " are different terms");

        var ax = x.args;
        var ay = y.args;

        if (ax.length !== ay.length) throw new
            Error(x.name + " and " + y.name + " have different arities");

        var args = ax.map(function (t, i) {
            return unify(t, ay[i]);
        });

        return complex(x.name, args);
    }
}

function resolve(t) {
    if (t.type === "non_variable") return t;

    var v = t;
    while (v.type === "variable" && v.term) v = v.term;
    return t.term = v;
}

function show(t) {
    return t.name + "(" + t.args.map(function (t) {
        return t.type === "non_variable" &&
           t.args.length > 0 ? show(t) : t.name;
    }).join(", ") + ")";
}

function occurs(v, t) {
    return t.args.some(function (t) {
        t = resolve(t);
        return t.type === "variable" ? t === v : occurs(v, t);
    });
}

И это работает:

var t = unify(t1, t2);

alert(show(t));

<script>
function variable(name) {
    return {
        type: "variable",
        name: name,
        term: null
    };
}

function constant(name) {
    return {
        type: "non_variable",
        name: name,
        args: []
    };
}

function complex(name, args) {
    return {
        type: "non_variable",
        name: name,
        args: args
    };
}

var t1 = complex("foo", [constant("jane"), variable("A"), variable("B")]);
var t2 = complex("foo", [variable("X"), variable("Y"), constant("rocks")]);

function unify(a, b) {
    var x = resolve(a);
    var y = resolve(b);

    var operation = 0;

    if (x.type === "non_variable") operation += 2;
    if (y.type === "non_variable") operation += 1;

    switch (operation) {
    case 0:
        return x.term = y.term = variable(x.name);
    case 1:
        if (occurs(x, y)) throw new Error(x.name + " occurs in " + show(y));
        return x.term = y;
    case 2:
        if (occurs(y, x)) throw new Error(y.name + " occurs in " + show(x));
        return y.term = x;
    case 3:
        if (x.name !== y.name) throw new
            Error(x.name + " and " + y.name + " are different terms");

        var ax = x.args;
        var ay = y.args;

        if (ax.length !== ay.length) throw new
            Error(x.name + " and " + y.name + " have different arities");

        var args = ax.map(function (t, i) {
            return unify(t, ay[i]);
        });

        return complex(x.name, args);
    }
}

function resolve(t) {
    if (t.type === "non_variable") return t;

    var v = t;
    while (v.type === "variable" && v.term) v = v.term;
    return t.term = v;
}

function show(t) {
    return t.name + "(" + t.args.map(function (t) {
        return t.type === "non_variable" &&
           t.args.length > 0 ? show(t) : t.name;
    }).join(", ") + ")";
}

function occurs(v, t) {
    return t.args.some(function (t) {
        t = resolve(t);
        return t.type === "variable" ? t === v : occurs(v, t);
    });
}
</script>

Однако у меня есть только одна проблема: способ, которым я реализовал первоклассные переменные, не очень хорош. Я реализовал это следующим образом:

1. Каждая переменная имеет term свойство, которое null изначально (чтобы показать, что переменная еще не была создана).
2. Когда переменная объединяется с не-переменной, ее term свойство установлено в не переменную, что хорошо.
3. Однако, когда переменная объединяется с другой переменной, возникает проблема. Мы не можем установить term свойство одной переменной к другой, потому что это приведет к циклической ссылке. Поэтому я создаю новую переменную и устанавливаю оба term свойства обеих переменных для новой переменной.
4. Это вызывает другую проблему. Если мы объединяем много переменных, то term цепь станет длиннее, поэтому мне нужно resolve функция в моем коде выше. Это пересекает term цепочка и возвращает последний член в цепочке.

Поэтому мой вопрос заключается в том, существует ли лучший способ создания первоклассных переменных в JavaScript (т. Е. Такой, в которой для совместного использования значений между двумя переменными не требуется использование term цепь). Если есть лучший способ, пожалуйста, опишите алгоритм.

Answer 1

Звучит так, как будто вы могли бы использовать disjoint-set-forest, членами которого были бы термины. Это имеет эффективный союз / поиск.

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

Небольшое прибегание к гуглу подтверждает, что это используется в реализациях объединения прологов.

http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=2318&context=cstech