*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

EMail: Jay_Reynolds_Freeman@mac.com.

Programming languages at times need to deal with logic, both to permit programs whose specific purpose is to reason logically, and to permit internal reasoning, within the program, about what to do next. A typical example of the latter might look rather like this, written out more nearly in English than in any programming language, with indentation to make it clear how the decision is structured.

if n is greater than zero do one thing otherwise do some other thing

If that were in Scheme, it might look like this:

(if (> n 0) (do-one-thing) (do-some-other-thing) )

That is an example of an __ if expression__, or an

The first part of our if statement is a ** test**, something whose evaluation gives an answer to a yes-or-no question.
In this example, the question we are concerned with is whether n is greater than zero. Scheme has a procedure
that tells whether one number is greater than another; that procedure's name is ">", and the procedure application

(> n 0)

will return a special Scheme object, "#t", called the ** true
boolean**, if n is greater than zero, and will return another special Scheme object,
"#f", called the

The other two parts of the if expression, which in this case are
"(do-one-thing)" and "(do-some-other-thing)", are respectively called
the __ consequent__ and the

Any Scheme procedure or special form that returns a boolean value is called
a ** predicate**. Predicates are obviously useful when you are writing if
expressions, but there is one more thing to keep in mind about predicates and tests.

** Scheme interprets every Scheme object except the false boolean as being true.** That means that
you can use any Scheme object, or any kind of Scheme expression, as a test, and Scheme will take
the test to be true unless the object or expression evaluates to #f. So for example, all of the
following if expressions will do the same thing; their tests will all evaluate to true, so they
they will all evaluate their consequent -- "(do-one-thing)" -- and return
whatever it returns.

