One of a series of tutorials about Scheme in general
and the Wraith Scheme interpreter in particular.
Copyright © 2011
Jay Reynolds Freeman,
all rights reserved.
Personal Web Site: http://JayReynoldsFreeman.com
In previous tutorials, I have discussed procedure applications and the evaluation of procedure arguments, but let's review.
In all the instances of procedure application that we have seen so far, the first item in the list has been a symbol -- a name of something -- which has had a particular procedure bound to it. Thus in the procedure application
the first item is the symbol
and we can see that this symbol is bound to a procedure merely by typing it by itself and pressing "return".
sqrt ;; ==> #<Built-in procedure "sqrt">
The first item in a procedure application does not have to be a symbol, however. Here is a somewhat unrealistic example to make the point. We are going to create a boolean variable, "use-plus?", then write a procedure application that uses the value of that boolean to decide whether to add two numbers or subtract them.
(define use-plus? #t) ;; ==> use-plus? use-plus? ;; ==> #t ((if use-plus? + -) 2 3) ;; ==> 5 (set! use-plus? #f) ;; ==> #t use-plus? ;; ==> #f ((if use-plus? + -) 2 3) ;; ==> -1
In the two instances of the procedure application "((if use-plus? + -) 2 3)", the first item in the procedure application is a use of the "if" special form; namely "(if use-plus? + -)". That special form examines the current value of "use-plus?" in order to decide what to do. If "use-plus?" is true, the "if" special form evaluates its third argument -- the symbol "+" -- and returns its value, which is the Scheme procedure that does addition. If "use-plus?" is false, the "if" special form similarly returns the Scheme procedure that does subtraction. So the overall procedure application, "((if use-plus? + -) 2 3)", may either add or subtract its arguments, depending on the value of "use-plus?".
Let's go through part of that example more carefully. If "use-plus?" is #t, then the "if" special form in essence converts
((if use-plus? + -) 2 3)
(#<Built-in procedure "+"> 2 3)
so the numbers get added up. (You cannot actually type "#<Built-in procedure "+">" into Scheme, I am just making the point that "if" has evaluated its third argument.)
In such circumstances, we say that Scheme evaluates the first item in the procedure application recursively, or by recursive descent: It keeps applying the rules for evaluating expressions and their arguments until there is nothing left to evaluate, going into the details of the expression as much as necessary.
The same idea works for all the other items of a procedure application. They are evaluated using recursive descent as well. Here is a Scheme expression for the hypotenuse of a right triangle whose sides have lengths 3 and 4, formatted to show that it involves nested procedure applications.
(sqrt (+ (* 3 3) (* 4 4) ) )
Let's see how recursive descent works in this more complicated example. The "sqrt" procedure takes just one argument; namely
(+ (* 3 3) (* 4 4) )
so of course Scheme has to evaluate it. That argument, however, is a procedure evaluation in its own right, of the "+" procedure, so Scheme has to evaluate each of the arguments to "+" as well. They are
(* 3 3)
(* 4 4)
Each of those is in turn a procedure application of "*", so that Scheme has to evaluate those procedure applications as well. They give results
Scheme passes the results to the "+" procedure, as its arguments
(+ 9 16 )
The "+" procedure returns
so that what the "sqrt" procedure finally sees is
(sqrt 25 )
which is 5.
The same evaluation mechanism, including the part about recursive descent, also works for special forms, except that as I said in an earlier tutorial
Thus you will recall that the "set!" special form does not evaluate its first argument.
There are two other things to remember about procedure applications:
Thus for example
(1 2 3) ;; ==> Error message: 1 Problem: Attempt to apply a non-procedure. (Resetting) Top-level loop ... () ;; ==> Error message: Problem: Reader encountered an unquoted empty list. (Resetting) Top-level loop ...
One of the interesting things about Scheme is that all procedure applications, and all of the built-in special forms, have the same syntax: They all look like lists, the first item of the list always evaluates to something that has to do with what is going on, and the rest of the items of the list are always arguments or some other kind of data. The syntax of Scheme is extremely regular.
This similarity of syntax is true for new procedures and special forms that you create, as well as for the ones that are part of R5 Scheme itself. You might create thousands of new procedures and special forms for a project, yet the project as a whole will "look like Scheme", and you or anyone else will be able to use all of the new material the same way -- with the same syntax -- as the standard Scheme procedures. This quality of a language, of being able to extend it and still use the same syntax, is sometimes called isosyntactic extensibility.
Whether regular syntax and isosyntactic extensibility are good things or bad ones is in great part a matter of opinion. There are plenty of people who don't agree with me, but reasons why I think these qualities might be good things include:
-- Jay Reynolds Freeman (Jay_Reynolds_Freeman@mac.com)