Re: "Strong typing vs. strong testing"

[Peter Keller]

I don't think you demonstrated it is false. Any values larger than an
int get truncated before they ever get to maximum. The problem does
not lie with the maximum function. It correctly returns the maximum of
whatever two integers it is provided. Calling it with values that are
larger than an int, that get converted to an int _before_ maximum is
called, is an issue outside of maximum.

After thinking for a bit. I believe I can demonstrate a situation
where indeed maximum could return the wrong answer and it isn't due to
being passed incorrect input.

If, in maximum, after the entrance to the function call but right
before the comparison, a signal handler gets invoked, walks the stack,
swaps the two values for a and b, and returns back into maximum. Then
maximum will do the wrong thing. Since control flow was always in
a subgraph of the control flow graph through maximum, this would
classify as a failure given your strict view. (As an aside, one can
do the same thing with a debugger.)

Blocking the signals around the comparison and assignment of the
result to a temporary variable that you will return won't fix it.
This is because (in C) you must have a sequence point after the
unblocking of the signals and before the assignment of a temporary
variable holding the result to the return register, where, in fact,
another signal could arrive and again corrupt the results. Depending
upon the optimzation values of the compiler, it may or may not adjust
the ordering semantics of the assignment to the return register in
relation to the call to unblock the signals. The assignment of a
result to a return register is not defined to be something in C,
and can happen anywhere. But the C statements you used to write it
must adhere to sequence evaluation.

Since the signal handler could do anything, including completely
replacing the text segments and/r loaded libraries of the code or
move the PC to an arbitrary palce, I don't think you can "fix" this
problem. Ever.

If you think this is a pedantic case which never happens in practice,
I'm the maintainer of a well-known user space checkpointing system
where these types of problems have to be thought about deeply because
they happen.

In addition, there are other modes of error injection: in compute
clusters with very high density memory that is not ECC, you can
actually calculate the probability that a bit will flip at an address
in memory due to cosmic rays. That probability is disturbingly high.

Just an idle search online produced this article:

http://news.cnet.com/8301-30685_3-10370026-264.html

which mentions some statistics. Think 1 billion hours is a lot and
"it'll never happen"?

There are 8760 hours in a year. So, you'd only need 114,156 computers
in a cluster running for one year before amassing 1 billion hours
of computation. That isn't a big number for large financial companies,
google, etc, etc, etc to own.

As a fun statistic, the BlueGene/P supercomputer can have 884,736
processors with associated memory modules. According to the math
in the article, one BlueGene/P should see a max of ~600,000 memory
errors per year.

Sure, you might not think any of this is a problem, because your
home desktop always produces the right answer when balancing your
checkbook, but it is a matter of perception of scale. Lots of large
clusters and data movement houses go to great length to ensure data
integrity. Injecting wrong data 4 hours into a 6 month long workflow
running on thousands of computers really upsets the hell out of people.

I've run into physicists who simply run their buggy software over
and over and over again on the same data and do statistical analysis
on the results. They've come to the realization that they can't
find/fix/verify all the bugs in their code, so they assume they are
there and write systems which try to be mathematically robust to the
nature of the beast. It is cheaper to wait for 1000 runs of a program
to be computed on a cluster than to spend human time debugging a
difficult bug in the code.

So, mathematically, maximum can't fail inside of itself, realistically
while executing on a physical machine, you bet it'll fail.

-pete

 

[RG]

I would say "blow up" would be "raise an exception".


So run your compiler with a decent set of warning levels, and watch as
you are magically warned that you're passing an object of the wrong type.

My code compiles with no warnings under gcc -Wall.

On any given system, one or the other is true:

1. The constant 8589934592 is of type int, and the function will
"work" -- will give that result.
2. The constant is not of type int, and the compiler will warn you about
this if you ask.

It would be nice if this were true, but my example clearly demonstrates
that it is not. And if your response is to say that I should have used
lint, then my response to that will be that because of the halting
problem, for any static analyzer that you present, I can construct a
program that either contains an error that either your analyzer will not
catch, or for which it will generate a false positive. It just so
happens that constructing such examples for standard C is very easy.

rg

 

