Nand2Tetris_Part2_08

Keep going.

Unit 8.1 Program Control

In this course, there have 2 components in program control:

• Functions: make the basic language can be extended at will.
• Branching: choose different solutions.

More precisely,
✅Branching commands:

• goto label
• if-goto label
• label label

✅Function commands:

• call function
• function function
• return

Unit 8.2 Branching

✅A. Unconditional branching: goto label
Jumps to execute the command just after label.

✅B. Conditional branching: if-goto label
if cond jump to execute the command just after label(Requires pushing the condition to the stack just before the if-goto command).

✅C. label

Implementation: Translate each branching command into assembly instructions that effect the specified operation.
🎉Simple: the assembly language has similar branching commands.

Unit 8.3 Functions: Abstraction

A. Functions in the VM language

The VM language features:

• primitive operations(fixed): add, sub, …
• abstract operations(extensible): multiply, sqrt, …

B. Functions in the VM language: defining

high-level language     pesudo VM code            final VM code
mult(int x, int y) ---> function mult(x, y) ---> function mult 2

C. Functions in the VM language: executing

⭐Caller: the calling function, Callee: the called function.

In the mult function, it has 3 stacks: stack, argument, local to execute the function code.

D. Making the abstraction work: implementation

For each function call during run-time, the implementation has to:

1. Pass parameters from the caller to the callee;
2. Determine the return address within the caller’s code;
3. Save the caller’s return address, stack and memory segments;
4. Jump to execute the callee.

For each function return during run-time, the implementation has to:

1. Return to the caller the calue computed by the called function;
2. Recycle the meory resources used by the called function;
3. Reinstate the caller’s stack and memory segments;
4. Jump to the return address in the caller’s code.

Unit 8.4 Function Call and Return: Implementation Preview

A. Function execution

• A computer program typically consists of many functions.
• During a given point of time, only a few functions are executing.
• Calling chain: foo -> bar -> sqrt -> …

B. The function’s state

During run-time:

• Each function uses a working stack + memory segments.
• The working stack and some of the segments should be:
  • Created when the function starts running,
  • Maintained as long as the function is executing,
  • Recycled when the function returns.

Once the callee starts running, the state of the caller has to be saved somewhere. When the callee has terminated, we can reinstate the caller’s state and continue it’s execution.

How to maintain the states of all the functions up the calling chain?
✨The answer is stack.

C. Function call and return: call

VM implementation:

1. Sets args
2. Saves the caller’s frame
3. Jumps to execute foo

D. Function call and return: function

VM implementation:

1. Sets up the local segment of the called function
2. The called function is running, doing something
3. When the called function end, it will prepare to return

E. Function call and return: return

VM implementation:

1. Copies the return value onto argument 0
2. Restores the segment pointers of the caller
3. Clears the stack
4. Sets SP for the caller
5. Jumps to the return address within the caller’s code.

F. The global stack

The global stack is the physical memory.
⭐block: every function’s global stack, include: argument, saved infomation belongs to caller, local, working stack.

Unit 8.5 Function Call and Return: Run-time Simulation

Unit 8.6 Function Call and Return: Implementation

A. Contract: the calling function’s view

• Before calling another function, I must push as many arguments as the function expects to get;
• Next, I invoke the function using call functionName nArgs;
• After the called function returns, the argument values that I pushed before the call have disappeared from the stack, and a return value(that always exists) appears at the top of the stack;
• After the called function returns, all my memory segments are exactly the same as they were before the call(except the temp is undefined and some values of my static segment may have changed).

B. Contract: the called function’s view

• Before I start executing, my argument segment has been initialized with the argument values passed by the caller;
• My local variables segment has been allocated and initialized to zeros;
• My static segment has been set to the static segment of the VM file to which I belong(memory segments this, that, pointer and temp are undefined upon entry)
• My working stack is empty
• Before returning, I must push a value onto the stack.

C. The VM implementation view

        VM Translator
VM code -------------> Assembly code

Handing call

VM command: call functionName nArgs
(calls the function, informing that nArgs arguments have been pushed onto the stack)

Assembly code(generated by the translator):

Handing function

VM command: function functionName nVars
(here starts a function that has nVars local variables)

Assembly code(generated by the translator):

Handing return

