The Elements of Computing Systems

Author

gentam

Date
2017-10-20
Status
draft
Category

booknote

Tag

comp-sci

Updated

2017-12-09

FPGAでCPUとか作ってみたいと思ったが(Learn FPGA), 全体的な知識不足を感じたので,NANDゲートから始めてアプリケーションが動くところまでを 手を動かして体験できるというこの本をやってみることにした.


Title

コンピュータシステムの理論と実装

Authors

Noam Nisan; Shimon Schocken

Translator

斎藤 康毅

Published

2015-03-23

ISBN

978-4-78311-712-6

URL

http://nand2tetris.org

Read

NA

Contents

この本の中心は章ごとのプロジェクトにある.手を動かして実際に作ってみることで理解ができるように作られているので, まずは,Nand2Tetris Software Suite <http://nand2tetris.org/software.php> をダウンロードする.

以下に載せた自分の回答は一応全てテストに通ってはいるが,模範解答ではなかったり, もっと良い解があると思うので,あてにしない方が良いかも.ちなみに PARTS: より上の部分は用意されている.

1 ブール演算

NANDを基本要素として,他の全ての論理回路を実現していく.

Note

動作テストはGUIから行うよりも path/to/nand2tetris/tools を$PATHに追加してシェルから $ HardwareSimulator.sh File.tst とやる方が進めやすい.

デバッグもGUIで動作を確認するより,File.out の最終行と File.cmp を見比べた方が 分かりやすいと自分は思った.

1.1 基本論理ゲート

Not.hdl:

/**
 * Not gate:
 * out = not in
 */

CHIP Not {
    IN in;
    OUT out;

    PARTS:

    Nand(a=in, b=in, out=out);
}

And.hdl:

/**
 * And gate:
 * out = 1 if (a == 1 and b == 1)
 *       0 otherwise
 */

CHIP And {
    IN a, b;
    OUT out;

    PARTS:

    Nand(a=a, b=b, out=nandAb);
    Not(in=nandAb, out=out);
}

Or.hdl:

/**
 * Or gate:
 * out = 1 if (a == 1 or b == 1)
 *       0 otherwise
 */

CHIP Or {
    IN a, b;
    OUT out;

    PARTS:

    Not(in=a, out=notA);
    Not(in=b, out=notB);
    Nand(a=notA, b=notB, out=out);
}

Xor.hdl:

/**
 * Exclusive-or gate:
 * out = not (a == b)
 */

CHIP Xor {
    IN a, b;
    OUT out;

    PARTS:

    Or(a=a, b=b, out=orAb);
    Nand(a=a, b=b, out=nandAb);
    And(a=orAb, b=nandAb, out=out);

    /* Nand only version
    Nand(a=a, b=b, out=nandAb);
    Nand(a=a, b=nandAb, out=notAorB);
    Nand(a=nandAb, b=b, out=aOrNotB);
    Nand(a=notAorB, b=aOrNotB, out=out);
    */
}

Mux.hdl:

/**
 * Multiplexor:
 * out = a if sel == 0
 *       b otherwise
 */

CHIP Mux {
    IN a, b, sel;
    OUT out;

    PARTS:

    Not(in=sel, out=notSel);
    And(a=a, b=notSel, out=andA);
    And(a=sel, b=b, out=andB);
    Or(a=andA, b=andB, out=out);
}

DMux.hdl:

/**
 * Demultiplexor:
 * {a, b} = {in, 0} if sel == 0
 *          {0, in} if sel == 1
 */

CHIP DMux {
    IN in, sel;
    OUT a, b;

    PARTS:

    Not(in=sel, out=notSel);
    And(a=in, b=notSel, out=a);
    And(a=in, b=sel, out=b);
}

1.2 多ビットの基本ゲート

nビットに拡張するには,単純に1ビットのゲートをn個並べればいい.

Not16.hdl:

CHIP Not16 {
    IN in[16];
    OUT out[16];

    PARTS:

    Not(in=in[0], out=out[0]);
    Not(in=in[1], out=out[1]);
    Not(in=in[2], out=out[2]);
    Not(in=in[3], out=out[3]);
    Not(in=in[4], out=out[4]);
    Not(in=in[5], out=out[5]);
    Not(in=in[6], out=out[6]);
    Not(in=in[7], out=out[7]);
    Not(in=in[8], out=out[8]);
    Not(in=in[9], out=out[9]);
    Not(in=in[10], out=out[10]);
    Not(in=in[11], out=out[11]);
    Not(in=in[12], out=out[12]);
    Not(in=in[13], out=out[13]);
    Not(in=in[14], out=out[14]);
    Not(in=in[15], out=out[15]);
}

And16.hdl:

CHIP And16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:

    And(a=a[0], b=b[0], out=out[0]);
    And(a=a[1], b=b[1], out=out[1]);
    And(a=a[2], b=b[2], out=out[2]);
    And(a=a[3], b=b[3], out=out[3]);
    And(a=a[4], b=b[4], out=out[4]);
    And(a=a[5], b=b[5], out=out[5]);
    And(a=a[6], b=b[6], out=out[6]);
    And(a=a[7], b=b[7], out=out[7]);
    And(a=a[8], b=b[8], out=out[8]);
    And(a=a[9], b=b[9], out=out[9]);
    And(a=a[10], b=b[10], out=out[10]);
    And(a=a[11], b=b[11], out=out[11]);
    And(a=a[12], b=b[12], out=out[12]);
    And(a=a[13], b=b[13], out=out[13]);
    And(a=a[14], b=b[14], out=out[14]);
    And(a=a[15], b=b[15], out=out[15]);
}

Or16.hdl:

CHIP Or16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:

    Or(a=a[0], b=b[0], out=out[0]);
    Or(a=a[1], b=b[1], out=out[1]);
    Or(a=a[2], b=b[2], out=out[2]);
    Or(a=a[3], b=b[3], out=out[3]);
    Or(a=a[4], b=b[4], out=out[4]);
    Or(a=a[5], b=b[5], out=out[5]);
    Or(a=a[6], b=b[6], out=out[6]);
    Or(a=a[7], b=b[7], out=out[7]);
    Or(a=a[8], b=b[8], out=out[8]);
    Or(a=a[9], b=b[9], out=out[9]);
    Or(a=a[10], b=b[10], out=out[10]);
    Or(a=a[11], b=b[11], out=out[11]);
    Or(a=a[12], b=b[12], out=out[12]);
    Or(a=a[13], b=b[13], out=out[13]);
    Or(a=a[14], b=b[14], out=out[14]);
    Or(a=a[15], b=b[15], out=out[15]);
}

Mux16.hdl:

