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.