基于DeltaML的自调整计算技术解析

### 基于Delta ML的自调整计算技术解析 #### 1. 快速凸包算法 快速凸包算法用于计算一组圆的凸包。首先，它会计算初始分割线，该分割线的端点是最左边和最右边的圆（基于圆心位置）。基于这条分割线，算法分两步计算凸包： - 第一步计算下凸包。 - 第二步计算完整凸包。 具体步骤如下： 1. 确定初始分割线，端点为最左和最右的圆。 2. 将圆列表根据分割线分为两部分。 3. 如果剩余列表为空，凸包仅由左圆组成。 4. 如果剩余列表非空，找到圆心离分割线最远的圆 `max`。 5. 递归计算由左圆和 `max`，以及 `max` 和右圆定义的两条分割线对应的凸包。 #### 2. 自调整计算性能分析 自调整计算允许程序以传统非增量程序的方式响应数据修改。在分析自调整程序的性能时，主要考虑两个指标：从头执行的运行时间和变更传播的运行时间。 ##### 2.1 从头执行 分析自调整程序从头执行的运行时间与分析传统程序基本相同。可以将程序视为传统程序，其中所有自调整计算原语的期望时间为常数。在分析从头执行时间时，可以忽略自调整计算原语，实际运行时间仅慢一个期望常数因子。 ##### 2.2 稳定性和变更传播 为了分析变更传播的运行时间，需要先确定要处理的输入修改。通常考虑单位大小的修改（如单个插入、单个删除），因为批量修改的时间不会超过各部分时间之和。 变更传播的时间与两次运行之间的距离成正比。在定义运行之间的距离之前，需要识别相似的子计算。两个相同函数的调用如果参数和结果相等，则认为它们相似。 两个单调执行的距离定义为两次执行的对称差的大小。如果一个程序对于某些输入变更的两次执行之间的距离有界为 $O(f(n))$，则称该程序对于这些输入变更是 $O(f(n))$ 稳定的。如果是 $O(log^c n)$ 稳定的，则认为程序是稳定的。 ##### 2.3 稳定性编程 在计算程序的稳定性时，传统上通过可修改对象的身份（内存中的物理位置）进行比较，这使得稳定性测量对非确定性内存分配敏感。为了解决这个问题，可以为每个可修改对象标记一个唯一的键，并定义如果两个可修改对象具有相同的键，则它们相等。 Delta ML 语言通过 `mkPut` 函数支持这种带键的分配策略。`mkPut` 函数创建一个用于带键分配的新哈希表，并返回一个关联的放置器函数。放置器函数接受两个参数：要分配的可修改对象的键和要放入分配的可修改对象的值。 以下是 `mkPut` 函数的使用流程： 1. 使用 `mkPut` 创建一个新的哈希表和放置器函数。 2. 调用放置器函数，传入键和值。 3. 放置器函数会先检查哈希表中是否已有与该键关联的位置。 4. 如果有，则重用该位置；否则，分配一个新位置并插入到哈希表中。 #### 3. 可修改列表 可修改列表的类型为 `α modlist`，它是一个盒装单元，单元可以为空或为 `CONS` 单元，包含一个类型为 `α` 的元素和一个可修改列表。 与传统列表不同的是，每个单元的尾部放在一个可修改对象中，这使得可以通过插入/删除元素来修改列表内容。下面介绍三个列表函数的实现： ##### 3.1 lengthLessThan 该函数接受一个整数，返回一个盒装布尔值，表示列表的长度是否小于给定整数。实现时，每个列表函数会创建一个放置器，并定义一个局部作用域的工作函数来执行实际工作。 ``` structure ModList = struct datatype α cell = NIL | CONS of α * α modlist withtype α modlist = α cell box type α t = α modlist afun lengthLessThan ```