CHIP Mux16 {
    IN a[16], b[16], sel;
    OUT out[16];

    PARTS:

    Mux(a=a[0], b=b[0], sel=sel, out=out[0]);
    Mux(a=a[1], b=b[1], sel=sel, out=out[1]);
    Mux(a=a[2], b=b[2], sel=sel, out=out[2]);
    Mux(a=a[3], b=b[3], sel=sel, out=out[3]);
    Mux(a=a[4], b=b[4], sel=sel, out=out[4]);
    Mux(a=a[5], b=b[5], sel=sel, out=out[5]);
    Mux(a=a[6], b=b[6], sel=sel, out=out[6]);
    Mux(a=a[7], b=b[7], sel=sel, out=out[7]);
    Mux(a=a[8], b=b[8], sel=sel, out=out[8]);
    Mux(a=a[9], b=b[9], sel=sel, out=out[9]);
    Mux(a=a[10], b=b[10], sel=sel, out=out[10]);
    Mux(a=a[11], b=b[11], sel=sel, out=out[11]);
    Mux(a=a[12], b=b[12], sel=sel, out=out[12]);
    Mux(a=a[13], b=b[13], sel=sel, out=out[13]);
    Mux(a=a[14], b=b[14], sel=sel, out=out[14]);
    Mux(a=a[15], b=b[15], sel=sel, out=out[15]);
}

1.3 多入力の基本ゲート

Or8Way.hdl:

/**
 * 8-way Or:
 * out = (in[0] or in[1] or ... or in[7])
 */

CHIP Or8Way {
    IN in[8];
    OUT out;

    PARTS:

    Or(a=in[0], b=in[1], out=orA);
    Or(a=in[2], b=in[3], out=orB);
    Or(a=in[4], b=in[5], out=orC);
    Or(a=in[6], b=in[7], out=orD);

    Or(a=orA, b=orB, out=orAb);
    Or(a=orC, b=orD, out=orCd);

    Or(a=orAb, b=orCd, out=out);
}

Mux4Way16.hdl:

/**
 * 4-way 16-bit multiplexor:
 * out = a if sel == 00
 *       b if sel == 01
 *       c if sel == 10
 *       d if sel == 11
 */

CHIP Mux4Way16 {
    IN a[16], b[16], c[16], d[16], sel[2];
    OUT out[16];

    PARTS:

    Mux16(a=a, b=b, sel=sel[0], out=muxAb);
    Mux16(a=c, b=d, sel=sel[0], out=muxCd);
    Mux16(a=muxAb, b=muxCd, sel=sel[1], out=out);
}

Mux8Way16.hdl:

CHIP Mux8Way16 {
    IN a[16], b[16], c[16], d[16],
       e[16], f[16], g[16], h[16],
       sel[3];
    OUT out[16];

    PARTS:

    Mux4Way16(a=a, b=b, c=c, d=d, sel=sel[0..1], out=muxAbcd);
    Mux4Way16(a=e, b=f, c=g, d=h, sel=sel[0..1], out=muxEfgh);
    Mux16(a=muxAbcd, b=muxEfgh, sel=sel[2], out=out);
}

DMux4Way.hdl:

/**
 * 4-way demultiplexor:
 * {a, b, c, d} = {in, 0, 0, 0} if sel == 00
 *                {0, in, 0, 0} if sel == 01
 *                {0, 0, in, 0} if sel == 10
 *                {0, 0, 0, in} if sel == 11
 */

CHIP DMux4Way {
    IN in, sel[2];
    OUT a, b, c, d;

    PARTS:

    DMux(in=in, sel=sel[1], a=dmuxAb, b=dmuxCd);
    DMux(in=dmuxAb, sel=sel[0], a=a, b=b);
    DMux(in=dmuxCd, sel=sel[0], a=c, b=d);
}

DMux8Way.hdl:

CHIP DMux8Way {
    IN in, sel[3];
    OUT a, b, c, d, e, f, g, h;

    PARTS:

    DMux(in=in, sel=sel[2], a=dmAbcd, b=dmEfgh);
    DMux4Way(in=dmAbcd, sel=sel[0..1], a=a, b=b, c=c, d=d);
    DMux4Way(in=dmEfgh, sel=sel[0..1], a=e, b=f, c=g, d=h);
}

2 ブール算術

ここまでで作った論理回路を応用して,算術演算をする.必要となる知識は二進数の加算 における桁上がりと,負の数を二の補数で表現する仕組み.

2.1 加算器 (Adder)

半加算器

HalfAdder.hdl:

/**
 * Computes the sum of two bits.
 */

CHIP HalfAdder {
    IN a, b;    // 1-bit inputs
    OUT sum,    // Right bit of a + b
        carry;  // Left bit of a + b

    PARTS:

    Xor(a=a, b=b, out=sum);
    And(a=a, b=b, out=carry);
}

全加算器

FullAdder.hdl:

/**
 * Computes the sum of three bits.
 */

CHIP FullAdder {
    IN a, b, c;  // 1-bit inputs
    OUT sum,     // Right bit of a + b + c
        carry;   // Left bit of a + b + c

    PARTS:

     /* 1. Using HalfAdder */
    HalfAdder(a=a, b=b, sum=sum1, carry=carry1);
    HalfAdder(a=sum1, b=c, sum=sum, carry=carry2);
    Or(a=carry1, b=carry2, out=carry);

    /* 2. Direct
    Xor(a=a, b=b, out=sum1);
    Xor(a=sum1, b=c, out=sum);
    And(a=a, b=b, out=carry1);
    And(a=sum1, b=c, out=carry2);
    Or(a=carry1, b=carry2, out=carry);
    */
}

16bitの加算器

Add16.hdl:

/**
 * Adds two 16-bit values.
 * The most significant carry bit is ignored.
 */

CHIP Add16 {
    IN a[16], b[16];
    OUT out[16];

    PARTS:

    HalfAdder(a=a[0], b=b[0], sum=out[0], carry=c1);
    FullAdder(a=a[1], b=b[1], c=c1, sum=out[1], carry=c2);
    FullAdder(a=a[2], b=b[2], c=c2, sum=out[2], carry=c3);
    FullAdder(a=a[3], b=b[3], c=c3, sum=out[3], carry=c4);
    FullAdder(a=a[4], b=b[4], c=c4, sum=out[4], carry=c5);
    FullAdder(a=a[5], b=b[5], c=c5, sum=out[5], carry=c6);
    FullAdder(a=a[6], b=b[6], c=c6, sum=out[6], carry=c7);
    FullAdder(a=a[7], b=b[7], c=c7, sum=out[7], carry=c8);
    FullAdder(a=a[8], b=b[8], c=c8, sum=out[8], carry=c9);
    FullAdder(a=a[9], b=b[9], c=c9, sum=out[9], carry=c10);
    FullAdder(a=a[10], b=b[10], c=c10, sum=out[10], carry=c11);
    FullAdder(a=a[11], b=b[11], c=c11, sum=out[11], carry=c12);
    FullAdder(a=a[12], b=b[12], c=c12, sum=out[12], carry=c13);
    FullAdder(a=a[13], b=b[13], c=c13, sum=out[13], carry=c14);
    FullAdder(a=a[14], b=b[14], c=c14, sum=out[14], carry=c15);
    FullAdder(a=a[15], b=b[15], c=c15, sum=out[15]);
}

インクリメンタ

Inc16.hdl:

/**
 * 16-bit incrementer:
 * out = in + 1 (arithmetic addition)
 */

