探索Manticore与非单子可变引用模型

### 探索Manticore与非单子可变引用模型 #### 1. Manticore语言与并行算法调整 Manticore是一种支持异构并行的语言，它将显式并发和隐式并行结合到一个通用的语言和执行框架中。在处理并行算法时，像Alpha - beta剪枝这种本质上是顺序的算法，需要进行一些调整。 Alpha - beta剪枝算法的调整过程如下： - 顺序计算一个子树作为起点。 - 使用该子树的值作为其余兄弟子树的剪枝阈值。 - 通过`pval`在内部循环中反复生成计算，并行计算这些兄弟子树。 - 当`pval`机制的隐式取消取消对特定子树右兄弟的评估时，就会发生剪枝。 Manticore的隐式并行机制为程序员提供了轻量级的语法提示，减轻了编排计算的负担。由于`val`声明绑定和`case`表达式是函数式程序员常用的习惯用法，提供隐式线程形式允许以熟悉的风格表达并行性。 #### 2. Manticore的现状与应用前景 Manticore语言的原型实现已经取得了稳步进展，大部分实现工作已经完成，并且能够运行中等规模的示例，如并行光线追踪器。不过，一些较新颖的特性，如`pcase`表达式形式，只有初步实现，还没有进行显著的优化。 Manticore有望更好地支持未来可能在通用处理器上运行的应用程序，如多媒体处理、计算机游戏、小规模模拟等。作为一种静态类型、严格的函数式语言，Manticore强调以值为导向且无突变的编程模型，避免了不同执行线程之间的纠缠。 #### 3. 非单子可变引用模型的提出 在函数式编程语言中，可变引用是常见的概念，在命令式语言中被称为指针。在纯函数式语言Haskell中，引用具有引用透明性且不存在类似空指针的引用，具有一定的安全性。Haskell有单子引用模型，即对引用的函数产生计算而不是值。 而在纯函数式语言Clean中，存在非单子引用模型的可能性，这些模型使用唯一堆。本文提出了一种基于唯一堆的可变引用模型，该模型对基本引用操作的评估顺序限制较少，具有更简单、更易处理的语义，并且支持堆之间的共享引用和堆的虚拟联合等特性。 #### 4. 模型特性与设计目标 该模型需要唯一性类型，这既可以看作是一个缺点，也可以看作是推动唯一性类型在函数式语言中传播的动力。模型设计的目标是提供一种更安全的引用模型，避免指针和引用带来的编程错误。 模型所包含的特性如下表所示： | 特性名称 | 引入位置 | 是否包含在提议模型中 | | ---- | ---- | ---- | | 堆种子 | 3.3节 | 否 | | 同质堆 | 3.5节 | 是 | | 单独种子 | 3.6节 | 是 | | 可删除引用 | 3.7节 | 是 | | 共享引用 | 3.8节 | 是 | | 堆的联合 | 3.9节 | 可选 | 对于每个模型，都存在具有相同接口的快速实现和纯实现，纯实现更简单，有助于理解模型的语义。 #### 5. Haskell中的单子引用模型 在Haskell的基础包中定义了两种类型的引用：`Data.IORef`模块中的IO - 引用和`Data.STRef`模块中的ST - 引用。 ##### 5.1 IO - 引用 IO - 引用的接口如下