Rascal 树上的顺序累积操作

Question

考虑到 Rascal 中数据的不变性，如果后面的操作依赖于前面的结果，那么首选的方法是什么？

例如，为树中的每个节点分配注释值，其中较高节点的值取决于较低节点的值。如果您编写包含多个案例的单个访问语句，则较低级别的插入语句不会更改树，因此较高级别的操作可能没有任何可操作的内容。另一方面，用访问语句围绕每个 case 语句——并在每次访问后将树变量重新绑定到新树——很麻烦，而且更糟的是，似乎使结果取决于语句的顺序。

Answer 1

微妙的问题 :-) visit 语句具有微妙的语义，特别是如果您从 OO 的角度来看它。在主动遍历一个值的同时，它也在重建一个新值。根据其 case 语句 "see" 中不同事物的遍历顺序匹配的策略（顺序）。

有时将 visit 想象成一个代码生成器是很有见地的，它生成一组相互递归的函数，这些函数将被访问的部分作为参数，return return 上的新值。访问的主体（案例）变成了 switch 语句，它是这些生成函数的核心。然后，根据遍历顺序，递归步骤要么位于 (bottom-up) 之前，要么位于此 switch 语句之后 (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 访问的 switch case 中的代码看到递归调用生成的树（尽管实际上没有更新树）。

这是一个例子：

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 节点已经被访问到 return 另一个已经递增的 i 节点之后。

试验其他策略会得到其他结果，请参阅 http://tutor.rascal-mpl.org/Rascal/Rascal.html#/Rascal/Expressions/Visit/Visit.html。请注意，访问语句范围内的变量由所有递归级别上的所有访问共享，这使得能够模拟类似拉链的行为（您始终可以将先前访问的节点存储在临时文件中）。

顺便说一句，语言设计试图避免需要更多复杂的东西 "functional programming design patterns"，例如 zippers，因为它们会使类型系统和人们与之交互的方式复杂化。为了使这些东西在对异构数据类型进行递归的访问中正确工作，您需要多态性博士学位才能理解它何时是正确的类型。秘密地，visit 语句模拟了一组内置的类型安全的 rank-2 高阶多态函数，但这都是在幕后。

Rascal 树上的顺序累积操作

Sequential, cumulative operations on Rascal trees

rascal