CHIP Inc16 {
    IN in[16];
    OUT out[16];

    PARTS:

    Add16(a=in, b[0]=true, out=out);
}

2.2 ALU (算術論理演算器)

ALU.hdl:

/**
 * The ALU (Arithmetic Logic Unit).
 * Computes one of the following functions:
 * x+y, x-y, y-x, 0, 1, -1, x, y, -x, -y, !x, !y,
 * x+1, y+1, x-1, y-1, x&y, x|y on two 16-bit inputs,
 * according to 6 input bits denoted zx,nx,zy,ny,f,no.
 * In addition, the ALU computes two 1-bit outputs:
 * if the ALU output == 0, zr is set to 1; otherwise zr is set to 0;
 * if the ALU output < 0, ng is set to 1; otherwise ng is set to 0.
 */

// Implementation: the ALU logic manipulates the x and y inputs
// and operates on the resulting values, as follows:
// if (zx == 1) set x = 0        // 16-bit constant
// if (nx == 1) set x = !x       // bitwise not
// if (zy == 1) set y = 0        // 16-bit constant
// if (ny == 1) set y = !y       // bitwise not
// if (f == 1)  set out = x + y  // integer 2's complement addition
// if (f == 0)  set out = x & y  // bitwise and
// if (no == 1) set out = !out   // bitwise not
// if (out == 0) set zr = 1
// if (out < 0) set ng = 1

CHIP ALU {
    IN
        x[16], y[16],  // 16-bit inputs
        zx, // zero the x input?
        nx, // negate the x input?
        zy, // zero the y input?
        ny, // negate the y input?
        f,  // compute out = x + y (if 1) or x & y (if 0)
        no; // negate the out output?

    OUT
        out[16], // 16-bit output
        zr, // 1 if (out == 0), 0 otherwise
        ng; // 1 if (out < 0),  0 otherwise

    PARTS:

    // for zx, zy
    Mux16(a=x, b[0..15]=false, sel=zx, out=muxZx);
    Mux16(a=y, b[0..15]=false, sel=zy, out=muxZy);

    // for nx, ny
    Not16(in=muxZx, out=notX);
    Not16(in=muxZy, out=notY);
    Mux16(a=muxZx, b=notX, sel=nx, out=muxNx);
    Mux16(a=muxZy, b=notY, sel=ny, out=muxNy);

    // for f
    Add16(a=muxNx, b=muxNy, out=addXy);
    And16(a=muxNx, b=muxNy, out=andXy);
    Mux16(a=andXy, b=addXy, sel=f, out=muxF);

    // for no
    Not16(in=muxF, out=notOut);
    Mux16(a=muxF, b=notOut, sel=no, out=out,
          out[0..7]=out1, out[8..15]=out2, out[15]=ng);

    // for zr
    Or8Way(in=out1, out=orZr1);
    Or8Way(in=out2, out=orZr2);
    Or(a=orZr1, b=orZr2, out=selZr);
    Mux(a=true, b=false, sel=selZr, out=zr);
}

3 順序回路

ここまではNAND回路を基本素子として,全ての 組み合わせ回路 (combinational circuit) を作ってきた.ここからはD型フリップフロップ回路(DFF)をプリミティブな構成要素として 順序回路 (sequential circuit) を作っていく.

組み合わせ回路は同じ入力に対して必ず同じ出力を返したが,ここには時間の概念がなく, 状態を保つことができない. 時間が経過しても状態を保つことができる記憶素子は順序回路から作ることができる. コンピュータにおける時間の経過は クロック によって表現される. このクロックよって全ての回路が同期して動く.

3.1 レジスタ

1ビットレジスタは,保存された1ビットの値を返し続ける. load 信号によってその内容を書き換えられる.

Bit.hdl:

/**
 * 1-bit register:
 * If load[t] == 1 then out[t+1] = in[t]
 *                 else out does not change (out[t+1] = out[t])
 */

CHIP Bit {
    IN in, load;
    OUT out;

    PARTS:

    Mux(a=outfb, b=in, sel=load, out=mout);
    DFF(in=mout, out=outfb, out=out);
}

Register.hdl:

/**
 * 16-bit register:
 * If load[t] == 1 then out[t+1] = in[t]
 * else out does not change
 */

CHIP Register {
    IN in[16], load;
    OUT out[16];

    PARTS:

    Bit(in=in[0], load=load, out=out[0]);
    Bit(in=in[1], load=load, out=out[1]);
    Bit(in=in[2], load=load, out=out[2]);
    Bit(in=in[3], load=load, out=out[3]);
    Bit(in=in[4], load=load, out=out[4]);
    Bit(in=in[5], load=load, out=out[5]);
    Bit(in=in[6], load=load, out=out[6]);
    Bit(in=in[7], load=load, out=out[7]);
    Bit(in=in[8], load=load, out=out[8]);
    Bit(in=in[9], load=load, out=out[9]);
    Bit(in=in[10], load=load, out=out[10]);
    Bit(in=in[11], load=load, out=out[11]);
    Bit(in=in[12], load=load, out=out[12]);
    Bit(in=in[13], load=load, out=out[13]);
    Bit(in=in[14], load=load, out=out[14]);
    Bit(in=in[15], load=load, out=out[15]);
}

3.2 メモリ

ここでは,メモリをレジスタ(=DFFの配列)の集まりとして作っているが, 実際のメモリがフリップフロップから構築されることはほとんどない.

RAM8.hdl:

/**
 * Memory of 8 registers, each 16 bit-wide. Out holds the value
 * stored at the memory location specified by address. If load==1, then
 * the in value is loaded into the memory location specified by address
 * (the loaded value will be emitted to out from the next time step onward).
 */

CHIP RAM8 {
    IN in[16], load, address[3];
    OUT out[16];

    PARTS:

    DMux8Way(in=load, sel=address,
        a=load0, b=load1, c=load2, d=load3,
        e=load4, f=load5, g=load6, h=load7);

    Register(in=in, load=load0, out=out0);
    Register(in=in, load=load1, out=out1);
    Register(in=in, load=load2, out=out2);
    Register(in=in, load=load3, out=out3);
    Register(in=in, load=load4, out=out4);
    Register(in=in, load=load5, out=out5);
    Register(in=in, load=load6, out=out6);
    Register(in=in, load=load7, out=out7);

    Mux8Way16(a=out0, b=out1, c=out2, d=out3,
              e=out4, f=out5, g=out6, h=out7,
              sel=address, out=out);
}

RAM64.hdl:

CHIP RAM64 {
    IN in[16], load, address[6];
    OUT out[16];

    PARTS:

    DMux8Way(in=load, sel=address[3..5],
        a=load0, b=load1, c=load2, d=load3,
        e=load4, f=load5, g=load6, h=load7);

    RAM8(in=in, load=load0, address=address[0..2], out=out0);
    RAM8(in=in, load=load1, address=address[0..2], out=out1);
    RAM8(in=in, load=load2, address=address[0..2], out=out2);
    RAM8(in=in, load=load3, address=address[0..2], out=out3);
    RAM8(in=in, load=load4, address=address[0..2], out=out4);
    RAM8(in=in, load=load5, address=address[0..2], out=out5);
    RAM8(in=in, load=load6, address=address[0..2], out=out6);
    RAM8(in=in, load=load7, address=address[0..2], out=out7);

    Mux8Way16(a=out0, b=out1, c=out2, d=out3,
              e=out4, f=out5, g=out6, h=out7,
              sel=address[3..5], out=out);

}

