CODEWITHSUNDEEP
javascripthaskellfunctional-programminglazy-evaluation
user1028880
user1028880

Reputation:

Where exactly does the performance advantage of LazyEvaluation emerge from?

In the past few days, I have researched LazyEvaluation, in performance aspect mostly, wondering from where the performance advantage of LazyEvalutaion emerges.

It's been so unclear to me reading various articles but a very few including

What are the advantages of Lazy Evaluation?

This refers to the evaluation of a syntax tree. If you evaluate a syntax tree lazily (i.e. when the value it represents is needed), you must carry it through the preceeding steps of your computation in its entirety. This is the overhead of lazy evaluation. However, there are two advantages. 1) you will not evaulate the tree unnecessarily if the result is never used,

JavaScript, for instance, implemented if syntax.

if(true)
{
    //to evaluate
}
else
{
    //not to evaluate
}

In this ordinary scenario, we don't have any performance issue.

To be evaluated is done, not to be evaluated is ignored in the syntax tree.

However, in some recursive loop, for instance, Tak function AKA Tarai function

function tak(x,y,z){ return (x <= y) ? y : tak(tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y)); }

Since Eager Evaluation strategy of JS evaluates function(arguments) inevitability, the if - else - not to be evaluated control no longer works, and the number of evaluation step of tak function explodes.

Against to this disadvantage of Eager Evaluation(of JS or other languages), Haskell can evaluate the tak without problems as it is, and some JS library such as lazy.js outperforms in a specific area like functional programming where recursive list management required.

Aside from infinite list, I understand this is the exact reason for performance advantage of LazyEvaluation. Am I correct?

Upvotes: 4

Views: 443

Answers (1)

Jeff Foster
Jeff Foster

Reputation: 44696

I think you've got the right idea.

I don't think you need all the complexity though. Imagine that the JavaScript was

if (veryExpensiveFunction()) {
  doThis();
} else {
  doThat();
}

Now imagine that veryExpensiveFunction is implemented.

function veryExpensiveFunction() {
   return true || evenMoreExpensiveFunction();
}

If JavaScript because || is lazy (only evaluates the second argument if needed) this will return very quickly (because true is, well, true!). If it was implemented instead like

function veryExpensiveFunction() {
  var a = true;
  var b = evenMoreExpensiveFunction(); // forces the evaluation

  return a || b;
}

This would take ages to evaluate because you've unnecessarily evaluated the arguments. Now imagine that the magic applied to || was applied to every function (i.e. a lazy language) and you can probably imagine the sort of performance advantages that laziness might bring.

In your example

function tak(x,y,z){ return (x <= y) ? y : tak(tak(x-1, y, z), tak(y-1, z, x), tak(z-1, x, y)); }

Let's imagine that everything was lazy.

 var a = tak(1,2,3);

This doesn't do anything (nothing needs to be evaluated). a isn't used, so nothing is evaluated.

 var a = tak(1,2,3);
 console.log(a);

Now we're in a position to drive the evaluation of tak. Evaluating as we need to get the results, we first substitute the values in (replace variables with their arguments). We then evaluate the condition, and then only the side of the conditional that we need.

 console.log((1 <= 2) ? 2 : tak(tak(1-1, 2, 3), tak(2-1, 1, 3), tak(3-1, 1, 2));
 console.log(   true  ? 2 : tak(tak(1-1, 2, 3), tak(2-1, 1, 3), tak(3-1, 1, 2));
 console.log(2);

In this example (assuming I've not made any horrible typos), then we don't need to evaluate anything else other than the arguments and no recursive calls are made.

Upvotes: 4

Related Questions