トップ > computer science > 【Elixirで学ぶCS】Elixirで論理ゲートを実装するまで

【Elixirで学ぶCS】Elixirで論理ゲートを実装するまで

computer science Elixir

なにこれ

僕は一応、理工学部の出身ではありますが建築土木が専攻でした
この業界にいながらcsについての知識が皆無
前からやらねば...やらねば..と思ってはいたが触れる機会がない & 一度挫折済み

しかし、アルゴリズムの勉強を始める中でデータ構造の重要性に気づき
データがコンピューター内部でどのように動いているか非常に気になった

良い機会だと思って「コンピュータシステムの理論と実装」を一読することに...
www.oreilly.co.jp

各説明は本を読んだ方が早いのでざっくりの説明で
実装部分をメインにブログで展開していくつもりです

ブール理論

コンピューターは一番下のレイヤーにいけば全て0と1(bool値)の組み合わせで構築されている
この組合せの数をたくさん増やす + 状態を保存(メモリやら)を使えばいろんな計算が出来るよねって話
このbool値を組み合わせて作るのが論理ゲートと呼ばれるもので

  • NOT
  • OR
  • AND

やらがある
さらにこれらの論理ゲートは全て、ベースとなる「NAND」という論理ゲートから作成することが可能
つまりはNANDさえ作れてしまえば全ての論理ゲートは実装可能となる
小さな世界から大きな世界が構築することが出来る(細胞が集まって生物になるみたいな感じ)

Elixirでの実装

NANDさえ作ってしまえば、他の論理ゲートは作成可能なのでまずはNANDから作成する

NANDゲート
NANDゲートは以下のような値を出力する関数とみなす

x y NAND(x, y)
0 0 1
1 0 1
0 1 1
1 1 0

ちょちょっと実装する
(1, 1)の時だけ0を返すようにしてある

defmodule RogicalGate do
  def nand(1, 1), do: 0
  def nand(_x, _y), do: 1
end

テストライブラリを使わずに簡単なテストを行なって
正しい値を出力しているかをチェックする

nand_test = [
  RogicalGate.nand(0,0) == 1,
  RogicalGate.nand(1,0) == 1,
  RogicalGate.nand(0,1) == 1,
  RogicalGate.nand(1,1) == 0,
]

Enum.map(nand_test, &(IO.puts(&1)))
true
true
true
true

あ、いいっすね

NOT
値を反転(0を1に, 1を0に)するのみ

x NOT(x)
0 1
1 0 
defmodule RogicalGate do
  def nand(1, 1), do: 0
  def nand(_x, _y), do: 1
  def not_(x), do: nand(x, x) <-- 追加
end

テストを実行

not_test = [
  RogicalGate.not_(0) == 1,
  RogicalGate.not_(1) == 0,
]

Enum.map(not_test, &(IO.puts(&1)))
true
true

OR

x y OR(x, y)
0 0 0
1 0 1
0 1 1
1 1 1

NANDを3つ組み合わせて実装

defmodule RogicalGate do
  def nand(1, 1), do: 0
  def nand(_x, _y), do: 1
  def or_(x, y), do: nand(nand(x, x), nand(y, y)) <-- 追加
  def not_(x), do: nand(x, x)
end

テスト

or_test = [
  RogicalGate.or_(0, 0) == 0,
  RogicalGate.or_(1, 0) == 1,
  RogicalGate.or_(0, 1) == 1,
  RogicalGate.or_(1, 1) == 1,
]

Enum.map(or_test, &(IO.puts(&1)))
true
true
true
true

AND

x y AND(x, y)
0 0 0
1 0 0
0 1 0
1 1 1

すでに実装したnot_を使ってANDを実装する

defmodule RogicalGate do
  def nand(1, 1), do: 0
  def nand(_x, _y), do: 1
  def or_(x, y), do: nand(nand(x, x), nand(y, y))
  def not_(x), do: nand(x, x)
  def and_(x, y), do: not_(nand(x,y))
