CS 61A Lab 8

Scheme and Calculator

Starter Files

We've provided a set of starter files with skeleton code for the exercises in the lab. You can get them in the following places:

Scheme

Scheme is a famous functional programming language from the 1970s. It is a dialect of Lisp (which stands for LISt Processing). The first observation most people make is the unique syntax, which uses Polish-prefix notation and (often many) nested parenthesis. (See: http://xkcd.com/297/). Scheme features first-class functions and optimized tail-recursion, which were relatively new features at the time.

Primitives and Functions

Let's take a look at the primitives in Scheme. Open up the Scheme interpreter in your terminal with the command stk, and try typing in the following expressions to see what Scheme would print.

STk> 1          ; Anything following a ';' is a comment
?
STk> 1.0
?
STk> -27
?
STk> #t         ; True
?
STk> #f         ; False
?
STk> "A string"
?
STk> 'symbol
?
STk> nil
()

Of course, what kind of programming language would Scheme be if it didn't have any functions? Scheme uses Polish prefix notation, where the operator comes before the operands. For example, to evaluate 3 + 4, we would type into the Scheme interpreter:

STk> (+ 3 4)

Notice that to call a function we need to enclose it in parenthesis, with its arguments following. Be careful about this, as while in Python an extra set of parentheses won't hurt, in Scheme, it will interpret the parentheses as a function call. Evaluating (3) results in an error because Scheme tries to call a function called 3 that takes no arguments, which would result in an error.

Let's familiarize ourselves with some of the built-in functions in Scheme. Try out the following in the interpreter

STk> (+ 3 5)
?
STk> (- 10 4)
?
STk> (* 7 6)
?
STk> (/ 28 2)
?
STk> (+ 1 2 3 4 5 6 7 8 9)      ;Arithmetic operators allow a variable number of arguments
?
STk> (abs -7)             ;Absolute Value
?
STk> (quotient 29 5)
?
STk> (remainder 29 5)
?
STk> (= 1 3)
?
STk> (> 1 3)
?
STk> (< 1 3)
?
STk> (or #t #f)
?
STk> (and #t #t)
?
STk> (and #t #f (/ 1 0))        ;Short-Circuiting
?
STk> (not #t)
?
STk> (define x 3)               ;Defining Variables
STk> x
?
STk> (define y (+ x 4))
STk> y
?
STk> nil
?

To write a program, we need to write functions, so let's define one. The syntax for defining a program in Scheme is:

(define ([name] [args])
        [body])

For example, let's define the double function:

(define (double x)
        (+ x x))

Question 1

Try it yourself! Define a function which cubes an input. You can load your definitions into Scheme by entering stk -load filename.scm in your terminal, or if you have the interpreter already opened up (load "filename.scm").

(define (cube x)
        0)          ; Replace the 0 with your code

Control and Recursion

So far, we can't do much in our functions so let's introduce control statements to allow our functions to do more complex operations! The if-statement has the following format:

(if [condition]
    [true_result]
    [false_result])

For example, the following code written in Scheme and Python are equivalent:

;Scheme
(if (> x 3)
    1
    2)

#Python
if x > 3:
    1
else:
    2

Notice that the if-statement has no elif case. If want to have multiple cases with the if-statement, you would need multiple branched if-statements:

;Scheme
(if (< x 0)
    (display "Negative")
    (if (= x 0)
        (display "Zero")
        (display "Positive")))

#Python Equivalent
if x < 0:
    print('Negative')
else:
    if x == 0:
        print('Zero')
    else:
        print('Positive')

But this gets messy as more cases are needed, so alternatively, we also have the cond statement, which has a different syntax:

(cond ([condition_1] [result_1])
      ([condition_2] [result_2])
        ...
      ([condition_n] [result_n])
      (else [result_else]))                ;'else' is optional

With this, we can write control statements with multiple cases neatly and without needing branching if-statements.

(cond ((and (> x 0) (= (modulo x 2) 0)) (display "Positive Even Integer"))
      ((and (> x 0) (= (modulo x 2) 1)) (display "Positive Odd Integer"))
      ((= x 0) (display "Zero"))
      ((and (< x 0) (= (modulo x 2) 0)) (display "Negative Even Integer"))
      ((and (< x 0) (= (modulo x 2) 1)) (display "Negative Odd Integer")))

Now that we have control statements in Scheme, let us revisit a familiar problem: factorial. We will write it using a recursive procedure, but with both recursive and iterative processes. Read section 1.2.1 of this link to see what we mean by this. In short, an iterative process is summarized by state variables (for example, a counter and a sum), and update and termination rules. The iterative process can still use an underlying recursive procedure.

Question 2

  1. Write factorial with a recursive process.
  2. Write factorial with an iterative process. The procedure should still make a recursive call!

In the iterative case, most programming languages consume memory proportional to the number of procedure calls. However, Scheme "will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive." We see then that syntax such as "for" and "while" loops are not necessary in Scheme; they are merely "syntactic sugar".

Lists

In Scheme, lists are composed similarly to how Rlists that we had worked with in Python were implemented. Lists are made up pairs, which can point to two objects. To create a pair, we use the cons function, which takes two arguments:

STk> (define a (cons 3 5))
a
STk> a
(3 . 5)

Note the dot between the 3 and 5. The dot indicates that this is a pair, rather than a sequence (as you'll see in a bit).

To retrive a value from a pair, we use the car and cdr functions to retrieve the first and second elements in the pair.

STk> (car a)
3
STk> (cdr a)
5

Look familiar yet? Like how Rlists are formed, lists in Scheme are formed by having the first element of a pair be the first element of the list, and the second element of the pair point to another pair containing the rest of list, or to nil to signify the end of the list. For example, the sequence (1, 2, 3) can be represented in Scheme with the following line:

STk> (define a (cons 1 (cons 2 (cons 3 nil))))

which creates the following object in Scheme:

rlist

We can then of course retrieve values from our list with the car and cdr function.

STk> a
(1 2 3)
STk> (car a)
1
STk> (cdr a)
(2 3)
STk> (car (cdr (cdr a)))
3

This is not the only way to create a list though. You can also use the list function, as well as the quote form to form a list as well:

STk> (list 1 2 3)
(1 2 3)
STk> '(1 2 3)
(1 2 3)
STk> '(1 . (2 . (3)))

There are a few other built-in functions in Scheme that are used for lists:

STk> (define a '(1 2 3 4))
a
STk> (define b '(4 5 6))
b
STk> (define empty '())
empty
STk> (append '(1 2 3) '(4 5 6))
(1 2 3 4 5 6)
STk> (length '(1 2 3 4 5))
5
STk> (null? '(1 2 3))             ;Checks whether list is empty.
#f
STk> (null? '())
#t
STk> (null? nil)
#t

Question 3

Create the structure as defined in the picture below. Check to make sure that your solution is correct!

rlist

Question 4

Implement a function (remove item lst) that takes in a list and returns a new list with item removed from lst.

Question 5

Create a function (filter f lst), which takes a predicate function and a list, and returns a new list containing only elements of the list that satisfy the predicate.

Question 6

Implement a function (all_satisfies lst pred) that returns #t if all of the elements in the list satisfy pred.

More Scheme

There's a lot to Scheme, which is perhaps too much for this lab. Scheme takes a bit of time to get used to, but it's really not much different from any other language. The important thing is to just try different things and learn through practice. You can find more exercises here.

Calculator

We are continuing our journey through the world of interpreters! We have seen interpreters before -- that thing you've been running all of your Python in? That's an interpreter! In fact, the Python interpreter we've been using all semester long is just a program, albeit a very complex one. You can think of it as a program that takes strings as input, evaluates them, and prints the result as output.

There's nothing magical about interpreters, though! They are programs, just like the ones you have been writing throughout the entire semester. In fact, it's possible to write a Python interpreter in Python! However, because Python is a complex language, writing an interpreter for it would be a very daunting project. Today, we'll play around with an interpreter for a calculator language.

In lecture, you were introduced to Calc, which acts as a simple calculator. You should have already copied the starter files (scheme_reader.py, calc.py, etc.) at the start of the lab. You can try running Calc by running this command in the terminal:

python3 calc.py

To exit the program, type Ctrl-D or Ctrl-C.

Question 7

Trace through the code in calc.py that would be evaluated when you type the following into calc.

> 2
> (+ 2 3)
> (+ 2 3 4)
> (+ 2 3)
> (+ 2)
> (+ 2 (* 4 5))

Infix notation

While prefix notation (+ 2 3) is easy for computers to interpret, it's not very natural for humans. We'd much prefer infix notation (2 + 3). Let's implement this in our own version of calc!

To do this, you need to fill in the following functions, which are in the scheme_reader.py file.

Question 8

Implement read_infix. This function takes two arguments: first, the first expression in the infix expression; and src, the Buffer of tokens that contains the rest of the infix expression (and possibly more). For example, if we wanted to construct 3 + 4 5 (note: the 5 will be ignored, so it's really just 3 + 4)), we would call

read_infix(3, Buffer(tokenize_lines('+ 4 5')))

The return value should be an expression which is mathematically the same as the infix notation expression (e.g. (+ 3 4)), but written using Scheme style Pairs. See the doctests for simple examples. Follow these steps:

  1. First, check if there are more tokens left in the Buffer. Hint: the Buffer class in the buffer.py file has a more_on_line property method. If there aren't, we should just return nil. Also, we would need to return nil if the Buffer's current value (there's already a method that gives you the current value!) is equal to one of two things. Think about what these two things would be.
  2. Next, figure out what the operator and second half of the infix expression should be.
  3. Finally, return a Scheme-style expression which represents the same thing as the infix notation expression you parsed. Look at the doctests for specific examples.

Question 9

Implement next_is_op. This function returns True if the next token in the given Buffer is an operator, and False otherwise.

Hint: don't forget to check if there are any tokens in the buffer first. Also, don't remove any tokens from the Buffer (i.e. don't use pop; think of another method you can use).

Question 10

Modify scheme_read to parse infix expressions. This requires modifying two parts of the code:

  1. First, we need to determine if we're dealing with an expression like 2 + 3. To do this, check if the first item in the Buffer is a float or a int (this part's already written). If it is, then check that the next token is an operator. If it is, read it like an infix expression. (Try to call methods you've already written!) Otherwise, just return the value (this part's already written).
  2. Next, we have to deal with the case of infix notation inside parentheses. Without parentheses, 2 + 2 * 3 and 2 * 3 + 2 should produce the exact same result, but in calc, they don't! calc doesn't implement order of operations, because prefix notation naturally takes care of operator precedence (why?).

    Instead of solving the real problem, we'll implement a quick fix. If we allow expressions to be surrounded by parentheses, we can write expressions like 2 + (2 * 3), which will evaluate to the same thing as (2 * 3) + 2.

    To do this, we need to change how we parse lists. This logic should be very similar to what you did in the previous part of scheme_read. Hint: The code should be exactly like part 1, but figure out why!

And that's it! We have infix notation! The following inputs to calc should work.

> (+ 2 2 * 3)
8
> 2 + (- 5 2)
5
> (+ 1 3 * 4 (* 7 4))
41
> (2 * 3) + 6
12
> 6 + (2 * 3)
12

Defining Variables

Now we're going to add the ability to define variables. For example:

> (define x 3)
x
> (+ x 2)
5
> (* x (+ 2 x))
15

For this part, we will be modifying the calc.py file. Do we need to change calc_eval? calc_apply? Is define a special form?

Question 11

Implement do_define_form. This function takes in a Pair that contains 2 items: the variable name, and the expression to which it should be assigned. do_define_form should modify the global environment, env (a dictionary, defined near the top of calc.py) to contain the name/value binding. It should also return the name of the variable you're defining.

Question 12

Finally, implement the lookup procedure in calc_eval. You should check if the given identifier exp is in the environment. If it is, then simply return the value associated with it. If not, you should raise an exception to signal that the user did something wrong.

And that's it! There you have basic variable declaration.