【Swiftで】簡単なアセンブラ実装した

こんちゃーす。普段iOS開発をやってる「よっしー」です。

最近、コンピューターサイエンスのバックグラウンドを身につけたくて、オライリーの「コンピュータシステムの理論と実装」をやってます。

普段ソフトウェアエンジニアをやっている中でアセンブリや機械語に触る機会はまぁなく、アセンブラ実装はすごく刺激的だったので、何を実装したかざっくり知ることができる記事を書きます。

どんな本？

ハードウェアからソフトウェアまで一気通貫で理論理解と実装を進めていくことで、コンピューターアーキテクチャの全体を見渡せるオライリー本。

1章から5章まででハードウェア実装をやり、6章から12章でソフトウェア実装をやります。

実装時間

１週間ぐらい（仕事終わりや休みの日にちまちま作っていたので詳しくは計測してない。）

言語オススメ

なんでも良いのですが、手に馴染んだ言語でTDDを使って実装するのをオススメいたします。
入門したての人にとっては、今までとは全く異なるロジックを実装しないといけないため、不安が常に付きまといます。それを確実に進めるためにテスト駆動した方が良いので、テストを書きやすい普段使っている言語が良さそうです。

実装内容

２パス方式のアセンブラを実装します

この6章はソフトウェアを扱う最初の章で、この本のために作られたアセンブリ言語をHackというプラットフォームの機械語に変換するアセンブラを実装します。好きな高級言語を用いて良いとのことだったので、Swiftで実装しました。

各種モジュールとAPIが本の中で記載されているので、それに従ってアセンブラを構築していきます。記載されているモジュールと内容は以下になります。

モジュール	内容
Parser	アセンブリを適切な領域に分割して返す
Code	ニーモニックを機械語に変換する
SymbolTable	ラベルシンボルや変数シンボルを管理する
main	これらのモジュールを適切に呼び出してアセンブリから機械語を出力する

実際は、もうちょっと独立してテストを書きたい部分もあったので個人的にモジュール分割しています。

アセンブリは以下のような形式で記述されます。　

rect.asm

           @0
           D=M
           @INFINITE_LOOP
           D;JLE
           @counter
           M=D
           @SCREEN
           D=A
           @address
           M=D
        (LOOP)
           ...

上記のコードを以下のような機械語に変換するのが目標です。

rect.hack

        0000000000000000
        1111110000010000
        0000000000010111
        1110001100000110
        0000000000010000
        1110001100001000
        0100000000000000
        1110110000010000

各モジュールに対して、簡単な解説と実装サンプルをお見せしていきます。

Parser

与えられたアセンブリを読み込んで、適切な領域に分割して返すモジュールを実装します。
例えばこれは、与えられたアセンブリの中から dest 領域だけを切り出す処理

本書では、 この処理はC命令の時にしか呼ばれてはならない のような記述があるので、その前提条件を precondition で表現しています。

Parser.swift

    var dest: String {
        precondition(commandType == .c)

        if let equalIndex = currentCommand.firstIndex(of: "=") {
            return String(currentCommand[..<equalIndex])
        } else {
            return "null"
        }

    }

Code

分割済みのニーモニックを受け取り、機械語を返すモジュールです。副作用がないので　static func として各種関数を実装しました。

例えば　jump(from:) では分岐条件を決めるニーモニックが渡され、その内容を見て各種ビットの内容を決めています。

guard 節より下部には規則性があったので楽に書きました。

Code.swift

final class Code {
    (中略)
    static func jump(from mnemonic: String) -> String {
        guard mnemonic != "JNE" else {
            return "101"
        }

        guard mnemonic != "JMP" else {
            return "111"
        }

        let j1 = mnemonic.contains("L").binary
        let j2 = mnemonic.contains("E").binary
        let j3 = mnemonic.contains("G").binary
        return "\(j1)\(j2)\(j3)"
    }

}

extension Bool {

    var binary: Int {
        return self == true ? 1 : 0
    }

}

SymbolTable

上記二つのモジュールだけでも、定義済みシンボルだけなら問題なく実装できました。しかし、ユーザー定義のシンボルがあると、それとメモリアドレスの対応づけを管理する必要があります。それがこのモジュールです。

addEntry(symbol:, address:) が（シンボル、アドレス）追加のAPIとなっています。

