Question

Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order evaluation or normal-order evaluation. He defines the following two procedures: (define \((\mathrm{p})(\mathrm{p}))\) (define (test \(\mathrm{x} \mathrm{y}\) ) (if \((=\mathrm{x} 0)\) 0 \(\mathrm{y})\) ) Then he evaluates the expression (test \(0(\mathrm{p}))\) What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What behavior will he observe with an interpreter that uses normalorder evaluation? Explain your answer. (Assume that the evaluation rule for the special form if is the same whether the interpreter is using normal or applicative order: The predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression.)

Short answer

Applicative-order causes infinite loop; normal-order returns 0.

Step-by-step solution

Understanding Applicative-Order Evaluation

In applicative-order evaluation, an interpreter evaluates the arguments of a function before applying the function itself. This means that in the expression \(\text{(test 0 (p))}\), it will first try to evaluate \(\text{(p)}\) before applying it to the \(\text{test}\) function. Since \(\text{p}\) is defined as \(\text{((\text{p})(\text{p}))}\), this leads to an infinite loop or non-terminating computation as \(\text{p}\) calls itself indefinitely.

Understanding Normal-Order Evaluation

In normal-order evaluation, the interpreter delays the evaluation of arguments until their values are actually needed. In the expression \(\text{(test 0 (p))}\), the interpreter will first evaluate the predicate \(\text{(= x 0)}\), which is true since \(x\) is 0. Because the if statement evaluates the consequent without needing the value of \((\text{p})\), the expression correctly returns \(0\) without evaluating \(\text{(p)}\). Thus, no error or infinite loop occurs.

Key concepts

Applicative-Order Evaluation

In applicative-order evaluation, the order of operations is important.
This type of evaluation means that an interpreter evaluates all function arguments before it actually applies the function itself.
Consider the analogy of cooking: it's like gathering all your ingredients before you start cooking.Let's look at the expression \[\text{(test 0 (p))}\] given in the original exercise: - Here, the interpreter would try to evaluate both arguments of `(test)`.
It looks at `0` and tries to evaluate `(p)`.- But, `(p)` is a recursive procedure: it calls itself without an end, forming the expression \[\text{((p)(p))}\]- This results in an infinite loop because it continues to call `(p)` forever, without reaching a termination point. Thus, in applicative-order evaluation, the function fails to complete successfully, leading to a non-terminating computation or error.

Normal-Order Evaluation

Normal-order evaluation takes a lazy approach.
It delays the computation of the function's arguments until their values are necessary.
This can be seen as only gathering ingredients for cooking when you are at the step where they are needed.In the expression \[\text{(test 0 (p))}\] the interpreter behaves differently under normal-order evaluation:- Initially, it evaluates only the predicate of the `if` form: `(= x 0)`.
Since `x` is `0`, this evaluates to `true`.- Unlike applicative-order, it does not evaluate `(p)` upfront.
Instead, it moves to the `consequent` branch since the condition is true.
It immediately returns `0` from `test`.- The argument `(p)` remains unevaluated, and thus avoids the infinite recursion problem entirely.This behavior allows completion without errors or infinite loops, showcasing how normal-order evaluation can bypass unnecessary computations.

Interpreter Behavior

The behavior of an interpreter in implementing these evaluation orders can greatly impact program execution.
Understanding how an interpreter evaluates a code is crucial for debugging and optimizing code execution. ### Key Behaviors of Each Evaluation - **Applicative-Order Behavior:** * Focuses on evaluating arguments before executing functions. * Often used because predictable order despite risks of non-termination in recursive definitions. - **Normal-Order Behavior:** * Delays argument evaluation until absolutely necessary. * Avoids non-termination that frustrates applicative-order but can be less efficient for large expressions. Each has strengths and weaknesses: - Applicative-order is typically faster since it evaluates arguments first.
However, it can be costly if not optimized due to unnecessary evaluations. - Normal-order can handle more general recursive procedures without needing explicit termination but may have higher runtime due to delayed evaluations. Ultimately, knowing the interpreter's evaluation order helps anticipate potential issues, improve efficiency, and write clearer, more effective code.