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
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 if statement. (Actually, "if" is a special form.) You will note that the "otherwise" is left out -- Scheme doesn't need a word like "otherwise" or "else" to separate the two things to do. You may not recognize the expressions "(do-one-thing)" and "(do-some-other-thing)" as procedure applications, because they do not have any arguments, but that is what they are: Procedures do not have to have arguments, and there is no reason you cannot create procedures "do-one-thing" and "do-some-other-thing", which take no arguments, if you want to.
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 false boolean, if not.
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 alternative. The way if statements work, is that if the test evaluates to true, the if statement evaluates the consequent and returns whatever the consequent does, but if the test evaluates to false, the if statement evaluates the alternative and returns whatever the alternative does. An if statement evaluates either the consequent or the alternative, the one whose value it is going to return. It never evaluates both.
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
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 case-independent.
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 important to ask whether two things have the same behavior. That is a different question from asking whether they are the same object or have the same content.
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 "member" work just like "memq", except that they compare things like "eqv?" and "equal?", respectively.
The second family of procedures is "assq", "assv" and "assoc", which respectively compare things like "eq?", "eqv?" and "equal?". They are for finding things in alists. They all take two arguments; the first is the object to search for, and the second is the alist.
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 "or" are particularly good at performing logical operations and doing useful work at the same time. Each takes a list of zero or more arguments. The values returned for zero arguments are special cases.
(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)