ipynb/BASIC.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align: right\"><i>Peter Norvig, Feb 2017</i></div>\n",
    "\n",
    "# BASIC Interpreter\n",
    "\n",
    "[Years ago](http://norvig.com/lispy.html), I showed how to write an Interpreter for a dialect of Lisp. Some readers appreciated it, and some asked about an interpreter for a language that isn't just a bunch of parentheses. In 2014 I saw a [celebration](http://time.com/69316/basic/) of the 50th anniversary of the 1964 [Dartmouth BASIC](http://web.archive.org/web/20120716185629/http://www.bitsavers.org/pdf/dartmouth/BASIC_Oct64.pdf) interpreter, and I thought that I could show how to implement such an interpreter.  I never quite finished in 2014, but now it is 2017, I rediscovered this unfinished file, and completed it. For those of you unfamiliar with BASIC, here is a sample program:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "program = '''\n",
    "10 REM POWER TABLE\n",
    "11 DATA 8, 4\n",
    "15 READ N0, P0\n",
    "20 PRINT \"N\",\n",
    "25 FOR P = 2 to P0\n",
    "30   PRINT \"N^\" P,\n",
    "35 NEXT P\n",
    "40 PRINT \"SUM\"\n",
    "45 LET S = 0\n",
    "50 FOR N = 2 TO N0\n",
    "55   PRINT N,\n",
    "60   FOR P = 2 TO P0\n",
    "65     LET S = S + N ^ P\n",
    "70     PRINT N ^ P,\n",
    "75   NEXT P\n",
    "80   PRINT S\n",
    "85 NEXT N\n",
    "99 END\n",
    "'''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course I don't have to build everything from scratch in assembly language, and I don't have to worry about every byte of storage, like [Kemeny](http://www.dartmouth.edu/basicfifty/basic.html), [Gates](http://www.pagetable.com/?p=774), [Allison](https://en.wikipedia.org/wiki/Tiny_BASIC) and [Woz](http://www.retrothing.com/2008/07/restoring-wozs.html) did, so my job is much easier.  The interpreter consists of three phases: \n",
    "* **Tokenization**: breaking a text into a list of tokens, for example: `\"10 READ N\"` becomes `['10', 'READ', 'N']`.\n",
    "* **Parsing**: building an internal representation from the tokens: `Stmt(num=10, typ='READ', args=['N'])`.\n",
    "* **Execution**: do what each statement says; in this case the `READ` statement\n",
    "assigns the next `DATA` element to `N`.\n",
    "\n",
    "Before covering the three phases, some imports:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re \n",
    "from typing import *\n",
    "from collections import namedtuple, defaultdict, deque"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tokenization\n",
    "\n",
    "One way to break a line of text into tokens is to define a regular expression that matches every legal token, and use the `findall` method to return a list of tokens. I'll use the `re.VERBOSE` option so that I can add whitespace and comments to make the regular expression more readble. You can refer to [regular expression syntax](https://docs.python.org/3/library/re.html#regular-expression-syntax) if needed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "tokenize = re.compile(r'''\n",
    "      \\d* \\.? \\d+ (?: E -? \\d+)?                      # number \n",
    "    | SIN|COS|TAN|ATN|EXP|ABS|LOG|SQR|RND|INT|FN[A-Z] # functions\n",
    "    | LET|READ|DATA|PRINT|GOTO|IF|FOR|NEXT|END        # statement types\n",
    "    | DEF|GOSUB|RETURN|DIM|REM|STOP                   # statement types\n",
    "    | TO|THEN|STEP                                    # keywords\n",
    "    | [A-Z]\\d?                                        # variable names (letter + optional digit)\n",
    "    | \".*?\"                                           # label strings (in double quotes)\n",
    "    | <> | >= | <=                                    # multi-character relational operators\n",
    "    | \\S                                              # non-space single character (operators and variables) ''',\n",
    "                      re.VERBOSE).findall"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this version of BASIC, variable names must be either a single letter, or a letter followed by a digit, and user-defined function names must be \"`FN`\" followed by a single letter. The only complicated part is the syntax for numbers: optional digits followed by an optional decimal point, some digits, and optionally a power of 10 marked by \"`E`\" and followed by an (optional) minus sign and some digits. (Note: The regular expression syntax \"`(?: ... )?`\" means that all of \"`...`\" is optional, but is not the group that the `findall` method captures.)\n",
    "\n",
    "Example usage of `tokenize`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['10', 'READ', 'N']"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tokenize('10 READ N')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['100', 'PRINT', '\"SIN(X)^2 = \"', ',', 'SIN', '(', 'X', ')', '^', '2']"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tokenize('100 PRINT \"SIN(X)^2 = \", SIN(X) ^ 2')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That looks good. Note that  my tokens are just strings; it will be the parser's job, not the tokenizer's, to recognize that `'2'` is a number and  `'X'` is the name of a variable.  (In some interpreters, the tokenizer makes  distinctions like these.)\n",
    "\n",
    "There's one important complication: the manual says that \"spaces have no significance in BASIC (except in messages to be printed...)\" Thus, the following should all be equivalent:\n",
    "\n",
    "    10 GOTO 99\n",
    "    10 GO TO 99\n",
    "    10GOTO99\n",
    "    1 0 GOT O9 9\n",
    "    \n",
    "The problem is that `tokenize` gets some of these wrong:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['10', 'G', 'O', 'TO', '99']"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tokenize('10 GO TO 99')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1', '0', 'G', 'O', 'T', 'O9', '9']"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tokenize('1 0 GOT O9 9')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "My first thought was to remove all white space from the input. But that would change the label string `\"HELLO WORLD\"` to `\"HELLOWORLD\"`, which is wrong.  To remove spaces everywhere *except* between  double quotes, I can tokenize the line, then join the tokens back together without spaces, then re-tokenize to get the final list of tokens. I do that in my new function below called `tokenizer`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tokenizer(line: str) -> List[str]:\n",
    "    \"Return a list of the tokens on this line, handling spaces properly, and upper-casing.\"\n",
    "    line = ''.join(tokenize(line)) # Remove whitespace\n",
    "    return tokenize(line.upper())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Peeking at and Popping Tokens\n",
    "\n",
    "I will store my list of tokens in the global variable `TOKENS` and access them through this interface:\n",
    "* `peek()`: return the next token in `TOKENS` (without changing `TOKENS`), or `None` if there are no more tokens.\n",
    "* `pop()`: remove and return the next token in `TOKENS`. \n",
    "* `pop(\"string\")`: remove and return the next token if it is equal to the string; else return `None` and leave `TOKENS` unchanged.\n",
    "* `pop(predicate)`: remove and return the next token if `predicate(token)` is true; else return `None` and leave `TOKENS` unchanged."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "Token = str # Type: a Token is a string\n",
    "\n",
    "TOKENS = [] # Global variable to hold a list of TOKENS\n",
    "\n",
    "def peek() -> Optional[Token]: \n",
    "    \"Return the first token in the global `TOKENS`, or None if we are at the end of the line.\"\n",
    "    return (TOKENS[0] if TOKENS else None)\n",
    "\n",
    "def pop(constraint=None) -> Optional[Token]:\n",
    "    \"\"\"Remove and return the first token in `TOKENS`, or return None if token fails constraint.\n",
    "    constraint can be None, a literal (e.g. pop('=')), or a predicate (e.g. pop(is_varname)).\"\"\"\n",
    "    token = peek()\n",
    "    if constraint is None or (token == constraint) or (callable(constraint) and constraint(token)):\n",
    "        return TOKENS.pop(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(Note: if I expected program lines to contain many tokens, I would use a `deque` instead of a `list` of tokens.) \n",
    "\n",
    "# Testing the Tokenizer\n",
    "\n",
    "We can test `tokenizer` and the related functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def lines(text: str) -> List[str]: \n",
    "    \"A list of the non-empty lines in a text.\"\n",
    "    return [line for line in text.splitlines() if line]\n",
    "    \n",
    "def test_tokenizer() -> bool:\n",
    "    global TOKENS\n",
    "    assert tokenizer('X-1') == ['X', '-', '1'] \n",
    "    assert tokenizer('-2') == ['-', '2']\n",
    "    assert tokenizer('PRINT \"HELLO WORLD\"') == ['PRINT', '\"HELLO WORLD\"']\n",
    "    assert (tokenizer('10 GOTO 99') == tokenizer('10 GO TO 99') == tokenizer('10GOTO99')  == \n",
    "            tokenizer('1 0 GOT O9 9') == ['10', 'GOTO', '99'])\n",
    "    assert (tokenizer('100 PRINT \"HELLO WORLD\", SIN(X) ^ 2') == \n",
    "            ['100', 'PRINT', '\"HELLO WORLD\"', ',', 'SIN', '(', 'X', ')', '^', '2'])\n",
    "    assert (tokenizer('100IFX1+123.4+E1-12.3E4 <> 1.2E-34*-12E34+1+\"HI\" THEN99') ==\n",
    "            ['100', 'IF', 'X1', '+', '123.4', '+', 'E1', '-', '12.3E4', '<>', \n",
    "             '1.2E-34', '*', '-', '12E34', '+', '1', '+', '\"HI\"', 'THEN', '99'])\n",
    "    assert lines('one line') == ['one line']\n",
    "    assert lines('''two\n",
    "    lines''') == ['two', '    lines']\n",
    "    assert lines(program) == [\n",
    "     '10 REM POWER TABLE',\n",
    "     '11 DATA 8, 4',\n",
    "     '15 READ N0, P0',\n",
    "     '20 PRINT \"N\",',\n",
    "     '25 FOR P = 2 to P0',\n",
    "     '30   PRINT \"N^\" P,',\n",
    "     '35 NEXT P',\n",
    "     '40 PRINT \"SUM\"',\n",
    "     '45 LET S = 0',\n",
    "     '50 FOR N = 2 TO N0',\n",
    "     '55   PRINT N,',\n",
    "     '60   FOR P = 2 TO P0',\n",
    "     '65     LET S = S + N ^ P',\n",
    "     '70     PRINT N ^ P,',\n",
    "     '75   NEXT P',\n",
    "     '80   PRINT S',\n",
    "     '85 NEXT N',\n",
    "     '99 END']\n",
    "    assert [tokenizer(line) for line in lines(program)] == [\n",
    "     ['10', 'REM', 'P', 'O', 'W', 'E', 'R', 'T', 'A', 'B', 'L', 'E'],\n",
    "     ['11', 'DATA', '8', ',', '4'],\n",
    "     ['15', 'READ', 'N0', ',', 'P0'],\n",
    "     ['20', 'PRINT', '\"N\"', ','],\n",
    "     ['25', 'FOR', 'P', '=', '2', 'TO', 'P0'],\n",
    "     ['30', 'PRINT', '\"N^\"', 'P', ','],\n",
    "     ['35', 'NEXT', 'P'],\n",
    "     ['40', 'PRINT', '\"SUM\"'],\n",
    "     ['45', 'LET', 'S', '=', '0'],\n",
    "     ['50', 'FOR', 'N', '=', '2', 'TO', 'N0'],\n",
    "     ['55', 'PRINT', 'N', ','],\n",
    "     ['60', 'FOR', 'P', '=', '2', 'TO', 'P0'],\n",
    "     ['65', 'LET', 'S', '=', 'S', '+', 'N', '^', 'P'],\n",
    "     ['70', 'PRINT', 'N', '^', 'P', ','],\n",
    "     ['75', 'NEXT', 'P'],\n",
    "     ['80', 'PRINT', 'S'],\n",
    "     ['85', 'NEXT', 'N'],\n",
    "     ['99', 'END']]\n",
    "\n",
    "    TOKENS = tokenizer('10 GO TO 99') \n",
    "    assert peek() == '10'\n",
    "    assert pop()  == '10'\n",
    "    assert peek() == 'GOTO'\n",
    "    assert pop()  == 'GOTO'\n",
    "    assert peek() == '99'\n",
    "    assert pop(str.isalpha) == None    # '99' is not alphabetic\n",
    "    assert pop('98.6') == None         # '99' is not '98.6'\n",
    "    assert peek() == '99'\n",
    "    assert pop(str.isnumeric)  == '99' # '99' is numeric\n",
    "    assert peek() is None and not TOKENS \n",
    "    \n",
    "    return True\n",
    "    \n",
    "test_tokenizer()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parsing: Grammar of Statements\n",
    "\n",
    "Parsing is the process of transforming the text of a program into an internal representation, which can then be executed.\n",
    "For BASIC, the representation will be an ordered list of statements, and we'll need various data types to represent the parts of the statements.\n",
    "I'll start by showing the grammar of BASIC statements, as seen in the appendix on pages 56-57 of [the manual](http://web.archive.org/web/20120716185629/http://www.bitsavers.org/pdf/dartmouth/BASIC_Oct64.pdf) (see also pages 26-30 for a simpler introduction). A statement starts with a line number, and then can be one of the following 15 types of statements, each \n",
    "type introduced by a distinct keyword and followes by components that are specific to the type:\n",
    "\n",
    "- **`LET`**  `<variable>` **=** `<expression>`\n",
    "- **`READ`** `<list of variable>`\n",
    "- **`DATA`** `<list of number>`\n",
    "- **`PRINT`** `<sequence of label and expression>`\n",
    "- **`GOTO`** `<linenumber>`\n",
    "- **`IF`** `<expression> <relational> <expression>` **`THEN`** `<linenumber>`\n",
    "- **`FOR`** `<varname>` **=** `<expression>` **`TO`** `<expression> [`**`STEP`** `<expression> ]`\n",
    "- **`NEXT`** `<varname>`\n",
    "- **`END`**\n",
    "- **`STOP`**\n",
    "- **`DEF`** `<funcname>` **(** `<varname>` **)** **=** `<expression>`\n",
    "- **`GOSUB`** `<linenumber>`\n",
    "- **`RETURN`**\n",
    "- **`DIM`** `<list of variable>`\n",
    "- **`REM`** `<any string of characters whatsoever>`\n",
    "              \n",
    "The notation `<variable>` means any variable and `<list of variable>` means zero or more variables, separated by commas.  `[`**`STEP`** `<expression> ]` means that the literal string `\"STEP\"` followed by an expression is optional. **Bold** characters must be matched exactly.\n",
    "\n",
    "Rather than use one of the many [language parsing frameworks](https://wiki.python.org/moin/LanguageParsing), I will show how to build a parser from scratch. First I'll translate the grammar above into  Python. Not character-for-character (because it would take a lot of work to get Python to understand how to handle those characters), but almost word-for-word (because I can envision a straightforward way to get Python to handle the following format):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Grammar() -> Dict[Token, list]: \n",
    "    return {\n",
    "    'LET':    [variable, '=', expression],\n",
    "    'READ':   [list_of(variable)],\n",
    "    'DATA':   [list_of(number)],\n",
    "    'PRINT':  [labels_and_expressions],\n",
    "    'GOTO':   [linenumber],\n",
    "    'IF':     [expression, relational, expression, 'THEN', linenumber],\n",
    "    'FOR':    [varname, '=', expression, 'TO', expression, step],\n",
    "    'NEXT':   [varname],\n",
    "    'END':    [],\n",
    "    'STOP':   [],\n",
    "    'DEF':    [funcname, '(', varname, ')', '=', expression],\n",
    "    'GOSUB':  [linenumber],\n",
    "    'RETURN': [],\n",
    "    'DIM':    [list_of(variable)], \n",
    "    'REM':    [anycharacters],\n",
    "    }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parsing Strategy\n",
    "\n",
    "A program is parsed into a list of statements, each statement an object of type `Stmt`. A statement contains various components: a line number, a statement type, and various parts such as numbers, variable names, subscripted variable references, user-defined functions, function calls, operation calls,  and labels.\n",
    "\n",
    "The grammar of BASIC is designed so that at every point, the next token tells us unambiguously how to parse. For example, the first token after the line number defines the type of statement; also, in an expression we know that all three-letter names are functions while all 1-letter names are variables. So the next token will always determine what to parse next, and we will never have to back up and undo a `pop()`. Here is my strategy for parsing statements:\n",
    "\n",
    "* The  grammatical categories, like `variable` and `expression` (and also `statement`), will be defined as functions\n",
    "(with no argument) that pop tokens from the global variable `TOKENS`, and return a data object. For example, calling `linenumber()` will pop a token, convert it to an `int`, and return that. \n",
    "* As an example, consider parsing the statement `\"20 LET X = X + 1\"`. \n",
    "* First tokenize to get: `TOKENS = ['20', 'LET', 'X', '=', 'X', '+', '1']`.\n",
    "* Then call `statement()` (defined below).\n",
    "  * `statement` first  calls `linenumber()`, getting back the integer `20` (and removing `'20'` from `TOKENS`).\n",
    "  * Then it calls `pop()` to get  `'LET'` (removing `'LET'` from `TOKENS`).\n",
    "  * Then it indexes into the grammar with `'LET'`, retrieving the grammar rule `[variable, '=', expression]`.\n",
    "  * Then it processes the 3 constituents of the grammar rule:\n",
    "    * First, call `variable()`, which removes and returns `'X'`.\n",
    "    * Second, call `pop('=')`, which removes `'='` from `TOKENS`, and discard it.\n",
    "    * Third, call `expression()`, which returns a representation of `X + 1`; we write that as `Opcall('X', '+', 1.0)`.\n",
    "  * Finally, `statement` assembles the pieces and returns `Stmt(num=20, typ='LET', args=['X', Opcall('X', '+', 1.0)])`.\n",
    "* If anything goes wrong, call `fail`, which raises an error.\n",
    "\n",
    "Here is the definition of the `Stmt` type and the `statement` grammatical category function:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "Stmt = namedtuple('Stmt', 'num, typ, args') # E.g. '10 GOTO 999' => Stmt(10, 'GOTO', 999)\n",
    "\n",
    "def statement() -> Stmt:\n",
    "    \"Parse a BASIC statement from the global variable `TOKENS`.\"\n",
    "    num  = linenumber()\n",
    "    typ  = pop(is_stmt_type) or fail('unknown statement type')\n",
    "    args = []\n",
    "    for p in grammar[typ]: # For each part of rule, call if callable or match if literal string\n",
    "        if callable(p):\n",
    "            args.append(p())\n",
    "        else:\n",
    "            pop(p) or fail('expected ' + repr(p))\n",
    "    return Stmt(num, typ, args)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Many of the grammatical categories are easy one-liners:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def number():        return (-number() if pop('-') else float(pop())) # Optional minus sign\n",
    "def step():          return (expression() if pop('STEP') else 1)     # 1 is the default step\n",
    "def linenumber():    return int(pop(is_number) or fail('missing line number'))\n",
    "def relational():    return pop(is_relational) or fail('expected a relational operator')\n",
    "def varname():       return pop(is_varname)    or fail('expected a variable name')\n",
    "def funcname():      return pop(is_funcname)   or fail('expected a function name')\n",
    "def anycharacters(): TOKENS.clear() # Ignore tokens in a REM statement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are the predicates that distinguish different types of tokens:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_stmt_type(x)  -> bool: return isa(x, Token) and x in grammar # LET, READ, ...\n",
    "def is_funcname(x)   -> bool: return isa(x, Token) and len(x) == 3 and x.isalpha()  # SIN, COS, FNA, FNB, ...\n",
    "def is_varname(x)    -> bool: return isa(x, Token) and len(x) in (1, 2) and x[0].isalpha() # A, A1, A2, B, ...\n",
    "def is_label(x)      -> bool: return isa(x, Token) and x.startswith('\"') # \"HELLO WORLD\", ...\n",
    "def is_relational(x) -> bool: return isa(x, Token) and x in ('<', '=', '>', '<=', '<>', '>=')\n",
    "def is_number(x)     -> bool: return isa(x, Token) and x and x[0] in '.0123456789'\n",
    "\n",
    "isa = isinstance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that `varname` is what the manual calls \"unsubscripted variable name\" (a letter  by itself, like `X`, or followed by a digit, like `X3`), and that `variable` is a `varname` optionally followed by one or two subscript expressions in parentheses, like `A(I)` or `M(2*I, J)`: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "Varname   = str # Type for a variable name such as `V` or `X3`\n",
    "Subscript = namedtuple('Subscript', 'var, indexes') # E.g. 'A(2, 3)' => Subscript('A', [2, 3])\n",
    "Variable  = Union[Varname, Subscript]\n",
    "\n",
    "def variable() -> Variable: \n",
    "    \"Parse a possibly subscripted variable e.g. 'X3' or 'A(I)' or 'M(I, J)'.\"\n",
    "    V = varname()\n",
    "    if pop('('):\n",
    "        indexes = list_of(expression)()\n",
    "        pop(')') or fail('expected \")\" to close subscript')\n",
    "        return Subscript(V, indexes) # E.g. 'A(I)' => Subscript('A', ['I'])\n",
    "    else: \n",
    "        return V                     # E.g. 'X3' "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`list_of` is tricky because it works at two different times. When I write `list_of(number)` in the grammar, this returns an object of class `list_of`. When this object is called (just as other grammatical categories like `variable` are called), the effect is that it will parse a list of `number`. That list can be empty (if there are no more tokens on the line), or can be a single number, or can be several numbers separated by comma tokens. I could have defined `list_of` as a function that returns a function, but I thought that it would be clearer to define it as a class, so I can clearly separate what happens at the two different times: first the `__init__` method determines what category to parse, and later the `__call__` method does the actual parsing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "class list_of:\n",
    "    \"list_of(category) is a callable that parses a comma-separated list of <category>\"\n",
    "    def __init__(self, category): self.category = category\n",
    "    def __call__(self) -> list:\n",
    "        result = ([self.category()] if TOKENS else [])\n",
    "        while pop(','):\n",
    "            result.append(self.category())\n",
    "        return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parsing: Top Level `parse`, and Handling Errors\n",
    "\n",
    "Most of the parsing action happens inside the function `statement()`, but at the very top level, `parse(program)` takes a program text (that is, a string), and parses each line by calling `parse_line`, sorting the resulting list of lines by line number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse(program: str) -> List[Stmt]: return sorted(map(parse_line, lines(program)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To handle syntactic errors, I add to `parse_line` a `try/except` that catches exceptions raised by calls to `fail`. I acknowledge the interpreter isn't very thorough about handling all errors, and the error messages could be more helpful."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse_line(line: str) -> Stmt:\n",
    "    \"Return a Stmt(linenumber, statement_type, arguments).\"\n",
    "    global TOKENS\n",
    "    TOKENS = tokenizer(line)\n",
    "    try:\n",
    "        stmt = statement()\n",
    "        if TOKENS: \n",
    "            fail('extra TOKENS at end of line')\n",
    "        return stmt\n",
    "    except SyntaxError as err:\n",
    "        error = f\"Error in line '{line}' at '{' '.join(TOKENS)}': {err}\"\n",
    "        print(error)\n",
    "        return Stmt(0, 'REM', [error]) # Return dummy statement\n",
    "        \n",
    "def fail(message): raise SyntaxError(message)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parsing: Grammar of `PRINT` Statements\n",
    "\n",
    "On page 26 of [the manual](https://web.archive.org/web/20120716185629/http://www.bitsavers.org/pdf/dartmouth/BASIC_Oct64.pdf), it appears that the grammar rule for `PRINT` should be `[list_of(expression)]`. But in section 3.1, **More about PRINT**, some complications are introduced:\n",
    "\n",
    "* Labels (strings enclosed in double quotes) are allowed, as well as expressions.\n",
    "* The `\",\"` is not a separator. A line can end with `\",\"`.\n",
    "* Optionally, `\";\"` can be used instead of `\",\"`.\n",
    "* Optionally, the `\",\"` or `\";\"` after a label can be omitted&mdash;we can have a label immediately followed by an expression.\n",
    "\n",
    "The effect of a comma is to advance the output to the next column that is a multiple of 15 (and to a new line if this goes past column 100). The effect of a semicolon is similar, but works in multiples of 3, not 15. (Note that column numbering starts at 0, not 1.) Normally, at the end of a `PRINT` statement we advance to a new line, but this is not done if the statement ends in `\",\"` or `\";\"`. Here are some examples:\n",
    "\n",
    "* `10 PRINT X, Y`\n",
    "<br>Prints the value of `X` in column 0 and `Y` in column 15. Advances to new line.\n",
    "\n",
    "* `20 PRINT \"X =\", X`\n",
    "<br>Prints the string `\"X =\"` in column 0 and the value of `X` in column 15. Advances to new line.\n",
    "\n",
    "* `30 PRINT \"X = \" X`\n",
    "<br>Prints the string `\"X =\"` in column 0 and the value of `X` immediately after. Advances to new line.\n",
    "\n",
    "* `40 PRINT X; Y,`\n",
    "<br>Prints the value of `X` in column 0, and the value of `Y` in the column that is the first available multiple of 3 after that.\n",
    "For example, if `X` is `'0'`, then print `Y` in column 3, but if `X` is `'12345'`, then we've gone past column 3, so print `Y` in column 6.\n",
    "Then, because the statement ends in a comma, advance to the next column that is a multiple of 15, but not to a new line.\n",
    "\n",
    "That explanation was long, but the implementation is short (at least for the parsing part; later we will see the execution part):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def labels_and_expressions() -> list:\n",
    "    \"Parse a sequence of label | comma | semicolon | expression (for PRINT statement).\"\n",
    "    result = []\n",
    "    while TOKENS:\n",
    "        result.append(pop(is_label) or pop(',') or pop(';') or expression())\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parsing: Grammar of Expressions\n",
    "\n",
    "Now for the single most complicated part of the grammar: the `expression`.  The biggest complication is operator precedence: the string `\"A + B * X + C\"` should be parsed as if it were `\"A + (B * X) + C\"`, and not as `\"(A + B) * (X + C),\"` because multiplication binds more tightly than addition. There are [many schemes](https://en.wikipedia.org/wiki/Operator-precedence_parser) for parsing expressions, I'll use  [an approach](https://groups.google.com/forum/#!topic/comp.compilers/ruJLlQTVJ8o) attributed to Keith Clarke called Compact Recursive-Descent Parsing.\n",
    "\n",
    "Like all our grammatical categories, calling `expression()` pops off some tokens and returns a data object. The first thing it does is parse one of five types of simple \"primary\" expressions: \n",
    "a number like `1.23`; \n",
    "a possibly-subscripted variable like `X` or `A(I)`;\n",
    "a function call like `SIN(X)`;\n",
    "a unary negation like `-X`;\n",
    "or a parenthesied expression like `(X + 1)`. \n",
    "\n",
    "Next, `expression` looks for infix operators. To parse `'X + 1'` as an expression, first `primary()` would parse `'X'`, then it would pop off the `'+'` operator, then a recursive call to `expression()` would parse `1`, and the results can then be combined into an `Opcall('X', '+', 1)`. If there are multiple infix operators, they can all be handled, as in `'X+1+Y+2'`, which gets parsed as `Opcall(Opcall(Opcall('X', '+', 1), '+', 'Y'), '+', 2)`.\n",
    "\n",
    "When there are multiple infix operators of *different* precedence, as in `\"A + B * X + C\"`, the trick is to know which operators are parsed by the top-level call to `expression`, and which by recursive calls. When we first call `expression()`, the optional parameter `prec` gets the default value, 1, which is the precedence of addition and subtraction. When `expression` makes a recursive call, it passes the precedence of the current operator, and we only parse off operator/expression pairs at an equal or higher precedence. So, in parsing `\"A + B * X + C\"`, when we pop off the `'*'` operator (which has precedence 2), we then recursively call `expression(2)`, which parses off an expression containing operators of precedence 2 or higher, which means the recursive call will parse `X`, but it won't pop off the `'+'`, because that is at a lower precedence. So we correctly get the structure `\"(A + ((B * X) + C)\"`.\n",
    "\n",
    "The function `associativity` ensures that the operator `'^'` is right associative, meaning `10^2^3` = `(10^(2^3))`, whereas the other operators are left associative, so `10-2-3` = `((10-2)-3)`.\n",
    "\n",
    "Here is the implementation of `expression`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "Opcall  = namedtuple('Opcall', 'x, op, y') # E.g., 'X + 1' => Opcall('X', '+', 1)\n",
    "\n",
    "def expression(prec=1) -> object: \n",
    "    \"Parse an expression: a primary and any [op expression]* pairs with precedence(op) >= prec.\"\n",
    "    exp = primary()                         # 'A' => 'A'\n",
    "    while precedence(peek()) >= prec:\n",
    "        op = pop()\n",
    "        rhs = expression(precedence(op) + associativity(op))\n",
    "        exp = Opcall(exp, op, rhs)          # 'A + B' => Opcall('A', '+', 'B')\n",
    "    return exp\n",
    "\n",
    "def primary() -> object:\n",
    "    \"Parse a primary expression (no infix op except maybe within parens).\"\n",
    "    if is_number(peek()):                   # '1.23' => 1.23 \n",
    "        return number()\n",
    "    elif is_varname(peek()):                # X or A(I) or M(I+1, J)\n",
    "        return variable()\n",
    "    elif is_funcname(peek()):               # SIN(X) => Funcall('SIN', 'X')\n",
    "        return Funcall(pop(), primary())\n",
    "    elif pop('-'):                          # '-X' => Funcall('NEG', 'X')\n",
    "        return Funcall('NEG', primary())\n",
    "    elif pop('('):                          # '(X)' => 'X'\n",
    "        exp = expression()\n",
    "        pop(')') or fail('expected \")\" to end expression')\n",
    "        return exp\n",
    "    else:\n",
    "        return fail('unknown expression')\n",
    "\n",
    "def precedence(op) -> int: \n",
    "    return (3 if op == '^' else 2 if op in ('*', '/', '%') else 1 if op in ('+', '-') else 0)\n",
    "\n",
    "def associativity(op) -> int: \n",
    "    return (0 if op == '^' else 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parsing: Function Definitions and Calls\n",
    "\n",
    "The class `Function` is used to represent the definition of a user defined function. When the user writes `\"DEF FNC(X) = X ^ 3\"`, we specify the function object with `Function(parm='X', body=Opcall('X', '^', 3))`, and whenever the program calls, say, `FNC(2)` in an expression, the call assigns 2 to the **global** variable `X` and computes 8 as the value to return.  (In modern languages, `X` would be a new **local** variable, but BASIC has no local variables.) Note the technique of making `Function` be a subclass of a `namedtuple`; we are then free to add the `__call__` method to the subclass.\n",
    "\n",
    "Note the distinction that `Function` is used to represent a user-defined function such as `FNC`, but `Funcall` is used to represent a function call such as `FNC(2)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "Funcall = namedtuple('Funcall', 'function, arg') # E.g., 'SIN(X)' => Funcall('SIN', 'X')\n",
    "\n",
    "class Function(namedtuple('_', 'parm, body')):\n",
    "    \"User-defined function; 'DEF FNC(X) = X ^ 3' => Function('X', Opcall('X', '^', 3))\"\n",
    "    def __call__(self, value):                           \n",
    "        variables[self.parm] = value # Global assignment to the parameter\n",
    "        return evaluate(self.body)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parsing: The Complete Parser in Action\n",
    "\n",
    "I've now written all the grammatical categories, so I can now safely instantiate the global variable `grammar` by calling `Grammar()`, and parse a program:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Stmt(num=10, typ='REM', args=[None]),\n",
       " Stmt(num=11, typ='DATA', args=[[8.0, 4.0]]),\n",
       " Stmt(num=15, typ='READ', args=[['N0', 'P0']]),\n",
       " Stmt(num=20, typ='PRINT', args=[['\"N\"', ',']]),\n",
       " Stmt(num=25, typ='FOR', args=['P', 2.0, 'P0', 1]),\n",
       " Stmt(num=30, typ='PRINT', args=[['\"N^\"', 'P', ',']]),\n",
       " Stmt(num=35, typ='NEXT', args=['P']),\n",
       " Stmt(num=40, typ='PRINT', args=[['\"SUM\"']]),\n",
       " Stmt(num=45, typ='LET', args=['S', 0.0]),\n",
       " Stmt(num=50, typ='FOR', args=['N', 2.0, 'N0', 1]),\n",
       " Stmt(num=55, typ='PRINT', args=[['N', ',']]),\n",
       " Stmt(num=60, typ='FOR', args=['P', 2.0, 'P0', 1]),\n",
       " Stmt(num=65, typ='LET', args=['S', Opcall(x='S', op='+', y=Opcall(x='N', op='^', y='P'))]),\n",
       " Stmt(num=70, typ='PRINT', args=[[Opcall(x='N', op='^', y='P'), ',']]),\n",
       " Stmt(num=75, typ='NEXT', args=['P']),\n",
       " Stmt(num=80, typ='PRINT', args=[['S']]),\n",
       " Stmt(num=85, typ='NEXT', args=['N']),\n",
       " Stmt(num=99, typ='END', args=[])]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "grammar = Grammar()\n",
    "\n",
    "parse(program)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You might think that the statement \"`11 DATA 8, 4`\" would be parsed into a `Stmt` with `args=[8, 4]`. It has two arguments, right? But according to the grammar, a `DATA` statement actually has only one argument, which is a list of numbers. That's why we get `args=[[8.0, 4.0]]`. \n",
    "\n",
    "Here are some more tests:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def test_exp(text: str, repr) -> bool:\n",
    "    \"Test that text can be parsed as an expression to yield repr, with no TOKENS left over.\"\n",
    "    global TOKENS\n",
    "    TOKENS = tokenizer(text)\n",
    "    return (expression() == repr) and not TOKENS\n",
    "    \n",
    "def test_parser() -> bool:\n",
    "    \"Tests of `expression` and other category functions.\"\n",
    "    assert is_funcname('SIN') and is_funcname('FNZ') # Function names are three letters\n",
    "    assert not is_funcname('X') and not is_funcname('') and not is_funcname('FN9')\n",
    "    assert is_varname('X') and is_varname('A2') # Variables names are one letter and an optional digit\n",
    "    assert not is_varname('FNZ') and not is_varname('A10') and not is_varname('')\n",
    "    assert is_relational('>') and is_relational('>=') and not is_relational('+')\n",
    "    \n",
    "    assert test_exp('A + B * X + C', Opcall(Opcall('A', '+', Opcall('B', '*', 'X')), '+', 'C'))\n",
    "    assert test_exp('A + B + X + C', Opcall(Opcall(Opcall('A', '+', 'B'), '+', 'X'), '+', 'C'))\n",
    "    assert test_exp('SIN(X)^2',      Opcall(Funcall('SIN', 'X'), '^', 2))\n",
    "    assert test_exp('10 ^ 2 ^ 3',    Opcall(10, '^', Opcall(2, '^', 3))) # right associative\n",
    "    assert test_exp('10 - 2 - 3',    Opcall(Opcall(10, '-', 2), '-', 3)) # left associative\n",
    "    assert test_exp('A(I)+M(I, J)',  Opcall(Subscript(var='A', indexes=['I']), '+', \n",
    "                                            Subscript(var='M', indexes=['I', 'J'])))\n",
    "    assert test_exp('X * -1',        Opcall('X', '*', Funcall('NEG', 1.0)))\n",
    "    assert test_exp('X--Y--Z',       Opcall(Opcall('X', '-', Funcall('NEG', 'Y')), \n",
    "                                            '-', Funcall('NEG', 'Z')))\n",
    "    assert test_exp('((((X))))',     'X')\n",
    "    return True\n",
    "\n",
    "test_parser()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Execution\n",
    "\n",
    "Now that we can parse programs, we're ready to execute them. I'll first define `run` to  `parse` and `execute` a program:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def run(program: str) -> None: \n",
    "    \"\"\"Parse and execute the BASIC program.\"\"\"\n",
    "    execute(parse(program))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function `execute(stmts)` first defines the runtime state of the program, which is partially held in three global variables (they are global because they are needed within `basic_print` or `evaluate`, and because the very nature of BASIC is to have global variables):\n",
    "\n",
    "* `column`: The column that `PRINT` will print in next.\n",
    "* `variables`: A mapping of the values of all BASIC variables (both subscripted and unsubscripted). <br>For example, `{'P1': 3.14, ('M', (1, 1)): 42.0}` says that the value of `P1` is `3.14` and `M(1, 1)` is `42.0`.\n",
    "* `functions`: A mapping of the values of all BASIC functions (both built-in and user-defined). <br>For example, `{'FNC': Function('X', Opcall('X', '^', 3)), 'SIN': math.sin}` \n",
    "\n",
    "Program state is also held in these variables that are local to `execute`:\n",
    "\n",
    "* `data`: a queue of all the numbers in the program's `DATA` statements.\n",
    "* `pc`: program counter; the index into the list of statements. Initially 0, the index of the first statement.\n",
    "* `ret`: the index where a `RETURN` statement will return to.\n",
    "* `fors`: a dict of `{varname: ForState(...)}` which gives the state of each `FOR` loop variable.\n",
    "* `goto`: a dict of `{linenumber: index}`, for example `{10: 0, 20: 1}` for a program with two line numbers, 10 and 20.\n",
    "\n",
    "\n",
    "Running the program means executing the statement that the program counter (`pc`) is currently pointing at, repeatedly, until we either hit an `END` or `STOP` statement, attempt a `READ` when there is no more data, or fall off the end of the program. \n",
    "\n",
    "The variable `pc` is initialized to `0`  and is then incremented by `1` each cycle to go to the following statement; but a branching statement (`GOTO`, `IF`, `GOSUB`, or `RETURN`) can change the `pc` to something other than the following statement. Note that branching statements refer to line numbers, but the `pc` refers to the *index* number within the list of statements (as does the `ForSTaate.continu` attribute). The variable `goto` maps from line numbers to index numbers. \n",
    "\n",
    "In BASIC there is no notion of a *stack*, neither for variables nor return addresses. If I do a `GOSUB` to a subroutine that itself does a `GOSUB`, then the original return address is lost, because BASIC has only one return address register (which we call `ret`).\n",
    "\n",
    "The main body of `execute` checks the statement type, and takes appropriate action. All the statement types are straightforward, except for `FOR` and `NEXT`, which are explained in the next section, and `PRINT` which is complicated by the need to keep track of columns."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "ForState  = namedtuple('ForState',  'continu, end, step') # Data for FOR loop \n",
    "\n",
    "def execute(stmts: List[Stmt]) -> None: \n",
    "    \"Execute the statements in the BASIC program.\"\n",
    "    global column, variables, functions, column\n",
    "    column    = 0                  # column to PRINT in next\n",
    "    variables = defaultdict(float) # mapping of {variable: value}, default 0.0\n",
    "    functions = {**builtins,\n",
    "                 **{name: Function(x, body) \n",
    "                    for  (_, _, (name, x, body)) in statements_of_type('DEF', stmts)}}\n",
    "        \n",
    "    data      = deque(append(s.args[0] for s in statements_of_type('DATA', stmts)))\n",
    "    pc        = 0                  # program counter\n",
    "    ret       = 0                  # index (pc) that a GOSUB returns to\n",
    "    fors      = {}                 # runtime map of {varname: ForState(...)}\n",
    "    goto      = {stmt.num: i for (i, stmt) in enumerate(stmts)} # {line_number: index}\n",
    "    while pc < len(stmts):\n",
    "        (_, typ, args) = stmts[pc] # Fetch and decode the current statement\n",
    "        pc += 1                    # Increment the program counter\n",
    "        if typ in ('END', 'STOP') or (typ == 'READ' and not data): \n",
    "            return\n",
    "        elif typ == 'LET':\n",
    "            V, exp = args\n",
    "            let(V, evaluate(exp))\n",
    "        elif typ == 'READ':\n",
    "            for V in args[0]:\n",
    "                let(V, data.popleft())\n",
    "        elif typ == 'PRINT':\n",
    "            basic_print(args[0])\n",
    "        elif typ == 'GOTO':\n",
    "            pc = goto[args[0]]\n",
    "        elif typ == 'IF':\n",
    "            lhs, relational, rhs, dest = args\n",
    "            if functions[relational](evaluate(lhs), evaluate(rhs)):\n",
    "                pc = goto[dest]\n",
    "        elif typ == 'GOSUB':\n",
    "            ret = pc\n",
    "            pc  = goto[args[0]]\n",
    "        elif typ == 'RETURN':\n",
    "            pc = ret\n",
    "        elif typ == 'FOR':\n",
    "            V, start, end, step = args\n",
    "            variables[V] = evaluate(start)\n",
    "            fors[V] = ForState(pc, evaluate(end), evaluate(step))\n",
    "        elif typ == 'NEXT':\n",
    "            V = args[0]\n",
    "            continu, end, step = fors[V]\n",
    "            if ((step >= 0 and variables[V] + step <= end) or\n",
    "                (step <  0 and variables[V] + step >= end)):\n",
    "                variables[V] += step\n",
    "                pc = continu\n",
    "        else:\n",
    "            assert typ in ('REM', 'DIM', 'DATA', 'DEF') # Ignore these at runtime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are the functions referenced by `execute`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import random\n",
    "import operator as op\n",
    "\n",
    "builtins = {  # A mapping of {name: function}\n",
    "    'SIN': math.sin, 'COS': math.cos, 'TAN': math.tan, 'ATN': math.atan, \n",
    "    'ABS': abs, 'EXP': math.exp, 'LOG': math.log, 'SQR': math.sqrt, 'INT': int,\n",
    "    '>': op.gt, '<': op.lt, '=': op.eq, '>=': op.ge, '<=': op.le, '<>': op.ne, \n",
    "    '^': pow, '+': op.add, '-': op.sub, '*': op.mul, '/': op.truediv, '%': op.mod,\n",
    "    'RND': lambda _: random.random(), 'NEG': op.neg}\n",
    "\n",
    "def statements_of_type(typ, statements: List[Stmt]) -> Iterable[Stmt]:\n",
    "    \"\"\"All statements of the given type.\"\"\"\n",
    "    return (stmt for stmt in statements if stmt.typ == typ)\n",
    "\n",
    "def append(list_of_lists) -> list:\n",
    "    \"\"\"Append together a list of lists.\"\"\"\n",
    "    return sum(list_of_lists, [])\n",
    "\n",
    "def evaluate(exp) -> float:\n",
    "    \"Evaluate an expression, returning a number.\"\n",
    "    if isa(exp, Opcall):\n",
    "        return functions[exp.op](evaluate(exp.x), evaluate(exp.y))\n",
    "    elif isa(exp, Funcall):\n",
    "        return functions[exp.function](evaluate(exp.arg))\n",
    "    elif isa(exp, Subscript):\n",
    "        return variables[(exp.var, *(evaluate(x) for x in  exp.indexes))]\n",
    "    elif isa(exp, Varname):\n",
    "        return variables[exp]\n",
    "    else: # Must be a number, which evaluates to itself\n",
    "        return exp\n",
    "        \n",
    "def let(V: Union[Variable, Subscript], value: float):\n",
    "    \"Assign value to the variable name or Subscripted variable.\"\n",
    "    if isa(V, Subscript): # A subsscripted variable\n",
    "        variables[(V.var, *(evaluate(x) for x in V.indexes))] = value \n",
    "    else:                        # An unsubscripted variable\n",
    "        variables[V] = value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Execution: `FOR/NEXT` Statements\n",
    "\n",
    "Some aspects of `FOR` loops are unclear. I have  questions!\n",
    "\n",
    "* Are the `END` and `STEP` expressions evaluated once when we first enter the `FOR` loop, or each time through the loop?\n",
    "  - I choose: only once. (Like Python, but unlike C.)\n",
    "* After executing `\"FOR V = 1 TO 10\"`, is the value of `V` equal to 10 or 11? \n",
    "  - Upon further review, [the manual](https://web.archive.org/web/20120716185629/http://www.bitsavers.org/pdf/dartmouth/BASIC_Oct64.pdf) says 10.\n",
    "* Does `\"FOR V = 2 TO 1\"` execute zero times? Or do all loops execute at least once, with the termination test done by the `NEXT`?\n",
    "  - All loops execute at least once. (Online BASIC interpreters agree.)\n",
    "* What if there are two different `FOR V` loops, and a `GOTO` branches from the middle of one to the middle of the other?\n",
    "  - BASIC doesn't really have a notion of a scope for a loop, there is just a sequence of statements, all in the same scope, and all variables are global to the program. Any `NEXT V` statement always branches to the most recently executed `FOR V`, regardless of the layout of the code. (Online BASIC interpreters agree.) \n",
    "* What if we execute a `NEXT V` statement before ever executing the `FOR V` statement? \n",
    "  - This raises an error. (I asked [Dennis Allison](https://en.wikipedia.org/wiki/Dennis_Allison), the developer of [Tiny Basic](https://en.wikipedia.org/wiki/Tiny_BASIC), and he said this case is undefined, so whatever I choose is okay.)\n",
    "  \n",
    "Consider this program:\n",
    "\n",
    "     0 PRINT \"TABLE OF SQUARES\"\n",
    "    10 LET N = 10\n",
    "    20 FOR V = 1 to N STEP N/5\n",
    "    30   PRINT V, V * V\n",
    "    40 NEXT V\n",
    "    50 END\n",
    "  \n",
    "    \n",
    "When control hits the `\"FOR V\"` statement in line 20, I make these assignments in the interpreter:\n",
    "\n",
    "     variables['V'] = 1\n",
    "     fors['V'] = ForState(continu=3, end=10, step=2)\n",
    "     \n",
    "where `3` is the index of the line right after the `FOR` statement; `10` is the value of `N`; and `2` is the value of `N/5`. A `ForState` is an object that is used during the dynamic execution of the program (one per `FOR` loop variable), but does not occur in the static representation of the program.\n",
    "\n",
    "When control hits the `\"NEXT V\"` statement, do the following:\n",
    "- Retrieve `fors['V']`\n",
    "- Check if `V` incremented by the step value, `2`, is within the bounds defined by the end, `10`. \n",
    "- If it is, increment `V` and assign the program counter `pc` to be `3`, the `continu` line value. \n",
    "- If not, continue on to the following statement, line `50`.\n",
    "\n",
    "My implementation might not be officially correct in every detail, but it correctly runs all the examples in  [the manual](https://web.archive.org/web/20120716185629/http://www.bitsavers.org/pdf/dartmouth/BASIC_Oct64.pdf). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Execution: Printing\n",
    "\n",
    "We showed how to parse a `PRINT` statement with `labels_and_expressions()`; now it is time to execute a `PRINT` statement, printing each of the labels and expressions, and keeping track of what column to print at next, using the global variable `column`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [],
   "source": [
    "def basic_print(items) -> None: \n",
    "    \"\"\"Print the items (',' | ';' | \"label\" | expression) in appropriate columns.\"\"\"\n",
    "    for item in items:\n",
    "        if item == ',':      pad(15)\n",
    "        elif item == ';':    pad(3)\n",
    "        elif is_label(item): print_string(item.replace('\"', ''))\n",
    "        else:                print_string(f\"{evaluate(item):g} \")\n",
    "    if (not items) or items[-1] not in (',', ';'):\n",
    "        newline()\n",
    "        \n",
    "def print_string(s) -> None: \n",
    "    \"Print a string, keeping track of column, and advancing to newline if at or beyond column 100.\"\n",
    "    global column\n",
    "    print(s, end='')\n",
    "    column += len(s)\n",
    "    if column >= 100: \n",
    "        newline()\n",
    "        \n",
    "def pad(width) -> None: \n",
    "    \"Pad out to the column that is the next multiple of width.\"\n",
    "    while column % width != 0: \n",
    "        print_string(' ')\n",
    "\n",
    "def newline(): global column; print(); column = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Running the First Sample Program\n",
    "\n",
    "Let's re-examine, parse, and run our first sample program:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "10 REM POWER TABLE\n",
      "11 DATA 8, 4\n",
      "15 READ N0, P0\n",
      "20 PRINT \"N\",\n",
      "25 FOR P = 2 to P0\n",
      "30   PRINT \"N^\" P,\n",
      "35 NEXT P\n",
      "40 PRINT \"SUM\"\n",
      "45 LET S = 0\n",
      "50 FOR N = 2 TO N0\n",
      "55   PRINT N,\n",
      "60   FOR P = 2 TO P0\n",
      "65     LET S = S + N ^ P\n",
      "70     PRINT N ^ P,\n",
      "75   NEXT P\n",
      "80   PRINT S\n",
      "85 NEXT N\n",
      "99 END\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(program)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Stmt(num=10, typ='REM', args=[None]),\n",
       " Stmt(num=11, typ='DATA', args=[[8.0, 4.0]]),\n",
       " Stmt(num=15, typ='READ', args=[['N0', 'P0']]),\n",
       " Stmt(num=20, typ='PRINT', args=[['\"N\"', ',']]),\n",
       " Stmt(num=25, typ='FOR', args=['P', 2.0, 'P0', 1]),\n",
       " Stmt(num=30, typ='PRINT', args=[['\"N^\"', 'P', ',']]),\n",
       " Stmt(num=35, typ='NEXT', args=['P']),\n",
       " Stmt(num=40, typ='PRINT', args=[['\"SUM\"']]),\n",
       " Stmt(num=45, typ='LET', args=['S', 0.0]),\n",
       " Stmt(num=50, typ='FOR', args=['N', 2.0, 'N0', 1]),\n",
       " Stmt(num=55, typ='PRINT', args=[['N', ',']]),\n",
       " Stmt(num=60, typ='FOR', args=['P', 2.0, 'P0', 1]),\n",
       " Stmt(num=65, typ='LET', args=['S', Opcall(x='S', op='+', y=Opcall(x='N', op='^', y='P'))]),\n",
       " Stmt(num=70, typ='PRINT', args=[[Opcall(x='N', op='^', y='P'), ',']]),\n",
       " Stmt(num=75, typ='NEXT', args=['P']),\n",
       " Stmt(num=80, typ='PRINT', args=[['S']]),\n",
       " Stmt(num=85, typ='NEXT', args=['N']),\n",
       " Stmt(num=99, typ='END', args=[])]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parse(program)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "N              N^2            N^3            N^4            SUM\n",
      "2              4              8              16             28 \n",
      "3              9              27             81             145 \n",
      "4              16             64             256            481 \n",
      "5              25             125            625            1256 \n",
      "6              36             216            1296           2804 \n",
      "7              49             343            2401           5597 \n",
      "8              64             512            4096           10269 \n"
     ]
    }
   ],
   "source": [
    "run(program)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "# Running More Programs\n",
    "\n",
    "Rather than put together a suite of unit tests for `execute`, I'll run integration tests&mdash;additional whole programs. I've also added a few assertions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4              -5.5 \n",
      "0.666667       0.166667 \n",
      "-3.66667       3.83333 \n"
     ]
    }
   ],
   "source": [
    "# Linear equation solver (page 3 and 19 of the manual)\n",
    "\n",
    "run('''\n",
    "10 READ A1, A2, A3, A4\n",
    "15 LET D = A1 * A4 - A3 * A2\n",
    "20 IF D = 0 THEN 65\n",
    "30 READ B1, B2\n",
    "37   LET X1 = (B1*A4 - B2 * A2) / D\n",
    "42   LET X2 = ( A1 * B2 - A3 * B1)/D\n",
    "55   PRINT X1, X2\n",
    "60 GOTO 30\n",
    "65 PRINT \"NO UNIQUE SOLUTION\"\n",
    "70 DATA 1, 2, 4\n",
    "80 DATA 2, -7, 5\n",
    "85 DATA 1, 3, 4, -7\n",
    "90 END\n",
    "''')\n",
    "\n",
    "assert variables['D'] != 0\n",
    "assert variables['X1'] == -11/3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X VALUE        SINE           RESOLUTION\n",
      "1.6            0.999574       0.1 \n",
      "1.57           1              0.01 \n",
      "1.571          1              0.001 \n",
      "1.5708         1              0.0001 \n"
     ]
    }
   ],
   "source": [
    "# Find max(sin(x)) for 0 <= x <= 3 (page 25)\n",
    "\n",
    "run('''\n",
    "5 PRINT \"X VALUE\", \"SINE\", \"RESOLUTION\"\n",
    "10 READ D\n",
    "20   LET M = -1\n",
    "30   FOR X = 0 TO 3 STEP D\n",
    "40   IF SIN(X) <= M THEN 80\n",
    "50     LET X0 = X\n",
    "60     LET M = SIN(X)\n",
    "80   NEXT X\n",
    "85   PRINT X0, M, D\n",
    "90 GO TO 10\n",
    "95 DATA .1, .01, .001, .0001\n",
    "99 END\n",
    "''')\n",
    "\n",
    "assert abs(variables['X0'] - math.pi / 2) < 0.00001"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1              2              3              4              5              6              7         \n",
      "8              9              10             11             12             "
     ]
    }
   ],
   "source": [
    "# Printing (page 32)\n",
    "\n",
    "run('''\n",
    "10 FOR I = 1 TO 12\n",
    "20   PRINT I,\n",
    "30 NEXT I\n",
    "40 END''')\n",
    "\n",
    "assert variables['I'] == 12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "THIS PROGRAM COMPUTES AND PRINTS THE NTH POWERS\n",
      "OF THE NUMBERS LESS THAN OR EQUAL TO N FOR VARIOUS\n",
      "N FROM 1 TO 7\n",
      "\n",
      "N =   1  I^N:\n",
      "1              \n",
      "\n",
      "N =   2  I^N:\n",
      "1              4              \n",
      "\n",
      "N =   3  I^N:\n",
      "1              8              27             \n",
      "\n",
      "N =   4  I^N:\n",
      "1              16             81             256            \n",
      "\n",
      "N =   5  I^N:\n",
      "1              32             243            1024           3125           \n",
      "\n",
      "N =   6  I^N:\n",
      "1              64             729            4096           15625          46656          \n",
      "\n",
      "N =   7  I^N:\n",
      "1              128            2187           16384          78125          279936         823543    \n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Powers (page 33)\n",
    "\n",
    "run('''\n",
    " 5 PRINT \"THIS PROGRAM COMPUTES AND PRINTS THE NTH POWERS\"\n",
    " 6 PRINT \"OF THE NUMBERS LESS THAN OR EQUAL TO N FOR VARIOUS\"\n",
    " 7 PRINT \"N FROM 1 TO 7\"\n",
    " 8 PRINT\n",
    "10 FOR N = 1 TO 7\n",
    "15   PRINT \"N = \"; N; \"I^N:\"\n",
    "20   FOR I = 1 TO N\n",
    "30     PRINT I^N,\n",
    "40   NEXT I\n",
    "50   PRINT\n",
    "60   PRINT\n",
    "70 NEXT N\n",
    "80 END''')\n",
    "\n",
    "assert variables['N'] ** variables['I'] == 7 ** 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1  8  27 64 125   216   343   512   729   1000  1331  1728  2197  2744  3375  4096  4913  5832  6859 \n",
      "8000  9261  10648 12167 13824 15625 17576 19683 21952 24389 27000 29791 32768 35937 39304 42875 46656 \n",
      "50653 54872 59319 64000 68921 74088 79507 85184 91125 97336 103823   110592   117649   125000   132651 \n",
      "140608   148877   157464   166375   175616   185193   195112   205379   216000   226981   238328   250047 \n",
      "262144   274625   287496   300763   314432   328509   343000   357911   373248   389017   405224   421875 \n",
      "438976   456533   474552   493039   512000   531441   551368   571787   592704   614125   636056   658503 \n",
      "681472   704969   729000   753571   778688   804357   830584   857375   884736   912673   941192   970299 \n",
      "1e+06 "
     ]
    }
   ],
   "source": [
    "# Cubes (page 35)\n",
    "\n",
    "run('''\n",
    "10 FOR I = 1 TO 100\n",
    "20   PRINT I*I*I;\n",
    "30 NEXT I\n",
    "40 END\n",
    "''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10000 9604  9216  8836  8464  8100  7744  7396  7056  6724  6400  6084  5776  5476  5184  4900  4624 \n",
      "4356  4096  3844  3600  3364  3136  2916  2704  2500  2304  2116  1936  1764  1600  1444  1296  1156 \n",
      "1024  900   784   676   576   484   400   324   256   196   144   100   64 36 16 4  0  "
     ]
    }
   ],
   "source": [
    "# Squares (variant of page 35 program, designed to test negative STEP)\n",
    "\n",
    "run('''\n",
    "10 FOR I = 100 TO 0 STEP -2\n",
    "20   PRINT I*I;\n",
    "30 NEXT I\n",
    "''')\n",
    "\n",
    "assert variables['I'] == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TOTAL SALES FOR SALESMAN1     $180.5 \n",
      "TOTAL SALES FOR SALESMAN2     $211.3 \n",
      "TOTAL SALES FOR SALESMAN3     $131.65 \n",
      "TOTAL SALES FOR SALESMAN4     $166.55 \n",
      "TOTAL SALES FOR SALESMAN5     $169.4 \n"
     ]
    }
   ],
   "source": [
    "# Sales ledger (page 37; cleaned up a bit)\n",
    "\n",
    "run('''\n",
    "10  FOR I = 1 TO 3\n",
    "20    READ P(I)\n",
    "30  NEXT I\n",
    "40  FOR I = 1 TO 3\n",
    "50    FOR J = 1 TO 5\n",
    "60      READ S(I, J)\n",
    "70    NEXT J\n",
    "80  NEXT I\n",
    "90  FOR J = 1 TO 5\n",
    "100   LET S = 0\n",
    "110   FOR I = 1 TO 3\n",
    "120     LET S = S + P(I) * S(I, J)\n",
    "130   NEXT I\n",
    "140   PRINT \"TOTAL SALES FOR SALESMAN\"J, \"$\"S\n",
    "150 NEXT J\n",
    "190 DIM S(3, 5)\n",
    "200 DATA 1.25, 4.30, 2.50\n",
    "210 DATA 40, 20, 37, 29, 42\n",
    "220 DATA 10, 16, 3, 21, 8\n",
    "230 DATA 35, 47, 29, 16, 33\n",
    "300 END\n",
    "''')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can look at the variables that have been stored for this program:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defaultdict(float,\n",
       "            {'I': 3.0,\n",
       "             ('P', 1.0): 1.25,\n",
       "             ('P', 2.0): 4.3,\n",
       "             ('P', 3.0): 2.5,\n",
       "             'J': 5.0,\n",
       "             ('S', 1.0, 1.0): 40.0,\n",
       "             ('S', 1.0, 2.0): 20.0,\n",
       "             ('S', 1.0, 3.0): 37.0,\n",
       "             ('S', 1.0, 4.0): 29.0,\n",
       "             ('S', 1.0, 5.0): 42.0,\n",
       "             ('S', 2.0, 1.0): 10.0,\n",
       "             ('S', 2.0, 2.0): 16.0,\n",
       "             ('S', 2.0, 3.0): 3.0,\n",
       "             ('S', 2.0, 4.0): 21.0,\n",
       "             ('S', 2.0, 5.0): 8.0,\n",
       "             ('S', 3.0, 1.0): 35.0,\n",
       "             ('S', 3.0, 2.0): 47.0,\n",
       "             ('S', 3.0, 3.0): 29.0,\n",
       "             ('S', 3.0, 4.0): 16.0,\n",
       "             ('S', 3.0, 5.0): 33.0,\n",
       "             'S': 169.4})"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "variables"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8  5  6  5  2  4  8  4  6  0  8  3  5  8  8  4  7  7  0  3  3  7  9  0  5  5  2  8  5  7  2  3  9  1 \n",
      "9  3  1  7  7  6  1  4  7  7  5  7  0  9  9  3  0  8  0  4  2  4  9  4  1  7  8  8  6  9  0  7  7  5 \n",
      "4  7  7  6  0  7  0  9  8  0  8  7  3  5  9  7  0  1  3  2  5  5  8  7  0  0  3  0  2  1  8  8  "
     ]
    }
   ],
   "source": [
    "# Random number generator (page 40)\n",
    "\n",
    "run('''\n",
    "10 FOR I = 1 TO 100\n",
    "20   PRINT INT(10 * RND(X));\n",
    "30 NEXT I\n",
    "40 END\n",
    "''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "D  SIN(D)      COS(D)         SIN(D)^2 + COS(D)^2\n",
      "0  0           1              1 \n",
      "15 0.258819    0.965926       1 \n",
      "30 0.5         0.866025       1 \n",
      "45 0.707107    0.707107       1 \n",
      "60 0.866025    0.5            1 \n",
      "75 0.965926    0.258819       1 \n",
      "90 1           1.61554e-15    1 \n"
     ]
    }
   ],
   "source": [
    "# DEF example: table of SIN(X) and COS(X) in degrees (page 41, expanded some)\n",
    "\n",
    "run('''\n",
    " 5 PRINT \"D\"; \"SIN(D)\", \"COS(D)\", \"SIN(D)^2 + COS(D)^2\"\n",
    "20 LET P1 = 3.14159265358979 / 180\n",
    "30 FOR X = 0 TO 90 STEP 15\n",
    "40   PRINT X; FNS(X), FNC(X), FNS(X)^2 + FNC(X)^2\n",
    "50 NEXT X\n",
    "97 DEF FNS(D) = SIN(D * P1)\n",
    "98 DEF FNC(D) = COS(D * P1)\n",
    "99 END\n",
    "''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9              27             120 \n",
      "25             125            780 \n",
      "Z = 2615 \n"
     ]
    }
   ],
   "source": [
    "# GOSUB example (page 43)\n",
    "\n",
    "run('''\n",
    "100 LET X = 3\n",
    "110 GOSUB 400\n",
    "120 PRINT U, V, W\n",
    "200 LET X = 5\n",
    "210 GOSUB 400\n",
    "215 PRINT U, V, W\n",
    "220 LET Z = U + 2*V + 3*W\n",
    "230 PRINT \"Z = \" Z\n",
    "240 STOP\n",
    "400 LET U = X*X\n",
    "410 LET V = X*X*X\n",
    "420 LET W = X*X*X*X + X*X*X + X*X + X\n",
    "430 RETURN\n",
    "440 END\n",
    "''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SUM = 21 \n"
     ]
    }
   ],
   "source": [
    "# Sum of non-negative multiples of 0.1 less than or equal to 2, two ways (page 47)\n",
    "\n",
    "run('''\n",
    " 5 LET S = 0\n",
    "10 LET N = 0\n",
    "20 LET S = S + N/10\n",
    "30   IF N >= 20 THEN 60\n",
    "40   LET N = N + 1\n",
    "50 GOTO 20\n",
    "60 PRINT \"SUM = \" S\n",
    "70 END\n",
    "''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SUM = 21 \n"
     ]
    }
   ],
   "source": [
    "run('''\n",
    "20 FOR N = 1 TO 20\n",
    "40   LET S = S + N/10\n",
    "50 NEXT N\n",
    "60 PRINT \"SUM = \"  S\n",
    "70 END\n",
    "''')\n",
    "\n",
    "assert variables['S'] == sum(N/10 for N in range(1, 21))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Checking for Syntax Errors\n",
    "\n",
    "Here we show a collection of syntax errors, and the messages they generate:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Error in line '1 X = 1' at 'X = 1': unknown statement type\n",
      "Error in line '2 GO TO JAIL' at 'J A I L': missing line number\n",
      "Error in line '3 FOR I = 1 ' at '': expected 'TO'\n",
      "Error in line '4 IF X > 0 & X < 10 GOTO 999' at '& X < 10 GOTO 999': expected 'THEN'\n",
      "Error in line '5 LET Z = (Z + 1' at '': expected \")\" to end expression\n",
      "Error in line '6 PRINT \"OH CANADA\", EH?' at '?': unknown expression\n",
      "Error in line '7 LET Z = +3' at '+ 3': unknown expression\n",
      "Error in line '8 LET X = Y ** 2' at '* 2': unknown expression\n",
      "Error in line '9 LET A(I = 1' at '= 1': expected \")\" to close subscript\n",
      "Error in line '10 IF A = 0 THEN 900 + 99' at '+ 99': extra TOKENS at end of line\n",
      "Error in line '11 NEXT A(I)' at '( I )': extra TOKENS at end of line\n",
      "Error in line '12 DEF F(X) = X ^ 2 + 1' at 'F ( X ) = X ^ 2 + 1': expected a function name\n",
      "Error in line '13 IF X != 0 THEN 999' at '! = 0 THEN 999': expected a relational operator\n",
      "Error in line '14 DEF FNS(X + 2*P1) = SIN(X)' at '+ 2 * P1 ) = SIN ( X )': expected ')'\n",
      "Error in line '15 DEF FNY(M, B) = M * X + B' at ', B ) = M * X + B': expected ')'\n",
      "Error in line '16 LET 3 = X' at '3 = X': expected a variable name\n",
      "Error in line '17 LET SIN = 7 * DEADLY' at 'SIN = 7 * D E A D L Y': expected a variable name\n",
      "Error in line '18 LET X = A-1(I)' at '( I )': extra TOKENS at end of line\n",
      "Error in line '19 FOR SCORE + 7' at 'C O R E + 7': expected '='\n",
      "Error in line '20 STOP IN NAME(LOVE)' at 'I N N A M E ( L O V E )': extra TOKENS at end of line\n",
      "Error in line '26 ENDURANCE.' at 'U R A N C E .': extra TOKENS at end of line\n",
      "NO ERROR IN LINE 27 DESPITE THE ERRORS ABOVE\n"
     ]
    }
   ],
   "source": [
    "run('''\n",
    "1 X = 1\n",
    "2 GO TO JAIL\n",
    "3 FOR I = 1 \n",
    "4 IF X > 0 & X < 10 GOTO 999\n",
    "5 LET Z = (Z + 1\n",
    "6 PRINT \"OH CANADA\", EH?\n",
    "7 LET Z = +3\n",
    "8 LET X = Y ** 2\n",
    "9 LET A(I = 1\n",
    "10 IF A = 0 THEN 900 + 99\n",
    "11 NEXT A(I)\n",
    "12 DEF F(X) = X ^ 2 + 1\n",
    "13 IF X != 0 THEN 999\n",
    "14 DEF FNS(X + 2*P1) = SIN(X)\n",
    "15 DEF FNY(M, B) = M * X + B\n",
    "16 LET 3 = X\n",
    "17 LET SIN = 7 * DEADLY\n",
    "18 LET X = A-1(I)\n",
    "19 FOR SCORE + 7\n",
    "20 STOP IN NAME(LOVE)\n",
    "21 REMARKABLY, THE INTERPRETER\n",
    "22 REMEDIES THE ERRORS, AND THE PROPGRAM\n",
    "23 REMAINS AN EXECUTABLE ENTITY, UN-\n",
    "24 REMITTENTLY RUNNING, WITH NO\n",
    "25 REMORSE OR REGRETS, AND WITH GREAT\n",
    "26 ENDURANCE.\n",
    "27 PRINT \"No error in line \" 3 ^ 3 \"despite the errors above\"\n",
    "''')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Longer Program: Life\n",
    "\n",
    "Now for a final, slightly more complicated example: Conway's Game of [Life](https://en.wikipedia.org/wiki/Conway's_Game_of_Life). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "GEN 0 \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  O  .  .  .  .  .  .  .  \n",
      ".  .  O  .  .  O  O  .  .  .  \n",
      ".  .  O  .  .  O  O  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      "GEN 1 \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  O  O  O  .  O  O  .  .  .  \n",
      ".  .  .  .  .  O  O  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      "GEN 2 \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  O  .  .  .  .  .  .  .  \n",
      ".  .  O  .  O  O  O  .  .  .  \n",
      ".  .  O  .  O  O  O  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      "GEN 3 \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  O  .  O  .  .  .  .  \n",
      ".  O  O  .  O  .  O  .  .  .  \n",
      ".  .  .  .  O  .  O  .  .  .  \n",
      ".  .  .  .  .  O  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      "GEN 4 \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  O  O  O  O  .  .  .  .  \n",
      ".  .  O  .  O  .  O  .  .  .  \n",
      ".  .  .  O  O  .  O  .  .  .  \n",
      ".  .  .  .  .  O  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      "GEN 5 \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  O  O  .  .  .  .  .  \n",
      ".  .  O  .  O  O  .  .  .  .  \n",
      ".  .  O  .  .  .  O  .  .  .  \n",
      ".  .  .  O  O  .  O  .  .  .  \n",
      ".  .  .  .  O  O  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      "GEN 6 \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  O  O  O  .  .  .  .  \n",
      ".  .  O  .  O  O  .  .  .  .  \n",
      ".  .  O  .  .  .  O  .  .  .  \n",
      ".  .  .  O  O  .  O  .  .  .  \n",
      ".  .  .  O  O  O  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      "GEN 7 \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  O  .  .  .  .  .  \n",
      ".  .  .  O  .  O  .  .  .  .  \n",
      ".  .  O  .  .  .  O  .  .  .  \n",
      ".  .  O  .  .  .  O  .  .  .  \n",
      ".  .  O  .  .  .  O  .  .  .  \n",
      ".  .  .  O  .  O  .  .  .  .  \n",
      ".  .  .  .  O  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      "GEN 8 \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  O  .  .  .  .  .  \n",
      ".  .  .  O  O  O  .  .  .  .  \n",
      ".  .  O  O  .  O  O  .  .  .  \n",
      ".  O  O  O  .  O  O  O  .  .  \n",
      ".  .  O  O  .  O  O  .  .  .  \n",
      ".  .  .  O  O  O  .  .  .  .  \n",
      ".  .  .  .  O  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      "GEN 9 \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  O  O  O  .  .  .  .  \n",
      ".  .  O  .  .  .  O  .  .  .  \n",
      ".  O  .  .  .  .  .  O  .  .  \n",
      ".  O  .  .  .  .  .  O  .  .  \n",
      ".  O  .  .  .  .  .  O  .  .  \n",
      ".  .  O  .  .  .  O  .  .  .  \n",
      ".  .  .  O  O  O  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n",
      "GEN 10 \n",
      ".  .  .  .  O  .  .  .  .  .  \n",
      ".  .  .  O  O  O  .  .  .  .  \n",
      ".  .  O  O  O  O  O  .  .  .  \n",
      ".  O  O  .  .  .  O  O  .  .  \n",
      "O  O  O  .  .  .  O  O  O  .  \n",
      ".  O  O  .  .  .  O  O  .  .  \n",
      ".  .  O  O  O  O  O  .  .  .  \n",
      ".  .  .  O  O  O  .  .  .  .  \n",
      ".  .  .  .  O  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  \n"
     ]
    }
   ],
   "source": [
    "run('''\n",
    "100 REM CONWAY'S GAME OF LIFE\n",
    "\n",
    "102 REM G IS NUMBER OF GENERATIONS, \n",
    "104 REM M IS MATRIX SIZE (M X M)\n",
    "106 REM L(SELF, NEIGHBORS_ALIVE) IS 1 IFF CELL WITH THOSE COUNTS LIVES\n",
    "108 REM A(X, Y) IS 1 IFF CELL AT (X, Y) IS LIVE\n",
    "110 REM B(X, Y) GETS THE NEXT GENERATION\n",
    "\n",
    "120 READ G,      M,      L(0,3), L(1,3), L(1,2)\n",
    "121 DATA 10,     10,     1,      1,      1\n",
    "130 READ A(3,4), A(3,5), A(3,6), A(6,5), A(6,6), A(7,5), A(7,6)\n",
    "131 DATA 1,      1,      1,      1,      1,      1,      1\n",
    "\n",
    "150 REM MAIN LOOP: PRINT, THEN REPEAT G TIMES: UPDATE / COPY / PRINT\n",
    "155 LET I = 0\n",
    "160 GOSUB 700\n",
    "170 FOR I = 1 TO G\n",
    "180   GOSUB 300\n",
    "190   GOSUB 500\n",
    "200   GOSUB 700\n",
    "210 NEXT I\n",
    "220 STOP\n",
    "\n",
    "300 REM ========== UPDATE B = NEXT_GEN(A)\n",
    "310 FOR Y = 1 TO M\n",
    "320   FOR X = 1 TO M\n",
    "325     LET N = A(X-1,Y)+A(X+1,Y)+A(X,Y-1)+A(X,Y+1)+A(X-1,Y-1)+A(X+1,Y+1)+A(X-1,Y+1)+A(X+1,Y-1)\n",
    "330     LET B(X, Y) = L(A(X, Y), N)\n",
    "340   NEXT X\n",
    "350 NEXT Y\n",
    "360 RETURN\n",
    "\n",
    "500 REM ========== COPY A = B\n",
    "510 FOR Y = 1 TO M\n",
    "520   FOR X = 1 TO M\n",
    "530     LET A(X, Y) = B(X, Y)\n",
    "540   NEXT X\n",
    "550 NEXT Y\n",
    "560 RETURN\n",
    "\n",
    "700 REM ========== PRINT A\n",
    "705 PRINT \"GEN \" I\n",
    "710 FOR Y = 1 TO M\n",
    "720   FOR X = 1 TO M\n",
    "730     IF A(X, Y) = 1 THEN 760\n",
    "740       PRINT \".\";\n",
    "750       GOTO 770\n",
    "760     PRINT \"O\";\n",
    "770   NEXT X\n",
    "780   PRINT\n",
    "790 NEXT Y\n",
    "795 RETURN\n",
    "\n",
    "999 END \n",
    "''')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Actually, this was an assignment in my high school BASIC class. (We used a [slightly different](https://www.grc.com/pdp-8/docs/os8_basic_reference.pdf) version of BASIC.) Back then, output was on [rolls of paper](https://en.wikipedia.org/wiki/Teletype_Corporation#/media/File:Teletype_with_papertape_punch_and_reader.jpg), and I thought it was wasteful to print only one generation per line. So I arranged to print multiple generations on the same line, storing them until it was time to print them out. But BASIC doesn't have three-dimensional arrays, so I needed to store several generations worth of data in one `A(X, Y)` value. Today, I know that that could be done by allocating one bit for each generation, but back then I don't think I knew about binary representation, so I stored one generation in each decimal digit. That means I no longer need two matrixes, `A` and `B`; instead, the current generation will always be the value in the one's place, the previous generation in the ten's place, and the one before that in the hundred's place."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false,
    "jupyter": {
     "outputs_hidden": false
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "GEN 0                            GEN 1                            GEN 2 \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  \n",
      ".  .  O  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  O  .  .  .  .  .  .  .  \n",
      ".  .  O  .  .  O  O  .  .  .  |  .  O  O  O  .  O  O  .  .  .  |  .  .  O  .  O  O  O  .  .  .  \n",
      ".  .  O  .  .  O  O  .  .  .  |  .  .  .  .  .  O  O  .  .  .  |  .  .  O  .  O  O  O  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  \n",
      "GEN 3                            GEN 4                            GEN 5 \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  O  O  .  .  .  .  .  \n",
      ".  .  .  O  .  O  .  .  .  .  |  .  .  O  O  O  O  .  .  .  .  |  .  .  O  .  O  O  .  .  .  .  \n",
      ".  O  O  .  O  .  O  .  .  .  |  .  .  O  .  O  .  O  .  .  .  |  .  .  O  .  .  .  O  .  .  .  \n",
      ".  .  .  .  O  .  O  .  .  .  |  .  .  .  O  O  .  O  .  .  .  |  .  .  .  O  O  .  O  .  .  .  \n",
      ".  .  .  .  .  O  .  .  .  .  |  .  .  .  .  .  O  .  .  .  .  |  .  .  .  .  O  O  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  \n",
      "GEN 6                            GEN 7                            GEN 8 \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  O  .  .  .  .  .  |  .  .  .  .  O  .  .  .  .  .  \n",
      ".  .  .  O  O  O  .  .  .  .  |  .  .  .  O  .  O  .  .  .  .  |  .  .  .  O  O  O  .  .  .  .  \n",
      ".  .  O  .  O  O  .  .  .  .  |  .  .  O  .  .  .  O  .  .  .  |  .  .  O  O  .  O  O  .  .  .  \n",
      ".  .  O  .  .  .  O  .  .  .  |  .  .  O  .  .  .  O  .  .  .  |  .  O  O  O  .  O  O  O  .  .  \n",
      ".  .  .  O  O  .  O  .  .  .  |  .  .  O  .  .  .  O  .  .  .  |  .  .  O  O  .  O  O  .  .  .  \n",
      ".  .  .  O  O  O  .  .  .  .  |  .  .  .  O  .  O  .  .  .  .  |  .  .  .  O  O  O  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  O  .  .  .  .  .  |  .  .  .  .  O  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  \n",
      "GEN 9                            GEN 10                           GEN 11 \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  O  .  .  .  .  .  |  .  .  .  O  O  O  .  .  .  .  \n",
      ".  .  .  O  O  O  .  .  .  .  |  .  .  .  O  O  O  .  .  .  .  |  .  .  O  .  .  .  O  .  .  .  \n",
      ".  .  O  .  .  .  O  .  .  .  |  .  .  O  O  O  O  O  .  .  .  |  .  O  .  .  .  .  .  O  .  .  \n",
      ".  O  .  .  .  .  .  O  .  .  |  .  O  O  .  .  .  O  O  .  .  |  O  .  .  .  O  .  .  .  O  .  \n",
      ".  O  .  .  .  .  .  O  .  .  |  O  O  O  .  .  .  O  O  O  .  |  O  .  .  O  .  O  .  .  O  .  \n",
      ".  O  .  .  .  .  .  O  .  .  |  .  O  O  .  .  .  O  O  .  .  |  O  .  .  .  O  .  .  .  O  .  \n",
      ".  .  O  .  .  .  O  .  .  .  |  .  .  O  O  O  O  O  .  .  .  |  .  O  .  .  .  .  .  O  .  .  \n",
      ".  .  .  O  O  O  .  .  .  .  |  .  .  .  O  O  O  .  .  .  .  |  .  .  O  .  .  .  O  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  O  .  .  .  .  .  |  .  .  .  O  O  O  .  .  .  .  \n",
      ".  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  |  .  .  .  .  .  .  .  .  .  .  \n"
     ]
    }
   ],
   "source": [
    "run('''\n",
    "100 REM CONWAY'S GAME OF LIFE\n",
    "\n",
    "102 REM G IS NUMBER OF GENERATIONS, \n",
    "104 REM M IS MATRIX SIZE (M X M)\n",
    "106 REM L(SELF, NEIGHBORS_ALIVE) IS 1 IFF CELL WITH THOSE COUNTS LIVES\n",
    "108 REM A(X, Y) STORES THE HISTORY OF THE CELL AT (X, Y); 1 MEANS LIVE,\n",
    "110 REM BUT WE STORE SEVERAL GENERATIONS: A(X, Y) = 100 MEANS THE CELL\n",
    "112 REM IS DEAD IN THE CURRENT AND PREVIOUS GENERATION (00), BUT LIVE IN THE\n",
    "114 REM GENERATION BEFORE THAT (1). WE STORE MULTIPLE GENERATIONS SO THAT\n",
    "116 REM WE CAN PRINT THEM OUT ON ONE LINE, SAVING SPACE/PAPER.\n",
    "\n",
    "120 READ G,      M,      L(0,3), L(1,3), L(1,2)\n",
    "122 DATA 11,     10,     1,      1,      1\n",
    "124 READ A(3,4), A(3,5), A(3,6), A(6,5), A(6,6), A(7,5), A(7,6)\n",
    "126 DATA 1,      1,      1,      1,      1,      1,      1\n",
    "\n",
    "130 REM FNA(N) = THE PREVIOUS GENERATION'S VALUE\n",
    "132 DEF FNA(N) = INT(N  / 10) % 10\n",
    "\n",
    "134 REM FNC(N) = THE GENERATION IN COLUMN C; FNC(123) = C FOR EACH C IN 1..3\n",
    "136 DEF FNC(N) = FNA(N / (10 ^ (2 - C)))\n",
    "\n",
    "150 REM MAIN LOOP: DO 3 UPDATES (2 FIRST TIME), THEN PRINT AND SHIFT\n",
    "160 FOR I = 1 TO G\n",
    "170   GOSUB 300\n",
    "175   IF I % 3 <> 2 THEN 200\n",
    "180     GOSUB 700\n",
    "190     GOSUB 800\n",
    "200 NEXT I\n",
    "210 STOP\n",
    "\n",
    "300 REM ========== UPDATE A: SHIFT OLD GENS LEFT; ADD IN NEW GEN\n",
    "310 FOR Y = 1 TO M\n",
    "320   FOR X = 1 TO M \n",
    "330     LET A(X, Y) = 10 * A(X, Y)\n",
    "340   NEXT X\n",
    "350 NEXT Y\n",
    "360 FOR Y = 1 TO M\n",
    "370   FOR X = 1 TO M \n",
    "380     LET N1 = FNA(A(X+1,Y-1)) + FNA(A(X+1,Y)) + FNA(A(X+1,Y+1)) + FNA(A(X,Y-1))\n",
    "390     LET N2 = FNA(A(X-1,Y-1)) + FNA(A(X-1,Y)) + FNA(A(X-1,Y+1)) + FNA(A(X,Y+1))\n",
    "400     LET S  = FNA(A(X, Y))\n",
    "410     LET A(X, Y) = A(X, Y) + L(S, N1 + N2)\n",
    "420   NEXT X\n",
    "430 NEXT Y\n",
    "440 RETURN\n",
    "\n",
    "700 REM ========== PRINT A (3 GENERATIONS ACROSS THE PAGE)\n",
    "705 PRINT \"GEN \" I-2, \" \", \"   GEN \" I-1, \" \", \"      GEN \" I\n",
    "710 FOR Y = 1 TO M\n",
    "715   FOR C = 1 TO 3\n",
    "720     FOR X = 1 TO M\n",
    "730       IF FNC(A(X, Y)) = 1 THEN 760\n",
    "740         PRINT \".\";\n",
    "750         GOTO 770\n",
    "760       PRINT \"O\";\n",
    "770     NEXT X\n",
    "772     IF C = 3 THEN 777\n",
    "775       PRINT \"|\";\n",
    "777   NEXT C\n",
    "780   PRINT\n",
    "790 NEXT Y\n",
    "795 RETURN\n",
    "\n",
    "800 REM ========== FORGET ALL BUT THE MOST RECENT GENERATION IN A\n",
    "810 FOR Y = 1 TO M\n",
    "820   FOR X = 1 TO M\n",
    "830     LET A(X, Y) = A(X, Y) % 10\n",
    "840   NEXT X\n",
    "850 NEXT Y\n",
    "860 RETURN\n",
    "\n",
    "999 END \n",
    "''')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}