###
### charme.py
###
### cs150 Spring 2007
### Problem Set 7

def intsto(n):
  if n == 0:
    return []
  else:
    res = intsto(n-1)
    res.append(n)
    return res

authors = ["study","guide"] 

charmeFactorialDefinition = '(define factorial (lambda (x) (cond ((= x 0) 1) (#t (* x (factorial (- x 1)))))))'

pleased = 'I am pleased that this string is at least twenty characters long.'
displeased = 'I am displeased that this string is at least twenty characters long.'

###
### Parser
###

def parseError(msg):
    print "Parse error: " + msg
    
def tokenize(s):
    current = ''
    tokens = []
    for c in s:
        if c.isspace():
            if len(current) > 0:
                tokens.append(current)
                current = ''
        elif c in '()':)

 

            if len(current) > 0:
                tokens.append(current)
                current = ''
            tokens.append(c)
        else:
            current = current + c

    if len(current) > 0:
        tokens.append(current)
    return tokens

def parse(s):
    def parsetokens(tokens, inner):
       res = []
       while len(tokens) > 0:
          current = tokens.pop(0)
          if current == '(':
             res.append (parsetokens(tokens, True))
          elif current == ')':
             if inner:
                return res
             else:
                parseError("Unmatched close paren: " + s)
                return None
          else:
             res.append(current)
        
       if inner:
          parseError ("Unmatched open paren: " + s)
          return None
       else:
          return res

    return parsetokens(tokenize(s), False)

###
### Evaluator
###

def evalError(msg):
    print "Error: " + msg    
    
###
### Primitive Procedures
###
    
def checkOperands(operands, num, prim):
    if (len(operands) != num):
       print ("%s expected %s operands, given %s: %s"
              % (prim, num, len(operands), str(operands)))
           
def primitivePlus (operands):
    if (len(operands) == 0):
       return 0
    else:
       return operands[0] + primitivePlus (operands[1:])

def primitiveTimes (operands):
    if (len(operands) == 0):
       return 1
    else:
       return operands[0] * primitiveTimes (operands[1:])
    
def primitiveMinus (operands):
    if (len(operands) == 1):
       return -1 * operands[0]
    elif len(operands) == 2:
       return operands[0] - operands[1]
    else:
       evalError("Primitive - expected 1 or 2 operands, given %s: %s"
                  % (len(operands), str(operands)))

def primitiveEquals (operands):
    checkOperands (operands, 2, "=")
    return operands[0] == operands[1]

def primitiveZero (operands):
    checkOperands (operands, 1, "zero?")
    return operands[0] == 0

def primitiveGreater (operands):
    checkOperands (operands, 2, ">")
    return operands[0] > operands[1]

def primitiveLessThan (operands):
    checkOperands (operands, 2, "<")
    return operands[0] < operands[1]

###
### Primitives
###

def isNumber(expr):
    return isinstance(expr, str) and expr.isdigit()

def isPrimitiveProcedure(expr):
    return callable(expr)

def isPrimitive(expr):
    return (isNumber(expr) or isPrimitiveProcedure(expr))

def evalPrimitive(expr):
    # A primitive evaluates to its pre-defined value
    if isNumber(expr):
        return int(expr)
    else:
        return expr

###
### Conditionals
###
    
def isSpecialForm(expr, keyword):
    return isinstance(expr, list) \
           and len(expr) > 0 and expr[0] == keyword

def isConditional(expr):
    return isSpecialForm(expr, 'cond')

def evalConditional(expr, env):
    assert isConditional(expr)
    if len(expr) <= 2:
        evalError ("Bad conditional expression: %s" % str(expr))
    for clause in expr[1:]:
        if len(clause) != 2:
            evalError ("Bad conditional clause: %s" % str(clause))
        predicate = clause[0]
        result = meval(predicate, env)
        if not result == False:
            return meval(clause[1], env)
    evalError ("No conditional predicate evaluates to non-false value: %s"
               % (expr))
    return None

###
### Names and Definitions
###
    
