{
"cells": [
{
- "cell_type": "code",
- "execution_count": 111,
+ "cell_type": "markdown",
"metadata": {},
+ "source": [
+ "# Machine interpreter\n",
+ "\n",
+ "## Instructions\n",
+ "\n",
+ "Three registers, `a`, `b`, and `c`. \n",
+ "Program counter, `pc`.\n",
+ "Unlimited memory in numbered addresses, completely separate from program storage.\n",
+ "\n",
+ "Each register and memory location can hold 8-byte integers (Java `long`s).\n",
+ "\n",
+ "Machine carries out the instruction at location `pc`. After it's executed, `pc` increments by 1.\n",
+ "\n",
+ "`jmp` and `jpz` override this normal change in `pc`.\n",
+ "\n",
+ "| Instruction | Description |\n",
+ "|:------------|:------------|\n",
+ "| `inc r` | increment contents of register `r` |\n",
+ "| `dec r` | decrement contents of register `r` |\n",
+ "| `set r i` | set contents of register `r` to literal value `i` |\n",
+ "| `cpy r s` | set contents of register `r` into register `s` | \n",
+ "| `sto r m` | store contents of register `r` into memory location `m` |\n",
+ "| `ld r m` | load contents of memory location `m` into register `r` |\n",
+ "| `jmp i` | jump to instruction `i` places forward |\n",
+ "| `jpz r i` | jump to instruction `i` places forward if<br>register `r` contains zero, otherwise continue to next instruction |\n",
+ "\n",
+ "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."
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 22,
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"def new_machine():\n",
},
{
"cell_type": "code",
- "execution_count": 193,
+ "execution_count": 23,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 112,
+ "execution_count": 24,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 113,
+ "execution_count": 25,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 114,
+ "execution_count": 26,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 115,
+ "execution_count": 27,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 116,
+ "execution_count": 28,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 117,
+ "execution_count": 29,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 129,
+ "execution_count": 30,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 130,
+ "execution_count": 31,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 131,
- "metadata": {},
+ "execution_count": 32,
+ "metadata": {
+ "collapsed": true
+ },
"outputs": [],
"source": [
"instruction_table = {'inc': inc, 'dec': dec, 'jmp': jmp,\n",
},
{
"cell_type": "code",
- "execution_count": 121,
+ "execution_count": 33,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 122,
+ "execution_count": 34,
"metadata": {},
"outputs": [
{
"{'a': 2, 'b': 1, 'c': 0, 'instructions': [], 'pc': 3}"
]
},
- "execution_count": 122,
+ "execution_count": 34,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 123,
+ "execution_count": 35,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 124,
+ "execution_count": 36,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def program_from_listing(listing, machine):\n",
- " program_from_instructions([i for i in listing.split('\\n') if i], machine)"
+ " labelled_instructions = [i for i in listing.split('\\n') if i]\n",
+ " instructions = replace_labels(labelled_instructions)\n",
+ " program_from_instructions(instructions, machine)"
]
},
{
"cell_type": "code",
- "execution_count": 156,
+ "execution_count": 37,
+ "metadata": {
+ "collapsed": true
+ },
+ "outputs": [],
+ "source": [
+ "def replace_labels(listing):\n",
+ " locations = {}\n",
+ " for n, i in enumerate(listing):\n",
+ " if ':' in i:\n",
+ " locations[i.split(':')[0]] = n\n",
+ "\n",
+ " unlabelled_listing = []\n",
+ " for n, i in enumerate(listing):\n",
+ " instr = i.split()\n",
+ " if ':' in i:\n",
+ " instr = i.split(':')[1].split()\n",
+ " else:\n",
+ " instr = i.split()\n",
+ " terms = []\n",
+ " for term in instr:\n",
+ " if term in locations:\n",
+ " terms += [str(locations[term] - n)]\n",
+ " else:\n",
+ " terms += [term]\n",
+ " transformed_instr = ' '.join(terms)\n",
+ " unlabelled_listing += [transformed_instr]\n",
+ " \n",
+ " return unlabelled_listing "
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 38,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['inc', 'a']"
+ ]
+ },
+ "execution_count": 38,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "'fred: inc a'.split(':')[1].split()"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 39,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "['set a 10', 'dec a', 'inc b', 'sto b 1', 'jpz a 2', 'jmp -4']"
+ ]
+ },
+ "execution_count": 39,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "program = \"\"\"\n",
+ " set a 10\n",
+ "loop: dec a\n",
+ " inc b\n",
+ " sto b 1\n",
+ " jpz a 2\n",
+ " jmp loop\n",
+ "\"\"\"\n",
+ "labelled_instructions = [i for i in program.split('\\n') if i]\n",
+ "instructions = replace_labels(labelled_instructions)\n",
+ "instructions"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 40,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 146,
+ "execution_count": 41,
"metadata": {
"collapsed": true
},
},