Sequence Evaluation and Tail Recursion Evaluating function applications - SICP Comparison Edition" /> 5.4.2   <span style="color:green"> Sequence Evaluation and Tail Recursion </span> <span style="color:blue"> Evaluating function applications </span> - SICP Comparison Edition
Original JavaScript
 Original JavaScript
 Original JavaScript The metacircular implementation of the evaluator in chapter 4 does not specify whether the evaluator is tail-recursive, because that evaluator inherits its mechanism for saving state from the underlying Scheme. With the explicit-control evaluator, however, we can trace through the evaluation process to see when procedure calls cause a net accumulation of information on the stack. The metacircular implementation of the evaluator in chapter 4 isn't tail-recursive. It implements a return statement as a constructor of a return value object containing the value to be returned and inspects the result of a function call to see whether it is such an object. If the evaluation of a function body produces a return value object, the return value of the function is the contents of that object; otherwise, the return value is undefined. Both the construction of the return value object and the eventual inspection of the result of the function call are deferred operations, which lead to an accumulation of information on the stack.
 Original JavaScript Our evaluator is tail-recursive, because in order to evaluate the final expression of a sequence we transfer directly to eval-dispatch without saving any information on the stack. Hence, evaluating the final expression in a sequence—even if it is a procedure call (as in sqrt-iter, where the if expression, which is the last expression in the procedure body, reduces to a call to sqrt-iter)—will not cause any information to be accumulated on the stack. If we did not think to take advantage of the fact that it was unnecessary to save information in this case, we might have implemented eval-sequence by treating all the expressions in a sequence in the same way—saving the registers, evaluating the expression, returning to restore the registers, and repeating this until all the expressions have been evaluated:[8] ev-sequence (test (op no-more-exps?) (reg unev)) (branch (label ev-sequence-end)) (assign exp (op first-exp) (reg unev)) (save unev) (save env) (assign continue (label ev-sequence-continue)) (goto (label eval-dispatch)) ev-sequence-continue (restore env) (restore unev) (assign unev (op rest-exps) (reg unev)) (goto (label ev-sequence)) ev-sequence-end (restore continue) (goto (reg continue)) Our explicit-control evaluator is tail-recursive, because it does not need to wrap up return values for inspection and thus avoids the buildup of stack from deferred operations. At ev_return, in order to evaluate the expression that computes the return value of a function, we transfer directly to eval_dispatch with nothing more on the stack than right before the function call. We accomplish this by undoing any saves to the stack by the function (which are useless because we are returning) using revert_stack_to_marker. Then, rather than arranging for eval_dispatch to come back here and then restoring continue from the stack and continuing at that entry point, we restore continue from the stack before going to eval_dispatch so that eval_dispatch will continue at that entry point after evaluating the expression. Finally, we transfer to eval_dispatch without saving any information on the stack. Thus, when we proceed to evaluate a return expression, the stack is the same as just before the call to the function whose return value we are about to compute. Hence, evaluating a return expression—even if it is a function call (as in sqrt_iter, where the conditional expression reduces to a call to sqrt_iter)—will not cause any information to accumulate on the stack.[9] If we did not think to take advantage of the fact that it is unnecessary to hold on to the useless information on the stack while evaluating a return expression, we might have taken the straightforward approach of evaluating the return expression, coming back to restore the stack, and finally continuing at the entry point that is waiting for the result of the function call: "ev_return", // alternative implementation: not tail-recursive assign("comp", list(op("return_expression"), reg("comp"))), assign("continue", label("ev_restore_stack")), go_to(label("eval_dispatch")), "ev_restore_stack", revert_stack_to_marker(), // undo saves in current function restore("continue"), // undo save at $\texttt{ev\char`_application}$ go_to(reg("continue")),
 Original JavaScript Note that our JavaScript implementation requires the use of return in order to be tail-recursive. Because the undoing of the register saves takes place at ev_return, removing return from the count function above will cause it to eventually run out of stack space. This explains the use of return in the infinite driver loops in chapter 4.
 Original JavaScript Exercise 5.23 Explain how the stack builds up if return is removed from count: function count(n) { display(n); count(n + 1); } 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 5.24 Implement the equivalent of push_marker_to_stack by using save at compound_apply to store a special marker value on the stack. Implement the equivalent of revert_stack_to_marker at ev_return and return_undefined as a loop that repeatedly performs a restore until it hits the marker. Note that this will require restoring a value to a register other than the one it was saved from. (Although we are careful to avoid that in our evaluator, our stack implementation actually allows it. See exercise 5.11.) This is necessary because the only way to pop from the stack is by restoring to a register. Hint: You will need to create a unique constant to serve as the marker, for example with const marker = list("marker"). Because list creates a new pair, it cannot be === to anything else on the stack. 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 5.25 Implement push_marker_to_stack and revert_stack_to_marker as register-machine instructions, following the implementation of save and restore in section 5.2.3. Add functions push_marker and pop_marker to access stacks, mirroring the implementation of push and pop in section 5.2.1. Note that you do not need to actually insert a marker into the stack. Instead, you can add a local state variable to the stack model to keep track of the position of the last save before each push_marker_to_stack. If you choose to put a marker on the stack, see the hint in exercise 5.24. 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

