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

Question

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

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

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

Может кто-нибудь объяснить мне, какая разница между этими фрагментами кода (помимо того, как они написаны) и тем, что я таким образом неправильно понял о влиянии 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; 
} 

Answer 1

Что такое внешний вид?

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

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

который в Мошенник терминах означает, что это:

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, а не на внешний?