class Environment:
    def __init__(self, parent):
        self._parent = parent
        self._frame = { }
    def addVariable(self, name, value):
        # add a new name, or replace old value
        self._frame[name] = value
    def lookupVariable(self, name):
        if self._frame.has_key(name):
            return self._frame[name]
        elif (self._parent):
            return self._parent.lookupVariable(name)
        else:
            evalError("Undefined name: %s" % (name))
    def toString(self):
        return "<Environment: %s / %s>" % (str(self._frame), str(self._parent))

def isDefinition(expr):
    return isSpecialForm(expr, 'define')

def evalDefinition(expr, env):
    assert isDefinition(expr)
    if len(expr) != 3:
        evalError ("Bad definition: %s" % str(expr))
    name = expr[1]
    if isinstance(name, str):
        value = meval(expr[2], env)
        env.addVariable(name, value)
    elif isinstance(name, list):
        evalError ("Procedure definition syntax not implemented")
    else:
        evalError ("Bad definition: %s" % str(expr))

def isName(expr):
    return isinstance(expr, str)

def evalName(expr, env):
    # To evaluate a name, lookup the value of the name in the environment
    assert isName(expr)
    return env.lookupVariable(expr)

###
### Procedures and Applications
###

### Modifies for Question 7
class Procedure:
    def __init__(self, params, body, env):
        self._params = params
        self._body = body
        self._env = env
        self._memos = { } # 7
    def getParams(self):
        return self._params
    def getBody(self):
        return self._body
    def getEnvironment(self):
        return self._env
    def hasResult(self, operands):                  # 7
        return self._memos.has_key(str(operands))   # 7
    def storeResult(self, operands, result):        # 7
        self._memos[str(operands)] = result         # 7
    def getResult(self, operands):                  # 7
        assert self.hasResult(str(operands))        # 7
        return self._memos[str(operands)]           # 7
    def __str__(self):
        return "<Procedure %s / %s>" % (str(self._params), str(self._body))

def isLambda(expr):
    return isSpecialForm(expr, 'lambda')

def evalLambda(expr,env):
    assert isLambda(expr)
    if len(expr) != 3:
        evalError ("Bad lambda expression: %s" % str(expr))
    return Procedure(expr[1], expr[2], env)
                      
def isApplication(expr):
    # Applications are lists [proc, oper, oper]
    # Assumes expr is not a special form (must check special forms first)
    return isinstance(expr, list)
   
def evalApplication(expr, env):
    # To evaluate an application, evaluate all the subexpressions
    subexprs = expr
    subexprvals = map (lambda sexpr: meval(sexpr, env), subexprs)
    # then, apply the value of the first subexpression to the rest
    return mapply(subexprvals[0], subexprvals[1:])

### Modified for Question 7
def mapply(proc, operands):
    if (isPrimitiveProcedure(proc)):
        return proc(operands)
    elif isinstance(proc, Procedure):
            params = proc.getParams()
            if proc.hasResult(operands):        # 7
                return proc.getResult(operands) # 7
            else:
                newenv = Environment(proc.getEnvironment())
                if len(params) != len(operands):
                    evalError ("Parameter length mismatch: %s given operands %s" \
                               % (proc.toString(), str(operands)))
                for i in range(0, len(params)):
                    newenv.addVariable(params[i], operands[i])        
                result = meval(proc.getBody(), newenv) # 7
                proc.storeResult(operands, result)     # 7
                return result                          # 7
    else:
        evalError("Application of non-procedure: %s" % (proc))

###
### Core Evaluator
###

def meval(expr, env):
    if isPrimitive(expr):
       return evalPrimitive(expr)
    elif isConditional(expr):
       return evalConditional(expr, env)
    elif isIf(expr):                 # Question 6
        return evalIf(expr, env)     #
    elif isLambda(expr):
       return evalLambda(expr, env)
    elif isDefinition(expr):                
       evalDefinition(expr, env)
    elif isName(expr):
       return evalName(expr, env)
    elif isApplication(expr):
       return evalApplication(expr, env)
    else:
       evalError ("Unknown expression type: " + str(expr))

