Что именно делает стратегия внешнего визита в Rascal?

visitor rascal

125 просмотра

1 ответ

111 Репутация автора

Я написал приведенный ниже код Rascal, который должен строить дерево из карты от имен узлов к узлам, начиная с узла, отображенного сверху. Он должен многократно заменять дочерние элементы всех узлов, у которых есть строки в качестве дочерних result, узлами, с nodeMapкоторыми они сопоставляются, до тех пор, пока ничего не изменится (точка фиксирования).

getNodeвозвращает узел, map[str,node]которому он соответствует, или сам ключ, если его нет в качестве ключа на карте. Это прекрасно работает, что подтверждает тот факт, что другой код в нижней части этого вопроса работает. Тем не менее, приведенный ниже код, кажется, работает бесконечно даже на очень маленьких входах.

node nodeMapToNode(map[str, node] nodeMap) {
    node result = nodeMap["top"];
    return outermost visit(result) {
        case node n: {
            if ([*str children] := getChildren(n)) {
                insert makeNode(getName(n), [getNode(child, nodeMap) | child <- children]);
            }
        }
    }
}

Следующий код работает и мгновенно возвращается на небольших входах, как я и ожидал. Это, однако, именно то, что я понял, что внешнее посещение должно делать из того, что я понял из репетитора Rascal.

Может кто-нибудь объяснить мне, в чем разница между этими фрагментами кода (помимо того, как они написаны) и что я, таким образом, неправильно понял относительно эффекта outermost visit? Кроме того, я хотел бы знать, существует ли более короткий и / или более приятный способ написания этого кода - использование чего-то вроде внешнего посещения вместо написания точки фиксации вручную - существует.

node nodeMapToNode(map[str, node] nodeMap) {
    node result = nodeMap["top"];
    node lastResult;
    do {
        lastResult = result;
        result = visit(lastResult) {
            case node n: {
                if ([*str children] := getChildren(n)) {
                    insert makeNode(getName(n),
                        [getNode(child, nodeMap) | child <- children]);
                }
            }
        }
    } while (result != lastResult);
    return result;
}
Автор: Olav Trauschke Источник Размещён: 18.07.2016 07:33

Ответы (1)


2 плюса

13185 Репутация автора

Решение

Что самое внешнее?

Репетитор негодяев очень компактен в своем объяснении, но давайте начнем с этого.

повторять обход сверху вниз, пока обход изменяет полученное значение (вычислить фиксированную точку).

что в негодяйском выражении означает, что это:

r = outermost visit(x) {
  case str s => s + "."
    when size(s) < 3
};

является синтаксическим сахаром для:

r = x;
solve(r) {
  r = top-down visit(r) {
    case str s => s + "."
      when size(s) < 3
  };
}

Я думаю, что есть два наиболее распространенных случая, которые имеют внешний / внутренний смысл:

  • Ваша замена должна повторяться несколько раз на одном и том же узле
  • ваша замена генерирует новые узлы, которые соответствуют другим шаблонам

Ваш конкретный пример

По поводу примера в вашем вопросе. Другой вручную переписан outermostна самом деле innermost. Стратегия посещения по умолчанию bottom-up.

Как правило, восходящее посещение дерева происходит быстрее, чем нисходящее. Особенно, когда вы переписываете его, поскольку Rascal неизменен, создание нового дерева снизу вверх происходит быстрее.

Итак, возможно, замените ваш код innermostпосещением, а не внешним?

Автор: Davy Landman Размещён: 19.07.2016 08:30
Вопросы из категории :
32x32