dont-tail-call and use it like this:(dont-tail-call (foo x))The semantics of Scheme are that the arguments are evaluated before the call to the function, so the call to
foo is required to occur before the call to dont-tail-call which necessitates allocation of a continuation.But what about a really clever compiler that somehow “optimizes” away the call to
dont-tail-call? Such an “optimization” is highly questionable because it changes the observable semantics of the program so it is no longer call-by-value. A compiler that performed that transformation wouldn't be a Scheme compiler because Scheme is a call-by-value language.But what if we had really clever compiler and we disregard the change in semantics? We can easily thwart the compiler by deferring the definition of
dont-tail-call until run time. Even the cleverest compiler cannot see into the future.The definition of
dont-tail-call is left to the reader, as is how to defer it's definition until run time.
R5/R7RS say at the end of section 3.5:
ReplyDelete(lambda ()
(if (g)
(let ((x (h)))
x)
(and (g) (f))))
Note: Implementations are allowed, but not required,
to recognize that some non-tail calls, such as the call to h
above, can be evaluated as though they were tail calls.
In the example above, the let expression could
be compiled as a tail call to h.
(The possibility of h returning an unexpected number
of values can be ignored, because in that case the
effect of the let is explicitly unspecified and
implementation-dependent.)
If we simplify the example by getting rid of the if (which isn't relevant) and macroexpanding the let into lambda, we get ((lambda (x) x) (h)) which is simply the identity procedure applied to the value of (h). R5RS and R7RS apparently allow some exceptions to call-by-value semantics, and they give us an example of the identity procedure applied to an argument. This is a bit vague because they don't specify exactly when exceptions to call-by-value are allowed. They probably didn't intend to make it possible to transform ((lambda (x) (g) x) (h)) into (begin (g) (h)) because this would change the order in which side effects happen. If the operator weren't the identity procedure but a procedure dependent upon the value of (h), then clearly (h) has to be evaluated first. The operator could be the identity everywhere except one point dependent on the value of (h) and this would still require (h) to be evaluated first. Even if the operator did just compute the identity, if it had a side-effect dependent on the value of (h), then (h) would have to be evaluated first. If our compiler couldn't determine that the operator is the identity at compile time (or any time before application time), then (h) would have to be evaluated first.
ReplyDeleteAll of these suggest implementation strategies for dont-tail-call that will prevent even the most aggressive Sufficiently Smart Compiler with whole code analysis from eliding the call.