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

なにこれ(5度目

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

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

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