45

In general, there are two types of syntax of defining functions - Something like C, C++, C#, or Java (int functionName(char arg)) vs the ML (and others) tradition of defining the return type after the function (and using something like a fun keyword to define a function - like fun functionName(char arg): int).

One of the advantages (for the parser, at least) for a fun keyword is that it lets the parser be context-free (it doesn't have to guess if int defines a variable or if it defines a function).

When C was invented, computers had very little memory and speed (so little, that the reason C requires one to define all the variables in the beginning of the function was because it had to be a one-pass parser). Why didn't they choose the simple way out and use function defining keyword?

  • 23
    Fun fact: That problem (of deciding if it's a variable or function) still causes issues today, in C++ (mostly). You'll find that std::vector<int> foo(); isn't a variable that's default-initialized, it's a function. In C, because you don't have constructors and all other function calls have an identifier before them, this isn't actually that big of an issue, though. – Nic Hartley Mar 12 '18 at 5:50
  • 2
    @nichartley and has been largely solved by {} – PlasmaHH Mar 12 '18 at 15:02
  • 1
    And with templates and ADL, C++ found it needed to add trailing return type so that the return type can reference other types in the signature. – Toby Speight Mar 12 '18 at 17:52
  • @PlasmaHH I thought that had a slightly different meaning than ()? Or is it exactly equivalent in that particular case (no contents)? – Nic Hartley Mar 12 '18 at 23:19
  • 3
    @PlasmaHH solved... and then broken again by std::initializer_list rules... – Ruslan Mar 14 '18 at 5:45
65

Dennis Ritchie’s paper on The Development of the C Language gives some idea of the reasoning behind this: namely, the fundamental rule in C that declaration syntax should match expression syntax.

For each object of such a composed type, there was already a way to mention the underlying object: index the array, call the function, use the indirection operator on the pointer. Analogical reasoning led to a declaration syntax for names mirroring that of the expression syntax in which the names typically appear. Thus,

int i, *pi, **ppi;

declare an integer, a pointer to an integer, a pointer to a pointer to an integer. The syntax of these declarations reflects the observation that i, *pi, and **ppi all yield an int type when used in an expression. Similarly,

int f(), *f(), (*f)();

declare a function returning an integer, a function returning a pointer to an integer, a pointer to a function returning an integer;

int *api[10], (*pai)[10];

declare an array of pointers to integers, and a pointer to an array of integers. In all these cases the declaration of a variable resembles its usage in an expression whose type is the one named at the head of the declaration.

It appears this rule trumped parser considerations. Its immediate consequence is that function declarations can’t use specific keywords, or impose a different ordering of declaration components.

It’s worth noting that parsing was somewhat different in early C, since function declarations didn’t specify their arguments, and function definitions separated the argument list from the argument declarations (which weren’t necessary for int arguments):

sum();

declares a sum function, which would then be defined as

sum(a, b) {
    return a + b;
}

(no types needed here, the default is int). So the parser didn’t deal with types inside argument lists...

  • 1
    In K&R C, there was no syntax for specifying the number of or types of arguments in function declarations i.e. the empty parentheses in your example were mandatory. In function definitions, you listed the names in the parentheses and then had a separate list before the function's opening brace that declared the types of the arguments. If an argument was missing from that list, it was assumed to be an int like the return type. – JeremyP Mar 12 '18 at 14:29
  • It should be noted that the k&r syntax for function parameters actually converts between and from long for the parameters, while the iso style doesnt – PlasmaHH Mar 12 '18 at 15:04
  • Thanks @JeremyP, I’ve clarified that part; that does indeed simplify the parser. – Stephen Kitt Mar 12 '18 at 15:23
  • Implicit int and K&R C has been used extensively on PPCG. – Weijun Zhou Mar 13 '18 at 2:16
13

Typically with questions like this, it's very difficult to determine the exact reason why a past design decision was made. This decision would have been made very early on in the development of C, and little was recorded about the design process at that time.

So the best we might hope for at this time is guesses. I have a few:

  1. The design of C tried to minimise the number of reserved keywords in the language. Adding a keyword solely for defining a function would have required another reserved keyword.

  2. The designers prioritised consistency over ease of parsing. The consistency I'm referring to here is the placement of the type in declarations such as int x; and int f();.

  3. Declaring a function pointer variable with your suggested fun keyword within the framework of C's variable declarations might be problematic. Would it look like this?

    fun(char arg): int *fp;
    

    Parsing that might become a worse problem than the one you're trying to solve.

Also, it's not clear to me whether the designers cared whether their language was context-free or not. The fact is that they did implement a compiler for the language that became C, and the fact that it worked was probably more important than adhering to particular rules of language grammar construction.

  • 3
    I suspect, as well, that "rules of language grammar construction" were pretty much non-existent, or at least poorly known, at the time. – Jack Aidley Mar 12 '18 at 16:58
  • 9
    The rules of regular grammars for programming language parsing were well known when Algol 68 was published... years before the C language was developed. The 1960s was not the stone age, that was a couple of decades earlier. – Stephen M. Webb Mar 12 '18 at 19:38
  • 7
    @JackAidley - Not only were said rules well known during the time period C was being designed, one of Dennis Ritchie's colleagues had recently published his PhD thesis on the topic and would quite literally go on to write the book on the subject, so I don't imagine he was unaware of these details, or short of help from colleagues who could assist in any areas he didn't understand in depth. – Jules Mar 13 '18 at 17:36
  • @Jules: Okay, great to know :) – Jack Aidley Mar 13 '18 at 18:17
6

Type name before function name (and type name before variable name) was common at the time C was designed, for instance I believe Algol 60 and FORTRAN both declared functions that way. "Because that's the way other people already do it" is a strong argument when designing the "user interface" of a programming language.

I doubt that parser performance had anything to do with it. (And yes I've written a compiler for a small computer system.) Parsing gets a lot of attention in textbooks and classes, but it's not that complicated or memory intensive. (At least, until you get to C++ template levels of absurdity.)

  • 3
    Both Algol and FORTRAN have keywords introducing procedures and/or functions, don’t they? And I get the impression Algol places the return type after the function name, and FORTRAN functions define their return type by the returning assignment, not in the declaration... – Stephen Kitt Mar 11 '18 at 23:10
  • In FORTRAN defining a function uses the keyword FUNCTION, but just declaring a function just say REAL SQRT, which looks like a variable declaration. The compiler does not know which is which until it is actually used. (I don't know Algol) – Stig Hemmer Mar 12 '18 at 8:59
  • Long time since I wrote ALGOL or FORTRAN. I remember declarations did have type first. Vars also had type first, and we did complain that functions definitions were inconsistent - something C got right – Hugh Fisher Mar 12 '18 at 10:08
  • C was based on CPL which was based on Algol so it followed the Algol syntax – cup Mar 12 '18 at 12:35
  • 1
    C was based on B, which was based on BCPL, which was based on CPL, which was based on Algol. In Algol, the type did indeed come first. real procedure foo(.... In CPL the type was implicit, I think: function foo[x] = x+1. In BCPL and B, types were not needed, since the languages did not feature type checking. – Theodore Norvell Mar 13 '18 at 17:53
6

Note C has much fewer places where a function definition can appear than languages like Pascal. Pascal supports nested functions, so a function definition can appear within any function, so basically anywhere. Marking a function definition with a keyword like FUNCTION, can thus help a lot.

For C, the parsing of a function is rather more easy: If anything on top level has a pair of parentheses, it must be a function. If it doesn't have a semicolon after the parentheses, it's a function definition. If it does, it must be a declaration.

Apart from that, when parsing a line, the order of things to expect for proper syntax doesn't really matter much in terms of effort. I don't think any of the more modern programming languages can be fully parsed with a pure LL(0) parser anyways.

  • many C compilers also support nested function as an extenstion – phuclv Mar 14 '18 at 2:39
  • @LưuVĩnhPhúc The only one I know is gcc. And that was not around in retro times. – tofro Mar 14 '18 at 6:36
4

The design of the C language began, to my understanding, in 1969 at Bell Labs, where Dennis Ritchie was working at the time. The language was based on B, a language which used a single data type that could be interpreted differently in different contexts (somewhat like assembly language). Keeping as close as possible to the structure of B was one of the aims of the language. B looked like this (quoting from wikipedia, which cites the example as being from the User's Reference to B):

/* The following function will print a non-negative number, n, to
   the base b, where 2<=b<=10.  This routine uses the fact that
   in the ASCII character set, the digits 0 to 9 have sequential
   code values.  */
printn(n, b) {
        extrn putchar;
        auto a;

        if (a = n / b)        /* assignment, not test for equality */
                printn(a, b); /* recursive */
        putchar(n % b + '0');
}

Note that the declarations of a local variable (auto a) and import of a global symbol (extrn putchar) both follow the same "kind-of-thing name-of-the-thing" layout that C uses. But in B, the "kind-of-thing" was just a simple choice from a predefined set of keywords, so caused no parsing problems. Extending that to the complex syntax of data types is where the problem came in.

Now, one can imagine that while designing C Ritchie would have noticed that the parsing for types in declarations was becoming more complex than a context-free grammar can handle. Some developers may have been deterred by this fact, and would have accepted the loss of this aspect of similarity to B in favour of a simpler parser design.

It's hard to say exactly why this didn't happen, but it may be because of the culture of Bell Labs, where a large number of extremely talented programmers and computer scientists were congregating at the time. Among them was Alfred Aho, who had recently published his PhD thesis on the subject of Indexed Grammars, and would therefore have been quite familiar with the consequences of leaving the safety of Context-free Grammars and the kinds of techniques that could be used to efficiently parse such languages. (Along with another Bell Labs researcher, Jeffrey Ullman, he would go on to write the best-known book on the subject of compiler design). It's just a hypothesis, as I have no evidence that they ever talked about the subject, but discussing any such troubles with Aho may have given Ritchie the confidence to continue with his design rather than rewriting to a more conservative type of grammar.

  • Do you have any idea whether the earliest C compilers would have processed int foo(x,y) int y,x; { ... } such that x would be the first argument and y the second? If early compilers had required that parameters objects be declared in the same order as parameters, and only be of valid parameter types, then a compiler's parameter-handling logic could be limited to simply saying having the "allocate space for object of size N" function yield current_offset > 0 ? (current_offset+=N)-N : current_offset-=N. If current_offset is set to 4 at the start of the function definition,... – supercat Dec 19 '18 at 18:05
  • ...and to zero when the compiler encounters the first opening brace, the compiler wouldn't have had to include any other logic related to parameter handling. – supercat Dec 19 '18 at 18:07

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.