やわらかテック

興味のあること。業務を通して得られた発見。個人的に試してみたことをアウトプットしています🍵

【レポート】第9回清流elixir勉強会を開催しました【ウェルカムElixir入門会】

トピック

今回で第9回目の勉強会を開催致しました
elixir-sr.connpass.com

東京で参加したElixir&ErlangFest2019やfukuoka.exさんの勉強会にリモート参加させて頂いた中で
コミュニティの盛り上がり、参加する人の多さが非常に重要であると痛感した

fukuokaex.connpass.com

それもそのはず。3人集まれば文殊の知恵と言うように
多くの人が集まればそれだけ多くの知識、アイディアが生まれる

同じ学習でも自分以外を交えて知識を交換しつつ学ぶ方が明らかに効率が良い

またElixirを4ヶ月程触る中で、いわゆる「良さ」というものを身にしみて理解することが出来た
この素晴らしい仕様と快適さを多くの人に体験してほしいと思った

そんな最もらしいこともあり、今回はElixirの入門会を開催した
結果、新規の方に2名参加していただき、Elixirの良さを伝える機会を頂くことが出来た
スピーカーとして自分は100点ではないのが申し訳ないが、良さは伝えられてたと思っている

清流elixir-infomation
開催場所: 丸の内(愛知)
参加人数: 2 -> 5 update!
コミュニティ参加人数 : 10 -> 13 update!
20190719現在

過去最高の参加者!! ありがとうございます!!

第9回の活動内容

Elixirの入門会を開催した
今までの勉強会の内容を振り返りつつ軽く手を動かしながら進めた
当日のアジェンダは以下

  • やさしいElixir -> Elixirって何やねん。化粧品? ポーション?
  • Elixirの特徴と機能的な話
  • なんで僕がElixirに興味を持っているか
  • Elixirのパワフルなシンタックス

やさしいElixir

まずは新規の参加者のお二人になぜElixirに手を出そうと思ったのかを聞いてみた
普段はpythonなどをメインに書かれており、どっから情報仕入れたのかなと思った

「名前がかっこいいからやろうと思った」

素晴らしいセンスを持っていらっしゃった
当然、Elixirという名前からファイナルファンタジーを連想するが前にもお話した通り
Elixirの作者Joseはファイナルファンタジーをプレイしたことが無いため、関係はない

定番の決まり文句でまずは場を盛り上げつつ、Elixirの概要に触れていく

  • Elixirって何?(全快のポーションではない) 2011年に誕生 -> まだ8歳
  • 2019年にわざわざ学ばなくてもいいプログラミング言語ランキングに7位でランクイン
  • 東海地方ではあまり名を聞くことのないプログラミング言語(2015年あたりに一度バズりがあったらしい) -> Qiitaの記事を種火にRuby勢が盛り上げた

Elixirの特徴と機能的な話

  • Erlangの仮想環境上(BEAM)で動作している
  • Erlangの機能が使用可能 -> 大量の独自プロセスを作成&管理可能
  • Erlang同様に非常に堅牢で、まず落ちない -> 任天堂switchの通知システムは2年間の間、一度も落ちていない(Erlang)
  • ErlangRubyシンタックスの良さを組み合わせ、Erlangの書きにくさが解消された
  • プロセス単位のガベージコレクタでメモリの使い方がかなりエコ
  • 大量の並行処理が気軽に記述可能
  • 終了したプロセスは消してしまうという考えなため、プロセスを再起動させて...なんてことをしなくていい
  • パワフルなシンタックス

Erlangの良さがつらつらと書かれているが、僕はErlang経験がないのでElixirから感銘を受けたのは並行処理、パワフルなシンタックスの部分である
なので上ら辺に書かれているErlangの強みがという部分に確信した情報を持っていないので一度、Erlangドキュメントに目を通さねばと思った
ErlangのOTPの仮想環境(BEAM)を一種のOSのように捉えていたが、本当にそうなのか?という議論になり非常に勉強になった

近日、勉強をしていたコンピューターサインエンスの話と繋がり、やっていてよかったと痛感
.exもしくは.exsの形式で保存されたファイルに記述された文字はElixirもしくはErlangによってコンパイルされ
BEAM(VM)上でbinarycodeに変換され実行されるという認識に落ち着いた
そのためElixirはErlangの機能を使用することが可能であり、OSに依存しない独自のプロセスが使えるということなのではと

なんで僕がElixirに興味を持っているか

このテーマに関しては過去の記事で何度も扱っているので、ざっくりとだけ記述しておく
より文字を読みたい方は以下のリンクを参照してほしい

www.okb-shelf.work