VM command: return

Assembly code(generated by the translator):

Unit 8.7 VM Implementation on the Hack Platform

Booting

VM programming convention:
One file in any VM program is expected to be named Main.vm; one VM function in this file is expected to be named main.

VM implementation convention:
When the VM implementation starts running, or is reset, it starts executing the argument-less OS function Sys.init; Sys.init then calls Main.main, and enters an infinite loop.

Hardware platform convention:

// Bootstrap code
SP=256
Call Sys.init

Standard mapping of the VM on the Hack platform

What we need to care about is the content of the following picture:

Special symbols in VM programs

see the book.😁

Unit 8.8 VM Translator: Proposed Implementation

Main

Parser

CodeWriter

Unit 8.9 Building the VM Translator, Part II

Unit 8.9 Project 8: Building VM Translator, Part II

Extend the basic VM translator built in Project 7 into a full-scale VM translator. In particular, add the ability to handle the program flow and function calling commands of the VM language.

Here is the codes:

commandtype.h

#ifndef __COMMANDTYPE_H__
#define __COMMANDTYPE_H__

enum CommandType {
    C_UNKONWN,
    C_ARITHMETIC,
    C_PUSH,
    C_POP,
    C_LABEL,
    C_GOTO,
    C_IF,
    C_FUNCTION,
    C_RETURN,
    C_CALL,
};

#endif

✅ commandtype.h has no difference with the previous version.

parser.h

#ifndef __PARSER_H__
#define __PARSER_H__

#include <fstream>
#include <string>
#include <vector>

#include "commandtype.h"

using namespace std;

class Parser {
public:
    Parser(const string& filename);
    ~Parser();
    bool hasMoreCommands();
    void advance();
    CommandType commandType();
    string arg1();
    string arg2();
    uint16_t arg3();

private:
    ifstream m_ifs;
    vector<string> m_tokens;
};

#endif

✅ parser.h has no difference with the previous version.

parser.cpp

#include "parser.h"

#include <exception>
#include <iostream>
#include <regex>
#include <sstream>

Parser::Parser(const string& filename) {
    m_ifs.open(filename, ios::in);
    if(!m_ifs) {
        throw runtime_error("Parser Failed to open file: " + filename);
    }
}

Parser::~Parser() {
    m_ifs.close();
}

bool Parser::hasMoreCommands() {
    return !m_ifs.eof();
}

void Parser::advance() {
    if(!hasMoreCommands())
        return;
    
    m_tokens.clear();
    string line;
    while(getline(m_ifs, line)) {
        regex endl_re("\\r*\\n+");
        regex space_re("\\s+");
        line = regex_replace(line, endl_re, "");
        line = regex_replace(line, space_re, " ");
        stringstream ss(line);
        string token;
        while(getline(ss, token, ' ')){
            if(token == "//") break;
            m_tokens.push_back(token);
        }
        if(!m_tokens.empty()) break;
    }
}

CommandType Parser::commandType() {
    CommandType ret = C_UNKONWN;
#define XX(str, type) \
    if(m_tokens[0] == str) \
        ret = type;

    if(m_tokens.size() == 1) {
        XX("add", C_ARITHMETIC);
        XX("sub", C_ARITHMETIC);
        XX("neg", C_ARITHMETIC);
        XX("eq", C_ARITHMETIC);
        XX("gt", C_ARITHMETIC);
        XX("lt", C_ARITHMETIC);
        XX("and", C_ARITHMETIC);
        XX("or", C_ARITHMETIC);
        XX("not", C_ARITHMETIC);

        XX("return", C_RETURN);
    } else if(m_tokens.size() == 2) {
        XX("label", C_LABEL);
        XX("goto", C_GOTO);
        XX("if-goto", C_IF);
    } else if(m_tokens.size() == 3) {
        XX("push", C_PUSH);
        XX("pop", C_POP);
        XX("function", C_FUNCTION);
        XX("call", C_CALL);
    }

#undef XX
    return ret;
}

string Parser::arg1() {
    return m_tokens[0];
}

string Parser::arg2() {
    CommandType cmd = commandType();
    stringstream ss;
    if(cmd == C_PUSH || cmd == C_POP || cmd == C_FUNCTION || cmd == C_CALL ||
        cmd == C_LABEL || cmd == C_GOTO || cmd == C_IF) {
        ss << m_tokens[1];
    }
    return ss.str();
}