[RG]

You get a warning if you ask for it. If you choose to run without all
the type checking on, that's your problem.

My example compiles with no warnings under gcc -Wall.

Yes, I know I could have used lint. But that misses the point. For any
static analyzer, because of the halting problem, I can construct a
program that either contains an error that the analyzer will not catch,
or for which the analyzer will produce a false positive.

rg

 

[Seebs]

My code compiles with no warnings under gcc -Wall.

That's nice. gcc -Wall uses only a small subset of warnings that fit
the usual expectations of C code that's trying to work on common
architectures.

It would be nice if this were true, but my example clearly demonstrates
that it is not.

No, it doesn't, because you didn't ask for the relevant kind of warnings.

And if your response is to say that I should have used
lint, then my response to that will be that because of the halting
problem, for any static analyzer that you present, I can construct a
program that either contains an error that either your analyzer will not
catch, or for which it will generate a false positive. It just so
happens that constructing such examples for standard C is very easy.

I'm not sure that that's actually a halting problem case. The thing about
static typing is that we don't actually HAVE to solve the halting problem;
we only have look at the types of the components, all of which are knowable
at compile time, and we can tell you whether there's any unsafe conversions.

And that's the magic of static typing: It is not a false positive to
warn you that "2L" is not of type int. There are things which would be a
false positive in trying to determine whether something will be out of range
in a runtime expression, but which are not false positives in a statically
typed language.

-s

 

[Scott L. Burson]

We is why we all have run time tools called unit tests, don't we?

My post that kicked off this thread was not cross-posted, so many of the
participants may not have seen it. Here it is again, for your convenience:

---------------------

This might have been mentioned here before, but I just came across it: a
2003 essay by Bruce Eckel on how reliable systems can get built in
dynamically-typed languages. It echoes things we've all said here, but
I think it's interesting because it describes a conversion experience:
Eckel started out in the strong-typing camp and was won over.

https://docs.google.com/View?id=dcsvntt2_25wpjvbbhk

-- Scott

 

[RG]

And that's the magic of static typing: It is not a false positive to
warn you that "2L" is not of type int.

We'll have to agree to disagree about that. The numerical value 2 can
safely be represented as an int, so I would consider this a false
positive.

rg

 

[Scott L. Burson]

Here's a post I wrote earlier, before the conversation got cross-posted.
To me, this is the essence of the matter.

-----------------------

>
> OK, but sometimes it is handy to have the possibility to make compile-time
> assertions which prevent you from committing easily avoidable simple
> mistakes.

Agreed. I actually don't see this issue in black and white terms; I've
written lots of Lisp, and I've written lots of code in statically typed
languages, and they all have advantages and disadvantages. In the end
it all comes back to my time: how much time does it take me to ship a
debugged system? Working in Lisp, sometimes I don't get immediate
feedback from the compiler that I've done something stupid, but this is
generally counterbalanced by the ease of interactive testing, that
frequently allows me to run a new piece of code several times in the
time it would have taken me to do a compile-and-link in, say, C++.

So while I agree with you that compiler warnings are sometimes handy,
and there are occasions, working in Lisp, that I would like to have more
of them(*), it really doesn't happen to me very often that the lack of
one is more than a minor problem.

(*) Lisp compilers generally do warn about some things, like passing the
wrong number of arguments to a function, or inconsistent spelling of the
name of a local variable. In my experience, these warnings cover a
substantial fraction of the stupid mistakes I actually make.

-- Scott

 

[Keith Thompson]

On the first line of code inside foo().

Look again; there's no cast in foo().

That first line declare barf as an object of type "pointer to
function returning int", or more precisely, "pointer to function with
an unspecified but fixed number and type of parameters returning int"
(i.e., an old-style non-prototype declaration, still legal but
deprecated in both C90 and C99). It then initializes it to point
to the "maximum" function. I *think* the types are sufficiently
"compatible" (not necessarily using that word the same way the
standard does) for the initialization to be valid and well defined.
I might check the standard later.

It would have been better to use a prototype (for those of you
in groups other than comp.lang.c, that's a function declaration that
specifies the types of any parameters):

