# Peter Norvig's BASIC interpreter in Python
# https://hub.mybinder.org/user/norvig-pytudes-c0nib49y/notebooks/ipynb/BASIC.ipynb
# Licensed under MIT as is the rest of norvig/pytudes (https://github.com/norvig/pytudes/blob/master/LICENSE)

import re

tokenize = re.compile(r'''
    \d* \.? \d+ (?: E -? \d+)?                     | # number 
    SIN|COS|TAN|ATN|EXP|ABS|LOG|SQR|RND|INT|FN[A-Z]| # functions
    LET|READ|DATA|PRINT|GOTO|IF|FOR|NEXT|END       | # keywords
    DEF|GOSUB|RETURN|DIM|REM|TO|THEN|STEP|STOP     | # keywords
    [A-Z]\d? | # variable names (letter + optional digit)
    ".*?"    | # labels (strings in double quotes)
    <>|>=|<= | # multi-character relational operators
    \S         # any non-space single character ''', 
    re.VERBOSE).findall

tokens = [] # Global variable to hold a list of tokens

def tokenizer(line):
    "Return a list of the tokens on this line, handling spaces properly, and upper-casing."
    line = ''.join(tokenize(line)) # Remove whitespace
    return tokenize(line.upper())

def peek(): 
    "Return the first token in the global `tokens`, or None if we are at the end of the line."
    return (tokens[0] if tokens else None)

def pop(constraint=None):
    """Remove and return the first token in `tokens`, or return None if token fails constraint.
    constraint can be None, a literal (e.g. pop('=')), or a predicate (e.g. pop(is_varname))."""
    top = peek()
    if constraint is None or (top == constraint) or (callable(constraint) and constraint(top)):
        return tokens.pop(0)
    
def remove_spaces(line): 
    "Remove white space from line, except space inside double quotes."
    return 

def lines(text): 
    "A list of the non-empty lines in a text."
    return [line for line in text.splitlines() if line]

def Grammar(): 
    return {
    'LET':    [variable, '=', expression],
    'READ':   [list_of(variable)],
    'DATA':   [list_of(number)],
    'PRINT':  [labels_and_expressions],
    'GOTO':   [linenumber],
    'IF':     [expression, relational, expression, 'THEN', linenumber],
    'FOR':    [varname, '=', expression, 'TO', expression, step],
    'NEXT':   [varname],
    'END':    [],
    'STOP':   [],
    'DEF':    [funcname, '(', varname, ')', '=', expression],
    'GOSUB':  [linenumber],
    'RETURN': [],
    'DIM':    [list_of(variable)], 
    'REM':    [anycharacters],
    'A':    []
    }

def statement():
    "Parse a BASIC statement from `tokens`."
    num  = linenumber()
    typ  = pop(is_stmt_type) or fail('unknown statement type')
    args = []
    for p in grammar[typ]: # For each part of rule, call if callable or match if literal string
        if callable(p):
            args.append(p())
        else:
            pop(p) or fail('expected ' + repr(p))
    return Stmt(num, typ, args)

def number():        return (-1 if pop('-') else +1) * float(pop()) # Optional minus sign
def step():          return (expression() if pop('STEP') else 1)    # 1 is the default step
def linenumber():    return (int(pop()) if peek().isnumeric() else fail('missing line number'))
def relational():    return pop(is_relational) or fail('expected a relational operator')
def varname():       return pop(is_varname)    or fail('expected a variable name')
def funcname():      return pop(is_funcname)   or fail('expected a function name')
def anycharacters(): tokens.clear() # Ignore tokens in a REM statement

def is_stmt_type(x):  return is_str(x) and x in grammar # LET, READ, ...
def is_funcname(x):   return is_str(x) and len(x) == 3 and x.isalpha()  # SIN, COS, FNA, FNB, ...
def is_varname(x):    return is_str(x) and len(x) in (1, 2) and x[0].isalpha() # A, A1, A2, B, ...
def is_label(x):      return is_str(x) and x.startswith('"') # "HELLO WORLD", ...
def is_relational(x): return is_str(x) and x in ('<', '=', '>', '<=', '<>', '>=')
def is_number(x):     return is_str(x) and x and x[0] in '.0123456789' # '3', '.14', ...

