Reversing a linked list

[Tony]

Yes, I know a little about Eiffel. My point it is that as soon as a
condition moves from being part of the caller's contract to part of
the function's responsibility,
it stops being a precondition; it
becomes part of the defined behaviour of the function.

There is "precondition (tm)" as in Eiffel, and then there is the basic
concept that existed way before Eiffel showed up. B. Meyer didn't invent
the concepts, and the concepts are what is important, not the
terminology. The responsibility for usage does not "move". Would you
really want to use a library that didn't do its due diligence in argument
checking? You may have made one of those "programmer error" things and
maybe the code would still "work", i.e., not crash, but be erroneous and
maybe you'd catch it elsewhere or maybe not.
Maybe at one time lack of argument checking could have been considered a
"quality of implementation" issue, but today (and long has been) that is
a difference between professional code and Programming 101 student code.

 

[Tony]

Le 16/09/11 16:21, ImpalerCore a écrit :

I would agree with that. For instance, "Reverse" needs a list with no
cycles.

It would be hugely expensive to test this precondition (I gave the
code for the test in an answer to Ben) since implies going through
all the list. But you are right that all the preconditions should be
explicitely documented, even if untested in the code.

The other precondition is that the list must be terminated by a NULL
pointer and all the Next pointer must be valid.

The first part can be easily tested with:

if (l->count > 0) assert(l->Last->Next == NULL);

That is an example of an invariant rather than a precondition.

This is cheap to do because the header structure stores a pointer
to the last element. But if there is no pointer to the last element
we have to go through the whole list, what makes testing for that
precondition extremely expensive.

It can be expensive though because that would only be active during
development of the data structure. After the development of the data
structure is completed, that can be removed (remove #define
CHECK_INVARIANTS) for the data structure should be designed to guarantee
that. In this case, the invariant check is a data structure development
aid, nothing more.

 

[Ben Bacarisse]

That would be living dangerously indeed. That kind of programming went
out in the, er, well apparently it hasn't, for you are still doing
that!

I bet that you are doing it too. Does your binary search function check
that the list is sorted? How do you check that your sort function's
compare function does, in fact, induce a correct ordering? To get more
on topic, how do you check, in C, that a function taking a pointer is
passed a valid one? Or one that it points to enough data. Or...

These things -- that a function assumes about it's parameters -- are
what I call pre-conditions. I accept you may not like that term, but
these unchecked or uncheckable things need a name. What do you call
them?

No it doesn't. It just means that when someone violates the precondition,
something controlled and defined happens rather than "anything can
happen". All arguments to public functions need to be verified*.

Mostly I agree, though I think you must agree that this is (a) not
possible in all cases, and (b) often deliberately not done even when
possible due to cost. My point was not "don't check you arguments" but
"those things you assume are pre-conditions; those that you check for
are part of the defined behaviour of the function" (though I accept
there is some grey here).

No. (I'm not referring to B. Meyer's definitions though, but rather my
own).

OK. I don't want to argue about definitions. It's interesting that
this term is used in different ways.

<snip>

 

[Ben Bacarisse]

There is "precondition (tm)" as in Eiffel, and then there is the basic
concept that existed way before Eiffel showed up. B. Meyer didn't invent
the concepts, and the concepts are what is important, not the
terminology. The responsibility for usage does not "move". Would you
really want to use a library that didn't do its due diligence in argument
checking? You may have made one of those "programmer error" things and
maybe the code would still "work", i.e., not crash, but be erroneous and
maybe you'd catch it elsewhere or maybe not.
Maybe at one time lack of argument checking could have been considered a
"quality of implementation" issue, but today (and long has been) that is
a difference between professional code and Programming 101 student
code.

How do conclude, from what I said, that I am advocating a lack of due
diligence or not checking arguments?

 

[HENRY Eshbaugh]

Readable, elegant, correct: pick any two!

I just noticed the bug. My bad.


void reverse_list(ListElement *head)
{
if (head == NULL) return;
__reverse_list(head->next, head);
return;
}

void __reverse_list(ListElement *this, ListElement *next)
{
if (this == NULL) return;

if (next->next) __reverse_list(next, next->next);

next->next = this;
}

Now it works.

 

[HENRY Eshbaugh]

You shouldn't use names starting with a double underscore, they are
reserved for the implementation.

If that's not the implementation of the algorithm, then what is it?

 

[Tony]