int (*barf)(int, int) = maximum;

IMHO it's better to use prototypes consistently than to figure out the
rules for interactions between prototyped vs. non-prototyped function
declarations.

[...]

 

[Paul Rubin]

Yes, I know I could have used lint. But that misses the point. For any
static analyzer, because of the halting problem, I can construct a
program that either contains an error that the analyzer will not catch,
or for which the analyzer will produce a false positive.

Can you describe any plausible real-world programs where the effort of
complicated static is justified, and for which the halting problem gets
in the way of analysis? By "real world", I meanI wouldn't consider
searching for counterexamples to the Collatz conjecture to qualify as
sufficiently real-world and sufficiently complex for fancy static
analysis. And even if it did, the static analyzer could deliver a
partial result, like "this function either returns a counterexample to
the Collatz conjecture or else it doesn't return".

D. Turner wrote a famous paper arguing something like the above, saying
basically that Turing completeness of programming languages is
overrated:

http://www.jucs.org/jucs_10_7/total_functional_programming

The main example of a sensible program that can't be written in a
non-complete language is an interpreter for a Turing-complete language.
But presumably a high-assurance application should never contain such a
thing, since the interpreted programs themselves then wouldn't have
static assurance.

 

[Pascal J. Bourguignon]

One might hypothesize that the best of both worlds would be a dynamic
language with a static analyzer layered on top. Such a thing does not
exist. It makes an instructive exercise to try to figure out why. (For
the record, I don't know the answer, but I've learned a lot through the
process of pondering this conundrum.)

There are static analysis tools for Common Lisp:
http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/code/tools/lint/0.html

or lisp in general. For example PHENARETE is in the category of static
analysis tools.

One could regret that they're not more developed, but I guess this only
proves the success of using dynamic programming languages: if there were
a real need for these tools, along with a good ROI, they would be more
developed. In the meantime, several test frameworks are developed.

 

[Pascal J. Bourguignon]

My example compiles with no warnings under gcc -Wall.

IIRC, -Wall is not reall ALL.

Try with: gcc -Wall -Wextra -Werror

I would still argue that should be the default, and if really there was
a need, there could be options to disable some warning, or to have some
errors be warnings...

 

[Keith Thompson]

Yes. I know. That was my whole point. There are ways to call a
function incorrectly (more broadly, there are errors in code) that a C
compiler is not required to diagnose.

Of course.

I'm not even saying it's a flaw in the language. All I'm saying is that
the original claim -- that any error in a C program will be caught by
the compiler -- is false, and more specifically, that it can be
demonstrated to be false without appeal to unknown run-time input.

Did someone *really* claim that "any error in a C program will
be caught by the compiler"? If so, I must have missed that.
It's certainly not true; code that compiles cleanly can be riddled
with errors. That's true in any language, but more so in C than
in some others.

As an aside, this particular error *could* be caught (and in fact would
be caught by other tools like lint), but there are errors that can not
be caught by any static analysis, and that therefore one should not be
lulled into a false sense of security by the fact that your code is
written in a statically typed language and compiled without errors or
warnings. That's all.

I don't believe anyone has said otherwise.

I would say that it is very, very hard to write correct code in C for
any non-vacuous definition of "correct". That is the reason that core
dumps and buffer overflows are so ubiquitous. I prefer Lisp or Python,
where core dumps and buffer overflows are virtually nonexistent. One
does get the occasional run-time error that might have been caught at
compile time, but I much prefer that to a core dump or a security hole.

I would say that it can certainly be difficult to write correct
code in C, but I don't believe it's nearly as hard as you think
it is. It requires more discipline than some other languages,
and it can require some detailed knowledge of the language itself,
particularly what it defines and what it doesn't. And it's not
always worth the effort if another language can do the job as well
or better.

 

[Pascal J. Bourguignon]

Never has execution halt.

I think a key reason in the big rise in the popularity of interpreted
languages

This is a false conception.

Whether the execution of a program is done by a processor of the
programming language, or a processor of another programming language
(and therefore requiring a translation phase), is a notion is NOT a
characteristic of programming language, but only of execution
environments.


