Loading ...
Sorry, an error occurred while loading the content.
 

RE: [XP] binary search, test first, by intention

Expand Messages
  • Ivan Tomek
    Ron, These exchanges are interesting but they don t prove anything. (I don t think that they are supposed to.) I think that it would be even more interesting
    Message 1 of 7 , May 28, 2002
      Ron,

      These exchanges are interesting but they don't prove anything. (I don't
      think that they are supposed to.) I think that it would be even more
      interesting if somebody designed a real experiment along these lines for
      this community that would be amenable to some concrete conclusions.

      Ivan


      -----Original Message-----
      From: Ron Jeffries [mailto:ronjeffries@...]
      Sent: Monday, May 27, 2002 3:36 PM
      To: extremeprogramming
      Subject: [XP] binary search, test first, by intention


      9:57 AM

      I'm going to try Binary Search again, this time using test-first and
      programming by intention. In programming by intention, as you'll see,
      we express what we intend to accomplish, then elaborate it. I'm
      expecting that this version of binary search will start out with a
      class, and methods, so that it won't initially be as compact as the
      other versions. Then I'll refactor it.

      Somewhere in there, though, I have to go to Star Wars. This may make
      the time computations tricky. I think I'll start anyway, because I'm
      bored.

      10:03 AM

      def testNotThere
      assert_equal(-1, binsrch([],1))
      end

      The test doesn't run. I'll create a starting method. I'll do this in
      the obvious way but I expect to deviate quickly from what went before.

      10:04 AM

      def binsrch(array, item)
      -1
      end

      OK, now a test that could work. I'm not going to pick the "in the
      middle" test this time.

      def test3
      assert_equal(3, binsrch([0,1,2,3,4,5,6,7,8,9], 3))
      end

      Doesn't work. I wish I hadn't done that. I want to refactor now. But
      no harm done, I'll do it anyway. I'm going to create an object to work
      in. Maybe there is a simpler way, but this is what I want to
      experiment with this time. No, wait. I won't do that. I'll just write
      my intentions right in the existing binsrch method. We'll see if I
      need to create a class. It's 10:07 AM.

      10:09 AM

      Here's my intention:

      def binsrch(array, item)
      defineRange
      while rangeNotEmpty
      return midrange if array[midrange] == item
      adjustRange
      end
      end

      Doesn't work, of course, those things aren't defined. So I'll define
      them ...

      def defineRange
      @low = 0
      @high = array.length-1
      end

      Ah. I decided the range was in instance variables @low and @high.
      Notice that I need the array. I could pass it as a parameter, but I
      don't want to do that. I'll make it an instance variable also:

      def binsrch(array, item)
      @array = array
      @item = item
      defineRange
      while rangeNotEmpty
      return midrange if array[midrange] == item
      adjustRange
      end
      end

      Notice that I violated YAGNI and defined item as an instance variable
      also. So shoot me, I'm going to use it, and I know just where. The
      time is 10:12 AM. My tests aren't running. I should be nervous, but
      I'm not: I know where I"m going. Still, this is a long delay with no
      tests ... we'll see what happens ...

      def rangeNotEmpty
      @low <= @high
      end

      def midrange
      (@low + @high) / 2
      end

      10:14 AM

      I think I might be done, I'll run my tests ... well, not while that
      code for defineRange says "array". I'll fix that and the other
      reference also, just for symmetry ...

      10:15 AM

      I got two errors. One is something about a nil. The other one is that
      I didn't define adjustRange. Sure is good that I have a computer to
      help me. Wish Chet wasn't in Italy ...

      10:16 AM

      Working by intention, I define

      def adjustRange
      if item < midItem
      lowRange
      else
      highRange
      end

      Notice that I decided I want a method midItem to return the middle
      item, and two methods to adjust the range. I'll write them. It's a
      long time with no tests working, but I feel on a roll ... we'll see if
      it bites me ...

      def midItem
      array[midRange]
      end

      def lowRange
      @high = midRange - 1
      end

      def highRange
      @low = midRange + 1
      end

      I also noticed that the main routine doesn't return -1 if the loop
      falls through, so I fixed that:

      def binsrch(array, item)
      @array = array
      @item = item
      defineRange
      while rangeNotEmpty
      return midrange if midItem == item
      adjustRange
      end
      -1
      end

      Time for Star Wars. It's 10:20 AM.

      Back from Star Wars and lunch. It's 3:21 PM. Let's see what we have
      here. I think I'll run the tests to find out what's going on ...

      Three typos: a missing end, a reference to array instead of @array,
      and midrange spelled midRange. Let's see what else ... running tests
      again at 3:24 PM. Oops. "item" used where I needed "@item".

      Now all the tests are running. All two of them. I wonder if I need any
      more. The tests are:

      def testNotThere
      assert_equal(-1, binsrch([],1))
      end

      def test3
      assert_equal(3, binsrch([0,1,2,3,4,5,6,7,8,9], 3))
      end

      Frankly I don't think I need any more, but I'll go grab the tests from
      the previous versions and run them all. Hold on a moment ...

      3:27 PM

      Well, how about that. 8 of 8 tests, 1010 asserts, all running
      correctly. Here's the program, 24 minutes in counting time to write
      the story:

      class BinarySearchTestCase < TestCase

      def testNotThere
      assert_equal(-1, binsrch([],1))
      end

      def test3
      assert_equal(3, binsrch([0,1,2,3,4,5,6,7,8,9], 3))
      end

      def testAbsent
      assert_equal(-1, binsrch([],3))
      end

      def testFound
      assert_equal( 4, binsrch([0,1,2,3,4,5,6,7,8], 4))
      end

      def testFoundLower
      assert_equal(2, binsrch([0,1,2,3,4,5,6,7,8], 2))
      end

      def testFoundHighEnd
      assert_equal(8, binsrch([0,1,2,3,4,5,6,7,8], 8))
      end

      def testFoundLowEnd
      assert_equal(0, binsrch([0,1,2,3,4,5,6,7,8], 0))
      end

      def test1000
      array = []
      (1..1000).each { | i | array << i }
      assert_equal(76, binsrch(array,77))
      assert_equal(75, binsrch(array,76))
      assert_equal(77, binsrch(array,78))
      (1..1000).each { | item |
      assert_equal(item-1, binsrch(array,item))
      }
      end
      end

      def binsrch(array, item)
      @array = array
      @item = item
      defineRange
      while rangeNotEmpty
      return midrange if midItem == item
      adjustRange
      end
      -1
      end

      def defineRange
      @low = 0
      @high = @...-1
      end

      def rangeNotEmpty
      @low <= @high
      end

      def midrange
      (@low + @high) / 2
      end

      def adjustRange
      if @item < midItem
      lowRange
      else
      highRange
      end
      end

      def midItem
      @array[midrange]
      end

      def lowRange
      @high = midrange - 1
      end

      def highRange
      @low = midrange + 1
      end

      I think that's interesting. Other than typos, there were basically no
      bugs. On the one hand I avoided the main one, low < high for low <=
      high, which we could argue was pretty easy since I had just fixed it
      yesterday. I want to argue, however that it's this definition that
      makes it clear:

      def rangeNotEmpty
      @low <= @high
      end

      As soon as we realize the question is "range not empty", we see that
      low == high has range size 1 and is therefore ... not empty.

      OK ... next installment ... refactoring to make it a class and tighten
      it up. If we think it needs it. It's pretty expressive as it is, I
      think ... what do you think?

      Regards,

      Ron Jeffries
      www.XProgramming.com
      Fear is the mindkiller. --Bene Gesserit Litany Against Fear


      To Post a message, send it to: extremeprogramming@...

      To Unsubscribe, send a blank message to:
      extremeprogramming-unsubscribe@...

      ad-free courtesy of objectmentor.com

      Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
    • Dossy
      ... I think they prove: 1) We don t know as much as we think we know, even when we think we know very simple things like binary search. 2) When mistakes are
      Message 2 of 7 , May 28, 2002
        On 2002.05.28, Ivan Tomek <ivan.tomek@...> wrote:
        >
        > These exchanges are interesting but they don't prove anything. (I don't
        > think that they are supposed to.) I think that it would be even more
        > interesting if somebody designed a real experiment along these lines for
        > this community that would be amenable to some concrete conclusions.

        I think they prove:

        1) We don't know as much as we think we know, even when we think
        we know very simple things like binary search.

        2) When mistakes are made when making small changes or implementing
        things using small steps, the mistakes are quicker to find and fix.
        This makes the effect of the mistake less costly.

        3) When you write code that is more expressive, it is easier to
        implement because you know what you're trying to achieve which makes
        it easier to make the code do what it's supposed to do.

        -- Dossy

        --
        Dossy Shiobara mail: dossy@...
        Panoptic Computer Network web: http://www.panoptic.com/
        "He realized the fastest way to change is to laugh at your own
        folly -- then you can let go and quickly move on." (p. 70)
      • Enrique Comba Riepenhausen
        Hi Ivan, and naturally everybody in the list. This would be a funny idea. I don t only mean to make a test-first-design session but a full mini-iteration
        Message 3 of 7 , May 28, 2002
          Hi Ivan, and naturally everybody in the list.

          This would be a funny idea. I don't only mean to make a
          test-first-design session but a full mini-iteration simulation to see
          how the whole process would be made.

          I don't know if there is any interest in this, but I personally think
          would be a funny idea...

          What do you mean ?

          > -----Mensaje original-----
          > De:
          > sentto-1505409-47890-1022594951-enrique.comba=m-centric.com@re
          > turns.groups.yahoo.com
          > [mailto:sentto-1505409-47890-1022594951-enrique.comba=m-centri
          c.com@...] En nombre de Ivan > Tomek
          > Enviado el: martes, 28 de mayo de 2002 16:09
          > Para: 'extremeprogramming@yahoogroups.com'
          > Asunto: RE: [XP] binary search, test first, by intention
          >
          >
          > Ron,
          >
          > These exchanges are interesting but they don't prove
          > anything. (I don't think that they are supposed to.) I think
          > that it would be even more interesting if somebody designed a
          > real experiment along these lines for this community that
          > would be amenable to some concrete conclusions.
          >
          > Ivan
          >
          >
          > -----Original Message-----
          > From: Ron Jeffries [mailto:ronjeffries@...]
          > Sent: Monday, May 27, 2002 3:36 PM
          > To: extremeprogramming
          > Subject: [XP] binary search, test first, by intention
          >
          >
          > 9:57 AM
          >
          > I'm going to try Binary Search again, this time using
          > test-first and programming by intention. In programming by
          > intention, as you'll see, we express what we intend to
          > accomplish, then elaborate it. I'm expecting that this
          > version of binary search will start out with a class, and
          > methods, so that it won't initially be as compact as the
          > other versions. Then I'll refactor it.
          >
          > Somewhere in there, though, I have to go to Star Wars. This
          > may make the time computations tricky. I think I'll start
          > anyway, because I'm bored.
          >
          > 10:03 AM
          >
          > def testNotThere
          > assert_equal(-1, binsrch([],1))
          > end
          >
          > The test doesn't run. I'll create a starting method. I'll do
          > this in the obvious way but I expect to deviate quickly from
          > what went before.
          >
          > 10:04 AM
          >
          > def binsrch(array, item)
          > -1
          > end
          >
          > OK, now a test that could work. I'm not going to pick the "in
          > the middle" test this time.
          >
          > def test3
          > assert_equal(3, binsrch([0,1,2,3,4,5,6,7,8,9], 3))
          > end
          >
          > Doesn't work. I wish I hadn't done that. I want to refactor
          > now. But no harm done, I'll do it anyway. I'm going to create
          > an object to work in. Maybe there is a simpler way, but this
          > is what I want to experiment with this time. No, wait. I
          > won't do that. I'll just write my intentions right in the
          > existing binsrch method. We'll see if I need to create a
          > class. It's 10:07 AM.
          >
          > 10:09 AM
          >
          > Here's my intention:
          >
          > def binsrch(array, item)
          > defineRange
          > while rangeNotEmpty
          > return midrange if array[midrange] == item
          > adjustRange
          > end
          > end
          >
          > Doesn't work, of course, those things aren't defined. So I'll
          > define them ...
          >
          > def defineRange
          > @low = 0
          > @high = array.length-1
          > end
          >
          > Ah. I decided the range was in instance variables @low and
          > @high. Notice that I need the array. I could pass it as a
          > parameter, but I don't want to do that. I'll make it an
          > instance variable also:
          >
          > def binsrch(array, item)
          > @array = array
          > @item = item
          > defineRange
          > while rangeNotEmpty
          > return midrange if array[midrange] == item
          > adjustRange
          > end
          > end
          >
          > Notice that I violated YAGNI and defined item as an instance
          > variable also. So shoot me, I'm going to use it, and I know
          > just where. The time is 10:12 AM. My tests aren't running. I
          > should be nervous, but I'm not: I know where I"m going.
          > Still, this is a long delay with no tests ... we'll see what
          > happens ...
          >
          > def rangeNotEmpty
          > @low <= @high
          > end
          >
          > def midrange
          > (@low + @high) / 2
          > end
          >
          > 10:14 AM
          >
          > I think I might be done, I'll run my tests ... well, not
          > while that code for defineRange says "array". I'll fix that
          > and the other reference also, just for symmetry ...
          >
          > 10:15 AM
          >
          > I got two errors. One is something about a nil. The other one
          > is that I didn't define adjustRange. Sure is good that I have
          > a computer to help me. Wish Chet wasn't in Italy ...
          >
          > 10:16 AM
          >
          > Working by intention, I define
          >
          > def adjustRange
          > if item < midItem
          > lowRange
          > else
          > highRange
          > end
          >
          > Notice that I decided I want a method midItem to return the
          > middle item, and two methods to adjust the range. I'll write
          > them. It's a long time with no tests working, but I feel on a
          > roll ... we'll see if it bites me ...
          >
          > def midItem
          > array[midRange]
          > end
          >
          > def lowRange
          > @high = midRange - 1
          > end
          >
          > def highRange
          > @low = midRange + 1
          > end
          >
          > I also noticed that the main routine doesn't return -1 if the
          > loop falls through, so I fixed that:
          >
          > def binsrch(array, item)
          > @array = array
          > @item = item
          > defineRange
          > while rangeNotEmpty
          > return midrange if midItem == item
          > adjustRange
          > end
          > -1
          > end
          >
          > Time for Star Wars. It's 10:20 AM.
          >
          > Back from Star Wars and lunch. It's 3:21 PM. Let's see what
          > we have here. I think I'll run the tests to find out what's
          > going on ...
          >
          > Three typos: a missing end, a reference to array instead of
          > @array, and midrange spelled midRange. Let's see what else
          > ... running tests again at 3:24 PM. Oops. "item" used where I
          > needed "@item".
          >
          > Now all the tests are running. All two of them. I wonder if I
          > need any more. The tests are:
          >
          > def testNotThere
          > assert_equal(-1, binsrch([],1))
          > end
          >
          > def test3
          > assert_equal(3, binsrch([0,1,2,3,4,5,6,7,8,9], 3))
          > end
          >
          > Frankly I don't think I need any more, but I'll go grab the
          > tests from the previous versions and run them all. Hold on a
          > moment ...
          >
          > 3:27 PM
          >
          > Well, how about that. 8 of 8 tests, 1010 asserts, all running
          > correctly. Here's the program, 24 minutes in counting time to
          > write the story:
          >
          > class BinarySearchTestCase < TestCase
          >
          > def testNotThere
          > assert_equal(-1, binsrch([],1))
          > end
          >
          > def test3
          > assert_equal(3, binsrch([0,1,2,3,4,5,6,7,8,9], 3))
          > end
          >
          > def testAbsent
          > assert_equal(-1, binsrch([],3))
          > end
          >
          > def testFound
          > assert_equal( 4, binsrch([0,1,2,3,4,5,6,7,8], 4))
          > end
          >
          > def testFoundLower
          > assert_equal(2, binsrch([0,1,2,3,4,5,6,7,8], 2))
          > end
          >
          > def testFoundHighEnd
          > assert_equal(8, binsrch([0,1,2,3,4,5,6,7,8], 8))
          > end
          >
          > def testFoundLowEnd
          > assert_equal(0, binsrch([0,1,2,3,4,5,6,7,8], 0))
          > end
          >
          > def test1000
          > array = []
          > (1..1000).each { | i | array << i }
          > assert_equal(76, binsrch(array,77))
          > assert_equal(75, binsrch(array,76))
          > assert_equal(77, binsrch(array,78))
          > (1..1000).each { | item |
          > assert_equal(item-1, binsrch(array,item))
          > }
          > end
          > end
          >
          > def binsrch(array, item)
          > @array = array
          > @item = item
          > defineRange
          > while rangeNotEmpty
          > return midrange if midItem == item
          > adjustRange
          > end
          > -1
          > end
          >
          > def defineRange
          > @low = 0
          > @high = @...-1
          > end
          >
          > def rangeNotEmpty
          > @low <= @high
          > end
          >
          > def midrange
          > (@low + @high) / 2
          > end
          >
          > def adjustRange
          > if @item < midItem
          > lowRange
          > else
          > highRange
          > end
          > end
          >
          > def midItem
          > @array[midrange]
          > end
          >
          > def lowRange
          > @high = midrange - 1
          > end
          >
          > def highRange
          > @low = midrange + 1
          > end
          >
          > I think that's interesting. Other than typos, there were
          > basically no bugs. On the one hand I avoided the main one,
          > low < high for low <= high, which we could argue was pretty
          > easy since I had just fixed it yesterday. I want to argue,
          > however that it's this definition that makes it clear:
          >
          > def rangeNotEmpty
          > @low <= @high
          > end
          >
          > As soon as we realize the question is "range not empty", we
          > see that low == high has range size 1 and is therefore ... not empty.
          >
          > OK ... next installment ... refactoring to make it a class
          > and tighten it up. If we think it needs it. It's pretty
          > expressive as it is, I think ... what do you think?
          >
          > Regards,
          >
          > Ron Jeffries
          > www.XProgramming.com
          > Fear is the mindkiller. --Bene Gesserit Litany Against Fear
          >
          >
          > To Post a message, send it to: extremeprogramming@...
          >
          > To Unsubscribe, send a blank message to:
          > extremeprogramming-unsubscribe@...
          >
          > ad-free courtesy of objectmentor.com
          >
          > Your use of Yahoo! Groups is subject to
          > http://docs.yahoo.com/info/terms/
          >
          >
          > To Post a message, send
          > it to: extremeprogramming@...
          >
          > To Unsubscribe, send a blank message to:
          > extremeprogramming-unsubscribe@...
          >
          > ad-free courtesy of objectmentor.com
          >
          > Your use of Yahoo! Groups is subject to
          > http://docs.yahoo.com/info/terms/
          >
          >
          >
        • Blum, Robert
          Hi Dossy, ... [snip] and of course, they prove that debugging by console printout is a major pain. - Robert
          Message 4 of 7 , May 28, 2002
            Hi Dossy,

            > I think they prove:

            [snip]

            and of course, they prove that debugging by console printout is a
            major pain.

            - Robert
          • Mike Clark
            ... It s interesting (to me, at least) that had tests for rangeNotEmpty and midrange been written first, they may have taken the low and high values as
            Message 5 of 7 , May 31, 2002
              Ron Jeffries wrote:

              ><snip>
              >
              >Ah. I decided the range was in instance variables @low and @high.
              >Notice that I need the array. I could pass it as a parameter, but I
              >don't want to do that. I'll make it an instance variable also:
              >
              >def binsrch(array, item)
              > @array = array
              > @item = item
              > defineRange
              > while rangeNotEmpty
              > return midrange if array[midrange] == item
              > adjustRange
              > end
              >end
              >
              >Notice that I violated YAGNI and defined item as an instance variable
              >also. So shoot me, I'm going to use it, and I know just where. The
              >time is 10:12 AM. My tests aren't running. I should be nervous, but
              >I'm not: I know where I"m going. Still, this is a long delay with no
              >tests ... we'll see what happens ...
              >
              >def rangeNotEmpty
              > @low <= @high
              >end
              >
              >def midrange
              > (@low + @high) / 2
              >end
              >


              It's interesting (to me, at least) that had tests for rangeNotEmpty and
              midrange been written first, they may have taken the low and high values
              as parameters, rather than using instance variables. The use of
              parameters may have made these methods more testable, at the cost of
              making them more procedural in nature. By starting with a
              coarser-grained test for binsrch the object took on more state.

              I find that if I start off with finer-grained tests, my classes look
              more procedural and there's little encapsulation. Starting with
              coarser-grained tests generally leads me toward objects with more
              encapsulated state.

              How does this compare with the experience of others?

              Mike
            • Ron Jeffries
              ... Well ... I have a pattern that sounds similar. I get better objects if I start top down or breadth first . However, since I try to practice YAGNI, I
              Message 6 of 7 , Jun 1 1:51 AM
                Around Friday, May 31, 2002, 10:06:59 AM, Mike Clark wrote:

                > It's interesting (to me, at least) that had tests for rangeNotEmpty and
                > midrange been written first, they may have taken the low and high values
                > as parameters, rather than using instance variables. The use of
                > parameters may have made these methods more testable, at the cost of
                > making them more procedural in nature. By starting with a
                > coarser-grained test for binsrch the object took on more state.

                > I find that if I start off with finer-grained tests, my classes look
                > more procedural and there's little encapsulation. Starting with
                > coarser-grained tests generally leads me toward objects with more
                > encapsulated state.

                > How does this compare with the experience of others?

                Well ... I have a pattern that sounds similar. I get better objects if
                I start "top down" or "breadth first".

                However, since I try to practice YAGNI, I /cannot/ write rangeNotEmpty
                or midrange first. So I don't have quite the same reaction to the
                forces that you describe here ...

                Ron Jeffries
                www.XProgramming.com
                "How do I get to XP?" "Practice, man, practice."
              • Mike Clark
                ... Excellent point. If rangeNotEmpty had been more complex such that you feared going too long without the binsrch test passing, would you have written an
                Message 7 of 7 , Jun 1 6:37 AM
                  Ron Jeffries wrote:

                  >
                  >Well ... I have a pattern that sounds similar. I get better objects if
                  >I start "top down" or "breadth first".
                  >
                  >However, since I try to practice YAGNI, I /cannot/ write rangeNotEmpty
                  >or midrange first. So I don't have quite the same reaction to the
                  >forces that you describe here ...
                  >

                  Excellent point.

                  If rangeNotEmpty had been more complex such that you feared going too
                  long without the binsrch test passing, would you have written an
                  individual test for rangeNotEmpty? Maybe that's more depth first.

                  Lately I've been listening for tests that break encapsulation in the
                  name of testability. It's usually a result of trying to individually
                  test methods like rangeNotEmpty that are already being tested through
                  binsrch. To your point, it's also a result of not practicing YAGNI.

                  Mike
                Your message has been successfully submitted and would be delivered to recipients shortly.