{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "
Peter Norvig, Feb 2017
\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`** `` **=** ``\n", "- **`READ`** ``\n", "- **`DATA`** ``\n", "- **`PRINT`** ``\n", "- **`GOTO`** ``\n", "- **`IF`** ` ` **`THEN`** ``\n", "- **`FOR`** `` **=** `` **`TO`** ` [`**`STEP`** ` ]`\n", "- **`NEXT`** ``\n", "- **`END`**\n", "- **`STOP`**\n", "- **`DEF`** `` **(** `` **)** **=** ``\n", "- **`GOSUB`** ``\n", "- **`RETURN`**\n", "- **`DIM`** ``\n", "- **`REM`** ``\n", " \n", "The notation `` means any variable and `` means zero or more variables, separated by commas. `[`**`STEP`** ` ]` 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 \"\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—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", "
Prints the value of `X` in column 0 and `Y` in column 15. Advances to new line.\n", "\n", "* `20 PRINT \"X =\", X`\n", "
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", "
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", "
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).
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).
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—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 }