亡羊补牢：Icicle 中的破坏性更新优化

Destructive Updates – A Stitch in Time

Source | HN Comments

文章介绍了 Icicle 语言通过优化破坏性更新来提升性能的方法。核心在于利用 Tardis Monad 和 Stitching Graph，在编译时分析代码中的数组引用，判断是否可以安全地省略复制操作，从而减少内存使用和运行时。文章详细阐述了优化动机、引用计数原理、内部DSL Avalanche 的构建、引用图的建立以及如何使用 Tardis Monad 进行正向和反向分析，最终实现复制省略，提升了性能。

Icicle

指南

亡羊补牢：Icicle 中的破坏性更新优化

发布于 2025 年 2 月 1 日，作者：Huw Campbell

Tardis Monad 和 Stitching Graph 如何帮助发现 affine array 的使用，从而允许破坏性更新。

Icicle 是一种高级流式查询语言，它为用户提供了新的能力，允许他们将数百个丰富的独立查询组合和融合到一个组合计划中，以实现安全高效的执行。该语言的核心是我们的 Core 中间语言，我们曾在之前的文章中讨论过它的优化。这是一个纯粹的、简单类型的基于 lambda 演算的 DSL，对任意递归和闭包创建进行了限制。为了确保速度，我们将所有查询编译为 C，并将几乎所有的数据类型转换为简单的、未装箱的 C 类型。例如，Either Int Bool 类型将被编译为堆栈上的三个 C 变量，分别表示标签和左右值变量。但是，语言中的 Map 和数组在转换为 C 时，使用 struct of arrays 的方法进行编译，从而编译成潜在的许多简单类型的 C 数组。然而，由于 Icicle Core 是一种纯语言，因此在降低级别时，编译器会在对数组执行任何突变之前插入复制操作。

这是一个关于我们如何通过在诸如插入 Map 或排序数组等操作期间执行破坏性更新，同时保持查询语义并将运行时减少高达 50% 的故事，从而消除惯用 Icicle 代码中的绝大多数复制操作。

动机查询

在 Icicle 查询中使用内置的 group 上下文非常常见，它有点像 SQL 的 group by。例如，以下查询查看一系列 injuries，然后计算一个从 locations 到 injuries 严重程度总和的 Map。

