Calculator Evaluation

For Question 3 (New Procedure) and Question 5 (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 3, 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 5, 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 Q3
        operands = ____________ # UPDATE THIS FOR Q3
        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 Q3
    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 Q5
        return _________________ # UPDATE THIS FOR Q5

Q2: 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
✂️

Q3: 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 (from operator to 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
    """
    # BEGIN SOLUTION Q3

Use Ok to test your code:

python3 ok -q floor_div
Copy
✂️

Q4: 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 Q4

Use Ok to test your code:

python3 ok -q eval_and
Copy
✂️

Q5: 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 Q5

Use Ok to test your code:

python3 ok -q eval_define
Copy
✂️

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.

Please submit both the lab12.py and lab12.scm files to Gradescope!

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!

Q6: Count

Implement count, which takes in an element x and a list s and returns the number of times that x is contained in s.

scm> (count 1 '(1 2 3 4))
1
scm> (count 'a '(a b a b a))
3

(define (count x s)
  'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q count
Copy
✂️

Q7: Unique

Implement unique, which takes in a list s and returns a new list containing the same elements as s with duplicates removed.

scm> (unique '(1 2 1 3 2 3 1))
(1 2 3)
scm> (unique '(a b c a a b b c))
(a b c)

Hint: you may find it useful to use the built-in filter procedure. See the built-in procedure reference for more information.

(define (unique s)
  'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q unique
Copy
✂️

Q8: Tally

Implement tally, which takes a list of names and returns a list of 2-element lists, one for each unique name in names. Each 2-element list should contain a name and the number of times that the name appeared in names. Each name should appear only once in the output, and the names should be ordered by when they first appear in names.

scm> (tally '())
()
scm> (tally '(kevin irene ashley irene irene ashley brandon irene irene brandon))
((kevin 1) (irene 5) (ashley 2) (brandon 2))

(define (tally names)
  'YOUR-CODE-HERE
)

Hint: You might want to use count and unique procedures in your solution. You may also want to use map.

See the built-in procedure reference for more information.

Use Ok to test your code:

python3 ok -q tally
Copy
✂️