uint16_t Parser::arg3() {
    CommandType cmd = commandType();
    uint16_t ret = 0;
    if(cmd == C_PUSH || cmd == C_POP || cmd == C_FUNCTION || cmd == C_CALL) {
        ret = stoul(m_tokens[2]);
    }
    return ret;
}

🔨 parser.cpp has one difference with the previous version: the function arg2 has been modified.

codewriter.h

#ifndef __CODEWRITER_H__
#define __CODEWRITER_H__

#include <fstream>
#include <string>

#include "commandtype.h"

using namespace std;

class CodeWriter {
public:
    CodeWriter(const string& filename);
    ~CodeWriter();
    void Close();
    static void setFunctionName(const string& functionName);
    static void setCurParseFileName(const string& filename);

    void writeArithmetic(const string& command);
    void writePushPop(CommandType command, const string& segment, uint16_t index);
    void writeInit();
    void writeLabel(const string& label);
    void writeGoto(const string& label);
    void writeIf(const string& label);
    void writeCall(const string& functionName, int numArgs);
    void writeReturn();
    void writeFunction(const string& functionName, int numArgs);

private:
    static string transName(const string &segment);

private:
    static string cd_add();
    static string cd_sub();
    static string cd_neg();
    static string cd_eq();
    static string cd_gt();
    static string cd_lt();
    static string cd_and();
    static string cd_or();
    static string cd_not();

    static string cd_push(const string& segment, uint16_t index);
    static string cd_pop(const string& segment, uint16_t index);

private:
    ofstream m_ofs;
    static string m_curParseFileName;
    static string m_functionName;
};

#endif

🔨 codewriter.h has several differences with the previous version: enable VM translator to handle programm flow and functions calling commands.

codewriter.cpp

#include "codewriter.h"

#include <functional>
#include <iostream>
#include <map>
#include <sstream>

static uint16_t cmpLabelCount = 0;
static uint16_t retAddrCount = 0;
string CodeWriter::m_functionName;
string CodeWriter::m_curParseFileName;

CodeWriter::CodeWriter(const string& filename) {
    m_ofs.open(filename, ios::out);
    if(!m_ofs) {
        throw runtime_error("CodeWriter Failed to open file: " + filename);
    }
    writeInit();
}

CodeWriter::~CodeWriter() {
    Close();
}

void CodeWriter::Close() {
    m_ofs.close();
}

void CodeWriter::setFunctionName(const string& functionName) {
    m_functionName = functionName;
}

void CodeWriter::setCurParseFileName(const string& filename) {
    m_curParseFileName = filename;
}

void CodeWriter::writeArithmetic(const string& command) {
    // m_ofs << "// " << command << '\n';
    static map<string, function<string()>> s_arithmetics = {
        {"add", cd_add},
        {"sub", cd_sub},
        {"neg", cd_neg},
        {"eq", cd_eq},
        {"gt", cd_gt},
        {"lt", cd_lt},
        {"and", cd_and},
        {"or", cd_or},
        {"not", cd_not},
    };
    m_ofs << s_arithmetics[command]() << '\n';
}

void CodeWriter::writePushPop(CommandType command, const string& segment, uint16_t index) {
    function<string(const string&, int)> cb;
    if(command == C_PUSH) {
        // m_ofs << "// push " << segment << " " << index << '\n';
        cb = cd_push;
    } else if(command == C_POP) {
        // m_ofs << "// pop " << segment << " " << index << '\n';
        cb = cd_pop;
    }
    m_ofs << cb(segment, index) << '\n';
}

void CodeWriter::writeInit() {
    // m_ofs << "// writeinit\n" << << "// SP = 256\n";
    stringstream ss;
    ss << "@256\nD=A\n@SP\nM=D\n";
    m_ofs << ss.str() << '\n';
    writeCall("Sys.init", 0);
}

void CodeWriter::writeLabel(const string& label) {
    // m_ofs << "// label " << label << '\n';
    if('0' <= label[0] && label[0] <= '9') {
        throw runtime_error("[syntax error] label can't start with numbers.");
    }
    stringstream ss;
    if(m_functionName.empty())
        ss << "(null$" << label << ")\n";
    else 
        ss << "(" << m_functionName << "$" << label << ")\n";
    m_ofs << ss.str() << '\n';
}

