1

My understanding is that for compiled languages such as C++, the compiler substitutes the line where the functions are called for the statements in the function body.

Why then, is there a difference between functions and procedures ? Since, a procedure is changing state in-line and so are functions, once compiled ?

pseudocode:

main()
{
let a = 1;
a = add_one(a);
}

fn add_one(n) {
  n + 1
}

at compile time, something like... (apologies, attempting to write pseudocode from my memory of that assembly class ~10 years ago is hard)

ASSIGN 1 to A
ASSIGN A FN ADDONE A
FN ADDONE A // Essentially, the function is converted into a procedure
A + 1 // That is evaluated and substituted in-line
EXIT
hotenthusiasm
  • 31
  • 3
  • 5
    You seem to be confusing multiple concepts. Firstly the difference between functional and procedural *languages* has nothing to do with any difference between *functions* and *procedures*. Secondly any notion of what an language construct means (it's meaning in the language) has little to do with how that construct is implemented (it's expression by the compiler). – john Aug 30 '22 at 13:09
  • 2
    *compiled languages such as C++, the compiler substitutes the line where the functions are called for the statements in the function body.* No. Most of the time it generates a call to the function. Inlining only happens for very small functions. – vandench Aug 30 '22 at 13:09
  • Refer to a [good c++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) – Jason Aug 30 '22 at 13:11
  • 1
    When I think of a "functional programming language", I think of language features like: monads, all code are expressions (no statements), immutability, pure functions, referential transparency, higher-kinded types, lambdas & closures, lazy evaluation, recursion (no loops), pattern matching, code-as-data, and separation of behavior and data. – Eljay Aug 30 '22 at 13:13
  • @john so, if I understand you correctly, even if the compiler spits out procedures upon evaluating the human readable code.. we distinguish a function and procedure on the basis of the code written in the .cpp and not on the basis of how it is processed "under the hood". Correct ? – hotenthusiasm Aug 30 '22 at 13:21
  • 1
    @hotenthusiasm The specification of the C++ language doesn't use the word _procedure_. There are only functions. If someone talks about procedures in the context of C++ I would assume that they are just not aware of correct terminology and intent it to be synonymous with _function_. The meaning/definition of such words will depend on the context in which they are used. It may be different in other languages or when talking about academic study of programming languages as a whole. – user17732522 Aug 30 '22 at 13:30
  • 1
    @hotenthusiasm Yes, as long as the compiler is correct it makes no difference. All current machine languages are procedural (as far as I know) but functional languages are still implemented by translating to procedural machine code. – john Aug 30 '22 at 13:31
  • Thank you so much, this cleared it up for me. – hotenthusiasm Aug 30 '22 at 13:42

1 Answers1

1

the compiler substitutes the line where the functions are called for the statements in the function body

That is something a compiler can optionally perform, known as "procedural integration", or more commonly "inlining".

Inlining is not the normal way of implementing procedure calls. Firstly, inlining all calls would cause compiled programs to explode in size, and potentially to run slower. (Inlining can speed up programs, but only when judiciously applied: an example of where it may help is when a small function that is executed many times in a loop is hoisted into that loop.)

Secondly, calls can be recursive. Recursion cannot be implemented by inlining; it is logically impossible for a function to be inserted into itself: this leads to infinite regress.*

The bare essence of a procedure call is that the calling procedure is suspended, while the called procedure executes. When the called procedure finishes executing, the caller is resumed. This semantics is preserved under inlining; it still looks like the surrounding procedure is suspended while the inlined one executes.

A regular non-inlined procedure call compiles into some kind of control transfer, whereby the machine, instead of executing the next instruction, is told to "jump" to some other list of instructions, corresponding to the body of the procedure. The previous location is somehow remembered. When the called procedure finishes, it "jumps" back to the remembered location, so the calling procedure resumes from that point. When multiple places in the program call a non-inlined procedure, they all share the same image of that procedure: the same list of instructions.

Both procedures and pure functions are susceptible inlining optimizations; there is no difference in that regard. The semantics is preserved; the inlined call appears to be passing parameters and returning a value.

The terminology like procedure and function varies from programming language to programming language.

How the words are used in computer science is that a function corresponds to the mathematical concept of a pure mapping from one abstract space to another. A function returns a value that is calculated from some arguments, which is done without side effects.

A procedure is a name given to some steps which perform some effects, making changes to the state of the machine. Those steps are invoked by their name. Procedures may look like functions in that they have arguments, and return values.

Some languages, like C, call everything function: printf is called a "function", even though it has a side effect of performing output. exit and abort are "functions", though they destroy the process and do not return.

When procedures are called functions, you may hear the term "pure function" in reference to functions that don't have side effects and only calculate a value.

Common Lisp uses the function terminology similarly to C; both functions and procedures are defined using defun and are called functions. Scheme uses the term "procedure". So even related language dialects don't necessarily agree.

You have to keep the concepts clearly separated from the way your programming language documentation refers to them. Don't assume that because your language reference manual says "function", that it's talking about a pure mapping between sets.

(There are subtleties in the "function" concept because in computer science, which is after all a branch of mathematics, "function" can refer to a mathematical function, or to a computational function which calculates some mathematical function using concrete algorithmic steps. The two are not the same because not all mathematical functions are computable by a corresponding computational function. For instance the "halting function" exists in mathematics, but cannot be computed. The halting function H has two arguments: a program P and an input I. It maps these to a Boolean value: true if the program P halts when given input I, or false if it doesn't halt. The mathematical function is real because every P(I) pair either halts or doesn't halt. But we cannot implement such a function.)

* Of course, partial inlining of recursion is possible. For instance, in the simple case of a function calling itself, a compiler could decide to inline some of the self-calls to some specific depth. The inlining will "bottom out", so that some of the calls remain non-inlined.

Kaz
  • 55,781
  • 9
  • 100
  • 149
  • So, if I understand correctly, both functions or procedures may or may not be in-lined at compile time. What distinguishes them (in theoretical CS), is that functions typically accept an argument and return a value without changing the state of the calling code. A procedure may have *side effects* that change the state of the procedure (machine) they are called from. What then is the difference in practice when a function is used vs a procedure ? Is there one ? Since it seems that functions can be defined such that they embody the characteristics of a procedure (pass by ref) and vice versa. – hotenthusiasm Aug 31 '22 at 06:41