3  Simple Data, Simple Functions

Scheme has the usual classes of atomic data: numbers, booleans, and characters. It also has symbols. More importantly, it comes with a number of mechanisms for constructing values from values: strings, which are constructed from characters, vectors, and structures. We discuss each of these classes of values and show how to write some simple programs with them.

3.1  Numbers, Booleans, Symbols, Characters

NUMBERS are the most unusual of Scheme's atomic classes of data. Scheme supports a complex hierarchy of numbers. The hierarchy includes integers, rationals, reals, and the complex numbers. Each of these classes comes in two flavors: exact and inexact. If a built-in numeric operation must approximate a mathematical number, the number is tagged as inexact.

Rational arithmetic is arbitrarily precise. That is, Scheme can represent all integers, no matter how large they are, as long as they fit into the physical computer. A number such as

1312783617286378126378137827823347832647823647823647

is perfectly fine. In addition, fractions can have arbitrarily large numerators or denominators. Rational operations, such as addition, multiplication, division, and so on, produce precise results.

Defining functions on numbers is straightforward:

;; Number Number  -->  Number
;; to compute the volume of a cylinder 
(define (volume-cylinder radius height)
  (* (area-disk radius) height))

;; Number  -->  Number
;; to compute the area of a disk 
(define (area-disk radius)
  (* pi radius radius))  

We recommend to write down at least two lines of comments per function. The first specifies the ``type'' of the function (how many and what kind of arguments it consumes, what it produces); the second explains what it computes. As the example shows, functions can refer to each other as needed. In particular, volume-cylinder calls area-disk to compute the area of its base.

BOOLEANS introduce the means for posing true-false questions. The two Boolean constants are #t and #f. What makes Booleans interesting are comparison operators, (class) predicates, and conditionals. Here are two expressions that compare numbers:

(<= 1 3)

which is true, and

(> 1 3)

which is false. Scheme's syntax also makes it possible to compare several numbers at once:

(< 1 3 8)

This checks whether 1 is less than 3 and whether 3 is less than 8. Both claims are true so the entire expression is true. If we had insisted on comparing these numbers the way conventional languages do, we could have written

(and (< 1 3) (< 3 8))

which also shows that Scheme also has ordinary Boolean-valued expressions.

Let's use this trick to write a small, useful function:

;; Number Number Number  -->  Number
;; check whether x is between left and right
(define (in-range left x right)
  (<= left x right))

In a program for playing ``shoot the ufo'' you can use the function to check (partially) whether a shot has hit the ufo; in a program for monitoring a patient's blood pressure, the function is useful to check whether the measured value is in a tolerable interval.

Another important use of Booleans is for distinguishing different classes of Scheme values. Every class comes with a predicate so that programs can identify to which class a value belongs. Such a predicate consumes a Scheme value and produces #t if the value belongs to the class; if not, it produces #f. For example,

(complex? 1+3i)

is true, but