1- There are C interpreters
CINT - http://root.cern.ch/root/Cint.html
EiC - http://eic.sourceforge.net/
Ch - http://www.softintegration.com

2- All the current Common Lisp implementations have compilers,

3- Most current Common Lisp implementations actually compile to native
code (ie they chose to translate to programming languages that are
implemented by Intel, AMD or Motorola. (Notice that these programming
languages are NOT implemented in hardware, but in software, called
micro-code, stored on the real hardware inside the
micro-processors); some choose to translate to C and call an external
C compiler to eventually translate to "native" code).

4- Actually, there is NO current Common Lisp implementation having only
an interpreter. On the contrary, most of the don't have any
interpreter (but all of them have a REPL, this is an orthogonal
concept).

5- Even the first LISP implementation made in 1959 had a compiler.

6- I know less the situation for the other dynamic programming language,
but for example, if CPython weren't a compiler, you should know that
CLPython is a compiler (it's an implementation of Python written in
Common Lisp, which translates Python into Common Lisp and compiles it).

is that when execution halts, they normally give a call
stack and usually a good reason for why things couldn't continue. As
opposed to compiled languages which present you with a blank screen
and force you to - fire up a debugger, or much much worse, look at a
core dump - to try and discern all the information the interpreter
presents to you immediately.

Theorically, a compiler for a static programming language has even more
information about the program, so it should be able to produce even
better backtrace in case of problem...

 

[Seebs]

We'll have to agree to disagree about that.

No, we won't. It's the *definition* of static typing. Static typing
is there to give you some guarantees at the expense of not being able
to express some things without special extra effort. That's why it's
static.

The numerical value 2 can
safely be represented as an int, so I would consider this a false
positive.

That's nice for you, I guess.

The point of static typing is that it makes it possible to ensure that
the values that reach a function are in fact of the correct type -- at
the cost of not being able to rely on free runtime conversions.

If you want to write safe conversions, you can do that. If you don't
bother to do that, you end up with errors -- by definition.

-s

 

[Seebs]

That first line declare barf as an object of type "pointer to
function returning int", or more precisely, "pointer to function with
an unspecified but fixed number and type of parameters returning int"
(i.e., an old-style non-prototype declaration, still legal but
deprecated in both C90 and C99). It then initializes it to point
to the "maximum" function. I *think* the types are sufficiently
"compatible" (not necessarily using that word the same way the
standard does) for the initialization to be valid and well defined.
I might check the standard later.

Hmm. You have a point. It's clearly a conversion from one type
to another.

IMHO it's better to use prototypes consistently than to figure out the
rules for interactions between prototyped vs. non-prototyped function
declarations.

Yes. It's clearly undefined behavior to call a function through a
pointer to a different type, or to call a function with the wrong number
of arguments. I am pretty sure at least one compiler catches this.

-s

 

[Ian Collins]

Yes, I can witness that it's in the mind set.

