Последовательные, кумулятивные операции над деревьями мошенников

Question

Учитывая неизменность данных в Rascal, каков предпочтительный метод для них, если последующие операции зависят от результатов предыдущих?

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

Answer 1

Тонкий вопрос :-) Заявление visit имеет тонкую семантику, особенно если вы посмотрите на него с точки зрения ОО. Пока он активно перемещается по ценности, он также перестраивает новую. В зависимости от стратегии (порядка) последовательных совпадений обхода в его заявлении дела «видят» разные вещи.

Иногда можно представить себе визит как генератор кода, который генерирует набор взаимно-рекурсивных функций, которые принимают посетившую часть в качестве аргумента и возвращают новое значение при возврате. Тело посещения (случаи) превращается в оператор switch, который является ядром этих сгенерированных функций. Затем, в зависимости от порядка обхода, рекурсивные шаги либо расположенные перед (bottom-up) или после этого переключателя оператора (top-down):

// bottom-up visit 
x f(value x) { 
    newChildren = map(f, children of x); 
    x = newX(x, newChildren); 
    switch (x) { 
    case y : return whatever(y); 
    } 
} 

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

Вот пример:

rascal>data T = tee(T, T) | i(int i); 
data T = tee(T, T) | i(int i); 
ok 
rascal>t = tee(tee(i(1),i(2)),tee(i(3),i(4))); 
t = tee(tee(i(1),i(2)),tee(i(3),i(4))); 
T: tee(
    tee(
    i(1), 
    i(2)), 
    tee(
    i(3), 
    i(4))) 
rascal>visit(t) { 
>>>>>>> case i(x)  => i(x+1) 
>>>>>>> case tee(i(x),y) => tee(i(x+1),y) 
>>>>>>>} 
T: tee(
    tee(
    i(3), // here you see how 1 turned into 3 by incrementing twice 
    i(3)), // increment happened once here 
    tee(
    i(5), // increment happened twice here too 
    i(5))) // increment happened once here 

Вы можете видеть, что некоторые узлы имели прирост в два раза, потому что второй случай согласованный один tee после его ребенок i узел уже посетил вернуть другой i узел, который уже увеличилось.

Эксперимент с другими стратегиями даст вам другие результаты, см. http://tutor.rascal-mpl.org/Rascal/Rascal.html#/Rascal/Expressions/Visit/Visit.html. Обратите внимание, что переменные, входящие в объем заявления о посещении, делятся всеми посещениями всех уровней рекурсии, которые дают возможность эмулировать поведение в стиле застежки-молнии (вы всегда можете сохранить ранее посещаемый узел во временном порядке).

В качестве альтернативы, языковой дизайн пытается избежать необходимости использования более сложных «шаблонов проектирования функциональных программ», таких как молнии, потому что они усложняют систему типов и способ взаимодействия людей с ней. Чтобы эти вещи правильно отображались в ходе посещения, который выполняет рекурсию по гетерогенному типу данных, вам нужен PhD в полиморфизме, чтобы понять, когда он корректен. Втайне, заявление о посещении имитирует набор встроенных полиморфных функций более высокого порядка второго порядка, но это все под капотом.