Misconceptions about loops in C

https://dl.acm.org/doi/10.1145/3652588.3663324

by matt_d • 2 years ago

166 178 2 years ago

dl.acm.org

Dylan16807• 2 years ago

So this is specifically from the point of view of someone analyzing control flow, and how that can be tricky or ridiculous based on how many features of C you combine. Not what I expected but quite interesting. Especially the difficulty in defining a loop.

diffxx• 2 years ago

I think it's really unfortunate that most programmers are taught c style loops before tail recursion. But this is also a symptom of standard c's problem of not allowing one to define functions inside of functions. A loop can always be expressed with tail recursion. While the reverse is also true, there are many problems for which this is not straightforward given that a tail recursive function can have multiple exit points and these have to be coalesced into a single flag for the loop.

Akronymus3• 2 years ago

IMO a functional first language should be the first language people learn. Much easier to go from FP to OOP and even PP rather than the other direction.

iainmerrick• 2 years ago

How do you know it’s easier?

russdill• 2 years ago

If you're teaching someone c, tail recursion is just handing them another gun to shoot themselves in the foot with.

dist-epoch• 2 years ago

That's like saying "it's unfortunate kids are first taught elementary arithmetic before integrals". C-style loops are natural and easy to understand, tail recursion is not.

svachalek2• 2 years ago

C loops are natural and easy to understand for programmers who were trained on loops. I doubt that tail recursion is any harder to get for students who don't have that background. Would be an interesting experiment though.

photochemsyn• 2 years ago

Or like saying they should start their study of addition and multiplication from the perspective of group theory - since the integers (Z) under addition forms a group because it satisfies closure, associativity, identity, and inverses, while Z under multiplication does not form a group because, although it satisfies closure, associativity, and identity, it fails to provide inverses for all elements.

chongli2• 2 years ago

Recursion is more natural and deeply-engrained than people realize. Natural language has a recursive grammar:

My dog => My friend's dog => My father's friend's dog => My father's sister's cousin's nephew's teacher's friend's plumber's dog's chew toy.

We can construct sentences like this with a completely arbitrary level of recursive nesting. It's so natural that people do it without thinking about it. Recursion only becomes unnatural when we prime people on it and get them thinking it's scary and complicated.

com2kid3• 2 years ago

I'd like to remind everyone that the computer doesn't care. The computer knows JMP (e.g. GOTO).

Everything else is just abstraction's we're built up to make our lives easier.

If we always jump to the top of the function, or if we jump someplace else, the machine cares not. Just don't blow the stack.

Jtsummers3• 2 years ago

there are many problems for which this is not straightforward given that a tail recursive function can have multiple exit points and these have to be coalesced into a single flag for the loop.

Loops don't require coalescing the exit condition to a single flag (or even a single conditional expression). You can also use break (or your language's equivalent) to allow multiple exits from the same loop.

User232• 2 years ago

Break also considerably complicates loop semantics. For example you can no longer rely on the loop condition being false on loop termination. Instead you have to do a flow analysis of every loop and conditional leading to the break to determine the established postcondition.

KerrAvon• 2 years ago

C compilers may not optimize tail recursion properly, so it's not necessarily safe to teach C programmers to do that.

speed_spread• 2 years ago

Tail or not, I find recursion to be too unsettling for my non-math orientated brain to deal with on the daily. It's like looking at oneself between facing mirrors. I find the loop (in for or while form) to be more comfortable to reason about. I believe I'm not alone in this situation.

runevault2• 2 years ago

Without having a way to tell the compiler to fail if it can't TCO (f# finally got this with a function attribute in 8.0), teaching tail calls first is only going to lead to problems because screwing them up to pile up on the stack is likely when you don't know what you're doing.

nequo5• 2 years ago

OCaml[1] and Scala[2] have had this too.

[1] https://batsov.com/articles/2024/01/16/learning-ocaml-verify...

[2] https://www.scala-lang.org/api/current/scala/annotation/tail...

akira25012• 2 years ago

A loop can always be expressed with tail recursion.

If I were writing the code in assembly, I would just use a loop, because that's what the machine is optimized to perform.

But this is also a symptom of standard c's problem of not allowing one to define functions inside of functions.

There are extensions that do this; however, they cannot create a scoped closure for you so nobody cares to use them for anything.

and these have to be coalesced into a single flag for the loop.

Or just use 'goto'.

