2

To reiterate the question - what does it mean to have a weaker or stronger postcondition when overriding a method that only does side effects with another one that only does side effects?

P.S. What about a mix of side effects & return values?

2

A Stronger Post-Condition -> Guarantees More

Essentially not only will it do X, it will also do X this way.

If it returns a type Shape, then a stronger post-condition might be that it returns a type Quadrilateral which derives from Shape.

If it throws an exception, then a stronger post-condition might limit the kinds of exception, or even not throw at all.

Similarly for side-effects. If the original agreement was that it updates some object Bread by Cooking it, then a stronger post-condition would be to Cooking it in a Bread Oven. The former agreement equally permits a flame-thrower, and use of lava.

A more computer sciencey example would be sorting. void sort(data[]) with the post-condition being that data conforms to for i..datalength-2 -> data[i] <= data[i+1].

void logsort(data[]) implements that agreement, except it has a stronger post-condition: Stable Sort.

A Stable Sort also guarantees that elements that would compare equal maintain there relative order.

Given: [ d, c1, a, c2, b, e, c3]
where c1 == c2 == c3, and all the letters sort: a, b, c, d, e

A sort might give:
   [ a, b, c3, c1, c2, d, e]
or [ a, b, c1, c3, c2, d, e]
or [ a, b, c2, c3, c1, d, e]
or ...

Log Sort would always give:
   [ a, b, c1, c2, c3, d, e]

Log Sort as such has a Stronger Post Condition.

That isn't the only Post-Condition that Log-Sort provides. It also guarantees that it will be finished in O(NlogN) (with a sizeable coeffiecient, and overhead for allocating buffer space and move elements around).

Another Sort such as void quicksort(data[]) also implements the sort guarantees and offers a stronger guarantee by sorting the data in O(nlogn) with a worst case of W(N^2).

Generally speaking a quicksort will be faster than a logsort for most unsorted data, at the price of not necessarily maintaining the relative order of equivalent elements. Which means that while both sorts provide stronger post-conditions than is required by void sort(data[]) they aren't necessarily stronger or weaker than each other.

| improve this answer | |
  • Beware of context. In this answer, you are defining your post condition based on the order of the elements, and are glossing over the performance. One could argue that your log sort is no longer a quick sort since you're now taking extra time to ensure the order of elements. If the purpose of the quicksort was specifically to be as quick as it can be (which, given the name, is going to be likely), then your post condition has weakened when you observe that performance as the goal (second only to the ordering of the elements itself of course). – Flater May 25 at 9:32
  • A good point. It does depend upon what is in the original agreement. I was considering the agreement of void sort(data[]) with the post-condition being that data conforms to for i..datalength-2 -> data[i] <= data[i+1] – Kain0_0 May 25 at 9:36
  • I agree. Maybe its purpose was to be a sort (nothing more), and the simplest one just happens to be called a "quicksort" even though quickness isn't a requirement. In that case, your answer is correct (it could've been called "dumbsort" - which would preclude the issue I pointed out). But if the quickness is a cornerstone of the quicksort's purpose, then its derivations should similarly prioritize quickness as well. – Flater May 25 at 9:39
  • @flater Technically quicksort is a N^2 algorithm (at least in its worst case), while logsort is a strict NlogN. Even though in most implementations quicksort will beat a logsort by a margin for most cases simply due to unavoidable overheads in logsort. Though i do take your point, I should have used something like DumbSort for illustration. – Kain0_0 May 25 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.