### Question 2
def primitiveLessThanOrEqualTo (operands):
    checkOperands (operands, 2, "<=")
    return operands[0] <= operands[1]

### Question 3
class Cons:
    def __init__(self, left, right):
        self._left = left
        self._right = right
    def __str__(self):
        if isList(self):
            return "(%s)" % self.strAsList()
        return "(%s . %s)" % (str(self._left), str(self._right))
    def strAsList(self):
        if self._right == None:
            return str(self._left)
        else:
            return str(self._left) + " " + self._right.strAsList()
    def car(self):
        return self._left
    def cdr(self):
        return self._right

def primitiveCons (operands):
    checkOperands (operands, 2, "cons")
    res = Cons(operands[0], operands[1])
    return res

def primitiveCar(operands):
    checkOperands(operands, 1, "car")
    return operands[0].car();

def primitiveCdr(operands):
    checkOperands(operands, 1, "cdr")
    return operands[0].cdr();

### Question 4

def primitiveIsNull (operands):
    checkOperands(operands, 1, "null?")
    return operands[0] == None

### Question 5

def primitiveList (operands):
    if (len(operands) == 0):
        return None
    else:
        return Cons(operands[0], primitiveList(operands[1:]))

def isList(expr):
    if expr == None:
        return True
    elif isinstance(expr, Cons):
        return isList(expr.cdr())
    else:
        return False

def isIf(expr):
    return isSpecialForm(expr, 'if')

def evalIf(expr,env):
    assert isIf(expr)
    if len(expr) != 4:
        evalError ("Bad if expression: %s" % str(expr))
    if meval(expr[1], env) != False:
        return meval(expr[2],env)
    else:
        return meval(expr[3],endef initializeGlobalEnvironment():

                     
    global globalEnvironment
    globalEnvironment = Environment(None)
    globalEnvironment.addVariable('#t', True)
    globalEnvironment.addVariable('#f', False)
    globalEnvironment.addVariable('+', primitivePlus)
    globalEnvironment.addVariable('-', primitiveMinus)
    globalEnvironment.addVariable('*', primitiveTimes)
    globalEnvironment.addVariable('=', primitiveEquals)
    globalEnvironment.addVariable('zero?', primitiveZero)
    globalEnvironment.addVariable('>', primitiveGreater)
    globalEnvironment.addVariable('<', primitiveLessThan)
    globalEnvironment.addVariable('<=', primitiveLessThanOrEqualTo)  # 2  
    globalEnvironment.addVariable('cons', primitiveCons) # 3
    globalEnvironment.addVariable('car', primitiveCar) # 3
    globalEnvironment.addVariable('cdr', primitiveCdr) # 3
    globalEnvironment.addVariable('null', None) # 4
    globalEnvironment.addVariable('null?', primitiveIsNull) # 4
    globalEnvironment.addVariable('list', primitiveList) # 5

initializeGlobalEnvironment();

def evalLoop():
    print "Welcome to Charme (the Snake Charmer's Language)"
    initializeGlobalEnvironment()
    while True:
        intext = raw_input("Charme> ")
        commands = intext.split()
        if commands[0] == 'quit':
            break
        elif commands[0] == 'load':
            if len(commands) != 2:
                print "Load commands expects one parameter."
                continue
            else:
                fname = commands[1]
                try:
                    f = open(fname)
                    intext = f.read()
                    f.close()
                except:
                    print "Error reading file: " + fname
        if True: #try:
            exprs = parse(intext)
            if exprs:
                for expr in exprs:
                    res = meval(expr, globalEnvironment)
                    if res != None:
                        print str(res)
#        except:
#            print "Error evaluating " + str(expr)
            
###
### Evaluates a top-level expression 
###
###   evalToplevelExp( parse("(+ 123 456)") ) 
### prints out 579
###

def evalToplevelExp(parsedExp):
    for expr in parsedExp:
        res = meval(expr, globalEnvironment)
        if isinstance(res, Procedure):
            print res.toString()
        elif res != None:
            print res