How do conclude, from what I said, that I am advocating a lack of due
diligence or not checking arguments?

By suggesting that documentation can preclude doing argument checking,
thereby "throwing the problem over the wall" making it the programmer's
problem for not reading "the directions".

 

[Tony]

I bet that you are doing it too.

I'll take that bet!

Does your binary search function
check that the list is sorted?

If in usage I did that, then it would be a bug. No need to move to a
higher level of abstraction in this issue. The issue is simple argument
checking in a simple case. Of course (!) the concepts should be applied
at higher levels too, but there is no need to complicate the simple case
(assumed for obvious reasons) in discussion.

How do you check that your sort
function's compare function does, in fact, induce a correct ordering?
To get more on topic, how do you check, in C, that a function taking
a pointer is passed a valid one? Or one that it points to enough
data. Or...

Again, that is at the program level and the concepts still apply, but
stick to the simple case please and the topic at hand which is exactly
that documentation cannot replace argument checking. Well it can, but
that is "bad programming" and "worst practice".

These things -- that a function assumes about it's parameters -- are
what I call pre-conditions. I accept you may not like that term, but
these unchecked or uncheckable things need a name. What do you call
them?

Alright, if that is what you meant. "Preconditions" is fine for the
those, if you want to use the term that way. I tend to think of
"precondition" as something that can be checked within the callee. That
you have to guarantee what you are talking about at the higher level,
seems to indicate it needs another name (or so I would have it, and
reserve "precondition" for the way I use it). "Guarantee" fits in there
somewhere, surely, as in, "the program has guaranteed that the list is
sorted by design". Instead of saying, "This library function call has the
precondition that the list must be sorted.", say "The program must
guarantee that the list is sorted". Violate a "precondition", then, and
no problem, something well-defined will happen during development/testing
to keep that bug out of the code. Violate a required guarantee though,
and you're hosed.
At the higher level during development, the instrumentation must be in
place to ensure that the required guarantees are indeed being designed
against. There doesn't appear to be avenue for formality (like there is
with argument precondition checking), other than the specification of
required guarantees.

So, how about "required guarantees" (to answer your question)? (I just
came up with it from the above thoughts).

Mostly I agree, though I think you must agree that this is (a) not
possible in all cases,

Not with your definition of "precondition". Though you must have said it
rather generally for me to jump all over it. I.e., included the argument
checking that CAN be done in what you wrote. Further, I don't think the
Eiffel usage includes such in its concept of "precondition" (?) and
weren't you alluding to that as some kind of litmus of "precondition"
terminology definition?

and (b) often deliberately not done even when
possible due to cost.

No, that is not an option. I don't know what other people/groups/whatever
are doing with that these days for I've been away from that for so long.
But, yes, I can fathom that that may be being done somewhere. Now THAT is
a quality issue and that would not only be low quality software, but an
inadequate development capability/process/outfit/etc. You just can't
shortcut this stuff and hope for the best. Any software is only as good
as the "weakest link" within it. If it breaks in deployment, the plane
won't go down, but if EVERYONE were to be doing that shitty of a job, it
just might do exactly that!

My point was not "don't check you arguments"

I thought that your point was that specification of "preconditions" is
adequate -- checking by the library, when it can do so, is optional.

but "those things you assume are pre-conditions; those that you check
for are part of the defined behaviour of the function" (though I
accept there is some grey here).

Not really, IMO, because it's the error path, not the mainline. The
behavior is the description of the error handling mechanism rather than
the application-program-specific behavior. IOW, that's the behavior IN
ALL the functions of the program upon error (or simply checking on
non-error, of course). It's like an "aspect".

OK. I don't want to argue about definitions. It's interesting that
this term is used in different ways.

To what I said above, I think my own definition is like Meyer's (I don't
know his EXACTLY) and unlike yours.

 

[Tony]

If that's not the implementation of the algorithm, then what is it?

By "implementation", Ian meant "the compiler". That is what is typically
understood as "the implementation". As in, "the implementation of the
language".