void CodeWriter::writeGoto(const string& label) {
    // m_ofs << "// goto " << label << '\n';
    stringstream ss;
    if(m_functionName.empty())
        ss << "@null$" << label << "\n0;JMP\n";
    else 
        ss << "@" << m_functionName << "$" << label << "\n0;JMP\n";
    m_ofs << ss.str() << '\n';
}

void CodeWriter::writeIf(const string& label) {
    // m_ofs << "// if-goto " << label << '\n';
    stringstream ss;
    if(m_functionName.empty())
        ss << "@SP\nAM=M-1\nD=M\n@null$" << label << "\nD;JNE\n";
    else
        ss << "@SP\nAM=M-1\nD=M\n@" << m_functionName << "$" << label
           << "\nD;JNE\n";
    m_ofs << ss.str() << '\n';
}

void CodeWriter::writeCall(const string& functionName, int numArgs) {
    // m_ofs << "// call " << functionName << " " << numArgs << '\n';
    stringstream ss;
    ss << "@" << functionName << ".retAddr." << retAddrCount << "\n"
       << "D=A\n@SP\nM=M+1\nA=M-1\nM=D\n"
       << "@LCL\nD=M\n@SP\nM=M+1\nA=M-1\nM=D\n"
       << "@ARG\nD=M\n@SP\nM=M+1\nA=M-1\nM=D\n"
       << "@THIS\nD=M\n@SP\nM=M+1\nA=M-1\nM=D\n"
       << "@THAT\nD=M\n@SP\nM=M+1\nA=M-1\nM=D\n"
       << "@SP\nD=M\n@5\nD=D-A\n@" << numArgs << "\nD=D-A\n@ARG\nM=D\n"
       << "@SP\nD=M\n@LCL\nM=D\n"
       << "@" << functionName << "\n0;JMP\n"
       << "(" << functionName << ".retAddr." << retAddrCount << ")\n";
    ++retAddrCount;
    m_ofs << ss.str() << '\n';
}

void CodeWriter::writeReturn() {
    // m_ofs << "// return" << '\n';
    stringstream ss;
    ss << "@LCL\nD=M\n@R13\nM=D\n"
       << "@5\nA=D-A\nD=M\n@R14\nM=D\n"
       << "@SP\nAM=M-1\nD=M\n@ARG\nA=M\nM=D\n"
       << "@ARG\nD=M+1\n@SP\nM=D\n"
       << "@R13\nAM=M-1\nD=M\n@THAT\nM=D\n"
       << "@R13\nAM=M-1\nD=M\n@THIS\nM=D\n"
       << "@R13\nAM=M-1\nD=M\n@ARG\nM=D\n"
       << "@R13\nAM=M-1\nD=M\n@LCL\nM=D\n"
       << "@R14\nA=M\n0;JMP\n";
    m_ofs << ss.str() << '\n';
}

void CodeWriter::writeFunction(const string& functionName, int numArgs) {
    // m_ofs << "// function " << functionName << " " << numArgs << '\n';
    setFunctionName(functionName);
    stringstream ss;
    ss << "(" << functionName << ")\n";
    for(int i = 0; i < numArgs; ++i) {
        ss << cd_push("constant", 0) << '\n';
    }
    m_ofs << ss.str();
}

string CodeWriter::transName(const string &segment) {
    stringstream ss;
    if(segment == "local") ss << "LCL";
    else if(segment == "argument") ss << "ARG";
    else if(segment == "this") ss << "THIS";
    else if(segment == "that") ss << "THAT";

    return ss.str();
}

string CodeWriter::cd_add() {
    return "@SP\nAM=M-1\nD=M\nA=A-1\nM=D+M\n";
}

string CodeWriter::cd_sub() {
    return "@SP\nAM=M-1\nD=M\nA=A-1\nM=M-D\n";
}

string CodeWriter::cd_neg() {
    return "@SP\nA=M-1\nM=-M\n";
}