RAM512.hdl:

CHIP RAM512 {
    IN in[16], load, address[9];
    OUT out[16];

    PARTS:

    DMux8Way(in=load, sel=address[6..8],
             a=load0, b=load1, c=load2, d=load3,
             e=load4, f=load5, g=load6, h=load7);

    RAM64(in=in, load=load0, address=address[0..5], out=out0);
    RAM64(in=in, load=load1, address=address[0..5], out=out1);
    RAM64(in=in, load=load2, address=address[0..5], out=out2);
    RAM64(in=in, load=load3, address=address[0..5], out=out3);
    RAM64(in=in, load=load4, address=address[0..5], out=out4);
    RAM64(in=in, load=load5, address=address[0..5], out=out5);
    RAM64(in=in, load=load6, address=address[0..5], out=out6);
    RAM64(in=in, load=load7, address=address[0..5], out=out7);

    Mux8Way16(a=out0, b=out1, c=out2, d=out3,
              e=out4, f=out5, g=out6, h=out7,
              sel=address[6..8], out=out);

}

RAM4K.hdl:

CHIP RAM4K {
    IN in[16], load, address[12];
    OUT out[16];

    PARTS:

    DMux8Way(in=load, sel=address[9..11],
             a=load0, b=load1, c=load2, d=load3,
             e=load4, f=load5, g=load6, h=load7);

    RAM512(in=in, load=load0, address=address[0..8], out=out0);
    RAM512(in=in, load=load1, address=address[0..8], out=out1);
    RAM512(in=in, load=load2, address=address[0..8], out=out2);
    RAM512(in=in, load=load3, address=address[0..8], out=out3);
    RAM512(in=in, load=load4, address=address[0..8], out=out4);
    RAM512(in=in, load=load5, address=address[0..8], out=out5);
    RAM512(in=in, load=load6, address=address[0..8], out=out6);
    RAM512(in=in, load=load7, address=address[0..8], out=out7);

    Mux8Way16(a=out0, b=out1, c=out2, d=out3,
              e=out4, f=out5, g=out6, h=out7,
              sel=address[9..11], out=out);

}

RAM16K.hdl:

CHIP RAM16K {
    IN in[16], load, address[14];
    OUT out[16];

    PARTS:

    DMux4Way(in=load, sel=address[12..13],
             a=load0, b=load1, c=load2, d=load3);

    RAM4K(in=in, load=load0, address=address[0..11], out=out0);
    RAM4K(in=in, load=load1, address=address[0..11], out=out1);
    RAM4K(in=in, load=load2, address=address[0..11], out=out2);
    RAM4K(in=in, load=load3, address=address[0..11], out=out3);

    Mux4Way16(a=out0, b=out1, c=out2, d=out3,
              sel=address[12..13], out=out);

}

3.3 カウンタ

なんかもっとシンプルに実装できそうな気もする.

PC.hdl:

/**
 * A 16-bit counter with load and reset control bits.
 * if      (reset[t] == 1) out[t+1] = 0
 * else if (load[t] == 1)  out[t+1] = in[t]
 * else if (inc[t] == 1)   out[t+1] = out[t] + 1  (integer addition)
 * else                    out[t+1] = out[t]
 */

CHIP PC {
    IN in[16], load, inc, reset;
    OUT out[16];

    PARTS:

    // handle control bits
    Or(a=reset, b=load, out=or1);
    Not(in=load, out=notLoad);
    And(a=inc, b=notLoad, out=andLi);
    Or(a=reset, b=andLi, out=or0);

    Inc16(in=feedback, out=plus1);

    Mux4Way16(a=feedback, b=plus1, c=in, d[0..15]=false,
              sel[1]=or1, sel[0]=or0, out=muxRes);

    Register(in=muxRes, load=true, out=out, out=feedback);
}

4 機械語

コンピュータ全体において最も重要なインターフェイスは何か? それは「機械語」 である.機械語においてハードウェアとソフトウェアが交わり,機械語において プログラマの抽象的思考がシリコン上で実行される物理的操作に変換される.

16bitコンピュータで用いられる命令,つまり機械語は16個の0と1の羅列になる. これを直接読むのは人間には辛いため,ニーモニック (mnemonic)という 1対1に対応した記号や英単語を使っても表す:

1010001100011001 -> ADD, R3, R1, R9

この記号による抽象化を進めて,プログラムを書きやすくしたのがアセンブリ言語.

メモリアクセスとアドレッシングの種類:

direct addressing

メモリのアドレスを指定する最も一般的な方法. アドレスを数値で指定するか,シンボルで参照する.

e.g. LOAD R1, 67 // R1 ← Memory[67])

immediate addressing

定数を読み込む.命令コード中の値をそのままレジスタに読み込む.

e.g. LOADI R1, 67 // R1 ← 67

indirect addressing

ポインタを扱うために用いられる.配列の要素にアクセスするために ベースアドレスにインデックスを加えるような処理.

e.g. x = foo[j] の変換は以下のようになる:

ADD R1, foo, j  // R1 ← foo+j
LOAD R2, R1     // R2 ← Memory[R1]
STR R2, x       // x ← R2

分岐命令

プログラムを頭から順番に実行できない場合がある.例えば,条件分岐や反復,関数呼び出し がそれに当たる.このような処理は,命令アドレスを指定してジャンプするという 分岐命令によって実現される.

4.1 Hack機械語の仕様

Hack機械語には,A命令(Address instruction)とC命令(Compute instruction)がある.

4.1.1 A命令

A命令は,Aレジスタに15ビットの値を設定する:

@value

0 v v v   v v v v   v v v v   v v v v
  +---------------------------------+
  | value (15bit)                   |

AレジスタはJUMP時の命令アドレスとしても,データの保存としても 両方使えるレジスタである. さらに,メモリアクセスをする際のアドレスにもAレジスタの値が使われる. そのため,メモリの値を使った計算は常にアドレスの設定のA命令とと実際の計算の C命令の2つがセットになる.

このようにAレジスタはJUMP命令とメモリアクセスそれぞれでアドレス指定に利用されるために, 1つの命令の中で同時に行うことはできない.

例えば M=D;JEQ という命令はAレジスタの値がメモリアクセスにもジャンプ先にも 参照されてしまうため衝突している.

4.1.2 C命令

C命令は,計算内容やその保存先,また次の命令など処理の中心を担う:

dest=comp;jump

1 1 1   a c1 c2 c3 c4 c5 c6   d1 d2 d3   j1 j2 j3
        +-----------------+   +------+   +------+
        | comp (1 + 6bit) |   | dest |   | jump |

