Definitions Declarations - SICP Comparison Edition" /> 4.1.6   Internal <span style="color:green">Definitions</span> <span style="color:blue">Declarations</span> - SICP Comparison Edition
 Original JavaScript Our environment model of evaluation and our metacircular evaluator execute definitions in sequence, extending the environment frame one definition at a time. This is particularly convenient for interactive program development, in which the programmer needs to freely mix the application of procedures definition procedures. However, if we think carefully about the internal definitions used to implement block structure (introduced in section 1.1.8), we will find that name-by-name extension of the environment may not be the best way to define local variables. Consider a procedure with internal definitions, such as (define (f x) (define (even? n) (if (= n 0) true (odd? (- n 1)))) (define (odd? n) (if (= n 0) false (even? (- n 1)))) $\langle$ rest of body of$\rangle$ f) Our intention here is that the name odd? in the body of the procedure even? should refer to the procedure odd? that is defined after even?. The scope of the name odd? is the entire body of f, not just the portion of the body of f starting at the point where the define for odd? occurs. Indeed, when we consider that odd? is itself defined in terms of even?—so that even? and odd? are mutually recursive procedures—we see that the only satisfactory interpretation of the two defines is to regard them as if the names even? and odd? were being added to the environment simultaneously. More generally, in block structure, the scope of a local name is the entire procedure body in which the define is evaluated. As it happens, our interpreter will evaluate calls to f correctly, but for an accidental reason: Since the definitions of the internal procedures come first, no calls to these procedures will be evaluated until all of them have been defined. Hence, odd? will have been defined by the time even? is executed. In fact, our sequential evaluation mechanism will give the same result as a mechanism that directly implements simultaneous definition for any procedure in which the internal definitions come first in a body and evaluation of the value expressions for the defined variables doesn't actually use any of the defined variables. (For an example of a procedure that doesn't obey these restrictions, so that sequential definition isn't equivalent to simultaneous definition, see exercise 4.27.)[1] There is, however, a simple way to treat definitions so that internally defined names have truly simultaneous scope—just create all local variables that will be in the current environment before evaluating any of the value expressions. One way to do this is by a syntax transformation on lambda expressions. Before evaluating the body of a lambda expression, we scan out and eliminate all the internal definitions in the body. The internally defined variables will be created with a let and then set to their values by assignment. For example, the procedure (lambda vars (define u e1) (define v e2) e3) would be transformed into (lambda vars (let ((u '*unassigned*) (v '*unassigned*)) (set! u e1) (set! v e2) e3)) where *unassigned* is a special symbol that causes looking up a variable to signal an error if an attempt is made to use the value of the not-yet-assigned variable. An alternative strategy for scanning out internal definitions is shown in exercise 4.26. Unlike the transformation shown above, this enforces the restriction that the defined variables' values can be evaluated without using any of the variables' values.[2] 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.21 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.8 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.22 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. 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.23 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:[3] (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$)); } 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.
 Original JavaScript Exercise 4.24 In this exercise we implement the method just described for interpreting internal definitions. We assume that the evaluator supports let (see exercise 4.9). Change lookup-variable-value (section 4.1.3) to signal an error if the value it finds is the symbol *unassigned*. Write a procedure scan-out-defines that takes a procedure body and returns an equivalent one that has no internal definitions, by making the transformation described above. Install scan-out-defines in the interpreter, either in make-procedure or in procedure-body (see section 4.1.3). Which place is better? Why? 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.25 Draw diagrams of the environment in effect when evaluating the expression e3 in the procedure in the text, comparing how this will be structured when definitions are interpreted sequentially with how it will be structured if definitions are scanned out as described. Why is there an extra frame in the transformed program? Explain why this difference in environment structure can never make a difference in the behavior of a correct program. Design a way to make the interpreter implement the simultaneous scope rule for internal definitions without constructing the extra frame. 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.
Original JavaScript
 Original JavaScript Exercise 4.27 Ben Bitdiddle, Alyssa P. Hacker, and Eva Lu Ator are arguing about the desired result of evaluating the expression (let ((a 1)) (define (f x) (define b (+ a x)) (define a 5) (+ a b)) (f 10)) Ben asserts that the result should be obtained using the sequential rule for define: b is defined to be 11, then a is defined to be 5, so the result is 16. Alyssa objects that mutual recursion requires the simultaneous scope rule for internal procedure definitions, and that it is unreasonable to treat procedure names differently from other names. Thus, she argues for the mechanism implemented in exercise 4.24. 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 procedure should produce an error. Eva has a third opinion. She says that if the definitions 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 definitions so that they behave as Eva prefers?[4] 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.
 Original JavaScript Exercise 4.28 Because internal definitions look sequential but are actually simultaneous, some people prefer to avoid them entirely, and use the special form letrec instead. Letrec looks like let, so it is not surprising that the variables it binds are bound simultaneously and have the same scope as each other. The sample procedure f above can be written without internal definitions, but with exactly the same meaning, as (define (f x) (letrec ((even? (lambda (n) (if (= n 0) true (odd? (- n 1))))) (odd? (lambda (n) (if (= n 0) false (even? (- n 1)))))) $\langle$rest of body of$\rangle$ f)) Letrec expressions, which have the form (letrec ((var$_{1}$ exp$_{1}$) $\ldots$ (var$_{n}$ exp$_{n}$)) body) are a variation on let in which the expressions exp$_{k}$ that provide the initial values for the variables var$_{k}$ are evaluated in an environment that includes all the letrec bindings. This permits recursion in the bindings, such as the mutual recursion of even? and odd? in the example above, or the evaluation of 10 factorial with (letrec ((fact (lambda (n) (if (= n 1) 1 (* n (fact (- n 1))))))) (fact 10)) Implement letrec as a derived expression, by transforming a letrec expression into a let expression as shown in the text above or in exercise 4.26. That is, the letrec variables should be created with a let and then be assigned their values with set!. Louis Reasoner is confused by all this fuss about internal definitions. The way he sees it, if you don't like to use define inside a procedure, you can just use let. Illustrate what is loose about his reasoning by drawing an environment diagram that shows the environment in which the $\langle$rest of body of$\rangle$ f is evaluated during evaluation of the expression (f 5), with f defined as in this exercise. Draw an environment diagram for the same evaluation, but with let in place of letrec in the definition of f. 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. 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.29 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.29, we see that views may differ as to whether that is desirable. Exercise 4.29 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?[5] 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.
 Original JavaScript Exercise 4.30 Amazingly, Louis's intuition in exercise 4.28 is correct. It is indeed possible to specify recursive procedures without using letrec (or even define), although the method for accomplishing this is much more subtle than Louis imagined. The following expression computes 10 factorial by applying a recursive factorial procedure:[6] ((lambda (n) ((lambda (fact) (fact fact n)) (lambda (ft k) (if (= 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 following procedure, which includes mutually recursive internal definitions: (define (f x) (define (even? n) (if (= n 0) true (odd? (- n 1)))) (define (odd? n) (if (= n 0) false (even? (- n 1)))) (even? x)) Fill in the missing expressions to complete an alternative definition of f, which uses neither internal definitions nor letrec: (define (f x) ((lambda (even? odd?) (even? even? odd? x)) (lambda (ev? od? n) (if (= n 0) true (od? ?? ?? ??))) (lambda (ev? od? n) (if (= n 0) false (ev? ?? ?? ??))))) 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.

[1] Wanting programs to not depend on this evaluation mechanism is the reason for the management is not responsible remark in footnote 4 of chapter 1. By insisting that internal definitions come first and do not use each other while the definitions are being evaluated, the IEEE standard for Scheme leaves implementors some choice in the mechanism used to evaluate these definitions. The choice of one evaluation rule rather than another here may seem like a small issue, affecting only the interpretation of badly formed programs. However, we will see in section 5.5.6 that moving to a model of simultaneous scoping for internal definitions avoids some nasty difficulties that would otherwise arise in implementing a compiler.
[2] The IEEE standard for Scheme allows for different implementation strategies by specifying that it is up to the programmer to obey this restriction, not up to the implementation to enforce it. Some Scheme implementations, including MIT Scheme, use the transformation shown above. Thus, some programs that don't obey this restriction will in fact run in such implementations.
[3] 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.)
[4] The MIT implementors of Scheme support Alyssa on the following grounds: Eva is in principle correct—the definitions 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 definitions (Alyssa's notion) than to produce an incorrect answer (as Ben would have it).
[5] 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).
[6] This example illustrates a programming trick for formulating recursive procedures without using define. 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 Scheme.)
4.1.6   Internal Definitions Declarations