(Aside: Isn't a single underscore suggested for use by libraries?).

 

[jacob navia]

Le 17/09/11 05:15, Tony a écrit :

And Tony answered:
By suggesting that documentation can preclude doing argument checking,
thereby "throwing the problem over the wall" making it the programmer's
problem for not reading "the directions".

Not all preconditions can be tested. For instance I proposed a routine
to test if a list is circular. It involves examining all the list.

If a library (like the C Containers library) would do that, its
performance would be close to zero.

And please do not forget that the routine to test the circularity of a
list`has its OWN preconditions too: the "next" pointers must be valid.

There is a point where testing everything becomes such a burden that it
is practically impossible and you *HAVE* to just write it down in the
documentation only.

 

[jacob navia]

Le 17/09/11 02:37, Tony a écrit :

Wishful thinking?
No.

The truth is surely that C/C++ are well within the
black hole now with no chance of escaping its mighty pull.

It is you that are in that black hole.
Proof: You see everything as doomed and the future is black ...

[snipped "foundations of data structures and algorithms" stuff]

How is "foundations of data structures and algorithms" (via YOUR library,
no less) on topic?

Because I say so. You do not like it?
Don't read my posts.

And pleeeeze, since C/C++ are in the black hole as
you say, there is no point in discussing anything here.

Just go away.

Are you not tryig to commandiere this NG to your
personal agenda?

Yes, I have a vested interest in reversing linked lists. Each
time somebody reverses a list I earn money you know?

Should all library vendors start posting examples in
here about usage of their products?

Yes, I am sure that Microsoft will come here to put ads
for C#

See the point?

Yes. You are a troll that doesn't like C and post stuff here
just to inflate your own ego.

C/C++ (whatever that is) is obsolete?

OK, then there is no point in discussing software in "C/C++".
GO AWAY.

 

[Tony]

Le 17/09/11 05:15, Tony a écrit :

Not all preconditions can be tested.

It seems to be a defintions (i.e., what is a "precondition"?) problem.
See the other posts in this thread.

For instance I proposed a routine
to test if a list is circular. It involves examining all the list.

I saw that and quickly guessed you were wanting an invariant, not a
precondition.

If a library (like the C Containers library) would do that, its
performance would be close to zero.

And please do not forget that the routine to test the circularity of a
list`has its OWN preconditions too: the "next" pointers must be valid.

Again, that's a development-time thing to work out via assertions,
invariants, etc.

There is a point where testing everything becomes such a burden that it
is practically impossible and you *HAVE* to just write it down in the
documentation only.

Well, no, this is exactly the kind of thing I was saying is inacceptable.
Sounds like "seat of the pants programming", and there is no way that is
ever going to work effectively. Everything you can check, you must. Else
reanalyze/redesign something if it seems "too heavy on the checking".
Maybe "all that checking" is hinting for the reanalysis/redesign.

Take a look at the other posts I made in response to Ben so I don't have
to repeat everything. Note my attempt at moving some things into the
realm of "required guarantee" to distinguish from "precondition" just to
make it clearer.

 

[Tony]

Le 17/09/11 02:37, Tony a écrit :

No.

What are the statistics? How many new C programmers are there each year?
Is the total number of C programmers increasing or decreasing?

It is you that are in that black hole.
Proof: You see everything as doomed and the future is black ...

When did C and C++ become "everything"? Did you mean that C/C++ means
everything to you?

[snipped "foundations of data structures and algorithms" stuff]

How is "foundations of data structures and algorithms" (via YOUR
library,
no less) on topic?

Because I say so. You do not like it?
Don't read my posts.

For the most part, I don't. The lead-in was semi-interesting, and the
rest I considered doldrum, off-topic and agenda-ish. After 1000 years of
C or whatever, now there's nothing better to talk about than "elementary
data structure principles in C" and your personal container project?
There are project websites for stuff like that you know, and for a
reason. Think about it: your project can have it's own little exclusive
home on the web somewhere where all talk can be of nothing but it 24x7.

And pleeeeze, since C/C++ are in the black hole as
you say, there is no point in discussing anything here.

Just go away.

No need to get all snipey. Geez.

Yes, I have a vested interest in reversing linked lists. Each
time somebody reverses a list I earn money you know?

There is a NG called comp.programming you know. Probably one on
algorithms and data structures too.

Yes, I am sure that Microsoft will come here to put ads
for C#

My bad. I meant every joe coder with his endeavors in trying to
understand linked lists for the first time. How is such elementary
endeavoring apt to attract C programmers or anyone who is ("foolishly",
hehe) learning C? C's supposed to be so mature and capable of very
sophisticated low-level tasks but its NG is about struggling with
linked-list concepts? It makes it seem like the once verile C is now
decrepit and back in diapers. How about some respect as it gets sucked
into the black hole to oblivion.

See the point?

Yes. You are a troll that doesn't like C and post stuff here
just to inflate your own ego.

C/C++ (whatever that is) is obsolete?

Yes, of course they are, but the transitionary period length is unknown
at this time, though preparation and some moves have already begun.

OK, then there is no point in discussing software in "C/C++".
GO AWAY.

Oh, ha, ha, ha. You jokester you!

 

[Ian Collins]

What are the statistics? How many new C programmers are there each year?
Is the total number of C programmers increasing or decreasing?

They are certainly increasing in my part of the world. As long as the
demand for embedded devices keeps growing, so will the demand for C and
C++ programmers.

 

[Tony]

They are certainly increasing in my part of the world. As long as the
demand for embedded devices keeps growing, so will the demand for C and
C++ programmers.

I could believe that. That would mean that the exodus from C/C++ for
other than systems-level work has come close to the end and now that one
category is seeing an increase. It would be very interesting to see
graphs of the number of users of various programming languages over a
long period of time, say from the 80's to now. If anyone has a link to
such info, please don't keep it a secret!

 

[Willem]

HENRY Eshbaugh wrote:
)> Readable, elegant, correct: pick any two!
)
) I just noticed the bug. My bad.
)
)
) void reverse_list(ListElement *head)
) {
) if (head == NULL) return;
) __reverse_list(head->next, head);
) return;
) }
)
) void __reverse_list(ListElement *this, ListElement *next)
) {
) if (this == NULL) return;
)
) if (next->next) __reverse_list(next, next->next);
)
) next->next = this;
) }
)
) Now it works.

