for
CSCI 301: Great Ideas in Computer Science
(c) 1993, 1994, 1995 John E. Howland, All Rights Reserved
Department of Computer Science
Trinity University
Stadium Drive
San Antonio, Texas 78212-7200
Internet: jhowland@ariel.cs.trinity.edu
When we ask this question, consider that we don't have car science or telephone science, dishwasher science, etc. Perhaps we should ask whether or not computer science is subsumed by such classical disciplines as mathematics, physics, neuro-science, electrical engineering, linguistics, logic and philosophy. In fact, some computer scientists consider this to be the case and consider it their goal to so thoroughly integrate the various parts of computer science back into its parent disciplines so that it no longer has a separate identity as a separate science. This somewhat controversial view is not widely held.
In the previous paragraph a number of terms were used which you may not be familiar with. Do not worry about this now as definitions for most of these will be given later.
Using this definition one might consider some of the sub areas of computer science to involve the design, structure, analysis, efficiency and correctness of algorithms, the mathematical properties of algorthms, the data they manipulate, the languages in which they are implemented and the machines on which they are interpreted.
Finally, one might study the limitations of algorithms.
You will need to make a little effort to develop some elementary programming skills so that you can carry out simple laboratory experiments as well as be able to read and understand expositions written in Scheme. However, it should be emphasized that the primary focus of our programming skills will be to learn to read and understand existing programs rather than learing to create our own independent solution to programming problems.
(+ 2 3)is an example of a simple Scheme sentence. It is verbalized as "plus 2 3". We don't pronouonce the parentheses unless we have a compound sentence which contains another sentence imbedded within as a subordinate clause. Most Scheme sentences are imperative, that is, they convey some action to be performed by the reader. In the above example, the reader is directed to add 2 and 3 producing a result of 5.
A Scheme computer system is in a repetitive process of reading the user's sentence, evaluating that sentence (performing the imperative action of the sentence) and printing the result of the sentence. We say that the Scheme system has a REPL (Read, Evaluate and Print Loop).
The general form of a Scheme sentence is:
<object>or
(<verb> [<object>] ...)The elipsis ... is a meta notation which means that the preceeding item may appear one or more times in a sentence. Actually, a sentence may consist of just a verb. An example of an English sentence consisting of just a verb might be:
Go!
In 1.3.2, the square brackets around <object> are a meta notation which signify that what is enclosed in brackets appears optionally. <verb> and <object> are also meta notation variables which stand for the kind of object which would appear at that place in a sentence. The other symbols such as ( and ) must appear at the beginning and end of every sentence.
We may form compound sentences, that is, an object in a sentence may itself be a sentence as in the following example:
(* 2 (+ 2 3))This could be verbalized as "times 2 and the quantity plus 2 3". Just as is the case with the English language, compound Scheme sentences are harder to verbalize. The parentheses surrounding the subordinate clause are prounounced as "the quantity". Notice also that there is an implied order in this imperitave sentence. The subordinate sentence (+ 2 3) must be read or performed before the times can be performed. In the compound sentence
(* (- 4 5) (+ 3.2 2))both the (- 4 5) and (+ 3.2 2) must be performed before the times can be performed, however, there is no specification of the order of the minus or the plus. In fact, they could be performed in parallel on a computer system which supports parallel computation.
The objects of a sentence are either nouns or pronouns. A noun in Scheme is a constant value whose meaning is universally understood and never changes. A noun is a constant value. Examples of nouns are 2 (the number), "21" (a string of two characters, namely 2 followed by 1. There are other types of nouns as we shall see later.
A pronoun in Scheme is a symbol which has been bound (defined) to a noun. A pronoun may be used in place of a noun in sentences. For example,
(define t1 5.52)defines a pronoun t1. Once so defined, t1 may be used as a noun as in the sentence
(+ 3 t1)The value of a pronoun may change from time to time, depending on the binding, just as the pronoun she takes on different meanings depending on the context.
A symbol may be bound to a verb creating what might called a proverb. For example we define
(define plus +)Then we write (plus 3 4). A proverb may be used in place of a verb in sentences. This is probably an unfamiliar concept in natural language since English does not have a mechanism to define new verbs. The Scheme notation allows us to define pronouns and proverbs with equal ease. We could even write
(define minus +)but this would likely lead to confusion. We need to exercise common sense in the choice of symbols used to define pronouns and proverbs to improve the readability of our Scheme sentences.
Pronouns and proverbs are the key to abstraction in Scheme. They allow the binding of a complex value or verb to a name which can then be used to form more complex objects.
Notice that define is not a verb, for if it were, then according to the evaluation rule 1.3.3,
(define a (+ 2 3))requires that the pronoun a be bound to a noun but the whole purpose of define is to provide bindings of pronouns and proverbs. Scheme solves this problem by allowing a collection of special syntaxes which deviate from the ordinary evaluation rule. Special syntax forms (sometimes called special forms) use a keyword in place of a verb and each special syntax has its own evaluation rule. Fortunately there are just a few special forms which must be learned. define is the first of the special forms.
(lambda (x) (* x x))makes a verb (unnamed) which is applied to a single object, called x. The action of this verb is to produce a noun by multiplying x by x. We could use this verb in a sentence without giving it a name, i. e. without defining a proverb, as:
((lambda (x) (* x x)) 5)This sentence would produce a noun of 25. Although it can be done, it is much more common to define a verb and define its proverb all in a single compound sentence becuase we usually need to use a verb more than just one time. Such definitions allow us to use the proverb to refer to the verb. Also, if the verb being defined is quite complex, the binding of a proverb is a means of abstracting that complexity thereby simplifying any subsequent references to it in other sentences. If we only need to use a verb one time in a sentece, then it makes some sense to not bother to define a proverb for that verb.
If it is likely that we will need to square many numbers we make the following definition.
(define square (lambda (x) (* x x)))Then the sentence
(square 5)produces the noun 25.
The general form of the lambda special syntax is:
(lambda <object-list> <action-sentence>)The <object-list> is a list of symbols, one symbol for each of objects which the verb will operate on. The <action-sentence> is a sentence which describes the imperative action the verb will perform.
(if (< 3 4) (* 2 3) (- 5 6))This form evaluates to 6. While
(if (> 3 4) (* 2 3) (- 5 6))evaluates to -1. It should be noted that (- 5 6) is not evaluated in the first if example while (* 2 3) is not evaluated in the second if example. While it is not obvious, it should be noted that if cannot be a verb, for if it were, then according to our evaluation rule 1.3.3, both (* 2 3) and (- 5 6) would need to be evaluated in both if examples given above and this violates our goal of conditionally performing one or the other (but not both) of these actions.
The general form of the if sentence is:
(if <condition-sentence> <true-sentence> <false-sentence>)Consider the following definition for the verb maximum which uses the if special syntax.
(define maximum
(lambda (x y)
(if (> x y) x y)))
(maximum
3 4) evaluates to 4, while (maximum 5 4) evaluates to
5.With this definition, the verb maximum is an abstraction of the process of taking the maximum of two numbers. Suppose we wish to compute the maximum of 3 numbers. We could try to work out a compound sentence which uses two or more if's, but there is another easier way which makes use of the maximum abstraction. First, consider a related problem. We know how to add two numbers a and b; (+ a b). When we need to sum three numbers a, b, and c, we could first sum a and b and then add c. This would be written as (+ (+ a b) c) in Scheme. This same approach may be used in the problem of finding the maximum of three number, that is, first use the new verb maximum to find the the largest of the first two, then apply maximum again to find the maximum of this result and the third. Here is the solution writen in Scheme.
(define max3
(lambda (x y z)
(maximum (maximum x y) z)))
Notice
the structural similarity to the solution of adding three numbers; only the
verb changes.
(quote (a 2 3 10 b))produces a data list of 5 items. The first is the symbol a, then the numbers 2 3 10, and finally the symbol b. A short-hand notation for the above quote is:
'(a 2 3 10 b)'<object> is fully equivalent to (quote <object>), in fact most Scheme readers transform '<object> into (quote <object>) without letting the user ever see the keyword quote.
Notice that the elements of a list of data items may themselves be lists, etc. For example:
(quote ((a b) def 2 (4 5.3)))is a list of 4 items, the list consisting of 2 symbols a and b, the symbol def, the number 2 and the list of two numbers 4 and 5.3 .
(car '(a b c))evaluates to the symbol a. It is a error to attempt to apply the verb car to an empty list.
(car '())produces an error.
The verb cdr produces a result of the list of all elements but the first of its object.
(cdr '(a b c))evaluates to (b c).
You may find your Scheme to be a bit more readable if you make the following definitions:
(define first car) (define rest cdr)We call the verbs car and cdr list accessor verbs because they perform the action of accessing the fundamental parts of a list.
The origin of the names car and cdr goes back to the very early days of computing. The Scheme notation is considered to be a dialect of the LISP [McC 60] notation. LISP stood for LISt Processing notation. Among programming languages, LISP is predated only by the ALGOL, Fortran and COBOL languages. The first implementation of LISP was done on the IBM 700 series of computers. This implementation used the address portion of a memory cell to store the location of the car of a list while the decrement portion of a cell contained the location of the cdr of a list. The names car (Contents of Address field of Register) and cdr (Contents of Decrement field of Register) were chosen from the names of the IBM machine instructions used to access the the address and decrement portion of a cell.
To obtain the second element of a list, one would first use the cdr verb and then apply the car verb to that result. For example,
(car (cdr '(a b c)))evaluates to the symbol b.
If we make the following definition,
(define cadr
(lambda (x)
(car (cdr x))))
then
(cadr '(a b c))is the second element b.
Similarly we could (and most Scheme systems do predefine) define verbs such as caddr, the car of the cdr of the cdr, etc. While such conventions provide convenient writing rules, learning to pronounce these verbs adds a new dimension to the meaning of the LISP language family.
(cons 'a '(b c)) ==> (a b c)We read "==>" used above as the sentence on the left evaluates to the item on the right. Similarly:
(cons 2 '()) ==> (2) (cons '(1 2) '(3 4)) ==> ((1 2) 3 4)If the second object given to the verb cons is always a list, then the result of cons is always a list. We call such a list a proper list. This means that if we repeatedly apply the verb cdr to a proper list, eventually the result of so doing will be an empty list. We call this process cdring down the list. cdring down a list is a fundamental approach in solving problems which require performing some action of every item of a list.
(cdr '(a b c)) ==> (b c) (cdr (cdr '(a b c))) ==> (c) (cdr (cdr (cdr '(a b c)))) ==> ()If a proper list has n elements, then the nth cdr of that list will be empty.
There is a verb, null? which, when applied to a proper list, will return #t (if the list is empty) or #f (if the list is not empty. The nouns #t and #f are Scheme representations of true and false. We say null? is a predicate, that is, it is a verb which evaluates to either #t or #f.
(null? '(1 2 3)) ==> #f (null? '()) ==> #tThere are some equations which can be written down which show the relationship between car, cdr and cons.
(cons (car x) (cdr x)) ==> xand given two Scheme items a and b:
(car (cons a b)) ==> a (cdr (cons a b)) ==> b
We begin the solution by observing that if the list, ls, is non-empty, then the solution can be expressed as (+ (car ls) (list-sum (cdr ls))). We call this type a solution the divide and conquer approach. That is, we have reduced the solution of the original problem to solution of two problems (an addition and summing a smaller lis of numbers) each of which is smaller than the original problem. Moreover, one of the sub-problems is identical (except for summing a smaller list) to the original problem. This means we can use the same solution to that sub-problem as we did on the original problem. The only thing that is left is to decide what to return as an answer when list-sum eventually attempts to compute the sum of an empty list. How about zero?
Consider the following definition for list-sum.
(define list-sum
(lambda (ls)
(if (null? ls)
0
(+ (car ls) (list-sum (cdr ls))))))
(list-sum '(1 2 3 4)) ==> 10
(list-sum '()) ==> 0
Most
Scheme systems allow tracing of function execution. We do this as follows:
(trace list-sum) ==> #<unspecified> (list-sum '(1 2 3 4)) Entry (list-sum '(1 2 3 4)) |Entry (list-sum '(2 3 4)) | Entry (list-sum '(3 4)) | Entry (list-sum '(4)) | |Entry (list-sum '()) | |==> 0 | ==> 4 | ==> 7 |==> 9 ==> 10Tracing is turned off by
(untrace list-sum)
factorial (0) = 1
factorial (n) = n * factorial (n - 1) , for n >0.
This leads us to the Scheme definition:
(define factorial
(lambda (n)
(if (= n 0)
1
(* n (factorial (- n 1))))))
(factorial 0) ==> 1
(factorial 4) ==> 24
(factorial 6) ==> 720
(trace factorial) ==> #<unspecified>
(factorial 7)
Entry (factorial 7)
|Entry (factorial 6)
| Entry (factorial 5)
| Entry (factorial 4)
| |Entry (factorial 3)
| | Entry (factorial 2)
| | Entry (factorial 1)
| | |Entry (factorial 0)
| | |==> 1
| | ==> 1
| | ==> 2
| |==> 6
| ==> 24
| ==> 120
|==> 720
==> 5040
Notice
the similarity between the list-sum and factorial verbs.
(= 2 3) ==> #f =? ==> #<primitive-procedure => (= 3 3.0) ==> #t (eq? 3 3.0) ==> #f (eqv? 3 3.0) ==> #f (equal? 3 3.0) ==> #fExamples 1.3.15 emphasize that = and =? should be used to compare numbers. Generally speaking, eq? will only return #t when eqv? returns #t. eq? may produce different results from eqv? under certain special cases such as
(eqv? "" "") (eq? "" "")eq? produces a result of #t if the two objects are actually the same object. For example:
(define plus +) (eq? plus +) ==> #t (eq? '(a b c) '(a b c)) ==> #fequal? is the least restrictive of the comparison predicates. Generally, equal? returns #t if the objects look or print the same.
(equal? '(a b c) '(a b c)) ==> #t
A Scheme program consists of one or more Scheme expressions. A Scheme computer system usually operates using a person/machine dialog, that is, the system waits for an expression to be typed. Once an expression has been entered, the system evaluates that expression and prints its result and then waits for the next expression. We call this the read-eval-print loop of the Scheme system.
Examples:
(+ 3 4) a (* 3 (/ 4 5)) (fact 100)
If the first item of the sentence is not a verb, then it must be special; otherwise the sentence results in an error. Each special form has its own rule of evaluation. Some of the more common special forms are listed below.
Following are some commonly used verbs. In the Scheme notation, lines containing ";" have comentary information. The ";" and all characters on that line following are ignored by a Scheme system. The "==>" should be read as "produces" or "yields". This notation is used to show the result which a Scheme system will produce when given the expression on the left.
;+ add (+ 2 3) ==> 5
;- subtract (- 2 3) ==> -1
;* multiply (* 4 .5) ==> 2.0
;/ divide (/ 1 9) ==> .1111111111
;expt power (expt 2 4) ==> 16
;sqrt square root (sqrt 2) ==> 1.4142135623730951
;< less than (< 2 3) ==> #t
;= equal to (= 2 3) ==> #f
;<= less or equal (<= 2 2) ==> #t
;> greater than (> 2 3) ==> #f
;>= greater or equal (>= 5 4) ==> #t ;car first element of a list (car '(a b c)) ==> a
;cdr remaining elements of a list (cdr '(1 2 3)) ==> (2 3)
;cons list constructor (cons 'a '(2 3)) ==> (a 2 3)
;null? predicate for empty list (null? (cdr '(a))) ==> #t
;list? predicate for a proper list (list? '((1 2) 3 4)) ==> #t
; length list length (length '(a b c (d e))) ==> 4
;list-ref kth element of a list (list-ref '(1 2 a b) 2) ==> a
;append append elements of lists (append '(a) '(y)) ==> (a y)
;list create a list from arguments (list 2 9 2) ==> (2 9 2) ;reverse reverse elements of a list (reverse '(1 (2 3) 4)) ==> (4 (2 3) 1)
Following is a listing of a few of the special forms.
Special Form: define
(define symbol expr)Evaluate expr and bind its value to symbol.
Examples:
(define a (+ 2 (* 3 4))) a ==> 14 (define plus +) plus ==> <procedure +>Special Form: quote
(quote expr)Return expr as data without evaluating expr.
Examples:
(quote (a b c)) ==> (a b c) (quote +) ==> +A shorthand notation for
(quote (a b c)) is '(a b c)Special Form: lambda
(lambda list-of-symbols rule-expr)Create a function having list-of-symbols as args and use rule-expr to compute value of the function.
Examples:
(lambda (x y) (+ x y)) ==> an unnamed function which adds its 2 arguments (define plus (lambda (x y) (+ x y))) (plus 3 4) ==> 7Special Form: unbounded lambda
(lambda symbol rule-expr)Create a function having a single argument, symbol, and use rule-expr to compute the value of the function. This function takes a variable number of arguments which are evaluated and bound to symbol before evaluating rule-expr.
Examples:
(define list (lambda x x)) (list 1 2 3) ==> (1 2 3) (list (* 3 4) 5) ==> (12 5) (list) ==> ()Special Form: if
(if cond-expr true-expr false-expr)Evaluate cond-expr; if #t, then evaluate true-expr, but do not evaluate false-expr. If cond-expr evaluates to #f, then evaluate false-expr, but do not evaluate true-expr.
Examples:
(if (< 2 3) (* 3 4) 'hi) ==> 12 (if (> 2 3) (* 3 4) 'hi) ==> hiSpecial Form: and
(and expr1 expr2 ...)The expressions are evaluated left to right. The value of the first expression that evaluates to #f is returned. Any remaining expressions are not evaluated. If no expressions evaluate to #f, then the value of the first expression which evaluates to true is returned. If there are no expressions, #t is returned.
Examples:
(and (< 2 3) (> 4 5)) ==> #f (and (< 2 3) (< 4 5) (< 6 7)) ==> #tSpecial Form: or
(or expr1 expr2 ...)The expressions are evaluated from left to right and the value of the first expression that evaluates to true is returned. Any remaining expressions are not evaluated. If no expressions evaluate to true, then #f is returned.
Examples:
(or (> 4 5) (< 5 4)) ==> #f (or (< 4 5) (> 4 5)) ==> #tSpecial Form: let
(let binding-expr body-expr)The binding-expr should be of the form
((symbol1 expr1) (symbol2 expr2) ...)expr1, expr2, ... are evaluated in some order and bound to symbol1, symbol2, ..., then body-expr is evaluated in the context of these definitions and the resulting value is returned from the let.
Examples:
(let ((a 2) (b 3)) (* a b)) ==> 6 (let ((a 2) (b (+ a 3))) (* a b) ==> unbound symbol, aSpecial Form: let*
(let* binding-expr body-expr)The binding-expr should be of the form
((symbol1 expr1) (symbol2 expr2) ...)expr1, expr2, ... are evaluated in left to right order and bound to symbol1, symbol2, ..., then body-expr is evaluated in the context of these definitions and the resulting value is returned from the let*.
Examples:
(let* ((a 2) (b 3)) (* a b)) ==> 6 (let* ((a 2) (b (+ a 3))) (* a b) ==> 10Special Form: letrec
(letrec binding-expr body-expr)The binding-expr should be of the form
((symbol1 expr1) (symbol2 expr2) ...)symbol1, symbol2, ... are bound to undefined values, next, expr1, expr2, ... are evaluated in an arbitrary order and assigned to symbol1, symbol2, ..., then body-expr is evaluated in the context of these definitions and the resulting value is returned from the letrec. This allows the definition of recursive functions within a letrec and these procedures may be evaluated in the body-expr.
Example:
(letrec ((fact (lambda (x)
(if (< x 2)
1
(* x (fact (- x 1)))))))
(fact 6)) ==> 720
The
definition of fact exists only within the letrec and is not
available elsewhere.Special Form: begin
(begin expr1 expr2 ...)The expressions are evaluated in left to right order and the value of the last expression is returned.
Examples:
(begin (* 2 3) (< 3 4)) ==> #t (begin (display "Hi") (* 3 4)) ==> Hi12Special Form: cond
(cond clause1 clause2 ...)Where each clause is of the form
(test-expr expr1 expr2 ...)The last test-expr may be the keyword else.
The test-expr's of the successive clauses are evaluated in sequence until a test-expr evaluates to true. Then the corresponding expr's are evaluated and the value of the last is returned as the value of the cond. If none of the test-expr's evaluate to true and the last test-expr is else, then the corresponding expr's are evaluated in sequence and the value of the last is returned as the value of the cond otherwise the value of the cond is unspecified.
Examples:
(cond ((> 3 2) 'greater)
((< 3 2) 'less)) ==> greater
(cond ((> 3 3) 'greater)
((< 3 3) 'less)
(else 'equal)) ==> equal
Special
Form: case
(case key clause1 clause2 ...)Where each clause is of the form
((datum ...) expr1 expr2 ...)The last clause may be an "else clause" of the form
(else expr1 expr2 ...)The case form is evaluated as follows: key is evaluated and then compared, using eqv?, to each datum. If key is equivalent to some datum, then the corresponding expr's are evaluated in sequence and the value of the last expr is returned as the value of the case expression. If an else clause is present and if key is not equivalent to any datum, then the else clause expr's are evaluated in sequence and the value of the last one is returned as the case value. If an else clause is not present and key is not equivalent to any datum, then the value of the case expression is unspecified.
Examples:
(case (* 2 3) ((2 3 5 7) 'prime) ((1 4 6 8 9) 'composite)) ==> composite (case (car '(c d)) ((a e i o u) 'vowel) ((w y) 'semivowel) (else 'consonant)) ==> consonant
(+ 2 3)is an example of a simple program which adds 2 and 3 to produce a result of 5. As an experiment, write several short programs utilizing some of the verbs from Section 1.4.2.
The special keyword lambda is used to create new verbs. For example,
(define plus (lambda (x y) (+ x y)))defines a verb plus which does the same thing as the verb +. In this simple case, we could have written
(define plus +)to achieve the same result.
We can create nouns which are lists of items. To do this we use the special keyword quote. quote returns its object as a datum. For example,
(quote (1 2 3 4 5)) ==> (1 2 3 4 5)quote is very useful syntax because it allows the use of the same syntax for data as is used for programs. quote allows the building of very flexible data models for computer science purposes since this is, as we shall see when we discuss computer organization, precisely the way a real computer's memory is used to store both programs and data. In fact, when we look inside the memeory of a real computer, we cannot distinguish between programs and data. Each looks the same as the other. We have to have some other knowledge of the uses of various areas of memory inorder to make the distiction between the two.
We can use both define and quote to make the following compound sentence:
(define data (quote (1 2 3 4 5)))This creates a pronoun data which is bound to the noun (1 2 3 4 5). There is a short-hand notation for quote.
(quote (1 2 3 4 5)) is the same as '(1 2 3 4 5)
Just as sentences may have items which themselves are sentences as shown in the following example,
(+ (* 3 4) (- 4 5))nouns may have items which themselves are data items as in the following example,
'(1 2 (3 4) (a bc d))The latter example is a list of four items, 1, 2, the list of two items 3 and 4, and the list of three items containing the symbols a, bc and d.
[Cli 91] Clinger, William and Rees, Johathan, editors, "Revised4 Report on the Algorithmic Language Scheme", SIGPLAN Lisp Pointers, November 1991.