コンピュータシステムの理論と実装の7章と8章のバーチャルマシンを実装しました

前回の続きです。今回はコンピュータシステムの理論と実装（以下、nand2tetris本）の7章と8章のバーチャルマシンをC言語で実装してみました。

今回のコード

下記、タグv0.0.2になります。

github.com

下記で動かせます。

git clone -b v0.0.2 https://github.com/nihemak/nand2tetris.git
cd nand2tetris
# download nand2tetris environment
./setup.sh
# test all
./test.sh

概要

今回、実装したのは.vmファイルまたは.vmファイル群を入力として受け取り.asmファイルを生成するコマンドです。

バーチャルマシンはスタックベースです。長くなってしまうためここでは細かい仕様の説明は省略します。気になる場合はコンピュータシステムの理論と実装の7章と8章に詳しく記載されています。この記事の目的は自分が後から思い出すためのとっかかりを残すことであるため実装してみた内容の概要の記述にとどめます。

なお、実装は書籍が用意したテストプログラムに対応する形でインクリメンタルに進めました。そのため、次の５つのバージョンが存在し後になるほど高機能になっていきます。

1. スタック算術コマンド に対応
2. メモリアクセスコマンド に対応
3. プログラムフローコマンド に対応
4. 関数呼び出しコマンド（ブートストラップなし） に対応
5. 関数呼び出しコマンド（完全版） に対応

7章（スタック操作）

スタック算術コマンド

ソースコードは07/VMtranslator1/です。

ここでは下記のコマンドに対応しました。

コマンド	概要
add	pop y, pop x, push (x + y)
sub	pop y, pop x, push (x - y)
neg	pop y, push (-y)
eq	pop y, pop x, push (x == y ? -1(true/0xFFFF) : 0(false/0x0000))
gt	pop y, pop x, push (x > y ? -1(true/0xFFFF) : 0(false/0x0000))
lt	pop y, pop x, push (x < y ? -1(true/0xFFFF) : 0(false/0x0000))
and	pop y, pop x, push (x and y)
or	pop y, pop x, push (x or y)
not	pop y, push (not y)
push constant index	push index

下記で使えます。

test07.sh:L3-L16

