Haskell 中的数字电路模拟器

# Haskell 中的数字电路模拟器（SICP 3.3） 来源：https://entropicthoughts.com/sicp-3-3-digital-circuit-simulator-in-haskell sicp-3-3-digital-circuit-simulator-in-haskell.jpg 我有一本 **sicp**，也被称为《巫师书》¹¹*《计算机程序的构造与解释》*；Abelson 与 Sussman；MIT Press；1996 年。这本书广受赞誉，但我无法抽出时间通读全书。相反，我会偶尔跳入其中感兴趣的部分。 在这个系列的前两篇文章中，我们研究了实现泛型函数的方法。第一篇中，我们通过标记值并基于标签分派操作（https://entropicthoughts.com/sicp-2-4-tagged-data-in-haskell）。第二篇中，我们通过填充一个操作-标签对的可变表（https://entropicthoughts.com/sicp-2-4-data-directed-programming-in-haskell）。我们看到了这些方法与 Haskell 现有的和类型及类型类是多么地相似。 现在我们将模拟一个数字电路。这之所以有趣，是因为 **sicp** 中的解决方案使用了隐藏的可变状态和消息传递来使代码面向对象。它甚至使用了一个可变的全局变量进行调度！我不确定在 Haskell 中能否复制这一点，但正如我们将看到的，它可以做到非常接近。 ## Haskell 确实有可变变量 (https://entropicthoughts.com/sicp-3-3-digital-circuit-simulator-in-haskell#haskell-does-have-mutable-variables) 在 Haskell 中有许多实现可变状态的方法，但首先，我们将采用与 **sicp** 解决方案最相似的方法：`IORef`。`IORef` 是一个可变变量，与其他任何编程语言一样²²。唯一的主要区别是，我们需要一些额外的机制来读取它，因为它被设计成无法在纯代码中意外读取（毕竟那会使代码变为不纯）。 我们定义一个类型 `Wire`，它初始时信号为 `Low`，并且有一个空的 *动作过程* 列表。 动作过程的概念来源于 **sicp** 对此代码的实现；动作过程是这条线上信号的订阅者，每当信号变化时它们会被调用。动作过程将由连接在该线下游的组件安装，这样当线值变化时，这些组件可以更新自己。 在 [1]： `` data Signal = Low | High deriving (Show, Eq, Ord, Bounded) data Wire = Wire { action_procedures :: IORef [IO ()] , signal_value :: IORef Signal } make_wire = do initial_procs <- newIORef [] initial_signal <- newIORef Low pure (Wire initial_procs initial_signal) `` 我们可以通过读取存放当前信号的可变变量来获取线上的信号。 在 [2]： `` get_signal (Wire _ signal) = readIORef signal `` 要设置线上的信号，我们写入可变变量。如果这引起了线的状态变化，我们还会运行已安装的动作过程来通知下游组件³³。这就是观察者模式，如果您听起来熟悉的话。 在 [3]： `` set_signal (Wire procs signal) new_value = do current <- readIORef signal when (new_value /= current) $ do writeIORef signal new_value actions <- readIORef procs sequence_ actions `` 最后，我们在线上有一个方法，允许下游组件安装新的动作过程。为了确保在连接组件时线得以正确的值初始化，我们立即运行所有安装的动作过程。 在 [4]： `` add_action (Wire procs _) action = do modifyIORef procs (action:) action `` 在 **sicp** 实现中，*probe* 是安装在线上并向程序用户报告线值的动作过程。 在 [5]： `` probe name wire = add_action wire $ do current <- get_signal wire putStrLn (name <> " new value: " <> show current) `` 至此，线对象已完成，我们可以在 REPL 中试验它。我们创建一条线并添加一个探测器。如果我们将它的信号设置成之前的值，什么也不会发生。如果我们将信号设置成一个新值，探测器就会触发。 在 [6]： `` λ> w <- make_wire λ> probe "wire" w wire new value: Low λ> set_signal w Low λ> set_signal w High wire new value: High `` 然后我们可以开始实现最基本的组件。`inverter` 与 **sicp** 实现中一样，是输入线上的一个动作过程，它将输出线上的信号设置为输入的反向。 在 [7]： `` inverter input output = add_action input $ do current <- get_signal input set_signal output $ case current of Low -> High High -> Low `` `and_gate` 工作方式类似，只是在确定输出之前读取两个输入。 在 [8]： `` and_gate a1 a2 output = let action = do c1 <- get_signal a1 c2 <- get_signal a2 set_signal output $ case (c1, c2) of (Low, Low) -> Low (Low, High) -> Low (High, High) -> High (High, Low) -> Low in do add_action a1 action add_action a2 action `` `or_gate` 与 `and_gate` 类似，只是真值表不同⁴⁴。就像一个真正的数字电路设计师，我已经用格雷码写出了真值表。 在 [9]： `` or_gate a1 a2 output = let action = do c1 <- get_signal a1 c2 <- get_signal a2 set_signal output $ case (c1, c2) of (Low, Low) -> Low (Low, High) -> High (High, High) -> High (High, Low) -> High in do add_action a1 action add_action a2 action `` 到目前为止，我们这里没有发明任何新东西；这一切都与 **sicp** 的实现一致。这个 Abelson 与 Sussman 的设计有三个简洁的特性： - 组件集合是开放的。如果我们将此转化为一个库，库的任何用户都可以添加自己的组件，并且他们的组件能与我们的组件完美交互。 - 组件的输入或输出数量不限。任何从线读取并写入其他线的都是有效的组件。 - 我们可以将这些基本门组合成高级组件，就像普通的语句过程一样。 后者意味着我们可以通过组合门来制造半加器，以及通过组合半加器和门来制造全加器。 在 [10]： `` half_adder a b s c = do d <- make_wire e <- make_wire or_gate a b d and_gate a b c inverter c e and_gate d e s full_adder a b c_in sum c_out = do s <- make_wire c1 <- make_wire c2 <- make_wire half_adder b c_in s c1 half_adder a s sum c2 or_gate c1 c2 c_out `` 这些都直接来自 **sicp** 的实现。目前我们唯一缺少的是一个模拟传播延迟的调度器。 ## 添加带有全局可变状态的调度器 (https://entropicthoughts.com/sicp-3-3-digital-circuit-simulator-in-haskell#adding-a-scheduler-with-global-mutable-state) 在 **sicp** 中，调度器被实现为一个全局可变变量。这让任何组件都可以隐式地访问它进行调度。让我们全力以赴，在 Haskell 中也这样做。 等等，Haskell 甚至能 *做* 这个？ 是的。看看定义 `the_agenda` 的最后一行。*真恶心！* 请永远不要在生成环境中这样做。全局可变状态是一个 *可怕* 的主意⁵⁵。这在任何编程语言中都是坏主意。但在 Haskell 中更糟糕，因为这样我们就会放弃只有 Haskell 能提供的一系列额外保证。 在 [11]： `` data Agenda = Agenda { current_time :: IORef Int , segments :: IORef (Map.Map Int [IO ()]) } make_agenda = do time <- newIORef 0 segs <- newIORef Map.empty pure (Agenda time segs) the_agenda = unsafePerformIO make_agenda `` Agenda 遵循 **sicp** 中的实现，维护了当前时间的可变变量，以及一个有序的时间列表和对应时间要执行的动作过程⁶⁶。在 **sicp** 中，他们使用一个链表并手动维护使其有序。我们也可以在 Haskell 中那样做，但这里我们偷懒，使用标准库中的有序字典。 `propagate` 函数使用这个 Agenda 模拟电路直到稳定。它从 Agenda 中弹出最小的下一个时间步，将当前时间更新为那个时间，并执行与之关联的动作。它重复这个过程，直到没有更多计划的时间步。 在 [12]： `` propagate = do segs <- readIORef (segments the_agenda) case Map.minViewWithKey segs of Nothing -> pure () Just ((time, actions), remaining) -> do writeIORef (current_time the_agenda) time writeIORef (segments the_agenda) remaining sequence_ actions propagate `` **sicp** 代码中有一个 `after_delay` 函数，帮助组件在各自的传播延迟之后安排更新。我们将实现相同的功能。 在 [13]： `` after_delay delay action = do time <- readIORef (current_time the_agenda) modifyIORef (segments the_agenda) $ Map.insertWith (<>) (delay + time) [action] `` 现在组件需要使用这个，这样它们只在延迟后更新输出，而不是立即更新。这意味着在所有组件中，在 `set_signal` 之前插入一个 `after_delay` 调用。这里以反相器为例展示。 在 [14]： `` inverter input output = add_action input $ do current <- get_signal input after_delay 2 $ do set_signal output $ case current of Low -> High High -> Low `` 我们还希望探测器在读取时显示当前时间。 在 [15]： `` probe name wire = add_action wire $ do current <- get_signal wire time <- readIORef (current_time the_agenda) putStrLn (name <> " (t=" <> show time <> ") new value: " <> show current) `` 就这样！现在我们完成了，可以打开 REPL 并运行与 Abelson 和 Sussman 相同的交互，以测试我们的代码是否与 **sicp** 代码行为相同。 在 [16]： `` λ> input_1 <- make_wire λ> input_2 <- make_wire λ> sum <- make_wire λ> carry <- make_wire λ> probe "sum" sum sum (t=0) new value: Low λ> probe "carry" carry carry (t=0) new value: Low λ> half_adder input_1 input_2 sum carry λ> set_signal input_1 High λ> propagate sum (t=8) new value: High λ> set_signal input_2 High λ> propagate carry (t=11) new value: High sum (t=16) new value: Low `` 实际上，Haskell 解决方案与 **sicp** 中的有多么接近，让我感到惊讶。它们几乎是一样的。我能想到的唯一主要区别是，由于 `the_agenda` 是 Haskell 中的顶级绑定，我们无法在 REPL 中重新赋值它。但也就这样了。 我们还可以做一些 **sicp** 作者从未展示的有趣事情：环形振荡器。如果我们把反相器的输出连接到自身，进行探测，然后传播，就会得到一个无限序列： 在 [17]： `` --------------- >8 ------- a (t=4558) new value: High a (t=4560) new value: Low a (t=4560) new value: High a (t=4562) new value: Low a (t=4562) new value: High a (t=4564) new value: Low a (t=4564) new value: High a (t=4566) new value: Low a (t=4566) new value: High a (t=4568) new value: Low --------------- >8 ------- `` 其中输出在每个传播延迟切换。 ## 下一个挑战：使其纯粹 (https://entropicthoughts.com/sicp-3-3-digital-circuit-simulator-in-haskell#next-challenge--making-it-pure) 上面的代码是没问题的。它充满了副作用，但 *它没问题*。 很多人似乎认为 Haskell 代码必须没有副作用，但事实并非如此。Haskell 代码不需要是一个纯净的抽象塔连接到一个肮脏的效果层。Haskell 代码可以像其他任何语言的代码一样——大部分是肮脏且具有效果的——但带有一些纯粹性的孤岛，在这些孤岛上纯粹性有所帮助。这是一种合法使用 Haskell 的方式，并且它仍然是对其他语言的一种改进 (https://entropicthoughts.com/haskell-procedural-programming)。 但是，如果我们 *想要* 使模拟变得纯粹呢？一种方法是将线状态管理从 `IO` 移到 `ST`。虽然 `IO` 是一种允许任意副作用的计算类型，但 `ST` 是一种只允许可变变量的计算类型，并且它被设计成没有任何效果可以逃逸到其局部上下文之外。这意味着我们可以在电路模拟内部执行基于 `ST` 的突变，这种方式从外部看是纯粹的。这将是一个相当普通的转换，并不有趣。 但 Haskell 允许我们做得更好。这将是另一篇文章。敬请期待。