The spread of "Functional Programming"

[paulca]

By C binary format, I mean like Linux ELF et. al.  Although, that really only applies to "main()" and any registered interrupt handlers?

Anyway, your point on optimisation mutes that point.  While "textbook" C will perform a full push of arguments onto the stack + return address and then jump... a good compiler will optimise that out if it has the same effect without it.

In this case the language was Java.  Java's JIC (just in time compiler) should optimise things like this, such as collapsing long single path nested method calls, but I don't believe it can optimise to prevent a stack overflow in these cases.

[brucehoult]

While "textbook" C will perform a full push of arguments onto the stack + return address and then jump

On what?

Not on amd64 / x86_64. Only the return address is pushed, by the hardware of the JSR instruction (sadly), the caller pushes nothing.

Not on any flavour of Arm, ever. Function calls do not touch the stack at all.

Not on RISC-V or MIPS or PowerPC or Alpha ... function calls do not touch the stack at all.


On all of the above, argument to a called function go in registers. On everything except x86_64 the desired return address also goes in a register.

If the called function is a leaf function then that is the end of it.

If the called function is not a leaf function then at the start it saves its own return address and any callee-save registers it needs on the stack, and restores all those before returning. That happens only once, in prolog and epilog, no matter how many other functions it calls, or how many times it calls them.

That "full push of arguments onto the stack + return address" stuff is only on CPUs (and their ABI) designed in the 1970s or before, 45 years ago.

[SiliconWizard]

Wasn't it the Pascal convention for the caller to push arguments & return address on the stack rather than the callee?

[brucehoult]

Wasn't it the Pascal convention for the caller to push arguments & return address on the stack rather than the callee?

Languages don't have physical calling conventions, only compilers do (and OSes and standard libraries).

In Pascal both the caller and the callee know how many bytes of arguments there are, so you can do anything you want. In ANSI C with prototyped functions without `...` in the prototype you also have both caller and callee knowing how many bytes of arguments there are, so you can again do anything you want.

If a function is called from more than one place in the program then the code size is smaller if the function does the cleanup than if the caller does the cleanup. If a function is called from exactly one place then it doesn't matter who does the cleanup. If a function is never used then the program is smaller if the caller does the cleanup :p

In pre-ANSI C, or varargs functions, the callee doesn't know how many bytes of arguments there are, so 1) the initial arguments [1] must be in fixed registers or in a fixed place on the stack (relative to SP), and 2) the callee can't remove the arguments or save them somewhere else because it doesn't know how many there really are.

The above is all assuming arguments passed on the stack and allocated and cleaned up at every function call/return.

The modern practice is for the compiler to analyse all the calls a function makes and find the maximum number/size of arguments and at function entry allocate enough space for the maximum number of outgoing function arguments needed (plus saved registers, plus spilled local variables). Arguments to called functions are then not pushed on to the stack (SP never moves) but instead stored at SP+0, SP+4, SP+8 etc etc. Then no one cleans up arguments after a function call -- not the caller and not the callee. The entire stack frame is deallocated at once at function exit.


[1] for example the argument with the printf() format string, though varargs functions can be much more complex than that

[Marco]

The map reduce stuff at least is useful for parallel programming.

Parallel execution is worthless if bottlenecks are IO, state management through SQL database and stuff like that.

I was mostly thinking about massive SIMD such as GPUs, for general purpose GPU programming. It never really took off there either as an explicit language construct, though a frequent pattern, but that's more due happenstance than suitability IMO.

[paulca]

While "textbook" C will perform a full push of arguments onto the stack + return address and then jump

On what?

Not on amd64 / x86_64. Only the return address is pushed, by the hardware of the JSR instruction (sadly), the caller pushes nothing.

That "full push of arguments onto the stack + return address" stuff is only on CPUs (and their ABI) designed in the 1970s or before, 45 years ago.

Okay. I'm either very out of date (a lot more than expected) or I'm confusing myself with something else.

What about buffer overflow exploits?  Some of those overrun the buffer to overwrites the function return address and direct it to other injected code.  I thought that was only possible when you have a fixed sized array on the stack?  Or maybe I am confusing myself between "stack" and "where there modern compilers 'stages' things.

[coppice]

Wasn't it the Pascal convention for the caller to push arguments & return address on the stack rather than the callee?

Languages don't have physical calling conventions, only compilers do (and OSes and standard libraries).

Well, it isn't usually compilers these days. Its almost always some ABI spec that everyone follows for the particular hardware. However, there is a sense where languages do have a calling convention. C from day one allowed for variable numbers of arguments. That won't work with the way most Pascal compilers handle arguments, so the language does impose some things on the calling convention.

[paulca]

Wasn't it the Pascal convention for the caller to push arguments & return address on the stack rather than the callee?

Languages don't have physical calling conventions, only compilers do (and OSes and standard libraries).

Well, it isn't usually compilers these days. Its almost always some ABI spec that everyone follows for the particular hardware. However, there is a sense where languages do have a calling convention. C from day one allowed for variable numbers of arguments. That won't work with the way most Pascal compilers handle arguments, so the language does impose some things on the calling convention.

How does the ELF binary format get involved?  So C code is not created as a monolithic block.  Functions can be "First class" and exist in global scope in isolation.  A single function can be stored in a .o or a .a etc.

What I was thinking was this specification which defines function formal prototypes for linkage and ... well integration with the rest of the OS.  Obviously the main() method has to have a contract with the OS to get launched and it's process setup and called. 

I suppose I was under the impression that also governed the generic contract for all functions and declarations. 

If you want to take your random single function .a file and wrap it into a .so dynamic loaded library it's going to have to obey some form of standard.  Maybe that does not in anyway govern how arguments and return values are passed or copied.

That is another consideration.  If the argument is passed by value and is not a "register" sized element.  How and where is space allocated for these, if not on the stack?

[SiliconWizard]

Wasn't it the Pascal convention for the caller to push arguments & return address on the stack rather than the callee?

Languages don't have physical calling conventions, only compilers do (and OSes and standard libraries).

Well, it isn't usually compilers these days. Its almost always some ABI spec that everyone follows for the particular hardware. However, there is a sense where languages do have a calling convention. C from day one allowed for variable numbers of arguments. That won't work with the way most Pascal compilers handle arguments, so the language does impose some things on the calling convention.

Yep. Sure that was intially defined by compilers, but it more or less became a convention. You're right it tied to the ABI of a given target.

The Pascal calling convention is listed in the x86 calling conventions, for instance: https://en.wikipedia.org/wiki/X86_calling_conventions
they indeed say that it was based on the convention used by Turbo Pascal compilers. It was similar on CP/M (so the Z80/8080). And yes, it did prevent the implementation of variable arguments.