这段Python代码的惯用Clojure等价是什么？

Question

我用Python写了一个简单的基于栈的虚拟机，现在我想把它重写成Clojure，但这对我来说有点难，因为我对Lisp不太熟悉。这个Python代码片段处理的是字节码，字节码用一系列元组表示，像这样：

[("label", "entry"),
 ("load", 0),
 ("load", 1),
 ("add",),
 ("store", 0)]

在Clojure中是这样的：

[[:label :entry]
 [:load 0]
 [:load 1]
 [:add]
 [:store 0]]

当一个函数对象加载字节码时，每个“标签”元组会被特别处理，以标记那个位置，而其他的元组则会保留在最终的字节码中。我猜Clojure中实现这个功能的方式可能会用到一个折叠（fold），但我不太确定怎么做才优雅或符合习惯。有没有什么想法？

Answer 1

(defn make-function [name code]
  (let [[code labels] (reduce (fn [[code labels] inst]
                                (if (= (first inst) :label)
                                  [code (assoc labels (second inst) (count code))]
                                  [(conj code inst) labels]))
                              [[] {}] ;; initial state of code and labels
                              code)]
    {:name name, :code code :labels labels}))

我觉得这个有点宽，但也还算可以。

Answer 2

我不能保证这段代码是标准的Clojure写法，但这是你Python代码的一个函数式版本，应该能让你接近你想要的效果。

(def prog [
 [:label :entry]
 [:load 0]
 [:load 1]
 [:add]
 [:store 0]])

(defn parse [stats]
    (let [
        f (fn [[out-stats labels pc] stat]
            (if (= :label (first stat))
                [out-stats (conj labels [(second stat) pc]) pc]
                [(conj out-stats stat) labels (+ 1 pc)]))
        init [[] {} 0]
        ]
        (reduce f init stats)))

(println (parse prog))

我觉得你说得对，使用“折叠”是你想要的。所有的函数式折叠都会遍历一个集合，并把这个集合“缩减”成一个单一的值。不过，没有规定说最后得到的单一值不能是一个集合，或者像这里一样，是一个集合的集合。

在我们的例子中，我们将使用三参数版本的reduce——这让我们可以提供一个初始的累加器值。我们需要这样做，因为在遍历字节码集合时，我们需要跟踪很多状态，而两参数版本基本上要求你的累加器和列表中的项目相似。（比如 (reduce + [1 2 3 4])）

在使用函数式折叠时，你需要考虑你在累积什么，以及输入集合中的每个元素如何对这个累积产生贡献。如果你看看你的Python代码，有三个值可以在每次循环中更新：

• 输出语句（self.code）
• 标签映射（self.labels）
• 程序计数器（pc）

在循环中没有其他东西被写入。所以，我们的累加器值需要存储这三个值。

上面那段是最重要的部分。

一旦你有了这些，剩下的就简单多了。我们需要一个初始的累加器值，它没有代码，没有标签映射，程序计数器从0开始。在每次迭代中，我们将以两种方式之一更新累加器：

• 添加一个新的标签映射
• 添加一个新的输出程序语句，并增加程序计数器

接下来是输出：

[[[:load 0] [:load 1] [:add] [:store 0]] 
 {:entry 0}
 4]

这是一个包含三个元素的向量。第一个元素是程序，第二个元素是标签映射，第三个元素是下一个程序计数器的值。现在，你可能会修改parse函数，让它只产生两个值；这样做也不算不合理。虽然有一些原因可能让你不想这样做，但这更多是API设计的问题。我把这个留给读者自己去思考。

我还应该提到，最开始我省略了let块，直接把命名的值写在了一起。后来我决定把它们分开，希望能提高可读性。再次强调，我不知道哪种写法更符合习惯，这可能是每个项目的约定不同。

最后，我不确定在Clojure社区中单子（monads）是否已经流行，但你也可以为字节码解析创建一个单子，并将“add-statement”和“add-label”定义为这个单子中的值。这会大大增加设置的复杂性，但会简化实际的解析代码。实际上，这会让你的解析代码看起来相当程序化，这可能是好事，也可能不是。（别担心，它仍然是函数式的，没有副作用；单子只是让你隐藏一些底层的细节。）如果你的Python示例能很好地代表你需要处理的数据类型，那么单子几乎肯定是多余的开销。另一方面，如果你确实需要管理比示例中更多的状态，那么单子可能会帮助你保持理智。

Answer 3

看了这个Python代码片段，你似乎想要的最终输出是这样的：

{:code [[:load 0]
        [:load 1]
        [:add]
        [:store 0]]
 :labels {:entry 0}}

在你清楚地描述了目标后，写代码就简单多了。其实这个过程很简单。虽然有很多不同风格的写法，但对我来说，这种写法最容易理解。

(defn load [asm]
  (reduce (fn [{:keys [code labels]} [op arg1 & args :as instruction]]
            (if (= :label op)
              {:code code
               :labels (assoc labels arg1 (count code))}
              {:code (conj code instruction)
               :labels labels}))
          {:code [], :labels {}},
          asm))

编辑

这个版本支持一个name参数，并且通过不重复那些不变的元素来简化了处理步骤。

(defn load [name asm]
  (reduce (fn [program [op arg1 :as instruction]]
            (if (= :label op)
              (assoc-in program [:labels arg1] (count (:code program)))
              (update-in program [:code] conj instruction)))
          {:code [], :labels {}, :name name},
          asm))