CS61A 的项目四之 Scheme 解释器实现 (2021-Fall)

...
def define(self, symbol, value):
    """Define Scheme SYMBOL to have VALUE."""
    self.bindings[symbol] = value

def lookup(self, symbol):
    """Return the value bound to SYMBOL. Errors if SYMBOL is not found."""
    # Case 1. we check if the symbol is in the current frame
    if symbol in self.bindings.keys():
        return self.bindings[symbol]
    else:
        # Case 2. we check the parent of the current frame repreatly
        pos = self.parent
        while pos is not None:
            if symbol in pos.bindings.keys():
                return pos.bindings[symbol]
            pos = pos.parent
    # Case 3. we can't find the symbol
    raise SchemeError("unknown identifier: {0}".format(symbol))
...

def scheme_apply(procedure, args, env):
    ...
    if isinstance(procedure, BuiltinProcedure):
        # Convert the Scheme list to a Python list of arguments
        args_list = []
        pos = args
        while pos is not nil:
            if pos.first is not nil:
                args_list.append(pos.first)
            else:
                args_list.append(nil)
            pos = pos.rest
        # Add the current environment if procedure.expect_env == True
        if procedure.expect_env:
            args_list.append(env)
        # Call procedure.py_func on all arguments
        try:
            return procedure.py_func(*args_list)
        except TypeError as e:
            raise SchemeError(f"incorrect number of arguments, {e}")
    ...

def scheme_eval(expr, env, _=None):  # Optional third argument is ignored
    ...
    else:
        # Evaluate the operator(first argument)
        operator = scheme_eval(first, env)
        validate_procedure(operator)
        # Evaluate all of the operands(other arguments)
        from functools import partial
        operands = rest.map(partial(scheme_eval, env=env))

        return scheme_apply(operator, operands, env)

def do_define_form(expressions, env):
    ...
    if scheme_symbolp(signature):
        # assigning a name to a value e.g. (define x (+ 1 2))
        validate_form(
            expressions, 2, 2
        )  # Checks that expressions is a list of length exactly 2
        env.define(signature, scheme_eval(expressions.rest.first, env))
        return signature
    ...

def do_quote_form(expressions, env):
    validate_form(expressions, 1, 1)
    return expressions.first

def eval_all(expressions, env):
    if expressions is nil:
        return None
    res = scheme_eval(expressions.first, env)
    if expressions.rest is nil:
        return res
    else:
        return eval_all(expressions.rest, env)

def do_lambda_form(expressions, env):
    validate_form(expressions, 2)
    formals = expressions.first
    validate_formals(formals)
    return LambdaProcedure(formals, expressions.rest, env)

def make_child_frame(self, formals, vals):
    if len(formals) != len(vals):
        raise SchemeError("Incorrect number of arguments to function call")
    sub_frame = Frame(self)
    # iterate
    pos1, pos2 = formals, vals
    while pos1 is not nil:
        key, value = pos1.first, pos2.first
        sub_frame.define(key, value)
        pos1, pos2 = pos1.rest, pos2.rest
    return sub_frame

def scheme_apply(procedure, args, env):
    ...
    elif isinstance(procedure, LambdaProcedure):
        child_frame = procedure.env.make_child_frame(procedure.formals, args)
        return eval_all(procedure.body, child_frame)
    ...

def do_define_form(expressions, env):
    ...
    elif isinstance(signature, Pair) and scheme_symbolp(signature.first):
        # defining a named procedure e.g. (define (f x y) (+ x y))

        # the signature is (f x y)
        formals = signature.rest  # (x y)
        validate_formals(formals)

        # now we need to parse (+ x y)
        env.define(signature.first, LambdaProcedure(formals, expressions.rest, env))
        return signature.first  # f
    ...

def scheme_apply(procedure, args, env):
    ...
    elif isinstance(procedure, MuProcedure):
        child_frame = env.make_child_frame(procedure.formals, args)
        return eval_all(procedure.body, child_frame)
    ...
def do_mu_form(expressions, env):
    validate_form(expressions, 2)
    formals = expressions.first
    validate_formals(formals)
    return MuProcedure(formals, expressions.rest)

def do_and_form(expressions, env):
    # base case: (and)
    if expressions is nil:
        return True
    front = scheme_eval(expressions.first, env)
    if is_scheme_true(front):
        if expressions.rest is nil:
            return front
        else:
            return do_and_form(expressions.rest, env)
    else:
        return front

def do_or_form(expressions, env):
    # base case: (or)
    if expressions is nil:
        return False
    front = scheme_eval(expressions.first, env)
    if is_scheme_false(front):
        if expressions.rest is nil:
            return front
        else:
            return do_or_form(expressions.rest, env)
    else:
        return front

def do_cond_form(expressions, env):
        ...
        if is_scheme_true(test):
            # no sub-expression
            if clause.rest is nil:
                return test
            return eval_all(clause.rest, env)
        ...

def make_let_frame(bindings, env):
    if not scheme_listp(bindings):
        raise SchemeError("bad bindings list in let form")
    names = values = nil

    # bingding: (<name> <expression>)
    # bingdings: ( (<name1> <expression1>) (<name2> <expression2>) ...)
    pos = bindings
    while pos is not nil:
        front = pos.first  # i.e. the first binding
        validate_form(front, 2, 2)  # verify the structure is (<name> <expression>)
        names = Pair(front.first, names)
        values = Pair(eval_all(front.rest, env), values)
        pos = pos.rest
    validate_formals(names)

    return = env.make_child_frame(names, values)

(define (enumerate s)
  (begin
      ;; a helper funtion
      (define (helper input index) 
        (cond ((null? input) '())             ;; base case: return () if it is nil
              (else (cons (cons index (cons (car input) nil))
                          (helper (cdr input) (+ index 1))))))   ;; recursive call
      (helper s 0))
  )

(define (merge inorder? list1 list2)
  (cond ((null? list1) list2)           ;; base case: list1 is empty
        ((null? list2) list1)           ;; base case: list2 is empty
        ((inorder? (car list1) (car list2))           
            (cons (car list1) (merge inorder? (cdr list1) list2)))      ;; consume list1
        (else
            (cons (car list2) (merge inorder? list1 (cdr list2)))))     ;; consume list2
  )