3.4.2 Application expressions

Most of the actual work done by a Scheme program is done by application expressions that apply procedures to operands. The expression (+ 1 2) is an ApplicationExpression, consisting of three subexpressions. Although this example is probably simple enough that you can probably guess that it evaluates to 3, we will show in detail how it is evaluated by breaking down into its subexpressions using the grammar rules. The same process will allow us to understand how any expression is evaluated.

The grammar rule for application is:

Expression :: $\Rightarrow$ ApplicationExpression
ApplicationExpression :: $\Rightarrow$ (Expression MoreExpressions)
MoreExpressions :: $\Rightarrow$ $\varepsilon$ | Expression MoreExpressions

This rule produces a list of one or more expressions surrounded by parentheses. The value of the first expression should be a procedure; the remaining expressions are the inputs to the procedure known as operands. Another name for operands is arguments.

Here is a parse tree for the expression (+ 1 2):

Following the grammar rules, we replace Expression with ApplicationExpression at the top of the parse tree. Then, we replace ApplicationExpression with (Expression MoreExpressions). The Expression term is replaced PrimitiveExpression, and finally, the primitive addition procedure +. This is the first subexpression of the application, so it is the procedure to be applied. The MoreExpressions term produces the two operand expressions: 1 and 2, both of which are primitives that evaluate to their own values. The application expression is evaluated by applying the value of the first expression (the primitive procedure +) to the inputs given by the values of the other expressions. Following the meaning of the primitive procedure, (+ 1 2) evaluates to 3 as expected.

The Expression nonterminals in the application expression can be replaced with anything that appears on the right side of an expression rule, including an ApplicationExpression.

We can build up complex expressions like (+ (* 10 10) (+ 25 25)). Its parse tree is:

This tree is similar to the previous tree, except instead of the subexpressions of the first application expression being simple primitive expressions, they are now application expressions. (Instead of showing the complete parse tree for the nested application expressions, we use triangles.)

To evaluate the output application, we need to evaluate all the subexpressions. The first subexpression, +, evaluates to the primitive procedure. The second subexpression, (* 10 10), evaluates to 100, and the third expression, (+ 25 25), evaluates to 50. Now, we can evaluate the original expression using the values for its three component subexpressions: (+ 100 50) evaluates to 150.

Exercise 3.1.  Draw a parse tree for the Scheme expression (+ 100 (* 5 (+ 5 5))) and show how it is evaluated.

Exercise 3.2.  Predict how each of the following Scheme expressions is evaluated. After making your prediction, try evaluating the expression in DrRacket. If the result is different from your prediction, explain why the Scheme interpreter evaluates the expression as it does.

  1. 1120

  2. (+ 1120)

  3. (+ (+ 10 20) (* 2 0))

  4. (= (+ 10 20) (* 15 (+ 5 5)))

  5. +

  6. (+ + \< )

Exercise 3.3.  For each question, construct a Scheme expression and evaluate it in DrRacket.

  1. How many seconds are there in a year?

  2. For how many seconds have you been alive?

  3. For what fraction of your life have you been in school?

Exercise 3.4.  Construct a Scheme expression to calculate the distance in inches that light travels during the time it takes the processor in your computer to execute one cycle. (A meter is defined as the distance light travels in $1/299792458^{th}$ of a second in a vacuum. Hence, light travels at $299,792,458$ meters per second. Your processor speed is probably given in gigahertz (GHz), which are 1,000,000,000 hertz. One hertz means once per second, so 1 GHz means the processor executes 1,000,000,000 cycles per second. On a Windows machine, you can find the speed of your processor by opening the Control Panel (select it from the Start menu) and selecting System. Note that Scheme performs calculations exactly, so the result will be displayed as a fraction. To see a more useful answer, use (exact- \> inexact Expression) to convert the value of the expression to a decimal representation.)