Lecture 2: Expression Evaluation

Introduction to Scheme

For these first few lectures, we will draw heavily on an on-line textbook: An Introduction to Scheme and its Implementation. The reading for this lecture is the Overview and the first two parts of the introduction: "What is Scheme?" and "Basic Scheme Features".

You may want to check the online Scheme Frequently Asked Questions list if you have other questions about the language.

Review: Three things every programming language has:

primitive expressions
means of combination
means of abstraction

Primitives

Scheme has a number of primitives. Here are some examples:

literals: numerals, booleans, strings, characters, etc.

Most languages have some means of specifying primitive data values like these. Since you type them in as they are meant to be taken literally, these are called literals. Here's how you specify them in Scheme:

numbers	`3`, `5.2`, etc.
characters	Use a "#\" preceding the character: `#\a` for the character 'a', etc.
strings	Use quotation marks as in C or Java: `"this is a string"`.
symbols	Scheme and some other languages have the ability to reference the symbols in their own code as a separate datatype. In Scheme, these are written by putting a single quote in front of the symbol: `'a`, `'hello`, etc.
booleans	`#t` and `#f` for true and false respectively

variables

Variables names (identifiers) in Scheme are a little more flexible than what you're probably used to. Not only are letters, number, and underscores (_) permissible, but so are most other characters: ?, !,+,-, etc. So, all of the following are legal identifiers in Scheme: remove-first, zero?, change!, this+that, +.

procedures or functions

Scheme has a number of pre-defined functions, such as + (addition), - (subtraction, * (multiplication), = (numeric compare), eq? (general compare), display (write to the screen), zero? (test for zero), etc. Be careful, though: these don't parse any differently than other functions and can be re-defined to be what you want them to be. In Scheme "+" is just the name of the pre-defined addition function, not anything else special. You can define your own functions, too, which we'll cover in a later lecture.

Expressions

In Scheme, we build primitives into compound objects be combining them in expressions. There are no statements in Scheme, everything is an expression. Expressions have the following properties:

prefix notation -- the operator is in front.
fully parenthesized -- there are lots of parentheses!

The syntax for all expressions thus looks like this:

      (<operator> <operand1> <operand2> <operand3>  ....)

What's this? A programming language with no semi-colons, commas, curly braces, etc? That's right. One of the things you'll learn very early in this class is that those are all just syntactic stuff that gets parsed out very early in the process. Languages use different syntaxes and may look very different on the outside, but inside they're really very similar—that's what this class is all about!

Abstraction (Definitions)

Scheme has a number of abstraction mechanisms. For now, we will only concern ourselves with one: definition. Definitions have the same syntax as expressions except that the operator is the keyword define:

     (define <name> <expression>)

The expression is evaluated and given the name.

Read-Eval-Print Loop

Before we dive into Scheme, a brief introduction to how the Scheme interpreter (as well as every interpreter) works is in order. To interpret a language statement, an interpreter must cycle through the following three steps:

read the expression
evaluate the result
print the answer

This is known as the Read-Eval-Print Loop or REP. This sequence is extremely important for what we will be doing in this class. Be sure to memorize it.

Reading Expressions

Reading an expression also goes by the name parsing. Parsing translates the string that the user types into a data structure on which the evaluator can operate.

Some of the notation used to describe syntax and algorithms for doing simple parsing should have be covered in CS 236 and CS 252. We will not talk about how to do parsing in this course. More details on parsing are covered in the compiler course (CS 431).

Evaluating Expressions

Evaluating expressions is the heart of this course. Fortunately evaluation in Scheme uses a simple algorithm: To evaluate an expression, (operator operand1 operand2 operand3 ....):

evaluate each of the subexpressions
apply the leftmost result to the rest.

While this seems overly simplistic, you will see that much of the rest of the semester will be built around this idea. Many other languages such as C++ or Java use this same basic algorithm, even though their syntax looks very different.

Printing Expressions

Printing an expression is the opposite problem of reading it. A printer must translate the internal representation into a string that can be written to the terminal.

Examples

As we just saw, Scheme works by reading an expression from the terminal, evaluating (that is, finding a meaning for) it, and printing the result at the terminal. After it has done this it goes back and is ready to do it again. Scheme lets you know that its ready to read an expression by prompting you with an arrow.

Simple primitives and expressions:

When we type something in response to the prompt, for instance a number, Scheme will provide the result of evaluating the number:

==>  255
255

Here we see an important behavior of Scheme. As I said before, Scheme evaluates everything presented to it. Primitive objects, such as numbers, evaluate to themselves. We can combine primitive objects with appropriate operators to form expressions. A compound expression is always enclosed in parentheses. This may be different than your previous experience with other programming languages where parentheses are used to denote optional grouping. You cannot insert and delete parentheses from a Scheme expression without changing the meaning of the expression.

Here are some examples of Scheme expressions and the results of their evaluation:

==> (* 2 2)
4
==> (- 4 2)
2
==> (+ 3 5.2)
8.2
==> (/ 4 2)
2
==> (/ 1 3)
.333333333333}
==> (- -3 -5)
2