cp ./nand2tetris/projects/07/StackArithmetic/SimpleAdd/* 07/VMtranslator1/

# ...(省略)...

cd 07/VMtranslator1/

clang --std=c11 -Wall -Wextra -o VMtranslator main.c Parser.c ParserPrivate.c CodeWriter.c CodeWriterPrivate.c

./VMtranslator SimpleAdd.vm 

main.c

コマンドのエントリポイントです。
main.cではコマンド引数の解析、ParserモジュールおよびCodeモジュールを用いたアセンブラへの変換処理を行います。main.cの中で使う関数はmain.c内で下記のように定義しました。

07/VMtranslator1/main.c:L15-L21

int translateByVmDir(DIR *dpVm, char *vmDirName);
int translateByVmFile(char *vmFileName);
bool isVmFileName(char *vmFileName);
void createVmFilePath(char *vmDirName, char *vmFileName, char *vmFilePath);
void createAsmFilePathFromDirName(char *vmDirName, char *asmFilePath);
void createAsmFilePathFromVmFileName(char *vmFileName, char *asmFilePath);
void translate(Parser parser, CodeWriter codeWriter);

コマンド引数には.vmファイルまたは.vmファイルを複数含むディレクトリにいづれかを指定できます。ただし複数の.vmファイルに対応するのは最後になるためここでは1ファイルのみ処理するようにしました。

ディレクトリが指定された場合の処理は次の通りです。.asmファイルを作成し.vmファイルが見つかったら変換処理(translate関数)に引き渡しています。ただしファイル数分ループしていますが1ファイル処理したらbreakで抜けるようにしてあります。

07/VMtranslator1/main.c:L54-L125

int translateByVmDir(DIR *dpVm, char *vmDirName)
{
    char asmFilePath[VM_DIRNAME_MAX_LENGTH + ASM_FILENAME_MAX_LENGTH + 1];
    char vmFilePath[VM_DIRNAME_MAX_LENGTH + VM_FILENAME_MAX_LENGTH + 1];
    int vmFileNum = 0;
    FILE *fpVm, *fpAsm;
    struct dirent *dEntry;
    Parser parser;
    CodeWriter codeWriter;

    if (strlen(vmDirName) > VM_DIRNAME_MAX_LENGTH) {
        fprintf(
            stderr, 
            "Error: Vm dirname max size is invalid. Max size is %d. (%s) is %lu\n", 
            VM_DIRNAME_MAX_LENGTH, 
            vmDirName,
            strlen(vmDirName)
        );
        return 1;
    }

    createAsmFilePathFromDirName(vmDirName, asmFilePath);
    if ((fpAsm = fopen(asmFilePath, "w")) == NULL) {
        fprintf(stderr, "Error: asm file not open (%s)\n", asmFilePath);
        return 1;
    }
    codeWriter = CodeWriter_init(fpAsm);

    while ((dEntry = readdir(dpVm)) != NULL) {
        char *vmFileName = dEntry->d_name;
        if (dEntry->d_type != DT_REG) {  // not file
            continue;
        }
        if (! isVmFileName(vmFileName)) {
            continue;
        }
        if (strlen(vmFileName) > VM_FILENAME_MAX_LENGTH) {
            fprintf(
                stderr, 
                "Skip: Vm filename max size is invalid. Max size is %d. (%s) is %lu\n", 
                VM_FILENAME_MAX_LENGTH, 
                vmFileName,
                strlen(vmFileName)
            );
            continue;
        }
        vmFileNum++;

        createVmFilePath(vmDirName, vmFileName, vmFilePath);
        if ((fpVm = fopen(vmFilePath, "r")) == NULL) {
            fprintf(stderr, "Error: vm file not found (%s)\n", vmFilePath);
            CodeWriter_close(codeWriter);
            return 1;
        }
        CodeWriter_setFileName(codeWriter, vmFileName);

        parser = Parser_init(fpVm);
        translate(parser, codeWriter);

        fclose(fpVm);

        break;
    }
    CodeWriter_close(codeWriter);

    if (vmFileNum == 0) {
        fprintf(stderr, "Error: vm file not found\n");
        return 1;
    }

    return 0;
}

ファイルが指定された場合の処理は次の通りです。.asmファイルを作成し変換処理(translate関数)に引き渡しています。

07/VMtranslator1/main.c:L127-L171

int translateByVmFile(char *vmFileName)
{
    char asmFilePath[ASM_FILENAME_MAX_LENGTH];
    FILE *fpVm, *fpAsm;
    Parser parser;
    CodeWriter codeWriter;

    if (! isVmFileName(vmFileName)) {
        fprintf(stderr, "Error: Vm filename extension(.vm) is invalid. (%s)\n", vmFileName);
        return 1;
    }

    if (strlen(vmFileName) > VM_FILENAME_MAX_LENGTH) {
        fprintf(
            stderr, 
            "Error: Vm filename max size is invalid. Max size is %d. (%s) is %lu\n", 
            VM_FILENAME_MAX_LENGTH, 
            vmFileName,
            strlen(vmFileName)
        );
        return 1;
    }

    if ((fpVm = fopen(vmFileName, "r")) == NULL) {
        fprintf(stderr, "Error: vm file not found (%s)\n", vmFileName);
        return 1;
    }
    parser = Parser_init(fpVm);

    createAsmFilePathFromVmFileName(vmFileName, asmFilePath);
    if ((fpAsm = fopen(asmFilePath, "w")) == NULL) {
        fprintf(stderr, "Error: asm file not open (%s)\n", asmFilePath);
        fclose(fpVm);
        return 1;
    }
    codeWriter = CodeWriter_init(fpAsm);

    CodeWriter_setFileName(codeWriter, vmFileName);
    translate(parser, codeWriter);

    CodeWriter_close(codeWriter);
    fclose(fpVm);

    return 0;
}

変換処理の実装は下記の通りです。.vmファイルをParserモジュールでパースしつつcommandTypeに応じてCodeWriterモジュールで対応するアセンブリ処理を.asmファイルに追記しています。

07/VMtranslator1/main.c:L219-L239

void translate(Parser parser, CodeWriter codeWriter)
{
    char command[PARSER_COMMAND_MAX_LENGTH + 1];
    char segment[PARSER_ARG1_MAX_LENGTH + 1];

    while (Parser_hasMoreCommands(parser)) {
        Parser_advance(parser);
        switch (Parser_commandType(parser)) {
        case PARSER_COMMAND_TYPE_C_ARITHMETIC:
            Parser_arg1(parser, command);
            CodeWriter_writeArithmetic(codeWriter, command);
            break;
        case PARSER_COMMAND_TYPE_C_PUSH:
            Parser_arg1(parser, segment);
            CodeWriter_writePushPop(codeWriter, Parser_commandType(parser), segment, Parser_arg2(parser));
            break;
        default:
            break;
        }
    }
}

Parserモジュール

.vmファイルをパースするためのモジュールです。
main.cで利用する関数はParser.hで下記のように定義しました。parser構造体はtypedefして定義はParser.c内に隠蔽するようにしてオブジェクトとして使うようにしました。それぞれの実装はParser.cで行いました。

07/VMtranslator1/Parser.h:L11-L23

typedef enum {
    PARSER_COMMAND_TYPE_C_ARITHMETIC = 1,
    PARSER_COMMAND_TYPE_C_PUSH
} Parser_CommandType;

typedef struct parser * Parser;

Parser Parser_init(FILE *fpVm);
bool Parser_hasMoreCommands(Parser thisObject);
void Parser_advance(Parser thisObject);
Parser_CommandType Parser_commandType(Parser thisObject);
void Parser_arg1(Parser thisObject, char *arg1);
int Parser_arg2(Parser thisObject);

またParser.c内で使う関数はParserPrivate.hで下記のように定義しParserPrivate.cで実装しました。

07/VMtranslator1/ParserPrivate.h:L7-L16

bool isSpace(FILE *fpVm);
bool isComment(FILE *fpVm);
bool isEndOfFile(FILE *fpVm);
bool isEndOfLine(FILE *fpVm);
bool isToken(FILE *fpVm);
void skipSpaces(FILE *fpVm);
void skipEndOFLines(FILE *fpVm);
void skipComment(FILE *fpVm);
void moveNextAdvance(FILE *fpVm);
void getToken(FILE *fpVm, char *token);

各コマンドごとの処理は下記の通りです。

07/VMtranslator1/Parser.c:L55-L86

Parser_CommandType Parser_commandType(Parser thisObject)
{
    IF_CMP_RET(thisObject->command,  "add", PARSER_COMMAND_TYPE_C_ARITHMETIC);
    IF_CMP_RET(thisObject->command,  "sub", PARSER_COMMAND_TYPE_C_ARITHMETIC);   
    IF_CMP_RET(thisObject->command,  "neg", PARSER_COMMAND_TYPE_C_ARITHMETIC);
    IF_CMP_RET(thisObject->command,   "eq", PARSER_COMMAND_TYPE_C_ARITHMETIC);
    IF_CMP_RET(thisObject->command,   "gt", PARSER_COMMAND_TYPE_C_ARITHMETIC);
    IF_CMP_RET(thisObject->command,   "lt", PARSER_COMMAND_TYPE_C_ARITHMETIC);
    IF_CMP_RET(thisObject->command,  "and", PARSER_COMMAND_TYPE_C_ARITHMETIC);
    IF_CMP_RET(thisObject->command,   "or", PARSER_COMMAND_TYPE_C_ARITHMETIC);
    IF_CMP_RET(thisObject->command,  "not", PARSER_COMMAND_TYPE_C_ARITHMETIC);
    IF_CMP_RET(thisObject->command, "push", PARSER_COMMAND_TYPE_C_PUSH);

    return -1;
}

void Parser_arg1(Parser thisObject, char *arg1)
{
    if (Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_ARITHMETIC) {
        strcpy(arg1, thisObject->command);
    } else if (Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_PUSH) {
        strcpy(arg1, thisObject->arg1);
    }
}

int Parser_arg2(Parser thisObject)
{
    if (Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_PUSH) {
        return atoi(thisObject->arg2);
    }
    return -1;
}

それぞれ実装の詳細はソースコードを参照。

CodeWriterモジュール

コマンドに対応するアセンブリ処理を.asmファイルに追記するためのモジュールです。
main.cで利用する関数はCodeWriter.hで下記のように定義しました。code_writer構造体はtypedefして定義はCodeWriter.c内に隠蔽するようにしてオブジェクトとして使うようにしました。それぞれの実装はCodeWriter.cで行いました。

07/VMtranslator1/CodeWriter.h:L9-L20

typedef struct code_writer * CodeWriter;

CodeWriter CodeWriter_init(FILE *fpAsm);
void CodeWriter_setFileName(CodeWriter thisObject, char *fileName);
void CodeWriter_writeArithmetic(CodeWriter thisObject, char *command);
void CodeWriter_writePushPop(
    CodeWriter thisObject,
    Parser_CommandType command,
    char *segment,
    int index
);
void CodeWriter_close(CodeWriter thisObject);

またCodeWriter.c内で使う関数はCodeWriterPrivate.hで下記のように定義しCodeWriterPrivate.cで実装しました。

07/VMtranslator1/CodeWriterPrivate.h:L8-L16

void fputslist(FILE* fp, ...);

void writeArithmethicAdd(FILE* fpAsm);
void writeArithmethicSub(FILE* fpAsm);
void writeArithmethicNeg(FILE* fpAsm);
void writeArithmethicEq(FILE* fpAsm, char *skipLabel);
void writeArithmethicGt(FILE* fpAsm, char *skipLabel);
void writeArithmethicLt(FILE* fpAsm, char *skipLabel);
void writeArithmethicAnd(FILE* fpAsm);
void writeArithmethicOr(FILE* fpAsm);
void writeArithmethicNot(FILE* fpAsm);

void writePushConstant(FILE* fpAsm, int index);

長くなってしまうため詳細は省きますが例えばaddの実装は下記の通り、対応するアセンブリ処理をfputsで追記しているだけです。fputslist関数は自作のfputsを連続して呼び出す関数です。

07/VMtranslator1/CodeWriterPrivate.c:L11-

// pop y, pop x, push (x + y)
void writeArithmethicAdd(FILE* fpAsm) { writeArithmethicBinaryOperation(fpAsm, "D+M"); }

// ...(省略)...

// Binary operation (M <- x, D <- y)
void writeArithmethicBinaryOperation(FILE* fpAsm, char *comp)
{
    fputslist(
        fpAsm,
        "// BinaryOperation ", comp, "\n",
        // Memory[SP] -= 1
        "@SP\n",
        "M=M-1\n",
        // y <- Memory[Memory[SP]]
        "A=M\n",
        "D=M\n",
        // Memory[SP] -= 1
        "@SP\n",
        "M=M-1\n",
        // x <- Memory[Memory[SP]]
        "A=M\n",
        // Memory[Memory[SP]] <- comp
        "M=", comp, "\n",
        // Memory[SP] += 1
        "@SP\n",
        "M=M+1\n",
        NULL
    );
}

// ...(省略)...

void fputslist(FILE* fp, ...)
{
    char* string;

    va_list args;
    va_start(args, fp);

    while ((string = va_arg(args, char*)) != NULL) {
        fputs(string, fp);
    }

    va_end(args);
}

それぞれ実装の詳細はソースコードを参照。

メモリアクセスコマンド

ソースコードは07/VMtranslator2/です。

ここでは下記のコマンドに対応しました。

コマンド	概要
push local index	push Memory[Memory[LCL]+index]
pop local index	pop Memory[Memory[LCL]+index]
push argument index	push Memory[Memory[ARG]+index]
pop argument index	pop Memory[Memory[ARG]+index]
push this index	push Memory[Memory[THIS]+index]
pop this index	pop Memory[Memory[THIS]+index]
push that index	push Memory[Memory[THAT]+index]
pop that index	pop Memory[Memory[THAT]+index]
push pointer index	push R{3+index}
pop pointer index	pop R{3+index}
push temp index	push R{5+index}
pop temp index	pop R{5+index}
push static index	push Memory[vmFileName.index]
pop static index	pop Memory[vmFileName.index]

下記で使えます。

test07.sh:L20-L40

cp ./nand2tetris/projects/07/MemoryAccess/BasicTest/* 07/VMtranslator2/

# ...(省略)...

cd 07/VMtranslator2/

clang --std=c11 -Wall -Wextra -o VMtranslator main.c Parser.c ParserPrivate.c CodeWriter.c CodeWriterPrivate.c

# ...(省略)...
./VMtranslator BasicTest.vm 

main.c

popに対応しました。

$ diff -r 07/VMtranslator1/main.c 07/VMtranslator2/main.c 
231a232
>         case PARSER_COMMAND_TYPE_C_POP:

Parserモジュール

popに対応しました。

$ diff -r 07/VMtranslator1/Parser.h 07/VMtranslator2/Parser.h 
13c13,14
<     PARSER_COMMAND_TYPE_C_PUSH
---
>     PARSER_COMMAND_TYPE_C_PUSH,
>     PARSER_COMMAND_TYPE_C_POP
$ diff -r 07/VMtranslator1/Parser.c 07/VMtranslator2/Parser.c
40a41
>     case PARSER_COMMAND_TYPE_C_POP:
66a68
>     IF_CMP_RET(thisObject->command,  "pop", PARSER_COMMAND_TYPE_C_POP);
75c77
<     } else if (Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_PUSH) {
---
>     } else {
82c84,85
<     if (Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_PUSH) {
---
>     if (Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_PUSH ||
>         Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_POP) {
$ diff -r 07/VMtranslator1/ParserPrivate.h 07/VMtranslator2/ParserPrivate.h
$ diff -r 07/VMtranslator1/ParserPrivate.c 07/VMtranslator2/ParserPrivate.c

CodeWriterモジュール

constant以外のpushとpopに対応しました。

$ diff -w -r 07/VMtranslator1/CodeWriter.h 07/VMtranslator2/CodeWriter.h 
$ diff -w -r 07/VMtranslator1/CodeWriter.c 07/VMtranslator2/CodeWriter.c
57,60c57,78
<     if (command == PARSER_COMMAND_TYPE_C_PUSH) {
<         if (strcmp(segment, "constant") == 0) {
<             writePushConstant(thisObject->fpAsm, index);
<         }
---
>     switch (command) {
>     case PARSER_COMMAND_TYPE_C_PUSH:
>              if (strcmp(segment, "constant") == 0) writePushConstant(thisObject->fpAsm, index);
>         else if (strcmp(segment,    "local") == 0) writePushLocal(thisObject->fpAsm, index);
>         else if (strcmp(segment, "argument") == 0) writePushArgument(thisObject->fpAsm, index);
>         else if (strcmp(segment,     "this") == 0) writePushThis(thisObject->fpAsm, index);
>         else if (strcmp(segment,     "that") == 0) writePushThat(thisObject->fpAsm, index);
>         else if (strcmp(segment,  "pointer") == 0) writePushPointer(thisObject->fpAsm, index);
>         else if (strcmp(segment,     "temp") == 0) writePushTemp(thisObject->fpAsm, index);
>         else if (strcmp(segment,   "static") == 0) writePushStatic(thisObject->fpAsm, thisObject->vmFileName, index);
>         break;
>     case PARSER_COMMAND_TYPE_C_POP:
>              if (strcmp(segment,    "local") == 0) writePopLocal(thisObject->fpAsm, index);
>         else if (strcmp(segment, "argument") == 0) writePopArgument(thisObject->fpAsm, index);
>         else if (strcmp(segment,     "this") == 0) writePopThis(thisObject->fpAsm, index);
>         else if (strcmp(segment,     "that") == 0) writePopThat(thisObject->fpAsm, index);
>         else if (strcmp(segment,  "pointer") == 0) writePopPointer(thisObject->fpAsm, index);
>         else if (strcmp(segment,     "temp") == 0) writePopTemp(thisObject->fpAsm, index);
>         else if (strcmp(segment,   "static") == 0) writePopStatic(thisObject->fpAsm, thisObject->vmFileName, index);
>         break;
>     default:
>         break;
$ diff -w -r 07/VMtranslator1/CodeWriterPrivate.h 07/VMtranslator2/CodeWriterPrivate.h
18a19,32
> void writePushLocal(FILE* fpAsm, int index);
> void writePopLocal(FILE* fpAsm, int index);
> void writePushArgument(FILE* fpAsm, int index);
> void writePopArgument(FILE* fpAsm, int index);
> void writePushThis(FILE* fpAsm, int index);
> void writePopThis(FILE* fpAsm, int index);
> void writePushThat(FILE* fpAsm, int index);
> void writePopThat(FILE* fpAsm, int index);
> void writePushPointer(FILE* fpAsm, int index);
> void writePopPointer(FILE* fpAsm, int index);
> void writePushTemp(FILE* fpAsm, int index);
> void writePopTemp(FILE* fpAsm, int index);
> void writePushStatic(FILE* fpAsm, char *vmFileName, int index);
> void writePopStatic(FILE* fpAsm, char *vmFileName, int index);
$ diff -w -r 07/VMtranslator1/CodeWriterPrivate.c 07/VMtranslator2/CodeWriterPrivate.c
1a2
> #include "CodeWriter.h"
4c5,6
< #define PUSH_CONSTANT_INDEX_MAX_DIGIT (6)
---
> #define PUSH_POP_INDEX_MAX_DIGIT   (6)
> #define PUSH_POP_SYMBOL_MAX_LENGTH (CODE_WRITER_VM_FILENAME_MAX_LENGTH + PUSH_POP_INDEX_MAX_DIGIT + 1)
9a12,16
> void writePushSymbol(FILE* fpAsm, char *symbol, int index);
> void writePopSymbol(FILE* fpAsm, char *symbol, int index);
> void writePushRegister(FILE* fpAsm, int registerNumber);
> void writePopRegister(FILE* fpAsm, int registerNumber);
> 
34c41
<     char indexStr[PUSH_CONSTANT_INDEX_MAX_DIGIT + 1];
---
>     char indexStr[PUSH_POP_INDEX_MAX_DIGIT + 1];
52a60,131
> // push Memory[Memory[LCL]+index]
> void writePushLocal(FILE* fpAsm, int index) { writePushSymbol(fpAsm, "LCL", index); }
> // pop Memory[Memory[LCL]+index]
> void writePopLocal(FILE* fpAsm, int index)  { writePopSymbol(fpAsm, "LCL", index); }
> 
> // push Memory[Memory[ARG]+index]
> void writePushArgument(FILE* fpAsm, int index) { writePushSymbol(fpAsm, "ARG", index); }
> // pop Memory[Memory[ARG]+index]
> void writePopArgument(FILE* fpAsm, int index)  { writePopSymbol(fpAsm, "ARG", index); }
> 
> // push Memory[Memory[THIS]+index]
> void writePushThis(FILE* fpAsm, int index) { writePushSymbol(fpAsm, "THIS", index); }
> // pop Memory[Memory[THIS]+index]
> void writePopThis(FILE* fpAsm, int index)  { writePopSymbol(fpAsm, "THIS", index); }
> 
> // push Memory[Memory[THAT]+index]
> void writePushThat(FILE* fpAsm, int index) { writePushSymbol(fpAsm, "THAT", index); }
> // pop Memory[Memory[THAT]+index]
> void writePopThat(FILE* fpAsm, int index)  { writePopSymbol(fpAsm, "THAT", index); }
> 
> // push R{3+index}
> void writePushPointer(FILE* fpAsm, int index) { writePushRegister(fpAsm, 3 + index); }
> // pop R{3+index}
> void writePopPointer(FILE* fpAsm, int index)  { writePopRegister(fpAsm, 3 + index); }
> 
> // push R{5+index}
> void writePushTemp(FILE* fpAsm, int index) { writePushRegister(fpAsm, 5 + index); }
> // pop R{5+index}
> void writePopTemp(FILE* fpAsm, int index)  { writePopRegister(fpAsm, 5 + index); }
> 
> // push Memory[vmFileName.index]
> void writePushStatic(FILE* fpAsm, char *vmFileName, int index)
> {
>     char symbol[PUSH_POP_SYMBOL_MAX_LENGTH + 1];
>     sprintf(symbol, "%s.%d", vmFileName, index);
> 
>     fputslist(
>         fpAsm,
>         // Memory[Memory[SP]] <- Memory[symbol]
>         "@", symbol, "\n",
>         "D=M\n",
>         "@SP\n",
>         "A=M\n",
>         "M=D\n",
>         // Memory[SP] += 1
>         "@SP\n",
>         "M=M+1\n",
>         NULL
>     );
> }
> 
> // pop Memory[vmFileName.index]
> void writePopStatic(FILE* fpAsm, char *vmFileName, int index)
> {
>     char symbol[PUSH_POP_SYMBOL_MAX_LENGTH + 1];
>     sprintf(symbol, "%s.%d", vmFileName, index);
> 
>     fputslist(
>         fpAsm,
>         // Memory[SP] -= 1
>         "@SP\n",
>         "M=M-1\n",
>         // Memory[symbol] <- Memory[Memory[SP]]
>         "@SP\n",
>         "A=M\n",
>         "D=M\n",
>         "@", symbol, "\n",
>         "M=D\n",
>         NULL
>     );
> }
> 
137a217,316
> // push Memory[Memory[Symbol]+index]
> void writePushSymbol(FILE* fpAsm, char *symbol, int index)
> {
>     char indexStr[PUSH_POP_INDEX_MAX_DIGIT + 1];
>     sprintf(indexStr, "%d", index);
> 
>     fputslist(
>         fpAsm,
>         "// push symbol ", symbol, " ", indexStr, "\n",
>         // R13 <- Memory[Symbol]+index
>         "@", indexStr, "\n",
>         "D=A\n",
>         "@", symbol, "\n",
>         "D=D+M\n",
>         "@R13\n",
>         "M=D\n",
>         // Memory[Memory[SP]] <- Memory[R13] 
>         "A=M\n",
>         "D=M\n",
>         "@SP\n",
>         "A=M\n",
>         "M=D\n",
>         // Memory[SP] += 1
>         "@SP\n",
>         "M=M+1\n",
>         NULL
>     );
> }
> 
> // pop Memory[Memory[Symbol]+index]
> void writePopSymbol(FILE* fpAsm, char *symbol, int index)
> {
>     char indexStr[PUSH_POP_INDEX_MAX_DIGIT + 1];
>     sprintf(indexStr, "%d", index);
> 
>     fputslist(
>         fpAsm,
>         // Memory[SP] -= 1
>         "@SP\n",
>         "M=M-1\n",
>         // R13 <- Memory[Symbol]+index
>         "@", indexStr, "\n",
>         "D=A\n",
>         "@", symbol, "\n",
>         "D=D+M\n",
>         "@R13\n",
>         "M=D\n",
>         // Memory[R13] <- Memory[Memory[SP]]
>         "@SP\n",
>         "A=M\n",
>         "D=M\n",
>         "@R13\n",
>         "A=M\n",
>         "M=D\n",
>         NULL
>     );
> }
> 
> // push R{registerNumber}
> void writePushRegister(FILE* fpAsm, int registerNumber)
> {
>     char symbol[8];
>     sprintf(symbol, "R%d", registerNumber);
> 
>     fputslist(
>         fpAsm,
>         // Memory[Memory[SP]] <- register
>         "@", symbol, "\n",
>         "D=M\n",
>         "@SP\n",
>         "A=M\n",
>         "M=D\n",
>         // Memory[SP] += 1
>         "@SP\n",
>         "M=M+1\n",
>         NULL
>     );
> }
> 
> // pop R{registerNumber}
> void writePopRegister(FILE* fpAsm, int registerNumber)
> {
>     char symbol[8];
>     sprintf(symbol, "R%d", registerNumber);
> 
>     fputslist(
>         fpAsm,
>         // Memory[SP] -= 1
>         "@SP\n",
>         "M=M-1\n",
>         // register <- Memory[Memory[SP]]
>         "@SP\n",
>         "A=M\n",
>         "D=M\n",
>         "@", symbol, "\n",
>         "M=D\n",
>         NULL
>     );
> }
> 

8章（プログラム制御）

プログラムフローコマンド

ソースコードは08/VMtranslator3/です。

ここでは下記のコマンドに対応しました。

コマンド	概要
label xxx	(vmFileName$xxx)
goto xxx	jump to vmFileName$xxx
if-goto xxx	pop y, if y != 0(false/0x0000) then jump to vmFileName$xxx

下記で使えます。

test08.sh:L8-L31

cp ./nand2tetris/projects/08/ProgramFlow/BasicLoop/* 08/VMtranslator3/

# ...(省略)...

cd 08/VMtranslator3/

clang --std=c11 -Wall -Wextra -o VMtranslator main.c Parser.c ParserPrivate.c CodeWriter.c CodeWriterPrivate.c

# ...(省略)...
./VMtranslator BasicLoop.vm 

main.c

label, goto, if-gotoに対応しました。

$ diff -w -r 07/VMtranslator2/main.c 08/VMtranslator3/main.c 
235a236,247
>         case PARSER_COMMAND_TYPE_C_LABEL:
>             Parser_arg1(parser, segment);
>             CodeWriter_writeLabel(codeWriter, segment);
>             break;
>         case PARSER_COMMAND_TYPE_C_GOTO:
>             Parser_arg1(parser, segment);
>             CodeWriter_writeGoto(codeWriter, segment);
>             break;
>         case PARSER_COMMAND_TYPE_C_IF:
>             Parser_arg1(parser, segment);
>             CodeWriter_writeIf(codeWriter, segment);
>             break;

Parserモジュール

label, goto, if-gotoに対応しました。

$ diff -w -r 07/VMtranslator2/Parser.h 08/VMtranslator3/Parser.h
7c7
< #define PARSER_COMMAND_MAX_LENGTH (4)
---
> #define PARSER_COMMAND_MAX_LENGTH (8)
14c14,17
<     PARSER_COMMAND_TYPE_C_POP
---
>     PARSER_COMMAND_TYPE_C_POP,
>     PARSER_COMMAND_TYPE_C_LABEL,
>     PARSER_COMMAND_TYPE_C_GOTO,
>     PARSER_COMMAND_TYPE_C_IF
$ diff -w -r 07/VMtranslator2/Parser.c 08/VMtranslator3/Parser.c
46a47,53
>     case PARSER_COMMAND_TYPE_C_LABEL:
>     case PARSER_COMMAND_TYPE_C_GOTO:
>     case PARSER_COMMAND_TYPE_C_IF:
>         skipSpaces(thisObject->fpVm);
>         getToken(thisObject->fpVm, thisObject->arg1);
>         strcpy(thisObject->arg2, "");
>         break;
68a76,78
>     IF_CMP_RET(thisObject->command,   "label", PARSER_COMMAND_TYPE_C_LABEL);
>     IF_CMP_RET(thisObject->command,    "goto", PARSER_COMMAND_TYPE_C_GOTO);
>     IF_CMP_RET(thisObject->command, "if-goto", PARSER_COMMAND_TYPE_C_IF);
$ diff -w -r 07/VMtranslator2/ParserPrivate.h 08/VMtranslator3/ParserPrivate.h
$ diff -w -r 07/VMtranslator2/ParserPrivate.c 08/VMtranslator3/ParserPrivate.c

CodeWriterモジュール

label, goto, if-gotoに対応しました。

$ diff -w -r 07/VMtranslator2/CodeWriter.h 08/VMtranslator3/CodeWriter.h
19a20,22
> void CodeWriter_writeLabel(CodeWriter thisObject, char *label);
> void CodeWriter_writeGoto(CodeWriter thisObject, char *label);
> void CodeWriter_writeIf(CodeWriter thisObject, char *label);
$ diff -w -r 07/VMtranslator2/CodeWriter.c 08/VMtranslator3/CodeWriter.c
5a6
> #define LABEL_SYMBOL_MAX_LENGTH (CODE_WRITER_VM_FILENAME_MAX_LENGTH + 24)
81a83,129
> void CodeWriter_writeLabel(CodeWriter thisObject, char *label)
> {
>     char labelSymbol[LABEL_SYMBOL_MAX_LENGTH + 1];
>     sprintf(labelSymbol, "%s$%s", thisObject->vmFileName, label);
> 
>     fputslist(
>         thisObject->fpAsm,
>         "(", labelSymbol, ")\n",
>         NULL
>     );
> }
> 
> void CodeWriter_writeGoto(CodeWriter thisObject, char *label)
> {
>     char labelSymbol[LABEL_SYMBOL_MAX_LENGTH + 1];
>     sprintf(labelSymbol, "%s$%s", thisObject->vmFileName, label);
> 
>     fputslist(
>         thisObject->fpAsm,
>         // goto labelSymbol
>         "@", labelSymbol, "\n",
>         "0;JMP\n",
>         NULL
>     );
> }
> 
> void CodeWriter_writeIf(CodeWriter thisObject, char *label)
> {
>     char labelSymbol[LABEL_SYMBOL_MAX_LENGTH + 1];
>     sprintf(labelSymbol, "%s$%s", thisObject->vmFileName, label);
> 
>     fputslist(
>         thisObject->fpAsm,
>         // Memory[SP] -= 1
>         "@SP\n",
>         "M=M-1\n",
>         // Register <- Memory[Memory[SP]]
>         "@SP\n",
>         "A=M\n",
>         "D=M\n",
>         // if jump(Register != 0) then goto labelSymbol
>         "@", labelSymbol, "\n",
>         "D;JNE\n",
>         NULL
>     );
> }
> 
$ diff -w -r 07/VMtranslator2/CodeWriterPrivate.h 08/VMtranslator3/CodeWriterPrivate.h
$ diff -w -r 07/VMtranslator2/CodeWriterPrivate.c 08/VMtranslator3/CodeWriterPrivate.c

関数呼び出しコマンド（ブートストラップなし）

ソースコードは08/VMtranslator4/です。

ここでは下記のコマンドに対応しました。

コマンド	概要
function f n	(f), push 0 repeat n
return	各種レジスタ復元, goto リターンアドレス

下記で使えます。

test08.sh:L40-L64

cp ./nand2tetris/projects/08/FunctionCalls/SimpleFunction/* 08/VMtranslator4/

# ...(省略)...

cd 08/VMtranslator4/

clang --std=c11 -Wall -Wextra -o VMtranslator main.c Parser.c ParserPrivate.c CodeWriter.c CodeWriterPrivate.c

# ...(省略)...
./VMtranslator SimpleFunction.vm 

main.c

function, returnに対応しました。

$ diff -w -r 08/VMtranslator3/main.c 08/VMtranslator4/main.c 
247a248,254
>         case PARSER_COMMAND_TYPE_C_RETURN:
>             CodeWriter_writeReturn(codeWriter);
>             break;
>         case PARSER_COMMAND_TYPE_C_FUNCTION:
>             Parser_arg1(parser, segment);
>             CodeWriter_writeFunction(codeWriter, segment, Parser_arg2(parser));
>             break;

Parserモジュール

function, returnに対応しました。

$ diff -w -r 08/VMtranslator3/Parser.h 08/VMtranslator4/Parser.h
7,8c7,8
< #define PARSER_COMMAND_MAX_LENGTH (8)
< #define PARSER_ARG1_MAX_LENGTH    (8)
---
> #define PARSER_COMMAND_MAX_LENGTH (16)
> #define PARSER_ARG1_MAX_LENGTH    (32)
17c17,19
<     PARSER_COMMAND_TYPE_C_IF
---
>     PARSER_COMMAND_TYPE_C_IF,
>     PARSER_COMMAND_TYPE_C_FUNCTION,
>     PARSER_COMMAND_TYPE_C_RETURN
$ diff -w -r 08/VMtranslator3/Parser.c 08/VMtranslator4/Parser.c
41a42
>     case PARSER_COMMAND_TYPE_C_FUNCTION:
53a55
>     case PARSER_COMMAND_TYPE_C_RETURN:
78a81,82
>     IF_CMP_RET(thisObject->command, "function", PARSER_COMMAND_TYPE_C_FUNCTION);
>     IF_CMP_RET(thisObject->command,   "return", PARSER_COMMAND_TYPE_C_RETURN);
95c99,100
<         Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_POP) {
---
>         Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_POP ||
>         Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_FUNCTION) {
$ diff -w -r 08/VMtranslator3/ParserPrivate.h 08/VMtranslator4/ParserPrivate.h 
$ diff -w -r 08/VMtranslator3/ParserPrivate.c 08/VMtranslator4/ParserPrivate.c

CodeWriterモジュール

function, returnに対応しました。

$ diff -w -r 08/VMtranslator3/CodeWriter.h 08/VMtranslator4/CodeWriter.h 
22a23,24
> void CodeWriter_writeReturn(CodeWriter thisObject);
> void CodeWriter_writeFunction(CodeWriter thisObject, char *functionName, int numLocals);
$ diff -w -r 08/VMtranslator3/CodeWriter.c 08/VMtranslator4/CodeWriter.c
129a130,218
> void CodeWriter_writeReturn(CodeWriter thisObject)
> {
>     fputslist(
>         thisObject->fpAsm,
>         "// return\n",
>         // Memory[R13] <- Memory[LCL]
>         "@LCL\n",
>         "D=M\n",
>         "@R13\n",
>         "M=D\n",
>         // Memory[R14] <- Memory[Memory[R13]-5]
>         "@5\n",
>         "D=A\n",
>         "@R13\n",
>         "A=M-D\n",
>         "D=M\n",
>         "@R14\n",
>         "M=D\n",
>         // Memory[SP] -= 1
>         "@SP\n",
>         "M=M-1\n",
>         // Memory[Memory[ARG]] <- Memory[Memory[SP]]
>         "@SP\n",
>         "A=M\n",
>         "D=M\n",
>         "@ARG\n",
>         "A=M\n",
>         "M=D\n",
>         // Memory[SP] <- Memory[ARG] + 1
>         "@ARG\n",
>         "D=M+1\n",
>         "@SP\n",
>         "M=D\n",
>         // Memory[THAT] <- Memory[Memory[R13]-1]
>         "@1\n",
>         "D=A\n",
>         "@R13\n",
>         "A=M-D\n",
>         "D=M\n",
>         "@THAT\n",
>         "M=D\n",
>         // Memory[THIS] <- Memory[Memory[R13]-2]
>         "@2\n",
>         "D=A\n",
>         "@R13\n",
>         "A=M-D\n",
>         "D=M\n",
>         "@THIS\n",
>         "M=D\n",
>         // Memory[ARG] <- Memory[Memory[R13]-3]
>         "@3\n",
>         "D=A\n",
>         "@R13\n",
>         "A=M-D\n",
>         "D=M\n",
>         "@ARG\n",
>         "M=D\n",
>         // Memory[LCL] <- Memory[Memory[R13]-4]
>         "@4\n",
>         "D=A\n",
>         "@R13\n",
>         "A=M-D\n",
>         "D=M\n",
>         "@LCL\n",
>         "M=D\n",
>         // goto Memory[R14]
>         "@R14\n",
>         "A=M\n",
>         "0;JMP\n",
>         NULL
>     );
> }
> 
> void CodeWriter_writeFunction(CodeWriter thisObject, char *functionName, int numLocals)
> {
>     char numLocalsString[255];
>     sprintf(numLocalsString, "%d", numLocals);
> 
>     fputslist(
>         thisObject->fpAsm,
>         "// function ", functionName, " ", numLocalsString, "\n",
>         "(", functionName, ")\n",
>         NULL
>     );
>     for (int i = 0; i < numLocals; i++) {
>         writePushConstant(thisObject->fpAsm, 0);
>     }
> }
> 
$ diff -w -r 08/VMtranslator3/CodeWriterPrivate.h 08/VMtranslator4/CodeWriterPrivate.h
$ diff -w -r 08/VMtranslator3/CodeWriterPrivate.c 08/VMtranslator4/CodeWriterPrivate.c

関数呼び出しコマンド（完全版）

ソースコードは08/VMtranslator5/です。

ここでは下記のコマンドに対応しました。また、ブートストラップコードに対応したので.vmファイルには必ずSys.init関数が必要です。

コマンド	概要
call f m	各種レジスタ保存, goto f

下記で使えます。

test08.sh:L66-L82

cp -r ./nand2tetris/projects/08/FunctionCalls/FibonacciElement 08/VMtranslator5/

# ...(省略)...

cd 08/VMtranslator5/

clang --std=c11 -Wall -Wextra -o VMtranslator main.c Parser.c ParserPrivate.c CodeWriter.c CodeWriterPrivate.c

# ...(省略)...
./VMtranslator FibonacciElement

main.c

callおよび複数vmファイルに対応しました。

$ diff -w -r 08/VMtranslator4/main.c 08/VMtranslator5/main.c 
80a81
>     CodeWriter_writeInit(codeWriter);
114,115d114
< 
<         break;
163c162
< 
---
>     CodeWriter_writeInit(codeWriter);
247a247,250
>         case PARSER_COMMAND_TYPE_C_CALL:
>             Parser_arg1(parser, segment);
>             CodeWriter_writeCall(codeWriter, segment, Parser_arg2(parser));
>             break;

Parserモジュール

callに対応しました。

$ diff -w -r 08/VMtranslator4/Parser.h 08/VMtranslator5/Parser.h 
19c19,20
<     PARSER_COMMAND_TYPE_C_RETURN
---
>     PARSER_COMMAND_TYPE_C_RETURN,
>     PARSER_COMMAND_TYPE_C_CALL
$ diff -w -r 08/VMtranslator4/Parser.c 08/VMtranslator5/Parser.c
42a43
>     case PARSER_COMMAND_TYPE_C_CALL:
82a84
>     IF_CMP_RET(thisObject->command,     "call", PARSER_COMMAND_TYPE_C_CALL);
100c102,103
<         Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_FUNCTION) {
---
>         Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_FUNCTION ||
>         Parser_commandType(thisObject) == PARSER_COMMAND_TYPE_C_CALL) {
$ diff -w -r 08/VMtranslator4/ParserPrivate.h 08/VMtranslator5/ParserPrivate.h
$ diff -w -r 08/VMtranslator4/ParserPrivate.c 08/VMtranslator5/ParserPrivate.c

CodeWriterモジュール

callおよび複数vmファイルに対応しました。

$ diff -w -r 08/VMtranslator4/CodeWriter.h 08/VMtranslator5/CodeWriter.h 
12a13
> void CodeWriter_writeInit(CodeWriter thisObject);
22a24
> void CodeWriter_writeCall(CodeWriter thisObject, char *functionName, int numArgs);
$ diff -w -r 08/VMtranslator4/CodeWriter.c 08/VMtranslator5/CodeWriter.c
10a11
> void writePushRegisterByName(FILE* fpAsm, char *registerName);
18a20
>     int callCount;
26a29
>     thisObject.callCount = 0;
38a42,56
> void CodeWriter_writeInit(CodeWriter thisObject)
> {
>     fputslist(
>         thisObject->fpAsm,
>         // Memory[SP] <- 256
>         "@256\n",
>         "D=A\n",
>         "@SP\n",
>         "M=D\n",
>         NULL
>     );
>     // call Sys.init 0
>     CodeWriter_writeCall(thisObject, "Sys.init", 0);
> }
> 
129a148,203
> void CodeWriter_writeCall(CodeWriter thisObject, char *functionName, int numArgs)
> {
>     char numArgsString[255];
>     sprintf(numArgsString, "%d", numArgs);
> 
>     char returnLabel[255];
>     sprintf(returnLabel, "%s$%d", functionName, thisObject->callCount);
> 
>     fputslist(
>         thisObject->fpAsm,
>         "// call ", functionName, " ", numArgsString, "\n",
>         // Memory[Memory[SP]] <- return-address
>         "@", returnLabel, "\n",
>         "D=A\n",
>         "@SP\n",
>         "A=M\n",
>         "M=D\n",
>         // Memory[SP] += 1
>         "@SP\n",
>         "M=M+1\n",
>         NULL
>     );
> 
>     // push LCL, ARG, THIS, THAT
>     writePushRegisterByName(thisObject->fpAsm, "LCL");
>     writePushRegisterByName(thisObject->fpAsm, "ARG");
>     writePushRegisterByName(thisObject->fpAsm, "THIS");
>     writePushRegisterByName(thisObject->fpAsm, "THAT");
> 
>     fputslist(
>         thisObject->fpAsm,
>         // Memory[ARG] <- Memory[SP]-numArgsString-5
>         "@SP\n",
>         "D=M\n",
>         "@", numArgsString, "\n",
>         "D=D-A\n",
>         "@5\n",
>         "D=D-A\n",
>         "@ARG\n",
>         "M=D\n",
>         // Memory[LCL] <- Memory[SP]
>         "@SP\n",
>         "D=M\n",
>         "@LCL\n",
>         "M=D\n",
>         // goto function
>         "@", functionName, "\n",
>         "0;JMP\n",
>         // (return-address) <- {thisObject->vmFileName}${thisObject->callCount}
>         "(", returnLabel, ")\n",
>         NULL
>     );
> 
>     thisObject->callCount++;
> }
> 
246a321,337
> 
> void writePushRegisterByName(FILE* fpAsm, char *registerName)
> {
>     fputslist(
>         fpAsm,
>         // Memory[Memory[SP]] <- Memory[registerName]
>         "@", registerName, "\n",
>         "D=M\n",
>         "@SP\n",
>         "A=M\n",
>         "M=D\n",
>         // Memory[SP] += 1
>         "@SP\n",
>         "M=M+1\n",
>         NULL
>     );
> }
$ diff -w -r 08/VMtranslator4/CodeWriterPrivate.h 08/VMtranslator5/CodeWriterPrivate.h
$ diff -w -r 08/VMtranslator4/CodeWriterPrivate.c 08/VMtranslator5/CodeWriterPrivate.c

まとめ

なんとなくは知っていたはずのバーチャルマシンも実際に実装してみようと思うと大変でした。特にコマンドに対応するアセンブラを考えるのは頭の体操になりました。また相変わらずC言語はディレクトリ、ファイル、文字列操作など大変と感じました。色々怪しい実装部分は残っていますがとりあえず動かせたのはよかったです。