def is_str(x):        return isinstance(x, str)
def variable(): 
    "Parse a possibly subscripted variable e.g. 'X3' or 'A(I)' or 'M(2*I, 3)'."
    V = varname()
    if pop('('):
        indexes = list_of(expression)()
        pop(')') or fail('expected ")" to close subscript')
        return Subscript(V, indexes) # E.g. 'A(I)' => Subscript('A', ['I'])
    else: 
        return V                     # E.g. 'X3' 
class list_of:
    "list_of(category) is a callable that parses a comma-separated list of <category>"
    def __init__(self, category): self.category = category
    def __call__(self):
        result = ([self.category()] if tokens else [])
        while pop(','):
            result.append(self.category())
        return result
def parse(program): return sorted(parse_line(line) for line in lines(program))
def parse_line(line):
    "Return a Stmt(linenumber, statement_type, arguments)."
    global tokens
    tokens = tokenizer(line)
    try:
        stmt = statement()
        if tokens: fail('extra tokens at end of line')
        return stmt
    except SyntaxError as err:
        print("Error in line '{}' at '{}': {}".format(line, ' '.join(tokens), err))
        return Stmt(0, 'REM', []) # Return dummy statement
        
def fail(message): raise SyntaxError(message)
  
from collections import namedtuple, defaultdict, deque

Stmt      = namedtuple('Stmt',      'num, typ, args')     # '1 GOTO 9' => Stmt(1, 'GOTO', 9)
Subscript = namedtuple('Subscript', 'var, indexes')       # 'A(I)'     => Subscript('A', ['I'])
Funcall   = namedtuple('Funcall',   'f, x')               # 'SQR(X)'   => Funcall('SQR', 'X')
Opcall    = namedtuple('Opcall',    'x, op, y')           # 'X + 1'    => Opcall('X', '+', 1)
ForState  = namedtuple('ForState',  'continu, end, step') # Data for FOR loop 

class Function(namedtuple('_', 'parm, body')):
    "User-defined function; 'DEF FNC(X) = X ^ 3' => Function('X', Opcall('X', '^', 3))"
    def __call__(self, value):                           
        variables[self.parm] = value # Global assignment to the parameter
        return evalu(self.body)
def labels_and_expressions():
    "Parse a sequence of label / comma / semicolon / expression (for PRINT statement)."
    result = []
    while tokens:
        item = pop(is_label) or pop(',') or pop(';') or expression()
        result.append(item)
    return result
def expression(prec=1): 
    "Parse an expression: a primary and any [op expression]* pairs with precedence(op) >= prec."
    exp = primary()                         # 'A' => 'A'
    while precedence(peek()) >= prec:
        op = pop()
        rhs = expression(precedence(op) + associativity(op))
        exp = Opcall(exp, op, rhs)          # 'A + B' => Opcall('A', '+', 'B')
    return exp

def primary():
    "Parse a primary expression (no infix op except maybe within parens)."
    if is_number(peek()):                   # '1.23' => 1.23 
        return number()
    elif is_varname(peek()):                # X or A(I) or M(I+1, J)
        return variable()
    elif is_funcname(peek()):               # SIN(X) => Funcall('SIN', 'X')
        return Funcall(pop(), primary())
    elif pop('-'):                          # '-X' => Funcall('NEG', 'X')
        return Funcall('NEG', primary())
    elif pop('('):                          # '(X)' => 'X'
        exp = expression()
        pop(')') or fail('expected ")" to end expression')
        return exp
    else:
        return fail('unknown expression')

def precedence(op): 
    return (3 if op == '^' else 2 if op in ('*', '/', '%') else 1 if op in ('+', '-') else 0)

def associativity(op): 
    return (0 if op == '^' else 1)
