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

Question

我曾用Python编写过一个简单基于堆栈的虚拟机，现在我尝试着用Clojure来重写它，但由于我对Lisp不太熟悉，所以有些困难。这份Python代码片段处理字节码，字节码是表示为元组列表的形式：This Python snippet。

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

或者在Clojure中：

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

当一个函数对象加载字节码时，每个“标签”元组都会被特殊处理以标记该位置，而每个其他元组都会留在最终的字节码中。我认为Clojure版本的这个函数涉及到折叠，但我不确定如何以优雅或惯用的方式实现。有什么想法吗？

- Jordan Danford

Answer 1

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

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

一旦你有一个明确的目标描述，编写代码就变得容易得多了，而且这是一个相当简单的reduce。有许多风格不同的编写reductor的方法，但是对我来说，这种方式似乎最容易阅读。

(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))

Edit

这个版本支持一个 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))

- amalloy

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))

所以我认为你是正确的，需要使用fold。所有的函数式fold都会遍历集合，并将该集合“归约”为单个值。然而，并没有规定生成的单个值不能是集合，或者像这种情况一样，是一个集合的集合。

在我们的情况下，我们将使用reduce的三参数版本 - 这允许我们提供一个初始累加器值。我们需要这样做，因为我们要在迭代字节码集合时跟踪很多状态，而两个参数的版本几乎要求您的累加器与列表中的项目类似。（参见 (reduce + [1 2 3 4])）

当使用函数式fold时，您需要考虑累积的内容以及输入集合中每个元素如何对该累加产生贡献。如果您查看Python代码，每次循环可以更新三个值：

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

循环期间不会写入任何其他内容。因此，我们的累加器值将需要存储这三个值。

前面的部分是最重要的部分。

有了这个之后，剩下的就很容易了。我们需要一个初始的累加器值，其中没有代码，没有标签映射，并且PC从0开始。在每次迭代中，我们将以以下两种方式之一更新累加器：

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

现在，就是输出结果了。

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

那是一个由三个元素组成的向量。第一个元素是程序，第二个元素是标签映射，第三个元素是下一个PC值。现在，你可以修改解析器(parse)只生成两个值；这不是一件不合理的事情。你可能不想这样做的原因是API设计问题，而不是其他问题。我会留给读者来练习。

我还应该提到，最初我省略了let块，并直接内联了命名值。我决定将它们分离出来，以增加可读性。同样，我不知道哪种方法更符合惯用法。这可能更多地是每个项目的约定。

最后，我不知道单子是否真正在Clojure社区中流行，但你也可以为字节码解析创建一个单子，并将“add-statement”和“add-label”操作定义为该单子中的值。这将极大地增加设置复杂性，但会简化实际解析代码。实际上，它将允许你的解析代码看起来相当程式化，这可能是好事或坏事。（别担心，它仍然是功能性和无副作用的；单子只是让你隐藏管道）如果你的Python示例相当代表你需要处理的数据类型，那么单子几乎肯定是不必要的开销。另一方面，如果你实际上需要处理比样本所示的状态更多的状态，那么单子可能有助于保持理智。

- Daniel Yankowsky

---

我还应该提到，我在Reddit上回复了，但被引导到这里。 - Daniel Yankowsky

Answer 3

(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}))

对我来说有点宽，但还不算太糟。

- mange

Answer 4

我将为您提供这类问题的通用解决方案。

大多数循环可以轻松地使用直接的map、filter或reduce完成，如果您的数据结构是递归的，那么循环自然就是递归。

然而，您的循环是一种不同类型的循环。您的循环累积了一个结果——这表明应该使用reduce——但循环还携带了一个局部变量（pc），因此它不是一个简单的reduce。

这是一种相当常见的循环。如果这是Racket，我会使用for/fold1，但由于不是，我们将不得不把您的循环塞进reduce中。

让我们定义一个名为load的函数，它返回两个东西，即处理后的代码和处理后的标签。我还将使用一个名为is-label?的辅助函数。

(defn load [asm]
  (defn is-label? [x] (= (first x) :label))
  {:code <<< CODE GOES HERE >>>

   :labels
   <<< CODE GOES HERE >>>
  })

现在，你的循环做了两件事情，它处理代码和标签。尽可能地，我试图让循环只完成单一任务。这使得它们更容易理解，并且通常会揭示使用更简单的循环结构的机会。

要获取代码，我们只需要删除标签。这可以通过调用filter来实现。

  {:code (filter (complement is-label?) asm)

   :labels
   <<< CODE GOES HERE >>>
  }

Reduce通常只有一个累加器，但是你的循环需要两个：结果和本地变量pc。我将把这两个打包成一个向量，该向量将立即被循环体解构。向量的两个插槽将成为我的两个本地变量。

这两个变量的初始值出现在reduce的第二个参数中。

   (first
    (reduce
     (fn [[result, pc] inst]

        << MORE CODE >>

     [{} 0] asm))

（注意变量的初始值与声明相距甚远。如果主体很长，这可能很难阅读。这就是Racket的for/fold1解决的问题。）

reduce返回后，我调用first来丢弃本地变量pc并仅保留结果。

填充循环体很简单。如果指令是标签，则assoc到结果中，否则将pc增加一。在任何情况下，我都构造一个包含所有局部变量新值的向量。

     (fn [[result, pc] [_ arg :as inst]]
       (if (is-label? inst)
         [(assoc result arg pc) pc]
         [result (inc pc)]))

这种技术可以用来将任何带有本地累加器的循环转换为reduce。以下是完整代码。

(defn load [asm]
  (defn is-label? [x] (= (first x) :label))
  {:code (filter (complement is-label?) asm)

   :labels
   (first
    (reduce
     (fn [[result, pc] [_ arg :as inst]]
       (if (is-label? inst)
         [(assoc result arg pc) pc]
         [result (inc pc)]))
     [{} 0] asm))})

- Guillaume Marceau