(rational? 1+3i)
and
(complex? #t)

evaluate to false. Similarly,

(boolean? #t)
and
(boolean? #f)

are both true, but

(boolean? 1)

is false. We discuss the exact nature of these predicates in section 7.

Once we have the answer to a true-false question, we can use a conditional expression to compute a value in case the answer was true and a different one in case the answer was false:

;; Number  -->  (union -1 0 +1)
;; to compute the sign of a number 
(define (sign0 x)
  (cond
    [(> x 0) +1]
    [(= x 0) 0]
    [(< x 0) -1]))

A cond expression consists of an arbitrary number of BRANCHES. The first expression in each branch is a Boolean expression -- a so-called test or question -- and the other one computes the answer if the corresponding test is the first one that is true. This means that (sign0 10) is +1 and (sign0 -10) is -1.

One unusual aspect of conditionals in Scheme is that they actually distinguish #f from all other values, not just #t. While this sounds strange at first, we will see that this kind of branching works well in Scheme.

Although cond expressions are convenient for most situations, Scheme provides a number of alternative conditional expressions. The most useful to know are: if, a two-branched conditional; when, a one-branched conditional; unless, another one-branched conditional; and case, a many-branched dispatch-oriented conditional for symbols. We shall use such alternative conditionals without much ado when appropriate and trust that you can look up what they mean in HelpDesk if there are any questions.

SYMBOLS are atomic values. A symbol represents some piece of information in the real world, but just like for numbers, there is no a priori meaning. It is up to the programmer (and sometimes the program's user) to relate symbolic data and real-world information. The programmer should make the meaning obvious in a specific context. For example, 'east should refer to the direction where the sun rises, 'professor should be the title of a person teaching and researching at a university, and 'temperature should not stand for the distance between two points.

While symbols are of little interest as individual values, they play an important role in constructed values, mostly as tags that identify other parts of the value. The key function for that purpose is symbol=?, which compares the identity of two symbols. Thus,

(symbol=? 'a 'b)

is false, and

(symbol=? 'a 'a)

is true. A shorter name for symbol=? is eq?. Well, almost.

Scheme also provides case, a conditional that dispatches on symbols:

;; Direction is one of: 
;; 'left 'right 'up 'down 

;; Direction  -->  Number
;; translate a directional symbol into a verbal command
(define (issue-command d)
  (case d
    [(left) -10]
    [(right) +10]
    [(up down) (error 'issue-command "illegal command")]))

Depending on the value of the dispatch expression, which is just the variable d in this sample function, the case expression evaluates one of its conditional lines. The test in each case line is a sequence of symbols -- without the quote mark -- and the answer is a Scheme expression. The test in the last line here takes care of two different symbols; the others can match at most one.

CHARACTERS represent the keyboard characters (and a few more). The Scheme way of writing down a character constant is cumbersome, e.g.,

#\a    #\A     #\space     #\( 

Characters aren't particularly interesting by themselves, but they make up strings and are important in that context.

Help Desk: Numbers, booleans, symbols, and characters come with other built-in functions. For numbers, Scheme has many trigonometric built-ins. Booleans are equipped with the usual Boolean combinators: and, or, and not. Symbols come with the case conditional.

When in doubt, guess the name of a built-in function and type it into DrScheme's Interactions window. If DrScheme responds without error, the function exists. Otherwise, consult the Help Desk to find out whether a function already exists. For questions on expressions forms, such as conditionals, it is always best to consult the Help Desk. 

3.2  Strings

A string is a sequence of keyboard characters, enclosed in double quotation marks:

 "hello world"
 "good bye, world"
 "he said \"to be or not to be\" and left."

The backslash serves as the escape character so that the last string contains a string-quote. We can insert a backslash into a string by escaping it with a backslash, too.

We can build a string from characters and extract characters from a string. Both

 (make-string 3 #\a)

and

 (string #\a #\a #\a)

construct the string "aaa". With string, we can also create strings from distinct characters. The built-in function string-ref extracts a character at a certain index from a string.

With just these built-ins, we can already define a function that reverses a string with three characters:

;; String  -->  String
;; reverse a string of size 3; "abc" becomes "cba"
(define (swap3 s)
  (string (string-ref s 2) (string-ref s 1) (string-ref s 0)))

With this, we can reverse strings with three characters, such as "dad", "mom", "aha", and "mad".

Strings come with additional built-in operations. The built-in function string-length counts the number of characters in a string; and string-append concatenates as many strings as it is given. Hence, the following function creates strings that are n characters wide by adding trailing spaces, if needed:

;; Number String  -->  String
;; to create a string of n characters, 
;; by truncating the tail or adding spaces as needed 
(define (fill-or-truncate n s)
  (cond
    [(>= (string-length s) n) (substring s 0 n)]
    [else (string-append s (make-string (- n (string-length s)) #\space))]))

3.3  Vectors

Vectors are like strings, except that they compound arbitrary values, not just characters. To construct a vector, we can use vector and make-vector, which are like string and make-string. For example,

(vector #\a #\b #\c)

creates a vector with three characters, and

(make-vector 10)

creates a vector with ten 0s. Vectors may also contain strings and vectors, not just atomic values, e.g.,

(vector "matthew" "robby" "shriram")
or
(vector (vector 1 2 3) (vector 4 5 6) (vector 7 8 9))

Better still, Scheme vectors are heterogeneous, that is, the values in a vector may come from many different classes of values. Here is a vector

 (vector 'a 0 (vector #\p #\l #\1) #t)

that contains a symbol, a number, a vector, and a Boolean.

Like strings, vectors also come with a host of built-in operations. Two important ones are vector-ref for accessing a particular item via its numeric index and vector-length for determining the number of items in a vector. See the Help Desk for more information.

3.4  Structures

A programmer can also create an entirely new class of compound values. These are called structures. A structure definition does not define a structure but means for creating a structure and for working with it. A structure is well-suited for representing information that consist of many distinct pieces. For example, a structure for representing people may consist of three distinct pieces of information: their name, gender, and yob description:

(define-struct person (name gender yob))
;; Person = (make-person String String Number)

By convention, every structure definition is accompanied by a comment that specifies the name of a class of values and how to construct an element of the class.

A structure definition does not create any structures. Instead, it is just a concise definition for a bunch of special functions. Specifically, a structure definitions defines:

  1. a constructor (e.g., make-person), which consumes as many values as there are fields in the structure definition and constructs a structure;

  2. a predicate (e.g., person?), which identifies values that were built with the constructor;

  3. as many selectors as there are fields in the structure definition (e.g., person-name, person-gender, and person-yob), which give access to the fields of a structure.

Hence, basic programming with structures differs little from basic programming with strings or vectors. We use functions to create structures, test for them, and extract their constituents.

Note: no existing predicate produces #t for a value of the new class of structures, only the predicate that the structure definition introduces.

3.5  Our First Program

It's time to begin writing our first program. The goal is to implement a little game of UFOs and things. Our first goal is to get the UFO to move across some canvas:

That is, we want a program that creates a small, square canvas and then repeatdely draws a UFO that is moving across the canvas. To indicate how time passes, the program also displays the current ``time'' in the upper left hand corner.

(define-struct ufo (pos vel))
;; UFO = (make-ufo Posn Posn)

;; Number  -->  UFO
(define (ufo-create n)
  (make-ufo (make-posn n 0) (make-posn 0 UFO-DROP)))

;; UFO  -->  UFO
(define (ufo-move u)
  (make-ufo
   (make-posn (+ (posn-x (ufo-pos u)) (posn-x (ufo-vel u)))
              (+ (posn-y (ufo-pos u)) (posn-y (ufo-vel u))))
   (ufo-vel u)))
  
;; ColorSymbol UFO  -->  true
(define (ufo-paint ufo)
  (local ((define p (ufo-pos ufo)))
    (and
     (draw-solid-disk p UFO-RADIUS UFO-COLOR)
     (draw-solid-rect 
      (make-posn (- (posn-x p) UFO-HALF) (- (posn-y p) UFO-CENTER))
      UFO-WIDTH UFO-HEIGHT UFO-COLOR))))

;; UFO  -->  true
(define (ufo-erase ufo)
  (local ((define p (ufo-pos ufo)))
    (and
     (draw-solid-disk p UFO-RADIUS BACKGROUND)
     (draw-solid-rect 
      (make-posn (- (posn-x p) UFO-HALF) (- (posn-y p) UFO-CENTER))
      UFO-WIDTH UFO-HEIGHT BACKGROUND))))

(define UFO-DROP 5)
(define UFO-RADIUS 8)
(define UFO-WIDTH  32)
(define UFO-HALF   (/ UFO-WIDTH 2))
(define UFO-HEIGHT 4)
(define UFO-CENTER (/ UFO-HEIGHT 2))
(define UFO-COLOR 'yellow)

Figure 1:  UFOs

Figure 1 contains the core of the program. It consists of one structure definition, five function definitions, six variable definitions, and two expressions. Also, it relies on one built-in class of structures -- posn -- and a library for drawing pictures on a canvas.

Let's discuss the built-in structures and the library first. Most Scheme languages in DrScheme even provide posn structures for representing positions on a canvas:

(define-struct posn (x y))
;; Posn = (make-posn Number Number)

A posn represents a point that is x pixels to the right and y pixels to the bottom from the northwest corner of a canvas. Naturally negative numbers denote the opposite direction.

Using posns, we can also draw pictures on the canvas. More precisely, we add the draw.ss library -- choose Language | Add Teachpack) to add it -- and use its functions. We discuss those later.

Now we can turn our attention to the problem itself. Imagine a real UFO flying across the sky. A physicist thinks of the UFO as a single point and a velocity, which describes how the UFO moves in one step. A Scheme programmer can represent such a UFO in several different ways but the most natural representation is a structure with two fields: one for the UFO's current position and one for its velocity:

(define-struct posn (x y))
;; Posn = (make-posn Number Number)

Here we have chosen to represent both the current position and the velocity as a posn structure, because both represent pairs of numbers.

Take a look at this example:

(make-ufo (make-posn 150 100) (make-posn -10 +10))

This UFO is currently at a location that is 150 pixels to the left and 100 pixels below the northwest corner of the canvas. In one step, it moves 10 pixels to the left and 10 pixels down. The result is this UFO:

(make-ufo (make-posn 140 110) (make-posn -10 +10))

This last observation suggests a function for computing a one-step move:

;; UFO  -->  UFO
;; move the UFO by one step 
(define (ufo-move b)
  (local ((define p (ufo-pos b))
          (define v (ufo-vel b)))
   (make-ufo (make-posn (+ (posn-x p) (posn-x v))
                        (+ (posn-y p) (posn-y v)))
             (ufo-vel b))))

This function consumes a UFO and produces a UFO, with an example given in the comment section. The velocity part of the new UFO is the same as the old one, but the position part is the result of adding the x portions and the y portions of the two posn structures, respectively.

A good Schemer should also turn examples into automated tests. At a minimum, we suggest to add tests like this to the bottom of a file:

"testing move"

(equal? 
  (move (make-ufo (make-posn 150 100) (make-posn -10 +10)))
  (make-ufo (make-posn 140 110) (make-posn -10 +10)))

The function equal? compares two values, piece by piece, which means that the expression produces true if the expected value is the one that the function computes. Developing such tests in parallel to the function is a good idea. When you change the function later, press execute and run the test suite. More about tests later.

Once we have chosen a representation for UFOs and know how to compute one move, we can begin to think about the visual aspects of the program. The program in figure 1 uses five functions from our drawing teachpack:

  1. draw-solid-disk : Posn Number ColorSymbol  -->  true, for drawing a disk with given center, radius, and color;

  2. draw-solid-string : Posn String  -->  true, for drawing a string at a given point;

  3. draw-solid-rect : Posn Number Number ColorSymbol  -->  true, for drawing a solid rectangle with given northwest corner, width, height and color; and

  4. sleep-for-a-while : N  -->  true, which adds a small pause to the program.

Each of these, except for the last one, consumes positions and draws geometric shape on a canvas. The last one stops the program for a while, so that changing the configuration on a canvas becomes observable.

Now that we know about this teachpack, we can study the graphical part of the program. In our program, the visible shape of the UFO is a disk crossed with a rectangle. This looks a bit like the old-fashioned UFOs; modern models are probably more aerodynamic. In any case, this explains the ufo-paint function.

;; UFO Number  -->  true
(define (run b t)
  (and (one-moment b t) (run (ufo-move b) (+ t DELTA))))

;; UFO Number  -->  true
(define (one-moment b t)
  (and (ufo-paint b) (announce-draw t)
       (sleep-for-a-while DELTA)
       (ufo-erase b) (announce-erase t)))

(define DELTA 1)
(define BACKGROUND 'blue)

;; run, program, run:
(start 300 300)
(draw-solid-rect (make-posn 0 0) 300 300 'blue)
(run (make-ufo (make-posn 100 100) (make-posn 1 5)) 0)

Figure 2:  Making a UFO fly

To move a UFO, the program must first erase it from the canvas and then draw it somewhere else. Erasing the UFO means restoring the color that was present before it was drawn. Put differently, the program draws the same shape, but with the BACKGROUND color. Take a look at ufo-erase and compare it to ufo-paint; keep the similarities in mind.

Drawing and erasing announcements naturally proceeds in the same manner:

;; Number  -->  true
(define (announce-draw t)
  (draw-solid-string (make-posn 20 20) (string-append "Time: " ( number--> string t))))

;; UFO  -->  true
(define (announce-erase t)
  (draw-solid-rect (make-posn 0 0) 200 30 BACKGROUND))

With all these preliminaries, we can now study how run and one-moment in figure 2 work. The one-moment function consumes a UFO and a time, draws everything, waits for a bit, and erases everything. The function run also consumes two values: a representation of the UFO and the current time. It uses one-moment to ``flash'' the scenery (UFO and announcement) on the screen for one moment. Then it computes where the UFO is going next, increments the time, and ..., yes, does it all over again. The function calls itself; we say it is recursive. Some people are afraid of recursion, but how else should we express that a function does it all over again? Recursion is natural; don't worry.