From 6b6255ad38d913560571c8d2aaea0fb55c9a030a Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Mon, 12 Jun 2017 09:34:17 +0100 Subject: [PATCH] Added some instructions, and labels for jumps --- 07-interpreter/machine-code.ipynb | 299 +++++++++++++++++++++++++----- 1 file changed, 253 insertions(+), 46 deletions(-) diff --git a/07-interpreter/machine-code.ipynb b/07-interpreter/machine-code.ipynb index cb8e186..7d3d6a6 100644 --- a/07-interpreter/machine-code.ipynb +++ b/07-interpreter/machine-code.ipynb @@ -1,9 +1,43 @@ { "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
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", @@ -16,7 +50,7 @@ }, { "cell_type": "code", - "execution_count": 193, + "execution_count": 23, "metadata": { "collapsed": true }, @@ -30,7 +64,7 @@ }, { "cell_type": "code", - "execution_count": 112, + "execution_count": 24, "metadata": { "collapsed": true }, @@ -43,7 +77,7 @@ }, { "cell_type": "code", - "execution_count": 113, + "execution_count": 25, "metadata": { "collapsed": true }, @@ -56,7 +90,7 @@ }, { "cell_type": "code", - "execution_count": 114, + "execution_count": 26, "metadata": { "collapsed": true }, @@ -68,7 +102,7 @@ }, { "cell_type": "code", - "execution_count": 115, + "execution_count": 27, "metadata": { "collapsed": true }, @@ -83,7 +117,7 @@ }, { "cell_type": "code", - "execution_count": 116, + "execution_count": 28, "metadata": { "collapsed": true }, @@ -96,7 +130,7 @@ }, { "cell_type": "code", - "execution_count": 117, + "execution_count": 29, "metadata": { "collapsed": true }, @@ -109,7 +143,7 @@ }, { "cell_type": "code", - "execution_count": 129, + "execution_count": 30, "metadata": { "collapsed": true }, @@ -122,7 +156,7 @@ }, { "cell_type": "code", - "execution_count": 130, + "execution_count": 31, "metadata": { "collapsed": true }, @@ -138,8 +172,10 @@ }, { "cell_type": "code", - "execution_count": 131, - "metadata": {}, + "execution_count": 32, + "metadata": { + "collapsed": true + }, "outputs": [], "source": [ "instruction_table = {'inc': inc, 'dec': dec, 'jmp': jmp,\n", @@ -150,7 +186,7 @@ }, { "cell_type": "code", - "execution_count": 121, + "execution_count": 33, "metadata": { "collapsed": true }, @@ -168,7 +204,7 @@ }, { "cell_type": "code", - "execution_count": 122, + "execution_count": 34, "metadata": {}, "outputs": [ { @@ -177,7 +213,7 @@ "{'a': 2, 'b': 1, 'c': 0, 'instructions': [], 'pc': 3}" ] }, - "execution_count": 122, + "execution_count": 34, "metadata": {}, "output_type": "execute_result" } @@ -193,7 +229,7 @@ }, { "cell_type": "code", - "execution_count": 123, + "execution_count": 35, "metadata": { "collapsed": true }, @@ -205,19 +241,104 @@ }, { "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 }, @@ -235,7 +356,7 @@ }, { "cell_type": "code", - "execution_count": 146, + "execution_count": 41, "metadata": { "collapsed": true }, @@ -250,7 +371,7 @@ }, { "cell_type": "code", - "execution_count": 127, + "execution_count": 42, "metadata": {}, "outputs": [ { @@ -266,7 +387,7 @@ " 'pc': 4}" ] }, - "execution_count": 127, + "execution_count": 42, "metadata": {}, "output_type": "execute_result" } @@ -283,26 +404,26 @@ }, { "cell_type": "code", - "execution_count": 143, + "execution_count": 43, "metadata": {}, "outputs": [ { "data": { "text/plain": [ - "{'c': 20,\n", + "{'b': 10,\n", + " 1: 10,\n", " 'instructions': [(, ['a', 10]),\n", " (, ['a']),\n", " (, ['b']),\n", " (, ['b', 1]),\n", " (, ['a', 2]),\n", " (, [-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" } @@ -324,7 +445,45 @@ }, { "cell_type": "code", - "execution_count": 159, + "execution_count": 44, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "{'b': 10,\n", + " 1: 10,\n", + " 'instructions': [(, ['a', 10]),\n", + " (, ['a']),\n", + " (, ['b']),\n", + " (, ['b', 1]),\n", + " (, ['a', 2]),\n", + " (, [-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": [ { @@ -345,7 +504,7 @@ " 'pc': 10}" ] }, - "execution_count": 159, + "execution_count": 45, "metadata": {}, "output_type": "execute_result" } @@ -370,38 +529,86 @@ }, { "cell_type": "code", - "execution_count": 196, + "execution_count": 49, + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "{'a': 0,\n", + " 'b': 1,\n", + " 'c': 5,\n", + " 'instructions': [(, ['c', 'a']),\n", + " (, ['b', 0]),\n", + " (, ['a']),\n", + " (, ['b', 3]),\n", + " (, ['b']),\n", + " (, [2]),\n", + " (, ['b']),\n", + " (, ['a', 2]),\n", + " (, [-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}))" ] }, { -- 2.34.1