(if (> 1 0) (do-one-thing) (do-some-other-thing) ) (if 42 (do-one-thing) (do-some-other-thing) ) (if (list 1 2 3 4 5) (do-one-thing) (do-some-other-thing) ) (if #t (do-one-thing) (do-some-other-thing) ) (if '() (do-one-thing) (do-some-other-thing) )

If you have any experience with other Lisp-class languages, there is a source of confusion lurking
here. In many other Lisps, the empty list, (), is taken to be false: It acts just like #f.
Scheme doesn't do that. ** In Scheme, the empty list has a logical value of true.**
(There was a long debate about that issue in the Scheme community, but this decision seems
to have been final.)

If you want to try out some if statements, you don't need to bother with creating procedures for "do-one-thing" and "do-some-other-thing". Try cutting and pasting this code directly into Wraith Scheme:

(if (> 1 0) "One is bigger than zero. Phew!" "One is NOT bigger than zero. HORRORS!!" )

Scheme has a lot of predicates. Rather than try to list and describe them all, I am going to tell you in
general what kinds of predicates there are, give a few specific examples, and discuss some of the more
important ones in detail. You can learn more about predicates
from the R5 report or from the Wraith Scheme Dictionary.

First, there are a lot of predicates that take just one argument and tell you something about it. For example, to every different kind of Scheme object there corresponds a predicate that takes one Scheme object and answers the question, "Is this one of those?". We have already seen a few of that kind of predicate.

(list? '(1 2 3)) ;; ==> #t (list? '(1 . 2)) ;; ==> #f (list? 42) ;; ==> #f (list? '()) ;; ==> #t (pair? '(1 2 3)) ;; ==> #t (pair? '(1 . 2)) ;; ==> #t (pair? 42) ;; ==> #f (pair? '()) ;; ==> #f (null? '(1 2 3)) ;; ==> #f (null? '(1 . 2)) ;; ==> #f (null? 42) ;; ==> #f (null? '()) ;; ==> #t

Here are a few more:

(string? "I see the cat!") ;; ==> #t (number? 42) ;; ==> #t (procedure? +) ;; ==> #t (procedure? if) ;; ==> #f ("if" is a special form) (symbol? 'foo) ;; ==> #t

You get the idea.

There are a lot of single-argument predicates for numbers, that report about specific properties of their arguments. Their arguments must in general be numbers, and some of them require specific kinds of numbers for arguments, such as reals or integers. The following examples show some of the error messages that you will see if you provide the wrong kind of argument.

(complex? 42) ;; ==> #t (complex? 2+3i) ;; ==> #t (real? 42) ;; ==> #t (real? 2+3i) ;; ==> #f (rational? 42) ;; ==> #t (rational? 2+3i) ;; ==> #f (rational? 1/2) ;; ==> #t (integer? 42) ;; ==> #t (integer? 2+3i) ;; ==> #f (integer? 1/2) ;; ==> #f (even? 1/2) ;; ==> Oops ... #<Built-in procedure "even?"> applied to (#e0.5): Expected an integer for the argument. Problem: Argument has improper type for this operation. (Resetting) Top-level loop ... (even? 2) ;; ==> #t (even? 1) ;; ==> #f (even? 0) ;; ==> #t (odd? 2) ;; ==> #f (odd? 1) ;; ==> #t (odd? 0) ;; ==> #f (zero? 2) ;; ==> #f (zero? 1) ;; ==> #f (zero? 0) ;; ==> #t (positive? 1+8i) ;; ==> Oops ... #<Built-in procedure "positive?"> applied to (1+8i): Expected a real number for the argument. Problem: Argument has improper type for this operation. (Resetting) Top-level loop ... (positive? 1) ;; ==> #t (positive? 0) ;; ==> #f (positive? -1) ;; ==> #f (negative? 1) ;; ==> #f (negative? 0) ;; ==> #f (negative? -1) ;; ==> #t (positive? (real-part 1-4i)) ;; ==> #t (negative? (imag-part 1-4i)) ;; ==> #t

There are lots of predicates that take more than one argument, for comparing things. The simplest and most familiar of these are for comparing numbers. Thus the predicate "=" takes two or more numbers as arguments, and will return #t if, and only if, all of its arguments are numerically equal.

(= (+ 1 1) 2) ;; ==> #t (= +i (sqrt -1)) ;; ==> #t (= 2 2 2 2 2 2) ;; ==> #t (= 2 2.01) ;; ==> #f (= 2 2 2 2 3 2) ;; ==> #f

Many other programming languages use a "double-equals" operation -- "==" -- to compare numbers. Scheme doesn't do that, it uses just one "=".

Scheme has predicates for the other usual arithmetic comparison operations; namely, ">", ">=", "<=", and "<". They all take two or more arguments, all of which must be real numbers. They all return #t if, and only if, each adjacent pair of arguments satisfies the inequality that the predicate deals with.

(> 3 2) ;; ==> #t (> 2 2) ;; ==> #f (> 2 3) ;; ==> #f (> 5 4 3 2 1) ;; ==> #t (> 5 4 3 3 1) ;; ==> #f (because 3 is not greater than 3) (<= 5.1 2.3) ;; ==> #f (<= 2 3 3 4) ;; ==> #t (>= 5 4 4 3 2 2 1 1) ;; ==> #t

Et cetera.

There are comparison operators for strings and for characters as well, that compare
the text characters of which these things are composed.. They generally
take exactly two arguments. Strings are compared ** lexicographically** --
one string is considered less than another if it would appear first in a
dictionary or in the index of a book. Characters are compared according to their
ordering in the standard ASCII character set. There are variants of these procedures
which are case-independent; these work by converting all capitalized letters to lower
case before performing the comparison. The occurrence of "ci" in the name of a procedure
means that the procedure is

Here are a few examples; see the Wraith Scheme Dictionary or the R5 report for more details.

(string<? "aardvark" "zygomorph") ;; ==> #t (string<? "aardvark" "Zygomorph") ;; ==> #f (string-ci<? "aardvark" "Zygomorph") ;; ==> #t (string<? "aaa" "aaaaaaaa") ;; ==> #t (char<? #\a #\b) ;; ==> #t Note how you write characters in Scheme. (char<? #\A #\b) ;; ==> #f (char-ci<? #\A #\b) ;; ==> #t

It is perhaps counterintuitive that all of the comparison predicates for strings and characters end in "?", but none of the arithmetic comparison predicates do.

There are Scheme predicates for deciding whether Scheme objects that are not
numbers, strings, or characters are equal, but at this point things start to get
complicated. Let me take some examples that use physical objects instead of Scheme
objects to show why.

Suppose you have two copies of the same book. They both have the same content -- the same words and pictures, In that sense they are equal. Yet they are not the same physical object; this one is right here in my hand, while the other one is over there on the table. In that sense, they are different. If someone asked you, "Is this the same book that I saw here yesterday?" you might have to stop and check which kind of equality the questioner had in mind.

Scheme worries about this distinction, and the concern is much the similar. There can be Scheme objects which have the same content -- they are duplicates -- but they are stored at different locations in Scheme memory. For example, consider the following two define statements:

(define a (list 1 2 3)) ;; ==> a (define b (list 1 2 3)) ;; ==> b a ;; ==> (1 2 3) b ;; ==> (1 2 3)

Clearly, "a" and "b" are both lists, and they both have the same content. Yet they are not
the same list! The "list" procedure has been used twice, and each time it is used, it builds
up a ** different** list, at a different location in Scheme memory. Here is some
proof:

(set-car! a 42) ;; ==> #t a ;; ==> (42 2 3) b ;; ==> (1 2 3)

You see, we changed the list that is bound to a, and the list that is bound to b did not change; it must be a different list.

There is one more kind of equality that Scheme worries about. Again, let me give an example using physical objects.

Suppose you have two very well trained sheep dogs. Your two dogs are definitely not the
same physical object, and even if they happen to be identical twins, you would probably not
say that they had the same content -- but you might ask yourself whether their training
was good enough that they had the same ** behavior**.
The answer is probably "no", though a sheep-dog breeder who was trying to pressure you into
making a purchase might tell you otherwise. Yet the point is not whether the answer is yes or no,
the point is that it might be

The behaviors that Scheme worries about are the behaviors of procedures and special forms. Suppose you had two different mathematical ways of solving a particular kind of equation, and you created different Scheme procedures for each of those methods. The procedures would be stored at different locations in Scheme memory, and they would not have the same content; that is, they would contain different sequences of instructions and all. Yet if the mathematics were correct, they would have the same behavior: Both procedures would always get the same, correct answer when they were applied to the same equation.

A very, very, very smart Scheme implementation might sometimes be able to look at two different procedures, stored within its memory, and figure out whether they always gave the same result when applied to the same input data. I hasten to add that Wraith Scheme isn't nearly that smart! Yet the R5 report allows for the possibility of a Scheme implementation being clever enough to decide whether different procedures or special forms are equivalent in that sense, and has predicates for that purpose. In Wraith Scheme, those predicates will always return #f when their arguments are stored at different places in Scheme memory, but that is not a violation of the R5 standard: R5 allows a Scheme implementation to return #f from those predicates if it chooses; for example, if it cannot prove that the arguments have the same behavior. Wraith Scheme simply throws up its paws and refuses even to attempt such a proof.

Scheme uses the term "equivalence" in situations like the previous example. ** Two Scheme
objects which behave the same way when subject to any combination of standard Scheme procedures
and special forms are said to be equivalent.** In most cases, the notion of
equivalence is simple. Two scheme objects are certainly equivalent if they are stored at the
same place in memory -- that means they are the same object. Two numbers are equivalent if
they have the same numerical value, with a waffle about "exact bits" that is described a
few paragraphs below, any two "#t"s are equivalent, and so on. Those are easy, but figuring
out when two procedures are equivalent is a tough job; indeed, it can be shown that in general
you cannot count on finding an answer to the question, "Are these two procedures equivalent?"
So Wraith Scheme has a good rationalization for not trying.

Now for the predicates themselves. The simplest one to understand is "** eq?**", which takes
two Scheme objects as arguments. If the objects are not of the same kind, "eq?" returns
#f. If they are of the same kind, and are of a kind that Wraith Scheme stores in Scheme
memory, "eq?" returns #t if, and only if, both objects are stored at the same memory location.
This is the kind of equality that many other programming languages call "pointer equality".

If the arguments to "eq?" are not a kind of object that Wraith Scheme stores in Scheme memory, "eq" returns
#t if, and only if, their values are equal:
The kinds of standard Scheme object that Wraith Scheme does not store in main memory are
limited; they are the true and false booleans, the empty list, and all numbers except
for complex numbers that have nonzero imaginary part. Scheme numbers include a bit
that tracks whether the mathematical operations used in a calculation have been able
to produce an exact result. The "eq?" procedure will not return #t for numeric arguments
unless both have the same ** exact bit**.

(eq? 1 1) ;; ==> #t (eq? 1+i 1+i) ;; ==> #f -- different memory locations (define my-complex 1+i) ;; ==> my-complex (eq? my-complex my-complex) ;; ==> #t (eq? "cat" "cat") ;; ==> #f -- different memory locations (eq? (list 1 2 3) (list 1 2 3)) ;; ==> #f -- different memory locations

Predicate "** eqv?**" is the one that tests for "equivalence" in the sense
described above. It does what "eq?" does, except that it checks for arithmetic equality
of complex numbers with nonzero imaginary part, including the exact bit, and returns
#t if these all match.

It is this predicate that would be worrying about whether procedures were equivalent, if Wraith Scheme were very, very, very smart. As is, Wraith Scheme's "eqv?" only reports two procedures as being equivalent if they are the same procedure; that is, if they are stored at the same place in Scheme memory.

(eqv? 1 1) ;; ==> #t (eqv? 1+i 1+i) ;; ==> #t (define my-complex 1+i) ;; ==> my-complex (eqv? my-complex my-complex) ;; ==> #t (eqv? "cat" "cat") ;; ==> #f -- different memory locations (eqv? (list 1 2 3) (list 1 2 3)) ;; ==> #f -- different memory locations

Predicate "** equal?**" also takes two Scheme objects as arguments. In comparing for
equality, it investigates the structure of those Scheme objects that are stored
in memory. It compares strings on a character-by-character basis, compares
each element of pairs (which we have studied) and of vectors (which we have not),
and uses "eqv?" to compare objects which are none of these.

In comparing the structure of pairs and vectors, "equal?" acts recursively: If the car or the cdr of a pair is itself another pair, "equal?" will compare the car and cdr of that pair, and so on, as long as necessary.

(equal? 1 1) ;; ==> #t (equal? 1+i 1+i) ;; ==> #t (define my-complex 1+i) ;; ==> my-complex (equal? my-complex my-complex) ;; ==> #t (equal? "cat" "cat") ;; ==> #t (equal? (list 1 2 3) (list 1 2 3)) ;; ==> #t

Note that two separate instances of (list 1 2 3) are neither "eq?" nor "eqv?", because they are stored at different locations in Scheme memory, but they are "equal?", because they have the same content. Predicate "equal?" checks for equality of content rather than equality of memory location, and it checks all the content it can possibly ferret out, all the way down the list, and into sublists, and so on.

As a rule of thumb, objects are "equal?" if they print the same way.

Comparisons of the "eq?", "eqv?" and "equal?" varieties are used in several other
Scheme procedures, which are arguably predicates but which I shall discuss here in any case.
There are two families of these; both families have to do with finding things in
lists.

The first family of procedures deals with the question, "Is there an object that is the same as this one in this list?" We have just talked about three possible ways to decide whether two objects are the same, and have described three Scheme predicates -- "eq?", "eqv?" and "equal?" that perform the appropriate comparisons. So I hope you are not surprised that there are three different procedures for finding things in lists, that make the same distinctions in notions of sameness.

The first is "** memq**", which compares things in the same way that "eq?" does.
It takes two arguments; the first is the object it is looking for, and the second is
a list. The "memq" procedure starts at the front of the list, and goes down the list
one item at a time, looking for a match. If it finds one, it returns the rest of the list,
starting from the object it found. If it does not find one, "memq" returns #f.

(memq 2 '(1 2 3 4)) ;; ==> (2 3 4) (memq 2 '(1 2 2 2 4)) ;; ==> (2 2 2 4) (memq 5 '(1 2 3 4)) ;; ==> #f

Procedures "** memv**" and "

The second family of procedures is "** assq**", "

An alist is a list of lists. It is a rather old data structure that is a slight generalization of
what in modern terminology would be called a ** list of key-value pairs**. What these
predicates do is go down the alist, looking for a list therein, whose car matches the object
they are looking for. When they find such a list, they return it, and if they do not find a match,
they return #f.

(assq 2 '((1 fee) (2 fie) (3 foe) (4 fum))) ;; ==> (2 fie) (assq 2 '((1 fee) (2 fie) (2 foe) (2 fum))) ;; ==> (2 fie) (assq 5 '((1 fee) (2 fie) (2 foe) (2 fum))) ;; ==> #f (assq 2 '((1 fee foo) (2 fie bar) (3 foe baz) (4 fum mumble))) ;; ==> (2 fie bar)

The idea of a list of key-value pairs is that the first item in any given sublist is the key, and the second is the value. If someone gives you a key, such as "2", you can use "assq" or one of its friends to find the entire key-value pair, and from that get the value -- which in the first example immediately above is "fie".

All of the last six procedures may be considered predicates in the sense that they return a value that is taken as truth if they find what they are looking for, but return #f if they find nothing; however, the value returned is not #t, it is something specifically useful in the context of the search.

Procedure "** not**" inverts a logical value

(not #f) ;; ==> #t (not #t) ;; ==> #f (not 42) ;; ==> #f

Special forms "** and**" and "

(and) ;; ==> #t (or) ;; ==> #f

With one or more arguments, "and" evaluates its arguments one at a time, starting with the first. If it finds an argument that evaluates to #f, "and" returns #f immediately. If none of its arguments evaluate to #f, "and" returns whatever the last argument did.

(and 1 2 3) ;; ==> 3 (and 1 #f 2) ;; ==> #f

With one or more arguments, "or" evaluates its arguments one at a time, starting with the first. If it finds an argument that does not evaluate to #f, "or" immediately returns whatever that argument did. If all of its arguments evaluate to #f, "or" returns #f.

(or 1 2 3) ;; ==> 1 (or #f 2 3) ;; ==> 2 (or #f #f #f) ;; ==> #f

These special forms are useful when their arguments are not simple things like numbers, but procedure applications that have side effects. You use "and" when what you want to have happen is "do this, and if it worked, do that, and if that worked, do something else ...". You write procedures that attempt the various tasks, and that return a true value or #f, depending on whether the task succeeded or failed. If you "and" those procedures together, the "and" will stop invoking the procedures as soon as one fails.

You use "or" similarly, when what you want is "try this, and if it didn't work, try that, and if that didn't work, try something else ...".

-- Jay Reynolds Freeman (Jay_Reynolds_Freeman@mac.com)