3 ms·

SICP point is that you can implement a for loop with tail recursion easily but not viceversa.

by afiori 6y ago

Jtsummers 6y ago
I don't think that's the point, as conversion in both directions is near trivial. It is a straightforward mechanical process, it may not always be easy or simple but it's more likely tedious than hard or complex. More importantly, in the listed languages (excepting a handful of compiler optimization options) the semantics of procedure calls are different than Scheme's semantics for procedure calls. So if you, in C, convert a for loop into a tail recursive procedure you have changed the behavior of the program, not just its appearance (and same in reverse). In Scheme or another language with tail call elimination, then this conversion ought not actually change the behavior of your program (done in either direction). This also has the effect of removing the loop constructs as a necessity of the language. You can describe an efficient iterative process in Scheme with tail recursion, but you cannot describe it (in a general sense, same caveat for some optimization options) with tail recursion in the listed procedural languages and must use a special syntax element (their loop constructs) to achieve the same program semantics.
- afiori 6y ago
  Transforming a program with tail calls to one without require to move all mutually recursive tail function to a common trampoline or something similar. Rewriting a single or a few tail functions into a loop/switch is easy, but it "impossible" to do for library API without global transformations. (I could be wrong, I am not an expert in this, my basis are that an open set of function with a call in tail position can be used to describe arbitrary state machines (with the state being the arguments of the tail call and the rules the code of each function) that is open to new functions being added from anywhere. If you want to transform this in an iterative state machine all your functions need to be "registered" and "called" by the state machine.)

SICP point is that you can implement a for loop with tail recursion easily but not viceversa.

by afiori 6y ago

SICP point is that you can implement a for loop with tail recursion easily but not viceversa.

I don't think that's the point, as conversion in both directions is near trivial. It is a straightforward mechanical process, it may not always be easy or simple but it's more likely tedious than hard or complex. More importantly, in the listed languages (excepting a handful of compiler optimization options) the semantics of procedure calls are different than Scheme's semantics for procedure calls. So if you, in C, convert a for loop into a tail recursive procedure you have changed the behavior of the program, not just its appearance (and same in reverse). In Scheme or another language with tail call elimination, then this conversion ought not actually change the behavior of your program (done in either direction). This also has the effect of removing the loop constructs as a necessity of the language. You can describe an efficient iterative process in Scheme with tail recursion, but you cannot describe it (in a general sense, same caveat for some optimization options) with tail recursion in the listed procedural languages and must use a special syntax element (their loop constructs) to achieve the same program semantics.

afiori 6y ago
Transforming a program with tail calls to one without require to move all mutually recursive tail function to a common trampoline or something similar. Rewriting a single or a few tail functions into a loop/switch is easy, but it "impossible" to do for library API without global transformations. (I could be wrong, I am not an expert in this, my basis are that an open set of function with a call in tail position can be used to describe arbitrary state machines (with the state being the arguments of the tail call and the rules the code of each function) that is open to new functions being added from anywhere. If you want to transform this in an iterative state machine all your functions need to be "registered" and "called" by the state machine.)