当日はこんな感じで話した(かな

  • 名前がかっこよい
  • 日本(特に東海では先駆者がいない) ではマイナー
  • 関数型言語をやってみたかった
  • 大量のプロセスによる並列処理がビックデータの処理にぴったり

Elixirのパワフルなシンタックス

ここでいうパワフルという意味は「少ない記述で高度な事が可能」という意味で扱っている
まずはEnumの関数達。入門という事で扱ったのは「map, filter, reduceの3つ」
そもそもElixirというか一般的に関数型言語にはfor文(繰り返し処理)が用意されていない
そんな時に使うのがElixirであればEnumの関数(内包表記など)
それぞれの使い方は以下の記事で紹介しているので詳しい話を以下のリンクを参照してほしい

話の落ちどころとしては、オブジェクト言語や手続き型言語で記述していたfor文を使った処理は
全て、Enum.map, Enum.filter, Enum.reduceなどの組み合わせで記述が可能であるということ
(まとめは参加者の方のお言葉をパクリスペクトさせて頂きました)

Enum.map, Enum.filterについて
www.okb-shelf.work

Enum.reduceについて(アキュムレーターという考え方がmapやfilterと異なるため、別に展開)
www.okb-shelf.work

Enumの関数は列挙可能なデータ構造に対して使用可能
列挙可能なデータ構造は以下

  • リスト
  • マップ
  • レンジ

今回は例としてリストを対象に手を動かした
まずはmapとfilterから

lst = [1,2,3,4,5,6,7,8,9,10]

# map: 全ての要素を2倍する
Enum.map(lst, fn num -> num * 2 end)
# [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

# filter: 7より大きい要素を破棄
Enum.filter(lst, fn num -> num < 7 end)
# [1, 2, 3, 4, 5, 6]

mapやfilterはリストを受け取ってリストを出力するため、データの型の変換を行うことが出来ない
そこで役立つのがreduce関数。accumlatorの考え方は上記のリンクをみて欲しい
以下の例ではリストの合計値を求めている。つまりはリストから数値への変換を行なっている

lst = [1,2,3,4,5,6,7,8,9,10]

# 要素の合計値を求める(リスト -> 数値)
Enum.reduce(lst, 0, fn num, acc -> num + acc end)
# 55

うん、すごい
しかし、単純にmap, filter, reduceはpythonにもある
でもElixirはもっとすごい。パイプ演算子という文法が用意されている
上記の3つの処理を順次pythonで行おうとするとこんな感じに

from functools import reduce

lst = [1,2,3,4,5,6,7,8,9,10]
res = map(lambda x: x * 2, lst)
res = filter(lambda x: x < 7, res)
res = reduce(lambda x, acc: x + acc, res)
print(res)
# 12

悪くはないが、都度、変数resに値を渡して、次へ次へと面倒臭い
Elixirであればパイプ演算子を使ってこんな風に記述することが出来る

lst = [1,2,3,4,5,6,7,8,9,10]

Enum.map(lst, fn num -> num * 2 end)
|> Enum.filter(fn num -> num < 7 end)
|> Enum.reduce(fn num, acc -> num + acc end)
|> IO.puts() 
# 12

何をやっているかが一目瞭然で、流れがよく分かる
不要になった部分はコメントアウトして以下のようにすれば良いし、新たに処理を追加するときも楽々だ

lst = [1,2,3,4,5,6,7,8,9,10]

# 処理を減らす
Enum.map(lst, fn num -> num * 2 end)
# |> Enum.filter(fn num -> num < 7 end)
|> Enum.reduce(fn num, acc -> num + acc end)
|> IO.puts()
# 110

# 処理を追加
Enum.map(lst, fn num -> num * 2 end)
|> Enum.filter(fn num -> num < 7 end)
|> Enum.map(fn num -> (num + 10) * 4 end)
|> Enum.reduce(fn num, acc -> num + acc end)
|> Integer.to_string()
|> IO.puts()
# 168

最後にパターンマッチについて触れた
(今回は関数の引数でのパターンマッチとガード説を用いた例を紹介-> fizzbuzzのため)

Elixirでは関数の引数に実際の値を記述しておくことで、その場合にのみ特定の関数を呼び出す事が可能であり
同名の関数を何個でも記述することが可能
(関数を定義するときはモジュール内部に記述する必要あり)

それぞれの対応する値段をパターンマッチを用いて返すという関数を作成した

defmodule Sample do
  def price("apple") do
    110
  end
  def price("banana") do
    150
  end
  def price("orange") do
    90
  end
  def price("grape") do
    540
  end
  def price(_fruit) do
    200
  end
end

in_cart = ["banana", "apple", "fish", "orange", "banana", "grape", "meat"]
convert_to_price = Enum.map(in_cart, fn item -> Sample.price(item) end)
IO.inspect(convert_to_price)

# [150, 110, 200, 90, 150, 540, 200]

まぁマップを使ってvalueを抜く方法は当然あるが、普通に書こうと思うとifをたくさん使うことになる
しかしElixirではパターンマッチを使って簡単に条件を書く事が可能であり、同名の関数を何個でも書けるので仕様変更にも強い
price関数にcherryを追加したければ、price("cherry")という関数を追加するだけだ

また受け取った値に対して、何らかの演算を行なってからパターンマッチを行たいときはガード節というものを使用する
例を見せた方が早い
映画の料金を年齢別に返す関数を作ってみた

defmodule Sample do
  def price(age) when age >= 20 do #20歳以上
    1500
  end
  def price(age) when age >= 10 do #10歳以上
    1000
  end
  def price(_age) do #10歳より下
    800
  end
end

Enum.map([25, 12, 9, 35, 4, 20, 10], fn age -> Sample.price(age) end)
|> IO.inspect()
# [1500, 1000, 800, 1500, 800, 1500, 1000]

パターンマッチは上から順にマッチされていくので2つ目のprice関数にマッチをする際には
1つ目の条件(age >= 20)が適用された状態なので、「20 > age >= 10」としなくても思ったように動く

以上の踏まえてElixirでfizzbuzzを作ってみる
rem()は除算の余りを求める関数である(eg: rem(30, 15) -> 0)

defmodule Sample do
  def fizz_buzz(num) when rem(num, 15) == 0 do
    "fizz_buzz: #{num}"
  end
  def fizz_buzz(num) when rem(num, 5) == 0 do
    "buzz: #{num}"
  end
  def fizz_buzz(num) when rem(num, 3) == 0 do
    "fizz #{num}"
  end
  def fizz_buzz(num) do
    "another #{num}"
  end
end

Enum.map(1..100, fn num -> Sample.fizz_buzz(num) end) |> IO.inspect()
# ["another 1", "another 2", "fizz 3", "another 4", "buzz: 5", "fizz 6",
# "another 7", "another 8", "fizz 9", "buzz: 10", "another 11", "fizz 12",
# "another 13", "another 14", "fizz_buzz: 15"....]

先ほども記述した通りに、仮に7の倍数にヒットさせたいとなった時は
同名のfizzbuzz関数を用意してrem(num, 7) == 0という条件を作成すれば良い
カスタムが非常に楽な上に強力。パターンマッチいいね

感想・まとめ

かなり駆け足で紹介したいものを紹介し尽くした
初めての試み故にうまく出来なかった部分もあるし、思ってたよりもウケた部分もあった
総じて反省、学習して次に生かせればと思う

最後に「Elixirめっちゃいいですね」と言ってもらえて良かった
また秋にでも入門会は開いてみようと思う

次回はfukuoka.exさんの開催するもくもく会にリモートで参加する予定です
また宜しくお願いします

fukuokaex.connpass.com

おまけのコーナー

さらに関数を省略形で記述することでfizzbuzzはもっと短くすることが出来る

defmodule ShortFizzbuzz do
  def fizz_buzz(num) when rem(num, 15) == 0, do: "fizzbuzz: #{num}"
  def fizz_buzz(num) when rem(num, 5) == 0, do: "buzz: #{num}"
  def fizz_buzz(num) when rem(num, 3) == 0, do: "fizz: #{num}"
  def fizz_buzz(num), do: "another: #{num}"
end

Enum.map(1..100, fn num -> ShortFizzbuzz.fizz_buzz(num) end)

いいね

【Elixirで学ぶCS】ElixirでアセンブラとVM変換器を実装するまで

なにこれ(5度目

Elixirでコンピューターサイエンスを学ぶシリーズの第5弾で以下記事の続編です

www.okb-shelf.work

この本を参考に勉強しつつコードを書いています

www.oreilly.co.jp

以前の記事まではかなり低レイヤーの部分をメインとして扱っていた
論理ゲートの実装から行い、加算器を作成し、ALUを作成し、メモリまでの実装が完了した

しかしながら、Elixir上でメモリをクロック同期がうんたらで実装させるには
参考にしている書籍では情報不足でHDL言語では何とか実装出来たのだが、Elixirで実装することが出来なかった
理由としては上の書籍ではCPUのクロック部分の実装は省略されており、付属のアプリケーションに委ねているためで
内部構成を上手く掴むことが出来なかったからだ

いずれはリベンジしたいとは思うが、ここで詰まって他の部分に触れないというのはもったいない
一旦、Elixirで進めるというチャレンジは停止していたが、6章から好きな言語を使って

を実装することが出来る
githubを除いてみたがElixirで実装している人は確認できなかったため、これはいいぞと思い
再び、Elixirのコードを書き始めた

現状としてはアセンブラ(一部バグあり)とVM変換器のメイン部分までの作成までを実装することが出来た(つまりは7章まで)
納品できるレベルではないが、完璧なコードを書くことを目的としておらず、まずはコンピューターサイエンスの全体像を掴むことをメインしているので
一旦は自分の中で良しとした。時間がある時にリベンジすれば良い

あと単純にアセンブラの文法に詳しくなりたいと全く思わないので突き詰める必要がないと判断した
話が少し長くなっているので、「そんなことは知っている」という方は読み飛ばして下さい

久々のブログでテンションが上がっている様です。ずっと仕事でしたので察して下さい

アセンブラについて

普段、我々が業務で使用している言語はいわゆる、高級言語と呼ばれるものであり
より人間が直感的に記述を行うことができるプログラミング言語である
しかしながら、今まで論理ゲートを実装してくる中で触れた通りに、実際にはコンピューターというのは0と1の情報だけで動作をしている

そのため、我々が汗水流しながら書いた高級言語を最終的には全てが0と1で記述されるバイナリコードのレベルまで翻訳をする必要がある
この翻訳の過程にはいくつかのステップが構成される

どうやらコンピューターによって使用が異なる場合がある様だが上から順に以下の様なレイヤー構造を持つ。名称は気にしなくて良い

ここで個人的に思ったことがある
論理ゲートの組み合わせが加算器になり、加算器などの組み合わせがALUになり、最終的にCPUになるという所からスタートしたが
このプログラミング言語が実行可能状態になるまで変換されるまでにも同じ様なレイヤーを持っていることに驚いた

コンピューターの設計の本質にあるのは「抽象化」であり、いつくのものレイヤーが重なることで複雑なことを可能としている
先人の知恵や努力が詰め込まれており、現代のコンピューターが動作をしている

また、この設計はそれぞれが独立したレイヤーとして作成されているため仕様変更も行いやすい
プログラミングでも同じことが言える。小出しに関数をレイヤー的に実装しておけば急な仕様の変更にも対応することが出来る
いいね

話はそれたが、アセンブラというものは書籍の内容と合わせて動きを追ってみる

@2
D=A
@3
D=D+A
@0
M=D

こんなような、かなり低レイヤーの言語をアセンブリ言語と呼ぶ。アセンブリアセンブラは異なるもので
アセンブリ言語バイナリーコードに変換するプログラムのことをアセンブラと呼ぶ

このアセンブリで書かれたコードをアセンブラを使ってバイナリーコードに変換するとこんな感じになる

0000000000000010
1110110000010000
0000000000000011
1110000010010000
0000000000000000
1110001100001000

もう何が何だが分からない。厳密には理解は可能だが可読性が悪いなんてレベルではない
アセンブリがどのように変換を行うかということに関しては説明をしない。書籍を読んだ方が早い
ざっくりとだけ自己満足程度に触れておくと、メモリ内に予め定義したコマンドの対応が用意されており(Elixirでいうmap(%{}))
その対応を元に1行ずつ解析を行なって変換していく

で、このアセンブリ言語を現代において書かれている方というのはあまり存在しないはず
先ほども話した様にコンピューターは構造的に設計されている。プログラミングが実行されるまでの過程でも同様であり
アセンブリ言語の上階層にはVM変換器」というものが存在している
VM変換器はコンパイラから受け取ったVM命令(スタック処理)をアセンブリに変換する

これが

# VM命令
push constant 7
push constant 8
add

こうじゃ

//push constant 7 
@7
D=A
@SP
A=M
M=D
@SP
M=M+1

//push constant 8
@8
D=A
@SP
A=M
M=D
@SP
M=M+1

//add 7 + 6
@SP
M=M-1
@SP
A=M
D=M
@SP
M=M-1
@SP
A=M
M=M+D
@SP
M=M+1

VM変換器を用いることで高級言語コンパイラされた結果に対してあらゆるプラットフォームで実行することができる
プログラミング言語を動作させる環境が変わっても、このVM変換器だけを対象のプラットフォームのために実装すれば良い
(メモリ内に定義されているコマンド対応がプラットフォーム毎に異なるため)

またVM変換器は複数の言語で使用することが可能であり、実行後の結果は同じアセンブリであるため
PythonからElixirを呼び出したりなんてことが可能になる

結局、何が言いたいのかというと、階層を分けて実装しておくことで仕様変更が楽に行えるということである
特にプラットフォームの互換性を保てるというのが凄い

Elixirでの実装

今回は上記のような変換を行うアセンブラVM変換器を実装した
厳密には機能が欠けているが理解に十分と判断したので手を止めた。全てのコードを解説しているとキリがないので
それぞれメイン関数の部分のみ順に説明をしておく。なお実装は書籍にある程度沿って実装した
コードがわりとボリューミィになったのでgithubを参照する
github.com

実装しての感想はElixirってやっぱりいいなって。
何がいいかというとコンピューターの設計は何回も述べている通り、抽象化に沿って階層的に設計されている
この階層的な処理は、流れをもっているという風に捉えることができて、まるでパイプ演算子のようだ
またElixirでは仕様変更、対応忘れてもうた〜、という時に同名関数のパターンマッチを楽々に追加することが出来る
Enum.map()の中でifやらcase書かなければいけないのは仕方がないがモジュール単位でこんなに仕様変更がしやすいのかと改めて驚いた
ifの条件を上から追っていく、つらい作業とはさよなら出来そうだ

アセンブラ

大まかな流れとしては

  • ファイルを読み込む
  • コマンドの種類の判定(AコマンドかCコマンド)
  • コマンドの領域を切り分け
  • バイナリコードへの変換

./assermbra.ex

defmodule Assembra do
  def to_binary(path, save_path) do
    """
      path -> 対象ファイルのパス
      save_path -> 対象ファイルの保存先のパス
    """
    # ファイルを読みこんでコメント記号、空白、改行記号を除去して文字列(各行)を配列にする
    res = Parser.read_file_and_adjustment(path)
          |> code_convert_to_command()
    
    # 変数の一覧表を作成する(symbol tabel)
    [symbol_table, _, _] = create_symbol_table(res)

    # 作成したシンボルテーブルを元に変数にメモリの番号を割り当てる
    replace_from_symbol_table(res, symbol_table)
    # コマンドを領域毎に分割
    |> Enum.map(&(Parser.symbol_or_mnemonic(&1)))
    # 領域毎に分割したコマンドをバイナリーに変換
    |> code_to_binary()
    |> save_to_hack_file(save_path) #保存
  end
end

VM変換器

大まかな流れとしては

  • ファイルを読み込む
  • コマンドの種類の判定(何のコマンドか)
  • コマンドから引数を抜き出す(引数は2で固定なため1,2)
  • VM命令(スタックコマンド)からアセンブリへの変換

./VMtranslator.ex

defmodule VMtranslator do
  def main(path) do
    # 絶対pathからファイル名と保存先を切り出し
    save_path = String.slice(path, 0..-3) <> "asm"
    file_name = String.split(path, "/") |> Enum.at(-1) |> String.slice(0..-4)
    save_string = Parser.read_file_and_adjustment(path) #ファイル読み込みと整形
      |> Stream.map(&(Parser.command_type(&1))) #コマンド種類の判定
      |> Stream.map(&(Parser.arg1(&1))) #第1引数を抜き出し
      |> Stream.map(&(Parser.arg2(&1))) #第2引数を抜き出し
      |> Enum.to_list() #stream -> listに 
      #ファイルの行数をaccumlatorに保存しつつ、mapを実行してアセンブリに変換していく
      |> Enum.map_reduce(0, fn {command, arithmetic, arg1, arg2}, acc ->
          if arithmetic in ["eq", "gt", "lt"] do
             # 特定条件の時にaccに+1をする(変数名が重複しないように)
            {CodeWriter.write_arithmetic({command, arithmetic, arg1, arg2, acc}), acc+1}
          else
            #staticの時にはファイル名を渡す
            if arg1 == "static" do
              {CodeWriter.write_arithmetic({command, arithmetic, arg1, arg2, file_name}), acc}
            else
              {CodeWriter.write_arithmetic({command, arithmetic, arg1, arg2, acc}), acc}
            end
          end
        end)
      # タプルから抜き出して保存
      |> (fn {res, _} -> res end).()
      |> Enum.map(fn {_, converted} -> converted end)
      |> Enum.join("\n")
    File.write(save_path, save_string)
  end
end

かなりざっくりだが、こんな感じになった
今まで作成したコードも合わせて一度githubにpushした

先に本書の8章~13章までの内容には実装をせずに目を通した
ここに来るまでに

という部分までを最低限触れたつもりだ
CPUの実装がElixirで出来なかったことはやや残念だが時間も有限なので仕方ない

本書をベースにすると今後、残されたテーマがコンパイラとOSだが
それぞれの解説が分かりにくかったため、本書を使用するのはここで終わろうと思う

コンパイラに関しては良い記事を発見しているので、そちらを参照していく
OSに関しても別書籍で1冊、目ぼしいものを確認しているのでそちらを

【Elixirで学ぶCS】ElixirでDフリップフロップと1Bitレジスタを実装するまで

なにこれ(4度目

Elixirでコンピューターサイエンスを学ぶシリーズの第4弾で以下記事の続編です

www.okb-shelf.work

この本を参考に勉強しつつコードを書いています

www.oreilly.co.jp

今回は順次回路と呼ばれるCPUのクロックを受けて同期する回路の作成に取り組んだ
一応、それっぽいものは作成することが出来た

しかしながら、なんというか状態を保存しておくという意味で関数型と相性が悪いのかなとも感じた
大量のアキュムレーターの実装が必要になる上に、管理が面倒臭い
単純に下手くそなだけかもしれないが、とりあえず動くものは出来た

ざっくり分かる順次回路

今まで作成してきたものは組み合わせ回路と呼ばれているもので

  • NAND
  • OR
  • AND
  • NOT

などを作成した
詳しくはElixirでコンピューターサイエンスを学ぶの初回の記事を見て頂きたい

www.okb-shelf.work

しかしながら組み合わせ回路のみでは状態の保存をすることが出来ない
1(2)+1(2)を実行できても、その出力値である10(2)が保存できない

そこで役に立つのが順序回路と呼ばれる状態を保存できる回路
しかも、順序回路は組み合わせ回路で作成することが可能であるため
NAND回路が作成できれば作成ができるというコンピューターサイエンスの理論から外れることはない

DFF(D-flip flop)の実装

順序回路を作成するためにDフリップフロップという
最も低レイヤーに存在する回路を作成する必要がある

DフリップフロップもNAND回路から作成することが可能だそうだが、本書の実装に従って
最も低レイヤーの回路としてNAND回路と同位置として扱うため
NAND回路を使用せずにElixirのパターンマッチを使用して実装している

Dフリップフロップは現在のtの値から1つ前のt-1時点での値を返す
日本語が下手で申し訳ないが、実際のデータの動きをみればピンと来るはず

# 毎回0or1の値をcachedに追加していく
t = 5
# 0を最後に追加
cached = [0,1,0,1,0]

#dffは1つ前(t-1 -> 5-1 = 4)の時点の値を返す
res = dff(cached, t )
res #1

作成したdff関数は2つの引数をもつ
第1引数には保存してきた値を保持するためのリストが入り
第2引数にはCPUから発生するクロック(t)をそれっぽく受け取るようにした
この第2引数を使って現在の状態を管理できるようにした(つもり

同名の関数が複数個存在するがElixirでは引数の条件でパターンマッチを行うことが可能で同名の関数をいくらでも実装できる

今回は予期せぬ場合(引数が不正な場合)には強制的に0を返すという仕様にした
例外処理的なことがElixirだと簡単にできるし、パターンが増えたとしても関数を増やせば良いだけなので可読性を保つことが可能だと思っている

defmodule RogicalGate do
  # timeが0の時には0(time 0の受付は想定していない)
  def dff(_, 0), do: 0

  # 保存された値がない場合には0
  def dff([], _), do: 0

  # 保存された値が1つの場合には0(timeとlistの整合性が合わなくなるのを回避する)
  # def dff(in_, _) when length(in_) == 1, do: 0

  # timeが1の場合に初期値である0を返す
  def dff(_, 1), do: 0

  # 上記条件に当てはまらない場合に1つ前の値(リストの後ろから2番目)を返す
  def dff(in_, t), do: Enum.at(in_, t - 2)
end

今更だが、dffはD-flip flopの略
深い意味はない

簡単なテストを行なってみる

res = [
  RogicalGate.dff([], 0) == 0,
  RogicalGate.dff([], 2) == 0,
  RogicalGate.dff([], 1) == 0,
  RogicalGate.dff([1,0], 2) == 1,
  RogicalGate.dff([1,0,1,0], 4) == 1
]

IO.inspect(res)
# [true, true, true, true, true]

次にDフリップフロップを使用してレジスタを実装する

レジスタについて

レジスタはDフリップフロップにsel(保存するかどうか)という値を渡すことで
dffと異なり、現在の入力値を保存するかどうかを選択することが出来る

# sel = 0の場合
cached = [1,0,1,0]
in = 1
sel = 0 #保存しない

cached = [1,0,1,0,0] #前の値を更新しないという意味で0を追加

# sel = 1の場合
cached = [1,0,1,0]
in = 1
sel = 1 #保存する

cached = [1,0,1,0,1] #入力値を保存

1Bit(1桁)対応のレジスタのことをBitと呼ぶ
まずは1Bitのレジスタを作成する。回路図については書籍を参考にした

入力は以下のような形を想定している

#[value, sel]

[
  [1,1], #t=1のとき -> 1を保存
  [0,1], #t=2のとき -> 0を保存
  [1,0], #t=3のとき -> 保存しない
  [1,0] #t=4のとき -> 保存しない
]

先ほど作成したdffを仕様してBitを実装する

defmodule Bit do
  def bit(inputs), do: _bit(inputs, [0], 0)
  # 1つ前の値を返したいのでEnum.at(lst, -2)
  def _bit([], register, _acc), do: {Enum.at(register, -2), register}
  # 再帰関数でhead | tail で処理を実行していく
  def _bit([[x, sel] | tail], register, acc) do
    # sel=1の時に保存
    muxout = RogicalGate.mux([acc, x], sel)
    register = register ++ [muxout]
    #初期値0を保存しないため+1
    dffout = RogicalGate.dff(register, Enum.count(register)+1)
    out = RogicalGate.or_(0, dffout)
    _bit(tail, register, out)
  end
end

思わぬバグが発生してEnum.count()に+1をする羽目になった
それっぽいものは完成したが関数型言語との相性はどうなのよと思った
最終的に{出力値, [保存した値]}が返ってくる

res = Bit.bit([[1,1],[0,1],[1,1],[1,0]])
IO.inspect(res)
# {1, [0, 1, 0, 1, 1]}
res = [
  Bit.bit([[1,1],[0,1],[1,1],[1,0]]) == {1, [0,1,0,1,1]},
  Bit.bit([[0,1],[0,0]]) == {0, [0,0,0]},
  Bit.bit([[1,0],[1,1],[0,0],[1,1],[0,1],[1,0]]) == {0, [0,0,1,1,1,0,0]}
]

IO.inspect(res)

最後にNbitレジスタだが、これは上手く作れていない&自己満なので
Enum.map祭りになっていることは気にしないでほしい

inputs = [
  [[1,1,1,0], 1], #4bit
  [[0,0,1,0], 0], #3bit
  [[1,1,0,1], 1], #2bit
  [[0,0,1,0], 0] #1bit
]

"""
こんな風に見てほしい
----------
4 3 2 1
----------
1 0 1 0(t=1)
1 0 1 0(t=2)
1 1 0 1(t=3)
0 0 1 0(t=4)

"""
#リストの形を上記のように変換
res =
    Enum.map(inputs, fn [row, _sel] -> row end)
    |> Enum.zip()
    |> Enum.map(fn row -> Tuple.to_list(row) end)
    |> Enum.zip(Enum.map(inputs, fn [_row, sel] -> sel end))
    |> Enum.map(fn {row, sel} -> [row, sel] end)

IO.inspect(res)
[
  [[1, 0, 1, 0], 1], 
  [[1, 0, 1, 0], 0], 
  [[1, 1, 0, 1], 1], 
  [[0, 0, 1, 0], 0]
]

先ほどのモジュールにregister関数を追記

defmodule Bit do
  def bit(inputs), do: _bit(inputs, [0], 0)
  def bit(inputs, register), do: _bit(inputs, register, 0)
  def _bit([], register, _acc), do: {Enum.at(register, -2), register}
  def _bit([[x, sel] | tail], register, acc) do
    muxout = RogicalGate.mux([acc, x], sel)
    register = register ++ [muxout]
    dffout = RogicalGate.dff(register, Enum.count(register)+1)
    out = RogicalGate.or_(0, dffout)
    _bit(tail, register, out)
  end
  def converter(inputs) do
    Enum.map(inputs, fn [row, sel] ->
      Enum.map(row, fn x -> [x, sel] end)
    end)
  end
  # selの値を全ての要素に付与する
  def register(inputs), do: _register(converter(inputs), [])
  def register(inputs, acc), do: _register(converter(inputs), acc)
  def _register(inputs, acc) do
    #順に実行していく(今回はreduceでいけた)
    Enum.reduce(inputs, acc, fn data, acc ->
      IO.inspect(data)
      {val, _register} = Bit.bit(data)
      IO.inspect(val)
    acc ++ [val] end)
  end
end

最終的な出力値はこんな感じになる

inputs = [
  [[1,1,1,0], 1],
  [[0,0,1,0], 0],
  [[1,1,0,1], 1],
  [[0,0,1,0], 0]
]

convert =
    Enum.map(inputs, fn [row, _sel] -> row end)
    |> Enum.zip()
    |> Enum.map(fn row -> Tuple.to_list(row) end)
    |> Enum.zip(Enum.map(inputs, fn [_row, sel] -> sel end))
    |> Enum.map(fn {row, sel} -> [row, sel] end)

#変換後: [[[1, 0, 1, 0], 1], [[1, 0, 1, 0], 0], [[1, 1, 0, 1], 1], [[0, 0, 1, 0], 0]]
res = Bit.register(convert)
IO.inspect(res)
# [1, 0, 0, 0]

上手くできていると信じたい
値の保持のさせ方をどうするかでかなり時間がかかってしまった

【レポート】第8回清流elixir勉強会を開催しました【競プロ(Cake and Donuts)@Elixir2】

トピック

今回で第8回目の勉強会を開催致しました
elixir-sr.connpass.com

隔週で勉強会を開催して早3ヶ月...
当初はElixirについてほとんど知らなかったが、現在ではある程度語れるレベルにはなった
Elixirを勉強しないという気持ちから、この面白い言語を多くの人に薦めたいと思うようになった

次回の勉強会ではElixirの入門会のようなことをしようと思う

清流elixir-infomation
開催場所: 丸の内(愛知)
参加人数: 3 -> 2
コミュニティ参加人数 : 10 -> 10 20190629現在

第8回の活動内容

www.okb-shelf.work

簡潔に述べると内容は第6回の続き
Elixirでの実装力を高めるために、競プロ問題をElixirで解いてみようということになった
素晴らしい。実際に何問か解いてみて難しさがよく分かった

Elixirでの標準入力の受け取りに関しては上記のリンクの記事を参照してほしい
今回、挑戦した問題はこちら

atcoder.jp

4ドルのケーキと7ドルのケーキをx個, y個買った時にN円になる組み合わせは存在するかどうか
入力 N
存在する場合: Yes と出力
存在しない場合: Noと出力

単純な組み合わせ問題ではあるが、Elixirでの実装ではかなり頭を使わされた

いろいろな試行錯誤

最初に思いついたことは

  • 4の倍数
  • 7の倍数
  • 11の倍数(4+7)

であればいいんじゃね?と
今思えば、思考不足だが当初はいい線いってるなぁと思いコードに起こしてみた

defmodule Main do
  def main do
    # Nの入力を受け取る
    total_price = IO.gets("") |> String.trim() |> String.to_integer()
    # それぞれの倍数で割り切れるか確認
    judge = Enum.map([4,7,11], fn x -> rem(total_price, x) == 0 end)
    case true in judge do
      true -> "Yes"
      false -> "No"
    end
  end
end

ある程度のケースに対応できるようだが、詰めが甘かった
以下のようなケースではうまく判定ができない

71 -> 7 * 9 + 4 * 2
23 -> 7 * 1 + 4 * 4
45 -> 7 * 3 + 4 * 6

そりゃそうだ。11の倍数でokでは対応出来ていなかった
なので、次に全組み合わせのパターン検索を行なってみた
どういうことかというと

--7 * 0のとき--
7 * 0 + 4 * 1 = 4
7 * 0 + 4 * 2 = 8
:
:
7 * 0 + 4 * n = 4 * n

--7 * 1のとき--
7 * 1 + 4 * 1 = 11
7 * 1 + 4 * 2 = 15
:
:
7 * 1 + 4 * n = 7 + 4 * n

:
:
--7 * nのとき--
7 * n + 4 * 1 = 7 * n + 4
7 * n + 4 * 2 = 7 * n + 8
:
:
7 * n + 4 * n2 = 7 * n + 4 * n2

こんな感じ。Enumを使ってコードに起こしてみる

defmodule Main do
  def main do
    total_price = IO.gets("") |> String.trim() |> String.to_integer()
    res = Enum.map(0..total_price, fn big_num ->
        Enum.map(1..total_price, fn small_num ->
          # 7* n1 + 4 * n2 が入力値に一致した場合にtrueを返す
          if 7 * big_num + 4 * small_num == total_price do
            IO.puts("--> big: #{big_num}, small: #{small_num} ==> #{big_num * 7 + small_num * 4}")
            true
          else
            false
          end
        end)
      end)
      # リストを2次元から1次元に結合
      |> Enum.reduce(fn x, acc -> x ++ acc end)
      # trueが含まれているかを確認
      |> Enum.member?(true)
    if res, do: IO.puts("Yes"), else: IO.puts("No")
  end
end

# 71の時
Main.main()
71
--> big: 1, small: 16 ==> 71
--> big: 5, small: 9 ==> 71
--> big: 9, small: 2 ==> 71
Yes
:ok

# 23の時
--> big: 1, small: 4 ==> 23
Yes
:ok

# 45の時
--> big: 3, small: 6 ==> 45
Yes
:ok

# 16の時
--> big: 0, small: 4 ==> 16
Yes
:ok

とりあえずはいい感じ
しかしながら、現状ではそれぞれ

  • 7: 0..入力値まで
  • 4: 1..入力値まで

のrangeを使っているのでかなりパフォーマンスが悪い
7 +* nの値が入力値を超えた時点で処理が終わるようにしたいので以下のように変更
rangeの上限値には割り算の数値に余りが存在する場合には+1を行なっている

num = 71
res3 = Enum.reduce(1..(div(num, 7) + if rem(num, 7) == 0, do: 0, else: 1), fn x, _acc -> x end)
IO.puts(res3)

# 11

これで無駄な処理が行われないようにできるはず

defmodule Main do
  def main do
    total_price = IO.gets("") |> String.trim() |> String.to_integer()
    # div->割り算に rem->余り が0でなければ1を足し合わせる
    res = Enum.map(0..(div(total_price, 7) + if rem(total_price, 7) == 0, do: 0, else: 1), fn big_num ->
            Enum.map(0..(div(total_price, 4) + if rem(total_price, 4) == 0, do: 0, else: 1), fn small_num ->
              if 7 * big_num + 4 * small_num == total_price do
                IO.puts("--> big: #{big_num}, small: #{small_num} ==> #{big_num * 7 + small_num * 4}")
                true
              else
                false
              end
            end)
          end)
      |> Enum.reduce(fn x, acc -> x ++ acc end)
      |> Enum.member?(true)
    if res, do: IO.puts("Yes"), else: IO.puts("No")
  end
end

こちらも上手く出力された
ただ、Enum.mapでは途中で条件に一致した場合に処理を停止することが出来ない
今回は全パターンの探索を行うことよりもそのパターンが存在する時点で探索を終了してYesを出力すれば良い
なので、無理やり再帰関数で上記のEnum.mapで行なっている処理を再現して、条件に一致した時点で停止するようにした

無駄にすごく長くなってしまって何かうーん...って感じ
やりたいことは出来たと思うけど

defmodule Main do
  def main() do
    # 入力値を受け取り計算を行う関数に渡す
    total_price = IO.gets("") |> String.trim() |> String.to_integer()
    can_buy(total_price, 0)
  end
  # 入力値を超えた時点で終了してNoを出力
  def can_buy(num, accum) when num < 7 * accum, do: IO.puts("No")
  def can_buy(num, accum) do
    if calc(num, accum) do
      IO.puts("Yes")
    else
      can_buy(num, accum + 1)
    end
  end
  def calc(num, accum), do: _calc(num, accum, 0)
  # 7 * n1 + 4 * n2の値が入力値を超えた時点でfalseを返し、次のn1に
  def _calc(num, _big_accum, accum) when num < 4 * accum, do: false
  def _calc(num, big_accum, accum) do
    if 7 * big_accum + 4 * accum == num do
      true
    else
      _calc(num, big_accum, accum + 1)
    end
  end
end

パフォーマンスは若干良くなったような気がするが、コードの記述時間はEnum.mapの方が圧倒的に早い
課題点としてはEnum.mapの途中で処理を終了できればと思う

何か方法はありそうだが、どうなのか...
とりあえずやりたいことはできたので良かった

競プロ難しいわ~

次回について

冒頭でも触れた通り、ある程度Elixirへの知見が溜まってきたため、そろそろElixir入門会を実施したいと思う
コミュニティの人を増やしたいという狙いもある
内容は

  • リストをパイプ演算子Enumでゴリゴリ回す
  • マルチプロセスで並列処理をゴリゴリ回す
  • パターンマッチでFizzBuzzを作る

あたりを考えているが、まだ詰めきれていないので考えなければ

【Elixirで学ぶCS】ElixirでそれっぽいALUが実装できるまで

なにこれ(3度目

Elixirでコンピューターサイエンスを学ぶシリーズの第3弾で以下記事の続編です
www.okb-shelf.work

この本を参考に勉強しつつコードを書いています

相変わらず内容に結構つまづいている
今、土日はだいたいこの本 + cousera使ってcsを勉強している
内容的には最初の方はよりレイヤーが深い話なので挫折しやすいってのがよく分かる
確かに論理ゲートとかいきなり言われてもなぁとは思いつつ、挫折しつつ何とか続いている

なんとか2章の終わりのALUまでを実装できたのでまとめておく

ALUについて

一言でいうとCPUのコアになる演算を行う部分
xとyの入力をリセットしたり、反転させたり、足し合わせたりってことやらが可能

このALUを利用してCPUは演算を行なっている
詳しい仕組みやなぜこの回路でALUが動作するのかという説明は行わない

上記で紹介した書籍などを参考にしてほしい
自分は全テストケースが通ったからOK程度の認識でいる

前回から追加したゲート

先に予備知識となる「sel」について説明する
selは何も難しいものではなくて、入力のどちらを採用するか(0or1)を回路に伝えるためのものである

# sel = 0のとき
input = [x, y]
sel = 0
out = x

# sel = 1のとき
input = [x, y]
sel = 1
out = y

ALUを実現するために、新たなゲートが必要になるのでざっくりと説明しておく

  • Mux回路 -> 複数の入力(x, yの2つ)からselの値を使用して1つを選択
  • Dmux回路 -> 受け取った値をどの位置に通すかを選択

Mux回路については先ほど紹介している & イメージがしやすいと思うが
Dmux回路の説明は言語の限界があるので許して欲しい
Mux回路同様に具体的な値の動き方を見てみる

# sel = 0のとき
val = 1
sel = 0
out = [1, 0]

# sel = 0のとき
val = 1
sel = 1
out = [0, 1]

先ほど説明する際に使用した「位置」という言葉はリストのindex位置だと思ってくれれば良い
入力された値をどのindexに格納して次に渡すかをDmux回路で行なっている

ElixirでMux回路とDmux回路を実装する

まずはシンプルにElixirのパターンマッチを使用して簡易なものを作成してイメージを確かめる

defmodule SimpleMux do
  def mux([a, _b], 0), do: a
  def mux([_a, b], 1), do: b
  def dmux(x, 0), do: {x, 0}
  def dmux(x, 1), do: {0, x}
end

Elixirっぽくていいね。異世界転生かってぐらいのチート実装
それぞれの回路でselのパターンは2種類しかないので楽勝

簡単なテストを実行しておく
まずはMux回路について

mux_test= [
  SimpleMux.mux([0,0], 0) == 0,
  SimpleMux.mux([0,0], 1) == 0,
  SimpleMux.mux([1,0], 0) == 1,
  SimpleMux.mux([1,0], 1) == 0,
  SimpleMux.mux([0,1], 0) == 0,
  SimpleMux.mux([0,1], 1) == 1,
  SimpleMux.mux([1,1], 0) == 1,
  SimpleMux.mux([1,1], 1) == 1,
]
IO.inspect(mux_test)
# [true, true, true, true, true, true, true, true]

次にDmux回路について

dmux_test = [
  SimpleMux.dmux(0, 0) == {0, 0},
  SimpleMux.dmux(0, 1) == {0, 0},
  SimpleMux.dmux(1, 0) == {1, 0},
  SimpleMux.dmux(1, 1) == {0, 1}
]

IO.inspect(dmux_test)
# [true, true, true, true]

しかし、この方法はゲート理論の実装から逸れたものになってしまうのでNG(Elixirごめんな)
なのでnotやandなどの他の回路を使って実装する。回路図はぐぐってね
実装は以前より引き続き使用しているRogicalGateモジュールに追加した

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))
  def mux([x, y], sel) do
    not_sel = not_(sel)
    or_(and_(x, not_sel), and_(y, sel))
  end
  def dmux(x, sel) do
    not_sel = not_(sel)
    {and_(x, not_sel), and_(x, sel)}
  end
end

先ほどのテストを流用。同じことなのでまとめて行う

mux_test= [
  RogicalGate.mux([0,0], 0) == 0,
  RogicalGate.mux([0,0], 1) == 0,
  RogicalGate.mux([1,0], 0) == 1,
  RogicalGate.mux([1,0], 1) == 0,
  RogicalGate.mux([0,1], 0) == 0,
  RogicalGate.mux([0,1], 1) == 1,
  RogicalGate.mux([1,1], 0) == 1,
  RogicalGate.mux([1,1], 1) == 1,
]

dmux_test = [
  RogicalGate.dmux(0, 0) == {0, 0},
  RogicalGate.dmux(0, 1) == {0, 0},
  RogicalGate.dmux(1, 0) == {1, 0},
  RogicalGate.dmux(1, 1) == {0, 1}
]

IO.inspect(mux_test)
# [true, true, true, true, true, true, true, true]
IO.inspect(dmux_test)
# [true, true, true, true]

理論をキッチリ守ることが出来た
次にMux回路とDmux回路をnbit対応させる
実装には以前より使用しているNbitRogicalGateを使用しているが、少し内容を変更している
回路の関数をnbitに対応させるヘルパー関数を用意してmux回路用の変換関数を追加した

defmodule NbitRogicalGate do
  # [x,y]のような入力を2つ受ける回路の変換関数
  def nbit_converter(inputs, gate_func), do: Enum.map(inputs, fn [x, y] -> gate_func.(x, y) end)
  # [x]のような入力を1つ受ける回路(not)の変換関数
  def nbit_not(inputs, gate_func), do: Enum.map(inputs, fn x -> gate_func.(x) end)
  # [[x,y],sel]のような入力を2つ(リストとsel)受ける回路(mux)の変換関数
  def nbit_mux(inputs, gate_func), do: Enum.map(inputs, fn [[x,y], sel] -> gate_func.([x,y], sel)  end)

  def nand(inputs), do: nbit_converter(inputs, &RogicalGate.nand/2)
  def not_(inputs), do: nbit_not(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)

  # ここに追加したよ~
  def mux(inputs), do: nbit_mux(inputs, &RogicalGate.mux/2)
  def dmux(inputs), do: nbit_converter(inputs, &RogicalGate.dmux/2)
end

動作を確認

res = NbitRogicalGate.mux([[[1,0], 0], [[0,0], 1], [[0,1], 1], [[1,1], 1]])
IO.inspect(res)
# [1, 0, 1, 1]

res_dmux = NbitRogicalGate.dmux([[1,0], [0,1], [1,1], [0,0]])
IO.inspect(res_dmux)
# [{1, 0}, {0, 0}, {0, 1}, {0, 0}]

良い感じっぽい
準備もそこそこ出来たのでALUの実装に移る

ALUの実装の前に...

ALUの内部構造について、ざっくりと触れておく
ALUは以下の値を受け取って値の演算を行う関数になる
(nはビット数-1とする。16bitの時は15 -> 0..15)

それぞれの入力値についてまとめる

  • x[0..n] -> 入力値x群
  • y[0..n] -> 入力値y群
  • zx(0or1 -> sel) -> xの値を全て0にするかどうか
  • nx(0or1 -> sel) -> xの値を全て反転するかどうか
  • zy(0or1 -> sel) -> yの値を全て0にするかどうか
  • ny(0or1 -> sel) -> yの値を全て反転するかどうか
  • f(0or1 -> sel) -> and(x, y)とadd(x, y)のどちらを採用するか
  • no(0or1 -> sel) -> 出力値を反転するかどうか

zxはおそらくzero_x, nxはnot_xの略だと思っている
で何?ってなると思うので4bitの演算の動きをサンプルデータを追って見ていく
これで少しはイメージを掴んでもらえればと思う

# 入力値xとy
x = [0,1,1,0]
y = [1,0,0,0]

# sel値
zx = 0
nx = 1
zy = 1
ny = 1
f = 0
no = 1

# xのデータに対しての変換
# zx = 0より(0にしない)
x = [0,1,1,0]

# nx = 1より(値を反転)
x = [1,0,0,1]

# yのデータに対しての変換
# zy = 1より(0にする)
y = [0,0,0,0]

# ny = 1より(値を反転)
y = [1,1,1,1]


# この時点でのxとyの値 -------------
x = [1,0,0,1]
y = [1,1,1,1]
# -----------------------------------

# f = 0より and(x, y)を採用
# こんな感じで処理していく
# [and(1,1), and(0,1), and(0,1), and(1,1)
fout = [1,0,0,1]

# no = 1よりfoutを反転
out = [0,1,1,0]

と、こんな感じで特に難しいことをやっているわけではない
このselの組み合わせで演算に必要なパターン18種が全て表現可能だそう
やっぱり考えた人が天才すぎる...

最終的な出力値のoutと別にzrとngという2つの出力値がある
zrは出力値に1が含まれていれば0を返す
ngは最上位bit(一番上の桁)が1なら1を返す

これでALUの実装の準備が本当に整った
さっそく上記の処理を論理ゲートを使って実装してみる

ALUの実装

先にコードの全体をお見せする
演算を行うメインの関数はcompute関数になる
他の関数については下記で説明をする

defmodule ALU do
  def lst_converter(x, y), do: Enum.map(Enum.zip(x, y), fn {a, b} -> [a, b] end)
  def lst_converter(x, y, sel), do: Enum.map(Enum.zip(x, y), fn {a, b} -> [[a, b], sel] end)
  def val_creater(val, len), do: Enum.map(1..len, fn _ -> val end)
  def compute(x, y, zx, nx, zy, ny, f, no) do
    nxout = common_calc_gate(x, zx, nx)
    nyout = common_calc_gate(y, zy, ny)

    merge_nx_ny = lst_converter(nxout, nyout)
    xandyout = NbitRogicalGate.and_(merge_nx_ny)
    xaddyout = NbitAdder.nbit_adder(merge_nx_ny)

    input_f = lst_converter(xandyout, xaddyout, f)
    fout = NbitRogicalGate.mux(input_f)
    not_fout = NbitRogicalGate.not_(fout)
    merge_fout = lst_converter(fout, not_fout, no)
    out = NbitRogicalGate.mux(merge_fout)
    ng = Enum.at(out, 0)
    zr = if Enum.member?(out, 1), do: 0, else: 1
    {out, zr, ng}
  end
  def common_calc_gate(lst, zero_key, not_key) do
    false_ = val_creater(0, length(lst))
    inputs = lst_converter(lst, false_, zero_key)
    mux_out = NbitRogicalGate.mux(inputs)
    not_out = NbitRogicalGate.not_(mux_out)

    inputs_out = lst_converter(mux_out, not_out, not_key)
    NbitRogicalGate.mux(inputs_out)
  end
end

補助関数について

演算をよしなに進めるためにリストの構造を変化させるlst_converter関数とval_creater関数をそれぞれ実装している
lst_converter関数は2つのリストを以下のように変換している

x = [1,0,1,1]
y = [1,1,1,0]

converted = lst_converter(x, y)
# [[1, 1], [0, 1], [1, 1], [1, 0]] 

# selがある場合(引数が3つの方にマッチ)
x = [1,0,1,1]
y = [1,1,1,0]
sel = 0

converted = lst_converter(x, y, sel)
# [[[1, 1], 0], [[0, 1], 0], [[1, 1], 0], [[1, 0], 0]] 

val_creater関数は受け取った値を指定サイズ分のリストにして返す

val = 1
len = 8
created = val_creater(val, len)
# [1, 1, 1, 1, 1, 1, 1, 1]

ALUのメイン実装

先ほど説明したzx -> nxとzy -> nyの処理は全く同じ処理なので
common_calc_gateという関数で一般化している
論理ゲートでifの動きを再現したい時はmuxを使えば上手くいく

def common_calc_gate(lst, zero_key, not_key) do
    false_ = val_creater(0, length(lst))
    inputs = lst_converter(lst, false_, zero_key)
    # 全て0のリストと入力リストのどちらを採用するか
    mux_out = NbitRogicalGate.mux(inputs)
    not_out = NbitRogicalGate.not_(mux_out)

    # zxもしくはzyの出力を反転するかどうか
    inputs_out = lst_converter(mux_out, not_out, not_key)
    NbitRogicalGate.mux(inputs_out)
  end

次にcommon_calc_gate関数を通して出力された2つのリストからandとaddを実行する
あとはfとnoのselを考慮して先ほどと同じ仕組みでifをmuxで再現する
ngとzrについてはEnumを使って算出しているが、参考にしたコードでもスライス使ってたので良しとした
zrの方だけOrで書き直してもいいかもしれない

defmodule ALU do
  def compute(x, y, zx, nx, zy, ny, f, no) do
    nxout = common_calc_gate(x, zx, nx)
    nyout = common_calc_gate(y, zy, ny)

    # リストを整形
    merge_nx_ny = lst_converter(nxout, nyout)

    # andとaddを計算
    xandyout = NbitRogicalGate.and_(merge_nx_ny)
    xaddyout = NbitAdder.nbit_adder(merge_nx_ny)

    # リストを整形
    input_f = lst_converter(xandyout, xaddyout, f)

    # andかaddのどちらを採用するか
    fout = NbitRogicalGate.mux(input_f)
    not_fout = NbitRogicalGate.not_(fout)
    merge_fout = lst_converter(fout, not_fout, no)

    # 値を反転するかどうか(sel: no)
    out = NbitRogicalGate.mux(merge_fout)

    # ngとzrの値を取得
    ng = Enum.at(out, 0)
    zr = if Enum.member?(out, 1), do: 0, else: 1
    {out, zr, ng}
  end

今回作成するALUはオーバーフローに対応させないため 以前実装した加算器からオーバーフローの対応を一時的に抜いておく

defmodule NbitAdder do
  #再帰関数: リストが空になったら終了
  # accumにcarryの追加をしないように変更
  # defp _nbit_adder([], carry, accum), do: [carry] ++ accum
  defp _nbit_adder([], _carry, accum), do: accum
  defp _nbit_adder([[a1, b1] | tail], carry, accum) do
    {c0, s0} = full_adder(a1, b1, carry)
    _nbit_adder(tail, c0, [s0] ++ accum)
  end
end

一応、ALUの実装は出来たのでやはりテストコードを実行する

x = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
y = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

test1 = [
  ALU.compute(x,y,1,0,1,0,1,0) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,1,1,1,1,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],0,0},
  ALU.compute(x,y,1,1,1,0,1,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,0,0,1,1,0,0) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,1,1,0,0,0,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,0,0,1,1,0,1) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,1,1,0,0,0,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,0,0,1,1,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,1,1,0,0,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],0,0},
  ALU.compute(x,y,0,1,1,1,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],0,0},
  ALU.compute(x,y,1,1,0,1,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,0,0,1,1,1,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,1,1,0,0,1,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],0,1},
  ALU.compute(x,y,0,0,0,0,1,0) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,0,1,0,0,1,1) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],0,0},
  ALU.compute(x,y,0,0,0,1,1,1) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1},
  ALU.compute(x,y,0,0,0,0,0,0) == {[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],1,0},
  ALU.compute(x,y,0,1,0,1,0,1) == {[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],0,1}
]

