07-interpreter/machine-code.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Machine interpreter\n",
   8     "\n",
   9     "## Instructions\n",
  10     "\n",
  11     "Three registers, `a`, `b`, and `c`. \n",
  12     "Program counter, `pc`.\n",
  13     "Unlimited memory in numbered addresses, completely separate from program storage.\n",
  14     "\n",
  15     "Each register and memory location can hold 8-byte integers (Java `long`s).\n",
  16     "\n",
  17     "Machine carries out the instruction at location `pc`. After it's executed, `pc` increments by 1.\n",
  18     "\n",
  19     "`jmp` and `jpz` override this normal change in `pc`.\n",
  20     "\n",
  21     "| Instruction | Description |\n",
  22     "|:------------|:------------|\n",
  23     "| `inc r`     | increment contents of register `r` |\n",
  24     "| `dec r`     | decrement contents of register `r` |\n",
  25     "| `set r i`   | set contents of register `r` to literal value `i` |\n",
  26     "| `cpy r s`   | set contents of register `r` into register `s` | \n",
  27     "| `sto r m`   | store contents of register `r` into memory location `m` |\n",
  28     "| `ld r m`    | load contents of memory location `m` into register `r` |\n",
  29     "| `jmp i`     | jump to instruction `i` places forward |\n",
  30     "| `jpz r i`   | jump to instruction `i` places forward if<br>register `r` contains zero, otherwise continue to next instruction |\n",
  31     "\n",
  32     "For `jmp` and `jpz`, `i` is relative to the current instruction. `i` can be negative to jump to earlier places in the program. `i`=1 is a no-op, `i`=0 causes an infinite loop."
  33    ]
  34   },
  35   {
  36    "cell_type": "code",
  37    "execution_count": 22,
  38    "metadata": {
  39     "collapsed": true
  40    },
  41    "outputs": [],
  42    "source": [
  43     "def new_machine():\n",
  44     "    return {'pc': 0, \n",
  45     "            'a': 0,\n",
  46     "            'b': 0, \n",
  47     "            'c': 0,\n",
  48     "            'instructions': []}"
  49    ]
  50   },
  51   {
  52    "cell_type": "code",
  53    "execution_count": 23,
  54    "metadata": {
  55     "collapsed": true
  56    },
  57    "outputs": [],
  58    "source": [
  59     "def show_machine(machine):\n",
  60     "    return ', '.join('{}: {}'.format(sk, machine[int(sk) if sk.isnumeric() else sk]) \n",
  61     "                     for sk in sorted(str(k) for k in machine)\n",
  62     "                     if sk != 'instructions')"
  63    ]
  64   },
  65   {
  66    "cell_type": "code",
  67    "execution_count": 24,
  68    "metadata": {
  69     "collapsed": true
  70    },
  71    "outputs": [],
  72    "source": [
  73     "def inc(reg, machine):\n",
  74     "    machine[reg] += 1\n",
  75     "    machine['pc'] += 1"
  76    ]
  77   },
  78   {
  79    "cell_type": "code",
  80    "execution_count": 25,
  81    "metadata": {
  82     "collapsed": true
  83    },
  84    "outputs": [],
  85    "source": [
  86     "def dec(reg, machine):\n",
  87     "    machine[reg] -= 1\n",
  88     "    machine['pc'] += 1"
  89    ]
  90   },
  91   {
  92    "cell_type": "code",
  93    "execution_count": 26,
  94    "metadata": {
  95     "collapsed": true
  96    },
  97    "outputs": [],
  98    "source": [
  99     "def jmp(addr, machine):\n",
 100     "    machine['pc'] += addr"
 101    ]
 102   },
 103   {
 104    "cell_type": "code",
 105    "execution_count": 27,
 106    "metadata": {
 107     "collapsed": true
 108    },
 109    "outputs": [],
 110    "source": [
 111     "def jpz(reg, addr, machine):\n",
 112     "    if machine[reg] == 0:\n",
 113     "        machine['pc'] += addr\n",
 114     "    else:\n",
 115     "        machine['pc'] += 1"
 116    ]
 117   },
 118   {
 119    "cell_type": "code",
 120    "execution_count": 28,
 121    "metadata": {
 122     "collapsed": true
 123    },
 124    "outputs": [],
 125    "source": [
 126     "def set_literal(reg, literal, machine):\n",
 127     "    machine[reg] = literal\n",
 128     "    machine['pc'] += 1"
 129    ]
 130   },
 131   {
 132    "cell_type": "code",
 133    "execution_count": 29,
 134    "metadata": {
 135     "collapsed": true
 136    },
 137    "outputs": [],
 138    "source": [
 139     "def cpy(from_reg, to_reg, machine):\n",
 140     "    machine[to_reg] = machine[from_reg]\n",
 141     "    machine['pc'] += 1"
 142    ]
 143   },
 144   {
 145    "cell_type": "code",
 146    "execution_count": 30,
 147    "metadata": {
 148     "collapsed": true
 149    },
 150    "outputs": [],
 151    "source": [
 152     "def sto(reg, addr, machine):\n",
 153     "    machine[addr] = machine[reg]\n",
 154     "    machine['pc'] += 1"
 155    ]
 156   },
 157   {
 158    "cell_type": "code",
 159    "execution_count": 31,
 160    "metadata": {
 161     "collapsed": true
 162    },
 163    "outputs": [],
 164    "source": [
 165     "def ld(reg, addr, machine):\n",
 166     "    if addr in machine:\n",
 167     "        machine[reg] = machine[addr]\n",
 168     "    else:\n",
 169     "        machine[reg] = 0\n",
 170     "    machine['pc'] += 1"
 171    ]
 172   },
 173   {
 174    "cell_type": "code",
 175    "execution_count": 32,
 176    "metadata": {
 177     "collapsed": true
 178    },
 179    "outputs": [],
 180    "source": [
 181     "instruction_table = {'inc': inc, 'dec': dec, 'jmp': jmp,\n",
 182     "                    'jpz': jpz, 'set': set_literal, 'cpy': cpy,\n",
 183     "                    'sto': sto, 'ld': ld}\n",
 184     "numeric_args_table = {'jmp': [0], 'jpz': [1], 'set': [1], 'sto': [1], 'ld': [1]}"
 185    ]
 186   },
 187   {
 188    "cell_type": "code",
 189    "execution_count": 33,
 190    "metadata": {
 191     "collapsed": true
 192    },
 193    "outputs": [],
 194    "source": [
 195     "def parse(instruction):\n",
 196     "    words = instruction.split()\n",
 197     "    instr = words[0]\n",
 198     "    args = words[1:]\n",
 199     "    if instr in numeric_args_table:\n",
 200     "        for p in numeric_args_table[instr]:\n",
 201     "            args[p] = int(args[p])\n",
 202     "    return instruction_table[instr], args"
 203    ]
 204   },
 205   {
 206    "cell_type": "code",
 207    "execution_count": 34,
 208    "metadata": {},
 209    "outputs": [
 210     {
 211      "data": {
 212       "text/plain": [
 213        "{'a': 2, 'b': 1, 'c': 0, 'instructions': [], 'pc': 3}"
 214       ]
 215      },
 216      "execution_count": 34,
 217      "metadata": {},
 218      "output_type": "execute_result"
 219     }
 220    ],
 221    "source": [
 222     "m = new_machine()\n",
 223     "inc('a', m)\n",
 224     "cargs = ['a', 'b']\n",
 225     "cpy(*cargs, m)\n",
 226     "inc('a', m)\n",
 227     "m"
 228    ]
 229   },
 230   {
 231    "cell_type": "code",
 232    "execution_count": 35,
 233    "metadata": {
 234     "collapsed": true
 235    },
 236    "outputs": [],
 237    "source": [
 238     "def program_from_instructions(prog, machine):\n",
 239     "    machine['instructions'] = [parse(instr) for instr in prog]"
 240    ]
 241   },
 242   {
 243    "cell_type": "code",
 244    "execution_count": 36,
 245    "metadata": {
 246     "collapsed": true
 247    },
 248    "outputs": [],
 249    "source": [
 250     "def program_from_listing(listing, machine):\n",
 251     "    labelled_instructions = [i for i in listing.split('\\n') if i]\n",
 252     "    instructions = replace_labels(labelled_instructions)\n",
 253     "    program_from_instructions(instructions, machine)"
 254    ]
 255   },
 256   {
 257    "cell_type": "code",
 258    "execution_count": 37,
 259    "metadata": {
 260     "collapsed": true
 261    },
 262    "outputs": [],
 263    "source": [
 264     "def replace_labels(listing):\n",
 265     "    locations = {}\n",
 266     "    for n, i in enumerate(listing):\n",
 267     "        if ':' in i:\n",
 268     "            locations[i.split(':')[0]] = n\n",
 269     "\n",
 270     "    unlabelled_listing = []\n",
 271     "    for n, i in enumerate(listing):\n",
 272     "        instr = i.split()\n",
 273     "        if ':' in i:\n",
 274     "            instr = i.split(':')[1].split()\n",
 275     "        else:\n",
 276     "            instr = i.split()\n",
 277     "        terms = []\n",
 278     "        for term in instr:\n",
 279     "            if term in locations:\n",
 280     "                terms += [str(locations[term] - n)]\n",
 281     "            else:\n",
 282     "                terms += [term]\n",
 283     "        transformed_instr = ' '.join(terms)\n",
 284     "        unlabelled_listing += [transformed_instr]\n",
 285     "        \n",
 286     "    return unlabelled_listing    "
 287    ]
 288   },
 289   {
 290    "cell_type": "code",
 291    "execution_count": 38,
 292    "metadata": {},
 293    "outputs": [
 294     {
 295      "data": {
 296       "text/plain": [
 297        "['inc', 'a']"
 298       ]
 299      },
 300      "execution_count": 38,
 301      "metadata": {},
 302      "output_type": "execute_result"
 303     }
 304    ],
 305    "source": [
 306     "'fred: inc a'.split(':')[1].split()"
 307    ]
 308   },
 309   {
 310    "cell_type": "code",
 311    "execution_count": 39,
 312    "metadata": {},
 313    "outputs": [
 314     {
 315      "data": {
 316       "text/plain": [
 317        "['set a 10', 'dec a', 'inc b', 'sto b 1', 'jpz a 2', 'jmp -4']"
 318       ]
 319      },
 320      "execution_count": 39,
 321      "metadata": {},
 322      "output_type": "execute_result"
 323     }
 324    ],
 325    "source": [
 326     "program = \"\"\"\n",
 327     "      set a 10\n",
 328     "loop: dec a\n",
 329     "      inc b\n",
 330     "      sto b 1\n",
 331     "      jpz a 2\n",
 332     "      jmp loop\n",
 333     "\"\"\"\n",
 334     "labelled_instructions = [i for i in program.split('\\n') if i]\n",
 335     "instructions = replace_labels(labelled_instructions)\n",
 336     "instructions"
 337    ]
 338   },
 339   {
 340    "cell_type": "code",
 341    "execution_count": 40,
 342    "metadata": {
 343     "collapsed": true
 344    },
 345    "outputs": [],
 346    "source": [
 347     "def run(machine, initial_state=None, trace=False):\n",
 348     "    if initial_state:\n",
 349     "        machine.update(initial_state)\n",
 350     "    while machine['pc'] < len(machine['instructions']):\n",
 351     "        if trace:\n",
 352     "            print(show_machine(machine))\n",
 353     "        cmd, args = machine['instructions'][machine['pc']]\n",
 354     "        cmd(*args, machine)"
 355    ]
 356   },
 357   {
 358    "cell_type": "code",
 359    "execution_count": 41,
 360    "metadata": {
 361     "collapsed": true
 362    },
 363    "outputs": [],
 364    "source": [
 365     "def execute(listing, initial_state=None, trace=False):\n",
 366     "    m = new_machine()\n",
 367     "    program_from_listing(listing, m)\n",
 368     "    run(m, initial_state=initial_state, trace=trace)\n",
 369     "    return m"
 370    ]
 371   },
 372   {
 373    "cell_type": "code",
 374    "execution_count": 42,
 375    "metadata": {},
 376    "outputs": [
 377     {
 378      "data": {
 379       "text/plain": [
 380        "{'a': 3,\n",
 381        " 'b': 2,\n",
 382        " 'c': 0,\n",
 383        " 'instructions': [(<function __main__.inc>, ['a']),\n",
 384        "  (<function __main__.inc>, ['a']),\n",
 385        "  (<function __main__.cpy>, ['a', 'b']),\n",
 386        "  (<function __main__.inc>, ['a'])],\n",
 387        " 'pc': 4}"
 388       ]
 389      },
 390      "execution_count": 42,
 391      "metadata": {},
 392      "output_type": "execute_result"
 393     }
 394    ],
 395    "source": [
 396     "program = \"\"\"\n",
 397     "inc a\n",
 398     "inc a\n",
 399     "cpy a b\n",
 400     "inc a\n",
 401     "\"\"\"\n",
 402     "execute(program)"
 403    ]
 404   },
 405   {
 406    "cell_type": "code",
 407    "execution_count": 43,
 408    "metadata": {},
 409    "outputs": [
 410     {
 411      "data": {
 412       "text/plain": [
 413        "{'b': 10,\n",
 414        " 1: 10,\n",
 415        " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
 416        "  (<function __main__.dec>, ['a']),\n",
 417        "  (<function __main__.inc>, ['b']),\n",
 418        "  (<function __main__.sto>, ['b', 1]),\n",
 419        "  (<function __main__.jpz>, ['a', 2]),\n",
 420        "  (<function __main__.jmp>, [-4])],\n",
 421        " 'pc': 6,\n",
 422        " 'a': 0,\n",
 423        " 'c': 20}"
 424       ]
 425      },
 426      "execution_count": 43,
 427      "metadata": {},
 428      "output_type": "execute_result"
 429     }
 430    ],
 431    "source": [
 432     "program = \"\"\"\n",
 433     "set a 10\n",
 434     "dec a\n",
 435     "inc b\n",
 436     "sto b 1\n",
 437     "jpz a 2\n",
 438     "jmp -4\n",
 439     "\"\"\"\n",
 440     "# m = new_machine()\n",
 441     "# program_from_listing(program, m)\n",
 442     "# run(m)\n",
 443     "execute(program, initial_state={'c': 20})"
 444    ]
 445   },
 446   {
 447    "cell_type": "code",
 448    "execution_count": 44,
 449    "metadata": {},
 450    "outputs": [
 451     {
 452      "data": {
 453       "text/plain": [
 454        "{'b': 10,\n",
 455        " 1: 10,\n",
 456        " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
 457        "  (<function __main__.dec>, ['a']),\n",
 458        "  (<function __main__.inc>, ['b']),\n",
 459        "  (<function __main__.sto>, ['b', 1]),\n",
 460        "  (<function __main__.jpz>, ['a', 2]),\n",
 461        "  (<function __main__.jmp>, [-4])],\n",
 462        " 'pc': 6,\n",
 463        " 'a': 0,\n",
 464        " 'c': 20}"
 465       ]
 466      },
 467      "execution_count": 44,
 468      "metadata": {},
 469      "output_type": "execute_result"
 470     }
 471    ],
 472    "source": [
 473     "program = \"\"\"\n",
 474     "      set a 10\n",
 475     "loop: dec a\n",
 476     "      inc b\n",
 477     "      sto b 1\n",
 478     "      jpz a 2\n",
 479     "      jmp loop\n",
 480     "\"\"\"\n",
 481     "execute(program, initial_state={'c': 20})"
 482    ]
 483   },
 484   {
 485    "cell_type": "code",
 486    "execution_count": 45,
 487    "metadata": {},
 488    "outputs": [
 489     {
 490      "data": {
 491       "text/plain": [
 492        "{'a': 0,\n",
 493        " 'b': 1,\n",
 494        " 'c': 5,\n",
 495        " 'instructions': [(<function __main__.cpy>, ['c', 'a']),\n",
 496        "  (<function __main__.set_literal>, ['b', 0]),\n",
 497        "  (<function __main__.dec>, ['a']),\n",
 498        "  (<function __main__.jpz>, ['b', 3]),\n",
 499        "  (<function __main__.dec>, ['b']),\n",
 500        "  (<function __main__.jmp>, [2]),\n",
 501        "  (<function __main__.inc>, ['b']),\n",
 502        "  (<function __main__.jpz>, ['a', 3]),\n",
 503        "  (<function __main__.jmp>, [-6])],\n",
 504        " 'pc': 10}"
 505       ]
 506      },
 507      "execution_count": 45,
 508      "metadata": {},
 509      "output_type": "execute_result"
 510     }
 511    ],
 512    "source": [
 513     "program = \"\"\"\n",
 514     "cpy c a\n",
 515     "set b 0\n",
 516     "dec a\n",
 517     "jpz b 3\n",
 518     "dec b\n",
 519     "jmp 2\n",
 520     "inc b\n",
 521     "jpz a 3\n",
 522     "jmp -6\n",
 523     "\"\"\"\n",
 524     "# m = new_machine()\n",
 525     "# program_from_listing(program, m)\n",
 526     "# run(m)\n",
 527     "execute(program, initial_state={'c': 5})"
 528    ]
 529   },
 530   {
 531    "cell_type": "code",
 532    "execution_count": 49,
 533    "metadata": {},
 534    "outputs": [
 535     {
 536      "data": {
 537       "text/plain": [
 538        "{'a': 0,\n",
 539        " 'b': 1,\n",
 540        " 'c': 5,\n",
 541        " 'instructions': [(<function __main__.cpy>, ['c', 'a']),\n",
 542        "  (<function __main__.set_literal>, ['b', 0]),\n",
 543        "  (<function __main__.dec>, ['a']),\n",
 544        "  (<function __main__.jpz>, ['b', 3]),\n",
 545        "  (<function __main__.dec>, ['b']),\n",
 546        "  (<function __main__.jmp>, [2]),\n",
 547        "  (<function __main__.inc>, ['b']),\n",
 548        "  (<function __main__.jpz>, ['a', 2]),\n",
 549        "  (<function __main__.jmp>, [-6])],\n",
 550        " 'pc': 9}"
 551       ]
 552      },
 553      "execution_count": 49,
 554      "metadata": {},
 555      "output_type": "execute_result"
 556     }
 557    ],
 558    "source": [
 559     "# b holds parity of number in c: (c % 2)\n",
 560     "program = \"\"\"\n",
 561     "      cpy c a\n",
 562     "      set b 0\n",
 563     "loop: dec a\n",
 564     "      jpz b odd\n",
 565     "      dec b\n",
 566     "      jmp end\n",
 567     "odd:  inc b\n",
 568     "end:  jpz a 2\n",
 569     "      jmp loop\n",
 570     "\"\"\"\n",
 571     "# m = new_machine()\n",
 572     "# program_from_listing(program, m)\n",
 573     "# run(m)\n",
 574     "execute(program, initial_state={'c': 5})"
 575    ]
 576   },
 577   {
 578    "cell_type": "code",
 579    "execution_count": 52,
 580    "metadata": {},
 581    "outputs": [
 582     {
 583      "data": {
 584       "text/plain": [
 585        "'10: 7, a: 0, b: 1, c: 3, pc: 11'"
 586       ]
 587      },
 588      "execution_count": 52,
 589      "metadata": {},
 590      "output_type": "execute_result"
 591     }
 592    ],
 593    "source": [
 594     "# c holds floor(a/2)\n",
 595     "program = \"\"\"\n",
 596     "      sto a 10\n",
 597     "      set c 0\n",
 598     "      set b 0\n",
 599     "loop: dec a\n",
 600     "      jpz b odd\n",
 601     "      dec b\n",
 602     "      inc c\n",
 603     "      jmp end\n",
 604     "odd:  inc b\n",
 605     "end:  jpz a 2\n",
 606     "      jmp loop\n",
 607     "\"\"\"\n",
 608     "# m = new_machine()\n",
 609     "# program_from_listing(program, m)\n",
 610     "# run(m)\n",
 611     "show_machine(execute(program, initial_state={'a': 7}))"
 612    ]
 613   },
 614   {
 615    "cell_type": "code",
 616    "execution_count": null,
 617    "metadata": {
 618     "collapsed": true
 619    },
 620    "outputs": [],
 621    "source": []
 622   }
 623  ],
 624  "metadata": {
 625   "kernelspec": {
 626    "display_name": "Python 3",
 627    "language": "python",
 628    "name": "python3"
 629   },
 630   "language_info": {
 631    "codemirror_mode": {
 632     "name": "ipython",
 633     "version": 3
 634    },
 635    "file_extension": ".py",
 636    "mimetype": "text/x-python",
 637    "name": "python",
 638    "nbconvert_exporter": "python",
 639    "pygments_lexer": "ipython3",
 640    "version": "3.5.2+"
 641   }
 642  },
 643  "nbformat": 4,
 644  "nbformat_minor": 2
 645 }