[Cryptography] tail recursion in C [was Re: "NSA-linked Cisco exploit poses bigger threat than previously thought"]

[Henry Baker]

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".