Dec 17, 2008

What's need by tail-recursion optimization in funcational language?

What's the common ideas needed by all high-level programming languages?

* Transfer of control
- conditional
- unconditional
* Environment operation
- variable binding on function entry
- declaration of local variable
* Side effects
- assignment
- IO
* Process synchronization
- resource allocation
- passing of information between processes

The idea behind tail-recursion optimization in applicative language

* function is goto with arguments. There's no need for return address for a function. We need save a return address on the stack when we begin to evaluate a form (function call) which is to provide an argument for another function, rather than when we invoke the function.
* so, we pushes addtional control stack only when evaluate forms, for function application, we only need set up environments.
* this is why we can't use the same way to optimize tail-recursion in imperative language - the return address for the caller function may not be the continuation address of the callee
* lexical binding is necessary for lambda goto rule. we can't use goto to replace funcation call with dynamic binding.

An interesting symmetry: control constructs determine constraints in time (sequencing) in a program, while environment operators determine constraints in space (textual extent, or scope).

Ref. Guy Lewis Steele, Jr.. "Lambda: The Ultimate Declarative". MIT AI Lab. AI Lab Memo AIM-379. November 1976.

No comments:

Post a Comment