\input bkmacs
\pagetag{\oz}
\photo{Once you see how it works, it's not so mysterious.}{\pspicture{4in}{oz}{oz}{}}
\let\ttfont=\twelvett
\chapter{Example: The\/ {\ttfont Functions} Program}
\chaptag{\fimp}
\normaltext
In Chapter \functions\ you used a program called \ttidx{functions} to explore
some of Scheme's primitive functions. Now we're going to go back to that
program from the other point of view: instead of using the program to learn
about functions, we're going to look at how the program works as an example
of programming with input and output.
\backskipsubhd{The Main Loop}{7}
The {\tt functions} program is an infinite loop similar to Scheme's
\idx{read-eval-print loop}. It reads in a function name and some arguments,
prints the result of applying that function to those arguments, and then
does the whole thing over again.
There are some complexities, though. The {\tt functions} program keeps
asking you for arguments until it has enough. This means that the {\tt
read} portion of the loop has to read a function name, figure out how many
arguments that procedure takes, and then ask for the right number of
arguments. On the other hand, each argument is an implicitly quoted datum
rather than an expression to be evaluated; the {\tt functions} evaluator
avoids the recursive complexity of arbitrary subexpressions within
expressions. (That's why we wrote it:\ to focus attention on one function
invocation at a time, rather than on the composition of functions.)
Here's the main loop:
{\prgex%
(define (\ufun{functions-loop})
(let ((fn-name (get-fn)))
(if (equal? fn-name 'exit)
"Thanks for using FUNCTIONS!"
(let ((args (get-args (arg-count fn-name))))
(if (not (in-domain? args fn-name))
(show "Argument(s) not in domain.")
(show-answer (apply (scheme-procedure fn-name) args)))
(functions-loop)))))
}
\noindent This invokes a lot of helper procedures. {\tt Arg-count} takes
the name of a procedure as its argument and returns the number of arguments
that the given procedure takes. {\tt In-domain?} takes a list and the name
of a procedure as arguments; it returns {\tt \#t} if the elements of the list
are valid arguments to the given procedure. {\tt Scheme-procedure} takes a
name as its argument and returns the Scheme procedure with the given name.
We'll get back to these helpers later.
The other helper procedures are the ones that do the input and output. The
actual versions are more complicated because of error checking; we'll show
them to you later.
{\prgex%
(define (get-fn) ;; first version
(display "Function: ")
(read))
(define (\ufun{get-args} n)
(if (= n 0)
'()
(let ((first (get-arg)))
(cons first (get-args (- n 1))))))
(define (get-arg) ;; first version
(display "Argument: ")
(read))
(define (\ufun{show-answer} answer)
(newline)
(display "The result is: ")
(if (not answer)
(show "#F")
(show answer))
(newline))
}
\noindent (That weird {\tt if} expression in {\tt show-answer} is needed
because in some old versions of Scheme the empty list means the same as {\tt
\#f}. We wanted to avoid raising this issue in Chapter \functions, so we
just made sure that false values always printed as {\tt \#F}.)
\subhd{The Difference between a Procedure and Its Name}
You may be wondering why we didn't just say
{\prgex%
(show-answer (apply fn-name args))
}
\noindent in the definition of {\tt functions-loop}. Remember that the value of
the variable {\tt fn-name} comes from {\tt get-fn}, which invokes {\tt read}.
Suppose you said
{\medskipamount=3pt\prgexskipamount=10pt
{\prgex%
(define x (read))
}
\noindent and then typed
{\prgex%
(+ 2 3)
}
\noindent The value of {\tt x} would be the three element list {\tt
(+~2~3)}, not the number five.
Similarly, if you type ``butfirst,'' then read will return the {\it
word\/} {\tt butfirst}, not the procedure of that name. So we need a way to
turn the name of a function into the procedure itself.
\backskipsubhd{The Association List of Functions}{4}
We accomplish this by creating a huge association list that contains
all of the functions the program knows about. Given a word, such as
{\tt butfirst}, we need to know three things:
\medskip
{\parindent=1em\parskip=8pt
\bb The Scheme procedure with that name (in this case, the {\tt butfirst}
procedure).
\bb The number of arguments required by the given procedure
(one).\footnt{Some Scheme procedures can accept any number of arguments,
but for the purposes of the {\tt functions} program we restrict these
procedures to their most usual case, such as two arguments for~{\tt +}.}
\bb The types of arguments required by the given procedure (one word or
sentence, which must not be empty).
}\medskip
We need to know the number of arguments the procedure requires because the
program prompts the user individually for each argument; it has to know how
many to ask for. Also, it needs to know the domain of each function so
it can complain if the arguments you give it are not in the
domain.\footnt{Scheme would complain all by itself, of course, but would
then stop running the {\tt functions} program. We want to catch the error
before Scheme does, so that after seeing the error message you're still in
{\tt functions}. As we mentioned in Chapter \implhof, a program meant for
beginners, such as the readers of Chapter \functions, should be
especially robust.}
This means that each entry in the association list is a list of four
elements:
% . It looks like this:
{\prgex%
(define *the-functions* ;; partial listing
(list (list '* * 2 (lambda (x y) (and (number? x) (number? y))))
(list '+ + 2 (lambda (x y) (and (number? x) (number? y))))
(list 'and (lambda (x y) (and x y)) 2
(lambda (x y) (and (boolean? x) (boolean? y))))
(list 'equal? equal? 2 (lambda (x y) #t))
(list 'even? even? 1 integer?)
(list 'word word 2 (lambda (x y) (and (word? x) (word? y))))))
}
\noindent The real list is much longer, of course, but you get the
idea.\footnt{Since {\tt and} is a special form, we can't just say
{\prgex%
(list 'and and 2 (lambda (x y) (and (boolean? x) (boolean? y))))
}
That's because special forms can't be elements of lists. Instead, we have
to create a normal procedure that can be put in a list but computes the same
function as {\tt and}:
{\prgex%
(lambda (x y) (and x y))
}
\noindent We can get away with this because in the {\tt functions} program we
don't care about argument evaluation, so it doesn't matter that {\tt and} is
a special form. We do the same thing for {\tt if} and {\tt or}.} It's a
convention in Scheme programming that names of global variables used
throughout a program are surrounded by {\tt *}asterisks{\tt *} to
distinguish them from parameters of procedures.
Here are the selector procedures for looking up information in this a-list:
{\prgex%
(define (\ufun{scheme-procedure} fn-name)
(cadr (assoc fn-name *the-functions*)))
(define (\ufun{arg-count} fn-name)
(caddr (assoc fn-name *the-functions*)))
(define (\ufun{type-predicate} fn-name)
(cadddr (assoc fn-name *the-functions*)))
}
\subhd{Domain Checking}
} % skip kludge
Note that we represent the domain of a procedure by another
procedure.\footnt{The domain of a procedure is a set, and sets are generally
represented in programs as lists. You might think that we'd have to store,
for example, a list of all the legal arguments to {\tt butfirst}. But that
would be impossible, since that list would have to be infinitely large.
Instead, we can take advantage of the fact that the only use we make of this
set is membership testing, that is, finding out whether a particular argument
is in a function's domain.} Each domain-checking procedure, or {\it type
predicate,\/} takes the same arguments as the procedure whose domain it
checks. For example, the type predicate for {\tt +} is
{\prgex%
(lambda (x y) (and (number? x) (number? y)))
}
\noindent The type predicate returns {\tt \#t} if its arguments
are valid and {\tt \#f} otherwise. So in the case of {\tt +}, any two
numbers are valid inputs, but any other types of arguments aren't.
Here's the {\tt in-domain?} predicate:
{\prgex%
(define (\ufun{in-domain?} args fn-name)
(apply (type-predicate fn-name) args))
}
Of course, certain type predicates are applicable to more than one
procedure. It would be silly to type
{\prgex%
(lambda (x y) (and (number? x) (number? y)))
}
\noindent for {\tt +}, {\tt -}, {\tt =}, and so on. Instead, we give this
function a name:
{\prgex%
(define (\ufun{two-numbers?} x y)
(and (number? x) (number? y)))
}
\noindent We then refer to the type predicate by name in the a-list:
{\prgex%
(define *the-functions* ;; partial listing, revised
(list (list '* * 2 two-numbers?)
(list '+ + 2 two-numbers?)
(list 'and (lambda (x y) (and x y)) 2
(lambda (x y) (and (boolean? x) (boolean? y))))
(list 'equal? equal? 2 (lambda (x y) #t))
(list 'even? even? 1 integer?)
(list 'word word 2 (lambda (x y) (and (word? x) (word? y))))))
}
Some of the type predicates are more complicated. For example,
here's the one for the {\tt member?} and {\tt appearances} functions:
{\prgex%
(define (\ufun{member-types-ok?} small big)
(and (word? small)
(or (sentence? big) (and (word? big) (= (count small) 1)))))
}
\noindent {\tt Item} also has a complicated domain:
{\prgex%
(lambda (n stuff)
(and (integer? n) (> n 0)
(word-or-sent? stuff) (<= n (count stuff))))
}
\noindent This invokes {\tt word-or-sent?}, which is itself the type
predicate for the {\tt count} procedure:
{\prgex%
(define (word-or-sent? x)
(or (word? x) (sentence? x)))
}
On the other hand, some are less complicated. {\tt Equal?} will accept any
two arguments, so its type predicate is just
{\prgex%
(lambda (x y) #t)
}
The complete listing at the end of the chapter shows the details of all these
procedures. Note that the {\tt functions} program has a more restricted
idea of domain than Scheme does. For example, in Scheme
{\prgex%
(and 6 #t)
}
\noindent returns {\tt \#t} and does not generate an error. But in
the {\tt functions} program the argument {\tt 6} is considered out of the
domain.\footnt{Why did we choose to restrict the domain? We were trying
to make the point that invoking a procedure makes sense only with appropriate
arguments; that point is obscured by the complicating fact that Scheme
interprets any non-{\tt \#f} value as true. In the {\tt functions} program,
where composition of functions is not allowed, there's no benefit to Scheme's
more permissive rule.}
If you don't like math, just ignore the domain predicates for the
mathematical primitives; they involve facts about the domains of math
functions that we don't expect you to know.\footnt{A reason that we
restricted the domains of some mathematical functions is to protect
ourselves from the fact that some version of Scheme support complex numbers
while others do not. We wanted to write one version of {\tt functions} that
would work in either case; sometimes the easiest way to avoid possible
problems was to restrict some function's domain.}
\subhd{Intentionally Confusing a Function with Its Name}
{\medskipamount=5pt\prgexskipamount=10pt
Earlier we made a big deal about the difference between a procedure and its
name, to make sure you wouldn't think you can apply the {\it word\/} {\tt
butfirst} to arguments. But the {\tt functions} program completely hides
this distinction from the user:
{\prgex%
Function: count
Argument: butlast
The result is: 7
Function: every
Argument: butlast
Argument: (helter skelter)
The result is: (HELTE SKELTE)
}
When we give {\tt butlast} as an argument to {\tt count}, it's as if we'd said
{\prgex%
(count 'butlast)
}
\noindent In other words, it's taken as a word. But when we give {\tt
butlast} as an argument to {\tt every}, it's as if we'd said
{\prgex%
(every butlast '(helter skelter))
}
How can we treat some arguments as quoted and others not? The way this
works is that {\it everything\/} is considered a word or a sentence by the
{\tt functions} program. The higher-order functions {\tt every} and {\tt
keep} are actually represented in the {\tt functions} implementation by
Scheme procedures that take the {\it name\/} of a function as an argument,
instead of a procedure itself as the ordinary versions do:
{\prgex%
(define (\ufun{named-every} fn-name list)
(every (scheme-procedure fn-name) list))
(define (\ufun{named-keep} fn-name list)
(keep (scheme-procedure fn-name) list))
> (every first '(another girl))
(A G)
> (named-every 'first '(another girl))
(A G)
> (every 'first '(another girl))
ERROR: ATTEMPT TO APPLY NON-PROCEDURE FIRST
}
} % end skip kludge
\noindent This illustration hides a subtle point. When we invoked {\tt
named-every} at a Scheme prompt, we had to quote the word {\tt first}
that we used as its argument. But when you run the {\tt functions} program,
you don't quote anything. The point is that {\tt functions} provides an
evaluator that uses a different notation from Scheme's notation. It may be
clearer if we show an interaction with an imaginary version of {\tt
functions} that {\it does\/} use Scheme notation:
{\prgex%
Function: first
Non-Automatically-Quoted-Argument: 'datum
The result is: D
Function: first
Non-Automatically-Quoted-Argument: datum
ERROR: THE VARIABLE DATUM IS UNBOUND.
}
\noindent We didn't want to raise the issue of quoting at that early point
in the book, so we wrote {\tt functions} so that {\it every\/} argument
is automatically quoted. Well, if that's the case, it's true even when
we're invoking {\tt every}. If you say
{\prgex%
Function: every
Argument: first
\ellipsis
}
\noindent then by the rules of the {\tt functions} program, that argument is
the quoted word {\tt first}. So {\tt named-every}, the procedure that
pretends to be {\tt every} in the {\tt functions} world, has to ``un-quote''
that argument by looking up the corresponding procedure.
\subhd{More on Higher-Order Functions}
One of the higher-order functions that you can use in the {\tt functions}
program is called {\tt number-of-arguments}. It takes a procedure (actually
the name of a procedure, as we've just been saying) as argument and returns
the number of arguments that that procedure accepts. This example is
unusual because there's no such function in Scheme. (It would be
complicated to define, for one thing, because some Scheme procedures can
accept a variable number of arguments. What should {\tt
number-of-arguments} return for such a procedure?)
The implementation of {\tt number-of-arguments} makes use of the same a-list
of functions that the {\tt functions} evaluator itself uses. Since the
{\tt functions} program needs to know the number of arguments for every
procedure anyway, it's hardly any extra effort to make that information
available to the user. We just add an entry to the a-list:
{\prgex%
(list '\ufun{number-of-arguments} arg-count 1 valid-fn-name?)
}
\noindent The type predicate merely has to check that the argument
is found in the a-list of functions:
{\prgex%
(define (\ufun{valid-fn-name?} name)
(assoc name *the-functions*))
}
The type checking for the arguments to {\tt every} and {\tt keep} is
unusually complicated because what's allowed as the second argument (the
collection of data) depends on which function is used as the first argument.
For example, it's illegal to compute
{\prgex%
(every square '(think for yourself))
}
\noindent even though either of those two arguments would be allowable if we
changed the other one:
{\prgex%
> (every square '(3 4 5))
(9 16 25)
> (every first '(think for yourself))
(T F Y)
}
The type-checking procedures for {\tt every} and {\tt keep} use a common
subprocedure. The one for {\tt every} is
{\prgex%
(lambda (fn stuff)
(hof-types-ok? fn stuff word-or-sent?))
}
\noindent and the one for {\tt keep} is
{\prgex%
(lambda (fn stuff)
(hof-types-ok? fn stuff boolean?))
}
\noindent The third argument specifies what types of results {\tt fn} must
return when applied to the elements of {\tt stuff}.
{\prgex%
(define (hof-types-ok? fn-name stuff range-predicate)
(and (valid-fn-name? fn-name)
(= 1 (arg-count fn-name))
(word-or-sent? stuff)
(empty? (keep (lambda (element)
(not ((type-predicate fn-name) element)))
stuff))
(null? (filter (lambda (element)
(not (range-predicate element)))
(map (scheme-procedure fn-name)
(every (lambda (x) x) stuff))))))
}
\noindent This says that the function being used as the first argument must
be a one-argument function (so you can't say, for example, {\tt every} of
{\tt word} and something); also, {\it each element\/} of the second argument
must be an acceptable argument to that function. (If you {\tt keep} the
unacceptable arguments, you get nothing.) Finally, each invocation of the
given function on an element of {\tt stuff} must return an object of the
appropriate type:\ words or sentences for {\tt every}, true or false for
{\tt keep}.\footnt{That last argument to {\tt and} is complicated. The
reason we use {\tt map} instead of {\tt every} is that the results of the
invocations of {\tt fn} might not be words or sentences, so {\tt every}
wouldn't accept them. But {\tt map} has its own limitation: It won't
accept a word as the {\tt stuff} argument. So we use {\tt every} to turn
{\tt stuff} into a sentence---which, as you know, is really a list---and
that's guaranteed to be acceptable to {\tt map}. (This is an example of a
situation in which respecting a data abstraction would be too horrible to
contemplate.)}
\subhd{More Robustness}
The program we've shown you so far works fine, as long as the user
never makes a mistake. Because this program was written for absolute
novices, we wanted to bend over backward to catch any kind of strange input
they might give us.
Using {\tt read} to accept user input has a number of disadvantages:
\medskip
{\parindent=1em
\bb If the user enters an empty line, {\tt read} continues waiting silently
for input.
\bb If the user types an unmatched open parenthesis, {\tt read} continues
reading forever.
\bb If the user types two expressions on a line, the second one will be
taken as a response to the question the {\tt functions} program hasn't asked
yet.
}\medskip
\noindent We solve all these problems by using {\tt read-line} to read
exactly one line, even if it's empty or ill-formed, and then checking
explicitly for possible errors.
{\tt Read-line} treats parentheses no differently from any other character.
That's an advantage if the user enters mismatched or inappropriately nested
parentheses. However, if the user correctly enters a sentence as an
argument to some function, {\tt read-line} will include the initial open
parenthesis as the first character of the first word, and the final close
parenthesis as the last character of the last word. {\tt Get-arg} must
correct for these extra characters.
Similarly, {\tt read-line} treats number signs ({\tt #}) like any other
character, so it doesn't recognize {\tt #t} and {\tt #f} as special values.
Instead it reads them as the strings {\tt "#t"} and {\tt "#f"}. {\tt
Get-arg} calls {\tt booleanize} to convert those strings into Boolean values.
{\prgex%
(define (\ufun{get-arg})
(display "Argument: ")
(let ((line (read-line)))
(cond ((empty? line)
(show "Please type an argument!")
(get-arg))
((and (equal? "(" (first (first line)))
(equal? ")" (last (last line))))
(let ((sent (remove-first-paren (remove-last-paren line))))
(if (any-parens? sent)
(begin (show "Sentences can't have parentheses inside.")
(get-arg))
(map booleanize sent))))
((any-parens? line)
(show "Bad parentheses")
(get-arg))
((empty? (bf line)) (booleanize (first line)))
(else (show "You typed more than one argument! Try again.")
(get-arg)))))
}
\hyphenchar\tentt=\count123
\noindent {\tt Get-arg} invokes {\tt any-parens?}, {\tt
remove-first-paren}, {\tt remove-last-paren}, and {\tt booleanize}, whose
meanings should be obvious from their names. You can look up their
definitions in the complete listing at the end of this chapter.
\hyphenchar\tentt=-1
{\tt Get-fn} is simpler than {\tt get-arg}, because there's no issue about
parentheses, but it's still much more complicated than the original version,
because of error checking.
{\medskipamount=5pt
{\prgex%
(define (\ufun{get-fn})
(display "Function: ")
(let ((line (read-line)))
(cond ((empty? line)
(show "Please type a function!")
(get-fn))
((not (= (count line) 1))
(show "You typed more than one thing! Try again.")
(get-fn))
((not (valid-fn-name? (first line)))
(show "Sorry, that's not a function.")
(get-fn))
(else (first line)))))
}
\noindent This version of {\tt get-fn} uses {\tt valid-fn-name?} (which
you've already seen) to ensure that what the user types is the name of a
function we know about.
There's a problem with using {\tt read-line}. As we mentioned in a pitfall
in Chapter \io, reading some input with {\tt read} and then reading the next
input with {\tt read-line} results in {\tt read-line} returning an empty
line left over by {\tt read}. Although the {\tt functions} program doesn't
use {\tt read}, Scheme itself used {\tt read} to read the {\tt (functions)}
expression that started the program. Therefore,
{\tt get-fn}'s first attempt to read a function name will see an empty
line. To fix this problem, the {\tt functions} procedure has an
extra invocation of {\tt read-line}:
{\prgex%
(define (functions)
(read-line)
(show "Welcome to the FUNCTIONS program.")
(functions-loop))
}
} % skip kludge
\subhd{Complete Program Listing}
\bigskip
\listing{functions.scm}
\esubhd{Exercises}
{\medskipamount=4pt
{\exercise
The {\tt get-args} procedure has a {\tt let} that creates the variable {\tt
first}, and then that variable is used only once inside the body of the {\tt
let}. Why doesn't it just say the following?
{\prgex%
(define (get-args n)
(if (= n 0)
'()
(cons (get-arg) (get-args (- n 1)))))
}
}
\solution
The {\tt let} is needed to ensure that the
arguments in the returned list are in the correct order:
Suppose that the user has chosen a two-argument function, so
{\tt functions-loop} calls {\tt get-args} with the argument 2.
{\tt Get-args} will ask
the user for two arguments; suppose that the user types ``the''
as the first response and ``beatles'' as the second response. So {\tt
get-args} {\it should\/} return the list {\tt (the~beatles)}.
Let's trace what happens, using the little people model. Glenda the {\tt
get-args} specialist is hired, with {\tt n} being 2. Since her {\tt n}
isn't 0, she evaluates the {\tt cons} expression.
Assume that in this version of Scheme the arguments to a
procedure are evaluated from right to left. The first thing that happens
is that Glenda hires Gerry, another {\tt get-args} specialist, giving him
an argument of 1. (Later, Glenda will hire a {\tt get-arg} specialist, and
then a {\tt cons} specialist.)
Gerry's job is to get one argument. We'll
take a leap of faith and assume that he correctly reads the first expression
the user typed, namely, the word {\tt the}. So Gerry returns the list {\tt
(the)}.
Now Glenda hires a {\tt get-arg} specialist, who reads {\tt beatles} from
the user. Glenda then hires a {\tt cons} specialist to insert {\tt beatles}
onto the front of {\tt (the)}, giving {\tt (beatles~the)} as her final
answer. But this is wrong! Glenda's list is backwards; instead of
returning {\tt (the~beatles)} she returned {\tt (beatles~the)}.
The {\tt let} in the correct version of {\tt get-args} is to ensure that the
call to {\tt read} happens {\it before\/} the recursive call, thus putting
the elements into the list in the right order.
@
{\exercise
The domain-checking function for {\tt equal?} is
{\prgex%
(lambda (x y) #t)
}
\noindent This seems silly; it's a function of two arguments that ignores
both arguments and always returns {\tt \#t}. Since we know ahead of time
that the answer is {\tt \#t}, why won't it work to have {\tt equal?}'s entry
in the a-list be
{\prgex%
(list 'equal? equal? 2 #t)
}
}
\solution
The {\tt functions} program uses the type-checking predicate by
invoking it with the given arguments. If the entry were {\tt #t}
instead of a function, then invoking it would be an error.
The relevant part of the program is {\tt in-domain?}:
{\prgex%
(define (in-domain? args fn-name)
(apply (type-predicate fn-name) args))
}
\noindent If an entry had {\tt #t} as the type ``predicate,'' then
this would be equivalent to
{\prgex%
(apply #t args)
}
@
} %%% kludge
{\exercise
Every time we want to know something about a function that the user typed
in, such as its number of arguments or its domain-checking predicate, we
have to do an {\tt assoc} in {\tt *the-functions*}. That's inefficient.
Instead, rewrite the program so that {\tt get-fn} returns a function's entry
from the a-list, instead of just its name. Then rename the variable {\tt
fn-name} to {\tt fn-entry} in the {\tt functions-loop} procedure, and rewrite
the selectors {\tt scheme-procedure}, {\tt arg-count}, and so on, so that
they don't invoke {\tt assoc}.
}
\solution
The changed parts of the program are shown here in boldface.
{\prgex%
(define (get-fn)
(display "Function: ")
(let ((line (read-line)))
(cond ((empty? line)
(show "Please type a function!")
(get-fn))
((not (= (count line) 1))
(show "You typed more than one thing! Try again.")
(get-fn))
((not (valid-fn-name? (first line)))
(show "Sorry, that's not a function.")
(get-fn))
(else \pmb{(assoc} (first line) \pmb{*the-functions)}))))
(define (functions-loop)
(let ((\pmb{fn-entry} (get-fn)))
(if (equal? \pmb{(function-name fn-entry)} 'exit)
"Thanks for using FUNCTIONS!"
(let ((args (get-args (arg-count \pmb{fn-entry}))))
(if (not (in-domain? args \pmb{fn-entry}))
(show "Argument(s) not in domain.")
(show-answer (apply (scheme-function \pmb{fn-entry}) args)))
(functions-loop)))))
(define (function-name \pmb{fn-entry})
(car \pmb{fn-entry}))
(define (scheme-function \pmb{fn-entry})
(cadr \pmb{fn-entry}))
(define (arg-count \pmb{fn-entry})
(caddr \pmb{fn-entry}))
(define (type-predicate \pmb{fn-entry})
(cadddr \pmb{fn-entry}))
}
A new selector {\tt function-name} was needed to look for the use
of the word {\tt exit} in place of a function name.
@
{\exercise
Currently, the program always gives the message ``argument(s) not in
domain'' when you try to apply a function to bad arguments. Modify the
program so that each record in {\tt *the-functions*} also contains a
specific out-of-domain message like ``both arguments must be numbers,'' then
modify {\tt functions} to look up and print this error message along with
``argument(s) not in domain.''
}
\solution
First we invent a new selector for the error message:
{\prgex%
(define (domain-error-message fn-name)
(car (cddddr (assoc fn-name *the-functions*))))
}
\noindent We can't just say {\tt caddddr} because those functions
are only defined for up to four steps. For elements this far into
the list, it might be clearer to use {\tt list-ref}:
{\prgex%
(define (domain-error-message fn-name)
(list-ref (assoc fn-name *the-functions*) 4))
}
Now we use the more specific error message.
The changed parts of the procedure are shown here in boldface.
{\prgex%
(define (functions-loop)
(let ((fn-name (get-fn)))
(if (equal? fn-name 'exit)
"Thanks for using FUNCTIONS!"
(let ((args (get-args (arg-count fn-name))))
(if (not (in-domain? args fn-name))
\pmb{(begin} (show "Argument(s) not in domain:")
\pmb{(show (domain-error-message fn-name)))}
(show-answer (apply (scheme-function fn-name) args)))
(functions-loop)))))
}
Of course we also must update the function list itself:
{\prgex%
(define *the-functions*
(list (list '* * 2 two-numbers? "Both arguments must be numbers.")
\ellipsis
(list 'butfirst butfirst 1 not-empty?
"The argument must be a non-empty word or sentence.")
\ellipsis))
}
@
\vfill\eject
{\exercise
Modify the program so that it prompts for the arguments this way:
{\prgex%
Function: if
First Argument: #t
Second Argument: paperback
Third Argument: writer
The result is: PAPERBACK
}
\noindent but if there's only one argument, the program shouldn't say {\tt
First}:
{\prgex%
Function: sqrt
Argument: 36
The result is 6
}}
\solution
The easiest way is not to modify {\tt get-arg} at all:
{\prgex%
(define (get-args n)
(if (= n 1)
(list (get-arg))
(get-args-helper 1 n)))
(define (get-args-helper this total)
(if (> this total)
'()
(begin (display (ordinal this))
(display " ")
(let ((first (get-arg)))
(cons first (get-args-helper (+ this 1) total))))))
(define (ordinal n)
(item n '("First" "Second" "Third" "Fourth" "Fifth")))
}
But it's a little bit of a kludge that {\tt get-args} prints half the prompt
and {\tt get-arg} prints the other half. Instead, we can have {\tt get-args}
figure out what the argument prompt should be, and tell {\tt get-arg} what
to print:
{\prgex%
(define (get-args n)
(if (= n 1)
(list (get-arg "Argument: "))
(get-args-helper 1 n)))
(define (get-args-helper this total)
(if (> this total)
'()
(let ((first (get-arg (word (ordinal this) " Argument: "))))
(cons first (get-args-helper (+ this 1) total)))))
(define (get-arg prompt)
(display prompt)
;;{\rm everything else get-arg used to do$\ldots$}
)
}
@
{\exercise
The {\tt assoc} procedure might return {\tt \#f} instead of an a-list
record. How come it's okay for {\tt arg-count} to take the {\tt caddr} of
{\tt assoc}'s return value if {\tt (caddr~\#f)} is an error?
}
\solution
{\tt Get-fn} invokes {\tt valid-fn-name?} to check whether or not
the requested function is in the a-list. If not, {\tt get-fn} asks
for another function name, so the selectors like {\tt arg-count}
will never be invoked with this nonexistent name.
@
{\exercise
Why is the domain-checking predicate for the {\tt word?} function
{\prgex%
(lambda (x) #t)
}
\noindent instead of the following procedure?
{\prgex%
(lambda (x) (word? x))
}
}
\solution
The domain of the {\tt word?} function is {\it anything,} not just words.
Invoking the {\tt word?} predicate is like asking the question ``is this a
word?'' You can ask that question about anything you like: ``Is {\tt
(1~2~3)} a word?'' --- ``No.'' ``Is {\tt \#t} a word?'' --- ``No.'' ``Is
{\tt banana} a word?'' --- ``Yes.'' So {\it everything\/} is in the domain
of {\tt word?}, and its domain-checking predicate always returns {\tt #t}.
Not every predicate has a domain that includes every possible value.
For example, the domain of the predicate {\tt even?} is just numbers;
you can't ask Scheme the question ``is {\tt banana} even?'' Therefore,
not every predicate will have
{\prgex%
(lambda (x) #t)
}
\noindent as its domain-checking function. But even for {\tt even?}, it
would be silly to use {\tt even?} itself as the domain-checking function.
If the domain of a predicate included only those things for which the
predicate is true, then that predicate could never return {\tt #f}! That
would make it a rather useless predicate. There's a difference between
asking Scheme a question to which it replies ``no'' and asking it a
meaningless question.
% Many people have trouble with the difference between getting back the answer
% ``no'' to a question and asking a meaningless question. If I say ``Is 5
% even?'' the answer is no. But if I ask ``Is {\tt elephant} even?'' it's a
% meaningless question. The domain of the {\tt even?} primitive is just
% numbers. On the other hand, the question ``Is such-and-such a word?'' is
% never meaningless, no matter what object I'm asking the question about.
@
{\exercise
What is the value of the following Scheme expression?
{\prgex%
(functions)
}
}
\solution
Invoking the expression {\tt (functions)} causes a lot of activity to occur,
but the value of that expression is always the string {\tt "Thanks for using
FUNCTIONS!"}
The {\tt functions} procedure has two (or three) expressions in its body, so
Scheme evaluates them all and returns the value of the last one. In this
case, the last one is a call to {\tt functions-loop}, so whatever {\tt
functions-loop} returns, {\tt functions} will return that, too.
{\tt Functions-loop} is recursive. In the recursive case, there's a {\tt
let} with two expressions, so Scheme evaluates them both and returns the
value of the second one. The second expression is a recursive call to {\tt
functions-loop}, so whatever the recursive call returns is what the
outer call will also return. Thus, the string {\tt "Thanks for using
FUNCTIONS!"}, returned by the base case, will be the return value from every
single call to {\tt functions-loop}, including the first one, so it will
also be the return value from {\tt functions}.
@
{\exercise
We said in the recursion chapters that every recursive procedure has to have
a base case and a recursive case, and that the recursive case has to somehow
reduce the size of the problem, getting closer to the base case. How does
the recursive call in {\tt get-fn} reduce the size of the problem?
}
\solution
Since {\tt get-fn} has no arguments, the recursive call is exactly the
same as the original call, so the problem doesn't get smaller. What
saves us is that even the original problem {\it might\/} be solved
without getting smaller at all, because it depends on the behavior of
the human user of the program. At each recursive invocation, the
problem is this: ``If the user enters a correct function, we're done.
If not, try again.'' If the user makes a mistake, then the procedure
calls itself recursively, with exactly the same problem. And, indeed,
this {\it can\/} be an infinite loop, if the user keeps typing incorrect
functions. But as soon as the user enters a correct function, the process
will terminate.
% A call to {\tt get-fn} looks like {\tt (get-fn)}, because the procedure
% takes zero arguments. So the recursive call, {\tt (get-fn)} is exactly the
% same as the original call. There are two ways to think about this.
%
% The first is ``The size of the problem {\it doesn't\/} get smaller.'' Since
% each call to {\tt get-fn} has the same arguments, the problem never changes,
% and there's an infinite loop. Indeed, if you invoke {\tt get-fn} and then
% sit in front of the computer forever typing incorrect functions, the {\tt
% get-fn} procedure will never return a value.
%
% The second way to think about this is ``even though the arguments never
% change, the state of the world changes between recursive calls, so
% eventually the program will return a value.'' In this case, the progress
% made by each recursive call is sort of bizarre: after each time the user
% incorrectly types the name of a function, he or she is more likely to get it
% right the next time.
@
\bye