在DeltaML中实现自调整计算与CIRCLES项目

### 在Delta ML中实现自调整计算与CIRCLES项目 #### 1. 自调整计算基础 在进行自调整计算时，有一些关键的操作和原则需要遵循。首先，某些操作不应该在自适应函数内部使用，否则可能会破坏变更传播的正确性。 为了进行初始运行，系统提供了`call`原语。在元级别，初始运行的结果要么是一个普通值，要么是一个异常。具体来说，`call`操作接受一个自适应函数和该函数的一个参数，调用该函数，并将其结果或抛出的异常存储在一个普通引用中。需要注意的是，`call`操作是在另一个自适应函数体之外“应用”自适应函数的唯一方式。其结果是一个引用单元，包含自调整计算的输出（区分正常终止和异常终止）。 此外，还有一些用于操作输入和输出的操作： - `new`操作：将一个值放入一个盒子中，它是`put`操作的元版本。 - `deref`操作：返回盒子中的内容，它是`get`操作的元版本。 - `change`操作：接受一个值和一个盒子，并通过破坏性更新将盒子的内容修改为给定的值。 一个典型的突变器（mutator）通常会先设置输入并调用一个自适应函数进行初始运行。然后，它会与环境交互，修改自适应函数的输入或初始运行创建的其他数据，并通过调用元原语`propagate`来执行变更传播。当应用`propagate`原语时，它会合并自计算开始或上一次调用`propagate`以来执行的变更操作的效果。 #### 2. 实现CIRCLES项目 接下来，我们将详细介绍如何在Delta ML中实现CIRCLES项目。由于自调整计算通过变更传播便于与数据修改进行交互，我们只需要开发一个静态情况下的程序，即输入的圆列表不发生变化的情况。然后使用一个突变器来驱动这个程序与用户进行交互。 ##### 2.1 列表和几何数据结构 为了实现CIRCLES项目，我们需要定义一些列表和几何数据结构。 **可修改列表**：我们使用列表数据结构来表示圆的集合。为了能够插入和删除元素，我们定义了可修改列表。其定义如下： ```ocaml datatype α cell = NIL | CONS of α * α modlist withtype α modlist = α cell box ``` 一个类型为`α modlist`的可修改列表是一个由`α cell`类型的单元组成的链表。一个单元要么为空（`NIL`），要么是一个元素和一个可修改列表的组合（`CONS`）。与传统列表不同的是，`CONS`单元的尾部组件被装箱，这使得突变器可以通过更新尾部可修改项来改变可修改列表的内容。 我们还可以定义一些标准的列表操作，如下所示： ```ocaml signature MOD LIST = sig datatype α cell = NIL | CONS of α * α modlist withtype α modlist = α t type α t = α modlist val lengthLessThan: int -> α t -$> bool box val map: (α -> β) -> α t -$> β t val filter: (α -> bool) -> α t -$> α t val reduce: (α -> α -> α) -> α t -> α -$> β t end ``` - `lengthLessThan`函数：接受一个数字和一个列表，并返回一个布尔可修改项，指示列表的长度是否小于指定的数字。 - `map`函数：接受一个可以将列表元素映射到新值的函数和一个列表，返回通过将该函数应用于列表中的每个元素而得到的列表。 - `filter`函数：接受一个谓词和一个列表，返回输入列表中满足该谓词的元素列表。 - `reduce`函数：接受一个定义在列表元素上的关联二元操作、一个列表和当列表为空时返回的值，返回通过使用该操作组合列表的所有元素而得到的值。 **几何数据结构和操作**：为了对圆进行操作，我们使用了一些几何数据结构。定义了点和线的接口，以及一些几何操作： ```ocaml signature POINT = sig type t val fromXY: real * real -> t val toXY: t -> real * real end signature GEOMETRY = sig structure Point : POINT type point type line = point * point val toLeft : point * point -> bool val toRight : point * point -> bool val dist : point * point -> real val lineSideTest: line * point -> bool val distToLine: point * line -> real end ``` - `toLeft`和`toRight`操作：分别返回第一个点是否在第二个点的左侧或右侧。 - `dist`操作：返回两个点之间的距离。 - `lineSideTest`操作：返回一个点是否在一条线的上方。 - `distToLine`操作：返回一个点到一条线的距离。 我们还定义了圆的类型： ```ocaml type circle = Point.t * (string * string * real) ``` 其中，圆由一个点（圆心）和一个三元组的辅助信息（字符串ID、字符串颜色和浮点半径）组成。 ##### 2.2 实现突变器 假设我们有一个自调整函数`processCircles`，它接受一个圆列表，找到它们的直径，渲染它们，并返回直径上的圆的名称。其签名可以写成： ```ocaml processCircles: ModList.t -> (string * string) box ``` 下面是一个简化的突变器代码，它允许用户修改现有圆的属性： ```ocaml fun mutator () = let fun realFromString (str) = . . . fun prompt target str = let val = print str val tokens = String.tokens Char.isSpace (TextIO.input TextIO.stdIn) in case tokens of t::nil => if t = target then NONE else SOME tokens | => SOME tokens end fun mkCircle tokens = let val [id, color,xs,ys,rs] = tokens val (x,y,r) = (realFromString xs,realFromString ys, realFromString rs) in (Point.fromXY (x,y),(id,color,r)) end fun readCs cs = case (prompt "done" ("Enter circle or type ’done’ : /n")) of NONE => cs | SOME tk => let val c = mkCircle tk in readCs (new (L.CONS (c,cs))) end fun findAndModify cs id c = let fun isId ( ,(id’, , )) = id = id’ fun find f l = case deref l of L.NIL => raise BadInput | L.CONS (h,t) => if f h then SOME l else find f t val SOME m = find isId cs val L.CONS (h,t) = deref m in change (m,L.CONS (c,t)) end fun modify cs = case (prompt "quit" "Enter the circle to modify or type ’quit’./n") of NONE => () | SOME [id] => let val SOME tokens = prompt "" ("Enter circle: /n") val c = mkCircle tokens val = findAndModify cs id c val = (print ‘‘Propagating.../n’’; propagate (); print ‘‘Done./n’’) in modify cs end fun main () = let val = init () val = print "Welcome to circles!/n" val cs = readCs (new L.NIL) val = call (processCircles, cs) val = modify cs in () end in main () end ``` 这个突变器的主要流程如下： 1. `main`函数作为交互循环的入口，初始化自调整计算系统，打印欢迎消息，从用户那里读取圆的信息。 2. 调用`processCircles`函数计算直径并渲染圆。 3. 进入`modify`函数的修改 - 传播循环，允许用户修改圆的属性，并执行变更传播。 ##### 2.3 实现核心部分 核心部分的代码如下： ```ocaml fun map = . . . (* See Figure 10 *) fun reduce = . . . (* See Figure 11 *) fun quick hull l = . . . (* See Figure 9 *) mfun renderCircles l = let fun printC (c as (p,(id,color,r))) = let val (x,y) = Point.toXY p val s = id ^ " : " ^ color ^ " (" ^ Real.toString x ^ ", " ^ Real.toString y ^ ")" ^ " " ^ Real.toString r ^ "/n" in print ("Rendering circle = " ^ s ^ "/n"); end in case get $ l of L.NIL => () | L.CONS(h, t) => (printC h ; renderCircles t) end afun findDiameter l = let val putM = mkPut $ () fun maxDist (da as ( ,va),db as ( ,vb)) = if (Real.> (va,vb)) then da else db fun dist (a as (o a, (id a, ,r a))) (b as (o b, (id b, ,r b))) = Geom.dist (o a,o b) - r a - r b end mfun farthestFrom (c,l) => let val dist = map (dist c) $ l val max = reduce maxDist $ dist in get $ max end mfun findAllDist l = let val putM = mkPut $ () in case get $ l of L.NIL => putM $ (NONE, L.NIL) | L.CONS(h,t) => case get $ t of L.NIL => putM $ (NONE,L.NIL) | => let val m = farthestFrom $ (h,t) in putM $ (SOME m, L.CONS(m, findAllDist $ t)) end end val hull = quick hull $ l val dist = findAllDist $ hull val max = reduce maxDist $ dist val ((ida,idb), ) = get $ max val = print ("diameter = : " ^ ida ^ " x " ^ idb ^ "/n") in putM $ (NONE,(ida,idb)) end afun processCircles l = (renderCircles l ; findDiameter l) ``` 核心部分的主要功能如下： - `renderCircles`函数：遍历圆列表并打印每个圆的属性。由于输入是可修改列表，使用`get`原语访问其内容，并且该函数是自适应函数，因为它使用了自调整原语`get`。 - `findDiameter`函数：计算圆集合的直径。为了提高效率，首先计算圆中心的凸包，然后计算凸包上的圆的两两距离，最后选择最大距离作为直径。 ##### 2.4 实现Quickhull算法 为了计算凸包，我们使用了Quickhull算法。其代码如下： ```ocaml fun select f (a,b) = if f (a, b) then a else b fun above (cl as (pl, ), cr as (pr, )) (c as (p, )) = Geom.lineSideTest ((pl, pr), p) fun distToLine (cl as (pl, ), cr as (pr, )) (c as (p, )) = Geom.distToLine (p, (pl,pr)) afun split (bcl, bcr, l, hull) = let val putM = mkPut $ () mfun splitM (cl, cr, l, hull) = let val lf = L.filter (above (cl, cr)) $ l in if get $ (L.lengthLessThan 1 $ lf) then putM $ (cl, L.CONS (cl, hull)) else let val dist = distToLine (cl,cr) val selectMax = select (fn (c1,c2) => dist c1 > dist c2) val max = get $ (combine selectMax $ lf) in splitM $ (cl, max, lf, splitM $ (max, cr, lf, hull)) end end val (cl,cr) = (get $ bcl, get $ bcr) in splitM $ (cl, cr, l, hull) end afun quick hull l = if get $ (L.lengthLessThan 2 $ l) then l else let fun isMin (c1 as (p1, ), c2 as (p2, )) = Geom.toLeft (p1,p2) fun isMax (c1 as (p1, ), c2 as (p2, )) = Geom.toRight (p1,p2) val min = combine (select isMin) $ l val max = combine (select isMax) $ l val lower = split $ (max, min, l, put $ L.NIL) val hull = split $ (min, max, l, lower) in hull end ``` Quickhull算法的主要步骤如下： 1. 找到最左和最右的点。 2. 将点集分为两部分，分别在这两点连线的上方和下方。 3. 递归地在每一部分中找到距离连线最远的点，并将其加入凸包。 4. 重复步骤2和3，直到所有点都被处理。 ### 总结 通过以上步骤，我们完成了在Delta ML中实现CIRCLES项目的过程。从自调整计算的基础操作，到列表和几何数据结构的定义，再到突变器、核心部分和Quickhull算法的实现，每个部分都紧密协作，实现了一个能够处理圆集合的自调整计算系统。这个系统可以方便地处理圆的修改，并通过变更传播自动更新计算结果，提高了计算效率和用户交互的便利性。 下面是一个简单的mermaid流程图，展示了突变器的主要流程： ```mermaid graph TD; A[开始] --> B[初始化系统]; B --> C[打印欢迎消息]; C --> D[读取圆信息]; D --> E[调用processCircles函数]; E --> F[进入修改循环]; F --> G[用户输入修改信息]; G --> H[查找并修改圆]; H --> I[执行变更传播]; I --> F; ``` 同时，我们还可以用表格总结一些关键操作和函数： | 操作/函数 | 描述 | | --- | --- | | `call` | 进行初始运行，调用自适应函数 | | `new` | 将值放入盒子 | | `deref` | 返回盒子内容 | | `change` | 修改盒子内容 | | `propagate` | 执行变更传播 | | `processCircles` | 处理圆列表，计算直径并渲染 | | `renderCircles` | 渲染圆列表 | | `findDiameter` | 计算圆集合的直径 | | `quick hull` | 计算凸包 | ### 在Delta ML中实现自调整计算与CIRCLES项目 #### 3. 关键技术点分析 ##### 3.1 自调整计算的优势 自调整计算通过变更传播机制，使得系统能够在数据发生变化时自动更新计算结果，避免了重新计算整个过程，大大提高了计算效率。例如在CIRCLES项目中，当用户修改圆的属性时，系统可以通过`propagate`操作快速更新直径等计算结果，而不需要重新计算所有圆的距离。 ##### 3.2 可修改列表的设计 可修改列表的设计允许在运行时动态地插入和删除元素。通过将`CONS`单元的尾部组件装箱，使得突变器可以方便地修改列表内容。这种设计与传统列表有所不同，但提供了更大的灵活性。例如，在突变器中可以使用`change`操作修改列表中的元素。 ##### 3.3 凸包算法的选择 在计算圆集合的直径时，选择了Quickhull算法来计算凸包。该算法虽然不是渐近最优的，但在实际应用中表现良好。通过先计算凸包，再计算凸包上的圆的两两距离，可以减少不必要的计算，提高计算效率。因为直径上的圆一定在凸包上，所以只需要考虑凸包上的圆即可。 #### 4. 操作步骤总结 ##### 4.1 初始运行步骤 1. 使用`call`原语调用自适应函数进行初始运行，传入自适应函数和参数。 2. 初始运行的结果存储在一个引用单元中，区分正常终止和异常终止。 ##### 4.2 数据修改与变更传播步骤 1. 使用`new`操作创建可修改的输入。 2. 使用`deref`操作访问可修改内容。 3. 使用`change`操作修改可修改内容。 4. 调用`propagate`原语执行变更传播，合并变更操作的效果。 ##### 4.3 突变器操作步骤 1. 初始化自调整计算系统。 2. 打印欢迎消息，从用户那里读取圆的信息。 3. 调用`processCircles`函数计算直径并渲染圆。 4. 进入修改 - 传播循环，允许用户修改圆的属性，查找并修改圆，然后执行变更传播。 #### 5. 代码优化建议 ##### 5.1 查找效率优化 在突变器中查找要修改的圆时，可以使用辅助搜索结构，如哈希表，将圆的ID映射到包含该圆的`CONS`单元，以提高查找效率。 ##### 5.2 函数调用优化 对于一些频繁调用的函数，可以考虑进行内联优化，减少函数调用的开销。 ##### 5.3 内存管理优化 在处理大量数据时，要注意内存的使用情况，及时释放不再使用的内存，避免内存泄漏。 #### 6. 总结与展望 通过以上的实现和分析，我们成功地在Delta ML中实现了CIRCLES项目，展示了自调整计算的强大功能和优势。自调整计算可以有效地处理数据的动态变化，提高计算效率和用户交互的便利性。 未来，可以进一步扩展这个项目，例如支持更多的几何操作，如计算圆的交集、并集等。还可以优化算法，提高计算效率，特别是在处理大规模数据时。另外，可以考虑将该系统集成到更复杂的应用中，如计算机图形学、地理信息系统等领域。 下面是一个mermaid流程图，展示了计算圆集合直径的主要流程： ```mermaid graph TD; A[输入圆列表] --> B[计算凸包]; B --> C[计算凸包上圆的两两距离]; C --> D[选择最大距离作为直径]; D --> E[输出直径信息]; ``` 同时，我们用表格总结一下代码中的主要数据结构和类型： | 数据结构/类型 | 描述 | | --- | --- | | `α cell` | 可修改列表的单元，有`NIL`和`CONS`两种类型 | | `α modlist` | 可修改列表，由`α cell`组成 | | `circle` | 圆的类型，由点和辅助信息组成 | | `point` | 点的类型，支持坐标转换操作 | | `line` | 线的类型，由两个点组成 |