There seem to be many opinions about what functional programs and what imperative programs are.
I think functional programs can most easily be described as "lazy evaluation" oriented. Instead of having a program counter iterate through instructions, the language by design takes a recursive approach.
In a functional language, the evaluation of a function would start at the return statement and backtrack, until it eventually reaches a value. This has far reaching consequences with regards to the language syntax.
Imperative: Shipping the computer around
Below, I've tried to illustrate it by using a post office analogy. The imperative language would be mailing the computer around to different algorithms, and then have the computer returned with a result.
Functional: Shipping recipes around
The functional language would be sending recipes around, and when you need a result - the computer would start processing the recipes.
This way, you ensure that you don't waste too many CPU cycles doing work that is never used to calculate the result.
When you call a function in a functional language, the return value is a recipe that is built up of recipes which in turn is built of recipes. These recipes are actually what's known as closures.
// helper function, to illustrate the point
function unwrap(val) {
while (typeof val === "function") val = val();
return val;
}
function inc(val) {
return function() { unwrap(val) + 1 };
}
function dec(val) {
return function() { unwrap(val) - 1 };
}
function add(val1, val2) {
return function() { unwrap(val1) + unwrap(val2) }
}
// lets "calculate" something
let thirteen = inc(inc(inc(10)))
let twentyFive = dec(add(thirteen, thirteen))
// MAGIC! The computer still has not calculated anything.
// 'thirteen' is simply a recipe that will provide us with the value 13
// lets compose a new function
let doubler = function(val) {
return add(val, val);
}
// more modern syntax, but it's the same:
let alternativeDoubler = (val) => add(val, val)
// another function
let doublerMinusOne = (val) => dec(add(val, val));
// Will this be calculating anything?
let twentyFive = doubler(thirteen)
// no, nothing has been calculated. If we need the value, we have to unwrap it:
console.log(unwrap(thirteen)); // 26
The unwrap function will evaluate all the functions to the point of having a scalar value.
Language Design Consequences
Some nice features in imperative languages, are impossible in functional languages. For example the value++
expression, which in functional languages would be difficult to evaluate. Functional languages make constraints on how the syntax must be, because of the way they are evaluated.
On the other hand, with imperative languages can borrow great ideas from functional languages and become hybrids.
Functional languages have great difficulty with unary operators like for example ++
to increment a value. The reason for this difficulty is not obvious, unless you understand that functional languages are evaluated "in reverse".
Implementing a unary operator would have to be implemented something like this:
let value = 10;
function increment_operator(value) {
return function() {
unwrap(value) + 1;
}
}
value++ // would "under the hood" become value = increment_operator(value)
Note that the unwrap
function I used above, is because javascript is not a functional language, so when needed we have to manually unwrap the value.
It is now apparent that applying increment a thousand times would cause us to wrap the value with 10000 closures, which is worthless.
The more obvious approach, is to actually directly change the value in place - but voila: you have introduced modifiable values a.k.a mutable values which makes the language imperative - or actually a hybrid.
Under the hood, it boils down to two different approaches to come up with an output when provided with an input.
Below, I'll try to make an illustration of a city with the following items:
- The Computer
- Your Home
- The Fibonaccis
Imperative Languages
Task: Calculate the 3rd fibonacci number.
Steps:
Put The Computer into a box and mark it with a sticky note:
Field |
Value |
Mail Address |
The Fibonaccis |
Return Address |
Your Home |
Parameters |
3 |
Return Value |
undefined |
and send off the computer.
The Fibonaccis will upon receiving the box do as they always do:
As you can imagine, quite a lot of work starts immediately after you send your computer off to the functions you call.
The entire programming logic is recursive, but in truth the algorithm happens sequentially as the computer moves from algorithm to algorithm with the help of a stack of sticky notes.
Functional Languages
Task: Calculate the 3rd fibonacci number. Steps:
Write the following down on a sticky note:
Field |
Value |
Instructions |
The Fibonaccis |
Parameters |
3 |
That's essentially it. That sticky note now represents the computation result of fib(3)
.
We have attached the parameter 3 to the recipe named The Fibonaccis
. The computer does not have to perform any calculations, unless somebody needs the scalar value.
Functional Javascript Example
I've been working on designing a programming language named Charm, and this is how fibonacci would look in that language.
fib: (n) => if (
n < 2 // test
n // when true
fib(n-1) + fib(n-2) // when false
)
print(fib(4));
This code can be compiled both into imperative and functional "bytecode".
The imperative javascript version would be:
let fib = (n) =>
n < 2 ?
n :
fib(n-1) + fib(n-2);
The HALF functional javascript version would be:
let fib = (n) => () =>
n < 2 ?
n :
fib(n-1) + fib(n-2);
The PURE functional javascript version would be much more involved, because javascript doesn't have functional equivalents.
let unwrap = ($) =>
typeof $ !== "function" ? $ : unwrap($());
let $if = ($test, $whenTrue, $whenFalse) => () =>
unwrap($test) ? $whenTrue : $whenFalse;
let $lessThen = (a, b) => () =>
unwrap(a) < unwrap(b);
let $add = ($value, $amount) => () =>
unwrap($value) + unwrap($amount);
let $sub = ($value, $amount) => () =>
unwrap($value) - unwrap($amount);
let $fib = ($n) => () =>
$if(
$lessThen($n, 2),
$n,
$add( $fib( $sub($n, 1) ), $fib( $sub($n, 2) ) )
);
I'll manually "compile" it into javascript code:
"use strict";
// Library of functions:
/**
* Function that resolves the output of a function.
*/
let $$ = (val) => {
while (typeof val === "function") {
val = val();
}
return val;
}
/**
* Functional if
*
* The $ suffix is a convention I use to show that it is "functional"
* style, and I need to use $$() to "unwrap" the value when I need it.
*/
let if$ = (test, whenTrue, otherwise) => () =>
$$(test) ? whenTrue : otherwise;
/**
* Functional lt (less then)
*/
let lt$ = (leftSide, rightSide) => () =>
$$(leftSide) < $$(rightSide)
/**
* Functional add (+)
*/
let add$ = (leftSide, rightSide) => () =>
$$(leftSide) + $$(rightSide)
// My hand compiled Charm script:
/**
* Functional fib compiled
*/
let fib$ = (n) => if$( // fib: (n) => if(
lt$(n, 2), // n < 2
() => n, // n
() => add$(fib$(n-2), fib$(n-1)) // fib(n-1) + fib(n-2)
) // )
// This takes a microsecond or so, because nothing is calculated
console.log(fib$(30));
// When you need the value, just unwrap it with $$( fib$(30) )
console.log( $$( fib$(5) ))
// The only problem that makes this not truly functional, is that
console.log(fib$(5) === fib$(5)) // is false, while it should be true
// but that should be solveable
https://jsfiddle.net/819Lgwtz/42/