35

More than 1 year has passed since last update.

# FizzBuzzは無慈悲な面接の女王

Last updated at Posted at 2021-12-04

この記事はFOLIOアドベントカレンダー2021の5日目です1

# 創世記

``````(defn nand [x y] 神)

(deftest nand-test
(testing "nand"
(is (true? (nand false false)))
(is (true? (nand false true)))
(is (true? (nand true false)))
(is (false? (nand true true)))))
``````

ジム・ケラーが「光あれ」と言った。するとnotがあった。

``````(defn not [x]
(nand x x))
``````

2日目、光は世界をandとorに分けた。

``````(defn and [x y]
(not (nand x y)))

(defn or [x y]
(nand (not x) (not y)))
``````

3日目、神は「nandの上にxorを作れ」と言った。そしてそのようになった。

``````(defn xor [x y]
(and (or x y) (nand x y)))
``````

4日目、神は選択肢を作った。

``````(defn mux [x y select]
(or
(and x (not select))
(and y select)))

(defn dmux [in select]
[(and in (not select))
(and in select)])
``````

5日目、神は、複数の引数を持つようにした。

``````(defn and3 [x y z] (and x (and y z)))

(defn and4 [a b c d] (and (and a b) (and c d)))

(defn or3 [x y z] (or x (or y z)))

(defn or4 [x0 x1 x2 x3]
(or (or x0 x1) (or x2 x3)))

(defn mux8 [a b c d e f g h select]
(let [[s0 s1 s2] select]
(or8-1
[(and4 a (not s0) (not s1) (not s2))
(and4 b s0 (not s1) (not s2))
(and4 c (not s0) s1 (not s2))
(and4 d s0 s1 (not s2))
(and4 e (not s0) (not s1) s2)
(and4 f s0 (not s1) s2)
(and4 g (not s0) s1 s2)
(and4 h s0 s1 s2)])))

(defn dmux8 [in select]
(let [[s0 s1 s2] select
and4 (fn [i0 i1 i2 i3] (and (and i0 i1) (and i2 i3)))]
[(and4 in (not s0) (not s1) (not s2))
(and4 in s0 (not s1) (not s2))
(and4 in (not s0) s1 (not s2))
(and4 in s0 s1 (not s2))
(and4 in (not s0) (not s1) s2)
(and4 in s0 (not s1) s2)
(and4 in (not s0) s1 s2)
(and4 in s0 s1 s2)]))
``````

6日目、神は「16bitを使え」と命じた。

``````(defn not16bit [in]
(let [[in0 in1 in2 in3 in4 in5 in6 in7 in8 in9 in10 in11 in12 in13 in14 in15] in]
[(not in0) (not in1) (not in2) (not in3) (not in4) (not in5) (not in6) (not in7)
(not in8) (not in9) (not in10) (not in11) (not in12) (not in13) (not in14) (not in15)]))

(defn and16bit [x y]
(let [[x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15] x
[y0 y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 y13 y14 y15] y]
[(and x0 y0) (and x1 y1) (and x2 y2) (and x3 y3) (and x4 y4) (and x5 y5) (and x6 y6) (and x7 y7)
(and x8 y8) (and x9 y9) (and x10 y10) (and x11 y11) (and x12 y12) (and x13 y13) (and x14 y14) (and x15 y15)]))

(defn or16bit [x y]
(let [[x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15] x
[y0 y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 y13 y14 y15] y]
[(or x0 y0) (or x1 y1) (or x2 y2) (or x3 y3) (or x4 y4) (or x5 y5) (or x6 y6) (or x7 y7)
(or x8 y8) (or x9 y9) (or x10 y10) (or x11 y11) (or x12 y12) (or x13 y13) (or x14 y14) (or x15 y15)]))

(defn mux16bit [x y select]
(let [[x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15] x
[y0 y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12 y13 y14 y15] y]
[(mux x0 y0 select) (mux x1 y1 select) (mux x2 y2 select) (mux x3 y3 select)
(mux x4 y4 select) (mux x5 y5 select) (mux x6 y6 select) (mux x7 y7 select)
(mux x8 y8 select) (mux x9 y9 select) (mux x10 y10 select) (mux x11 y11 select)
(mux x12 y12 select) (mux x13 y13 select) (mux x14 y14 select) (mux x15 y15 select)]))
``````

