4.1.6 Internal Declarations - SICP Comparison Edition

Permalink copied!

In JavaScript, the scope of a declaration is the entire block that immediately surrounds the declaration, not just the portion of the block starting at the point where the declaration occurs. This section takes a closer look at this design choice.

Let us revisit the pair of mutually recursive functions is_even and is_odd from Section 3.2.4, declared locally in the body of a function f. function f(x) { function is_even(n) { return n === 0 ? true : is_odd(n - 1); } function is_odd(n) { return n === 0 ? false : is_even(n - 1); } return is_even(x); } Our intention here is that the name is_odd in the body of the function is_even should refer to the function is_odd that is declared after is_even. The scope of the name is_odd is the entire body block of f, not just the portion of the body of f starting at the point where the declaration of is_odd occurs. Indeed, when we consider that is_odd is itself defined in terms of is_even—so that is_even and is_odd are mutually recursive functions—we see that the only satisfactory interpretation of the two declarations is to regard them as if the names is_even and is_odd were being added to the environment simultaneously. More generally, in block structure, the scope of a local name is the entire block in which the declaration is evaluated.

The evaluation of blocks in the metacircular evaluator of section 4.1.1 achieves such a simultaneous scope for local names by scanning out the declarations in the block and extending the current environment with a frame containing bindings for all the declared names before evaluating the declarations. Thus the new environment in which the block body is evaluated already contains bindings for is_even and is_odd, and any occurrence of one of these names refers to the correct binding. Once their declarations are evaluated, these names are bound to their declared values, namely function objects that have the extended environment as their environment part. Thus, for example, by the time is_even gets applied in the body of f, its environment already contains the correct binding for the symbol is_odd, and the evaluation of the name is_odd in the body of is_even retrieves the correct value.

Exercise 4.16 Consider the function f_3 of section 1.3.2:

function f_3(x, y) {
    const a = 1 + x * y;
    const b = 1 - y;
    return x * square(a) + y * b + a * b;
}

Draw a diagram of the environment in effect during evaluation of the return expression of f_3.
When evaluating a function application, the evaluator creates two frames: one for the parameters and one for the names declared directly in the function's body block, as opposed to in an inner block. Since all these names have the same scope, an implementation could combine the two frames. Change the evaluator such that the evaluation of the body block does not create a new frame. You may assume that this will not result in duplicate names in the frame (exercise 4.5 justifies this).

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.17 Eva Lu Ator is writing programs in which function declarations and other statements are interleaved. She needs to make sure that the declarations are evaluated before the functions are applied. She complains: Why can't the evaluator take care of this chore, and hoist all function declarations to the beginning of the block in which they appear? Function declarations outside of blocks should be hoisted to the beginning of the program.

Modify the evaluator following Eva's suggestion.
The designers of JavaScript decided to follow Eva's approach. Discuss this decision.
In addition, the designers of JavaScript decided to allow the name declared by a function declaration to be reassigned using assignment. Modify your solution accordingly and discuss this decision.

Exercise 4.18 Recursive functions are obtained in a roundabout way in our interpreter: First declare the name that will refer to the recursive function and assign to it the special value "*unassigned*"; then define the recursive function in the scope of that name; and finally assign the defined function to the name. By the time the recursive function gets applied, any occurrences of the name in the body properly refer to the recursive function. Amazingly, it is possible to specify recursive functions without using declarations or assignment. The following program computes 10 factorial by applying a recursive factorial function:[1]

(n => (fact => fact(fact, n))
      ((ft, k) => k === 1
                  ? 1
                  : k * ft(ft, k - 1)))(10);

Check (by evaluating the expression) that this really does compute factorials. Devise an analogous expression for computing Fibonacci numbers.
Consider the function f given above: function f(x) { function is_even(n) { return n === 0 ? true : is_odd(n - 1); } function is_odd(n) { return n === 0 ? false : is_even(n - 1); } return is_even(x); } Fill in the missing expressions to complete an alternative declaration of f, which has no internal function declarations: function f(x) { return ((is_even, is_odd) => is_even(is_even, is_odd, x)) ((is_ev, is_od, n) => n === 0 ? true : is_od($\langle{}$??$\rangle$, $\langle{}$??$\rangle$, $\langle{}$??$\rangle$), (is_ev, is_od, n) => n === 0 ? false : is_ev($\langle{}$??$\rangle$, $\langle{}$??$\rangle$, $\langle{}$??$\rangle$)); }

Part (a)

// solution provided by GitHub user LucasGdosR