WJW2• 2 years ago

Do you mean a conditional jump? Because assembly doesn't know about loops. And recursion is basically a jump too, even more so if you manually do the TCO. They are literally equivalent.

duped• 2 years ago

I don't think many people consider tail calls more intuitive than a while loop. The opposite is more obvious.

aleph_minus_one• 2 years ago

I don't think many people consider tail calls more intuitive than a while loop. The opposite is more obvious.

This depends a lot on the background of the respective person. For someone who is more trained in classical mathematics, tail calls are more intuitive (or rather: nearer to their knowledge base) than while loops.

kimixa• 2 years ago

I mean "for" and "while" loops are effectively used in natural language all the time, even to the youngest of kids.

"Do this action 10 times" "Put one item in each box"

I fail to see how recursion is /more/ intuitive, in pretty much every (english) language construct I can think of the condition is separate from the action.

onetimeuse923042• 2 years ago

How is this unfortunate?

Most programmers learn about loops pretty much at the absolute start of their development experience, where they don't yet have a way to talk about recursion. Don't even start about tail recursion or tail recursion optimisation.

Zambyte• 2 years ago

Most people learning programming have already been exposed to function calling in math (f(x)=x+1). Recursion is not a very big jump semantically from this. Conditional loops are a (relatively) big jump.

smaudet3• 2 years ago

where they don't yet have a way to talk about recursion.

I'd like to know how its unfortunate as well, I'm not sure I agree with this though.

    int a = 0
  begin:
    if a == 10 {
      jump :end
    } else {
      a = a + 1
      jump :begin
    }
  end:

The programmer will have learnt that programs have a beginning and an end, they will have some notion of a variable, its type, and manipulating their values. They will even likely have learnt conditional branching logic. The only new concept here is that of jumping areas of code.

If you next introduce methods you can clean it up and illustrate it more cleanly:

  myFunc(int a) {
    if a == 10 {
      return
    } else {
      a = a + 1
      return myFunc(a)
    }
  }

  myFunc(0)

Finally you can explain the programmer "hey, there's this shortcut we can take called a loop that expresses this more succinctly":

  int a = 0
  while (a != 10) {
    a = a + 1
  }

Nice simple-looking code. Yet this concept requires being able to grok much more than the relatively simple tail-recursive definition.

Farmadupe• 2 years ago

I feel like there's a semi-philosophical question somehwere here. Recursion is clearly a core computer science concept (see: many university courses, or even the low level implementation of many data structures), but it's surprisingly rare to see it in "day to day" code (i.e I probably don't write recursive code in a typical week, but I know it's in library code I depend on...)

But why do you think we live in a world that likes to hide recursion? Why is it common for tree data structure APIs to expose visitors, rather than expecting you write your own recursive depth/breadth-first tree traversal?

Is there something innate in human nature that makes recursion less comprehensible than looping? In my career I've met many programmers who don't 'do' recursion, but none who are scared of loops.

And to me the weird thing about it is, looping is just a specialized form of recursion, so if you can wrap your head around a for loop it means you already understand tail call recursion.

zelphirkalt6• 2 years ago

It is unfortunate, because many programmers develop some feeling of recursion being weird, more difficult or in any way worse than a loop, while this is mostly based on unfortunate language design and lack of familiarity with recursion. It also often comes along with fear of recursive data structures, which is holding programmers back and the products they make.

jameshart• 2 years ago

If we’re going to fundamentally alter the way programmers are educated to handle repetitive tasks, the first lesson should be on map and reduce, not counters or recursion.

suprjami3• 2 years ago

In my experience, modern optimising compilers can turn many naive loops into tail recursive loops.

Actually learning tail recursion and writing loops for it is a lot less necessary today than it was in the 1980s. It isn't necessary to teach it to beginners anymore because the compiler largely does the heavy lifting for us.

These days, tail recursion is a very advanced performance tuning trick, only used when you've positively identified your compiler version's implementation of your loop as the cause of slowness and you're willing to incur the increased code complexity for the increased performance.

guntars2• 2 years ago

How can tail recursion have better performance if they both compile to the same machine instruction - a conditional jump?

CyberDildonics• 2 years ago

Using recursion for loops then letting the compiler work out that it's not actually recursion and it actually a loop is more for people caught up in the pageantry of programming than people who want to make programs run.

layer8• 2 years ago