7日目、神はブラック企業勤めだったので有休をもらえなかった。

# 天岩戸

``````(defn make-register []
(let [r (ref false)]
岩戸に隠れる)
岩戸から出てくる))))

(deftest make-register-test
(testing "register"
(is (false? (let [r (make-register)]
(r false true)
(r false false))))
(is (false? (let [r (make-register)]
(r false true)
(r true false))))
(is (true? (let [r (make-register)]
(r true true)
(r false true))))
(is (true? (let [r (make-register)]
(r true true)
(r true true))))))
``````

``````(defn make-register16 []
(let [r0 (make-register) r1 (make-register) r2 (make-register) r3 (make-register)
r4 (make-register) r5 (make-register) r6 (make-register) r7 (make-register)
r8 (make-register) r9 (make-register) r10 (make-register) r11 (make-register)
r12 (make-register) r13 (make-register) r14 (make-register) r15 (make-register)]
(let [[in0 in1 in2 in3 in4 in5 in6 in7 in8 in9 in10 in11 in12 in13 in14 in15] in]

(defn make-ram8 []
(let [r0 (make-register16) r1 (make-register16) r2 (make-register16) r3 (make-register16)
r4 (make-register16) r5 (make-register16) r6 (make-register16) r7 (make-register16)]
(let [[l0 l1 l2 l3 l4 l5 l6 l7] (dmux8 load addr)
ro0 (r0 in l0)
ro1 (r1 in l1)
ro2 (r2 in l2)
ro3 (r3 in l3)
ro4 (r4 in l4)
ro5 (r5 in l5)
ro6 (r6 in l6)
ro7 (r7 in l7)]
(mux16bit-8 ro0 ro1 ro2 ro3 ro4 ro5 ro6 ro7 addr)))))
``````

# 国生み神話

``````(defn half-adder [x y]
[(xor x y)
(and x y)])
``````

ところが手順に間違いがあって、キャリービットを扱うことができなかった。外部コンサルタントに相談したところ、ブロックチェーンを使うよう勧められた。占いに従ってもう一度やり直したところ、全加算器が生まれた。

``````(defn full-adder [x y cin]
(let [[s0 c0] (half-adder x y)
[s1 (or c0 c1)]))
``````

こうして、伊邪那岐と伊邪那美はプロジェクトマネジメントの経験を積み、ALUを作り出した。

``````(defn alu [x y zx nx zy ny f no]
(let [
x-zero (and16bit x (expand16 (not zx)))
y-zero (and16bit y (expand16 (not zy)))
x-negate (xor16bit x-zero (expand16 nx))
y-negate (xor16bit y-zero (expand16 ny))

rand (and16bit x-negate y-negate)
zr (not (or16 out))
ng (nth out 15)]
[out zr ng]))
``````

# 因幡の白兎

「私はどうしてもRubyカンファレンスに出たかったのですが、泳がないで島を渡る方法がなかったのです。そこにワニの群れが現れたので、私は彼らを利用しようと思いました。私は彼らに、『RISCとCISCどちらが優れているか競争しよう』と持ち掛け、人力プログラムカウンターとして一列に並んでほしい、と頼みました」。そして数を数えるふりをしながら、彼らを踏み台にして、島を渡ろうとしました。

``````(defn make-pc []
(let [r (make-register16)]
(r
(mux16bit-4
zero16
zero16
in
(inc16bit (r false16 false))
[(or inc (not load)) (not reset)])
``````

「ところが渡りきったところで、うっかり『LinuxよりWindowsのほうが普及してるよね』と言ってしまい、怒ったワニは私の皮を剥いでしまったのです」

# 国造り

``````(defn -cpu [a-register
d-register
pc
instruction inM reset
(let [
[instruction-type v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15] instruction ; A-instruction
[_
exit                                               ; Exit command
_
a c1 c2 c3 c4 c5 c6
d1                                                 ; Save to A?
d2                                                 ; Save to D?
d3                                                 ; Save to M?
j1
j2
j3
] instruction                                      ; C-instruction

a-current (a-register dont-care false)
d-current (d-register dont-care false)

[outM zr ng] (alu
d-current
(mux16bit a-current inM a)           ; if comp-a == true inM else A-register
c1 c2 c3 c4 c5 c6)

_ (a-register
(mux16bit [v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 false] outM instruction-type)
(and
(or (not instruction-type) d1)

instruction-type                          ; not an a-instruction
(or4
(and3 j1 j2 j3)                         ; 1 1 1; just jump
(and j1 ng)                             ; j1 is true and output < 0
(and j2 zr)                             ; j2 is true and output is 0
(and j3 (not (or ng zr)))               ; j3 is true and output > 0
)
pc-out (pc a-current pc-inc pc-load reset)

exit-out (and instruction-type exit)                ; c-instruction & exit code is true
]
[outM d3 a-current pc-out exit-out]
))

(defn make-cpu []
(let [
a-register (make-register16)
d-register (make-register16)
pc (make-pc)
]
(fn
([instruction inM reset] (cpu instruction inM reset false))
))
``````

ところが須佐之男は「君、変なところで改行挟む癖あるよね」と難癖をつけ結婚を認めなかった。そこで、須勢理毘売命のプルリクの助けを受けて、コンピューターを完成させた。

``````(defn console [in load]
(if load (print (i2s (ba2i in)))))

(defn computer [program-memory]
(let [
cpu (make-cpu)
ram (make-ram16k)
(let [[a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14] addr
addr-memory [a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13]
_ (console in l1)
]
(mux16bit-4 ro false16 false16 false16 [a13 false])
)
)
]
(loop []
(let [
[_ _ current-address pc] (cpu false16 false16 false true)
instruction (program-memory pc)
[outM writeM addressM _ exit] (cpu instruction inM false)
]
(if (false? exit) (recur))))))
``````

8

こうして大己貴命は、須佐之男に結婚を認めさせた。

# 今日はMPが足りないみたいだ

``````(defn lex [^String code]
(filter #(not (blank? %))
(re-seq #"[\w\"]+|[\s\(\)\{\}\;]|\+\+|<=|==|=|%" code)))

(defn parse
[code]
(let [[t0 t1 t2 t3 t4] code]
(cond
(= t2 "=") {:type "assign" :name t1 :value (parse-value t3) :rest (drop-semi (drop 4 code))}
(= t1 "<=") {:type "le" :x (parse-value t0) :y (parse-value t2) :rest (drop-semi (drop 3 code))}
(= t1 "++") {:type "inc" :name t0 :rest (drop-semi (drop 2 code))}
(and (= t1 "%") (= t3 "==")) {:type "rem" :x (parse-value t0) :y (parse-value t2) :z (parse-value t4) :rest (drop-semi (drop 5 code))}
(= t0 "for") (parse-for code)
(= t0 "if") (parse-if code)
(and (re-matches #"[\w]+" t0) (= t1 "(") (= t3 ")")) {:type "call" :name t0 :arg (parse-value t2) :rest (drop-semi (drop 4 code))}
:else (let [v (parse-value t0)] (merge v {:rest (rest code)})))))
``````

``````(defn a-inst [in]
(into [false]
(cond
(int? in) (bit15 (i2ba in))
(string? in) (bit15 (s2ba in))
(= 15 (count in)) in                                  ; bit array[15]
(= 16 (count in)) (bit15 in))))                       ; bit array[16]

(defn c-inst
([comp dest] (c-inst false comp dest))
([a comp dest] (c-inst a comp dest op-no-jump))
([a comp dest jump] (c-inst [false false] a comp dest jump))
([ext a comp dest jump] (vec (concat [true] ext [a] comp dest jump))))

(defn compile-for [code var]
(let [offset (:offset var)
{init :init cond :cond loop :loop body :body} code
[op-init var'] (-compile init var)
c-op-init (count op-init)
[op-cond] (-compile cond (assoc var' :offset (+ offset c-op-init)))
c-op-cond (count op-cond)
[op-body] (-compile body (assoc var' :offset (+ offset c-op-init c-op-cond 2)))
c-op-body (count op-body)
[op-loop] (-compile loop (assoc var' :offset (+ offset c-op-init c-op-cond 2 c-op-body)))
c-op-loop (count op-loop)
]
[(vec (concat
op-init
op-cond
[(a-inst (+ offset c-op-init c-op-cond 2 c-op-body c-op-loop 2)) ; @ the end of the loop
(c-inst false op-d op-dest-null op-jeq)        ; D,JEQ ; if cond=false jump
]
op-body
op-loop
[(a-inst (+ offset c-op-init))                  ; @cond
(c-inst false op-0 op-dest-null op-jmp)        ; JMP
]))
var]))

(defn compile-if [code var]
(let [offset (:offset var)
{cond :cond then :then else :else} code
[op-cond] (-compile cond var)
c-op-cond (count op-cond)
[op-then] (-compile then (assoc var :offset (+ offset c-op-cond 2)))
c-op-then (count op-then)
[op-else] (-compile else (assoc var :offset (+ offset c-op-cond c-op-then 4)))
c-op-else (count op-else)
]
[(vec (concat
op-cond
[(a-inst (+ offset c-op-cond 2 c-op-then 2))    ; A = offset + len(op-cond) + 2 +len(op-then) + 2
(c-inst false op-d op-dest-null op-jeq)        ; D,JNE ; if cond = false jump to op-else
]
op-then
[(a-inst (+ offset c-op-cond 2 c-op-then 2 c-op-else)) ; A = offset + len(op-cond) + 2 + len(op-then) + 2 + len(op-else)
op-else
))
var]))

(defn -compile [code var]
(let [type (:type code)]
(increment-offset
(cond
(= type "assign") (compile-assign code var)
(= type "int") [(compile-int code) var]
(= type "str") (compile-str code var)
(= type "ref") (compile-ref code var)
(= type "le") (compile-le code var)
(= type "inc") (compile-inc code var)
(= type "rem") (compile-rem code var)
(= type "call") (compile-call code var)
(= type "for") (compile-for code var)
(= type "if") (compile-if code var)))))
``````

10

``````(defn -main []
(computer
(make-program-memory (compile (parse (lex "
for (int i = 1; i <= 100; i++) {
if (i % 15 == 0) {
println(\"FizzBuzz\");
} else if (i % 5 == 0) {
println(\"Buzz\");
} else if (i % 3 == 0) {
println(\"Fizz\");
} else {
println(i);
}
}
"))))))

(deftest main-test
(testing "main"
(is (=
(str
(->>
(range 1 101)
(map
#(match [(rem %1 3) (rem %1 5)]
[0 0] "FizzBuzz"
[0 _] "Fizz"
[_ 0] "Buzz"
:else %1)
)
(join "\n"))
"\n")
(with-out-str (-main))))))
``````

``````> lein run
1
2
Fizz
4
Buzz
...
``````

# クレジット

ソースコード

1. この記事はあくまで個人の見解であり、所属会社の立場を表すものではない。念のため。

2. 本記事では、`nand``make-register`の二つをプリミティブなコンポーネントとして使用する。

3. 出典:Noam Nisan, Shimon Schocken『コンピュータシステムの理論と実装』

4. `nth`を使っているが、引数が定数なのでずるではない。

5. 「Javaだろ!」とお怒りの方は、誤字脱字に寛容になろう

6. 『コンピュータシステムの理論と実装』に加え、C命令の2bit目を終了コマンドとして使用している。

7. きちんとコードを読んだ人は(そんな人はいないだろうが)、レジスターを二回呼び出していることにお気づきだろう。これは、電気の流れを関数の呼び出しとして表現しているためである。組み合わせ回路の即座に変更されるべき値と、順序回路の呼び出しに従って変わるべき値の、信号が巡回して帰ってくるというもともとの意味の『回路』を再現しているのである……というのは建前で、コードの美しさのため1クロック=1回の関数呼び出しとしたかったのだが、アドベントカレンダーの〆切的に無理だったので断念した。`disable-loading`はその「読み取り」の際に、レジスターを更新しないようにするため追加したフラグである。

8. コンソールはハードウェアなので直接printを呼んでいる

9. この記事の作者はClojureが全く書けないのである。本物のLISPerであればマクロを使うところだ。

10. 「スタックマシンを使えよ」というお怒りはもっともである。

11. Hexing the Technical Interviewの解説を読みたい人は、本記事の筆者のホームページを見よう!

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
3. You can use dark theme
What you can do with signing up
35