string CodeWriter::cd_eq() {
    stringstream ss;
    ss << "@SP\nAM=M-1\nD=M\nA=A-1\nD=M-D\nM=-1\n" 
       << "@eqCMPx" << cmpLabelCount
       << "\nD;JEQ\n@SP\nA=M-1\nM=0\n(eqCMPx" 
       << cmpLabelCount << ")\n";
    ++cmpLabelCount;
    return ss.str();
}

string CodeWriter::cd_gt() {
    stringstream ss;
    ss << "@SP\nAM=M-1\nD=M\nA=A-1\nD=M-D\nM=-1\n"
       << "@gtCMPx" << cmpLabelCount
       << "\nD;JGT\n@SP\nA=M-1\nM=0\n(gtCMPx"
       << cmpLabelCount << ")\n";
    ++cmpLabelCount;
    return ss.str();
}

string CodeWriter::cd_lt() {
    stringstream ss;
    ss << "@SP\nAM=M-1\nD=M\nA=A-1\nD=M-D\nM=-1\n"
       << "@ltCMPx" << cmpLabelCount
       << "\nD;JLT\n@SP\nA=M-1\nM=0\n(ltCMPx"
       << cmpLabelCount << ")\n";
    ++cmpLabelCount;
    return ss.str();
}

string CodeWriter::cd_and() {
    return "@SP\nAM=M-1\nD=M\nA=A-1\nM=D&M\n";
}

string CodeWriter::cd_or() {
    return "@SP\nAM=M-1\nD=M\nA=A-1\nM=D|M\n";
}

string CodeWriter::cd_not() {
    return "@SP\nA=M-1\nM=!M\n";
}

string CodeWriter::cd_push(const string& segment, uint16_t index) {
    stringstream ss;
    if(segment == "local" || segment == "argument" || segment == "this" || segment == "that") {
        ss << '@' << transName(segment) << "\nD=M\n@" << index
           << "\nA=D+A\nD=M\n@SP\nA=M\nM=D\n@SP\nM=M+1\n";
    } else if(segment == "constant") {
        ss << '@' << index
           << "\nD=A\n@SP\nA=M\nM=D\n@SP\nM=M+1\n";
    } else if(segment == "static") {
        ss << '@' << m_curParseFileName << '.' << index
           << "\nD=M\n@SP\nA=M\nM=D\n@SP\nM=M+1\n";
    } else if(segment == "temp") {
        ss << "@5\nD=A\n@" << index << "\nA=D+A\n"
           << "D=M\n@SP\nA=M\nM=D\n@SP\nM=M+1\n";
    } else if(segment == "pointer") {
        if(index == 0) ss << "@THIS";
        else ss << "@THAT";
        ss << "\nD=M\n@SP\nA=M\nM=D\n@SP\nM=M+1\n";
    }
    return ss.str();
}

string CodeWriter::cd_pop(const string& segment, uint16_t index) {
    stringstream ss;
    if(segment == "local" || segment == "argument" || segment == "this" || segment == "that") {
        ss << '@' << transName(segment) << "\nD=M\n@" << index
           << "\nD=D+A\n@R13\nM=D\n@SP\nAM=M-1\nD=M\n@R13\nA=M\nM=D\n";
    } else if(segment == "static") {
        ss << "@SP\nAM=M-1\nD=M\n@" << m_curParseFileName << '.' << index
           << "\nM=D\n";
    } else if(segment == "temp") {
        ss << "@5\nD=A\n@" << index << "\nD=D+A\n"
           << "@R13\nM=D\n@SP\nAM=M-1\nD=M\n@R13\nA=M\nM=D\n";
    } else if(segment == "pointer") {
        ss << "@SP\nAM=M-1\nD=M\n";
        if(index == 0) ss << "@THIS\n";
        else ss << "@THAT\n";
        ss << "M=D\n";
    }
    return ss.str();
}

🔨 codewriter.cpp also has several differences with the previous version:

• modify the name of variables to translate different commands
• implement the program flow and function calling commands

🎈 PS: reserve some comments for debugging.

main.cpp

#include <algorithm>
#include <exception>
#include <iostream>
#include <windows.h>

#include "parser.h"
#include "codewriter.h"

using namespace std;

