clojure中的Nand门电路仿真器

Question

对于简单的代码评审来说，这可能有点大，但我认为它包含了许多不同的需求，以及我试图满足它们的方式。选择一个部门或功能，让我知道我可以改进。该代码是为nand门模拟器，并采取一个输入文件与布线对。就像变量到门或者门到其他门一样。最后输入示例。

;;Namespace
(ns wiring.core (:gen-class) (:use clojure.set))
;;Reading in file in groups of 2 char sequences at a time to get wiring pairs.
(defn get-wiring-groups
  [filename]
  (partition 2 (re-seq #"[a-zA-Z0-9]+" (slurp filename))))
;;Checks each of the sequences for whether or not the first character is a
;;number
;;or letter sequence. Sets letters as variables. Because it only checks first
;;Outputs may be letters aswell. Restricting only middle inputs to be numbers.
(defn get-variable-set
  [wiring-groups]
  (reduce (fn [build-set [variable? number]]
            (if (not (number? (read-string variable?)))
              (conj build-set variable?)
              build-set))
    #{}
    wiring-groups))
;;For putting together wires under same output
(defn merge-wires
  [new-wire wire-list]
  (merge-with (fn [x y] (list x y)) new-wire wire-list))
;;Creates the wiring map using merge-wires on wiring-groups
(defn get-wiring-map-no-defaults
  [wiring-groups]
  (reduce (fn [build-map [from to]] (merge-wires build-map {to from}))
    {}
    wiring-groups))
;;Turns single input gates to true and single input
(defn add-defaults
  [wiring-map]
  (reduce-kv (fn [m k v]
               (if (list? v) (conj m [k v]) (conj m [k (list v true)])))
             {}
             wiring-map))
;;Gets real wiring map
(defn get-wiring-map
  [wiring-groups]
  (-> wiring-groups
      (get-wiring-map-no-defaults)
      (add-defaults)))

;;Checks wiring list to find all inputs, used later for finding which are
;;outputs.
(defn get-input-set
  [wiring-groups]
  (reduce #(conj %1 (first %2)) #{} wiring-groups))
;;Doubles a list by adding a copy to end
(defn double-list [l] (flatten (repeat 2 l)))
;;Doubles a list by repeating each element twice
(defn double-elements [l] (reverse (reduce #(conj %1 %2 %2) '() l)))
;;Creates a list of n possible inputs true or false.
(defn gen-possibilities
  [letter-count]
  (loop [n letter-count
         [start :as all] (list (list true false))]
    (if (> n 1)
      (recur (- n 1) (conj (map double-elements all) (double-list start)))
      all)))
;;Takes the first from each of the possibilities lists and pairs them with
;;their
;;variable in a map
(defn get-current-possibilities [letters all] (zipmap letters (map first all)))
;;Checks if value is boolean
(defn boolean? [v] (or (true? v) (false? v)))
;;Simple nand gate that takes two boolean inputs
(defn nand [in1 in2] (not (and in1 in2)))
;;Checks to see if wire value is known. If so it returns the known value
;;otherwise it returns the wire.
(defn check-known
  [known wire]
  (if (contains? known wire) (get known wire) wire))
;;Interprets a single wire by using nand gate or looking up value
(defn interpret-single
  [[build-new-unknown known] k [wire1 wire2]]
  (if (and (boolean? wire1) (boolean? wire2))
    [build-new-unknown (conj known [k (nand wire1 wire2)])]
    [(conj build-new-unknown
           [k [(check-known known wire1) (check-known known wire2)]]) known]))
;;Interprets one step (either getting nand value or looking up) each wire
(defn interpret
  [unknown known]
  (reduce-kv #(interpret-single %1 %2 %3) [{} known] unknown))
;;Steps till all wire outputs are known
(defn step-all
  [unk kno]
  (loop [[unknown known] [unk kno]]
    (if (not (empty? unknown)) (recur (interpret unknown known)) known)))
;;Calls step all on each possible sequence of inputs
(defn do-all-possibilities
  [wiring letters possibilities-lists]
  (loop [all possibilities-lists
         outputs []]
    (if (not (empty? (first all)))
      (recur (map rest all)
             (conj outputs
                   (step-all wiring (get-current-possibilities letters all))))
      outputs)))
;;Takes in a set and will take those elements from the list of maps
(defn take-results-from
  [s results-list]
  (for [results results-list]
    (filter (fn [[wire output]] (contains? s wire)) results)))
;;Prints the input and output section titles
(defn print-titles
  [inputs]
  (printf (str "%-" (* 10 inputs) "s") "INPUTS")
  (print "OUTPUTS"))
;;Prints the input and output names
(defn print-headers
  [[variables]]
  (doseq [[variable value] variables] (printf "%-10s" variable)))
;;Prints all output and input values
(defn print-vals
  [variables]
  (doseq [[variable value] variables] (printf "%-10s" value)))
;;Driver
(defn -main
  [input-file]
  (let [wiring-groups (get-wiring-groups input-file)
        wiring-map (get-wiring-map wiring-groups)
        variable-set (get-variable-set wiring-groups)
        output-set (difference (set (keys wiring-map))
                               (get-input-set wiring-groups))
        possibilities (gen-possibilities (count variable-set))
        results-list
          (do-all-possibilities wiring-map variable-set possibilities)
        variables-list (take-results-from variable-set results-list)
        outputs-list (take-results-from output-set results-list)]
    (print-titles (count (first variables-list)))
    (println)
    (print-headers variables-list)
    (print-headers outputs-list)
    (println)
    (doall (map (fn [variables outputs]
                  (print-vals variables)
                  (print-vals outputs)
                  (println))
             variables-list
             outputs-list))))

示例输入文件：

(a, 2) 
(b, 2)
(2, 3)
(3, OUT)
(c, OUT)

它的输出：

INPUTS                        OUTPUTS
a         b         c         OUT       
true      true      true      false     
false     true      true      true      
true      false     true      true      
false     false     true      true      
true      true      false     true      
false     true      false     true      
true      false     false     true      
false     false     false     true

Answer 1

该程序生成由NAND门组成的逻辑电路的真值表。电路是--或者应该是--一个有向无圈图。您的一些函数一般适用于有向图。

你关心的主要问题是

1. 如何在内部表示图形
2. 如何表示真值表
3. 如何从图表中导出真值表。

到目前为止，我已经讨论了(1)和一些(2)。

我建议的大多数修改都涉及使用来自序列库的函数，而不是循环，甚至reduces。这些修改，即使有些会使程序变慢，但我希望这样做能让它变得更清晰。

您将得到一份边缘边缘的列表。由于您正在为给定的一组输入计算输出，因此您需要知道每个顶点顶点的前身是什么。其中一个功能就是..。

(defn get-wiring-map [arc-list]
  (reduce
    (fn [ans [p s]]
      (assoc ans s (conj (get ans s []) p)))
      {}
      arc-list))

例如，给出

(def arc-list '((a, 2) (b, 2) (2, 3) (3, OUT) (c, OUT)))

然后

(get-wiring-map arc-list)
;{OUT [3 c], 3 [2], 2 [a b]}

(用符号和数字代替字符串的示例)。

你把这事搞得有点糟了。您的get-wiring-map直接或间接地使用merge-wires、get-wiring-map-no-defaults和add-defaults。

您的版本在单个集合值中插入默认的true值；

(get-wiring-map arc-list)
;{2 (a b), 3 (2 true), OUT (3 c)}

如果你能更好地组织计算(尚未显示出来)，你就不需要这个了。

您的get-input-set更清晰，因为

(defn get-input-set
  [wiring-groups]
  (->> wiring-groups (map first) (into #{})))

我喜欢您在gen-possibilities函数中为真值表生成行的方式。我会这样做：

(defn double-list [l] (concat l l))
(defn double-elements [l] (interleave l l))

(defn gen-possibilities [letter-count]
  (let [double (fn [all] (conj (map double-elements all) (double-list (first all))))
        start (list (list true false))]
    (nth (iterate double start) (dec letter-count))))

例如,

(gen-possibilities 3)
;((true false true false true false true false)
; (true true false false true true false false)
; (true true true true false false false false))

备注

• 我喜欢你的漂亮印花，但要分开。一旦你用输入或输出触摸到系统的边缘，你的程序就更难测试了。