applicative-order/call-by-value and normal-order/c

Question

Background

I am learning the sicp according to an online course and got confused by its lecture notes. In the lecture notes, the applicative order seems to equal cbv and normal order to cbn.

Confusion

But the wiki points out that, beside evaluation orders(left to right, right to left, or simultaneous), there is a difference between the applicative order and cbv:

Unlike call-by-value, applicative order evaluation reduces terms within a function body as much as possible before the function is applied.

I don't understand what does it mean by reduced. Aren't applicative order and cbv both going to get the exact value of a variable before going into the function evaluation.

And for the normal order and cbv, I am even more confused according to wiki.

In contrast, a call-by-name strategy does not evaluate inside the body of an unapplied function.

I guess does it mean that normal order would evaluate inside the body of an unapplied function. How could it be?

Question

1. Could someone give me some more concrete definitions of the four strategies.
2. Could someone show an example for each strategy, using whatever programming language.

Thanks a lot?

Answer 1

Applicative order (without taking into account the order of evaluation ,which in scheme is undefined) would be equivalent to cbv. All arguments of a function call are fully evaluated before entering the functions body. This is the example given in SICP

(define (try a b)
  (if (= a 0) 1 b))

If you define the function, and call it with these arguments:

(try 0 (/ 1 0))

When using applicative order evaluation (default in scheme) this will produce and error. It will evaluate (/ 1 0) before entering the body. While with normal order evaluation, this would return 1. The arguments will be passed without evaluation to the functions body and (/ 1 0) will never be evaluated because (= a 1) is true, avoiding the error.

In the article you link to, they are talking about Lambda Calculus when they mention Applicative and Normal order evaluation. In this article wiki It is explained more clearly I think. Reduced means applying reduction rules to the expression. (also in the link).

α-conversion: changing bound variables (alpha);

β-reduction: applying functions to their arguments (beta);

Normal order:

The leftmost, outermost redex is always reduced first. That is, whenever possible the arguments are substituted into the body of an abstraction before the arguments are reduced.

Call-by-name

As normal order, but no reductions are performed inside abstractions. For example λx.(λx.x)x is in normal form according to this strategy, although it contains the redex (λx.x)x.

A normal form is an equivalent expression that cannot be reduced any further under the rules imposed by the form

In the same article, they say about call-by-value

Only the outermost redexes are reduced: a redex is reduced only when its right hand side has reduced to a value (variable or lambda abstraction).

And Applicative order:

The leftmost, innermost redex is always reduced first. Intuitively this means a function's arguments are always reduced before the function itself.

You can read the article I linked for more information about lambda-calculus. Also Programming Language Foundations