Loops are more intuitive for similar reasons that ∑ and ∏ are more intuitive than the equivalent recursive formulation.

dboreham2• 2 years ago

Perhaps they just want to write programs that work without becoming confused?

zogrodea4• 2 years ago

I think recursion is easier to read than C-style for-loops because you don't need to memorise syntax.

for (int i = 0; i < 5; i++) {...}

```let rec func_name counter = if counter = 5 then print "blast off!" else func_name (counter + 1)```

I don't really need to memorise the order of operations compared to a for loop (initialise, exit condition, increment) and I don't need to memorise if the exit condition means "execute while this is true" or "break the loop if this is true". That's just me though. I think the syntax for recursion is easier but loops might conceptually be easier to understand.

I think, better than both of those for the general case (and a good introduction) are "fold" functions and "foreach"-style loops, which iterate over every element in a list. I think those are used more often, and the reason you may want to do this is clearer to a student.

ummonk• 2 years ago

Aren’t you leaving out the initialization in your recursive example though?

nomel4• 2 years ago

With beginners, there's a severe "working memory" limitation from the fact that they have no compression that comes from tying things together.

The for line ends up being one independent line they can grok, then free from their memory when looking inside the loop, knowing that I gets bigger for a while. From my experience, something like the recursion will blow away a beginners working memory, because they can't piecewise it. But, the biggest problem is the for loop is trivially expanded with the exact same format, you just shove stuff into the body. The recursion method requires significant reworking to expand. Beginners appreciate simple templates that they can understand and modify, because they're still putting it all together.

Mikhail_Edoshin2• 2 years ago

Loops themselves are a design mistake. Look how wordy loop notation is. This is a sign of an internal struggle: the real thing does not fit a Procrustean concept. In C we have five loop-related keywords: 'do', 'while', 'for', 'break', and 'continue'. All of them are syntactic sugar for 'goto'. Yet all that sugar is not sufficient for certain cases of control flow. And these cases are not even exotic. We all know how to loop forward in C:

    for (i = 0; i < n; ++i)

Now let's try to loop backward:

    for (i = n; i--; )

Why this thing is so asymmetric to the forward case? And doesn’t it, perhaps, start to become a little too idiomatic? Now, if we try to rewrite them with 'goto':

        i = 0;
    a:  <body>
        ++i;
        if (i < n)
          goto a;

        i = n;
    b:  --i;
        <body>
        if (i > 0)
           goto b;

Isn’t this more symmetric? Can we now see that the chief reason of asymmetry is that 'n' is not a valid value for 'i' but '0' is?

'Goto' is, of course, an implementation detail and is not convenient for reasoning. Thing is loops are not necessary for reasoning either. They are an implementation detail mistakenly dressed into reasoning clothes.

trealira4• 2 years ago

I also think that some algorithms can be expressed better using goto than with a combination of nested loops, break, and continue. For example, Donald Knuth talks about the "basic backtrack" algorithm in fascicle 5 [0], which he uses to implement a solution to the N-queens problem.

It's possible to express it as a set of while loops (which someone on Stack Overflow showed [1]), but it's, IMO, less readable than the goto version. Of course, the recursive solution is the most readable anyway.

Edit: Also, both the goto version and while loop version of that algorithm on the Stack Overflow post have an out of bounds index when col and row are both zero. That algorithm was meant for 1-indexed arrays and was not properly translated.

[0] https://cs.stanford.edu/%7Eknuth/fasc5b.ps.gz

[1] https://stackoverflow.com/questions/78614303/can-knuths-algo...

nedt• 2 years ago

You are writing it differently with the goto. You can do the same with the for loop and it becomes symmetric again

  for (i = 0; i <  n; ++i);
  for (i = n; i >= 0; --i);

(Note: not sure if intended that backward should run more often and include i = n)

pizlonator6• 2 years ago

It’s great to see this write up - should be mandatory reading for anyone getting started with compilers. But it’s not news for the experienced folks in the field.

almostgotcaught8• 2 years ago

I wish people would quit pretending that a research paper should only have the most novel/freshest/unique results. It would not only dramatically improve researchers lives it would actually improve the average quality of research output because you would no longer have to exaggerate claims.

pizlonator6• 2 years ago

It’s a terminology issue for me.

This paper is documenting reality that is known to folks who practice the craft so in that sense it is not research as I would normally think of it. But it is useful documentation and so worth having written down.

marmaduke• 2 years ago

