Calculator Evaluation

For Question 2 (New Procedure) and Question 4 (Saving Values), you'll need to update the calc_eval function as listed below. This function performs the evaluations for each token with our Pairs. For instance, we've included the evaluations for numbers and booleans for you (they'll automatically be returned as is since they're atomic Scheme expressions). For Question 2, you'll be tasked to determine what the operator and operands for a funtion call in Scheme as well as actually applying the function in the calc_apply line. For Question 4, you'll be tasked to determing how to look up variables that we've previously stored.

def calc_eval(exp):
    """
    >>> calc_eval(Pair("define", Pair("a", Pair(1, nil))))
    'a'
    >>> calc_eval("a")
    1
    >>> calc_eval(Pair("+", Pair(1, Pair(2, nil))))
    3
    """
    if isinstance(exp, Pair):
        operator = ____________ # UPDATE THIS FOR Q2
        operands = ____________ # UPDATE THIS FOR Q2
        if operator == 'and': # and expressions
            return eval_and(operands)
        elif operator == 'define': # define expressions
            return eval_define(operands)
        else: # Call expressions
            return calc_apply(___________, ___________) # UPDATE THIS FOR Q2
    elif exp in OPERATORS:   # Looking up procedures
        return OPERATORS[exp]
    elif isinstance(exp, int) or isinstance(exp, bool):   # Numbers and booleans
        return exp
    elif _________________: # CHANGE THIS CONDITION FOR Q4
        return _________________ # UPDATE THIS FOR Q4

Q1: Using Pair

Answer the following questions about a Pair instance representing the Calculator expression (+ (- 2 4) 6 8).

Use Ok to test your understanding:

python3 ok -q using_pair -u
Copy
✂️

Q2: New Procedure

Suppose we want to add the // operation to our Calculator interpreter. Recall from Python that // is the floor division operation, so we are looking to add a built-in procedure // in our interpreter such that (// dividend divisor) returns dividend // divisor. Similarly we handle multiple inputs as illustrated in the following example (// dividend divisor1 divisor2 divisor3) evaluates to (((dividend // divisor1) // divisor2) // divisor3). For this problem you can assume you are always given at least 1 divisor.

Hint: You will need to modify both the calc_eval and floor_div methods for this question!

