We're beginning our journey into the world of interpreters! You may have seen an interpreter before. (Hint: that thing you've been running all your Python code 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 ones 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 with an interpreter for a simpler language, Scheme. (This course used to be taught in Scheme!)
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. 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? Plus 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 less colons!
We've decided to write our own dialect of Scheme (and by extension, Lisp) called stutter. Stutter is a stripped down version of Scheme, only supporting a versy small subset of the full Scheme language. 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/stutter.py . cp ~cs61a/lib/lab/pair.py .
You can also find the code here and here. You can try running stutter by running this command in terminal:
python3 stutter.py
The remaining 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 language.
Trace through the code in stutter.py that would be evaluated when you type the following into stutter. (Note: substitute is a little bit complicated and is a bit of a hack to get lambdas to work. Don't worry too much about understanding that part of the code).
stutter> 2 stutter> (+ 2 3) stutter> ((lambda (x y) (+ x y)) 1 2)
You might have noticed that if you type a lambda expression directly into stutter (without applying it to anything) that it returns None, like in the following example.
stutter> (lambda (x) (+ x 2)) None
Why does this happen? (Hint: What value gets returned in Python if you don't have a return statement?)
We've decided that we want stutter to become a major contender in the mathematical programming languages field! Unfortunately, right now it only has the +, -, *, and / mathematical operations. Help us corner the market by augmenting stutter so that it includes our killer new feature, the square function. It'd be used like this:
stutter> (square 4) 16 stutter> (square (+ 2 3)) 25
To get started, take a look at where predefined functions such as + and * are located in stutter.py. Understanding how the provided functions work will help out a lot when you try to add one yourself!
Right now, the only way to check multiple conditions is to use nested if statements. For instance, if I wanted to write a function to see if a number was less than 3 or greater than 7:
stutter> (lambda (x) (if (< x 3) #t (if (> x 7) #t #f)))
This is way too messy! Let's add or to stutter, so that we can write this instead:
stutter> (lambda (x) (or (< x 3) (> x 7)))
However, think back to what you know about Python's or operator. It did something we call "short-circuiting," which is a fancy way of saying that it stops checking its arguments as soon as it knows the answer. Consider the following case:
>>> True or 3 / 0 True
If or worked the same way as any normal operator, then it would evaluate both of its arguments before doing any work. However, we can see that or never evaluated its second argument, or else we would've gotten a ZeroDivisionError. That's because once it sees the True as its first argument, it knows the entire result will be True, and so it returns True immediately without checking any additional arguments.
We'd like our stutter or to do the same thing. However, we can't implement it the same way that we did for square, since doing it that way won't short-circuit! Instead, we'll need to find a different place to put it. You may want to start by looking at how if is set up in stutter. Remember that if is another one of those statements that doesn't follow the standard evaluation order! Once you have successfully implemented or, the following statement should not cause an error:
stutter> (or (= 1 1) (+ 1 #t)) #t