It seems like there are plenty of examples of clever things being done in a lazily-evaluated language that can't be done in an environment with strict evaluation. For example infinite lists in Haskell or replacing every element in a tree with the tree's minimum value in one pass.
Are there any examples of clever things being done in a strictly-evaluated language that can't easily be done in a lazily-evaluated language?
Well, no, more or less by definition. In a lazy-evaluation language, you should by definition get the same results you'd get with vigorous (are people really using "strict" now?) evaluation, except for the delay of evaluation until needed, storage implications and all that. So if you could get some different behavior except for that, it would be a bug.
In a strict evaluation language such as C# it is possible to achieve lazy evaluation by returning a thunk to a value (Func) instead of the value itself. As an example in the construction of the Y-Combinator in c# can be done in this way:
public Func<int, int> Y(Func<Func<int, int>, Func<int, int>> f)
{
return x => f(Y(f))(x);
}
This declaration would be more concise in a lazy environment:
Y f = f (Y f)
As Charlie Martin wrote, result of strict and lazy program should be equivalent. Difference lay in time and space constrains and/or language expressiveness. Beside performance effect of laziness for unneeded values there one can in lazy language easily introduce new language constructs without additional language concept (e.g. macro in LISP). Anyway, laziness can bit you
http://stackoverflow.com/questions/412919/how-haskell-tail-recursion-works and same think can be more complicated than in strict language. (Shouldn't haskell compiler recognize that compute +1 is less expensive than make thunk ( x + 1 )?)
I program in Erlang a bit, and find the lack of lazy evaluation that I learnt back at university quite frustrating.
I've been looking briefly at some of the project Euler problems, particularly those dealing with primes.
With lazy evaluation you can have a function that returns a list of all primes, but it only actually returns those that you actually want. Hence it's really easy to say "give me the first n primes".
Without lazy evaluation, you tend to end up with a more constraining "give me a list of all of the primes between 1 and n".
No; there are some things you can do* with lazy evaluation (AKA normal-order reduction, or left-outermost reduction) that you can't do with strict evaluation, but not the other way around.
The reason for this is that lazy evaluation is in some way the ‘most general’ way to evaluate, which is known as:
The Computational Adequacy Theorem: If some order of evaluation terminates and produces a particular result, then lazy evaluation will also terminate and produce the same result.
* (please note that we are not talking about Turing-equivalence here)
The main things you can do easily in an eager (strict) language and not in a lazy language:
Predict from the source code the time and space costs of your programs
Permit side effects, including constant-time update of mutable arrays, which makes it easier to implement some algorithms fast
In my opinion, the major benefit of an eager language is that it's much easier to get your code to perform the way you want, and there are very few performance traps in which a small change in the code leads to a huge change in performance.
Having said that, on the whole I prefer to write complicated things in Haskell.
The answer that was rated the best one suffers, unfortunately, from a logical error. From the theorem Porges cites does not follow that one can do more in a lazy language.
Proof to the contrary is that all programs in lazy languages are compiled to equivalents in strict languages (which are compiled further to assembler programs) or executed by an interpreter written in a strict language (and yes, the interpreter is an assembler program ultimatively).
The most obvious use of laziness in an everyday language is the "if" statement, where only one branch of the conditional is executed.
The opposite of a purely non-strict (lazy) language would be a purely strict language.
There is an least one case where 'purely strict' is beneficial, namely branch predication.
Rough paraphrase of the linked article:
Long ago in the world of CPUs, instructions to execute were loaded when the branch condition was tested. At some point, instruction pipelines were added to cut down on the load time. The downside was that a CPU would not know which branch it needed to load, so it would by default load one. If the branch went the other way, the pipeline would stall while the code for the other branch was loaded.
The solution is to load both branches, execute both branches, then the result of the conditional tells you which branch result to keep, and which to throw away. Then you don't get pipeline stalls.
This is my favorite (only?) example of the benefit of a purely strict language.
'Hello, World' programs come to mind, or all things related to side-effects basically.
In strict evaluation, evaluating an expression can easily have a side-effect as you have a clear overview on the order of evaluation, and thus the order of side-effects, usually important in side-effects. That's the basic advantage of strict evaluation, and also why most languages have it. And why even performance-oriented languages like C often use a pass-by-value model.
Both can do the same, just with different levels of human difficulty, you can perfectly well simulate infinite lists in a strict language, and you can simulate all effects of side-effects with non-strict languages.