Mailing-List: contact mjd-book-help@plover.com; run by ezmlm
Date: 14 Jun 2000 04:26:49 -0000
Message-ID: <20000614042649.15228.qmail@plover.com>
From: mjd@plover.com
To: mjd-book@plover.com
Subject: Chapter 3 not finished, but big progress in my brain

Hi, folks.  It's been a while since I had an announcement.  But I
promised low traffic, and I want to be sure I deliver.  I was going to
wait until I had finished another chapter before announcing anything,
but there have been a couple of reasonably interesting developments
recently.

As some of you may know, I'm giving a class at TPC called `Advanced
Programming Techniques with Perl' or something like that.  The title
should sound vaguely familiar.  I got to give the class last week on
the Perl Whirl, where it was a big hit, and I'll do it once more at
YAPC next week.  The slides for the class are now on-line; URL appears
at the end of this message.  (Of course, I left all the most cool
examples out of the class.)

One delightful thing that happened while I was putting together the
class was that I realized that all my book material is a lot more
interconnected than I realized at first.  I had thought that the
chapters would be fairly disconnected, sort of a big bag of five or
ten major techniques.  But it turned out that each item was related to
all the other items in ways that I hadn't appreciated at first.  For
example, I had planned to show currying, but while I was putting
together the class, I realized that currying is what you get when you
combine closures with callbacks.  And I had planned to show generic
higher-order functions, such as 'fold', which is a function that
constructs functions that operate on lists, but I don't think it had
occured to me to think of a function that accepts callbacks as a
special case of a higher-order function, or vice versa.  So making up
the class first is going to result in a much better book.

This knitting-together process is continuing.  Today I had a really
wonderful experience that makes me feel better than ever about the
book.  I was talking to Jeff Goff on IRC, and he asked about the
partitioning problem.  This problem is to take a bunch of balls, and
to try to find all the ways of dividing them into groups.  For ex-
ample, if you have four balls, there are five ways to divide them up:

        4
        3+1
        2+2
        2+1+1
        1+1+1+1

(Note that duplicates, like 1+2+1 or 1+3, are not present.)

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.  

One of these themes is genericity; the idea that when you have an
algorithm to do something, you should abstract out all the specific
behavior that you can until you're left with a pure algorithm, and
then you can let the caller put that behavior back in by passing a
bunch of callbacks.  The very first example in the book, which is the
'hanoi' function, is about this: We start with a function that solves
the Towers of Hanoi problem and prints a solution to the screen, and
then turn it into a function that solves the Towers of Hanoi problem
and performs an arbitrary action at each step.

A second theme is that recursion is suitable for processes involving
recursive structures and recursive spaces.  And I had planned to talk
about tree search, but I don't think I realized until today just how
pervasive tree search actually is.  But almost any search problem can
be characterized as a tree search of some sort, and almost any
recursive function can be viewed as a sort of search. 

A third theme is the use of lazy iterators to represent the set of
solutions to a searching or other generation problem.  In the class I
taught last week, I showed a function that generates a list of
solutions to a problem, and then I show the solution with an iterator,
which in many ways is better.  The recursive version generates all the
solutions before it returns, which takes a really long time and is
wasteful of time and memory.  With the iterator solution, you extract
exactly as many solutions as you need and then throw away the
iterator.  But the iterator solution requires a lot more code, and
it's not clear how to transform the straightforward recursive solution
into an iterator without applying ingenuity, which is always in short
supply.  I ended up by saying that you really need continuations to do
this easily, and Perl does not have continuations.

But I was wrong; you do not need continuations.  The bright idea I had
today was that any recursive problem can be cast in the guise of a
tree search, and it isn't difficult to write a higher-order function
which accepts a few callbacks for generating the tree and for
recognizing solutions, and which constructs a tree search iterator
object that searches the tree recursively and returns a solution each
time it finds one.

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.

So it was a good day for me and a good day for PATH.  You can be sure
that this super example is going to appear in the book somewhere,
probably accompanied by a less mathematics-oriented example.

Here's the code.  I have a more heavily commented version, but I
looked it over and I think the comments detract from the readability.
(Of course, it might be more cryptic than I think because you haven't
yet read the chapters where I explain the techniques I'm using.)

----------------------------------------------------------------

#!/usr/bin/perl -x

# This function constructs a generic tree-search iterator.
sub make_search {
  my ($start_state, $is_leaf, $is_solution, $children) = @_;
  my @queue = $start_state;
  return sub {
    for (;;) {
      return undef unless @queue;
      my $s = shift @queue;
      if ($is_leaf->($s)) {
        return $s if $is_solution->($s);
      } else {
        push @queue, $children->($s);
      }
    }
  };
}

# This function uses the generic constructor to manufacture an
# iterator to solve the partition problem.
sub make_partitioner {
  my ($n) = @_;
  my $correct_total = sub {
    $_[0][0] == 0;
  };
  my $children = sub {
    my ($r, $m, $p) = @{$_[0]};
    my @res;
    for my $i ($m .. $r) {
      push @res, [$r-$i, $i, [@$p, $i]];
    }
    @res;
  };
  make_search([$n, 1, []], $correct_total, sub { 1 }, $children);
}

# Main program starts here
if (@ARGV != 1) {
  print "Usage: $0 number\n";
  exit 1;
}

# Construct iterator
my $it = make_partitioner(shift());

# Generate and print all partitions of the input argument
while (defined(my $s = $it->())) {
  my @p = @{$s->[2]};
  local $" = ', ';
  print "{@p}\n";
}

__END__
----------------------------------------------------------------

I really couldn't believe how easy it was to put this together.  The
essential part of the code is the make_partitioner function, which is
eleven lines long; it depends on make_search, which also only eleven
lines long and which is a totally interchangeable part that I expect
to use over and over again for a hundred different problems.

I started the book with the idea that I was going to show new,
powerful techniques that would make hard things easy, but I wasn't
quite sure that it would work out.  But I think this example is a huge
success.  I feel better about PATH than I ever have before.

Thanks all for your interest.  I will probably be in touch again next
time something happens, probably later in the summer when chapter 3 is
ready.

[ Sorry, class slides are available only to mailing list subscribers. 
  Send mail to 
        mjd-book-subscribe@plover.com
  to subscribe.
]