There is so many terminology which means the same or almost the same. Let's figure out what is what.
What is common in function, lambda, procedure, routine (subroutine), program (subprogram), application (as a noun), algorithm, method, closure, operator (operation)? All of them are computations.
There are several ways to define computation. For now, I take the simplest: a computation is a sequence of steps, which I call a behavior. There are three common choices for what a step is, leading to three different kinds of behavior:
- Action Behavior...
- State Behavior...
- State-Action Behavior...
-- Computation and State Machines. Leslie Lamport, 19 April 2008
Function vs procedure
There is a mathematical definition of function (I wrote about it here):
- takes at least one input
- produces one output
- for the same input always produce the same output
- doesn't have any side effects - e.g. the only result of executing function is its output nothing else happening
From mathematical PoV, the function is the same as lambda (can be denoted as greek letter λ).
But not all programming language follow the strict definition (I guess for historical reasons). For example, JavaScript:
Same input but different result:
let counter = 0;
const increase = (x) => counter += x;
increase(1) !== increase(1)
Result of the function is not communicated with return value but rather with a side effect:
console.log('Hello, world!');
// Outputs Hello, World
// Returns undefined
No input value:
Date.now();
This is not a strict rule because we can think about it as:
Date.now(undefined);
Some programming languages try to distinguish functions and "none-functions". For example, Pascal:
A procedure is a routine that does not return a value.
A function is a routine that, in contrast to procedures, returns a value.
A routine is a re-usable piece of source code that performs some functionality.
The problem is that Pascal doesn't restrict usage of side-effects inside functions, so division is not precise.
Some programming languages don't have "none-functions" at all, for example, Haskell. How do they handle side effects then? They use monads to model IO (a subject for a different article).
Routine, program, application
Definition for routine from Pascal:
A routine is a re-usable piece of source code that performs some functionality.
From The C Programming Language:
In C, a function is equivalent to a subroutine or function in Fortran, or a
procedure or function in Pascal. A function provides a convenient way to encapsulate some computation, which can then be used without worrying about its implementation.
All of those are the same: routine (subroutine), program (subprogram), application (as a noun) - some re-usable computations.
For example, in Bash, you can treat separate programs (or applications, or binaries, or executables) as "functions" - e.g. take the output from one program and pass (pipe) it to another one.
cat /var/log/syslog | grep 'post'
cat - concatenate files and print on the standard output.
grep - print lines matching a pattern.
Algorithm
Algorithm - a step-by-step procedure for solving a problem or accomplishing some end
In a broad definition, Algorithm is equivalent to computation. Sometimes people refer algorithm as pre-made solutions (in the same vein as design patterns):
Algorithms — methods for solving problems that are suited for computer implementations. Algorithms go hand in hand with data structures — schemes for organizing data
-- Algorithms, 4th Edition, Robert Sedgewick and Kevin Wayne. A
Compare to:
A design pattern is a three-part rule, which expresses a relation between a certain context, a problem, and a solution. The pattern is, in short, at the same time a thing, ..., and the rule which tells us how to create that thing, and when we must create it.
-- A Pattern Language: Towns, Buildings, Construction, 1977
Closure and method
Closure is a computation (function) with environment attached to it. For example, in JavaScript:
const True = (x) => (y) => x;
const condition = True('then');
condition('else') === 'then';
condition is the function, with environment attached to it. Environment encolosing condition contains x so it works, but there is not x outside of this closure:
const NotTrue = (z) => (y) => x;
const condition = NotTrue('then');
condition('else'); // Uncaught ReferenceError: x is not defined
The method is a computation (function) with the object attached to it. Typically attached object is accessible through this or self keywords. For example, in JavaScript:
class DogClass {
constructor(name) {
this.name = name;
}
bark() {
return `${this.name} is a good dog!`;
}
}
const belka = new DogClass('Belka');
belka.bark();
bark is the method.
In some PL passing of object is explicit, for example, in Lua:
function Account.withdraw (self, v)
self.balance = self.balance - v
end
Operator
In math:
Operator is a symbol or function representing a mathematical operation.
-- WolframAlpha
In math operator can be treated as a special version of the function, typically operator takes two arguments and uses infix notation (e.g. it is placed between symbols). For example, infix notation:
1 + 1
Prefix notation:
f(a, b) = a + b
f(1, 1)
Nobody uses this notation but it would be the same: +(1, 1).
In PL operators can have a different treatment then functions. For example, in JavaScript, there is conditional operator.
age = 20
(age >= 18) ? console.log('adult') : console.log('minor');
// outputs adult
// returns undefined
If we would want to implement the same thing as a function:
const ternary = (condition, thenAction, elseAction) => {
if (condition) {
return thenAction;
} else {
return elseAction;
}
}
ternary(age >= 18, console.log('adult'), console.log('minor'));
// outputs adult
// outputs minor
// returns undefined
The problem here is that console.log('adult'), console.log('minor') are executed before passing to ternary function. We can fix it by wrapping actions into functions (() => ...):
const ternary = (condition, thenAction, elseAction) => {
if (condition) {
return thenAction();
} else {
return elseAction();
}
}
ternary(age >= 18, () => console.log('adult'), () => console.log('minor'));
But as you can see the operator is treated differently than function (in JS).
On the other hand, there are languages which don't have this problem, for example, in Haskell it would be possible to implement if as function, without need for wrapping in additional function. Because Haskell is doing lazy evaluation aka call-by-need.
In some languages methods and some operators can be the same, for example, in Ruby:
a + b
Is the same as:
a.+(b)
It is confusing terminology which varies from one PL to another.
Routine and closure
From compilation point of view sometimes people differentiate routines (think of C functions) and closures. Because routine can be implemented as a trivial pointer, but closure compilation would need more work.
Photo by Matt Artz on Unsplash
Top comments (0)