'''
lisp2.py
Written in 15-112-F26 Lecture2 on 10/06/2026.

Note: This code is strictly for demonstrational purposes.
It was written very quickly in lecture while cutting many
corners so we could focus on the Big Picture while writing
a working Lisp interpreter in just over an hour.

Bottom line: do not actually use this code for anything.
If you are interested in making a more robust Lisp interpreter,
please talk to the course faculty and we will happily
help you shore up this design.
'''

import string

EOF = chr(0)
COMMENT_CHAR = '?'

def tokenize(code):
    code += EOF
    code = list(code)
    tokens = [ ]
    while code not in [ [], [EOF] ]:
        c = code.pop(0)
        token = None
        if c.isspace():
            continue
        elif c == COMMENT_CHAR:
            while code[0] not in ['\n', EOF]:
                code.pop(0)
        elif c.isdigit():
            token = int(c)
            while code[0].isdigit():
                token = 10*token + int(code.pop(0))
        elif c.isalpha():
            token = c
            while code[0].isalpha():
                token += code.pop(0)
        elif c in string.punctuation:
            token = c
        else:
            raise Exception(f'Illegal token: {c}')
        if token != None:
            tokens.append(token)
    return tokens + [EOF]

def parse(tokens):
    token = tokens.pop(0)
    if token == '(':
        # ( CMD ARG ARG ... ARG )
        cmd = tokens.pop(0)
        parseTree = [ cmd ]
        while tokens[0] != ')':
            parseTree.append(parse(tokens))
        tokens.pop(0) # eat the right paren )
        return parseTree
    elif isinstance(token, int):
        return token
    elif isinstance(token, str):
        return token
    else:
        raise Exception(f'Illegal token in parse: {token}')

g = globalVars = dict()
fm = functionsMap = dict()

def evaluate(parseTree, localVars=None):
    if localVars == None:
        localVars = globalVars
    if isinstance(parseTree, int):
        return parseTree
    elif isinstance(parseTree, str):
        # This is a variable, evaluate to its value
        varName = parseTree
        return localVars[varName]
    elif isinstance(parseTree, list):
        cmd = parseTree[0]
        args = parseTree[1:]
        if cmd == 'set':
            # (set VARNAME VARVAL)
            varName = args[0]
            varValue = evaluate(args[1], localVars)
            localVars[varName] = varValue
            return varValue
        elif cmd == 'if':
            # (if TEST TRUE_RESULT FALSE_RESULT)
            condition = evaluate(args[0], localVars)
            if condition == 1:
                return evaluate(args[1], localVars)
            else:
                return evaluate(args[2], localVars)
        elif cmd == 'while':
            # (while TEST BODY)
            result = 0
            while True:
                condition = evaluate(args[0], localVars)
                if condition == 0:
                    return result
                result = evaluate(args[1], localVars)
        elif cmd == 'function':
            fnName = args[0]
            parms = args[1]
            body = args[2]
            functionsMap[fnName] = (parms, body)
            return 0
        evaluatedArgs = [evaluate(arg, localVars) for arg in args]
        if cmd == '+': return sum(evaluatedArgs)
        elif cmd == '*': return multiply(evaluatedArgs)
        elif cmd == '/': return divide(evaluatedArgs)
        elif cmd == '-': return subtract(evaluatedArgs)
        elif cmd == '<': return lessThan(evaluatedArgs)
        elif cmd == 'block': return evaluatedArgs[-1]
        elif cmd == 'output': print(evaluatedArgs); return 0
        elif cmd in functionsMap:
            # user-defined function
            parms, body = functionsMap[cmd]
            if len(evaluatedArgs) != len(parms):
                raise Exception(f'Wrong # of args to {cmd}')
            localVars = dict() # create the local scope
            for parm, arg in zip(parms, evaluatedArgs):
                localVars[parm] = arg
            return evaluate(body, localVars)
        else:
            raise Exception(f'Unknown cmd: {cmd}')
    else:
        raise Exception(f'Illegal parseTree: {parseTree}')

def multiply(L):
    result = L[0]
    for v in L[1:]: result *= v
    return result

def divide(L):
    result = L[0]
    for v in L[1:]: result //= v
    return result

def subtract(L):
    result = L[0]
    for v in L[1:]: result -= v
    return result

def lessThan(L):
    for i in range(1, len(L)):
        if L[i-1] >= L[i]:
            return 0
    return 1

code = '''
    (+ (* 3 4)  ? 12
       (/ 10 2) ? 5
    ) ? 17
'''

code = '''
    (block
        (set x (+ 1 4))
        (* x 5) ? 25
        (output (* x 100))
    )
'''

code = '''
    (block
        (set x 5)
        (while (< x 10)
            (block
                (set x (+ 1 x))
                (output x)
            )
        )
    )
'''

code = '''
    (block
        (function f (x y)
            (+ x y)
        )
        (f 2 3)
    )
'''

code = '''
    (block
        (function fib (n)
            (if (< n 2)
                1
                (+ (fib (- n 1))
                   (fib (- n 2))
                )
            )
        )
        (set x 0)
        (while (< x 10)
            (block
                (output x (fib x))
                (set x (+ 1 x))
            )
        )
    )

'''

print('tokens:   ', tokenize(code))
print('parseTree:', parse(tokenize(code)))
print('-----')
print('result:   ', evaluate(parse(tokenize(code))))