bool parserPath(vector<string>& filenames, string path) {
    bool isDir = true;
    for(int i = path.length() - 1; i >= 0; --i) {
        if(path[i] == '\\') {
            break;
        } else if(path[i] == '.') {
            isDir = false;
        }
    }
    if(isDir) {
        path.append("\\*");
        WIN32_FIND_DATAA data;
        HANDLE hFind = FindFirstFileA(path.c_str(), &data);
        do {
            string t(data.cFileName);
            auto it = t.find(".vm");
            if(it != string::npos) {
                filenames.push_back(t.substr(0, it));
            }
        } while(FindNextFileA(hFind, &data));
    } else {
        auto it1 = path.find_last_of("\\");
        auto it2 = path.find_last_of(".");
        filenames.push_back(path.substr(it1 + 1, it2 - it1 - 1));
    }
    return isDir;
}

void doTranslate(CodeWriter& codewriter, const string& filepath) {
    Parser parser(filepath);
    while(parser.hasMoreCommands()) {
        parser.advance();
        CommandType pcmd = parser.commandType();
        if(pcmd == C_ARITHMETIC) {
            codewriter.writeArithmetic(parser.arg1());
        } else if(pcmd == C_PUSH || pcmd == C_POP) {
            codewriter.writePushPop(pcmd, parser.arg2(), parser.arg3());
        } else if(pcmd == C_LABEL) {
            codewriter.writeLabel(parser.arg2());
        } else if(pcmd == C_GOTO) {
            codewriter.writeGoto(parser.arg2());
        } else if(pcmd == C_IF) {
            codewriter.writeIf(parser.arg2());
        } else if(pcmd == C_FUNCTION) {
            codewriter.writeFunction(parser.arg2(), parser.arg3());
        } else if(pcmd == C_RETURN) {
            codewriter.writeReturn();
        } else if(pcmd == C_CALL) {
            codewriter.writeCall(parser.arg2(), parser.arg3());
        }
    }
}

int main(int argc, char** argv) {
    if(argc != 2) {
        cout << "Input error!\nSyntax: .\\VMTranslator.exe [filename or filepath]" << endl;
        return 0;
    }
    try {
        string path(argv[1]);
        vector<string> filenames;
        bool isDir = parserPath(filenames, path);
        if(filenames.size() == 0) {
            throw runtime_error("Input file or path are inappropriate");
        }
        if(!isDir) {
            string newfilepath = path.substr(0, path.find(".vm")) + ".asm";
            CodeWriter codewriter(newfilepath);
            codewriter.setCurParseFileName(filenames[0]);
            doTranslate(codewriter, path);
        } else {
            string::size_type pos = path.find_last_of("\\");
            string dirName = path.substr(pos + 1, path.length() - pos - 1);
            string newfilepath = path + "\\" + dirName + ".asm";
            CodeWriter codewriter(newfilepath);
            for(auto& s: filenames) {
                codewriter.setCurParseFileName(s);
                string filename = path + "\\" + s + ".vm";
                doTranslate(codewriter, filename);
            }
        } 
    } catch(exception& e) {
        cout << "Error: " << e.what() << endl;
    }
    return 0;
}

🔨 codewriter.cpp also has several differences with the previous version:

• compelted the processing for directory
• use doTranslate function to complete work
• provide easy exception support

Unit 8.10 Perspective

1. How useful is this VM language? Does it really make the writing of compilers easy?

• Of course. The virtual machine is an extremely powerful and practical idea.

2. What about efficiency? Why is C++ more efficient than Java?

• Obviously any two-stage translation model entails additional overhead, and results in more lines of less efficient machine code.

3. Why is Java more secure than C++, and what does this has to do with our VM architecture?

• For example, we can inspect the VM code and look for security breaches. It’s much easier to analyze the symantics of VM programs compared to machine language programs, which are far more elaborate and cryptic. Also, let’s not forget that the VM code must be handled by some virtual machine implementation. SO we can design this implementation in a way that creates what is sometimes called a sandbox effect. The idea is that during runtime, executing programs can never reach out of this sandbox and mess up with toys that they are not allowed to manipulate, like the host RAM. And that’s extremely important in a world in which software is routinely downloaded off the internet, to your computer or to your cell phone, without you even knowing this. So in that respect, the VM implementation that runs on your PC, or your cell phone can be viewed not only as an enabing technology, but also a security layer that protects your device from malicious code.

---