grammar = Grammar()
def run(program): execute(parse(program))
def execute(stmts): 
    "Parse and execute the BASIC program."
    global variables, functions, column
    functions, data = preprocess(stmts) # {name: function,...}, deque[number,...]
    variables = defaultdict(float) # mapping of {variable: value}, default 0.0
    column    = 0                  # column to PRINT in next
    pc        = 0                  # program counter
    ret       = 0                  # index (pc) that a GOSUB returns to
    fors      = {}                 # runtime map of {varname: ForState(...)}
    goto      = {stmt.num: i       # map of {linenumber: index}
                 for (i, stmt) in enumerate(stmts)}
    while pc < len(stmts):
        (_, typ, args) = stmts[pc] # Fetch and decode the instruction
        pc += 1                    # Increment the program counter
        if typ in ('END', 'STOP') or (typ == 'READ' and not data): 
            return
        elif typ == 'LET':
            V, exp = args
            let(V, evalu(exp))
        elif typ == 'READ':
            for V in args[0]:
                let(V, data.popleft())
        elif typ == 'PRINT':
            basic_print(args[0])
        elif typ == 'GOTO':
            pc = goto[args[0]]
        elif typ == 'IF':
            lhs, relational, rhs, dest = args
            if functions[relational](evalu(lhs), evalu(rhs)):
                pc = goto[dest]
        elif typ == 'FOR':
            V, start, end, step = args
            variables[V] = evalu(start)
            fors[V] = ForState(pc, evalu(end), evalu(step))
        elif typ == 'NEXT':
            V = args[0]
            continu, end, step = fors[V]
            if ((step >= 0 and variables[V] + step <= end) or
                (step <  0 and variables[V] + step >= end)):
                variables[V] += step
                pc = continu
        elif typ == 'GOSUB':
            ret = pc
            pc  = goto[args[0]]
        elif typ == 'RETURN':
            pc = ret
import math
import random
import operator as op

def preprocess(stmts):
    """Go through stmts and return two values extracted from the declarations: 
    functions: a mapping of {name: function}, for both built-in and user-defined functions,
    data:      a queue of all the numbers in DATA statements."""
    functions = {  # A mapping of {name: function}; first the built-ins:
        'SIN': math.sin, 'COS': math.cos, 'TAN': math.tan, 'ATN': math.atan, 
        'ABS': abs, 'EXP': math.exp, 'LOG': math.log, 'SQR': math.sqrt, 'INT': int,
        '>': op.gt, '<': op.lt, '=': op.eq, '>=': op.ge, '<=': op.le, '<>': op.ne, 
        '^': pow, '+': op.add, '-': op.sub, '*': op.mul, '/': op.truediv, '%': op.mod,
        'RND': lambda _: random.random(), 'NEG': op.neg}
    data = deque() # A queue of numbers that READ can read from
    for (_, typ, args) in stmts:
        if typ == 'DEF':
            name, parm, body = args
            functions[name] = Function(parm, body)
        elif typ == 'DATA':
            data.extend(args[0])
    return functions, data

def evalu(exp):
    "Evaluate an expression, returning a number."
    if isinstance(exp, Opcall):
        return functions[exp.op](evalu(exp.x), evalu(exp.y))
    elif isinstance(exp, Funcall):
        return functions[exp.f](evalu(exp.x))
    elif isinstance(exp, Subscript):
        return variables[exp.var, tuple(evalu(x) for x in  exp.indexes)]
    elif is_varname(exp):
        return variables[exp]
    else: # number constant
        return exp
    
def let(V, value):
    "Assign value to the variable name or Subscripted variable."
    if isinstance(V, Subscript): # A subsscripted variable
        variables[V.var, tuple(evalu(x) for x in V.indexes)] = value 
    else:                        # An unsubscripted variable
        variables[V] = value
def basic_print(items): 
    "Print the items (',' / ';' / label / expression) in appropriate columns."
    for item in items:
        if item == ',':      pad(15)
        elif item == ';':    pad(3)
        elif is_label(item): print_string(item.replace('"', ''))
        else:                print_string("{:g} ".format(evalu(item)))
    if (not items) or items[-1] not in (',', ';'):
        newline()
        
def print_string(s): 
    "Print a string, keeping track of column, and advancing to newline if at or beyond column 100."
    global column
    print(s, end='')
    column += len(s)
    if column >= 100: newline()
        
def pad(width): 
    "Pad out to the column that is the next multiple of width."
    while column % width != 0: 
        print_string(' ')

def newline(): global column; print(); column = 0