[1] This is an important but subtle point in translating algorithms from a procedural language, such as JavaScript, to a register-machine language. As an alternative to saving only what is needed, we could save all the registers (except val) before each recursive call. This is called a framed-stack discipline. This would work but might save more registers than necessary; this could be an important consideration in a system where stack operations are expensive. Saving registers whose contents will not be needed later may also hold on to useless data that could otherwise be garbage-collected, freeing space to be reused.
[2] We assume that the syntax transformer operator_combination_to_application is available as a machine operation. In an actual implementation built from scratch, we would use our explicit-control evaluator to interpret a JavaScript program that performs source-level transformations like this one and function_decl_to_constant_decl in a syntax phase that runs before execution.
[3] We add to the evaluator data-structure functions in section 4.1.3 the following two functions for manipulating argument lists: function empty_arglist() { return null; } function adjoin_arg(arg, arglist) { return append(arglist, list(arg)); } We also make use of an additional syntax function to test for the last argument expression in an application: function is_last_argument_expression(arg_expression) { return is_null(tail(arg_expression)); }
[4] The optimization of treating the last argument expression specially is known as evlis tail recursion (see Wand 1980). We could be somewhat more efficient in the argument evaluation loop if we made evaluation of the first argument expression a special case too. This would permit us to postpone initializing argl until after evaluating the first argument expression, so as to avoid saving argl in this case. The compiler in section 5.5 performs this optimization. (Compare the construct_arglist function of section 5.5.3.)
[5] The order of argument-expression evaluation by the function list_of_values in the metacircular evaluator is determined by the order of evaluation of the arguments to pair, which is used to construct the argument list. The version of list_of_values in footnote 4 of section 4.1 calls pair directly; the version in the text uses map, which calls pair. (See exercise 4.2.)
[6] The special instructions push_marker_to_stack and revert_stack_to_marker are not strictly necessary and could be implemented by explicitly pushing and popping a marker value onto and off the stack. Anything that could not be confused with a value in the program can be used as a marker. See exercise 5.24.
[7] We saw in section 5.1 how to implement such a process with a register machine that had no stack; the state of the process was stored in a fixed set of registers.
[8] We can define no-more-exps? as follows: (define (no-more-exps? seq) (null? seq))
[9] This implementation of tail recursion is one variety of a well-known optimization technique used by many compilers. In compiling a function that ends with a function call, one can replace the call by a jump to the called function's entry point. Building this strategy into the interpreter, as we have done in this section, provides the optimization uniformly throughout the language.
5.4.2   Sequence Evaluation and Tail Recursion Evaluating function applications