M03: Simple Data

The term Boolean comes from the name of the British mathematician George Boole, who defined an algebra on these values.

You may see #true or #t instead of true and #false or #f in place of false. They mean the same thing and are interchangeable except that our Style Guide says you should always use true and false. Check your language settings in DrRacket. See M02, slide 7 .

There is more than one way to write this code.

The practice of only evaluating as many arguments as necessary is sometimes called “short circuiting”.

It’s made possible by the fact that all of the arguments to and must be true in order for the whole expression to be true. If we find even one argument that is false, the whole expression will be false.

or is similar except that all the arguments must be false for the whole expression to be false; if we find even one argument that is true then the whole expression will be true.

In the first example, a computer can determine if a number is odd or greater than 2 quickly and easily. In contrast, determining if a number is prime may involve a huge number of division operations making it a very slow test. In this case, placing the fast tests first causes the program to run faster.

The following stepper shows the short-circuit evaluation but replaces prime? with a simpler test.

In the steep? and not-steep? examples, the expressions are logical opposites. For any pair of values for delta-x and delta-y exactly one of the two functions will be true and the other will be false.

steep? avoids division by zero because or stops evaluating arguments (and thus doesn’t reach the division by zero) when it finds that the first one is true – and thus the whole expression must be true.

Similarly, the and in not-steep? stops evaluating arguments when it finds that one is false – and thus the whole expression must be false.

Puzzled by the third substitution rule? Watch the video!

Video: Download m04.80_trace_and

The substitutions rules enforce short-circuiting behaviour. If the first clause is true, it goes on to verify the rest of the arguments. If the first clause is false, the answer will be false no matter what the rest of the arguments are, so it simply returns false.

Work through (and (= 3 3) (> 7 4) (< 7 4) (> 0 (/ 3 0))) by hand first. Then compare here to verify your understanding:

Here’s the second example:

Trace by hand first. Then compare here to verify your understanding:

Warning: The stepper that is built into DrRacket uses different rules that are more complex than ours. CS135 will always use the rules outlined here instead of the rules used by DrRacket.

The following video introduces conditional expressions, the key tool in Racket that allows us to vary the execution of the program depending on the conditions it encounters.

It uses a slightly more complex example with four question/answer pairs.

Video: Download m04.50_cond

The code shown on the slide would normally be included in a function.

(define (ssqw x)
  (cond
    [(< x 0) 0]
    [(>= x 1) 1]
    [(< x 1)
     (sqr (sin (* x pi 0.5)))]))

cond is a special form. Even though it looks like a function, it does not fully evaluate its arguments like a function would.

Examples of properly nested brackets: [()]. Improperly nested brackets: [(]] or [(]).

What’s the error? Step through this example to see.

Remember: the question/answer pairs are considered in order, top to bottom, and it stops as soon as it finds a question which evaluates to true.

else will sometimes hide an error. Consider using else with the buggy code on the previous slide. The bug would have gone unnoticed more easily.

Remember to choose the left-most subexpression to simplify – means that the question part of a cond’s question/answer pair will always be reduced to either true or false before we apply one of the three rules for cond.

These three rules are “context sensitive”. The rule to apply depends on the context. Use the first rule if the first question/answer pair evaluated to false. Use the second rule if the first question/answer pair evaluted to true. Use the third rule if the first question/answer pair is else.

Remember that cond is a special form. It looks like a function application but the arguments are not necessarily evaluated. In this case the question argument is evaluated but the answer argument is not.

Trace by hand first, then check your understanding with the stepper.

The code shown here is a straight-forward (and correct!) implementation of the conditions shown in the graphic.

But when (>= mark 40) is evaluated in the second question/answer pair, we already know that mark is at least 40. Because of Racket’s top-to-bottom evaluation of a cond, we cannot reach the second question/answer pair unless mark is at least 40. We don’t need to test it again.

Similarly, we cannot reach the third question/answer pair unless mark is at least 50 (and therefore don’t need to test again).

Code that takes advantage of these observations is on the next slide.

Note that the original code will produce the correct answer if the order of the question/answer pairs is rearranged. The revised code depends on the order.
Rearrange it and you’ll get wrong answers.

Note that after5? is a Bool. It is either true or false, exactly what is needed to answer the question in the cond’s question-answer pair.

Students sometimes write code to check which value a Bool has. For example, (boolean=? after5? true) is true if after5? is true; it’s false if after5? is false.

Don’t do this; it is bad style. Just use the Bool directly, as shown in this example.

It is poor style to put a cond as the answer to an else, like in the first version.

If you ever find you have written such code, carefully examine how you can simplify your code to put it together like in the second version.

Note that [else (cond ...)] is different from [else ... (cond ...)]. We’re talking about the first one.

We need to make sure that all of the code in the conditional is tested and thus must choose our test cases carefully with the specific questions in the conditional in mind.

Please watch the video for more details.

Video: Download m04.60_testing

More generally,

• or: enough tests to make the expression true for each clause, and one test that makes the entire or expression false.

• and: enough tests to make the expression false for each clause, and one test that makes the entire and expression true.

  Video: Download m04.65_testing_bools

  

What do we mean by “appropriate constants”?

The numbers 45000, 90000, 0.10, 0.20, 0.30 are “magic numbers”. They should not appear in your functions.

For each such value, define a constant. Use the constant in your functions. Meaningful names help communicate what the constants are used for. “threshold1” or “slope2” could be good constant names.

Here are some tests to help verify your code:

(check-expect (tax-payable 7000) 700)
(check-expect (tax-payable 45000) 4500)
(check-expect (tax-payable 50000) 5500)
(check-expect (tax-payable 90000) 13500)
(check-expect (tax-payable 100000) 16500)

The following comment is a little bit mind-bendy. Feel free to ignore it.

The problem description includes the phrase “as above”, twice. Can you use that to write a version of tax-payable that uses tax-payable as a helper function?

Racket’s grandparent language, Lisp, was created in 1958 largely out of frustration with the limited abilities of existing languages to handle non-numeric data.

symbol=? consumes two symbols and produces a Boolean result.

Comparing symbols for equality is pretty much the only thing we’ll do with them in CS135. That’s pretty limited, computationally! We can do so much more with numbers (addition, multiplication, comparison, etc). But the self-documenting nature of symbols makes them a worthwhile data type to have available.

Technically, these describe lexicographic order . Lexicographic order includes alphabetic order, and also gives an order for all UNICODE characters.

A few examples:

;; Uppercase letters come first.
(string<? "A" "a") ⇒ true

;; Ordering works in any language.
(string<=? "ᒌᐦᑫᔨᐦᑕᒼ" "ᒌᐦᑫᔨᐦᒋᑫᐤ") ⇒ true

;; All UNICODE characters are ordered.
(string<? "I❤🍰" "I❤☕") ⇒ false

Racket has many more functions on strings. See the online documentation or use the help desk in DrRacket. There’s no need to memorize all those functions. We’ll use a pretty small subset in CS135.

Symbols are like multiple choice; strings are like short answer.

These twelve rules explain practically everything we’ve learned so far about how Racket evaluates a program. They define precisely what a program means (by reducing it to a sequence of definitions and values).

Remember that when there is a choice of which rule to apply, always take the leftmost one.

Also pay attention to what needs to be reduced to a value first (e.g. arguments to a function application).