4 "cell_type": "markdown",
7 "# Machine interpreter\n",
11 "Four registers, `a`, `b`, `c`, and `d`.\n",
12 "Program counter, `pc`.\n",
14 "Each register can hold 8-byte integers (Java `long`s).\n",
16 "Machine carries out the instruction at location `pc`. After it's executed, `pc` increments by 1.\n",
18 "`jmp` and `jpz` override this normal change in `pc`.\n",
20 "| Instruction | Description |\n",
21 "|:------------|:------------|\n",
22 "| `inc r` | increment contents of register `r` |\n",
23 "| `dec r` | decrement contents of register `r` |\n",
24 "| `set r i` | set contents of register `r` to literal value `i` |\n",
25 "| `cpy r s` | copy contents of register `r` into register `s` | \n",
26 "| `jmp i` | jump to instruction `i` places forward |\n",
27 "| `jpz r i` | jump to instruction `i` places forward if<br>register `r` contains zero, otherwise continue to next instruction |\n",
29 "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."
40 "def new_machine():\n",
41 " return {'pc': 0, \n",
46 " 'instructions': []}"
57 "def show_machine(machine):\n",
58 " return ', '.join('{}: {}'.format(sk, machine[int(sk) if sk.isnumeric() else sk]) \n",
59 " for sk in sorted(str(k) for k in machine)\n",
60 " if sk != 'instructions')"
71 "def inc(reg, machine):\n",
72 " machine[reg] += 1\n",
84 "def dec(reg, machine):\n",
85 " machine[reg] -= 1\n",
97 "def jmp(addr, machine):\n",
98 " machine['pc'] += addr"
103 "execution_count": 6,
109 "def jpz(reg, addr, machine):\n",
110 " if machine[reg] == 0:\n",
111 " machine['pc'] += addr\n",
113 " machine['pc'] += 1"
118 "execution_count": 7,
124 "def set_literal(reg, literal, machine):\n",
125 " machine[reg] = literal\n",
126 " machine['pc'] += 1"
131 "execution_count": 8,
137 "def cpy(from_reg, to_reg, machine):\n",
138 " machine[to_reg] = machine[from_reg]\n",
139 " machine['pc'] += 1"
144 "execution_count": 9,
150 "instruction_table = {'inc': inc, 'dec': dec, 'jmp': jmp,\n",
151 " 'jpz': jpz, 'set': set_literal, 'cpy': cpy}\n",
152 "numeric_args_table = {'jmp': [0], 'jpz': [1], 'set': [1], 'sto': [1], 'ld': [1]}"
157 "execution_count": 10,
163 "def parse(instruction):\n",
164 " words = instruction.split()\n",
165 " instr = words[0]\n",
166 " args = words[1:]\n",
167 " if instr in numeric_args_table:\n",
168 " for p in numeric_args_table[instr]:\n",
169 " args[p] = int(args[p])\n",
170 " return instruction_table[instr], args"
175 "execution_count": 11,
181 "{'a': 2, 'b': 1, 'c': 0, 'd': 0, 'instructions': [], 'pc': 3}"
184 "execution_count": 11,
186 "output_type": "execute_result"
190 "m = new_machine()\n",
192 "cargs = ['a', 'b']\n",
200 "execution_count": 12,
206 "def program_from_instructions(prog, machine):\n",
207 " machine['instructions'] = [parse(instr) for instr in prog]"
212 "execution_count": 45,
218 "def unlabel_listing(listing):\n",
219 " labelled_instructions = [i.strip() for i in listing.split('\\n') \n",
221 " if not i.strip().startswith('#')]\n",
222 " return replace_labels(labelled_instructions) "
227 "execution_count": 13,
233 "# def program_from_listing(listing, machine):\n",
234 "# labelled_instructions = [i.strip() for i in listing.split('\\n') \n",
236 "# if not i.strip().startswith('#')]\n",
237 "# instructions = replace_labels(labelled_instructions)\n",
238 "# program_from_instructions(instructions, machine)"
243 "execution_count": 53,
249 "def program_from_listing(listing, machine):\n",
250 " instructions = unlabel_listing(listing)\n",
251 " program_from_instructions(instructions, machine)"
256 "execution_count": 14,
262 "def replace_labels(listing):\n",
264 " for n, i in enumerate(listing):\n",
266 " locations[i.split(':')[0]] = n\n",
268 " unlabelled_listing = []\n",
269 " for n, i in enumerate(listing):\n",
270 " instr = i.split()\n",
272 " instr = i.split(':')[1].split()\n",
274 " instr = i.split()\n",
276 " for term in instr:\n",
277 " if term in locations:\n",
278 " terms += [str(locations[term] - n)]\n",
280 " terms += [term]\n",
281 " transformed_instr = ' '.join(terms)\n",
282 " unlabelled_listing += [transformed_instr]\n",
284 " return unlabelled_listing "
289 "execution_count": 15,
298 "execution_count": 15,
300 "output_type": "execute_result"
304 "'fred: inc a'.split(':')[1].split()"
309 "execution_count": 47,
314 "output_type": "stream",
325 "program = \"\"\"\n",
334 "labelled_instructions = [i.strip() for i in program.split('\\n') if i.strip() if not i.strip().startswith('#')]\n",
335 "instructions = replace_labels(labelled_instructions)\n",
336 "print('\\n'.join(instructions))"
341 "execution_count": 49,
346 "output_type": "stream",
357 "print('\\n'.join(unlabel_listing(program)))"
362 "execution_count": 17,
368 "def run(machine, initial_state=None, trace=False):\n",
369 " if initial_state:\n",
370 " machine.update(initial_state)\n",
371 " while machine['pc'] < len(machine['instructions']):\n",
373 " print(show_machine(machine))\n",
374 " cmd, args = machine['instructions'][machine['pc']]\n",
375 " cmd(*args, machine)"
380 "execution_count": 18,
386 "def execute(listing, initial_state=None, trace=False):\n",
387 " m = new_machine()\n",
388 " program_from_listing(listing, m)\n",
389 " run(m, initial_state=initial_state, trace=trace)\n",
395 "execution_count": 19,
405 " 'instructions': [(<function __main__.inc>, ['a']),\n",
406 " (<function __main__.inc>, ['a']),\n",
407 " (<function __main__.cpy>, ['a', 'b']),\n",
408 " (<function __main__.inc>, ['a'])],\n",
412 "execution_count": 19,
414 "output_type": "execute_result"
418 "program = \"\"\"\n",
429 "execution_count": 20,
439 " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
440 " (<function __main__.dec>, ['a']),\n",
441 " (<function __main__.inc>, ['b']),\n",
442 " (<function __main__.jpz>, ['a', 2]),\n",
443 " (<function __main__.jmp>, [-3])],\n",
447 "execution_count": 20,
449 "output_type": "execute_result"
453 "program = \"\"\"\n",
460 "# m = new_machine()\n",
461 "# program_from_listing(program, m)\n",
463 "execute(program, initial_state={'c': 20})"
468 "execution_count": 21,
478 " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
479 " (<function __main__.dec>, ['a']),\n",
480 " (<function __main__.inc>, ['b']),\n",
481 " (<function __main__.jpz>, ['a', 2]),\n",
482 " (<function __main__.jmp>, [-3])],\n",
486 "execution_count": 21,
488 "output_type": "execute_result"
492 "program = \"\"\"\n",
499 "execute(program, initial_state={'c': 20})"
504 "execution_count": 22,
514 " 'instructions': [(<function __main__.cpy>, ['c', 'a']),\n",
515 " (<function __main__.set_literal>, ['b', 0]),\n",
516 " (<function __main__.dec>, ['a']),\n",
517 " (<function __main__.jpz>, ['b', 3]),\n",
518 " (<function __main__.dec>, ['b']),\n",
519 " (<function __main__.jmp>, [2]),\n",
520 " (<function __main__.inc>, ['b']),\n",
521 " (<function __main__.jpz>, ['a', 3]),\n",
522 " (<function __main__.jmp>, [-6])],\n",
526 "execution_count": 22,
528 "output_type": "execute_result"
532 "program = \"\"\"\n",
543 "# m = new_machine()\n",
544 "# program_from_listing(program, m)\n",
546 "execute(program, initial_state={'c': 5})"
551 "execution_count": 71,
561 " 'instructions': [(<function __main__.cpy>, ['c', 'a']),\n",
562 " (<function __main__.set_literal>, ['b', 0]),\n",
563 " (<function __main__.dec>, ['a']),\n",
564 " (<function __main__.jpz>, ['b', 3]),\n",
565 " (<function __main__.dec>, ['b']),\n",
566 " (<function __main__.jmp>, [2]),\n",
567 " (<function __main__.inc>, ['b']),\n",
568 " (<function __main__.jpz>, ['a', 2]),\n",
569 " (<function __main__.jmp>, [-6])],\n",
573 "execution_count": 71,
575 "output_type": "execute_result"
579 "# b holds parity of number in c: (c % 2)\n",
580 "program = \"\"\"\n",
591 "# m = new_machine()\n",
592 "# program_from_listing(program, m)\n",
594 "execute(program, initial_state={'c': 5})"
599 "execution_count": 64,
604 "output_type": "stream",
619 "print('\\n'.join(unlabel_listing(program)))"
624 "execution_count": 65,
630 "'a: 0, b: 1, c: 8, d: 0, pc: 10'"
633 "execution_count": 65,
635 "output_type": "execute_result"
639 "# c holds floor(a/2)\n",
640 "program = \"\"\"\n",
652 "# m = new_machine()\n",
653 "# program_from_listing(program, m)\n",
655 "show_machine(execute(program, initial_state={'a': 17}))"
660 "execution_count": 66,
665 "output_type": "stream",
681 "print('\\n'.join(unlabel_listing(program)))"
686 "execution_count": 25,
692 "'a: 4, b: 0, c: 12, d: 0, pc: 9'"
695 "execution_count": 25,
697 "output_type": "execute_result"
702 "program = \"\"\"\n",
705 " # start of main loop\n",
713 " # end of program \n",
717 "# m = new_machine()\n",
718 "# program_from_listing(program, m)\n",
720 "show_machine(execute(program, initial_state={'a': 4}))"
725 "execution_count": 67,
731 "'a: 0, b: 0, c: 27, d: 0, pc: 11'"
734 "execution_count": 67,
736 "output_type": "execute_result"
741 "program = \"\"\"\n",
744 "loop: jpz b end \n",
747 "smul: jpz a emul\n",
755 "m = new_machine()\n",
756 "program_from_listing(program, m)\n",
758 "show_machine(execute(program, initial_state={'a': 9, 'b': 3}))"
763 "execution_count": 68,
768 "output_type": "stream",
785 "print('\\n'.join(unlabel_listing(program)))"
790 "execution_count": 27,
795 "output_type": "stream",
812 "labelled_instructions = [i.strip() for i in program.split('\\n') if i.strip() if not i.strip().startswith('#')]\n",
813 "instructions = replace_labels(labelled_instructions)\n",
814 "print('\\n'.join(instructions))"
819 "execution_count": 28,
825 "'a: 2, b: 0, c: 10, d: 2, pc: 13'"
828 "execution_count": 28,
830 "output_type": "execute_result"
835 "program = \"\"\"\n",
840 "loop: jpz b end \n",
843 "smul: jpz a emul\n",
851 "m = new_machine()\n",
852 "program_from_listing(program, m)\n",
854 "show_machine(execute(program, initial_state={'a': 9, 'b': 3}))"
859 "execution_count": 29,
864 "output_type": "stream",
883 "labelled_instructions = [i.strip() for i in program.split('\\n') \n",
885 " if not i.strip().startswith('#')]\n",
886 "instructions = replace_labels(labelled_instructions)\n",
887 "print('\\n'.join(instructions))"
892 "execution_count": 30,
898 "'a: 52, b: 0, c: 0, d: 0, pc: 48'"
901 "execution_count": 30,
903 "output_type": "execute_result"
907 "# Collatz. a initially holds value, but location 1 is used to store the current value as we're going along.\n",
908 "# Location 2 holds number of steps taken\n",
909 "# Location 3 holds max value reached\n",
910 "program = \"\"\"\n",
915 " # if a is one, finish, \n",
920 " # find parity of a\n",
931 " # b == 0 means a even; b == 1 means a odd\n",
934 " # c holds a * 3 + 1\n",
961 "maxc: jpz c this\n",
969 " # end of program \n",
975 "# m = new_machine()\n",
976 "# program_from_listing(program, m)\n",
978 "show_machine(execute(program, initial_state={'a': 7}))"
983 "execution_count": 31,
992 "execution_count": 31,
994 "output_type": "execute_result"
1002 "cell_type": "code",
1003 "execution_count": 32,
1009 "def max_collatz(start):\n",
1013 " if i % 2 == 0:\n",
1023 "cell_type": "code",
1024 "execution_count": 33,
1033 "execution_count": 33,
1035 "output_type": "execute_result"
1043 "cell_type": "code",
1044 "execution_count": 34,
1053 "execution_count": 34,
1055 "output_type": "execute_result"
1059 "max([(max_collatz(i), i) for i in range(1, 1000)])"
1063 "cell_type": "code",
1064 "execution_count": 36,
1075 "execution_count": 36,
1077 "output_type": "execute_result"
1082 "for i in range(1, 100):\n",
1083 " m = execute(program, initial_state={'a': i})\n",
1084 " c = max_collatz(i)\n",
1085 " if m['a'] != c:\n",
1086 " ans += [(i, m['a'], c)]\n",
1091 "cell_type": "code",
1092 "execution_count": 37,
1096 "ename": "KeyboardInterrupt",
1098 "output_type": "error",
1100 "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
1101 "\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)",
1102 "\u001b[0;32m<ipython-input-37-a9f4d977edea>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mshow_machine\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mexecute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mprogram\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0minitial_state\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;34m{\u001b[0m\u001b[0;34m'a'\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;36m937\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
1103 "\u001b[0;32m<ipython-input-18-d22f089366e4>\u001b[0m in \u001b[0;36mexecute\u001b[0;34m(listing, initial_state, trace)\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0mm\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mnew_machine\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 3\u001b[0m \u001b[0mprogram_from_listing\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlisting\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mm\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0mrun\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mm\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0minitial_state\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0minitial_state\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtrace\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mtrace\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 5\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mm\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
1104 "\u001b[0;32m<ipython-input-17-5478d48920ba>\u001b[0m in \u001b[0;36mrun\u001b[0;34m(machine, initial_state, trace)\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0minitial_state\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 3\u001b[0m \u001b[0mmachine\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mupdate\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0minitial_state\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 4\u001b[0;31m \u001b[0;32mwhile\u001b[0m \u001b[0mmachine\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'pc'\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmachine\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'instructions'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 5\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mtrace\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 6\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mshow_machine\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmachine\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
1105 "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
1110 "show_machine(execute(program, initial_state={'a': 937}))"
1114 "cell_type": "code",
1115 "execution_count": null,
1119 "# labelled_instructions = [i.strip() for i in program.split('\\n') \n",
1120 "# if i.strip() \n",
1121 "# if not i.strip().startswith('#')]\n",
1122 "# instructions = replace_labels(labelled_instructions)\n",
1123 "# print('\\n'.join(instructions))\n",
1124 "# open('07-program.txt', 'w').write('\\n'.join(instructions))"
1128 "cell_type": "code",
1129 "execution_count": 58,
1139 " 'instructions': [(<function __main__.dec>, ['a']),\n",
1140 " (<function __main__.inc>, ['b']),\n",
1141 " (<function __main__.jpz>, ['a', 2]),\n",
1142 " (<function __main__.jmp>, [-3])],\n",
1146 "execution_count": 58,
1148 "output_type": "execute_result"
1153 "program = \"\"\"\n",
1159 "execute(program, initial_state={'a': 3})"
1163 "cell_type": "code",
1164 "execution_count": 59,
1169 "output_type": "stream",
1179 "print('\\n'.join(unlabel_listing(program)))"
1183 "cell_type": "code",
1184 "execution_count": 55,
1194 " 'instructions': [(<function __main__.dec>, ['a']),\n",
1195 " (<function __main__.inc>, ['b']),\n",
1196 " (<function __main__.jpz>, ['a', 2]),\n",
1197 " (<function __main__.jmp>, [-3])],\n",
1201 "execution_count": 55,
1203 "output_type": "execute_result"
1208 "program = \"\"\"\n",
1214 "execute(program, initial_state={'a': 3, 'b': 4})"
1218 "cell_type": "code",
1219 "execution_count": 61,
1229 " 'instructions': [(<function __main__.set_literal>, ['b', 0]),\n",
1230 " (<function __main__.set_literal>, ['c', 0]),\n",
1231 " (<function __main__.jpz>, ['a', 11]),\n",
1232 " (<function __main__.dec>, ['a']),\n",
1233 " (<function __main__.inc>, ['b']),\n",
1234 " (<function __main__.inc>, ['b']),\n",
1235 " (<function __main__.inc>, ['c']),\n",
1236 " (<function __main__.jpz>, ['a', 2]),\n",
1237 " (<function __main__.jmp>, [-5]),\n",
1238 " (<function __main__.dec>, ['c']),\n",
1239 " (<function __main__.inc>, ['a']),\n",
1240 " (<function __main__.jpz>, ['c', 2]),\n",
1241 " (<function __main__.jmp>, [-3]),\n",
1242 " (<function __main__.set_literal>, ['c', 0])],\n",
1246 "execution_count": 61,
1248 "output_type": "execute_result"
1252 "# Puts double a in b, leaves a unchanged\n",
1253 "program = \"\"\"\n",
1269 "execute(program, initial_state={'a': 4})"
1273 "cell_type": "code",
1274 "execution_count": 62,
1279 "output_type": "stream",
1299 "print('\\n'.join(unlabel_listing(program)))"
1303 "cell_type": "code",
1304 "execution_count": null,
1314 "display_name": "Python 3",
1315 "language": "python",
1319 "codemirror_mode": {
1323 "file_extension": ".py",
1324 "mimetype": "text/x-python",
1326 "nbconvert_exporter": "python",
1327 "pygments_lexer": "ipython3",