// The Fibonacci function receives n as an argument
// It applies the fib function recursively, passing n as an argument,
// as well as the initial arguments (k = 1, fib1 = 1, fib2 = 1)
(n => (fib => fib(fib, n, 2, 1, 1))
      // The fib function is then defined as ft,
      // with parameters n, k, fib1, and fib2
      // Establish the base cases: n === 1 or n === 2
      ((ft, n, k, fib1, fib2) => n === 1
                  ? 1
                  : n === 2
                  ? 1
                  :
                  // Iterate until k equals n. Notice k starts at 2, and gets incremented every iteration
                  k === n
                  // When k reaches n, return the accumulated fib2
                  ? fib2
                  // Otherwise, accumulate the sum as the new fib2
                  : ft(ft, n, k + 1, fib2, fib1 + fib2)));

Part (b)

// solution provided by GitHub user LucasGdosR

function f(x) {
    return ((is_even, is_odd) => is_even(is_even, is_odd, x))
           ((is_ev, is_od, n) => n === 0 ? true : is_od(is_ev, is_od, n - 1),
           (is_ev, is_od, n) => n === 0 ? false : is_ev(is_ev, is_od, n - 1));
}

Sequential Declaration Processing

The design of our evaluator of section 4.1.1 imposes a runtime burden on the evaluation of blocks: It needs to scan the body of the block for locally declared names, extend the current environment with a new frame that binds those names, and evaluate the block body in this extended environment. Alternatively, the evaluation of a block could extend the current environment with an empty frame. The evaluation of each declaration in the block body would then add a new binding to that frame. To implement this design, we first simplify eval_block:

function eval_block(component, env) {
    const body = block_body(component);
    return evaluate(body, extend_environment(null, null, env);
}

The function eval_declaration can no longer assume that the environment already has a binding for the name. Instead of using assign_symbol_value to change an existing binding, it calls a new function, add_binding_to_frame, to add to the first frame of the environment a binding of the name to the value of the value expression.

function eval_declaration(component, env) {
    add_binding_to_frame(
        declaration_symbol(component),
        evaluate(declaration_value_expression(component), env),
        first_frame(env));
    return undefined;
}
function add_binding_to_frame(symbol, value, frame) {
    set_head(frame, pair(symbol, head(frame)));
    set_tail(frame, pair(value, tail(frame)));
}

With sequential declaration processing, the scope of a declaration is no longer the entire block that immediately surrounds the declaration, but rather just the portion of the block starting at the point where the declaration occurs. Although we no longer have simultaneous scope, sequential declaration processing will evaluate calls to the function f at the beginning of this section correctly, but for an accidental reason: Since the declarations of the internal functions come first, no calls to these functions will be evaluated until all of them have been declared. Hence, is_odd will have been declared by the time is_even is executed. In fact, sequential declaration processing will give the same result as our scanning-out-names evaluator in section 4.1.1 for any function in which the internal declarations come first in a body and evaluation of the value expressions for the declared names doesn't actually use any of the declared names. Exercise 4.19 shows an example of a function that doesn't obey these restrictions, so that the alternative evaluator isn't equivalent to our scanning-out-names evaluator.

Sequential declaration processing is more efficient and easier to implement than scanning out names. However, with sequential processing, the declaration to which a name refers may depend on the order in which the statements in a block are evaluated. In exercise 4.19, we see that views may differ as to whether that is desirable.

Exercise 4.19 Ben Bitdiddle, Alyssa P. Hacker, and Eva Lu Ator are arguing about the desired result of evaluating the program

const a = 1;
function f(x) {      
    const b = a + x;
    const a = 5;
    return a + b;
}
f(10);

Ben asserts that the result should be obtained using the sequential processing of declarations: b is declared to be 11, then a is declared to be 5, so the result is 16. Alyssa objects that mutual recursion requires the simultaneous scope rule for internal function declarations, and that it is unreasonable to treat function names differently from other names. Thus, she argues for the mechanism implemented in section 4.1.1. This would lead to a being unassigned at the time that the value for b is to be computed. Hence, in Alyssa's view the function should produce an error. Eva has a third opinion. She says that if the declarations of a and b are truly meant to be simultaneous, then the value 5 for a should be used in evaluating b. Hence, in Eva's view a should be 5, b should be 15, and the result should be 20. Which (if any) of these viewpoints do you support? Can you devise a way to implement internal declarations so that they behave as Eva prefers?[2]

[1] This example illustrates a programming trick for formulating recursive functions without using assignment. The most general trick of this sort is the $Y$ operator, which can be used to give a pure $\lambda$-calculus implementation of recursion. (See Stoy 1977 for details on the lambda calculus, and Gabriel 1988 for an exposition of the $Y$ operator in the language Scheme.)

[2] The designers of JavaScript support Alyssa on the following grounds: Eva is in principle correct—the declarations should be regarded as simultaneous. But it seems difficult to implement a general, efficient mechanism that does what Eva requires. In the absence of such a mechanism, it is better to generate an error in the difficult cases of simultaneous declarations (Alyssa's notion) than to produce an incorrect answer (as Ben would have it).

< Previous

Next >

4.1.6 Internal Declarations