Scheme is a programming language. It is a dialect of Lisp, an even *older* language, that is
famous for having lots of parentheses. Much like Python, we also
have an interpreter for Scheme installed on the lab machines, which you can access by running
stk on the lab machines. Doing so gives you a prompt, which we can play around
with. It is important to be familiar with Scheme in order for you to complete project 4, where you
write an interpreter for Scheme in Python. So let's dive in!

We have numbers...

STk> 0 0 STk> 2 2

And we have strings...

STk> "hello" "hello"

And we have booleans...(#t means, true, #f means false)

STk> #f #f STk> (= 1 1) #t STk> (if (= 1 1) "math is fine" "math is broken") "math is fine"

And we have functions...

STk> 1+1 *** Error: unbound variable: 1+1 Current eval stack: __________________ 0 1+1

Wait, what gives? '+' doesn't seem to work! That's because Scheme doesn't have
infix notation (where the operator appears between the operands). No, in Scheme, every time you call a
function, you put the function in *front*, and you enclose the whole thing in parentheses:

STk> (+ 1 2) 3

This is true of *any* function call you could ever want to make in Scheme. Just type an open
parenthesis, the name of your function, any arguments, then a close parenthesis. Behold:

STk> (+ 1 (* 3 4)) 13 STk> (list 1 2 3) (1 2 3) STk> (map (lambda (x) (* x 2)) (list 1 2 3)) (2 4 6)

Hey, that last example included our favorite keyword again, lambda! It's also present in Scheme, and it does something very similar. In this case, (lambda (x) (* x 2)) creates a Scheme function that takes a single argument, x, and returns x multiplied by 2. Note that it looks similar to its Python equivalent, lambda x: x*2, except with more parentheses and fewer colons!

You can even define your own functions!

STk> (define (fib x) (if (<= x 1) 1 (+ (fib (- x 1)) (fib (- x 2))))) STk> (fib 5) 8 STk> (fib 20) 10946

To exit STk, use either the function bye or exit:

STk> (bye)

1. Try each of the following lines of Scheme in STk and see if you can explain to your peers what is happening (do them in order, some of the lines depend on the code above it):

3 (+ 2 3) (+ 5 6 7 8) (+) (sqrt 16) (+ (* 3 4) 5) + '+ 'hello '(+ 2 3) '(good morning) (first 274) (butfirst 274) (first 'hello) (first hello) (first (bf 'hello)) (+ (first 23) (last 45)) (define pi 3.14159) pi 'pi (+ pi 7) (* pi pi) (define (square x) (* x x)) (square 5) (square (+ 2 3)) (define a 3) (define b (+ a 1)) (+ a b (* a b)) (= a b) (if (and (> b a) (< b (* a b))) b a) (cond ((= a 4) 6) ((= b 4) (+ 6 7 a)) (else 25)) (+ 2 (if (> b a) b a)) (* (cond ((> a b) a) ((< a b) b) (else -1)) (+ a 1)) ((if (< a b) + -) a b)

We're beginning our journey onto the world of interpreters! You may have seen an interpreter before. (Hint: that thing you've been running all of your Python in? Yeah, that's an interpreter). In fact, the Python interpreter we've been using all semester long is really nothing but a program, albeit a very complex one. You can think of it as a program that takes strings as input and produces their evaluated result as output.

There's nothing magical about interpreters, though! They're programs, just like the one's you've been writing throughout the entire semester. In fact, it's possible to write a Python interpreter in Python; PyPy is proof of that. However, because Python is a complex language, writing an interpreter for it would be a very daunting project. Instead, we'll play around with an interpreter for a calculator language.

In lecture, you were introduced to our first interpreter program, calc, which acts as a simple calculator. It currently supports basic arithmetic, if statements, and lambda statements. You can copy the code to your current directory by running the following in your terminal:

cp ~cs61a/lib/lab/lab12/calc.py .

You can also find the code here. You can try running calc by running this command in the terminal:

python3 calc.py

To exit the program, type Ctrl-d

The following questions in the lab will ask you to look through the code to understand how it works and to modify the code to add your own extensions to the current version of the calc language.

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

calc> 2 calc> add(2, 3) calc> add(2, 3, 4) calc> +(2, 3) calc> add(2) calc> add(2, mul(4, 5))

3. It's boring to only do simple math; it'd be nice to compare numbers and eventually make choices based on these comparisons. Add in 3 additional operators eq, lt, and gt which allow us to compare two numbers. It should work in the following way:

calc> eq(5, 6) False calc> eq(4, 4) True calc> lt(5, 6) True calc> lt(6, 5) False calc> lt(6, 6) False calc> gt(5, 6) False calc> gt(6, 5) True calc> gt(6, 6) False calc> eq(mul(2, 2), 4) True calc> eq(mul(2, 6), 18) False calc> gt(mul(2, 2), 5) False calc> lt(mul(2, 2), 5) True

(*Hint*: You'll probably want to edit both the known_operators list
and the calc_apply function.)

4. Now that we can compare values, it'd be great to be able to make decisions using something like Python's if statement. Let's add if to the calc language!

To do this, we need to change the way calc **evaluates** the
"arguments" of if to be different from the way it handles
arguments for other functions. As a result, you will be making changes to calc_eval
in order to get if working correctly. Once you've implemented
if, you should be able to do the following:

calc> if(gt(5, 6), mul(5, 5), mul(6, 6)) 36 calc> if(eq(6, 6), mul(5, 5), mul(6, 6)) 25 calc> if(eq(6, 6), mul(5, 5), div(6, 0)) 25 calc> if(eq(5, 6), mul(5, 5), div(6, 0)) ZeroDivisionError: division by zero

**Note:** you should make sure that there's no error for that third example! if
doesn't evaluate all three of its arguments!

5. Now we will add in and and or which will behave
similarly to and and or in Python. Remember that
and and or are
short-circuiting
operators and that they return the *value* of the last expression they evaluate before stopping! Once
you're done, it should behave like the example below:

calc> and(eq(2, 3), div(4, 0)) False calc> and(eq(2, 2), div(4, 0)) ZeroDivisionError: division by zero calc> and(4, 5) 5 calc> or(eq(2, 2), div(4, 0)) True calc> or(4, 5) 4 calc> or(eq(2, 3), eq(2, 2), div(4, 0)) True calc> and(eq(2, 2), eq(2, 3), div(4, 0)) False