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.
Original JavaScript
Original JavaScript
Original JavaScript
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