dest=comp;jump というフォーマットの中で,dest=;jump は, 要らない場合省略されるが,comp 部は必ず必要.

4.1.2.1 C命令のcomp領域

一番左と一番右の列が,a=0とa=1のときに対応するmnemonic.

a=0

c1

c2

c3

c4

c5

c6

a=1

0

1

0

1

0

1

0

1

1

1

1

1

1

1

-1

1

1

1

0

1

0

D

0

0

1

1

0

0

A

1

1

0

0

0

0

M

!D

0

0

1

1

0

1

!A

1

1

0

0

0

1

!M

-D

0

0

1

1

1

1

-A

1

1

0

0

1

1

-M

D+1

0

1

1

1

1

1

A+1

1

1

0

1

1

1

M+1

D-1

0

0

1

1

1

0

A-1

1

1

0

0

1

0

M-1

D+A

0

0

0

0

1

0

D+M

D-A

0

1

0

0

1

1

D-M

A-D

0

0

0

1

1

1

M-D

D&A

0

0

0

0

0

0

D&M

D|A

0

1

0

1

0

1

D|M

a の値と,c1..c6 の6bitで実際に命令を指定する.この6bit が2章で実装した ALU (算術論理演算器) の6本のセレクタによる命令セットと対応している: (c1→zx, c2→nx, c3→zy, c4→ny, c5→f, c6→no)

また,a=0 の際にはAレジスタとDレジスタ演算.a=1の場合は,メモリとDレジスタの 演算という具合に設計されている.

4.1.2.2 C命令のdest領域

d1

d2

d3

Mnemonic

0

0

0

null

0

0

1

M

0

1

0

D

0

1

1

MD

1

0

0

A

1

0

1

AM

1

1

0

AD

1

1

1

AMD

d1→A,d2→D,d3→M と対応している.

4.1.2.3 C命令のjump領域

j1

j2

j3

Mnemonic

0

0

0

null

0

0

1

JGT (>0)

0

1

0

JEQ (=0)

0

1

1

JGE (>=0)

1

0

0

JLT (< 0)

1

0

1

JNE (!=0)

1

1

0

JLE (<=0)

1

1

1

JMP

j1→out<0,j2→out=0,j3→out>0 と対応している.


Memory[7] の値を1インクリメントして,その結果をDレジスタに保存する例:

0000 0000 0000 0111    // @7
1111 1101 1101 1000    // MD=M+1
   a cccc ccdd djjj
   +---------------
   | a    = 1
   | comp = 110111 -> M+1
   | dest = 011    -> MD (Memory[A]とDレジスタ)
   | jump = 000    -> null (No jump)

4.2 乗算プログラム (Mult.asm)

掛け算は,n回の足し算と考えられる.

Mult.asm:

// Multiplies R0 and R1 and stores the result in R2.
// (R0, R1, R2 refer to RAM[0], RAM[1], and RAM[2], respectively.)

@2
M=0 // initialize R2=0
(Loop)
    @1
    MD=M-1 // R1 as a loop counter
    @End
    D;JLT // if R1 < 0 then goto End
    @0
    D=M
    @2
    M=D+M // add R0 to R2
    @Loop
    0;JMP // goto Loop
(End)
    @End
    0;JMP

アセンブラをかけると以下のような機械語が出力される. $ Assembler.sh && cat Mult.hack:

0000000000000010
1110101010001000
0000000000000001
1111110010011000
0000000000001100
1110001100000100
0000000000000000
1111110000010000
0000000000000010
1111000010001000
0000000000000010
1110101010000111
0000000000001100
1110101010000111

これを上の命令のフィールドに沿って見やすく分割して行番号を付け, テーブルに従って逆にニーモニックに戻してみる:

 LN  Binary                    Mnemonic
---  ------------------------  --------
  0  0  000000000000010        @2
  1  111  0 101010  001 000    M=0
  2  0  000000000000001        @1
  3  111  1 110010  011 000    MD=M-1
  4  0  000000000001100        @12
  5  111  0 001100  000 100    D;JLT
  6  0  000000000000000        @0
  7  111  1 110000  010 000    D=M
  8  0  000000000000010        @2
  9  111  1 000010  001 000    M=D+M
 10  0  000000000000010        @2
 11  111  0 101010  000 111    0;JMP
 12  0  000000000001100        @12
 13  111  0 101010  000 111    0;JMP

すると上のMult.asmが完全に復元でき,またJump命令のラベルが行番号,すなわち メモリ上に格納されたプログラムのワードアドレスに置き換わっていることが確認できる.

4.3 入出力操作プログラム (Fill.asm)

入出力は メモリマップ を通じて,スクリーンとキーボードを扱うことができる.

スクリーンは,メモリ上の 0x4000 (16384) から8Kのメモリマップで表される. これは,512 x 256 ピクセルの白黒スクリーンで,0が白,1が黒に対応する. (1ワードが16bitなので,512*256/16=8192)

キーボードは 0x6000 (24576) の1ワードのメモリマップを介して接続する.

これを利用して,キーボードが押されたときだけ画面を黒く塗りつぶし, 押されていないときは白くするというプログラムが以下.

最後にfillした色を保持して変化がない限りはFillループに飛ばないようにするつもりだったけど 毎回描画しても十分レスポンシブだったので,なるべくシンプルな状態に止めておく.

Fill.asm:

// Runs an infinite loop that listens to the keyboard input.
// When a key is pressed (any key), the program blackens the screen,
// i.e. writes "black" in every pixel;
// the screen should remain fully black as long as the key is pressed.
// When no key is pressed, the program clears the screen, i.e. writes
// "white" in every pixel;
// the screen should remain fully clear as long as no key is pressed.

@KBD
D=A-1 // = SCREEN+8K-1 = 24575 (the end of screen memory map)
@R1
M=D

(Main)
    @SCREEN
    D=A
    @R0
    M=D-1 // initialize R0 = SCREEN-1

    @KBD
    D=M
    @FillWhite
    D;JEQ // no key was pressed
    @FillBlack
    0;JMP

(FillWhite)
    @R0 // R0 = Current address of SCREEN
    MD=M+1
    A=D
    M=0 // fill 0

    @R1
    D=D-M
    @Main
    D;JEQ // reached end

    @FillWhite
    0;JMP

(FillBlack)
    @R0
    MD=M+1
    A=D
    M=0
    M=!M // fill 1

    @R1
    D=D-M
    @Main
    D;JEQ

    @FillBlack
    0;JMP

5 コンピュータアーキテクチャ

この章がハードウェア編のまとめ.ここまでNANDとDFFから作ってきた回路を組み合わせる ことで,コンピュータを作る.

5.1 メモリ

まずはメモリから.これは単純に3章で作ったRAM16Kと,スクリーンとキーボード用の メモリマップ部分を,連続したアドレス空間のインターフェイスとして提供するもの.

最初は引き算とかXORでアドレスの範囲を区別しようとしていたけど, メモリの境界アドレスが,0x400と0x600になっていることの親切さに途中で気がついた.

