[Cryptography] tail recursion in C [was Re: "NSA-linked Cisco exploit poses bigger threat than previously thought"]
Henry Baker
hbaker1 at pipeline.com
Mon Aug 29 13:23:00 EDT 2016
At 04:25 AM 8/27/2016, Ron Garret wrote:
>On Aug 26, 2016, at 9:31 PM, D. Hugh Redelmeier <hugh at mimosa.com> wrote:
>> | From: Ron Garret <ron at flownet.com>
>>
>> | You can't GOTO a label outside of the current function. That
>> | makes it impossible to implement tail recursion in pure C unless you
>> | compile your entire program into a single C function.
>>
>> If the last act of a function is to call another function, that call
>> can be compiled as a goto (plus some conversion of the current
>> function's activation record into the parameters for the new
>> function). Tail recursion optimization is a special case of this.
>>
>> This is purely an implementation feature.
>
>No, it's not.
>
>Some languages, like Scheme and Haskell, require proper tail-call optimization as part of the language spec.
>
>It's not optional.
Actually, "tail recursion" is equivalent to the lambda calculus axiom "Eta":
(lambda (x) (f x)) => f (Lisp/Scheme notation for unary functions.)
Axiom Eta is *independent* of the other axioms of the lambda calculus, so *no*, tail recursion is *not* "just an optimization".
More information about the cryptography
mailing list