この記事はFOLIOアドベントカレンダー2021の5日目です1
創世記
最初にnandがあった。nandは神であった。
(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日目、神はブラック企業勤めだったので有休をもらえなかった。
天岩戸
高天原にいた天照大御神は、度重なる須佐之男の狼藉に耐え兼ね、天岩戸に隠れてしまった。こうして順序回路が生まれた。2
(defn make-register []
(let [r (ref false)]
(fn [in load]
(if load
岩戸に隠れる)
岩戸から出てくる))))
(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)]
(fn [in load]
(let [[in0 in1 in2 in3 in4 in5 in6 in7 in8 in9 in10 in11 in12 in13 in14 in15] in]
[(r0 in0 load) (r1 in1 load) (r2 in2 load) (r3 in3 load) (r4 in4 load) (r5 in5 load) (r6 in6 load) (r7 in7 load)
(r8 in8 load) (r9 in9 load) (r10 in10 load) (r11 in11 load) (r12 in12 load) (r13 in13 load) (r14 in14 load) (r15 in15 load)]))))
(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)]
(fn [in addr load]
(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)))))
国生み神話
伊邪那岐と伊邪那美は結婚し、ALUを完成させるよう命ぜられた。二柱は天沼矛で地上をかき混ぜ、加算器を作った。
(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 c1] (half-adder s0 cin)]
[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))
[radd] (adder16bit x-negate y-negate false)
rand (and16bit x-negate y-negate)
out-added (mux16bit rand radd f)
out (xor16bit out-added (expand16 no))
zr (not (or16 out))
ng (nth out 15)]
[out zr ng]))
因幡の白兎
大己貴命がScalaMatsuriに向かっている途中、因幡の国に通りがかった。そこで白い兎が皮を剥がれているのを見つけ、いったいどうしたのか尋ねた。
「私はどうしてもRubyカンファレンスに出たかったのですが、泳がないで島を渡る方法がなかったのです。そこにワニの群れが現れたので、私は彼らを利用しようと思いました。私は彼らに、『RISCとCISCどちらが優れているか競争しよう』と持ち掛け、人力プログラムカウンターとして一列に並んでほしい、と頼みました」。そして数を数えるふりをしながら、彼らを踏み台にして、島を渡ろうとしました。
(defn make-pc []
(let [r (make-register16)]
(fn [in inc load reset]
(r
(mux16bit-4
zero16
zero16
in
(inc16bit (r false16 false))
[(or inc (not load)) (not reset)])
(or (or load inc) reset)))))
「ところが渡りきったところで、うっかり『LinuxよりWindowsのほうが普及してるよね』と言ってしまい、怒ったワニは私の皮を剥いでしまったのです」
大己貴命は(それって大概自分が悪くね?)と思ったが、心優しい彼はそう指摘する代わりに、FedoraのCD-Rを兎にプレゼントした。
国造り
大己貴命は須勢理毘売命に惚れ、父親の須佐之男命に結婚を認めてくれるよう頼んだ。ところが須佐之男は、「最近多いんだよねーJAVA5とかちょっとかじった程度で、俺プログラマーやってますって顔する子」と言って結婚を認めなかった。大己貴命はパイソニアンの群れがいる部屋の中に閉じ込められてしまった。しかし、事前に須勢理毘売命に聖杯を授かっていた大己貴命は歴史学者を倒し、CPUを完成させた。
(defn -cpu [a-register
d-register
pc
instruction inM reset
disable-loading]
(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)
(not disable-loading)))
_ (d-register outM (and d2 (not disable-loading)))
pc-load (and3
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
)
(not disable-loading)) ; not disabled
pc-inc (not (or pc-load disable-loading)) ; neither load nor disabled
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)
cpu (fn [instruction inM reset disable-loading]
(-cpu a-register d-register pc instruction inM reset disable-loading))
]
(fn
([instruction inM reset] (cpu instruction inM reset false))
([instruction inM reset disable-loading] (cpu instruction inM reset disable-loading)))
))
ところが須佐之男は「君、変なところで改行挟む癖あるよね」と難癖をつけ結婚を認めなかった。そこで、須勢理毘売命のプルリクの助けを受けて、コンピューターを完成させた。
(defn console [in load]
(if load (print (i2s (ba2i in)))))
(defn computer [program-memory]
(let [
cpu (make-cpu)
ram (make-ram16k)
memory (fn [in addr load]
(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]
[l0 l1] (dmux load a14)
ro (ram in addr-memory l0)
_ (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)
inM (memory false16 current-address false)
[outM writeM addressM _ exit] (cpu instruction inM false)
]
(memory outM addressM writeM)
(if (false? exit) (recur))))))
こうして大己貴命は、須佐之男に結婚を認めさせた。
今日はMPが足りないみたいだ
面接官「特技はLISPとありますが？」
学生 「はい。LISPです。」
面接官「LISPとは何のことですか？」
学生 「魔法です。」
面接官「え、魔法？」
学生 「はい。魔法です。敵全員に大ダメージを与えます。」9
(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)})))))
面接官「・・・で、そのLISPは当社において働くうえで何のメリットがあるとお考えですか？」
学生 「はい。オブジェクト指向が襲って来ても守れます。」
面接官「いや、当社には襲ってくるような輩はいません。それに人に危害を加えるのは犯罪ですよね。」
学生 「でも、Smalltalkにも勝てますよ。」
面接官「いや、勝つとかそういう問題じゃなくてですね・・・」
(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)
(c-inst false op-0 op-dest-null op-jmp)] ; D,JMP ; jump to last
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)))))
学生 「FizzBuzzだって実行できるんですよ。」
面接官「ふざけないでください。それにFizzBuzzって何ですか。だいたい・・・」
(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))))))
学生 「FizzBuzzです。FizzBuzz問題とも書きます。FizzBuzzというのは・・・」
面接官「聞いてません。帰って下さい。」
学生 「あれあれ？怒らせていいんですか？使いますよ。FizzBuzz。」
面接官「いいですよ。使って下さい。FizzBuzzとやらを。それで満足したら帰って下さい。」
> lein run
1
2
Fizz
4
Buzz
...
学生 「運がよかったな。今日はRAMが足りないみたいだ。」
面接官「帰れよ。」
クレジット
ソースコード
本記事は、AphyrのRewriting the Technical Interviewに直接の着想を得ている。11
実装詳細の大部分は、『コンピュータシステムの理論と実装』によるところが大きい。
-
この記事はあくまで個人の見解であり、所属会社の立場を表すものではない。念のため。 ↩
-
本記事では、
nandとmake-registerの二つをプリミティブなコンポーネントとして使用する。 ↩ -
出典:Noam Nisan, Shimon Schocken『コンピュータシステムの理論と実装』 ↩
-
nthを使っているが、引数が定数なのでずるではない。 ↩ -
「Javaだろ!」とお怒りの方は、誤字脱字に寛容になろう ↩
-
『コンピュータシステムの理論と実装』に加え、C命令の2bit目を終了コマンドとして使用している。 ↩
-
きちんとコードを読んだ人は(そんな人はいないだろうが)、レジスターを二回呼び出していることにお気づきだろう。これは、電気の流れを関数の呼び出しとして表現しているためである。組み合わせ回路の即座に変更されるべき値と、順序回路の呼び出しに従って変わるべき値の、信号が巡回して帰ってくるというもともとの意味の『回路』を再現しているのである……というのは建前で、コードの美しさのため1クロック=1回の関数呼び出しとしたかったのだが、アドベントカレンダーの〆切的に無理だったので断念した。
disable-loadingはその「読み取り」の際に、レジスターを更新しないようにするため追加したフラグである。 ↩ -
コンソールはハードウェアなので直接printを呼んでいる ↩
-
この記事の作者はClojureが全く書けないのである。本物のLISPerであればマクロを使うところだ。 ↩
-
「スタックマシンを使えよ」というお怒りはもっともである。 ↩
-
Hexing the Technical Interviewの解説を読みたい人は、本記事の筆者のホームページを見よう! ↩