Re: Type System as Design Tool [Was: We do not use C++ exceptions]
thant.tessman@gmail.com (Thant Tessman) wrote (abridged):
So a 'contract' is what a programmer has decided to do in the case
that a stack is empty? Again, I'll try to ask the dumb question:
What makes a 'contract' different than "the decided-upon behavior"?
One purpose of the contract is to distinguish between: behaviour the
author decided upon incidentally, for the private convenience of the
implementation, that might vary with future implementations; and
behaviour that is essential, intended to be stable and reliable, even
across multiple implementations and versions of the code.
Contracts are especially important with polymorphism, because you can
then have multiple implementations within the same program. The contract
expresses what it is they are all guaranteed to have in common.
You cannot deduce the contract just from inspecting the implementation
because the implementation can be changed. The aim of contracts is to be
more stable than implementations. (They should also be more visible, more
explicit and more abstract.)
The programmer must explicitly take into account the fact that a
stack is perfectly welcome to be an empty stack.
Can you see that this is sometimes a problem? There has to be code to
handle that case. If the programmer could say, "the stack must not be
empty", then they wouldn't need that code.
You can try to express that statically, in the type system, and that can
be a good thing to do. Sometimes, though, it adds so much complexity to
the types that there's no net gain. And further, if we want our type
systems to be statically decidable (else what's the point?), then the
type system has to be limited. In particular it should not be Turing
Complete; if you can express the Halting Problem in your static type
system then you've gone astray. There are some constraints which are
simply too dynamic to encode into the static type system.
So we are left with a function that has a constraint that must be checked
at run-time. There are two places we can put the check: in the function
itself, or in the caller. You have argued, in effect, that the check
should always be in the function itself. One problem with this is that if
this function calls another that has the same constraint, it will end up
repeating the check. This leads to clutter in the program as well as
run-time costs, plus the usual maintenance issues from duplicated code.
If we shift the check to the caller, then we save code in the function,
which is good. In some cases the caller can shift the burden to its
caller, so it wins too. In other cases, the caller can trivially know the
constraint is true. For example, if the caller has just pushed something
onto the stack, it knows statically that the stack is not empty and
doesn't need any run-time check at all.
This is a common pattern: you move checks up the call-chain until you
reach the place best suited to dealing with them. The behaviour on
failing a check is then expressed in exactly one place, without
repetition.
Design by Contract helps manage all this because it provides a way to be
explicit about how responsibilities are divided between function and
caller.
Talk about the need to decide what to do in the empty-stack case
all you want, but nowhere does the explicit notion of preconditions,
postconditions, or invariants as described in the OO world bring
anything to this particular party.
Because you have required every function that gets something from a stack,
to handle the empty-stack case. Hence clutter, repeated code, run-time
costs.
In this version I never even wrote a 'top' function. There was
no need.
That's for unrelated reasons. "Top" in C++ is a non-mutating operation,
which you don't need because you've implemented "pop" without mutation.
It (and any contract it embodied) would be superfluous. More
than that, the function embodying the contract would--if we
were being strict--itself require a contract.
I'm not sure what you mean by "the function embodying the contract". It
sounds like a confusion about the levels of abstraction involved.
-- Dave Harris, Nottingham, UK.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]