この記事は Retty Advent Calendar 11日目です。
昨日は草山くん(@Masaki-Kusayama)のwebフロントエンドの速度改善に取り組んでみた話でした。
最近、巷でにわかに人気が高まっているKotlinですが、いざやってみようと思っても、手頃な題材が手元になくて困っていませんか？
今回は、手軽に楽しく書けそうな論理回路をKotlinで書いてみようと思います。
論理回路
論理回路は、論理演算を組み合わせていくことで、0/1の入力から期待する出力を得るための回路です。
例えば、以下は2つの2bit数値を加算した結果を得る論理演算の表です。
| input0[] | input1[] | output |
|---|---|---|
| 00 | 00 | 00 |
| 00 | 01 | 01 |
| 00 | 10 | 10 |
| 00 | 11 | 11 |
| 01 | 00 | 01 |
| ... | ... | ... |
論理回路を実装するときには、AND/OR/NOTのような基本的な演算ができる論理素子を組み合わせて作っていきます。CPUなんかも論理素子の組み合わせで作ることができます。夢いっぱいですね。
論理回路をKotlinで実装する
論理回路と一口に言っても種類は様々ですが、今回は「4bit加算器」を作ろうと思います。4bitの2進数を2つ入力に取り、4bitの2進数を1つ出力する回路です。
データ構造
論理回路では、その性質上inputやoutputが複数存在するので、まずはデータの組を作れるTupleと、子クラスを定義することにします1。
abstract class Tuple<out T>(vararg private val output: T) {
operator fun get(idx: Int): T = this.output[idx]
}
このときget関数を実装しておくことで
val t = object: Tuple<Int>(0, 1, 2, 3)
println(t[3]) // 3
みたいな書き方ができるようになります。数が少ないTupleであれば、組み込みのPairのようにプロパティでアクセスさせても良いと思いますが、数が多くなりそうであれば便利になりそうなので実装することにします。
あとは、これを拡張した具象クラスとして、2つ組、3つ組...を実装しておきます。
class Twins<out T>(first: T, second: T) : Tuple<T>(first, second) {
operator fun component1(): T = this[0]
operator fun component2(): T = this[1]
}
class Triplets<out T>(first: T, second: T, third: T) : Tuple<T>(first, second, third) {
operator fun component1(): T = this[0]
operator fun component2(): T = this[1]
operator fun component3(): T = this[2]
}
component*関数は、分解宣言(Destructuring Declarations)というものを使うのに必要な関数で、実装しておくと下記のような書き方ができるようになります。
val triplets = Triplets<Int>(1, 2, 3)
val (v1, v2, v3) = triplets
回路の実装
今回は回路を次のように実装することにします。最終的な出力も、「入力をそのまま出力する回路」と考えて、このインタフェースに従うようにします。
interface Circuit {
val outputs: Tuple<Circuit>
val output: Circuit
get() = this.outputs[0]
}
outputは、デフォルト実装つきプロパティです。論理回路の場合、出力が1つしかないケースもそれなりにあるので、ヘルパーとして用意してあります。
NAND素子を作る
論理素子にはNAND素子という素子があります。!(A & B)を返す素子ですが、この素子には完全性があって、この素子で全ての論理演算を実装できることが証明されています。そこで今回はNANDだけ実装して、他はNANDを使ったクラスとして実装しようと思います2。
まず、Nandのロジックを作ります。ここは普通の条件式を使って作ることになるので割愛しますが、他の素子もNandクラスを使って作れます。
class Nand(private val inputA: Circuit, private val inputB: Circuit) : Circuit {
override val outputs: Tuple<Circuit> = <NANDの結果を返すロジック>
}
NAND素子から他の素子を作る
さて、ここでNAND素子から他の素子を作っていくのですが、NANDが完全性を持っているとは言っても、それを直接使っていくのは大変なので、NOT/AND/ORの3つの素子を作ることを考えます。
まず、NOTを作ります。NOT(A)はNAND(A,A)で実現できます。ここで、Circuitはインタフェースですので、Kotlinのdelegateをつかって簡潔に書くことができます。
class Not(input: Circuit) : Circuit by Nand(input, input)
こう書くことで、Notクラスの処理はNandクラスのインスタンスNand(input, input)が代わりにやってくれます。同様に基礎的な素子を作っていきます。
class And(inputA: Circuit, inputB: Circuit) : Circuit by Not(Nand(inputA, inputB))
class Nor(inputA: Circuit, inputB: Circuit) : Circuit by And(Not(inputA), Not(inputB))
class Or(inputA: Circuit, inputB: Circuit) : Circuit by Not(Nor(inputA, inputB))
class Xor(inputA: Circuit, inputB: Circuit) : Circuit by Not(Or(Nor(inputA, inputB), And(inputA, inputB)))
上の実装は一例で、一般に素子の組み合わせ方は複数あるので、パズル感覚でやってみると面白いかもしれません。
半加算器と全加算器
いよいよ、加算器のベースとなる半加算器と全加算器を作ります。半加算器は2つの1ビット値の加算結果を計算する回路、全加算器は3つ（2値と繰り上がり値）の加算結果を計算する回路です。全加算器まで作れば、それをビット数分組み合わせて4bit加算器が作れます。
これまでと大きく違うのは、出力が複数値になってTupleを使うことになるため、delegateが使えない点です。ひとまず半加算器を作ってみます。
| 入力A | 入力B | 出力 |
|---|---|---|
| 0 | 0 | 00 |
| 0 | 1 | 01 |
| 1 | 0 | 01 |
| 1 | 1 | 10 |
class HalfAdder(inputA: Circuit, inputB: Circuit) : Circuit {
override val outputs: Tuple<Circuit> = Twins(
Xor(inputA, inputB).output,
And(inputA, inputB).output
)
}
byは使えませんが、プロパティを1つ実装すればよさそうです。
続いて全加算器です。全加算器は、シンプルに3値の表を作って作ってもよいのですが、ここでは今作った半加算器を使って作ってみます。HalfAdderの結果の1の位と、3つ目の値をHalfAdderに食わせれば1の位は作れそうですね。2の位は、各半加算器の繰り上がり値のどちらかが1であればいいでしょう。これを実装してみると
class FullAdder(inputA: Circuit, inputB: Circuit, x: Circuit) : Circuit {
override val outputs: Tuple<Circuit> = HalfAdder(inputA, inputB).outputs
.let { val (sum1, carry1) = it as Twins
HalfAdder(sum1, x).outputs.let { val (sum2, carry2) = it as Twins
Twins(sum2, Or(carry1, carry2).output)
}
}
}
こんな感じでしょうか。いままでよりだいぶ複雑になってきました。先にcomponent*系の関数を定義していたおかげで、letの中のラムダが、ちょっとだけ2変数引数の関数っぽく扱えていますね。
4bit加算器
複数bitになった加算器の考え方はシンプルで、下位ビット計算結果の繰り上がり値と、入力の該当ビット2つの加算結果を全加算器で求めてあげれば良さそうです。
class FourBitAdder(inputA: Quadruplets<Circuit>, inputB: Quadruplets<Circuit>) : Circuit {
override val outputs: Tuple<Circuit> = FullAdder(inputA[0], inputB[0], Value.Zero).outputs
.let { val (sum0, carry0) = it as Twins
FullAdder(inputA[1], inputB[1], carry0).outputs
.let { val (sum1, carry1) = it as Twins
FullAdder(inputA[2], inputB[2], carry1).outputs
.let { val (sum2, carry2) = it as Twins
Quadruplets(sum0, sum1, sum2,
FullAdder(inputA[3], inputB[3], carry2).output)
}
}
}
}
※本文中では触れていませんが、Valueクラスは、Circuitを実装した、定数をそのまま返すenum classです。
ここまでできればめでたく4bit加算器の完成です！
おまけ: 7セグメントディスプレイ
加算器はここで終わりですが、せっかくここまで作ったのであればデジタル数字で表示したいですよね。というわけで7セグメントディスプレイを作りました。こういうやつです。
---- ---- ---- ---- ---- ---- ---- ----
| | | | | | | | | | | | | |
---- ---- ---- ---- ---- ---- ----
| | | | | | | | | | | | |
---- ---- ---- ---- ---- ---- ----
これも、1セグメント毎に論理回路を用意すればそれで実現できそうです。今回の場合4bitなので、-8~7を表示するロジックを作れば良さそうですね。
例えば、一番上の横線を出すロジックを考えてみます。詳細は割愛しますが入力値を下位ビットからa0~a3だと定義してあげると、次のような論理式を実現すれば良いことがわかります。
!a0 & !a2 | a1 & !a3 | a1 & !a2 | !a0 & a1 | !a2 & a3 | a0 & a2 & !a3 | a0 & !a1 & a2 | a0 & !a1 & a3
今までと比べて一気に複雑になりましたね。ちなみに、今までの論理素子は2変数しか引数がないので、それで書こうとするとこうなります。
Or(
And(Not(a[0]), Not(a[2])),
Or(
And(a[1], Not(a[2])),
Or(
And(a[1], Not(a[2]))
Or(
And(Not(a[0]), a[1])
... 以下省略
)
)
)
これを7種類書かないといけないとか、考えただけで書くのを諦めそうですね。可変長引数の論理素子を作れば、まだ綺麗に書けそうなので、その方法でやるのもいいのですが、今回のケースでは、演算子オーバーロードを使ってみます。ANDを*、ORを+、NOTを!で書けたら、演算子の優先順位を考えてもちょうど良さそうです3。
実際にやってみます。Circuitに3つの関数を足すだけです。
operator fun Circuit.plus(c: Circuit) = Or(this, c)
operator fun Circuit.times(c: Circuit) = And(this, c)
operator fun Circuit.not() = Not(this)
せっかくなので拡張関数で足してみました。これらを使うと、さっきのややこしかったネストが
!a[0]*!a[2] + a[1]*!a[3] + a[1]*!a[2] + !a[0]*a[1] + !a[2]*a[3] + a[0]*a[2]* a[3] + a[0]*!a[1]* a[2] + a[0]*!a[1]*a[3]
こうなります。かなり読みやすくなりました。これでストレスなく7セグメントディスプレイを実装できそうです。
まとめ
いかがでしたでしょうか？
今回は論理回路というパズルのような題材を使って、Kotlinのいくつかの使い方を紹介しました。Kotlinにはdelegateや拡張関数、演算子オーバーロードなど、ソースコードをより見やすくシンプルに書けるようにするための仕組みが色々盛り込まれています。ソースコードがシンプルに書けるとなんだか嬉しくなりますよね。
この記事が、Kotlinをちょっと触ってみようかなと思っている方の参考になれば幸いです。
なお、作ったソースコードはgithubに上げましたので、よければご覧ください。
https://github.com/noripi/logical_circuit