Evaluation
From Telecomix Crypto Munitions Bureau
Evaluation, what is it?
[edit] Evaluation vs. computation
Evaluation can be thought of as "reducing an expression to its meaning" while computation can be thought of as "calculating numbers". This is how most functional programming literature describes it.
[edit] Strict evaluation
Strict evaluation means that the program will evaluate the expressions it is composed of at once. This is how most "normal" programming languages do it.
Example:
function A: B = 3 X = B + 4 return X
This function will always do the same thing. It will assign the value 3 to B and then add 4 to it and store the result in X, before returning X to the caller.
Unless the function is simplified by an effective compiler at compile time, the calculations will always be done, despite that they always add up to 7. An effective compiler would reduce all references of the function to the constant 7.
[edit] Lazy evaluation
If strict evaluation means that all and every expression is computed at once, lazy evaluation means that only those expressions that are actually needed are computed.
As a computer program is running, it is thought to be making computations. Not so with lazy evaluation. Instead, as the computer program runs, it stores the expressions that it is supposed to execute in a dataset. The set of computations described is not computed until they are needed, which might never happen. This is called lazy evaluation.
In haskell, functions only perform any work if "someone" demands to see the result. Writing a function call will by itself just add expressions to its dataset. "Someone" demanding to see the result usually means that a decision has to be made to choose a branch / course-of-action depending on the shape/value of the function result, and only then will the expression in the dataset actually be evaluated (by demanding it) (and then caching the result). The "someone" can be any (possibly) other function, which calls the first, and whose result is in turn demanded; the demanding could also happen because the program needs to decide what to communicate to the external world / Operating System. This communication with the OS is (always) done by using the I/O-monad (possibly hidden behind a higher abstraction layer, if you want).
An expression that has been evaluated does not have to be evaluated again: Purely functional programming languages that does not allow side-effects will never change their variables once they are set to a value. This means that the value of an expression, once it has its variables defined, never change. We can store the value of the evaluated expression in our dataset for future use. Instead of evaluating the expression one time too much, the value of the expression can just be fetched from the dataset. (The previous four sentences are important.)
Lazy evaluation makes it possible to create languages that can express more complex thoughts in less words. This is just a random statement that probably can not be proven to be true, but it often seems to be true.
Among the more exotic effects of lazy evaluation is the possibility of describing infinity. Lazy evaluation for example makes it possible to define lists of infinite length (such as "the list of all prime numbers"), and have functions operate on them. When the result is needed, only the entries in the infinite list that are needed are used.
Example:
function_A: B = 3 X = B + 4 return X
This function will not always do the same thing. The first time the function is evaluated, it will evaluate B to 3, evaluate X to 7 and finally evaluate function_A to 7. The second time there is a reference to function_A, the value is already known and stored in the dataset. The function becomes equal to the constant 7, and never again has to be evaluated.
The evaluation of function_A can happen at compile time, in which case the whole function is replaced with the constant 7 and never evaluates.
Example:
function_B(Y): B = 3 X = Y + B + 4 return X
This function evaluate to Y+7. After it has been evaluated, every time function_B is used, it will be replaced with the expression Y+7. The entire function can be reduced to this statement at compile time.
[edit] Criticism of lazy evaluation
Some random arguments...
[edit] Higher order functions
Higher order functions are functions that accept functions as parameters and functions that evaluates to functions. One can think of higher order functions as code that reads and writes code.
Higher order functions are not limited to languages with lazy evaluation. But with lazy evaluation, higher order functions can be reduced and simplified at run time so that they do not consume as much time to evaluate (this is not always true). This makes it possible to write somewhat efficient code that is very abstract. Way beyond what can be done with object orientation. This comes at the cost of making programs a bit more difficult to debug.
[edit] What about space and time-complexity?
One might think that this would greatly speed up evaluation, but it is not always the case. Storing the values of expressions in a dataset requires the program to make a lot of references to RAM. It also becomes a little bit more difficult to analyze how much resources a program will use because of this feature. A program that makes a lot of distinct and unique computations would use up a lot of RAM. Some (most?) programs however benefit from this, especially if they are redoing the same evaluations over and over again.
This means that space complexity becomes a "problem" for programs that traditionally would only require analysis of their time complexity.
[edit] Abstract thought vs. menial labor?
Heavily CPU-bound problems are not suited for lazily evaluated functional programming languages. While this might change with better compilers and/or interpreters, at the time of writing, these languages are better suited for abstract logic. These types of languages are used to simulate quantum computers, make automated theorem provers, AI research and programs that solve problems that would be difficult to describe in other programming languages.
[edit] Is your life worth something?
A benefit to lazily evaluated languages is that the programmers need to spend less time typing the software and more time thinking about software. Programs written in functional languages are often very short, and very high level. The lazy functionalist argument goes like this: "It is more fun to think about what to type, than to type what I has already thought." and if asked about the speed of the programs, they would reply "So what if my program takes twice the amount of time to finish, moores law says that in 1.5 years, the computer will be twice as fast. My time is more important than that of my computers time. Also consider that O(2) is a constant, which means that this is a compiler issue. Also, note that I usually do not detect the difference between 14 microseconds and 28 microseconds, so who cares if it takes twice the time."
[edit] ??
Lazily evaluated languages is either future-tech or some stupid academic nerd-rage going on, serving no purpose but to make our code even more bloated. Decide for yourself.
