021: 「SSCを定義する」の解答

問題 / ヒント

難易度: ☆☆☆

方針

命令表を1つ定義し、そこからopcodeの逆引き辞書を作ります。 命令の実行では、現在の pc が指すメモリを読み、命令名ごとにAccumulator、メモリ、入出力、pc を更新します。

実装

INSTRUCTIONS = {
    "Jump": 0b000,
    "Add": 0b001,
    "Sub": 0b010,
    "Load": 0b011,
    "Store": 0b100,
    "Read": 0b101,
    "Write": 0b110,
    "Shift": 0b111,
}

OPCODE_TO_NAME = {}
for name, opcode in INSTRUCTIONS.items():
    OPCODE_TO_NAME[opcode] = name


def encode_instruction(name, operand):
    if operand < 0 or operand > 31:
        raise ValueError("operand must be between 0 and 31")
    return (INSTRUCTIONS[name] << 5) | operand


def decode_instruction(instruction):
    if instruction < 0 or instruction > 255:
        raise ValueError("instruction must be an 8-bit integer")
    opcode = instruction >> 5
    operand = instruction & 0b11111
    return (OPCODE_TO_NAME[opcode], operand)


def assemble_line(line):
    line = line.split(";", 1)[0].strip()
    if line == "":
        return None
    if line == "Stop":
        return encode_instruction("Jump", 0)

    name, operand_text = line.split()
    return encode_instruction(name, int(operand_text))


def disassemble_instruction(instruction):
    name, operand = decode_instruction(instruction)
    if name == "Jump" and operand == 0:
        return "Stop"
    return name + " " + str(operand)


def make_machine(program=None, inputs=None):
    memory = [0] * 32
    if program is not None:
        if len(program) > 32:
            raise ValueError("program is too large")
        for address, value in enumerate(program):
            memory[address] = value
    if inputs is None:
        inputs = []
    return {
        "memory": memory,
        "pc": 0,
        "acc": 0,
        "inputs": list(inputs),
        "outputs": [],
        "halted": False,
    }


def step(machine):
    if machine["halted"]:
        return

    pc = machine["pc"]
    if pc < 0 or pc >= 32:
        raise ValueError("pc is out of range")

    instruction = machine["memory"][pc]
    name, operand = decode_instruction(instruction)
    next_pc = pc + 1

    if name == "Jump":
        if operand == 0:
            machine["halted"] = True
            return
        if machine["acc"] > 0:
            next_pc = operand
    elif name == "Add":
        machine["acc"] += machine["memory"][operand]
    elif name == "Sub":
        machine["acc"] -= machine["memory"][operand]
    elif name == "Load":
        machine["acc"] = machine["memory"][operand]
    elif name == "Store":
        machine["memory"][operand] = machine["acc"]
    elif name == "Read":
        if machine["inputs"] == []:
            raise EOFError("input is empty")
        machine["memory"][operand] = machine["inputs"].pop(0)
    elif name == "Write":
        machine["outputs"].append(machine["memory"][operand])
    elif name == "Shift":
        machine["acc"] <<= operand

    machine["pc"] = next_pc


def run(program, inputs=None, max_steps=1000):
    machine = make_machine(program, inputs)
    steps = 0
    while not machine["halted"]:
        if steps >= max_steps:
            raise RuntimeError("program did not halt")
        step(machine)
        steps += 1
    return machine["outputs"]

確認

assert decode_instruction(0b01100111) == ("Load", 7)
assert encode_instruction("Load", 7) == 103
assert assemble_line("  Shift 1  ; double") == 225
assert disassemble_instruction(0) == "Stop"

program = [
    assemble_line("Read 10"),
    assemble_line("Write 10"),
    assemble_line("Stop"),
]
assert run(program, [42]) == [42]
assert run([assemble_line("Stop")]) == []

発展

メモリを0で埋めると、未使用領域は Jump 0 になります。 そのため、短いプログラムが明示的な Stop を持たなくても、次の0番のメモリ語を実行した時点で停止します。