calc> (// 1 1)
1
calc> (// 5 2)
2
calc> (// 28 (+ 1 1) 1)
14

Hint: Make sure that every element in a Pair (the operator and all operands) will be calc_eval-uated once, so that we can correctly apply the relevant Python operator to operands! You may find the map method of the Pair class useful for this.

def floor_div(expr):
    """
    >>> floor_div(Pair(100, Pair(10, nil)))
    10
    >>> floor_div(Pair(5, Pair(3, nil)))
    1
    >>> floor_div(Pair(1, Pair(1, nil)))
    1
    >>> floor_div(Pair(5, Pair(2, nil)))
    2
    >>> floor_div(Pair(23, Pair(2, Pair(5, nil))))
    2
    >>> calc_eval(Pair("//", Pair(4, Pair(2, nil))))
    2
    >>> calc_eval(Pair("//", Pair(100, Pair(2, Pair(2, Pair(2, Pair(2, Pair(2, nil))))))))
    3
    >>> calc_eval(Pair("//", Pair(100, Pair(Pair("+", Pair(2, Pair(3, nil))), nil))))
    20
    """ 
    # BEGIN SOLUTION Q2

Use Ok to test your code:

python3 ok -q floor_div
Copy
✂️

Q3: New Form

Suppose we want to add handling for and expressions to our Calculator interpreter as well as introduce the Scheme boolean expressions #t and #f. These should work the same way they do in Scheme. (The examples below assumes conditional operators (e.g. <, >, =, etc) have already been implemented, but you do not have to worry about them for this question.)

calc> (and (= 1 1) 3)
3
calc> (and (+ 1 0) (< 1 0) (/ 1 0))
#f
calc> (and #f (+ 1 0))
#f
calc> (and 0 1 (+ 5 1)) ; 0 is truthy in Scheme!
6

In a typical call expression, we first evaluate the operator, then evaluate the operands, and finally apply the operator to the evaluated operands (just like you did for floor_div in the previous question). However, since and is a special form that short circuits on the first false-y operand, we cannot handle these expressions the same way we handle regular call expressions. We need to add special handling for combinations that don't evaluate all the operands. Complete the implementation below to handle and expressions.

Hint: Even though our calculator is interpreting Scheme expressions (with Pairs), we're performing evaluations in Python, which means we'll want to compare our calc_evaled expressions to the Python False, not the Scheme #f!

def eval_and(operands):
    """
    >>> calc_eval(Pair("and", Pair(1, nil)))
    1
    >>> calc_eval(Pair("and", Pair(False, Pair("1", nil))))
    False
    >>> calc_eval(Pair("and", Pair(1, Pair(Pair("//", Pair(5, Pair(2, nil))), nil))))
    2
    >>> calc_eval(Pair("and", Pair(Pair('+', Pair(1, Pair(1, nil))), Pair(3, nil))))
    3
    >>> calc_eval(Pair("and", Pair(Pair('-', Pair(1, Pair(0, nil))), Pair(Pair('/', Pair(5, Pair(2, nil))), nil))))
    2.5
    >>> calc_eval(Pair("and", Pair(0, Pair(1, nil))))
    1
    >>> calc_eval(Pair("and", nil))
    True
    """
    # BEGIN SOLUTION Q3

Use Ok to test your code:

python3 ok -q eval_and
Copy
✂️

Q4: Saving Values

In the last few questions we went through a lot of effort to add operations so we can do most arithmetic operations easily. However it's a real shame we can't store these values. So for this question let's implement a define special form that saves values to variable names. This should work like variable assignment in Scheme; this means that you should expect inputs of the form(define <variable_name> <value>) and these inputs should return the symbol corresponding to the variable name.

calc> (define a 1)
a
calc> a
1

This is a more involved change. Here are the 4 steps involved:

1. Add a bindings dictionary that will store the names and correspondings values of variables as key-value pairs of the dictionary.
2. Identify when the define form is given to calc_eval.
3. Allow variables to be looked up in calc_eval.
4. Write the function eval_define which should actually handle adding names and values to the bindings dictionary.

We've done step 1 for you. Now you'll do the remaining steps.

bindings = {}

def eval_define(expr):
    """
    >>> eval_define(Pair("a", Pair(1, nil)))
    'a'
    >>> eval_define(Pair("b", Pair(3, nil)))
    'b'
    >>> eval_define(Pair("c", Pair("a", nil)))
    'c'
    >>> calc_eval("c")
    1
    >>> calc_eval(Pair("define", Pair("d", Pair("//", nil))))
    'd'
    >>> calc_eval(Pair("d", Pair(4, Pair(2, nil))))
    2
    """
    # BEGIN SOLUTION Q4

Use Ok to test your code:

python3 ok -q eval_define
Copy
✂️

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit

Make sure to submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. For a refresher on how to do this, refer to Lab 00.

Optional Questions

These questions are optional, but you must complete them in order to be checked off before the end of the lab period. They are also useful practice!

Scheme Data Abstraction

Q5: Make Even

We've solved this problem with the Tree class. Now let's try it in Scheme!

Define a procedure make_even which takes in a tree t whose values are integers, and returns a new tree such that all the odd integers are increased by 1 and all the even integers remain the same.

(define (make-even t)
    'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q make-even
Copy
✂️

Q6: Find

Implement find which takes in a tree t whose values are integers and returns whether there exists any instances of integer x within the tree.

Hint: It may feel natural to use Python's all or any operator in this solution, but those operators unfortunately do not exist in scheme. For 7 and 8, is there some clever way we can emulate all andany using Scheme's filter and length operators?

(define (find t x)
    'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q find
Copy
✂️

Q7: N-ary Tree

We will define an N-ary tree to be a tree where each non-leaf subtree or node has exactly n branches. Implement a procedure n-ary which returns whether a tree t is an N-ary tree.

Note: This N-ary definition is contrived. In computer science, the actual definition of an N-ary tree is a tree where a node has any arbitrary number of branches - aka the type of trees we usually work with!

(define (n-ary t n)
    'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q n-ary
Copy
✂️