[](https://icicle-lang.github.io/posts/<#cb1-1>)from injury in
[](https://icicle-lang.github.io/posts/<#cb1-2>) group location in sum severity

在我们的 core 语言中，这将变成如下所示（省略错误处理）：

[](https://icicle-lang.github.io/posts/<#cb2-1>)STREAM_FOLD accum : Map String Double
[](https://icicle-lang.github.io/posts/<#cb2-2>) INIT:
[](https://icicle-lang.github.io/posts/<#cb2-3>)  Map []
[](https://icicle-lang.github.io/posts/<#cb2-4>) KONS:
[](https://icicle-lang.github.io/posts/<#cb2-5>)  let
[](https://icicle-lang.github.io/posts/<#cb2-6>)   severity =
[](https://icicle-lang.github.io/posts/<#cb2-7>)    get_severity# input
[](https://icicle-lang.github.io/posts/<#cb2-8>)
[](https://icicle-lang.github.io/posts/<#cb2-9>)   location =
[](https://icicle-lang.github.io/posts/<#cb2-10>)    get_location# input
[](https://icicle-lang.github.io/posts/<#cb2-11>)
[](https://icicle-lang.github.io/posts/<#cb2-12>)  in
[](https://icicle-lang.github.io/posts/<#cb2-13>)   Map_insertOrUpdate#
[](https://icicle-lang.github.io/posts/<#cb2-14>)    (\current -> add# current severity)
[](https://icicle-lang.github.io/posts/<#cb2-15>)    severity
[](https://icicle-lang.github.io/posts/<#cb2-16>)    location
[](https://icicle-lang.github.io/posts/<#cb2-17>)    accum

当编译为我们的较低级别 DSL，并最终编译为 C 时，此查询最终将由两个数组支持。当有新事件进入并被更新时，最好保持内存使用量与键的数量呈线性关系。然而，由于来自纯 Core DSL 的隐式复制操作，一种幼稚的方法最终可能使用与键的数量乘以 injuries 数量成正比的内存。

回顾 - 引用计数如何实现复制省略

R 编程语言在统计学家和数据科学家中很受欢迎，并且具有许多独特的属性。 R 中的大多数操作都是纯粹的和引用透明的，这对于它的易用性和安全性至关重要。它也是一种具有普遍向量化的语言。 R 的所有核心数据结构都是向量。原子向量巧妙地包装了 C 数组。但是，人们仍然希望他们的 R 代码具有相对较好的性能，并且为每个向量更新添加幼稚的复制操作会非常慢。看看这个 R 程序：

[](https://icicle-lang.github.io/posts/<#cb3-1>)>x  <-1:10
[](https://icicle-lang.github.io/posts/<#cb3-2>)>y  <-x
[](https://icicle-lang.github.io/posts/<#cb3-3>)>x[5] <-10
[](https://icicle-lang.github.io/posts/<#cb3-4>)>x
[](https://icicle-lang.github.io/posts/<#cb3-5>) [1] 1 2 3 4 10 6 7 8 9 10
[](https://icicle-lang.github.io/posts/<#cb3-6>)>y
[](https://icicle-lang.github.io/posts/<#cb3-7>) [1] 1 2 3 4 5 6 7 8 9 10

该程序维护了 R 的引用语义，但在底层发生了一些有趣的事情。有人可能会首先假设当 y 绑定到 x 时，会创建一个向量的副本，但那不是 R 在这里要做的事情。

在 R 中，名称只是引用值的方式，在这种情况下，将有两个名称指向原子向量 1:10；并且当 x 将被改变时，将在那个时间点创建一个支持数组的副本。

然而，这个程序会做一些非常不同的事情：

[](https://icicle-lang.github.io/posts/<#cb4-1>)>x  <-1:10
[](https://icicle-lang.github.io/posts/<#cb4-2>)>x[5] <-10
[](https://icicle-lang.github.io/posts/<#cb4-3>)>x
[](https://icicle-lang.github.io/posts/<#cb4-4>) [1] 1 2 3 4 10 6 7 8 9 10

在这个程序中，因为只有一个名称指向有问题的向量，所以该值将被就地更新。 R 可以执行此优化，因为它是一种引用计数的语言，并且当调用 []<- 函数时，它可以查看存在的引用数量 - 然后，如果只有一个引用（它本身），它知道它可以就地修改而不会使优化破坏程序的语义（参见Advanced R）。

采用此技术的其他语言包括 Lean proof assistant 和函数式编程语言 Koka，它也重用构造函数（如 list 的 cons）。

Icicle – 编译时复制省略

在 Icicle 中，我们避免使用引用计数，而是为每个实体使用一个简单的 bump 分配器。我们这样做是因为：

除了数组和字符串之外，所有绑定都直接放置在堆栈上；
它很快；
每个实体都单独运行，并且受到事件数量的限制；并且
它使得在完成处理实体后清除内存接近于微不足道。

也就是说，我们仍然应该以提高速度和内存效率为目标来减少新的数组分配，但在这里我们完全在编译时完成。

此优化的约束条件是：

如果不再访问原始数组，则应删除副本。
它不得更改查询的结果。
它不得过度降低编译速度。

要消除复制操作，我们需要确定两个关键因素：

在复制时可能指向数组的所有引用。
复制完成后使用的所有引用。

如果在将要复制的数组之后没有任何引用的后续使用，我们可以消除复制操作并简单地别名该绑定。但这提出了一个挑战：我们需要考虑的所有引用都来自复制操作之前；而所有用法都来自它之后。因此，在查询的任何时候，我们都需要对 AST 执行正向和反向传递才能知道该怎么做。最后，由于 Icicle 的语义本质上是一个严格的左折叠，它被编译为一个 for 循环，我们的内部 DSL 必须包含循环结构（for 和 while）。可以想象，即使是对未来和过去访问的定义也可能会变得有点模糊，因为每个循环都可以引用来自先前迭代的数据。

Avalanche - 我们的内部 DSL

我们在一个名为 Avalanche 的低级内部 DSL 中执行复制省略。这是一种小的命令式语言，包含基本的 if 和 foreach 语句；并且可以创建、读取和更新可变变量。它不执行 IO。作为 Haskell 类型，该语言看起来有点像这样：

[](https://icicle-lang.github.io/posts/<#cb5-1>)data Statement
[](https://icicle-lang.github.io/posts/<#cb5-2>) -- | A branch
[](https://icicle-lang.github.io/posts/<#cb5-3>) = If Exp Statement Statement
[](https://icicle-lang.github.io/posts/<#cb5-4>) -- | Loop while an accumulator reads true.
[](https://icicle-lang.github.io/posts/<#cb5-5>) | While Name Statement
[](https://icicle-lang.github.io/posts/<#cb5-6>) -- | Loop over facts
[](https://icicle-lang.github.io/posts/<#cb5-7>) | ForeachFacts Statement
[](https://icicle-lang.github.io/posts/<#cb5-8>) -- | Execute several statements in a block.
[](https://icicle-lang.github.io/posts/<#cb5-9>) | Block [Statement]
[](https://icicle-lang.github.io/posts/<#cb5-10>) -- | Local binding.
[](https://icicle-lang.github.io/posts/<#cb5-11>) | Let Name Exp Statement
[](https://icicle-lang.github.io/posts/<#cb5-12>) -- | Initialise an accumulator
[](https://icicle-lang.github.io/posts/<#cb5-13>) | InitAccumulator !Name !Exp Statement
[](https://icicle-lang.github.io/posts/<#cb5-14>) -- | Read from an accumulator into a local binding
[](https://icicle-lang.github.io/posts/<#cb5-15>) | Read Name Name Statement
[](https://icicle-lang.github.io/posts/<#cb5-16>) -- | Update an accumulator
[](https://icicle-lang.github.io/posts/<#cb5-17>) | Write Name Exp

其中 Exp 是一种简单的表达式类型，包含变量（Var）、原语和完全应用的应用。重要的是要注意 Let、InitAccumulator 和 Read 引入了作用域……它们包含可以使用引入的绑定的 Statement。为了简化生活，我们禁止在此 DSL 中进行阴影处理 - 源语言中的阴影绑定将被刷新。此外，我们应该注意 Avalanche 程序可能会变得非常大，例如，map 操作通常包括用于二分搜索的代码。典型的 Avalanche 程序还包含多达一百个用户查询的代码。

构建引用图

我们想要构建所有引用的有向图，以便我们可以确定是否会在程序的后面再次使用引用。由于这是 Haskell，我们使用一个纯粹的、持久的数据结构（这里由一对 Data.Map Name (Set Name) 支持），它指示向前和向后边。我们维护几个不变式：

如果由于删除导致 Set 变为空，则 Set 必须为非空，我们也会删除该键。
如果我们从图中删除一个键，我们会缝合它的传入和传出边。因此，如果删除 b，则图 a -> b -> c 将变为 a -> c。
- 这就是我们将其称为 Stitching Graph 的原因。
如果我们 overwrite 一条边（这是我们的主要 insert 操作），则该边将成为从起始键出发的唯一边。即，overwrite a c (overwrite a b empty) == overwrite a c empty。
如果我们有一个循环，例如 a -> b -> a 并删除 b，则缝合到 a -> a 将简化为无，并且该节点将被删除。

它的 API 看起来有点像这样：

[](https://icicle-lang.github.io/posts/<#cb6-1>)module Graph where
[](https://icicle-lang.github.io/posts/<#cb6-2>)
[](https://icicle-lang.github.io/posts/<#cb6-3>)data Graph
[](https://icicle-lang.github.io/posts/<#cb6-4>)
[](https://icicle-lang.github.io/posts/<#cb6-5>)-- | Insert an edge into a graph and remove existing ones
[](https://icicle-lang.github.io/posts/<#cb6-6>)--  from this node.
[](https://icicle-lang.github.io/posts/<#cb6-7>)overwrite :: Name -> Name -> Graph -> Graph
[](https://icicle-lang.github.io/posts/<#cb6-8>)
[](https://icicle-lang.github.io/posts/<#cb6-9>)-- | Delete a node and stitch up transiently connected nodes
[](https://icicle-lang.github.io/posts/<#cb6-10>)deleteAndStitch :: Name -> Graph -> Graph
[](https://icicle-lang.github.io/posts/<#cb6-11>)
[](https://icicle-lang.github.io/posts/<#cb6-12>)-- | Take the union of the maps
[](https://icicle-lang.github.io/posts/<#cb6-13>)merge :: Graph -> Graph -> Graph

因为这个结构共享得很好，所以在我们遍历程序的 AST 时构建和保留这个类型是可以的。在此初始示例中使用 State monad：

[](https://icicle-lang.github.io/posts/<#cb7-1>)go :: Statement -> State Graph Statement
[](https://icicle-lang.github.io/posts/<#cb7-2>)go statement =
[](https://icicle-lang.github.io/posts/<#cb7-3>) case statement of
[](https://icicle-lang.github.io/posts/<#cb7-4>)  --
[](https://icicle-lang.github.io/posts/<#cb7-5>)  -- Let bindings are a lot like reads and
[](https://icicle-lang.github.io/posts/<#cb7-6>)  -- initialisations if the expression is
[](https://icicle-lang.github.io/posts/<#cb7-7>)  -- a reference, then add to the graph.
[](https://icicle-lang.github.io/posts/<#cb7-8>)  Let nm x inner
[](https://icicle-lang.github.io/posts/<#cb7-9>)   | Just ref <- arrayReference x ->
[](https://icicle-lang.github.io/posts/<#cb7-10>)    Let nm x <$>
[](https://icicle-lang.github.io/posts/<#cb7-11>)     scopedGo nm ref inner
[](https://icicle-lang.github.io/posts/<#cb7-12>)
[](https://icicle-lang.github.io/posts/<#cb7-13>)   | otherwise ->
[](https://icicle-lang.github.io/posts/<#cb7-14>)    Let nm x <$>
[](https://icicle-lang.github.io/posts/<#cb7-15>)     scopedGo' nm inner
[](https://icicle-lang.github.io/posts/<#cb7-16>)
[](https://icicle-lang.github.io/posts/<#cb7-17>)  --
[](https://icicle-lang.github.io/posts/<#cb7-18>)  -- If the write is a reference, then we need
[](https://icicle-lang.github.io/posts/<#cb7-19>)  -- to know that this memory location has been
[](https://icicle-lang.github.io/posts/<#cb7-20>)  -- updated.
[](https://icicle-lang.github.io/posts/<#cb7-21>)  Write n x
[](https://icicle-lang.github.io/posts/<#cb7-22>)   | Just ref <- arrayReference x -> do
[](https://icicle-lang.github.io/posts/<#cb7-23>)    modify $
[](https://icicle-lang.github.io/posts/<#cb7-24>)     Graph.overwrite n ref
[](https://icicle-lang.github.io/posts/<#cb7-25>)
[](https://icicle-lang.github.io/posts/<#cb7-26>)    pure $ Write n x
[](https://icicle-lang.github.io/posts/<#cb7-27>)
[](https://icicle-lang.github.io/posts/<#cb7-28>)   | otherwise ->
[](https://icicle-lang.github.io/posts/<#cb7-29>)    pure $ Write n x
[](https://icicle-lang.github.io/posts/<#cb7-30>)
[](https://icicle-lang.github.io/posts/<#cb7-31>)  --
[](https://icicle-lang.github.io/posts/<#cb7-32>)  -- Traverse the block items in order.
[](https://icicle-lang.github.io/posts/<#cb7-33>)  Block inner ->
[](https://icicle-lang.github.io/posts/<#cb7-34>)   Block <$> traverse go inner
[](https://icicle-lang.github.io/posts/<#cb7-35>)
[](https://icicle-lang.github.io/posts/<#cb7-36>)  --
[](https://icicle-lang.github.io/posts/<#cb7-37>)  -- Run both sides and merge
[](https://icicle-lang.github.io/posts/<#cb7-38>)  If condition truth falsity -> do
[](https://icicle-lang.github.io/posts/<#cb7-39>)   aliased   <- get
[](https://icicle-lang.github.io/posts/<#cb7-40>)   let ~(truth',  tA) = runState (go truth) aliased
[](https://icicle-lang.github.io/posts/<#cb7-41>)   let ~(falsity', fA) = runState (go falsity) aliased
[](https://icicle-lang.github.io/posts/<#cb7-42>)
[](https://icicle-lang.github.io/posts/<#cb7-43>)   modify $
[](https://icicle-lang.github.io/posts/<#cb7-44>)    Graph.merge tA . Graph.merge fA
[](https://icicle-lang.github.io/posts/<#cb7-45>)
[](https://icicle-lang.github.io/posts/<#cb7-46>)   return $
[](https://icicle-lang.github.io/posts/<#cb7-47>)    If condition truth' falsity'
[](https://icicle-lang.github.io/posts/<#cb7-48>)
[](https://icicle-lang.github.io/posts/<#cb7-49>)  --
[](https://icicle-lang.github.io/posts/<#cb7-50>)  -- Reach a fixpoint, running until the
[](https://icicle-lang.github.io/posts/<#cb7-51>)  -- graph doesn't change anymore.
[](https://icicle-lang.github.io/posts/<#cb7-52>)  ForeachFacts inner -> do
[](https://icicle-lang.github.io/posts/<#cb7-53>)   ForeachFacts <$>
[](https://icicle-lang.github.io/posts/<#cb7-54>)    fixGo inner
[](https://icicle-lang.github.io/posts/<#cb7-55>)
[](https://icicle-lang.github.io/posts/<#cb7-56>)
[](https://icicle-lang.github.io/posts/<#cb7-57>) where
[](https://icicle-lang.github.io/posts/<#cb7-58>)  --
[](https://icicle-lang.github.io/posts/<#cb7-59>)  -- This introduces the alias for name to ref, then when it goes
[](https://icicle-lang.github.io/posts/<#cb7-60>)  -- out of scope, deletes this name and stitches up transient refs
[](https://icicle-lang.github.io/posts/<#cb7-61>)  -- as direct ones.
[](https://icicle-lang.github.io/posts/<#cb7-62>)  scopedGo nm ref ss = do
[](https://icicle-lang.github.io/posts/<#cb7-63>)   modify (Graph.overwrite nm ref)
[](https://icicle-lang.github.io/posts/<#cb7-64>)   sS <- go ss
[](https://icicle-lang.github.io/posts/<#cb7-65>)   modify (Graph.deleteAndStitch nm)
[](https://icicle-lang.github.io/posts/<#cb7-66>)   pure sS
[](https://icicle-lang.github.io/posts/<#cb7-67>)
[](https://icicle-lang.github.io/posts/<#cb7-68>)  --
[](https://icicle-lang.github.io/posts/<#cb7-69>)  -- Delete this name after it goes out of scope
[](https://icicle-lang.github.io/posts/<#cb7-70>)  -- (things might reference it).
[](https://icicle-lang.github.io/posts/<#cb7-71>)  scopedGo' nm ss =
[](https://icicle-lang.github.io/posts/<#cb7-72>)   sS <- go ss
[](https://icicle-lang.github.io/posts/<#cb7-73>)   modify (Graph.deleteAndStitch nm)
[](https://icicle-lang.github.io/posts/<#cb7-74>)   pure sS
[](https://icicle-lang.github.io/posts/<#cb7-75>)
[](https://icicle-lang.github.io/posts/<#cb7-76>)
[](https://icicle-lang.github.io/posts/<#cb7-77>)  --
[](https://icicle-lang.github.io/posts/<#cb7-78>)  -- Loops are interesting.
[](https://icicle-lang.github.io/posts/<#cb7-79>)  -- It's possible to write queries where after a pass is complete
[](https://icicle-lang.github.io/posts/<#cb7-80>)  -- accumulators depend on other accumulators initialised before
[](https://icicle-lang.github.io/posts/<#cb7-81>)  -- the loop began; so we need to reach a fixpoint on both the
[](https://icicle-lang.github.io/posts/<#cb7-82>)  -- initial alias map and the returned alias map.
[](https://icicle-lang.github.io/posts/<#cb7-83>)  --
[](https://icicle-lang.github.io/posts/<#cb7-84>)  -- If the maps don't match, rerun with the merged alias map on
[](https://icicle-lang.github.io/posts/<#cb7-85>)  -- the original statements.
[](https://icicle-lang.github.io/posts/<#cb7-86>)  fixGo ss = do
[](https://icicle-lang.github.io/posts/<#cb7-87>)   before <- get
[](https://icicle-lang.github.io/posts/<#cb7-88>)   sS   <- go ss
[](https://icicle-lang.github.io/posts/<#cb7-89>)   after <- get
[](https://icicle-lang.github.io/posts/<#cb7-90>)   let merged = Graph.merge before after
[](https://icicle-lang.github.io/posts/<#cb7-91>)   if before == merged then
[](https://icicle-lang.github.io/posts/<#cb7-92>)    pure sS
[](https://icicle-lang.github.io/posts/<#cb7-93>)   else do
[](https://icicle-lang.github.io/posts/<#cb7-94>)    set merged
[](https://icicle-lang.github.io/posts/<#cb7-95>)    fixGo ss
[](https://icicle-lang.github.io/posts/<#cb7-96>)
[](https://icicle-lang.github.io/posts/<#cb7-97>)
[](https://icicle-lang.github.io/posts/<#cb7-98>)  --
[](https://icicle-lang.github.io/posts/<#cb7-99>)  -- Whether this is a `Var` or a function which mutably
[](https://icicle-lang.github.io/posts/<#cb7-100>)  -- updates an array and returns it.
[](https://icicle-lang.github.io/posts/<#cb7-101>)  arrayReference :: Exp -> Maybe Name
[](https://icicle-lang.github.io/posts/<#cb7-102>)  arrayReference = \case
[](https://icicle-lang.github.io/posts/<#cb7-103>)   Var nm ->
[](https://icicle-lang.github.io/posts/<#cb7-104>)    Just nm
[](https://icicle-lang.github.io/posts/<#cb7-105>)   Exp.App (Exp.Prim Prim.SortInPlace) argument ->
[](https://icicle-lang.github.io/posts/<#cb7-106>)    arrayReference argument
[](https://icicle-lang.github.io/posts/<#cb7-107>)   ...

省略了 Read 和 InitAccumulator，因为它们看起来很像 Let；以及 While，因为它看起来像 ForeachFacts。

走进 Tardis

我们完成了正向传递，因此在任何时候我们都知道引用图的样子；但我们只完成了一半，因为我们不知道程序中稍后会使用哪些绑定。为此，我们需要向后传播信息，这要归功于惰性和反向状态 monad。提供正向和反向状态 Monad 的一个很好的组合的包是 tardis 包，它提供了 Tardis monad。在上面的代码清单中，我们切换到 Tardis monad 并将 get 替换为 getPast，将 modify 替换为 modifyForwards。此外，每次我们在 Exp 的 Var 中或作为命名项目（例如，Read）中看到 Name 时，我们都会向后发送用法（自由变量）

[](https://icicle-lang.github.io/posts/<#cb8-1>)go :: Statement -> Tardis (Set Name) Graph Statement
[](https://icicle-lang.github.io/posts/<#cb8-2>)go statement =
[](https://icicle-lang.github.io/posts/<#cb8-3>) case statement of
[](https://icicle-lang.github.io/posts/<#cb8-4>)  Let nm x ss
[](https://icicle-lang.github.io/posts/<#cb8-5>)   | Just ref <- arrayReference x ->
[](https://icicle-lang.github.io/posts/<#cb8-6>)    modifyBackwards (Set.delete nm . Set.union (Exp.freeVars x))
[](https://icicle-lang.github.io/posts/<#cb8-7>)    Let nm x <$>
[](https://icicle-lang.github.io/posts/<#cb8-8>)     scopedGo nm ref ss
[](https://icicle-lang.github.io/posts/<#cb8-9>)
[](https://icicle-lang.github.io/posts/<#cb8-10>)   | otherwise ->
[](https://icicle-lang.github.io/posts/<#cb8-11>)    modifyBackwards (Set.delete nm . Set.union (Exp.freeVars x))
[](https://icicle-lang.github.io/posts/<#cb8-12>)    Let nm x <$>
[](https://icicle-lang.github.io/posts/<#cb8-13>)     scopedGo' nm ss

因为我们还在向后遍历时删除了由 Let 和 friends 创建的绑定，所以我们实际上维护了在此向后传递中观察到的自由变量的 Set。

执行复制省略

我们的 Avalanche 阐述器将在执行任何变异操作（例如：堆排序或更新）之前发出复制操作，但幸运的是，它以一种非常可预测的方式发出这些操作 - 直接作为写入累加器的表达式。因此，除了 Statement 语法树之外，我们不需要太小心地将 Tardis 状态穿过 Exp 语法树，我们可以稍微作弊一下，并在 go 的定义中直接添加一个重写

[](https://icicle-lang.github.io/posts/<#cb9-1>)go statements =
[](https://icicle-lang.github.io/posts/<#cb9-2>) case statements of
[](https://icicle-lang.github.io/posts/<#cb9-3>)  --
[](https://icicle-lang.github.io/posts/<#cb9-4>)  -- Here's the key judgement and rewrite.
[](https://icicle-lang.github.io/posts/<#cb9-5>)  -- This write copies an array into an accumulator.
[](https://icicle-lang.github.io/posts/<#cb9-6>)  Write n x
[](https://icicle-lang.github.io/posts/<#cb9-7>)   | Exp.App (Exp.Prim Prim.ArrayCopy) (Exp.Var ref) <- x -> do
[](https://icicle-lang.github.io/posts/<#cb9-8>)    modifyBackwards (Set.insert ref)
[](https://icicle-lang.github.io/posts/<#cb9-9>)    aliased <- getPast
[](https://icicle-lang.github.io/posts/<#cb9-10>)    used  <- getFuture
[](https://icicle-lang.github.io/posts/<#cb9-11>)
[](https://icicle-lang.github.io/posts/<#cb9-12>)    --
[](https://icicle-lang.github.io/posts/<#cb9-13>)    -- It's important to add this ref when we're calculating
[](https://icicle-lang.github.io/posts/<#cb9-14>)    -- loop fixpoints.
[](https://icicle-lang.github.io/posts/<#cb9-15>)    modifyForwards $
[](https://icicle-lang.github.io/posts/<#cb9-16>)     Graph.overwrite n ref
[](https://icicle-lang.github.io/posts/<#cb9-17>)
[](https://icicle-lang.github.io/posts/<#cb9-18>)    pure $
[](https://icicle-lang.github.io/posts/<#cb9-19>)     --
[](https://icicle-lang.github.io/posts/<#cb9-20>)     -- Here's the important calculation.
[](https://icicle-lang.github.io/posts/<#cb9-21>)     -- Fortunately this is lazy, allowing us to "fix"
[](https://icicle-lang.github.io/posts/<#cb9-22>)     -- the Tardis.
[](https://icicle-lang.github.io/posts/<#cb9-23>)     if hasNoFurtherReferences n ref aliased used then do
[](https://icicle-lang.github.io/posts/<#