ちなみにMemoryのテストには途中でキーボードを押す部分が入るので,GUIから 入力しないといけなかった.(たぶん)

Memory.hdl:

/**
 * The complete address space of the Hack computer's memory,
 * including RAM and memory-mapped I/O.
 * The chip facilitates read and write operations, as follows:
 *     Read:  out(t) = Memory[address(t)](t)
 *     Write: if load(t-1) then Memory[address(t-1)](t) = in(t-1)
 * In words: the chip always outputs the value stored at the memory
 * location specified by address. If load==1, the in value is loaded
 * into the memory location specified by address. This value becomes
 * available through the out output from the next time step onward.
 * Address space rules:
 * Only the upper 16K+8K+1 words of the Memory chip are used.
 * Access to address>0x6000 is invalid. Access to any address in
 * the range 0x4000-0x5FFF results in accessing the screen memory
 * map. Access to address 0x6000 results in accessing the keyboard
 * memory map. The behavior in these addresses is described in the
 * Screen and Keyboard chip specifications given in the book.
 */

CHIP Memory {
    IN in[16], load, address[15];
    OUT out[16];

    PARTS:

    DMux(in=load, sel=address[14], a=ramLoad, b=scrLoad);

    RAM16K(in=in, load=ramLoad, address=address[0..13], out=ramOut);
    Screen(in=in, load=scrLoad, address=address[0..12], out=scrOut);
    Keyboard(out=kbdOut);

    Mux4Way16(a=ramOut, b=ramOut, c=scrOut, d=kbdOut,
              sel[1]=address[14], sel[0]=address[13], out=out);
}

5.2 CPU

次が遂にCPU.

これくらい複雑になると,自分はHDLコードを書いて想像するのが難しかったので, 紙に書いて設計してから,それをコードに落とすという風に進めた.(というか これまでもそうしていたことの方が多かった) とりあえず紙に回路を書こうとすれば,どうすればいいか分かっていない箇所が 明らかになりやすい. 最初は計画性がないので配線がぐちゃぐちゃになったが,2, 3回書き直しながら, 細部を詰めて行くと,コードを睨めているのと比べて一気に進んだ.

一度出来上がってから見るととても単純に見えるのに,思いつくまでには驚くほど 時間がかかってしまうので,まだ回路設計の考え方には慣れていないなと感じる.

CPU.hdl:

/**
 * The Hack CPU (Central Processing unit), consisting of an ALU,
 * two registers named A and D, and a program counter named PC.
 * The CPU is designed to fetch and execute instructions written in
 * the Hack machine language. In particular, functions as follows:
 * Executes the inputted instruction according to the Hack machine
 * language specification. The D and A in the language specification
 * refer to CPU-resident registers, while M refers to the external
 * memory location addressed by A, i.e. to Memory[A]. The inM input
 * holds the value of this location. If the current instruction needs
 * to write a value to M, the value is placed in outM, the address
 * of the target location is placed in the addressM output, and the
 * writeM control bit is asserted. (When writeM==0, any value may
 * appear in outM). The outM and writeM outputs are combinational:
 * they are affected instantaneously by the execution of the current
 * instruction. The addressM and pc outputs are clocked: although they
 * are affected by the execution of the current instruction, they commit
 * to their new values only in the next time step. If reset==1 then the
 * CPU jumps to address 0 (i.e. pc is set to 0 in next time step) rather
 * than to the address resulting from executing the current instruction.
 */

CHIP CPU {

    IN  inM[16],         // M value input  (M = contents of RAM[A])
        instruction[16], // Instruction for execution
        reset;           // Signals whether to re-start the current
                         // program (reset==1) or continue executing
                         // the current program (reset==0).

    OUT outM[16],        // M value output
        writeM,          // Write to M?
        addressM[15],    // Address in data memory (of M)
        pc[15];          // address of next instruction

    PARTS:
    // Put your code here:

    // if it's an address instruction then set dst and jump bits to 0
    Mux16(a[0..5]=false, b[0..5]=instruction[0..5], sel=instruction[15],
          out[5]=md1, out[4]=md2, out[3]=writeM,
          out[2]=mj1, out[1]=mj2, out[0]=mj3);

    // handle A and D registers
    Mux16(a=instruction, b=outAlu, sel=instruction[15], out=mInstAlu);
    Mux(a=true, b=md1, sel=instruction[15], out=m1md1);
    ARegister(in=mInstAlu, load=m1md1, out=regA, out[0..14]=addressM);
    DRegister(in=outAlu, load=md2, out=regD);
    Mux16(a=regA, b=inM, sel=instruction[12], out=mRegAM);

    // ALU
    ALU(x=regD, y=mRegAM,
        zx=instruction[11], nx=instruction[10], zy=instruction[9],
        ny=instruction[8], f=instruction[7], no=instruction[6],
        out=outM, out=outAlu, zr=zr, ng=ng);

    // handle jump
    Not(in=ng, out=notNg);
    Not(in=zr, out=notZr);
    Or(a=ng, b=zr, out=ngOrZr);
    And(a=notNg, b=notZr, out=notNgAndNotZr);
    Mux8Way16(a[0]=false, b[0]=notNgAndNotZr, c[0]=zr, d[0]=notNg,
              e[0]=ng, f[0]=notZr, g[0]=ngOrZr, h[0]=true,
              sel[2]=mj1, sel[1]=mj2, sel[0]=mj3,
              out[0]=outJmp);

    // program counter
    Not(in=outJmp, out=notOutJmp);
    PC(in=regA, load=outJmp, inc=notOutJmp, reset=reset, out[0..14]=pc);
}

5.3 コンピュータ

最後に,プログラム用のROMとCPUとRAMを繋げてコンピュータの完成.

Computer.hdl:

/**
 * The HACK computer, including CPU, ROM and RAM.
 * When reset is 0, the program stored in the computer's ROM executes.
 * When reset is 1, the execution of the program restarts.
 * Thus, to start a program's execution, reset must be pushed "up" (1)
 * and "down" (0). From this point onward the user is at the mercy of
 * the software. In particular, depending on the program's code, the
 * screen may show some output and the user may be able to interact
 * with the computer via the keyboard.
 */

CHIP Computer {

    IN reset;

    PARTS:

    ROM32K(address=pc, out=outInstruction);
    CPU(inM=outMemory, instruction=outInstruction, reset=reset,
        outM=outCpu, writeM=outLoad, addressM=outAddress, pc=pc);
    Memory(in=outCpu, load=outLoad, address=outAddress, out=outMemory);
}

パズル的でとても楽しかったが,同時に結構疲れた.

そもそもこの本を始めたのは,FPGAで遊ぶために必要な,Verilogを学ぶためにちょっと前提知識をつけよう. という動機だったので,6章以降のソフトウェア編は今後の楽しみにとっておき,一旦 Learn FPGA へ戻る.(2017-10-30)

6 アセンブラ

6章以降はこの本のソフトウェア編になる.ハードウェア編は全てHDLで実装してきたが, ソフトウェア編は好きな言語で書くことができる.

