ranger - mirror of ranger - a simple, vim-like file manager

	Commit message (Collapse)	Author	Age	Files	Lines
*	clean up	hut	2010-03-31	1	-10/+0
\|
*	more documentation	hut	2010-03-12	1	-3/+19
\|
*	misc changes, make install	hut	2010-03-12	1	-3/+12
\|
*	working on the configuration system / main method	hut	2010-03-12	1	-1/+1
\|
*	stuff	hut	2010-01-25	1	-1/+1
\|
*	added install instructions	hut	2010-01-14	1	-0/+30

<HTML> <HEAD> <TITLE>Computer Science Logo Style vol 1 ch 8: Practical Recursion: the Leap of Faith</TITLE> </HEAD> <BODY> <CITE>Computer Science Logo Style</CITE> volume 1: <CITE>Symbolic Computing</CITE> 2/e Copyright (C) 1997 MIT <H1>Practical Recursion: the Leap of Faith</H1> <TABLE width="100%"><TR><TD> <IMG SRC="../csls1.jpg" ALT="cover photo"> <TD><TABLE> <TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian Harvey</A> University of California, Berkeley</CITE> <TR><TD align="right"> <TR><TD align="right"><A HREF="../pdf/v1ch08.pdf">Download PDF version</A> <TR><TD align="right"><A HREF="../v1-toc2.html">Back to Table of Contents</A> <TR><TD align="right"><A HREF="../v1ch7/v1ch7.html">BACK</A> chapter thread <A HREF="../v1ch9/v1ch9.html">NEXT</A> <TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-1">MIT Press web page for Computer Science Logo Style</A> </TABLE></TABLE> <HR> When people first meet the idea of recursive procedures, they almost always think there is some sort of magic involved. "How can that possibly work? That procedure uses itself as a subprocedure! That's not fair." To overcome that sense of unfairness, the combining method works up to a recursive procedure by starting small, so that each step is completely working before the next step, to solve a larger problem, relies on it. There is no mystery about allowing <CODE>downup5</CODE> to rely on <CODE>downup4</CODE>. The trouble with the combining method is that it's too much effort to be practical. Once you believe in recursion, you don't want to have to write a special procedure for a size-one problem, then another special procedure for a size-two problem, and so on; you want to write the general recursive solution right away. I'm calling this the "leap of faith" method because you write a procedure while taking on faith that you can invoke the same procedure to handle a smaller subproblem. <H2>Recursive Patterns</H2> Let's look, once more, at the problem we were trying to solve when writing the <CODE>downup</CODE> procedure. We wanted the program to behave like this: <PRE>? downup "hello hello hell hel he h he hel hell hello </PRE> The secret of recursive programming is the same as a secret of problem solving in general: see if you can reduce a big problem to a smaller problem. In this case we can look at the printout from <CODE>downup</CODE> this way: <CENTER><IMG SRC="recur2-1.gif" ALT="downup hello results"></CENTER> What I've done here is to notice that the printout from applying <CODE> downup</CODE> to a five-letter word, <CODE>hello</CODE>, includes within itself the printout that would result from applying <CODE>downup</CODE> to a smaller word, <CODE>hell</CODE>. This is where the leap of faith comes in. I'm going to pretend that <CODE>downup</CODE> already works for the case of four-letter words. We haven't begun to write the procedure yet, but never mind that. So it seems that in order to evaluate the instruction <PRE>downup "hello </PRE> we must carry out these three instructions: <PRE>print "hello downup "hell print "hello </PRE> (The two <CODE>print</CODE> instructions print the first and last lines of the desired result, the ones that aren't part of the smaller <CODE>downup</CODE> printout.) To turn these instructions into a general procedure, we must use a variable in place of the specific word <CODE>hello</CODE>. We also have to figure out the general relationship that is exemplified by the transformation from <CODE>hello</CODE> into <CODE>hell</CODE>. This relationship is, of course, simply <CODE>butlast</CODE>. Here is the procedure that results from this process of generalization: <PRE>to downup :word print :word downup butlast :word print :word end </PRE> As you already know, this procedure won't quite work. It lacks a stop rule. But once we have come this far, it's a relatively simple matter to add the stop rule. All we have to do is ask ourselves, "What's the smallest case we want the program to handle?" The answer is that for a single-letter word the <CODE>downup</CODE> should just print the word once. In other words, for a single-letter word, <CODE>downup</CODE> should carry out its first instruction and then stop. So the stop rule goes after that first instruction, and it stops if the input has only one letter: <PRE>to downup :word print :word if equalp count :word 1 [stop] downup butlast :word print :word end </PRE> Voilà! The trick is not to think about the stop rule at first. Just accept, on faith, that the procedure will somehow manage to work for inputs that are smaller than the one you're interested in. Most people find it hard to do that. Since you haven't written the program yet, after all, the faith I'm asking you to show is really unjustified. Nevertheless you have to pretend that someone has already written a version of the desired procedure that works for smaller inputs. Let's take another example from Chapter 7. <PRE>? one.per.line "hello h e l l o </PRE> There are two different ways in which we can find a smaller pattern within this one. First we might notice this one: <CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch8/recur2-2.gif" ALT="one.per.line results"></CENTER> This pattern would lead to the following procedure, for which I haven't yet invented a stop rule. <PRE>to one.per.line :word print first :word one.per.line butfirst :word end </PRE> Alternatively we might notice this pattern: <CENTER><IMG SRC="recur2-3.gif" ALT="alternate one.per.line view"></CENTER> In that case we'd have a different version of the procedure. This one, also, doesn't yet have a stop rule. <PRE>to one.per.line :word one.per.line butlast :word print last :word end </PRE> Either of these procedures can be made to work by adding the appropriate stop rule: <PRE>if emptyp :word [stop] </PRE> This instruction should be the first in either procedure. Since both versions work, is there any reason to choose one over the other? Well, there's no theoretical reason but there is a practical one. It turns out that <CODE>first</CODE> and <CODE>butfirst</CODE> work faster than <CODE>last</CODE> and <CODE>butlast</CODE>. It also turns out that procedures that are tail recursive (that is, with the recursion step at the end) can survive more levels of invocation, without running out of memory, than those that are recursive in other ways. For both of these reasons the first version of <CODE>one.per.line</CODE> is a better choice than the second. (Try timing both versions with a very long list as input.) »Rewrite <A HREF="../v1ch5/hof.html#say">the <CODE>say</CODE> procedure</A> from Chapter 5 recursively. <H2>The Leap of Faith</H2> If we think of <PRE>to one.per.line :word print first :word one.per.line butfirst :word end </PRE> merely as a statement of a true fact about the "shape" of the result printed by <CODE>one.per.line</CODE>, it's not very remarkable. The amazing part is that this fragment is runnable!* It doesn't look runnable because it invokes itself as a helper procedure, and--if you haven't already been through the combining method--that looks as if it can't work. "How can you use <CODE>one.per.line</CODE> when you haven't written it yet?" <BLOCKQUOTE>*Well, almost. It needs a base case.</BLOCKQUOTE>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 <CODE>one.per.line</CODE> procedure that can compute <CODE>one.per.line "hello</CODE>, we assume that <CODE>one.per.line "ello</CODE> 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 five-letter <CODE>one.per.line</CODE> is relying on the four-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 <CODE>one.per.line1</CODE> through <CODE> one.per.line4</CODE> "by hand." The reason that the 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 <CODE>whatever4</CODE> before we even raised the question of <CODE>whatever5</CODE>. 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 you can write the recursive solution immediately, without bothering with many individual cases. The reason I 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. <H2>The Tower of Hanoi</H2> One of the most famous recursive problems is a puzzle called the Tower of Hanoi. You can find this puzzle in toy stores; look for a set of three posts and five or six disks. You start out with the puzzle arranged like this: <CENTER><IMG SRC="hanoi1.gif" ALT="figure: hanoi1"></CENTER> The object of the puzzle is to move all of the disks to the second post, like this: <CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch8/hanoi2.gif" ALT="figure: hanoi2"></CENTER> This looks easy, but there are rules you must follow. You can only move one disk at a time, and you can't put a disk on top of a smaller disk. You might start trying to solve the puzzle this way: <CENTER><IMG SRC="hanoi3.gif" ALT="figure: hanoi3"></CENTER> After that, you could move disk number 1 either onto post A, on top of disk 3, or onto post C, on top of disk 2. I'm about to describe a solution to the puzzle, so if you want to work on it yourself first, stop reading now. In the examples of <CODE>downup</CODE> and <CODE>one.per.line</CODE>, we identified each problem as one for which a recursive program was appropriate because within the pattern of the overall solution we found a smaller, similar pattern. The same principle will apply in this case. We want to end up with all five disks on post B. To do that, at some point we have to move disk 5 from post A to post B. To do that, we first have to get the other four disks out of the way. Specifically, "out of the way" must mean onto post C. So the solution to the problem can be represented graphically this way, in three parts: <CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch8/hanoi4.gif" ALT="figure: hanoi4"></CENTER> The first part of the solution is to move disks 1 through 4 from post A to post C. The second part is a single step, moving disk 5 from post A to post B. The third part, like the first, involves several steps, to move disks 1 through 4 from post C to post B. If you've developed the proper recursive spirit, you'll now say, "Aha! The first part and the third part are just like the entire puzzle, only with four disks instead of five!" I hope that after this example you'll develop a sort of instinct that will let you notice patterns like that instantly. You should then be ready to make a rough draft of a procedure to solve the puzzle: <PRE>to hanoi :number hanoi :number-1 movedisk :number hanoi :number-1 end </PRE> Of course, this isn't at all a finished program. For one thing, it lacks a stop rule. (As usual, we leave that part for last.) For another, we have to write the subprocedure <CODE>movedisk</CODE> that moves a single disk. But a more important point is that we've only provided for changing the disk number we're moving, not for selecting which posts to move from and to. You might want to supply <CODE>hanoi</CODE> with two more inputs, named <CODE>from</CODE> and <CODE>to</CODE>, which would be the names of the posts. So to solve the puzzle we'd say <PRE>hanoi 5 "A "B </PRE> But that's not quite adequate. <CODE>Hanoi</CODE> also needs to know the name of the third post. Why? Because in the recursive calls, that third post becomes one of the two "active" ones. For example, here are the three steps in solving the five-disk puzzle: <PRE>hanoi 4 "A "C movedisk 5 "A "B hanoi 4 "C "B </PRE> You can see that both of the recursive invocations need to use the name of the third post. Therefore, we'll give <CODE>hanoi</CODE> a fourth input, called <CODE>other</CODE>, that will contain that name. Here is another not-quite-finished version: <PRE>to hanoi :number :from :to :other hanoi :number-1 :from :other :to movedisk :number :from :to hanoi :number-1 :other :to :from end </PRE> This version still lacks a stop rule, and we still have to write <CODE> movedisk</CODE>. But we're much closer. Notice that <CODE>movedisk</CODE> does not need the name of the third post as an input. Its job is to take a single step, moving a single disk. The unused post really has nothing to do with it. Here's a simple version of <CODE>movedisk</CODE>: <PRE>to movedisk :number :from :to print (sentence [Move disk] :number "from :from "to :to) end </PRE> What about the stop rule in <CODE>hanoi</CODE>? The first thing that will come to your mind, probably, is that the case of moving disk number 1 is special because there are no preconditions. (No other disk can ever be on top of number 1, which is the smallest.) So you might want to use this stop rule: <PRE>if equalp :number 1 [movedisk 1 :from :to stop] </PRE> Indeed, that will work. (Where would you put it in the procedure?) But it turns out that a slightly more elegant solution is possible. You can let the procedure for disk 1 go ahead and invoke itself recursively for disk number 0. Since there is no such disk, the procedure then has nothing to do. By this reasoning the stop rule should be this: <PRE>if equalp :number 0 [stop] </PRE> You may have to trace out the procedure to convince yourself that this really works. Convincing yourself is worth the effort, though; it turns out that very often you can get away with allowing an "extra" level of recursive invocation that does nothing. When that's possible, it makes for a very clean-looking procedure. (Once again, I've left you on your own in deciding where to insert this stop rule in <CODE>hanoi</CODE>.) If your procedure is working correctly, you should get results like this for a small version of the puzzle: <PRE>? hanoi 3 "A "B "C Move disk 1 from A to B Move disk 2 from A to C Move disk 1 from B to C Move disk 3 from A to B Move disk 1 from C to A Move disk 2 from C to B Move disk 1 from A to B </PRE> If you like graphics programming and have been impatient to see a turtle in this book, you might want to write a graphic version of <CODE> movedisk</CODE> that would actually display the moves on the screen. <H2>More Complicated Patterns</H2> Suppose that, instead of <CODE>downup</CODE>, we wanted to write <CODE> updown</CODE>, which works like this: <PRE>? updown "hello h he hel hell hello hell hel he h </PRE> It's harder to find a smaller subproblem within this pattern. With <CODE>downup</CODE>, removing the first and last lines of the printout left a <CODE>downup</CODE> pattern for a shorter word. But the middle lines of this <CODE> updown</CODE> pattern aren't an <CODE>updown</CODE>. The middle lines don't start with a single letter, like the <CODE>h</CODE> in the full pattern. Also, the middle lines are clearly made out of the word <CODE>hello</CODE>, not some shortened version of it. » You might want to try to find a solution yourself before reading further. There are several approaches to writing <CODE>updown</CODE>. One thing we could do is to divide the pattern into two parts: <CENTER><IMG SRC="recur2-4.gif" ALT="up and down"></CENTER> It is relatively easy to invent the procedures <CODE>up</CODE> and <CODE>down</CODE> to create the two parts of the pattern. <PRE>to up :word if emptyp :word [stop] up butlast :word print :word end to down :word if emptyp :word [stop] print :word down butlast :word end </PRE> Then we can use these as subprocedures of the complete <CODE> updown</CODE>: <PRE>to updown :word up :word down butlast :word end </PRE> Another approach would be to use numbers to keep track of things, as in the <CODE>inout</CODE> example of Chapter 7. In this case we can consider the middle lines as a smaller version of the problem. <CENTER><IMG SRC="recur2-5.gif" ALT="nested updowns"></CENTER> In this point of view all the inner, smaller <CODE>updown</CODE> patterns are made from the same word, <CODE>hello</CODE>. But each invocation of <CODE> updown1</CODE> (which is what I'll call this version of <CODE>updown</CODE>) will use a second input, a number that tells it how many letters to print in the first and last lines: <PRE>? updown1 "hello 3 hel hell hello hell hel ? updown1 "hello 5 hello </PRE> We need a subprocedure, <CODE>truncate</CODE>, that prints the beginning of a word, up to a certain number of letters. <PRE>to truncate :word :size if equalp count :word :size [print :word stop] truncate butlast :word :size end to updown1 :word :size truncate :word :size if equalp count :word :size [stop] updown1 :word :size+1 truncate :word :size end </PRE> (The helper procedure <CODE>truncate</CODE> is the sort of thing that should really be an operation, for the same reason that <CODE>second</CODE> was better than <CODE>prsecond</CODE> <A HREF="../v1ch4/v1ch4.html#prsecond">here</A>. We'll come back to the writing of recursive operations in Chapter 11.) Finally, we can write a new superprocedure called <CODE> updown</CODE> that uses <CODE>updown1</CODE> with the correct inputs. (If you try all these approaches on the computer, remember that you can have only one procedure named <CODE>updown</CODE> in your workspace at a time.) <PRE>to updown :word updown1 :word 1 end </PRE> A third approach, which illustrates a very powerful technique, also uses an initialization procedure <CODE>updown</CODE> and a subprocedure <CODE> updown1</CODE> with two inputs. In this version, though, both inputs to the subprocedure are words: the partial word that we're printing right now and the partial word that is not yet to be printed. <CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch8/recur2-6.gif" ALT="alternate updowns"></CENTER> In this example, to print an <CODE>updown</CODE> pattern for the word <CODE>hello</CODE>, the two subprocedure inputs would be <CODE>h</CODE> (what's printed on the first line) and <CODE>ello</CODE> (what isn't printed there). For the inner pattern with the first and last lines removed, the two inputs would be <CODE>he</CODE> and <CODE>llo</CODE>. Here is the program: <PRE>to updown1 :now :later print :now if emptyp :later [stop] updown1 (word :now first :later) butfirst :later print :now end to updown :word updown1 first :word butfirst :word end </PRE> This program may be a little tricky to understand. The important part is <CODE>updown1</CODE>. Read it first without paying attention to the stop rule; see if you can understand how it corresponds to the <CODE>updown</CODE> pattern. A trace of its recursive invocations might help: <PRE>updown "hello updown1 "h "ello updown1 "he "llo updown1 "hel "lo updown1 "hell "o updown1 "hello " </PRE> The innermost level of recursion has been reached when the second input is the empty word. Notice how <CODE>first</CODE>, <CODE>butfirst</CODE>, and <CODE>word</CODE> are used in combination to calculate the inputs. »Write a recursive procedure <CODE>slant</CODE> that takes a word as input and prints it on a diagonal, one letter per line, like this: <PRE>? slant "salami s a l a m i </PRE> <H2>A Mini-project: Scrambled Sentences</H2> Just as Logo programs can be iterative or recursive, so can English sentences. People are pretty good at understanding even rather long iterative sentences: "This is the farmer who kept the cock that waked the priest that married the man that kissed the maiden that milked the cow that tossed the dog that worried the cat that killed the rat that ate the malt that lay in the house that Jack built." But even a short recursive (nested) sentence is confusing: "This is the rat the cat the dog worried killed." »Write a procedure that takes as its first input a list of noun-verb pairs representing actor and action, and as its second input a word representing the object of the last action in the list. Your procedure will print two sentences describing the events, an iterative one and a nested one, following this pattern: <PRE>? scramble [[girl saw] [boy owned] [dog chased] [cat bit]] "rat This is the girl that saw the boy that owned the dog that chased the cat that bit the rat This is the rat the cat the dog the boy the girl saw owned chased bit </PRE> You don't have to worry about special cases like "that Jack built"; your sentences will follow this pattern exactly. Ordinarily the most natural way to program this problem would be as an operation that outputs the desired sentence, but right now we are concentrating on recursive commands, so you'll write a procedure that <CODE> print</CODE>s each line as shown above. <H2>Procedure Patterns</H2> Certain patterns come up over and over in programming problems. It's worth your while to learn to recognize some of them. For example, let's look again at <CODE>one.per.line</CODE>: <PRE>to one.per.line :word if emptyp :word [stop] print first :word one.per.line butfirst :word end </PRE> This is an example of a very common pattern: <PRE>to procedure :input if emptyp :input [stop] do.something.to first :input procedure butfirst :input end </PRE> A procedure pattern is different from the result patterns we examined earlier in this chapter. Before we were looking at what we wanted a not-yet-written procedure to accomplish; now we are looking at already-written procedures to find patterns in their instructions. A particular procedure might look like this pattern with the blanks filled in. Here's an example: <PRE>to praise :flavors if emptyp :flavors [stop] print sentence [I love] first :flavors praise butfirst :flavors end ? praise [[ultra chocolate] [chocolate cinnamon raisin] ginger] I love ultra chocolate I love chocolate cinnamon raisin I love ginger </PRE> Do you see how <CODE>praise</CODE> fits the pattern? »Continuing our investigation of literary forms, write a procedure to compose love poems, like this: <PRE>? lovepoem "Mary M is for marvelous, that's what you are. A is for awesome, the best by far. R is for rosy, just like your cheek. Y is for youthful, with zest at its peak. Put them together, they spell Mary, The greatest girl in the world. </PRE> The core of this project is a database of deathless lines, in the form of a list of lists: <PRE>make "lines [[A is for albatross, around my neck.] [B is for baloney, your opinions are dreck.] [C is for corpulent, ...] ...] </PRE> and a recursive procedure <CODE>select</CODE> that takes a letter and a list of lines as inputs and finds the appropriate line to print by comparing the letter to the beginning of each line in the list. Another common pattern is a recursive procedure that counts something numerically, like <CODE>countdown</CODE>: <PRE>to countdown :number if equalp :number 0 [stop] print :number countdown :number-1 end </PRE> And here is the pattern: <PRE>to procedure :number if equalp :number 0 [stop] do.something procedure :number-1 end </PRE> A procedure built on this pattern is likely to have additional inputs so that it can do something other than just manipulate the number itself. For example: <PRE>to manyprint :number :text if equalp :number 0 [stop] print :text manyprint :number-1 :text end ? manyprint 4 [Lots of echo in this cavern.] Lots of echo in this cavern. Lots of echo in this cavern. Lots of echo in this cavern. Lots of echo in this cavern. to multiply :letters :number if equalp :number 0 [stop] print :letters multiply (word :letters first :letters) :number-1 end ? multiply "f 5 f ff fff ffff fffff </PRE> One way to become a skillful programmer is to study other people's programs carefully. As you read the programs in this book and others, keep an eye open for examples of patterns that you think might come in handy later on. <H2>Tricky Stop Rules</H2> Suppose that instead of <CODE>one.per.line</CODE> we'd like a procedure to print the members of a list two per line. (This is plausible if we have a list of many short items, for example. We'd probably want to control the spacing on each line so that the items would form two columns, but let's not worry about that yet.) The recursive part of this program is fairly straightforward: <PRE>to two.per.line :stuff print list (first :stuff) (first butfirst :stuff) two.per.line butfirst butfirst :stuff end </PRE> The only thing out of the ordinary is that the recursive step uses a subproblem that's smaller by two members, instead of the usual one. But it's easy to fall into a trap about the stop rule. It's not good enough to say <PRE>if emptyp :stuff [stop] </PRE> because in this procedure it matters whether the length of the input is odd or even. These two possibilities give rise to two stop rules. For an even-length list, we stop if the input is empty. But for an odd-length list, we must treat the case of a one-member list specially also. <PRE>to two.per.line :stuff if emptyp :stuff [stop] if emptyp butfirst :stuff [show first :stuff stop] print list (first :stuff) (first butfirst :stuff) two.per.line butfirst butfirst :stuff end </PRE> It's important to get the two stop rules in the right order; we must be sure the input isn't empty before we try to take its <CODE>butfirst</CODE>. »Why does this procedure include one <CODE>show</CODE> instruction and one <CODE>print</CODE> instruction? Why aren't they either both <CODE>show</CODE> or both <CODE>print</CODE>? <A HREF="../v1-toc2.html">(back to Table of Contents)</A> <A HREF="../v1ch7/v1ch7.html">BACK</A> chapter thread <A HREF="../v1ch9/v1ch9.html">NEXT</A> <ADDRESS> <A HREF="../index.html">Brian Harvey</A>, <CODE>bh@cs.berkeley.edu</CODE> </ADDRESS> </BODY> </HTML>