4 ms·

> The order of presentation of a program is dictated by the needs of a single-pass compiler That never really made sense to me. All those "if"s, and "while"s,

> The order of presentation of a program is dictated by the needs of a single-pass compiler That never really made sense to me. All those "if"s, and "while"s, and "break"s, and "return"s jump to the not-yet-generated places in code just fine; a similar technique could be used for delaying the resolution of function/procedure calls as well. Now, generating initialized data/rodata sections is something that single-pass compilers do struggle with (that's why Pascal didn't have array literals), and it's understandable: the Modula compiler, which got them (or was it Modula-2?), had to hold all of that initialized data section in memory and then dump it to the disk only after the code-generation (and patching the offsets) was done. But dealing with not-yet-defined code labels? That's something you have to do anyhow.

Someone 2y ago
> All those "if"s, and "while"s, and "break"s, and "return"s jump to the not-yet-generated places in code just fine; a similar technique could be used for delaying the resolution of function/procedure calls as well. Not quite. When compiling "if"s, and "while"s, and "break"s, a compiler will make use of the fact that code is structured. Because of that, a stack of addresses is sufficient to track (similar to how Forth uses the return stack to compile such constructs) For returns, the compiler doesn’t resolve the target address; that happens at runtime. For function calls, a compiler would need a map mapping function names to addresses. Also, generating good error messages is harder if you allow forward references. You cannot generate an error before seeing the definition, even if, say you encounter two calls to foo before seeing its definition.
- Joker_vD 2y ago
  Of course you can do all of this! After all, the sources of e.g. Wirth's Modula-2 single-pass compiler for the Macintosh (that generates native MC68000 code) have survived, and it doesn't use "stack of addresses": it uses "fixup()" calls when compiling conditions, loops, references to (imported) global variables etc. and, surely enough, calls to functions. It even has "CheckUDProc()" call at the end of the module-translation procedure to check whether there are any undefined procedures left in the symbol table. It would be entirely possible to treat calls to undefined functions as implicit forward declarations; he simply never chose to do so.
int_19h 2y ago
The problem with functions is that when you see something like this: F(X); there may be implicit conversions happening to X here depending on its type, and, crucially, the declared type of the argument - e.g. Integer to Real. This would be a separate function call in many cases, so it's not just a single address to patch - indeed, you don't even know the size of the code that will need to be inserted in advance.
- Joker_vD 2y ago
  Yes, and the way that e.g. C famously handles it is that it treats it as X being implicitly int, if it's an integral expression that produces something shorter than long, and a double, if X is a floating-point-valued expression, and whatever happens to structs when invoking implicitly-declared functions. This, again, can be checked for the correctness at the end of the translation of a particular compilation unit, C just decided to not bother with this at all and leave it to the linker to figure out (even though it started its life as a language with 2-and-a-half passes compiler), and Pascal and its descendants decided to require either forward declarations, or using function pointers. I personally think that e.g. var F: proc(whatever): whatever; proc G() begin ... F(whatever); ... end G; proc F0(whatever): whatever begin ... G(); ... end F0; begin F := F0; end module. is a needless pessimization but e.g. Oberon does it this way.

Someone 2y ago

> All those "if"s, and "while"s, and "break"s, and "return"s jump to the not-yet-generated places in code just fine; a similar technique could be used for delaying the resolution of function/procedure calls as well. Not quite. When compiling "if"s, and "while"s, and "break"s, a compiler will make use of the fact that code is structured. Because of that, a stack of addresses is sufficient to track (similar to how Forth uses the return stack to compile such constructs) For returns, the compiler doesn’t resolve the target address; that happens at runtime. For function calls, a compiler would need a map mapping function names to addresses. Also, generating good error messages is harder if you allow forward references. You cannot generate an error before seeing the definition, even if, say you encounter two calls to foo before seeing its definition.

Joker_vD 2y ago
Of course you can do all of this! After all, the sources of e.g. Wirth's Modula-2 single-pass compiler for the Macintosh (that generates native MC68000 code) have survived, and it doesn't use "stack of addresses": it uses "fixup()" calls when compiling conditions, loops, references to (imported) global variables etc. and, surely enough, calls to functions. It even has "CheckUDProc()" call at the end of the module-translation procedure to check whether there are any undefined procedures left in the symbol table. It would be entirely possible to treat calls to undefined functions as implicit forward declarations; he simply never chose to do so.

int_19h 2y ago

The problem with functions is that when you see something like this: F(X); there may be implicit conversions happening to X here depending on its type, and, crucially, the declared type of the argument - e.g. Integer to Real. This would be a separate function call in many cases, so it's not just a single address to patch - indeed, you don't even know the size of the code that will need to be inserted in advance.

Joker_vD 2y ago
Yes, and the way that e.g. C famously handles it is that it treats it as X being implicitly int, if it's an integral expression that produces something shorter than long, and a double, if X is a floating-point-valued expression, and whatever happens to structs when invoking implicitly-declared functions. This, again, can be checked for the correctness at the end of the translation of a particular compilation unit, C just decided to not bother with this at all and leave it to the linker to figure out (even though it started its life as a language with 2-and-a-half passes compiler), and Pascal and its descendants decided to require either forward declarations, or using function pointers. I personally think that e.g. var F: proc(whatever): whatever; proc G() begin ... F(whatever); ... end G; proc F0(whatever): whatever begin ... G(); ... end F0; begin F := F0; end module. is a needless pessimization but e.g. Oberon does it this way.