まずこの章ではアセンブラを書く.アセンブリ言語をバイナリファイルへ変換するのは 基本的にはニーモニックに対応するビット列を出力するだけでできる. 唯一注意すべきは,ユーザが定義したラベルやシンボルをシンボルテーブルを使って, 対応するアドレスと結びつける必要があるという点.

パーサなどのテキスト処理を書くのにはOCamlが向いているようなイメージがあるが, 触ったことがなかったのでこの機会に使ってみる. (Learn OCaml) ...と一度考えたが, メモを作りながら 勉強すると思ったより時間がかかりそうだから途中でErlangで書いてしまった.

手続き的にループで書いたら2周でできるところを,リストへの関数適応のイメージで 書くと,全体を何周もするかなり非効率なものになってしまったが,やっぱり パターンマッチでかけるのは気持ち良い.

$ escript assembler.erl file.asm

#!/usr/local/bin/escript

-module(assembler).
-export([main/1]).
%% -compile(export_all).

main([IFileName]) ->
    case check_filename(IFileName) of
        {ok, OFileName} ->
            {ok, Binary} = file:read_file(IFileName),
            Asm = binary_to_list(Binary),
            Result = assemble(Asm),
            Ascii = bin_format_list(Result),
            ok = file:write_file(OFileName, Ascii);
        error ->
            usage()
    end;
main([]) ->
    usage().

usage() ->
    io:format("usage: ./assembler file.asm\n"),
    halt(1).

check_filename(FileName) ->
    [Name|Ext] = string:split(FileName, ".", trailing),
    case Ext of
        ["asm"] ->
            {ok, Name ++ ".hack"};
        _ ->
            error
    end.

%% print machine code in ascii text
bin_format_list(Ls) ->
    lists:map(fun (L) -> [bin_format(L), "\n"] end, Ls).

bin_format(L) ->
    case length(L) of
        2 ->
            ["0",
            string:pad(integer_to_list(lists:nth(2, L), 2), 15, leading, $0)];
        _ ->
            ["111",
            string:pad(integer_to_list(lists:nth(2, L), 2), 7, leading, $0),
            string:pad(integer_to_list(lists:nth(3, L), 2), 3, leading, $0),
            string:pad(integer_to_list(lists:nth(4, L), 2), 3, leading, $0)]
    end.

%%------------------------------------------------------------
%% Core
%%------------------------------------------------------------

assemble(Asm) ->
    Parsed = parse(Asm),
    %% io:format("Parsed:~p~n", [Parsed]),
    {LabelFree, SymbolTable} = label_to_addr(Parsed, symbol_init()),
    SymbolFree = name_rez(LabelFree, SymbolTable),
    code_gen(SymbolFree).

%%------------------------------------------------------------
%% Parse raw text
%%------------------------------------------------------------

parse(Asm) ->
    Lined = string:split(Asm, "\n", all),
    Cleaned = clean(Lined),
    lists:map(fun(L) -> command_type(L) end, Cleaned).

clean(Line) ->
    lists:filtermap(
      fun(L) ->
              L1 = lists:nth(1, string:split(L, "//", all)), % delete comment
              L2 = string:trim(L1), % delete spaces
              if L2 =:= [] -> false;
                true      -> {true, L2}
              end
      end, Line).

