探索Hume语言：并发与功能的融合

### 探索Hume语言：并发与功能的融合 #### 1. 引言 在反应式函数式语言领域，有许多优秀的代表，如Concurrent Clean、Concurrent ML、Concurrent Haskell和Eden等。近年来，Frob（Functional Robotics）也崭露头角，它为定时事件、任务和行为提供了单子支持，并在耶鲁大学的机器人课程中得到了成功应用。Frob主要用于探索高级表达性的问题，而非控制系统、实时系统或有界空间。 #### 2. Hume设计理念 Hume采用了两级语言设计方法，将纯函数表达式层嵌入到描述通信进程的进程层中。与Embedded Gofer使用单子封装进程、Eden在函数表达式中使用进程构造、Concurrent ML使用有副作用的进程创建和通信构造不同，Hume通过引入语法上不同的进程表示法，并使用隐式通信，使这种分离更加明确。 成本稳定性是Hume设计的关键。其设计方式确保了可以为所有Hume语言构造构建形式化的成本模型和相关的正确性证明。为了给成本概念提供结构，设想了一系列重叠的语言子集，每个超集在表达式层增加了表达性，但可能会失去形式属性的某些可判定性，或者增加提供形式正确性/成本模型的难度。程序员可以通过选择合适的语言级别，在表达性和成本稳定性之间取得所需的平衡。 #### 3. 盒子与协调 为了支持并发，Hume需要计算和协调构造。Hume中计算的基本单位是盒子，它以函数方式定义了从输入到输出的有限映射。盒子通过布线指令连接成静态的并发进程网络，每个盒子引入一个进程。 Hume的抽象语法采用基于规则的方法，将相当传统的纯函数表达式表示法嵌入到异步进程模型中，这简化了表达式层的正确性证明和成本模型的构建。有四种非常规的表达式形式： - `⟨⟨...⟩⟩` 是向量模式或表达式； - `exp within constraint` 表示对时间或空间使用的可检查约束； - `exp as τ` 表示动态强制转换为指定类型 `τ`； - `*` 用于定义异步程序。 盒子是对应于（通常是有限的）状态机的进程抽象。一个Hume盒子由一组模式导向的规则、异常处理程序和类型信息组成。规则的左侧定义了规则可能激活的情况，右侧是规则激活并匹配相应模式时盒子的结果表达式。 例如，定义一个同时增加输入并将其作为固定宽度字符串输出的盒子 `inc`： ```haskell box inc in (nin :: int 32) out (nout ::int 32, nstr::string 11) match n -> (n+1, n as string 10 ++ "\n"); ``` 这个盒子首先指定了输入和输出的类型，然后定义了一个模式匹配规则，将输入的整数 `n` 增加1，并将 `n` 转换为固定宽度的字符串。 #### 4. 布线 盒子通过布线声明连接成静态进程网络，每根线将一个特定的盒子输出映射到一个特定的输入。每个盒子输出必须恰好连接到一个输入，每个输入必须恰好有一个输出连接到它。除了连接盒子的常规线外，输入/输出还可以连接到外部设备，如I/O流或硬件设备的端口，也可以指定线上出现的初始值。 例如，对 `inc` 盒子进行布线： ```haskell wire inc.nout to inc.nin initially 0; wire inc.nstr to output; stream output to "std_out"; ``` #### 5. 协调 Hume中基本的盒子执行周期如下： 1. 检查所有盒子输入的可用性并锁定输入值； 2. 依次将盒子输入与盒子规则进行匹配； 3. 消耗所有盒子输入； 4. 将变量绑定到输入值并计算所选规则的右侧； 5. 将盒子输出写入相应的线。 关键问题是线上输入和输出值的管理。在Hume模型中，输入线和输出线是一一对应的，且每根线都是单缓冲的。这确保了通信缓冲区的大小是有界的，避免了无缓冲时可能出现的同步问题。 盒子执行周期完成并将所有输出写入相应的线缓冲区后，盒子在下一个调度周期中可执行，这提高了并发性，避免了不必要的同步。需要注意的是，单个Hume盒子永远不会终止，程序终止发生在没有盒子可运行且未来没有外部输入可用时，这反映了嵌入式系统领域的要求。 #### 6. 异步协调构造 许多实时应用受益于异步性。Hume通过忽略某些输入/输出和引入公平匹配来引入异步协调。基本的盒子执行周期需要进行如下更改： 1. 根据可能的匹配检查输入可用性并锁定可用输入值； 2. 依次将可用输入与盒子规则进行匹配； 3. 消耗那些已匹配且在所选规则中未被忽略的输入； 4. 将变量绑定到输入值并计算所选规则的右侧； 5. 将未被忽略的输出写入相应的线； 6. 根据公平性标准重新排序匹配规则。 例如，定义一个公平合并操作： ```haskell box merge in ( xs :: int 32, ys :: int 32) out ( xys :: int 32) fair (x, *) -> x | (*, y) -> y ; ``` `*` 模式表示相应的输入位置应被忽略，它匹配任何输入但不消耗它。与通配符/变量模式不同，通配符/变量模式成功匹配会从输入缓冲区中移除相应的输入值。 #### 7. 线程调度 原型Hume抽象机实现维护一个线程向量，每个盒子对应一个线程，每个线程有自己的线程状态记录，包含状态信息和与输入/输出线的链接。线由值和有效性标志组成，标志在输出写入线时原子地设置为真，在输入被消耗时重置为假。 线程由内置调度器控制，目前实现的是轮询调度。如果某个线程的任何规则执行所需的所有输入都可用，则该线程被视为可运行。编译器指定的矩阵用于确定是否需要