IO.inspect(test1)
# [true, true, true, true, true, true, true, ... true, true, true, true] すべてtrue
x = [0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1]
y = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1]

test2 = [
  ALU.compute(x,y,1,0,1,0,1,0) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],1,0},
  ALU.compute(x,y,1,1,1,1,1,1) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],0,0},
  ALU.compute(x,y,1,1,1,0,1,0) == {[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],0,1},
  ALU.compute(x,y,0,0,1,1,0,0) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1],0,0},
  ALU.compute(x,y,1,1,0,0,0,0) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1],0,0},
  ALU.compute(x,y,0,0,1,1,0,1) == {[1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0],0,1},
  ALU.compute(x,y,1,1,0,0,0,1) == {[1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0],0,1},
  ALU.compute(x,y,0,0,1,1,1,1) == {[1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1],0,1},
  ALU.compute(x,y,1,1,0,0,1,1) == {[1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1],0,1},
  ALU.compute(x,y,0,1,1,1,1,1) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0],0,0},
  ALU.compute(x,y,1,1,0,1,1,1) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0],0,0},
  ALU.compute(x,y,0,0,1,1,1,0) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],0,0},
  ALU.compute(x,y,1,1,0,0,1,0) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0],0,0},
  ALU.compute(x,y,0,0,0,0,1,0) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0],0,0},
  ALU.compute(x,y,0,1,0,0,1,1) == {[0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0],0,0},
  ALU.compute(x,y,0,0,0,1,1,1) == {[1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0],0,1},
  ALU.compute(x,y,0,0,0,0,0,0) == {[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],0,0},
  ALU.compute(x,y,0,1,0,1,0,1) == {[0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1],0,0},
]

IO.inspect(test2)
# [true, true, true, true, true, true, true, ... true, true, true, true] すべてtrue

いいですね。そろそろこのテスト方法はしんどくなってきたが
ライブラリなしで実行できるので割と気に入っている

とりあえず、情報学部でも何でもないがALUの実装までをElixirで出来た
Elixirの実装の前にhdlというもので実装を行なっており、hdl + Elixirで実装するため
かなり時間がかかっているが言語を変えて実装してみるというのは非常に勉強になる
Elixirの勉強になる上にcsの勉強にもなるため、この勉強法はかなりアリだと思っている

めちゃくちゃ長くなってしまった。過去最高の13000文字。どひゃー