There are several important points to make about the above Scheme session. First, note that the leftmost element in a compound expression is the operator, followed by the operands. The Scheme evaluator determines the value of the expression by applying the procedure specified by the operator to the value of the operands. That last sentence was extremely important, so make sure you understand what it says.

Another point to make is that Scheme does not differentiate between integers and real numbers. The result of adding 3 to 5.2 is 8.2. The result of dividing 1 by 3 is .33333. This will seem obvious to those of you without previous programming experience, but other computer languages frequently make this distinction.

Lastly, notice that in the last expression, the "-" occurs three times and means two different things. When it's the leftmost element in the expression, it represents the operation that is to take place, when its appended to the front of a number, it means that the number is negative. Spacing is important here; (- - 3 -5) will produce an error.

When the operator proceeds the operands, we say that the expression is using prefix notation. Scheme uses prefix notation exclusively. Prefix notation has several advantages over other notations:

Using prefix notation, we can have an arbitrary number of arguments. For example, it is easy to write (+ 3 4 8 6 5 4 7 6 5 8 9) using prefix notation. In other notation, such as infix, this expression would be longer and involve more than one operator.
We don't have to be worried about issues of precedence when we use prefix notation. For example, in the expression 3 + 4 * 5 / 6 - 7, which operations are performed first? You probably know because you memorized this as a young child learning arithmetic. Using prefix notation, however, the issues of precedence are clear without anyone memorizing precedence rules. The above example would be written (- (+ 3 (/ (* 4 5) 6)) 7). You may be saying to yourself that this isn't clear at all, but trust me, its just a matter of exposure and you'll be as comfortable with this system as any other.
Like any good language, Scheme allows us to build complex expressions out of simple ones. We do this by nesting expressions inside one another. Prefix notation allows us to nest expressions in a straightforward way. For example, 4 / 2 + (4 + 6) is written:

(+ (/ 4 2) (+ 4 6))

One problem with prefix notation is that sometimes there are so many parentheses that we get lost:

(* (* (+ 3 5) (- 3 (/ 4 3))) (- (* (+ 4 5) (+ 7 6)) 4))

If we really try, we could probably figure this out, but it is not clear what this means to the casual observer. In order to help with this kind of confusion, most Scheme programmers adopt some sort of indentation scheme to allow them to read programs easily. If we write the above expression over a number of lines and indent them carefully, we can more easily see how it should be evaluated:

(* (* (+ 3 5)
      (- 3 (/ 4 3)))
   (- (* (+ 4 5)
         (+ 7 6))
      4))

Of course, this isn't the only way to indent this and you may prefer another, but I think anyone will agree that this is better than the original. It doesn't matter what kind of indenting you use in this course as long as your meaning can be clearly understood.

Definitions

One of the most important things a programming language does is provide tools for building abstractions. One of the simplest, but most frequently used, tools for building abstractions is being able to give names to computational objects.

Consider for a moment how one talks about problems in daily life. To find the circumference of a circle with a radius of 3, we say multiply 3 times 2 times pi. Pi is the name of a number. Its a name that means something to anyone who has had seventh grade mathematics and furthermore gives us a convenient handle for referring to a not so convenient number.

To associate a name with a number in Scheme, we use a special operator called define. When you type

==> (define PI 3.14159)
pi

you cause the Scheme interpreter to associate the name pi with the computational object 3.14159. Just like all other expressions, this Scheme expression returns a value. In this case, the name that is being defined.

Now that we have associated a name with the object 3.14159, we can refer to that object by name. For instance:

==> pi
3.14159
==> (+ 2 pi)
5.14159

and so on. Here are some more examples:

==> (define radius 6)
radius
==> (* 2 pi radius)
37.70
==> (define circumference (* 2 pi radius))
circumference}
==> circumference
37.70

Notice that after we have defined circumference we can ask Scheme to evaluate it. Its important to realize that the value of circumference is 37.70 not (* 2 pi radius). The expression is evaluated at the time of the definition and its value is given the name circumference.

Consider the following sequence of three definitions:

    (define a 3)
    (define b (+ a 1))
    (define a 4)

What are the values of a and b after each definition? What is the value of b at the end? Try it in your interpreter to see for yourself.

As I said before, define is Scheme's simplest means of abstraction. Being able to name computational objects allows names to be associated with complex results, such as circumference. In addition, we don't need to repeat the whole string and, more importantly, reevaluate it each time we need to know the circumference. Finally, we can build programs incrementally by successive definition. This last point is very important. Programming in Scheme is done by defining one thing, and then the next, building up a program in a series of steps. At each point along the way the objects that have been defined are available for use and testing.

