読者です 読者をやめる 読者になる 読者になる

Haskellでいってみよう

日曜プログラマにも満たないレベルでもHaskellで何かソフトウェアを作りたい!

CPUの創りかた(1): 基本論理回路の定義など

logic circuit

さて今回からは、論理回路をやろう。といっても電子工作をする わけではないので、要するにシミュレータを作るということだ。 もちろん大仰なシミュレータではないが。今回唐突に論理回路を 持ち出したのは次の本の「せい」だ。

2003年発行の本で、当時から気になって買いたいと思っていたが そのままになってしまっていた。数ヶ月前にとうとう買ってしまったが、 当方にはその内容がすこぶる面白かった。マシン語は昔やっていたし、 大学で半導体論理回路(ANDゲートだの加算器だの)も勉強したが、 間を埋めるもの=CPUの構造はわからないままだった。命令はどう フェッチするのか、インストラクションはどこに規定されているのか、 レジスタに値が入ったり出たりするのはどうなっているのか、などなど。 この本には、非常に簡易なCPUだけれどもその辺が明快に記述されている。

となると次は、実際にここに書いてあるCPUを作りたくなるものだ。 が、電子工作の経験はほとんどなく、また道具もないし・・・。 じゃあせめてその論理回路をパソコン上でシミュレートしたいなあ、 というのが今回のネタである。

この本の中では、TD4というCPUを作っている。発売当初はTD4の製作 ネタのHPがいろいろあったようだが今はリンク切れも幾つかある。 ブームは過ぎたかもしれないが、今一度(ソフトウェアで)製作記と 行こう。

論理回路の定義、クロックとか

論理回路といっても単純なANDゲートなどから加算器とか順序回路とか いろいろある。これをどう表現したらいいか? 電源はともかくクロックとかは? などよくわからないことが幾つか出てくる。

Haskellモナドやライブラリはまだよくわかっていないので、あとあと もっと良い表現・実装方法が見つかればガラッと変えるかもしれないが、 一旦は次のようなものと決めよう。

  • 論理回路複数の入力と複数の出力を持つ関数のようなものとする。
  • 端子の状態は0か1で表現されることが多いが、今回はBool型で代用する。 ただしBinという別名をつけておく。
  • 入力と出力はBinのリストで表す。
  • クロックは厳密に扱わない。論理回路(の関数)を呼び出すことが すなわちクロックが立ち上がったタイミングであるとする。
  • 論理回路内の遅延は「無視」する。
  • 「状態」を持つ回路については、その状態も出力の一部として出し、 次にその値を入力することで「状態」を表現する。

最後のところはHaskellではStateモナドというものを使えばいいのかも しれないがよくわからないので今の所はこうしておこう。

基本ゲート

早速コードにしてみよう。まず端子の状態を表すBin型を作る。また 論理回路を関数として定義したいので、その引数と返値の型も決めて おこう。こうすることで、その関数は「論理回路」と言える。

type Bin = Bool
type LogicCircuit = [Bin] -> [Bin]

試しにAND回路を定義してみる。2入力に限定してもよかったが、今後 多入力もあり得るし、リスト処理関数andを使えば一緒なので最初から 多入力とした。また入力がない(=空リスト)の時は便宜的にすべての端子が Lと考えてL=Falseを返すようにした。

-- AND gate (multiple input)

lc_and :: LogicCircuit
lc_and [] = [False]
lc_and xs = [and xs]

2入力で動作確認してみる。

main :: IO ()
main = do
  putStrLn ("[L,L]->" ++ (show $ lc_and [False,False]))
  putStrLn ("[L,H]->" ++ (show $ lc_and [False,True]))
  putStrLn ("[H,L]->" ++ (show $ lc_and [True,False]))
  putStrLn ("[H,H]->" ++ (show $ lc_and [True,True]))

実行結果はこれ。

[L,L]->[False]
[L,H]->[False]
[H,L]->[False]
[H,H]->[True]

同様にすればORゲートも簡単だ。ついでにNOTゲートも。

-- OR gate (multiple input)

lc_or :: LogicCircuit
lc_or [] = [False]
lc_or xs = [or xs]

-- NOT gate (multiple input)

lc_not :: LogicCircuit
lc_not [] = [True]
lc_not xs = map (not) xs

NOTは多入力というより多数のNOTを一括処理できるイメージだが。。。 それぞれ図にすると下のようになる。

f:id:eijian:20151213135643p:plain

ここまで来るとこれらを使って他のゲートも定義可能だ。電子工作で 頻繁に使われるというNAND、ついでにNORも次の通り。

-- NAND gate (multiple input)

lc_nand :: LogicCircuit
lc_nand = lc_not . lc_and

-- NOR gate (multiple input)

lc_nor :: LogicCircuit
lc_nor = lc_not . lc_or

NANDはANDの結果を反転させるだけだが、lc_andの返値がリストなので 論理演算子notを使わずlc_notをかますことにした。ああ簡単だ。 図にすると下の通り。

f:id:eijian:20151213135649p:plain

まとめ

初回なので、まずどのようなシミュレーションをするかを大枠で決め、 次に簡単な論理ゲートを幾つか作ってみた。次はこれらを組み合わせた もう少し大きな回路に取り組んでみたい。