command_type(Line) ->
    case Line of
        [$@ | A] -> % address
            case string:to_integer(A) of
                {error, _} ->
                    {address, {symbol, A}};
                {Int, _} ->
                    {address, Int}
            end;

        [$( | L] -> % label
            {label, string:trim(L, trailing, ")")}; % delete "()"

        _ -> % compute
            Es = string:lexemes(Line, "=;"),
            [D, C, J] = case Es of
                            [X] ->
                                [[], X, []];
                            [X, Y] ->
                                Sr = string:find(Line, "="),
                                if Sr =:= nomatch ->
                                        [[], X, Y];
                                  true ->
                                        [X, Y, []]
                                end;
                            _ ->
                                Es
                        end,
            {compute, {{dest, D}, {comp, C}, {jump, J}}}
    end.

%%------------------------------------------------------------
%% Symbol/label to address resolution
%%------------------------------------------------------------

symbol_init() ->
    #{"SP"     => 16#0000,
      "LCL"    => 16#0001,
      "ARG"    => 16#0002,
      "THIS"   => 16#0003,
      "THAT"   => 16#0004,
      "R0"     => 16#0000,
      "R1"     => 16#0001,
      "R2"     => 16#0002,
      "R3"     => 16#0003,
      "R4"     => 16#0004,
      "R5"     => 16#0005,
      "R6"     => 16#0006,
      "R7"     => 16#0007,
      "R8"     => 16#0008,
      "R9"     => 16#0009,
      "R10"    => 16#000a,
      "R11"    => 16#000b,
      "R12"    => 16#000c,
      "R13"    => 16#000d,
      "R14"    => 16#000e,
      "R15"    => 16#000f,
      "SCREEN" => 16#4000,
      "KBD"    => 16#6000}.

%% delete "(LABEL)" and store its address to map
label_to_addr(Ls, Map) ->
    label_to_addr(Ls, Map, -1, []).

label_to_addr([], Map, _, Acc) ->
    {lists:reverse(Acc), Map};
label_to_addr([H|T], M, Ln, Acc) ->
    {Type, Val} = H,
    case Type of
        label ->
            M1 = maps:put(Val, Ln+1, M),
            label_to_addr(T, M1, Ln, Acc);
        _ ->
            label_to_addr(T, M, Ln+1, [H|Acc])
    end.

%% name resolution of "@LABEL" and "@user-defined-symbol"
name_rez(Ls, Map) ->
    name_rez(Ls, Map, 16#0010, []).

name_rez([], _, _, Acc) ->
    lists:reverse(Acc);
name_rez([{address, {symbol, S}} | T], M, Sp, Acc) ->
    case maps:find(S, M) of
        {ok, Addr} ->
            name_rez(T, M, Sp, [{address, Addr} | Acc]);
        error ->
            M1 = maps:put(S, Sp, M),
            name_rez(T, M1, Sp+1, [{address, Sp} | Acc])
    end;
name_rez([H|T], M, Sp, Acc) ->
    name_rez(T, M, Sp, [H|Acc]).

%%------------------------------------------------------------
%% Code generation
%%------------------------------------------------------------

code_gen(Ls) ->
    code_gen(Ls, []).

code_gen([], Acc) ->
    lists:reverse(Acc);
code_gen([H|T], Acc) ->
    {Type, Val} = H,
    case Type of
        address ->
            code_gen(T, [[2#0, Val] | Acc]);
        compute ->
            code_gen(T, [handle_comp(Val) | Acc])
    end.

handle_comp(I) ->
    {{dest, D}, {comp, C}, {jump, J}} = I,
    [2#111,
    match_comp(C),
    match_dest(D),
    match_jump(J)].

match_comp(C) ->
    case C of
        %% comp when a=0
        "0"   -> 2#0101010;
        "1"   -> 2#0111111;
        "-1"  -> 2#0111010;
        "D"   -> 2#0001100;
        "A"   -> 2#0110000;
        "!D"  -> 2#0001101;
        "!A"  -> 2#0110001;
        "-D"  -> 2#0001111;
        "-A"  -> 2#0110011;
        "D+1" -> 2#0011111;
        "A+1" -> 2#0110111;
        "D-1" -> 2#0001110;
        "A-1" -> 2#0110010;
        "D+A" -> 2#0000010;
        "D-A" -> 2#0010011;
        "A-D" -> 2#0000111;
        "D&A" -> 2#0000000;
        "D|A" -> 2#0010101;
        %% comp when a=1
        "M"   -> 2#1110000;
        "!M"  -> 2#1110001;
        "-M"  -> 2#1110011;
        "M+1" -> 2#1110111;
        "M-1" -> 2#1110010;
        "D+M" -> 2#1000010;
        "D-M" -> 2#1010011;
        "M-D" -> 2#1000111;
        "D&M" -> 2#1000000;
        "D|M" -> 2#1010101
    end.

match_dest(D) ->
    case D of
        []     -> 2#000;
        "null" -> 2#000;
        "M"    -> 2#001;
        "D"    -> 2#010;
        "MD"   -> 2#011;
        "A"    -> 2#100;
        "AM"   -> 2#101;
        "AD"   -> 2#110;
        "AMD"  -> 2#111
    end.

match_jump(J) ->
    case J of
        []     -> 2#000;
        "null" -> 2#000;
        "JGT"  -> 2#001;
        "JEQ"  -> 2#010;
        "JGE"  -> 2#011;
        "JLT"  -> 2#100;
        "JNE"  -> 2#101;
        "JLE"  -> 2#110;
        "JMP"  -> 2#111
    end.

7 バーチャルマシン#1: スタック操作

コンパイラの構築へ向けた最初の章. この本では以下の2段階で高水準言語で書いたプログラムをHack CPUで実行できるようにする:

  1. 高水準言語をVMを対象とした中間コードへ変換する (9, 10章)

  2. VMをターゲットにした中間コードを機械語へ変換する (7, 8章)

もしコンパイラがこの段階を分けなければ,異なるアーキテクチャごとに別のコンパイラ が必要になってしまう.一方バーチャルマシンは抽象化されたコンピュータであり, 他のコンピュータ上で再現することができる.したがって,このVM向けの中間コード を挟むことによって,高水準言語の移植性を高められる.

バーチャルマシンの実装は様々な方法で実現できる:

この本ではVM変換器 (VM Translator) を実装し,VMコードをHackのアセンブリコードへ変換する方針.

VMプログラムを書く「言語」には以下の4種類のコマンドが含まれる:

  1. 算術

  2. メモリアクセス

  3. プログラムフロー

  4. サブルーチンの呼び出し

この章では,算術とメモリアクセスのためのコマンドを変換する変換器を作る.

スタックマシン

オペランドや命令結果を格納するデータ構造として,スタックを利用する計算モデル. 命令をスタックの一番上から取り出して,その結果をスタックの一番上に置く.

複雑な演算も,スタックへの pushpop で実現することができ, これは逆ポーランド記法に対応する.

7.1 VMのコマンド仕様

実装するVMは16ビットのデータ型を持ち,整数,ブール値,ポインタとして使われる.

7.1.1 算術と論理コマンド

command

return value

add

x + y

sub

x - y

neg

-y

eq

(x = y) ? true : false

gt

(x > y) ? true : false

lt

(x < y) ? true : false

and

x & y

or

x | y

not

!y

なお true = -1 (0xFFFF), false = 0 (0x0000)

7.1.2 メモリアクセスコマンド

push segment index

segment[index] をスタック上にプッシュ

pop segment index

スタックの一番上のデータをポップして,segment[index]へ格納

なお segment は以下の8つで,index は0以上の整数.

segment

purpose

argument

関数の引数を格納

local

関数のローカル変数を格納

static

スタティック変数を格納

constant

0~32767の定数値を持つ擬似セグメント

this/that

異なるヒープ領域に対応する汎用セグメント

pointer

thisとthatセグメントのベースアドレスを持つ2つの要素からなる

temp

一時的な変数を格納するための,固定された8つの要素からなる

argument, localは関数に入るとVMが動的に割り当てる.staticは同じファイルの関数で共有される. またヒープはオブジェクトと配列を格納するためのRAMの専用領域.

7.1.3 プログラムフローと関数呼び出しコマンド

label symbol   // ラベル宣言
goto symbol    // 無条件分岐
if-goto symbol // 条件分岐

function functionName nLocals // 関数宣言.ローカル変数の数を指定
call functionName nArgs       // 関数呼び出し.引数の数を指定
reutn                         // 関数の呼び出し元へ制御を戻す

7.2 標準VMマッピング

ここまでで定義されて抽象的な仕様を実装するためには,VM要素からHackハードウェアへ, VM命令から機械語へのマッピング(標準マッピンング)が必要となる.

VM変換器は1つ以上の .vm ファイルを受け取って1つの .asm ファイルを出力する.

RAMのアドレスは以下のようにマッピングされる:

address

usage

0-15

16個の仮想レジスタ

16-255

スタティック変数

256-2047

スタック

2048-16383

ヒープ

15384-24575

メモリマップドI/O

24576-32767

使用しない

アセンブリ言語の仕様で,RAMのアドレス0から15は, R0-R15のシンボルに加えて SP, LCL, ARG, THIS, THATで参照できるようになっていたが,これはVM実装の 可読性を高めるため.

register

name

usage

RAM[0]

SP

スタックポインタ

RAM[1]

LCL

現在のVM関数におけるlocalセグメントのベースアドレス

RAM[2]

ARG

現在のVM関数におけるargumentセグメントのベースアドレス

RAM[3]

THIS

現在の(ヒープ内における)thisセグメントのベースアドレス

RAM[4]

THAT

現在の(ヒープ内における)thatセグメントのベースアドレス

RAM[5-12]

tempセグメントの値を保持

RAM[13-15]

汎用的なレジスタ

local, argument, this, that

それぞれ,LCL, ARG, THIS, THATに物理ベースアドレスが保持される.よって arg i 等へのアクセスは, base+i 番目のアドレスへ変換される.(この場合 base はARGに保存されたベースアドレスになる)

pointer, temp

pointerセグメントは,THISとTHATにマッピングされ,tempセグメントはR5~R12にマッピングされる. つまり pointer i は 3+i に, temp i は 5+i 番目のアドレスへ変換される.

constant

このセグメントは他と違って物理領域を占有しない,仮想的な存在.VM実装は単純に constant i を 数値のiとして扱う.

static

アセンブリプログラム内の新しいシンボルは,RAMのアドレスが16番目以降の領域に割り当てられ, これがstaticに対応する.例えば Xxx.vmpush static 3 というコマンドが 含まれているとすると @File.3D=M というアセンブリに変換できる.

8 バーチャルマシン#2: プログラム制御

9 高水準言語

10 コンパイラ#1: 構文解析

11 コンパイラ#2: コード生成

12 オペレーティングシステム

13 さらに先へ