# Simply Scheme Chapter 12 – The Leap of Faith

### The Leap of Faith

The leap of faith method is the assumption that the procedure we’re in the middle of writing already works. That is, if we’re thinking about writing a `reverse` procedure that can compute `(reverse 'paul)`, we assume that `(reverse 'aul)` will work.
Of course it’s not really a leap of faith, in the sense of something accepted as miraculous but not understood. The assumption is justified by our understanding of the combining method. For example, we understand that the four-letter `reverse` is relying on the three-letter version of the problem, not really on itself, so there’s no circular reasoning involved. And we know that if we had to, we could write `reverse1` through `reverse3` “by hand.”
The reason that our technique in this chapter may seem more mysterious than the combining method is that this time we are thinking about the problem top-down. In the combining method, we had already written `whatever3` before we even raised the question of `whatever4`. Now we start by thinking about the larger problem and assume that we can rely on the smaller one. Again, we’re entitled to that assumption because we’ve gone through the process from smaller to larger so many times already.
The leap of faith method, once you understand it, is faster than the combining method for writing new recursive procedures, because we can write the recursive solution immediately, without bothering with many individual cases. The reason we showed you the combining method first is that the leap of faith method seems too much like magic, or like “cheating,” until you’ve seen several believable recursive programs. The combining method is the way to learn about recursion; the leap of faith method is the way to write recursive procedures once you’ve learned.

### Example: `Evens`

I found part of the book’s discussion about this particular example a bit confusing so I figured I’d discuss it in detail.

Here’s a case in which mindlessly guessing `butfirst` or `butlast` doesn’t lead to a very good solution.

They’re referring to trying to figure out how to make a recursive procedure by guessing which operations might be helpful. For example, consider the `downup` procedure:

If you take `bl` of the input (`'pau`), you get a good chunk of the answer:

So that’s a hint that `bl` is gonna be involved in the solution. But this trick doesn’t always work, and the SS authors are going to talk about `evens` as a case where it doesn’t work.

We want a procedure that takes a sentence as its argument and returns a sentence of the even-numbered words of the original sentence:

We look at `evens` of the `butfirst` and `butlast` of this sentence:

`Butfirst` is clearly not helpful; it gives all the wrong words. `Butlast` looks promising. The relationship between `evens` of the bigger sentence and `evens` of the smaller sentence is that the last word of the larger sentence is missing from `evens` of the smaller sentence.

For a base case, we’ll take the empty sentence:

`losing-evens` should not be returning the whole sentence but only `'(WANT HOLD HAND)`, so something is broken.

This isn’t quite right.
It’s true that `evens` of `(i want to hold your hand)` is the same as `evens` of `(i want to hold your)` plus the word `hand` at the end. But what about `evens` of `(i want to hold your)`? By the reasoning we’ve been using, we would expect that to be `evens` of `(i want to hold)` plus the word `your`. But since the word `your` is the fifth word of the argument sentence, it shouldn’t be part of the result at all. Here’s how `evens` should work:

I thought about the problem instead of trying to do more mechanical guessing. I thought maybe I’d need a `cond` but then realized, like the SS authors eventually point out, that you can account for going through the sentence two words at a time pretty elegantly:

the `(<= (count sent) 1)` part handles both an empty sentence and a sentence where you’ve got 1 word left (because you started with an odd number of words) and returns the empty sentence in both cases.

### Simplifying Base Cases

The book suggests trying to find the simplest possible base case:

For example, consider using the empty word, empty sentence, or zero instead of one-letter words, one-word sentences, or one.

An illustration of a case where the empty word won’t work is `downup`. Here’s the version that works:

If you try to rewrite it like so:

You run into a problem, which is that you always get two copies of the single letter when you only want 1:

The thing about `donwup` is that you actually don’t want to treat the one letter case the same as you do the other cases. You want one copy of it and not two. Wanting to treat a case in a special/different way than all the other cases seems like a good indicator that something is the base case.

Another example they talk about is `letter-pairs`.

The book says that maybe you’ll think that the recursive case can handle one letter words and so the base case only needs to handle empty words. However, if the recursive case handles e.g. the one-letter word `a`, you get:

`bf 'a` is the empty word. Trying to take the `first` of the empty word leads to an error, since there is nothing to take the `first` of.

There is no second letter of a one-letter word. As soon as you see the expression (first (bf wd)) within this program, you know that one-letter words must be part of the base case. The same kind of reasoning can be used in many problems; the base case must handle anything that’s too small to fit the needs of the recursive case.

### Boring Exercises

#### ✅ Exercise 12.1

Here is a definition of a procedure that returns the sum of the numbers in its argument sentence:

Although this works, it could be simplified by changing the base case. Do that.

In their example they made the base case check if the `bf` of `nums` was empty and then return `first nums` if that is the case. This is stopping early for no good reason. You can go all the way to when `nums` is empty and check for that.

If you do that, there is a question of what to return in the base case. For `addup`, since the recursive case is adding up numbers, we want something that can be returned and that will cause no change in the sum being added. Thus we want to return 0.

#### ✅ Exercise 12.2

Fix the bug in the following definition:

If you try to run it as is you get e.g.:

The issue is that the recursive case correctly did `(first (first sent))` but the base case only did `first sent`. Easy fix:

#### ✅ Exercise 12.3

Can we reduce the factorial base case argument from 0 to -1? If so, show the resulting procedure. If not, why not?

We cannot. `factorial` will multiply the values together that are produced by the recursive case until arriving at the base case. So what happens if we take `factorial` and try to make it have a base case of -1?

`(factorial 5)` should produce 120 (5 x 4 x 3 x 2 x 1). What happens with our modified procedure, though, is that by trying to establish the base case at -1, we add a 0 into the mix. `factorial` winds up calculating 5 x 4 x 3 x 2 x 1 x 0 x 1 (the 1 at the end is from our base case). 0 multiplied by anything is zero, so all our factorial results become 0. Bad!

#### ✅ Exercise 12.4

Here’s the definition of a function f:

Implement f as a Scheme procedure. What does f do?

It reverses sentences. More specifically, in its recursive case, the function invokes `sentence`, and within that invocation, calls itself on `bf sent`, and then returns `first sent` and puts that after the recursive call. So essentially, it is putting the first word of the sentence last, and then calling itself with all but the first word of the sentence, and doing the same, so the whole sentence ultimately gets flipped around.

### Real Exercises

#### ✅ Exercise 12.5

Write an exaggerate procedure which exaggerates sentences:

It should double all the numbers in the sentence, and it should replace “good” with “great,” “bad” with “terrible,” and anything else you can think of.

This is how I solved this in chapter 8:

So I think I’ll use the `hyperbole` helper procedure again.

#### ✅ Exercise 12.6

Write a GPA procedure. It should take a sentence of grades as its argument and return the corresponding grade point average:

Hint: write a helper procedure base-grade that takes a grade as argument and returns 0, 1, 2, 3, or 4, and another helper procedure grade-modifier that returns −.33, 0, or .33, depending on whether the grade has a minus, a plus, or neither.

I found this one tricky until I came across the idea that I shouldn’t try to do the main part of the procedure all in one step.

The issue was that I wanted to use recursion to go and figure out/add up the grades, but keep the `count` of the initial `grades`. I eventually realized that the best way to achieve this was to break out the grade calculation part into its own helper procedure and just have `gpa` basically call that helper procedure and divide by `count grades`. I call my helper procedure `grade-adder`.

I actually came up with `grade-adder` by breaking the problem down into steps. I figured that I’d figure out how to add the grades first and then worry about dividing them. It worked out 🙂

#### ✅ Exercise 12.7

Write a procedure `spell-number` that spells out the digits of a number:

Use this helper procedure:

#### ✅ Exercise 12.8

Write a procedure `numbers` that takes a sentence as its argument and returns another sentence containing only the numbers in the argument:

#### ✅ Exercise 12.9

Write a procedure `real-words` that takes a sentence as argument and returns all the “real” words of the sentence, using the same rule as the real-word? procedure from Chapter 1.

#### ✅ Exercise 12.10

Write a procedure `remove` that takes a word and a sentence as arguments and returns the same sentence, but with all copies of the given word removed:

#### ✅ Exercise 12.11

Write the procedure `count`, which returns the number of words in a sentence or the number of letters in a word.

I named it `count2` to avoid a naming conflict.

#### ✅ Exercise 12.12

Write a procedure `arabic` which converts Roman numerals into Arabic numerals:

You will probably find the `roman-value` procedure from Chapter 6 helpful. Don’t forget that a letter can reduce the overall value if the letter that comes after it has a larger value, such as the `C` in `MCM`.

here is that procedure:

I wanted to make this a bit more elegant by having a `num2` that stood for `(roman-value (first (bf number)))`. With the organization of the program that I had above, that wouldn’t work, because the `(first (bf number)))` statement would get evaluated when there was only one character left in the roman numeral and lead to an error. However, after looking at a different solution for 12.13 below, I had the idea of putting the `let` statement after an `if` that handles the case where there is only roman numeral left. By checking for this case first and then using the `let` statement, I was able to avoid the problem I was having and was able to rewrite the program the way i wanted to:

#### ✅❌ Exercise 12.13

(I was able to make a working program without referencing other stuff, but lol @ the organization of my initial version. Cuz the organization was so bad, I’m only giving myself half credit here)

Write a new version of the `describe-time` procedure from Exercise . Instead of returning a decimal number, it should behave like this:

Can you make the program smart about saying `1 CENTURY` instead of `1 CENTURIES`?

My solution incorporates procedures from past work. Interestingly, I got stuck on the last bit about making stuff properly plural because I tried to use recursion to solve it and wound up getting this:

Gollum-speak was not the intended outcome 🙂

I ultimately wound up kind of inelegantly “brute-forcing” it rather than trying for something elegant. It does work though:

One thing I noticed was that while my first result matches their result exactly, the second one varies in the number of weeks, days, and hours. Their result was:

I actually used Scheme’s math functions to test something out on this point. If I did…

…which represents the result that I got, then I get the same number I put in, `4967189641`. OTOH, if I do…

…which represents the result they got, then I get `4963798441`. This value is 3,391,200 less than the previous value of `4967189641`. Since I was able to get the same value out that I put back in when I multiplied everything out, I’m not going to worry about this too much.

Ok so that’s really messy, though it does work.

I looked at a past solution I found on my hard drive (for some of these, I’m not sure if I worked them out myself or if I saw something somewhere online. Couldn’t find this one readily online in any case):

Much cleaner, yes?

The `number-helper` function tests if the seconds are in “range” of a particular value (like centuries). It then takes the seconds and finds the quotient using `quotient` (rather than the roundabout method I was using of dividing and then using `floor`).

`name-helper` outputs a plural name form if the number of seconds is above the appropriate threshold.

`se` concatenates the `number-helper` and `name-helper` for a given unit of time (like centuries) together.

The `remainder-helper` function uses a similar approach as `number-helper` to find the remainder, and passes the remaining number of seconds to a recursive call of `describe-time-recursive`.

This is way better than what I did above. The only thing it lacks is an ability to handle singular and plural names. Adding my pluralization procedures from my first program + a couple of calls to `thismany` in the body of `describe-time-recursive`, along with changing the default names in `name-helper` to the singular form, solves this issue:

After looking at AnneB’s tests, I didn’t like how my procedure handled `0` (it said `0 second` instead of `0 seconds`), so I made a change to `(thismany)` to address that:

##### Other Solutions

buntine’s solution is interesting.

He made special divider programs for calculating the number of seconds of things. E.g. he’s got a `minutes` program that divides the input value by 60 and other programs that build on those all the way up to `centuries`. He then using these to figure out what number to display when saying the names of the time units, e.g. `(se (centuries s) 'century))` will return the appropriate number of centuries.

The structure of his main `describe-time` program is also interesting. He uses a `let` statement to be able to address each part of a two-word pair (such as “1 century”) and pass it to a pluralization helper procedure (which is something I struggled with). He also uses a similar approach to mine when

Also for some reason he uses a `time-for` program to retrieve the amount of seconds of a unit of time (like an hour) by passing the name of the unit of time in, rather than just using `define` to specify names directly.