Yes, amen

There's not having to exaggerate and moreover there's value in rehashing known but tricky stuff

slashdave3• 2 years ago

I wouldn't call this a research paper. It doesn't include any research.

eru4• 2 years ago

[...] should be mandatory reading for anyone getting started with compilers.

Well, only for those folks who you taint with C before you let them loose on compilers. If you follow something like https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_... as your introduction, I doubt you would benefit from worrying about pitfalls of C.

pizlonator6• 2 years ago

But then you’d want your compiler to infer loops from tail recursion and then you’d have all of the same problems as this paper cites.

The paper’s title is misleading in that way. It’s describing problems with loops, not problems with C loops.

IshKebab• 2 years ago

These are all obvious but this looks very useful as a checklist if you are writing a static analysis tool, which I think is the intended purpose.

user-• 2 years ago

For the first time, I used a c style loop in a bash script today. What a coincidence

ssahoo• 2 years ago

Why the fuck they still write papers in 2 columns? It's a pain both for humans and computers alike. Here is the link to PDF https://dl.acm.org/doi/pdf/10.1145/3652588.3663324

pornel• 2 years ago

If you're wondering why the paper seems to complicate "simple" constructs by converting them to control flow graphs — that's because many other kinds of static analysis, like tracking when variables are initialized and overwritten, are even more puzzling when trying to analyze very stateful code directly based on the syntax tree. The graph representation allows splitting the code into smaller blocks, and remove a lot of statefulness from them.

WalterBright2• 2 years ago

Back in the 80's it was normal for C compilers to recognize `for` loops and do optimizations on them.

I had attended a summer class at Stanford on Data Flow Analysis, and took advantage. My compiler would break all the C flow control constructs into `if` and `goto` statements. Then, the optimizer would reconstruct the loops using graph algorithms.

Then, no matter what snarl of for, while, break, do-while, continue switch, or goto statements the programmer wrote, the optimizer could find all the loops, identify the loop variables, the loop header, etc. and then optimize it.

eru4• 2 years ago

I imagine that would also be a good idea, if you wanted to (re-) optimise something like Risc-V assembly?

dzaima• 2 years ago

While good in general, that does have its downsides. I've had a case of adding an "if (undesired input format) { change input format; goto place_that_decides_method; }" resulting in clang now considering most of a massive function as being a loop body, and thus a bunch of computation from various branches being extracted to be always calculated outside "the loop" (despite me knowing that at no point should any single path (beyond the small dispatching part) be executed more than once).

WalterBright2• 2 years ago

All optimizations have cases where they are deleterious. The number I used for loop optimizations is assume the loop executes 10 times. It works reliably well.

fweimer• 2 years ago

GCC does the same thing to this day. As a result, the GCC AST hasn't much S in it, except for some OpenMP constructs (which are preserved in the AST). It's not great if you want to write syntax-driven tools.

OnlyMortal• 2 years ago

Back in the late 80s, the Mac MPW C compiler would create a stack frame every time you used a brace bracket.

As a 68k coder (from Amiga)I often looked at the code generated and re-write the pinch points in assembler.

A Boyer-Moore text searching algorithm being one of them. The C code was nicked from Dr Dobbs.

eru4• 2 years ago

First author is named as 'Martin Brain'. I wonder if that's a case of nominative determinism at work.

fifticon• 2 years ago

it was probably originally Martian Brain

userbinator2• 2 years ago

This reminds me of the decompilation stuff I worked on long ago, which was essentially a large recursive pattern-matching algorithm. Flows that couldn't be matched as loop constructs just got left as gotos, and breaks would be identified as such where possible, but for the most part it worked pretty well with the (very) stupid compiler output of the time, and even with much of the handwritten Asm that was far more common than it is now.

Perenti• 2 years ago

Best footnote for June:

returns should be thought of as domesticated gotos but domesticated in the same way that cats are domesticated

raverbashing• 2 years ago

Good footnote but crap take

As even their example mentions error handling

Goto sucks but not having proper exception handling sucks more

salawat2• 2 years ago

So returns are gatos?

mshockwave• 2 years ago

LLVM tries to canonicalize all the loops into one of the two canonical forms[1] before doing any useful analysis and transformations. It has been quite effectives. Not all loops can be shaped into a canonical one though.

[1] https://llvm.org/docs/LoopTerminology.html

Misconceptions about loops in C

Related Stories