定義済みシンボルにはR0とSPのように同じメモリアドレスを指すものがあります。詳しい実装方法には言及されていなかったので、僕はR0~R15までをforEach で初期化してSP,LCLのような別名は findAlias(symbol:) という関数でアドレスを返すようにしました。

SymbolTable.swift

final class SymbolTable {
    private(set) var table: [String: Int16] = [:]

    init() {
        (0...15).forEach { table["R\($0!)"] = $0 }
        table["SCREEN"] = 16384
        table["KBD"] = 24576
    }

    func addEntry(symbol: String, address: Int16) {
        table[symbol] = address
    }

    func contains(symbol: String) -> Bool {

        guard findAlias(symbol: symbol) == nil else {
            return true
        }

        return table[symbol] != nil
    }

    func getAddress(symbol: String) -> Int16 {
        if let alilas = findAlias(symbol: symbol) {
            return alilas
        } else {
            let address = table[symbol]
            assert(address != nil)

            return address!
        }
    }

    private func findAlias(symbol: String) -> Int16? {
        switch symbol {
        case "SP":
            return table["R0"]

        case "LCL":
            return table["R1"]

        case "ARG":
            return table["R2"]

        case "THIS":
            return table["R3"]

        case "THAT":
            return table["R4"]

        default:
            return nil
        }
    }

}

Assembler

アセンブルの処理をメイン関数として実装してしまうと、コマンドラインとしてのI/O処理も加わってテストしにくいので、Assembler という結合モジュールを実装しました。

内部では、上記で説明したモジュールを使って、
- 1回目の実行で、ユーザー定義シンボルだけをシンボルテーブルに追加する
- 2回目の実行で、アセンブリを機械語に変換する。記述されたシンボルがシンボルテーブルに追加されている場合は、メモリアドレスを取得して機械語に変換する。

などのようなことを1行ずつ最後までしています。

アセンブリをガッと渡したら、機械語をバッと返してくれるモジュールです！

テストは以下のように実装しました。（内部実装は面倒なので割愛)

testAdd.swift

func testAdd() {
        let testAssembly = """
        // This file is part of www.nand2tetris.org
        // and the book "The Elements of Computing Systems"
        // by Nisan and Schocken, MIT Press.
        // File name: projects/06/max/Max.asm

        // Computes R2 = max(R0, R1)  (R0,R1,R2 refer to RAM[0],RAM[1],RAM[2])

           @R0
           D=M              // D = first number
           @R1
           D=D-M            // D = first number - second number
           @OUTPUT_FIRST
           D;JGT            // if D>0 (first is greater) goto output_first
           @R1
           D=M              // D = second number
           @OUTPUT_D
           0;JMP            // goto output_d
        (OUTPUT_FIRST)
           @R0
           D=M              // D = first number
        (OUTPUT_D)
           @R2
           M=D              // M[2] = D (greatest number)
        (INFINITE_LOOP)
           @INFINITE_LOOP
           0;JMP            // infinite loop
        """

        let expectation = """
        0000000000000000
        1111110000010000
        0000000000000001
        1111010011010000
        0000000000001010
        1110001100000001
        0000000000000001
        1111110000010000
        0000000000001100
        1110101010000111
        0000000000000000
        1111110000010000
        0000000000000010
        1110001100001000
        0000000000001110
        1110101010000111
        """

        let assembler = Assembler(assembly: testAssembly)
        let assembled = assembler.assembled()
        XCTAssertEqual(assembled, expectation)
    }

感想

難易度はかなり高かったですが、パズルみたいで楽しめました。

副次的効果として、テスト駆動の重要性と効果について初めて大きな利益を享受できました。
普段のiOS開発は、より良い書き方や実装方法はあるとしても「全く実装がわからない」というケースは基本的には遭遇しなかったので、TDDのメリットを感覚的に理解しきれなかったところがあったのですが、このアセンブラ実装は本当に訳が分からなくて不安しかない状態で始まったので、テストのおかげで実装を最後までやりきることができました。(TDDの教材に追加してほしいぐらい。)

次はバーチャルマシンの実装なのですが、かなり楽しみなので気合い入れてやってきます。

GitHub

自分の実装レポジトリはこちらにおいて置きますので参考になるかはわかりませんが、よければチラ見してくださーい。PRお待ちしておりまーす。

(CommandLine化するの面倒くさくなって、Assembler.swiftのテストだけ通してメイン関数実装していないですが許して！）
https://github.com/syatyo/HackAssembler