Lambda Calculus, Evaluation Order, Call by name and value

When you try to evaluate an application, you may have to use many reductions and usually, there is more than one strategy to use on how to choose the order of the reductions. For example, if you have more than one instance of application like λx.T1 T2  in an application (T1, T2, T3 are terms) like the following:

(λx.(λy.T1) T2) T3

Then you can have more than one way to reduce the application and find out the result. For a simple example assume:

T1  = λy.y  and  T2 = x 

So the application will be something like:

(λx.(λy.y) x) T3

Now you can either go from inner side to out:

(λx.(λy.y) x) T3  → (λx.x) T3  →  T3     (1)

Or you can reduce from outer to inner, like this:

(λx.(λy.y) x) T3  → (λy.y) T3   →  T3    (2)



Call by name
Call by name or lazy strategy doesn't evaluate a function unless it is necessary, in fact, it evaluates the application with given argument as late as possible. This is how we evaluated the application in (1) This method usually terminates to a stable point. (We will see that sometimes when you are trying to evaluate an application you stuck in an infinite evaluation loop) So for evaluating T1 T2, we first reduce T1 to T1' and the use beta reduction to reduce T1' T2.

Call by value
Call by value or strict strategy evaluates a function as soon as possible, in other words, it tries to apply the passed argument to the application first, like what we did in (2) Most languages like C, Pascal, Java and ... uses this method to evaluate the ordinary function calls. Note if the argument itself is an application, when calling by value you have to make sure you pass the argument as an abstraction so in this case the first thing to get evaluated will be the passed argument. So for evaluating T1 T2, first we reduce T2 to the state of an abstraction like T2' and the we use beta reductions to evaluate the application T1 T2'.

Other strategies ...
Just know that there are more strategies to choose the order of the evaluation, like call by need, application order or full beta reduction and ... these are (including the two call by name and value) typical strategies that any programming languages use to determine when it is the time to evaluate the arguments of a function and what to pass to it.