Are prototypes required for all functions in C89, C90 or C99?

It depends on what you mean by 'truly standards compliant'. However, the short answer is "it is a good idea to ensure that all functions have a prototype in scope before being used".

A more qualified answer notes that if the function accepts variable arguments (notably the printf() family of functions), then a prototype must be in scope to be strictly standards compliant. This is true of C89 (from ANSI) and C90 (from ISO; the same as C89 except for the section numbering). Other than 'varargs' functions, though, functions which return an int do not have to be declared, and functions that return something other than an int do need a declaration that shows the return type but do not need the prototype for the argument list.

Note, however, that if the function takes arguments that are subject to 'normal promotions' in the absence of prototypes (for example, a function that takes a char or short - both of which are converted to int; more seriously, perhaps, a function that takes a float instead of a double), then a prototype is needed. The standard was lax about this to allow old C code to compile under standard conformant compilers; older code was not written to worry about ensuring that functions were declared before use - and by definition, older code did not use prototypes since they did not become available in C until there was a standard.

C99 disallows 'implicit int'...that means both oddball cases like 'static a;' (an int by default) and also implicit function declarations. These are mentioned (along with about 50 other major changes) in the foreword to ISO/IEC 9899:1999, which compares that standard to the previous versions:

• remove implicit int
  …
• remove implicit function declaration

In ISO/IEC 9899:1990, §6.3.2.2 Function calls stated:

If the expression that precedes the parenthesized argument list in a function call consists solely of an identifier, and if no declaration is visible for this identifier, the identifier is implicitly declared exactly as if, in the innermost block containing the function call, the declaration:

extern int identifier();

appeared.³⁸

³⁸ That is, an identifier with block scope declared to have external linkage with type function without parameter information and returning an int. If in fact it is not defined as having type “function returning int,” the behavior is undefined.

This paragraph is missing in the 1999 standard. I've not (yet) tracked the change in verbiage that allows static a; in C90 and disallows it (requiring static int a;) in C99.

Note that if a function is static, it may be defined before it is used, and need not be preceded by a declaration. GCC can be persuaded to witter if a non-static function is defined without a declaration preceding it (-Wmissing-prototypes).

A prototype is a function declaration that specifies the types of the function's parameters.

Pre-ANSI C (the language described by the 1978 first edition of Kernighan & Ritchie's "The C Programming Language") did not have prototypes; it was not possible for a function declaration to describe the number or types of the parameters. It was up to the caller to pass the correct number and type of arguments.

ANSI C introduced "prototypes", declarations that specify the types of the parameters (a feature borrowed from early C++).

As of C89/C90 (the ANSI and ISO standards describe the same language), it's legal to call a function with no visible declaration; an implicit declaration is provided. If the implicit declaration is incompatible with the actual definition (say, calling sqrt("foo"), then the behavior is undefined. Neither this implicit declaration nor a non-prototype declaration can be compatible with a variadic function, so any call to a variadic function (like printf or scanf) must have a visible prototype.

C99 dropped implicit declarations. Any call to a function without a visible declaration is a constraint violation, requiring a compiler diagnostic. But that declaration is still not required to be a prototype; it can be an old-style declaration that doesn't specify parameter types.

C11 made no significant changes in this area.

So even as of the 2011 ISO C standard, old-style function declarations and definitions (which have been "obsolescent" since 1989) are still permitted in conforming code.

For all versions of C going back to 1989, as a matter of style, there is very little reason not to use prototypes for all functions. Old-style declarations and definitions are kept only to avoid breaking old code.

No, functions do not always need a prototype. The only requirement is that a function be "declared" before you use it. There are two ways to declare a function: to write a prototype, or to write the function itself (called a "definition.") A definition is always a declaration, but not all declarations are definitions.