Defining Your Own Functions

We'll talk a lot more about functions in Lecture 4, but here's a simple syntax for defining functions:

    (define (inc x)
       (+ x 1))

Notice that it has the following parts:

You use define, just as you define other things
Instead of an identifier, you put (function-name function-parameters) . You can have as many parameters as you want for the function.
Unlike in a regular define, the expression is not evaluated yet but is bound to the function and called later when the function is used.

Go ahead and use this syntax for declaring function for now, but be aware that it's really short-hand for a much more powerful mechanism for defining functions, which we'll cover in Lecture 4.

Conditional Expressions

Yes, expressions, not statements!

Syntax: (if test-expr then-expr else-expr)
Only one of the two branches is evaluated. Please note that while this is the expected behavior of a conditional statement, it differs from what would happen if this were a procedure.
A conditional statement isn't one of the three things that every programming language has. Why not? How could a programming language not have a conditional statement and do anything useful?

All high-level languages have a way of expressing the idea of choice in an algorithm, although some do not have conditional expressions or statements. In Scheme, there are two different forms of conditional expressions. The first form is the most general and is called cond. Cond is used like this:

(define (zero? x)
   (cond ((= x 0) true)
         ((< x 0) false)
         ((> x 0) false))))

This function can be used like this:

==>(zero? 12)
#f
==>(zero? 0)
#t
==>(zero? -5)
#f

The general form of the cond statement in Scheme is

(cond (<p1> <e1>)
      (<p2> <e2>)
            .
            .
            .
      (<pn> <en>))

Each of the arguments to the cond statement, called clauses, is a pair of expressions. The first one, the predicate, is a boolean expression. The second part of the clause, called the consequent, is an expression to evaluate if the predicate is true. When the Scheme interpreter comes across a cond statement, it finds the value of the first predicate. If it's value is false, the next predicate is evaluated. This continues until a predicate that evaluates to true is found, then the consequent expression associated with that predicate is evaluated and its value returned as the value of the cond statement. If none of the predicates evaluate to true, cond returns a value of false.

Its easy to make mistakes with the parentheses in a cond statement, but if you remember a few points, its not that hard. Think of cond as an operator with a number of arguments, each of the arguments is enclosed in parentheses. The predicate and consequent expressions are just like the expressions that we've seen so far. They can be simple expressions or compound expressions.

One special form of the cond statement involves the use of else. We had three clauses in our zero? function, but only wanted two different values returned. What we really want to say is ``if the argument to the function is 0, then return 1, otherwise return 0''. We can express this like so:

(define (zero? x)
   (cond ((= x 0) true)
         (else false))))

The else is a predicate that always evaluates to >true, thus if none of the predicates before it are true, the consequent associated with the else clause is always evaluated. Note that it is syntactically incorrect to enclose the else in parentheses.

Another conditional statement that can be used much like that cond is called if. Using the if statement, we could rewrite the zero? predicate like this:

(define (zero? x)
   (if (= x 0) true false)))

The if operator takes three arguments, a predicate, a consequent, and an alternative. The predicate is evaluated, if it is true the consequent is evaluated and its value returned, if the predicate's value is false, the alternative is evaluated.

We can combine predicates to form complex predicates using the boolean operators and, or, and not. The boolean operators work just like arithmetic operators, using prefix notation. You must take care that the predicate is something that can be determined algorithmically. In other words, we have to tell the computer how to determine the boolean value of something. This shouldn't surprise you since computer science is concerned with ``how to'', not ``what is''. For example, in English we may say ``if we owe the customer change, ...''. In a computer language, we must tell the computer how to determine if there is any change needed. We might write

(if (> (- amountTendered cost) 0) <consequent> <alternative>)

to accomplish this algorithmically. Here's another example using the cond statement. This function determines the sign of its argument and returns -1, 0, or 1 respectively. Note that this is not a predicate (and hence no ?) since it doesn't return a simple yes or no answer.

==> (define (sign x)
    (cond ((< x 0) -1)
          ((> x 0) 1)
          (else 0))))
SIGN
==> (sign -2)
-1
==> (sign 4)
1
==> (sign 0)
0

Comments

Like C and Java, Scheme uses both single-line and block comments.

Single line comments are specified using a semicolon:

(define pi 3.14) ; OK, it's sloppy a sloppy approximation

Block comments are specified using #| and |#:


    #|
        Here is my code for homework #1
        by Jean Nyess
    |#

Questions

These questions are for your review and entertainment:

Write an expression that compares two variables and returns true if they are both zero and false otherwise. Note that there are at least two ways to do this: one using the boolean function and and one using addition. Try writing the function both ways. Does it surprise you that there is more than one way to do the same thing?

Last updated at 9:39 pm on Friday, September 17, 2004.