Doesn't that effectively push the entire linked list up the stack first,
and then go down the stack again to build the reversed list ?
Seems wasteful to me, when it can be done in O(1) space.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Ben Bacarisse]

By suggesting that documentation can preclude doing argument checking,
thereby "throwing the problem over the wall" making it the programmer's
problem for not reading "the directions".

I hope you now accept that that is not what I was saying. In case there
is any doubt: I am not saying that.

 

[BartC]

Ben Bacarisse wrote:

Again, that is at the program level and the concepts still apply, but
stick to the simple case please and the topic at hand which is exactly
that documentation cannot replace argument checking. Well it can, but that
is "bad programming" and "worst practice".

Documentation ensures that if anything goes wrong due to wrong inputs, then
it is the caller's fault. (In the same way that if a circuit doesn't work as
expected, you check that it is being driven according to spec.)

And there are many, many reasons why not every possible input can be
verified.

However I don't recall you posting any code showing us all how these things
should be done!

 

[jacob navia]

Le 17/09/11 13:48, BartC a écrit :

And there are many, many reasons why not every possible input can be
verified.

However I don't recall you posting any code showing us all how these things
should be done!

Like, (for instance), verifying that you got a correct pointer pointing
to a correct object of the specified length.

 

[jacob navia]

Le 17/09/11 17:07, Richard Harter a écrit :

Well, no, it wouldn't. The cost of checking whether a linked list
terminates in a cycle is of the same order as the cost of reversing
the list.
Yes.

One could even integrate cycle checking into the reversal
code.

This is a VERY good idea, I didn't even think about that but now
that you mention it, it is obvious.

Easy since we have already one pointer that goes through the list. We
could setup a second pointer, incrementing it twice as fast. This
would cost for a list of length N:

1) A test for pointer equality (N times)
2) A conditional jump (N times)
3) A test for NULL (N / 2 times)
4) An extra pointer dereferencing. (N / 2 times)

In a modern machine with a pipeline depth of 32 instructions (say)
the 1 and 2 would cost not even a cycle since the conditional branch
would be correctly predicted. For a pipeline depth of 32 it would
cost (2/32 --> 1/16 cycle)

The same analysis for 3: also a cost of 1/16 makes 1/8 cycle for
a pipeline depth of 32.

For 4 we have the extra cost of loading a cache line when
the "next" pointer dereferences data that is not in the cache.

For the worst case when the list is too big to fit into the L1 or L2
caches (several MB) we would double the cost of loading the list into
the cache, probably doubling the running time or more.

Mmmmmm... That would be the real show stopper.

If one does that one could also reverse a cycle terminated
linked list by defining the new head as the node that joined the
cycle. I don't suppose you would want to do that but it could be done
cheaply enough.

More or less, see the analysis above. But it is a very good idea. I will
integrate it into the solved exercises.


Thank you very much for this contribution.