'''
lisp1.py
Written in 15-112-F26 Lecture1 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 (c := code.pop(0)) != EOF:
        token = None
        if c.isspace():
            continue
        elif c == COMMENT_CHAR:
            while code.pop(0) not in ['\n', EOF]:
                pass
        elif c.isdigit():
            # start of a number
            token = int(c)
            while code[0].isdigit():
                token = 10*token + int(code.pop(0))
        elif c.isalpha():
            # start of a variable name
            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 isinstance(token, int):
        return token
    elif token[0] == '(':
        # it's a list ( CMD arg0 arg1 ... argK )
        cmd = tokens.pop(0)
        result = [ cmd ]
        while tokens[0] != ')':
            result.append(parse(tokens))
        tokens.pop(0)
        return result
    elif isinstance(token, str) and token.isalpha():
        # variable like 'x''
        return token
    else:
        raise Exception(f'Illegal token: {token}')

g = globalVars = dict()
functionsMap = dict() # functions[fnName] = (fnParms, fnBody)

def evaluate(parseTree, localVars=None):
    if localVars == None:
        localVars = globalVars
    if isinstance(parseTree, int):
        return parseTree
    elif isinstance(parseTree, str):
        varName = parseTree
        if varName not in localVars:
            raise Exception(f'Undefined variable: {varName}')
        return localVars[varName]
    elif isinstance(parseTree, list):
        # [CMD, ARG, ARG... ]
        cmd = parseTree[0]
        rawArgs = parseTree[1:]
        if cmd == 'set':
            # (set VARNAME VARVAL)
            varName = rawArgs[0]
            varValue = evaluate(rawArgs[1], localVars)
            localVars[varName] = varValue
            return varValue
        elif cmd == 'if':
            # (if TEST TRUE_RESULT FALSE_RESULT)
            condition = evaluate(rawArgs[0], localVars)
            if condition == 1:
                return evaluate(rawArgs[1], localVars) # TRUE
            else:
                return evaluate(rawArgs[2], localVars) # FALS#
        elif cmd == 'while':
            # (while TEST BODY)
            result = 0
            while True:
                condition = evaluate(rawArgs[0], localVars)
                if condition == 0:
                    break
                result = evaluate(rawArgs[1], localVars)
            return result
        elif cmd == 'function':
            # (function NAME PARMS BODY)
            name, parms, body = rawArgs
            functionsMap[name] = (parms, body)
            return 2030
        evaluatedArgs = [evaluate(arg, localVars) for arg in rawArgs]
        if cmd == '+': return sum(evaluatedArgs)
        elif cmd == '-': return subtract(evaluatedArgs)
        elif cmd == '*': return multiply(evaluatedArgs)
        elif cmd == '/': return divide(evaluatedArgs)
        elif cmd == '<': return lessThan(evaluatedArgs)
        elif cmd == 'output': print(evaluatedArgs); return 0
        elif cmd == 'block': return evaluatedArgs[-1]
        elif cmd in functionsMap:
            # this is a user-defined function call
            parms, body = functionsMap[cmd]
            # set parms to args
            localVars = dict()
            for parm, arg in zip(parms, evaluatedArgs):
                localVars[parm] = arg
            return evaluate(body, localVars)
        else:
            raise Exception(f'Unknown command: {cmd}')
    else:
        raise Exception(f'Illegal parseTree: {parseTree}')

def subtract(L):
    return L[0] - sum(L[1:])

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 lessThan(L):
    for i in range(1, len(L)):
        if L[i-1] >= L[i]:
            return 0
    return 1

code = '''
    (+  (+ 10 2) ! 12
        (+  9 2) ! 11
        8
    ) ! 31
'''

code = '''
    (+  (* 10 2) ! 
        (/ 10 2)  !  5
        (- 10 2)  !  8
    ) ! 33
'''

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

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

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

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 (+ x 1))
            )
        )
    )
'''

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