Question

When we defined the evaluation model in section 1.1.3, we said that the first step in evaluating an expression is to evaluate its subexpressions. But we never specified the order in which the subexpressions should be evaluated (e.g., left to right or right to left). When we introduce assignment, the order in which the arguments to a procedure are evaluated can make a difference to the result. Define a simple procedure \(f\) such that evaluating (+ (f 0) ( \(f\) ) ) will return 0 if the arguments to \(+\) are evaluated from left to right but will return 1 if the arguments are evaluated from right to left.

Short answer

Define \(f\) with a side effect: set a global variable to 1 when no argument is provided. Evaluate \(+ (f 0) (f)\).

Step-by-step solution

Understanding the Problem

The problem states that we need to define a procedure \(f\) such that evaluating \(+ (f 0) (f)\) will yield different results depending on the order of evaluation of the arguments. Specifically, it should return 0 if evaluated left to right, and 1 if evaluated right to left.

Define the Function f

To cause a different result based on evaluation order, the function \(f\) must have side effects. We'll use a side effect by assigning a global variable. Define \(f\) as a procedure that changes this global variable's value and returns a specific result. Initially, let's assume \(f(n)\) returns \(n\) and modifies the side effect.

Set Up Global Variable

Define a global variable \(result\) initialized to 0. The procedure \(f\) should set \(result\) to a specific value each time it is called without any arguments.

Define Function Behavior

Modify \(f\) so that it checks if an argument is provided. If an argument is given, it does not modify the global variable. Without an argument, it sets \(result\) to 1 before returning 0.

Checking Evaluation Result

When the expression \(+ (f 0) (f)\) is evaluated left to right, \(f(0)\) returns 0 and does not change \(result\). Therefore, the final result is 0. When evaluated right to left, the first \(f()\) sets \(result\) to 1, influencing the sum to also be 1.

Key concepts

Side Effects

In programming, a side effect is any change of state or observable interaction with the outside world during the execution of a function or expression. Side effects can include modifying a global variable, altering a static local variable, or performing I/O operations like printing to the console or writing to a file.

Side effects are an important concept because they can influence the outcome of a program depending on how and when functions are called. For instance, if a function modifies a global variable, calling it even without using its return value can change the state of the program.

In this exercise, we're using side effects to alter global variables based on the order of expression evaluation. When the function is evaluated, it modifies a global variable, which in turn affects the final outcome of the computation.

Global Variables

Global variables are variables that are defined outside of any function and can be accessed and modified by any function in the program. They are quite versatile but need to be used cautiously since they can lead to unexpected behaviors and bugs if altered unknowingly by different parts of the program.

In the task described, global variables play a critical role. We set up a global variable to track the effect caused by the function’s execution. This global variable is updated based on whether the function was called with or without an argument, influencing the result when evaluating combined expressions.

One advantage of global variables is that they provide a convenient way to keep track of information shared across various functions without needing to pass extra parameters. However, excessive use of global variables can make debugging and maintaining the code more difficult, as any change in one part of the program can potentially affect another seemingly unrelated part.

Procedures in Programming

Procedures, often referred to as functions or subroutines, are a fundamental concept in programming. They allow for code reuse, modular programming, and abstraction. Procedures can take inputs, known as arguments, and can return outputs as a result of their execution.

The exercise showcases how the order of evaluation of procedures can impact the program's output. When defining a procedure, it’s essential to be aware of both its intended return value and any possible side effects that can arise. A function that only returns a value and doesn't cause side effects is considered a pure function, which tends to be easier to reason about.

In programming languages like Scheme or Lisp, evaluation order can significantly impact results, especially when dealing with complex expressions. Understanding and controlling the order in which procedures execute can help in crafting more predictable and reliable code.