Message-ID: <20030117020531.15404.qmail@plover.com> Subject: Chapter VI draft is ready Organization: Plover Systems Date: Thu, 16 Jan 2003 21:04:29 -0500 From: Mark Jason Dominus If you forgot what this list is about, or you don't know why you're getting this message, please see http://perl.plover.com/book/ To unsubscribe, send a blank message to mjd-book-unsubscribe@plover.com. ---------------------------------------------------------------- * I didn't finish Chapter VI by December 20, but I did finish it, and that's something. I think this might be a speed record for me. I hope I can keep it up. I hope you all will find it interesting, and that you will send me many suggestions and corrections. I love to get mail about my book, and I was a little disappointed by the response to Chapter V. * Chapter VI is about infinite lists. Infinite lists are a subject that's really close to my heart, because my career as a Perl expert really took off when I started writing articles for _The Perl Journal_, and my first article was about infinite lists. That article is available at http://perl.plover.com/Stream/ if you're interested. * After my last message, in which I discussed by struggles with depression, I received a lot of very kind and supportive mail from list members. Thank you everyone! * There is a long, mathematical digression below. If you fear or despise mathematics, please ignore it. * The book is further along than it might appear. The original outline called for 13 chapters. The current Chapter V is not in the original outline, and the current Chapter IV is likely to turn into three chapters. Chapter XIII from the outline is probably going away, and Chapters VII and VIII of the outline will be merged into a single chapter. Chapter I on the outline was an introduction. So I have about 8 chapters written, and about 5 to go. The current manuscript is 93,772 words long, which is about 268 manuscript pages. * I need to think of a title. I haven't come up with anything I like in the past three years. Does anyone have a suggestion? Some restrictions: * The title must contain the word 'Perl' * The title may not mention mathematics * The title may not mention functional programming * The title may not contain the word 'lambda' * The title should not be easily confusable with the title of any other Perl book It is a plus for the title to have a catchy acronym. ---------------------------------------------------------------- Something I forgot to mention in my last message: Way back in June 2000, I sent out an excited message about a method I had discovered for converting recursive functions to iterators: It's not too hard to come up with a recursive solution, but Jeff wanted an iterator-structured solution, which means that he wanted an object which supported a 'next' method which generates a different solution each time it is called. I thought about this a little this morning and couldn't see how to do it. But then I was thinking about it again over dinner and I had a really great flash of inspiration that tied together three big themes in the book. ... I rushed home and implemented the idea right away, and to my amazement: 1. It was very, very easy to write the code; there was almost no thought involved at all because each part was so simple and so self-contained. 2. It worked perfectly on the first try. (I don't know about you, but this never happens to me.) I was especially amazed because just a few hours before, using conventional procedural techniques, I had been unable to see how to wolve the problem at all. With the PATH techniques, I got the answer right away. If was almost totally formulaic. (http://perl.plover.com/book/announce/03) I should have mentioned in my previous message on the list that this idea has become one of the major subjects of Chapter V. If you were holding your breath waiting for the explanation, you can exhale now. Chapter V is still available in the secret area of the web site, but I will be removing it in another week or so. ---------------------------------------------------------------- The draft of Chapter VI is available from [ Sorry, freebies are available only to mailing list subscribers. Send mail to mjd-book-subscribe@plover.com to subscribe. ] Once again, I must remind you that you absolutely must not distribute this to anyone else, and in fact I'd prefer it if you didn't even download a permanent copy to your computer. This is because it will drive me bananas if I get corrections to the cruddy old drafts three years after the finished version of the book is published. In fact, even if I don't get corrections, it will keep me awake at night if I think there are people out in the world reading my mistakes and thinking what a dummy I am after I have already corrected them. Yes, I know it's nuts, but please contribute to my peace of mind. There's no point in saving a copy anyway, because the final version will be available on my web site once the book is done. Please make me happy and repay my trust by not copying or distributing the drafts. It is OK to print them out if you want to read them on paper or make corrections or whatever. Please do destroy them when you are done, however. Also, please do not advertise the draft URL to other people. I want the drafts to be a special present for the people on my mailing list. But please do advertise the mailing list to other people. I will be very happy if more people join the mailing list. To subscribe, send email to mjd-book-subscribe@plover.com or visit the subscription form at http://perl.plover.com/book/#mlist Thank you all for your interest and kind support. ---------------------------------------------------------------- Long mathematical digression: * At one point, the draft of VI was longer than any other chapter except for the humongous Chapter IV. Then I decided that two of the topics I had planned to cover were just belaboring the point, so I cut them out; it's now about 40 pages long. If there's interest I can make the cut-out stuff available to the mailing list subscribers. The cut-out stuff concerns the internal implementation of floating-point numbers, whose behavior is very weird. For example, it is possible to find three floats such that (a + b) + c != a + (b + c) Floats are always doing wacky and unexpected things. Even simple round-off error freaks out a lot of people. On the one hand, you have people who get freaked out because 0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1 != 1; Then on the other hand you have the people who know that and who overreact and think you can't use == on floating-point numbers at all. Very few people understand floating-point numbers, and that's quite excusable, because flaoting-point numbers are very complicated! You can use infinite-precision floating point numbers, as supplied by the Perl 'Math::BigFloat' library, but that has some severe disadvantages. Typically, your inputs to 'Math::BigFloat' will be approximations; for example, you might approximate 1/6 as '0.1666666666' and then ask what 1/6 * 1/6 is. Math::BigFloat will tell you that the answer is 0.02777777775555555556. This is a pain in the ass for two reasons. First, the answer is only correct to 10 places; the last 10 places are wrong, because of the error in the original approximations to 1/6. And second, Math::BigFloat is too stupid to realize this, so it wasted plenty of time computing those useless extra 10 digits. This problem gets worse and worse the more you calculate. I have a nice example in section 6.1.2 in which a straightforward calculation of sqrt(2) with Math::BigFloat produces an 80-digit answer of which only the first 5 digits are correct. How can you solve this? One way is by choosing a better representation of floating-point numbers. Infinite list work well. You can represent a float as an infinite list of digits. 1/6 is represented as [0, 1, 6, 6, 6, 6, 6, .....] where the 6'es continue forever. You can do arithmetic on these lists; 1/6 * 1/6 produces [0, 0, 2, 7, 7, 7, 7, ...] where the 7's continue forever. But the really wonderful thing about this is that you only do as much work as you need to get the precision you want. If you only look at the first four elements of the answer, Perl only computes just as much as it needs to show them to you. The rest of the 7's are in limbo, and won't be computed unless you look at them later. If the 1/6'es were produced by some other computation, then that computation will be executed only as much as is necessary to produce the precision needed in the multiplication to produce as much of the final answer as you're trying to look at. Each operation can demand more digits from its arguments if it needs them, and computes only as many digits in its result as are demanded of it. * There's an even better way to represent numbers. Representing them as streams of decimal digits is prejudiced in favor of beings with 10 fingers. Numbers like 17/200 can be represented exactly, but much simpler numbers like 1/3 and 3/17 can't. Mathematicians have invented a representation called 'continued fractions' that is neutral with respect to the number of fingers you have. It represents all fractions as briefly as possible, and many other numbers as well. Consider the number 24/7 = 3.428571428... . It is approximately 3. 3 + a little bit. How much is the little bit, 0.428571428...? It's about 1/2. But it's not exactly 1/2, because 1/0.428571428... = 2.333333..., so 24/7 = 3 + 1/(2 + a little bit). How much is the little bit now, 0.33333...? It's exactly 1/3. So 24/7 = 3 + 1 / (2 + 1/3). This is the 'continued fraction expansion' of 24/7. The continued fraction expansion of any rational number always terminates. The continued fraction expansion of any sum or product of rational numbers and square roots of rational numbers always has a periodic continued fraction expansion. For example, sqrt(2) = 1 + 1/(2 + 1/(2 + 1/(2 + 1/(2 + .......)))). You can get a rational approximation to one of these just by chopping off the end. For example, sqrt(2) is approximately 1 = 1. sqrt(2) is approximately 1+1/2 = 1.5. sqrt(2) is approximately 1+1/(2 + 1/2) = 1+1/(5/2) = 1+2/5 = 1.4. sqrt(2) is approximately 1+1/(2 + 1/(2+1/2)) = 1+1/(2 + 1/(5/2)) = 1+1/(2 + 2/5) = 1+1/(12/5) = 1+5/12 = 1.4166666... sqrt(2) is approximately 1+1/(2 + 1/(2+1/(2+1/2))) = 1+1/(2 + 1/(2+1/(5/2))) = 1+1/(2 + 1/(2+2/5)) = 1+1/(2 + 1/(12/5)) = 1+1/(2 + 5/12) = 1+1/(29/12) = 1+12/29 = 1.4137931... These fractions are called the 'continuants' of sqrt(2). Mathematicians have proved that the continuants of a number are the *best possible* rational approximations to that number; the only way to get better approximations is to use fractions with larger denominators---but these fractions will be no better than continuants that you can get by chopping the continued fraction representation later on. You can do this with rational numbers also. One of the chopped-out sections in the book discussed the Gregorian calendar, and showed how to use continued fractions to figure out how to schedule leap days in way that repeats more frequently than every 400 years, but that is more accurate than the 400-year schedule used by the Gregorian calendar. The big problem with continued fractions: Until fairly recently, nobody knew how to do arithmetic with them. How can you figure out the continued fraction for sqrt(2) + sqrt(3), given only the continued fraction expansions for sqrt(2) and sqrt(3)? About 25 years ago, Bill Gosper figured out how to do this. I spent a lot of time in the past 12 months tracking down his unpublished papers about this, reading and understanding them, and implementing the algorithms. They work really well. I can multiply 1/6 and 1/6 and get an exact answer. I can also multiply sqrt(2) and sqrt(2) and get an exact answer. Try *that* with Math::BigFloat! But I decided there was too much mathematics in Chapter VI already, so I cut it all out. Oh well. My editor says that perhaps stuff like this can go into an appendix.