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:

Answer:

✅ 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:

Answer:

✅ 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.

Answer:

✅ 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:

Answer:

✅ 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.

Answer:

✅ 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:

First attempt at answer:

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.