6.001/Recitation 2

Rob Speer

Contents 1 Brain teaser: Roll your own if 2 Practice with if 3 Recursion review 4 More on special forms 4.1 if just returns a value 4.2 and and or 4.3 So what does define return? 5 Side effects

Brain teaser: Roll your own if

Wouldn't it be nice if everything were made of lambdas? Come up with representations for #t, #f, and if (call them my-true, my-false, and my-if) that don't use any pre-defined functions or special forms.

• You can assume that other functions like = are rewritten to return your new representation.
• Since this isn't a special form, it's okay if both statements in the if get evaluated. In fact, it has to work that way.

Practice with if

The real one, of course.

What do these evaluate to? (In some cases the value depends on x.)

(if #t (+ 1 1) 17)
(if #f #f 42)
(if (> x 0) x (− x))
(if 0 1 2)
(if x 7 (7))

Recursion review

Here's a good way of thinking about writing a recursive procedure, which may help when the procedures get more complicated.

1. "Wishful thinking": suppose you've been given a function that solves almost the whole problem, up to the last step.
2. Use that function.
3. Do the last step.
4. Add a base case.
   • In Which Our Protagonist Learns the Importance of the Base Case

• Write sum-nats, a function that adds the natural numbers up to n, using delayed operations. (So that means don't do it in closed form.)

• Write sum-nats-iter, which does the same thing with tail recursion.

More on special forms

if just returns a value

You may not be used to if returning a value. Beginning Schemers who are used to procedural programming tend to put all their ifs on the outside, and make their code unnecessarily long.

(define (symmetrical-log x)
  (if (> x 0) (log x) (log (- x))))

does the same thing as

(define (symmetrical-log x)
  (log (if (> x 0) x (- x))))

and and or

There are two conditionals that are useful enough that you shouldn't have to always make them out of if, though you could.

• and returns a true value iff all its arguments are true values.
• or returns a true value iff one of its arguments is a true value.

These functions "short-circuit" much like if does:

• and stops as soon as something is false
• or stops as soon as something is true

We know there's only one false value, but what true value do they return?

• and returns the last value if all its arguments are true.
• or returns the first value that is true.

What do these return?

(and #t #f)
(and 10 20)
(or 10 20)
(or 10 20 #f)
(or #t (/ 1 0))
(or #t)
(or)     ; There's only one consistent answer
(and)    ; There are many possible answers, but take a guess

So what does define return?

• DrScheme won't let you write code that uses the result of a define.
• No, really. Try it. You get an error message before the code even runs. It throws out whole lambdas if it has to.
• In MIT Scheme, on the other hand, define returns a value called <undefined>.
• In DrScheme, functions like display return a similar result, called "void", that doesn't show up in the read-eval-print loop.
  • If you want to write a function like that in a project, you can evaluate the combination (void), which does nothing and returns void.
    • Don't do that on a test, though; the grader might not get it. Return a meaningless value instead.

Side effects

You may have noticed that you're stuck if you ever use a function, like display, that doesn't return a useful result. So far, it seems you have to use every result you ever get. But what if you want to make a side-effect happen and return a useful value?

begin evaluates a sequence of expressions, in order, and returns the result of the last one, throwing the others out.

Here's a particularly talkative abs function:

(define (loud-abs x)
  (if (< x 0)
    (begin
      (display "Oh no! A negative number!")
      (- x))
    x))

Side effect functions like display are why Scheme needs rules about evaluation order, and they will be the downfall of the substitution model.