
{
"cell_type": "code",
- "execution_count": 127,
+ "execution_count": 42,
"metadata": {},
"outputs": [
{
" 'pc': 4}"
]
},
- "execution_count": 127,
+ "execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 143,
+ "execution_count": 43,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
- "{'c': 20,\n",
+ "{'b': 10,\n",
+ " 1: 10,\n",
" 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
" (<function __main__.dec>, ['a']),\n",
" (<function __main__.inc>, ['b']),\n",
" (<function __main__.sto>, ['b', 1]),\n",
" (<function __main__.jpz>, ['a', 2]),\n",
" (<function __main__.jmp>, [-4])],\n",
- " 1: 10,\n",
- " 'b': 10,\n",
" 'pc': 6,\n",
- " 'a': 0}"
+ " 'a': 0,\n",
+ " 'c': 20}"
]
},
- "execution_count": 143,
+ "execution_count": 43,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 159,
+ "execution_count": 44,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "{'b': 10,\n",
+ " 1: 10,\n",
+ " 'instructions': [(<function __main__.set_literal>, ['a', 10]),\n",
+ " (<function __main__.dec>, ['a']),\n",
+ " (<function __main__.inc>, ['b']),\n",
+ " (<function __main__.sto>, ['b', 1]),\n",
+ " (<function __main__.jpz>, ['a', 2]),\n",
+ " (<function __main__.jmp>, [-4])],\n",
+ " 'pc': 6,\n",
+ " 'a': 0,\n",
+ " 'c': 20}"
+ ]
+ },
+ "execution_count": 44,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "program = \"\"\"\n",
+ " set a 10\n",
+ "loop: dec a\n",
+ " inc b\n",
+ " sto b 1\n",
+ " jpz a 2\n",
+ " jmp loop\n",
+ "\"\"\"\n",
+ "execute(program, initial_state={'c': 20})"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 45,
"metadata": {},
"outputs": [
{
" 'pc': 10}"
]
},
- "execution_count": 159,
+ "execution_count": 45,
"metadata": {},
"output_type": "execute_result"
}
},
{
"cell_type": "code",
- "execution_count": 196,
+ "execution_count": 49,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "{'a': 0,\n",
+ " 'b': 1,\n",
+ " 'c': 5,\n",
+ " 'instructions': [(<function __main__.cpy>, ['c', 'a']),\n",
+ " (<function __main__.set_literal>, ['b', 0]),\n",
+ " (<function __main__.dec>, ['a']),\n",
+ " (<function __main__.jpz>, ['b', 3]),\n",
+ " (<function __main__.dec>, ['b']),\n",
+ " (<function __main__.jmp>, [2]),\n",
+ " (<function __main__.inc>, ['b']),\n",
+ " (<function __main__.jpz>, ['a', 2]),\n",
+ " (<function __main__.jmp>, [-6])],\n",
+ " 'pc': 9}"
+ ]
+ },
+ "execution_count": 49,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "# b holds parity of number in c: (c % 2)\n",
+ "program = \"\"\"\n",
+ " cpy c a\n",
+ " set b 0\n",
+ "loop: dec a\n",
+ " jpz b odd\n",
+ " dec b\n",
+ " jmp end\n",
+ "odd: inc b\n",
+ "end: jpz a 2\n",
+ " jmp loop\n",
+ "\"\"\"\n",
+ "# m = new_machine()\n",
+ "# program_from_listing(program, m)\n",
+ "# run(m)\n",
+ "execute(program, initial_state={'c': 5})"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 52,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
- "'10: 10, a: 0, b: 0, c: 5, pc: 11'"
+ "'10: 7, a: 0, b: 1, c: 3, pc: 11'"
]
},
- "execution_count": 196,
+ "execution_count": 52,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
+ "# c holds floor(a/2)\n",
"program = \"\"\"\n",
- "sto a 10\n",
- "set c 0\n",
- "set b 0\n",
- "dec a\n",
- "jpz b 4\n",
- "dec b\n",
- "inc c\n",
- "jmp 2\n",
- "inc b\n",
- "jpz a 2\n",
- "jmp -7\n",
+ " sto a 10\n",
+ " set c 0\n",
+ " set b 0\n",
+ "loop: dec a\n",
+ " jpz b odd\n",
+ " dec b\n",
+ " inc c\n",
+ " jmp end\n",
+ "odd: inc b\n",
+ "end: jpz a 2\n",
+ " jmp loop\n",
"\"\"\"\n",
"# m = new_machine()\n",
"# program_from_listing(program, m)\n",
"# run(m)\n",
- "show_machine(execute(program, initial_state={'a': 10}))"
+ "show_machine(execute(program, initial_state={'a': 7}))"
]
},
{
projects / ou-summer-of-code-2017.git / commitdiff