end

テスト

or_test = [
  RogicalGate.and_(0, 0) == 0,
  RogicalGate.and_(1, 0) == 0,
  RogicalGate.and_(0, 1) == 0,
  RogicalGate.and_(1, 1) == 1,
]

Enum.map(or_test, &(IO.puts(&1)))
true
true
true
true

いいっすね
次は作成したAND, NOT, ORを組み合わせてXORを作成してみる

XOR
(1, 0)か(0, 1)の際に1を出力させる
ORと異なるのは(1, 1 )の場合に0が返ってくるという点

x y XOR(x, y)
0 0 0
1 0 1
0 1 1
1 1 0

先ほど作成した論理ゲートをフルに使って実装する

defmodule RogicalGate do
  def nand(1, 1), do: 0
  def nand(_x, _y), do: 1
  def or_(x, y), do: nand(nand(x, x), nand(y, y))
  def not_(x), do: nand(x, x)
  def and_(x, y), do: not_(nand(x,y))
  def xor_(x, y), do: or_(and_(x,not_(y)), and_(not_(x),y))
end

xor_test = [
  RogicalGate.xor_(0, 0) == 0,
  RogicalGate.xor_(1, 0) == 1,
  RogicalGate.xor_(0, 1) == 1,
  RogicalGate.xor_(1, 1) == 0,
]

Enum.map(xor_test, &(IO.puts(&1)))
true
true
true
true

nビット論理ゲートへの対応

今まで作成したゲートをnビットの場合にも実行できるようにする
nビットといってもただ入力がリストになって複数入力されるだけで大したことはない

こんな関数を用意した
入力された2次元のリストから値を取り出して、引数から受け取った関数を適宜実行していく
notの場合はリストのサイズが1になるのでcaseで条件を分岐させている

def nbit_converter(inputs, gate_func) do
    Enum.map(inputs, fn row -> 
        case Enum.count(row) == 2 do
          true ->
            [x, y] = row
            gate_func.(x, y)
          false ->
            [x] = row
            gate_func.(x)
        end
      end
    )
  end

この関数を使ってnandなどをnビット対応にラップする
関数を引数で渡す場合には &モジュール名.関数名/引数の数 とすることで可能

defmodule NbitRogicalGate do
  def nbit_converter(inputs, gate_func) do
    Enum.map(inputs, fn row -> 
        case Enum.count(row) == 2 do
          true ->
            [x, y] = row
            gate_func.(x, y)
          false ->
            [x] = row
            gate_func.(x)
        end
      end
    )
  end
  def nand(inputs), do: nbit_converter(inputs, &RogicalGate.nand/2)
  def not_(inputs), do: nbit_converter(inputs, &RogicalGate.not_/1)
  def or_(inputs), do: nbit_converter(inputs, &RogicalGate.or_/2)
  def and_(inputs), do: nbit_converter(inputs, &RogicalGate.and_/2)
  def xor_(inputs), do: nbit_converter(inputs, &RogicalGate.xor_/2)
end

実行結果を見てみる

info = [
  [0, 0],
  [1, 0],
  [0, 1],
  [1, 1],
]

info_for_not = [
  [1],
  [0]
]

res = [
  NbitRogicalGate.nand(info),
  NbitRogicalGate.not_(info_for_not),
  NbitRogicalGate.or_(info),
  NbitRogicalGate.and_(info),
  NbitRogicalGate.xor_(info),
]

Enum.map(res, &(IO.inspect(&1)))

先ほどの表どおり、値が上手く出力された

[1, 1, 1, 0]
[0, 1]
[0, 1, 1, 1]
[0, 0, 0, 1]
[0, 1, 1, 0]

コンピューターで最も基本的なブール理論の論理ゲートの実装が何とか出来た
この論理ゲートの幾多なる組み合わせでコンピューターが動いていると考えると
考えた奴はマジで天才すぎる