Elementry question on indeces

[Kragen Sitaker]

In article <38C1EAA7.4F48FC57 at python.net>,
Thomas A. Bryan <tbryan at python.net> wrote:
>Rick wrote:
>[..in a reply to an answer to a sequence slicing question..]
>> 
>> OK, got it....thanks.
>> 
>> I would question why it's done this way, but I guess I should read on.
>
>I often find it convenient that Lst[x:z] covers the same elements as does 
>Lst[x:y] and Lst[y:z] for any indices 0 <= x <= y <= z <= len(Lst).  Perhaps 
>you'll come to like this feature when you start using it more often in your 
>Python programs.

My early experience as a programmer was marred by many off-by-one
errors.  Eventually, I discovered the STL (now the core of the C++
standard library), which uses this same convention (just like Python
slices and range()) for all of its ranges.

I discovered that consistently doing things that way eliminated the
majority of my off-by-one errors, especially in languages where array
indices start at 0.

Other useful properties, in addition to x:z being the union of x:y and y:z, 
include:
- the number of elements in x:y is y-x, not y-x+1 or y-x-1.
- as a result, you don't need to write "len(array)-1" unless you're
  leaving an element off the end of something --- 0:len(array) is the
  whole array.  Even better, if you're leaving two elements off the
  end, you don't have to write "len(array)-3" (in which case you are
  very likely to write "len(array)-2" instead.)
- an empty range, which if extended by one element would include
  element 0, doesn't have an end of -1.

Much of what I've learned as I've become a better programmer has been
things like this.  It's certainly possible to get your program to work
if you use (x, y) to mean a range from x to y inclusive, or x-1 to y+1,
or whatever.  It just takes more thought.  It's even possible to get
your program to work if you mix and match, and (x, y) means "x to y
inclusive" to one function and "x to y-1 inclusive" to another.

It just takes more thought.

The distinguishing feature of an expert is that they do not have to
think about what they are doing.  

I am an expert at walking.  I do not have to think about moving my feet
unless the ground is very rough.  (I am not an expert at walking on
very rough ground.)  Instead, I am free to think about where I want to
walk.

I am an expert driver.  I don't have to think about shifting gears; I
don't have to think about moving the steering wheel, or moving my hands
on the steering wheel.  Instead, I am free to think about where I am
going, what is going on around me, and how fast the car is moving.

Expert musicians I know do not think about their fingering.  They are
free to think about the emotions they are expressing instead.

I am noticeably more expert at automatic-transmission driving than at
manual-transmission driving.  This is because manual-transmission
driving is more difficult, and it takes longer to become an expert.
There is more to pay attention to --- or, rather, to internalize the
skills of coping with so no attention is required.

Practices like this convention about expressing ranges, and like
goto-less programming, reduce the amount of stuff you have to get
right.  They avoid adding extra difficulty to a task that is, in
general, already quite difficult.

There is an excellent parable by Edsger W. Dijkstra about this subject,
published as Edsger W. Dijkstra note EWD594; it is on the Web at
http://www.cbi.umn.edu/inv/burros/ewd594.htm.  It is presumably
copyright Burroughs Corporation, 1973; I reproduce it here because I
have had trouble reaching the Web server this morning.

EWD594 - 0 

(Recently I found the following text in manuscript among old papers of
mine. It must have been written in the middle of 1973, but I don't
think that in the intervening three years it has lost anything of its
significance.  Hence I now incorporate it in the EWD-series.)

A parable. 

Years ago a railway company was erected and one of its directors
-- probably the commercial bloke -- discovered that the initial
investments could be reduced significantly if only fifty percent of the
cars would be equipped with a toilet, and, therefore, so was decided.

Shortly after the company had started its operations, however,
complaints about the toilets came pouring in.  An investigation was
carried out and revealed that the obvious thing had happened: despite
its youth the company was already suffering from internal communication
problems, for the director's decision on the toilets had not been
transmitted to the shunting yard, where all cars were treated as
equivalent, and, as a result, sometimes trains were composed with
hardly any toilets at all.

In order to solve the problem, a bit of information was associated with
each car, telling whether it was a car with or without a toilet, and
the shunting yard was instructed to compose trains with the numbers of
cars of both types as equal as possible. It was a complication for the
shunting yard, but, once it had been solved, the people responsible for
the shunting procedures were quite proud that they could manage it.

When the new shunting procedures had been made effective, however,
complaints about the toilets continued. A new investigation was carried
out and then it transpired that, although in each train about half the
cars had indeed toilets, sometimes trains were composed with nearly all
toilets in one half of the train. In order to remedy the situation, new
instructions were issued, prescribing that cars with and cars without
toilets should alternate. This was a move severe complication for the
shunting people, but after some initial graumbling [sic], eventually
they managed.

Complaints, however, continued and the reason turned out to be that, as
the cars with toilets had their toilet at one of their ends, the
distance between two successive toilets in the train could still be
nearly three car lengths, and for mothers with children in urgent need
-- and perhaps even luggage piled up in the corridors -- this still
could lead to disasters. As a result, the cars with toilets got another
bit of information attached to them, making them into directed objects,
and the new instructions were, that in each trains [sic] the cars with
toilets should have the same orientation. This time, the new
instructions for the shunting yard were received with less than
enthusiasm, for the number of truntables [sic] was hardly sufficient;
to be quite fair to the shunting people we must even admit that
according to all reasonable standards, the number of turntables was
insufficient, and it was only by virtue of the most cunning ingenuity,
that they could just manage.

With all toilets equally spaced along the train the company felt
confident that now everything was alright, but passengers continued to
complain: although no passenger was more than a car length away from
the nearest toilet, passengers (in urgent need) did not know in which
direction to start their stumbling itinary [sic] along the corridor! To
solve this problem, arrows saying "TOILET" were fixed in all corridors,
thereby also making the other half of the cars into directed objects
that should be properly oriented by the shunting procedure.

EWD594 - 1 

When the new instruction reached the shunting yard, they created an
atmosphere ranging from despair to revolt: it just couln't [sic] be
done! At that critical moment a man whose name has been forgotten and
shall never be traced, made the following observation. When each car
with a toilet was coupled, from now until eternity, at its toileted end
with a car without a toilet, from then onwards the shunting yard,
instead of dealing with N directed cars of two types, could deal with
N/2 identical units that, to all intents and purposes, could be
regarded as symmetrical. And this observation solved all shunting
problems at the modest price of, firstly sticking to trains with an
even number of cars only -- the few additional cars needed for that
could be paid out of the initial savings effected by the commercial
bloke! -- and, secondly, slightly cheating with regard to the equal
spacing of the toilets. But, after all, who cares about the last three
feet?

Although at the time that this story took place, mankind was not
blessed yet with automatic computers, our anonymous man who found this
solution deserves to be called the world's first competent programmer.

* * * 

I have told the above story to different audiences. Programmers, as a
rule, are delighted by it, and managers, invariably, get more and more
annoyed as the story progresses; true mathematicians, however, fail to
see the point.

Platasnstreat 5                         prof.dr.Edsger W. Dijkstra
NL-4565 NUENEN                          Burroughs Research Fellow
The Netherlands
-- 
<kragen at pobox.com>       Kragen Sitaker     <http://www.pobox.com/~kragen/>
The Internet stock bubble didn't burst on 1999-11-08.  Hurrah!
<URL:http://www.pobox.com/~kragen/bubble.html>
The power didn't go out on 2000-01-01 either.  :)