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

Ron Garret ron at flownet.com
Sat Aug 27 07:25:14 EDT 2016


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.  This is why very few compilers for non-C-like languages actually use C as an intermediate representation.  It’s too constraining.  There are exceptions, of course, but they all rely on various hacks.  There is in fact a whole branch of research devoted to the completely artificial problem of how to compile non-C-like languages to C.  If C were truly a good portable assembler, this would be a non-issue.

> I cannot think of anything in C that precludes this optimization.  Just culture?

Yes, of course, though I think it’s a mistake to write it off as “just” culture.  C culture has become so prevalent that a majority of programmers aren’t even aware that there are viable alternatives.  Any language that doesn’t conform to the C culture is considered “weird” and not worthy of serious consideration.

Remember that my original comment was in response to the claim that C is a good portable assembler.  That’s only true if you’re using it as a target for a C-like language.  For a non-C-like language C is a terrible portable assembler.  The reason C is considered a good portable assembler is that many people think that C-like languages are all there is, or at least all that matter.

> This optimization confuses programmers trying to debug the result,
> but then so do many optimizations.
> 
> Slide to crypto relevance:
> 
> Optimization can destroy some properties that one might have
> intentionally coded into a program.

Yes, all this is true.  But debuggability train left the C station a long time ago.  The fact that there is so much undefined behavior in C, and that the standard allows a program with undefined behavior to do *anything at all* means that you pretty much can’t count on a C compiler to do anything reasonable under any but the most extraordinary of circumstances.  This is not to say that there aren’t C compilers that do reasonable things under a broad range of circumstances.  But you can’t count on it.

All of these are reasons why I dispute the claim that C is “a good portable assembler.”  C is a really cool hack that lets you do amazing things under very tight resource constraints.  But it’s not 1970 any more.  We don’t need to run our compilers on machines with 64k of RAM.  But for some reason we are still programming with a language designed primarily to meet that constraint.

rg



More information about the cryptography mailing list