Scheme Programming/Numbers and Expressions

From Wikibooks, open books for an open world
Jump to navigation Jump to search
Scheme Programming
 ← Simple Expressions Numbers and Expressions Further Maths → 

In this section, we'll continue to work with numbers, since they're familiar and easy to reason about. We'll also introduce the Scheme type system and consider more carefully how Scheme expressions are evaluated.

Types[edit | edit source]

First, though, what do we mean when we say a Scheme object is a "number" or a "boolean"? These names denote the type of an object. Very generally, knowing an object's type gives us information about what we can do with it. If we know that and both have type boolean, we know that the AND operation of logic is defined on and ; that is, the value of ( AND ) will be meaningful. We say that such a meaningful expression is well-typed. If, on the other hand, has type number, we have no way to evaluate ( AND ), because we don't know how to make sense of AND unless both of its arguments are booleans. In this case, the expression is ill-typed and its value is undefined.

Scheme is a strongly-typed language, which means that ill-typed expressions are forbidden; evaluating one will cause Scheme to report an error.[1] For example, we can expect Scheme to reject the following expression:

> (+ 10 #t)
;; Error: (+) bad argument type - not a number: #t

From the error message, we can infer that the Scheme procedure + expects its arguments to be numbers. Since #t is a boolean, the expression (+ 10 #t) is ill-typed; no meaningful value can be obtained, so the execution of the program halts. In this way, Scheme prevents further surprises which we might encounter were execution to continue with a bogus value.

How do we get type information about Scheme objects? Scheme types are defined by type predicates. These are procedures which, given any Scheme object as an argument, return #t if the object has a specific type, and #f otherwise. By applying a type predicate foo? for a type foo, then, we can divide the set of all Scheme objects into objects of type foo and the rest.

So far, we've worked with numbers and booleans, which have the type predicates number? and, as you might have guessed, boolean?.

> (number? 10)
#t
> (number? #t)
#f
> (boolean? 3)
#f
> (boolean? #f)
#t

Scheme guarantees[2] that the basic types, including numbers and booleans, are disjoint. This means, for example, that no Scheme object is a number and a boolean; it might be one or the other or neither, but it cannot be both. In type-predicate terms, there's no Scheme object x such that (number? x) and (boolean? x) are both #t.

We won't use basic type predicates like number? too often in this book, but it's important to understand how they define the Scheme type system. They are used constantly in core Scheme and library procedures, for example, to ensure that arguments are well-typed.

Numbers[edit | edit source]

We looked at several examples of simple numerical programs in the previous section. So far, though, the programs we've seen have only used integers. Scheme has a rich system of number types, called the numerical tower, which lets us compute with rational, real, and complex numbers.

> (+ 9/10 4/5)
17/10
> (* 2.423 -5.39245)
-13.06590635
> 2.762e8
276200000.0      ; 2.762 * 10^8
> (- 4+2i 1+7i)
3-5i
> (* 3+5i (+ 1.3 (/ 3 2)))
8.4+14.0i

As these examples show, Scheme also gives us many ways to write numbers. Rational numbers are written in the form a/b, reals can be written in exponential ("scientific") notation as men (which gives the value ), and complex numbers are written in the rectangular form a+bi (or a-bi), where a is the real part and b the imaginary part.[3]

As we see in the final, nested example, Scheme allows us to mix different kinds of numbers without having to manually convert them to a common form.

Scheme also provides a wealth of numerical procedures. Here are a few examples:

> (gcd 36 60)  ; greatest common divisor
12
> (min 3 4.7 2.1)  ; min gives the minimum of its arguments
2.1
> (log 18)  ; natural logarithm of 18
2.89037175789616
> (floor-remainder 15 8)  ; integer division remainder (modulo)
7

See R7RS § 6.2.6 for a comprehensive list of numerical procedures.

Expressions[edit | edit source]

By this point, we've seen Scheme evaluate a number of expressions (and, hopefully, you've tried them out in your Scheme interpreter). However, we've been vague about the meaning of Scheme expressions. It's easy to guess that (+ 2 3) is evaluated by adding the numbers 2 and 3, but guessing isn't enough when we're faced with complex nesting or expressions containing things less familiar than, say, natural numbers or addition. We need a model of evaluation for the Scheme expressions we've been seeing. What follows is a simplified version, but one that is correct for the programs we'll look at in this chapter.

The expression (+ 2 3) may seem a bit trivial to evaluate, but let's step through it. This expression is an application of the operator + to the operands 2 and 3. To evaluate an application,

  • First, evaluate the operator and operands.
  • Then, apply the procedure which is the value of the operator to the values of the operands.

We saw in the very first example in "A taste of Scheme" that asking Scheme to evaluate a number gives us the number back as the value. This observation gives us the general rule of evaluation for numbers:

Evaluating numbers: Numbers are self-evaluating.

With this rule in hand, it's trivial to evaluate the operands. Now we need the value of +, the operator. This value is a procedure object. This value is opaque; that is, it's a "black box" for performing addition that Scheme gives us, and we can't see its inner workings. We can then apply this value to the values of the operands to obtain 5, the value of the whole expression.

A more interesting example is the expression (* (+ 2 3) (- 7 5)). Here, the operator is * and the operands are (+ 2 3) and (- 7 5). To find the value of this application, we must evaluate these subexpressions, which are themselves applications! Here is one possible sequence of evaluation steps:[4]

(* (+ 2 3) (- 7 5))
  = (* 5 (- 7 5))
  = (* 5 2)
  = 10

More complicated expressions are evaluated by exactly the same process; see exercise 1 below. So long as we are dealing with expressions built entirely out of applications, then, we know how to evaluate them; we recursively apply our evaluation rules until the expression is fully evaluated.

Exercises (Solutions)
  1. Give one sequence of evaluation steps for the following expression.
    (* (- 7 (/ 9 3)) (* 10 (- 15 3) (+ 4 2)))
    

Notes[edit | edit source]

  1. Some popular languages, including JavaScript and PHP, are weakly-typed. Roughly, these languages permit combinations which would be ill-typed in languages with strong typing. This is often accomplished by automatically converting values of one type to those of another; for example, the JavaScript expression 4 + "five" (which combines a number and a character string) evaluates to the string "4five". Here, the numeric operand 4 has been implicitly converted to the string "4". Scheme, like other strongly-typed languages, performs no such magic; values must be converted explicitly.
  2. R7RS § 3.2
  3. Scheme also provides polar notation for complex numbers. We can write r@t to denote the complex number with modulus r and argument t (in radians).
  4. We don't actually know the order in which the operands are evaluated. At the moment, this makes no difference, but it is important to understand that Scheme will evaluate them in some (unspecified) order.