Well, the problem being always the same, the time pressures coming from
the sales people (who can sell products of which the first line of
specifications has not been written yet, much less of code), it's always
a battle to explain that once the code is written, there is still a lot
of time needed to run tests and debug it. I've even technical managers,
who should know better, expecting that we write bug-free code in the
first place (when we didn't even have a specification to begin with!).

Which is why agile practices such as TDD have an edge. If it compiles
*and* passes all its tests, it must be right.

 

[Ian Collins]

Yes. It's clearly undefined behavior to call a function through a
pointer to a different type, or to call a function with the wrong number
of arguments. I am pretty sure at least one compiler catches this.

Any C++ compiler will refuse to accept it.

C isn't really a strongly typed language and having to support archaic
non-prototyped function declarations makes thorough type checking
extremely difficult if not impossible.

 

[RG]

Can you describe any plausible real-world programs where the effort of
complicated static is justified, and for which the halting problem gets
in the way of analysis? By "real world", I meanI wouldn't consider
searching for counterexamples to the Collatz conjecture to qualify as
sufficiently real-world and sufficiently complex for fancy static
analysis. And even if it did, the static analyzer could deliver a
partial result, like "this function either returns a counterexample to
the Collatz conjecture or else it doesn't return".

D. Turner wrote a famous paper arguing something like the above, saying
basically that Turing completeness of programming languages is
overrated:

http://www.jucs.org/jucs_10_7/total_functional_programming

The main example of a sensible program that can't be written in a
non-complete language is an interpreter for a Turing-complete language.
But presumably a high-assurance application should never contain such a
thing, since the interpreted programs themselves then wouldn't have
static assurance.

There are only two possibilities: either you have a finite-state
machine, or you have a Turning machine. (Well, OK, you could have a
pushdown automaton, but there are no programming languages that model a
PDA. Well, OK, there's Forth, but AFAIK there are no static type
checkers for Forth. Besides, who uses Forth? ;-)

If you have a finite state machine everything is trivial. If you have a
Turing machine everything is generally impossible. This is an
oversimplification but not far from the fundamental underlying truth.

My favorite practical example is the square root function. The standard
C library defines a square root function on floats (actually on
doubles), which is to say, over a finite-state model with 2^64 states.
The model is not well defined over half of that range (negative
numbers), which the static type checker cannot catch because there is no
such thing as an unsigned double.

But the fun doesn't stop there. Doubles >= 0.0 are not the only thing
one might reasonably want to take a square root of, and indeed C++
overloads sqrt to work on complex and valarray types in addition to
floats of various lengths (though you still have to manually keep track
of whether or not the argument to sqrt might be a negative real). But
what if I want an exact integer square root? Or a square root of a data
type that represents irrational numbers not as floating point
approximations but as exact symbolic representations? I haven't worked
out the details, but I'd be surprised if none of these variations turned
out to be Turing complete.

The Turner paper is right on point: there's a fundamental distinction
between the (known) finite and the (potentially) infinite. In my
experience most of the cool interesting stuff has been found in the
latter domain, and trying to shoehorn the latter into the former is more
trouble then it's worth.

rg

 

[ImpalerCore]

[ron@mighty:~]$ cat foo.c
#include <stdio.h>

int maximum(int a, int b) { return a > b ? a : b; }

int main() {
  long x = 8589934592;
  printf("Max of %ld and 1 is %d\n", x, maximum(x,1));
  return 0;}

[ron@mighty:~]$ gcc -Wall foo.c
[ron@mighty:~]$ ./a.out
Max of 8589934592 and 1 is 1

In the context of procedural programming, there is always an implicit
contract between the function and its client. If you're going to fool
around sending cleverly crafted garbage into the input of 'maximum'
due to C conversion rules, why do you expect the 'maximum' function to
be responsible for producing the correct response to an ill-formed
question? What alternative behavior of 'maximum' would you prefer to
see, that the C language auto-promote the function arguments and
return type to type long based on the type of arguments provided to
the 'maximum' function?

You either learn to play in the sandbox that C provides, splinters and
all, or you find another sandbox.

Best regards,
John D.

 

[Keith Thompson]

My code compiles with no warnings under gcc -Wall.

Conclusion: "-Wall" is not "a decent set of warning levels" in this
context, in spite of the name. (If you want to complain that the
name "-Wall" is misleading, I won't disagree, but it's a gcc issue,
not a C issue.)

With "-Wconversion", I get:

c.c: In function 'main':
c.c:7: warning: passing argument 1 of 'maximum' with different width due to prototype

[...]

It would be nice if this were true, but my example clearly demonstrates
that it is not. And if your response is to say that I should have used
lint, then my response to that will be that because of the halting
problem, for any static analyzer that you present, I can construct a
program that either contains an error that either your analyzer will not
catch, or for which it will generate a false positive. It just so
happens that constructing such examples for standard C is very easy.

And yet you have not managed to do it.

It seems to me that the line between errors that a sufficiently
clever compiler could or should warn you about, and errors that
compilers cannot reasonably be expected to detect, is a very
fuzzy one. A fairly clear example of the latter is:

const double pi = 2.71828182845904523526;

To a human reader, it's obviously either a mistake or deliberate
obfuscation, but I'm not sure I'd *want* my compiler to warn me
about it just because I named the object "pi" rather than "e".
(And if I called it "x", even an intelligent human wouldn't know
that it's wrong.)