Misconceptions about loops in C
dl.acm.org
dl.acm.org
returns should be thought of as domesticated gotos but domesticated in the same way that cats are domesticated
As even their example mentions error handling
Goto sucks but not having proper exception handling sucks more
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.
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.
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.
I "practice the craft" (and I'm fully, gainfully, highly employed to practice the craft), I have a PhD in the "craft", I have published papers about the "craft", and I'm here to tell you IDGAF about what's terminologically research and what's not. I only care about well-written, detailed articles that explain a complex technical issue, problem, or solution.
EDIT:
"Research is 'creative and systematic work undertaken to increase the stock of knowledge'. It involves the collection, organization, and analysis of evidence to increase understanding of a topic, characterized by a particular attentiveness to controlling sources of bias and error."
The crucial/key words/phrases here are: "systematic", "increase understanding of a topic", "controlling sources of bias and error". Nowhere do I see "completely brand new never before heard of".
https://en.wikipedia.org/wiki/Research
EDIT2:
> It’s a terminology issue for me.
PLDI, the premier compilers/PL conference, which you must put a lot of stock in since you care about the current institutionally supported notion of "research", disagrees with you.
I’ve been published there, twice, but academic understanding of PL implementation is probably at least a decade (if not more) behind where the top folks in industry are. If you’re good at abstract interpretation, IR design, GC, etc then you’re going to be making good money and having a blast shipping that shit to people, usually in some open source context with a friendly and nontoxic community around you. So much better than the hatchet-job style reviewing and publish-or-perish of the PLDI crew.
My friend you're just driving more nails into your own coffin; yes I'm very well aware of this and hence all the more reason to dispense with the idea that what PLDI publishes needs to be cutting edge novelty.
> So much better than the hatchet-job style reviewing and publish-or-perish of the PLDI crew.
Again: you're literally contradicting yourself. The reason PLDI and all other "top" venues are so toxic is because of people like you on review committees that demand utmost novelty. Relax your requirements (i.e. encourage them to relax their requirements) and you will magically transform academic research into a fun, friendly, and vibrant community.
There's not having to exaggerate and moreover there's value in rehashing known but tricky stuff
I wasn't actually - I was pointing out the contradiction in supporting gatekeeping and then the second-guessing the gatekeepers.
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.
The paper’s title is misleading in that way. It’s describing problems with loops, not problems with C loops.
that claim seems absurd. all the functional languages I've come across also frequently use routines, modules, and 'objects of whatever' to manage the complexity of huge amounts of code.
objects/entities are just a pattern for hiding complexity behind a simple interface. they can be useful in any language, regardless of mutability.
OOP as a pattern, rather than a language construct.
the great advantage here is that all manipulations are local. there is no spooky action at a distance in an immutable language.
as long as you stay out of the IO monad, anyways.
let rec eventLoop state = let input = getInput () let newState = update input state drawState state; eventLoop newState
The update function takes an existing state and an input record (key events, etc.), returning a new state (which may have nested records within itself but it is all immutable).
New state is kept by the recursion (passing new state to the same function). The only IO is getting input and drawing, which are inherently side-effecting operations.
I do have nested records, but (at each stage) they get joined into a new parent record. No mutability there.
numbers.map(x => x * x)
let result = [];
for (let i = 0; i < numbers.length; ++i) {
result.push(numbers[i] * numbers[i]);
}For example, what if you now want to write to a log before each multiplication, or you want to time how long each multiplication takes? Suddenly, the latter seems far preferable.
numbers.map(x => {
console.log(x);
return x * x;
})
While, when starting with PP or OOP, it is incredibly hard to then learn FP.
for numbers $ \x -> do
Console.log x
return (x * x)It's not enough to just point at an example of a monad and say "look, the example is simple, therefore the generalisation is simple". As many philosophers have pointed out, particulars are easier to point out than universals. The latter requires a lot of thought.
> As many philosophers have pointed out, particulars are easier to point out than universals. The latter requires a lot of thought.
Fair enough, that’s a good point.
You don’t have to use >>= and >> if you don’t want to though. Use the do notation instead and the code will look much more familiar. You also mention fmap; that’s `.map` in Rust, etc. in other languages.
All I’m trying to say is, there are many parallels between Haskell and other languages at the level of particulars. The concepts behind >>= and >> are not unique to it anymore. So there is hope if you want to reconstruct the universal concepts in your mind from those particulars, especially if you use fitting abstractions like the do notation.
Of course there are parallels, there must be for Haskell to be able to do what imperative languages can do. However that doesn't mean the abstractions are simple. "do notation" is another complicated generalisation and there's no way any Haskell programmer it going to be able to simply pretend that their do notation is a normal imperative language.
You seem to be asserting that I'm claiming that Haskell simply can't do the things that imperative languages can do, and I'm not at all and I don't understand how you inferred that.
No, that’s not my intention. I responded to your view that monads are hard to understand by saying that they show up in other languages too in non-trivial ways.
I also don’t mean to say that Haskell is like imperative languages. Just that monads by themselves show up in imperative languages too, so they are not as esoteric as the operator names (>>=, >>) may make them seem.
I appreciate that you followed up in good faith. The point of view that you expressed makes sense to me.
You were a kid in shop class. Now you want your kids to take shop class. Because, recursion.
If you have to make up nonsensical examples to prove your point, then you probably don't have a point.
> You were a kid in shop class. Now you want your kids to take shop class. Because, recursion.
That's not recursion.
def spawn():
take_shop_class()
return spawn()Int counter_of_sanded_legs = 0;
do{
Sand_a_leg; Counter_of_sanded_legs++;
} While (counter_of_sanded_legs < 4);
Need four legs, have none. Doing while I don't have enough. How many legs do I have? 1. Doing. How many legs do I have? 2. Doing. How many legs do I have? 3. Doing. How many legs do I have? 4. Done.
Alternatively:
for (int i=0;i<4;i++;) {
//how we start; whether we repeat; how we update our counter.
Sand_leg();
}
You only need to sand a leg when you don't have enough legs.
These aren't that far off of actual things you'd do moving about. In fact, not realizing that you're distilling something physical into the symbolic is a leading cause of confusion in my experience.
A "do x times" dedicated looping construct would be syntactic sugar that detracts from understanding what the underlying semantics are; which if you're teaching how to program is a bad idea. The idea is to have your understanding precede the machine. Not lag behind.
You can start screwing around with abstractions after you get the basics. As once you have the basics, you can compose them into any form you want.
The rest is just increasing levels of crippling mental illness.
But take a newbie, and "do this 3 times" in a loop is far more clear than the recursive equivalent.
Sometimes recursion does allow you to reason about code more easily or come to a working solution faster, sometimes it does not.
Measure the concrete: CPU time and memory consumed. Iteration will likely trump recursive methods w.r.t both these metrics. If it doesn't, you can likely transform your iterative algorithm to one that utilizes SIMD (not always).
Let me try: in classical dance, martial arts, or even skateboarding, advanced skills manifest as effortlessness: the movements comes naturally, they're not forced, things just flow.
If you compare a typical functional (recursive + pattern matching, but the point would stand even with a fold) factorial with an imperative one (for loop), the functional approach is more effortless, you have to be less explicit about what's going on. It's more eloquent.
However as you seem to imply, when we're programming, the focus should be on delivering something that works as expected; this particular kind of aesthetic is secondary at best.
Using the beholder's eye, of course.
Simplicity is actually a hallmark of this sense of beauty.
What culty group even exists around recursion anyway? Can you get me an invitation?
Everyone else doesn't care, shouldn't care.
But yeah, using it systematically (in a non-functional language) is unwise.
But this doesn't change the fact that humans seem to intuitively perceive iteration as more natural.
Like, "space" and "time" can't be understood as two distinct notions, per relativity. But we still perceive them as such on a daily basis.
There are examples of other communities which have invented something pretty much the same as loop syntax, for example you get things which are basically loops in knitting patterns or (less reguarly) in recipes. I have never seen an example of recursion outside computer science/programming.
Also in crochet. A pattern will have instructions like
* (2tr, 3ch, 2tr) all in next 2ch sp; repeat from * 6 times more
where statements like 2tr mean 2 treble stitches and the bit between the * symbols is repeated 6 times
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.
Darth Helmet: I am your father's brother's nephew's cousin's former roommate.
Lonestar: What does that make us?
Darth Helmet: Absolutely nothing.
It's VASTLY simpler than the alternative. See how difficult it is to express the same relationship without using the recursive grammar.
Anyway, give anyone a family tree diagram containing all of these relationships and they can follow the chain from that sentence to the destination. This is the essence of why we use recursion in computer science in the first place: it's the best tool for navigating trees.
This is because English sucks at tree relationships. Other languages are much better at this.
For example, Mandarine Chinese has unique words for each side of the family tree (e.g. unique word for Grandma on mother's side vs Grandma on Father's Side), and also a rather logical system to describe how you navigate the tree.
Chinese isn't even unique in this, it is just that English is really really bad.
Or is it that you're referring to other relations than those two having unique words? If so then that would seem to introduce its own problems in ballooning the vocabulary.
Maybe English is just happier with the ambiguity?
I got very tired, very quickly, even as a kid, of saying "Grandma on my Dad's side".
I had two Uncles with the same name, again, "Uncle <foo> on my Dad's side" is a PITA after awhile.
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.
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.
It has consequences, but it's first week sort of thing because it's so easy/relatable.
I rarely write loops where the relationship between the loop control variables has anything meaningful to say about what the iterations did.
It is a little disappointing how few programmers know how to construct a nontrivial loop that both always terminates and does what it’s supposed to for all inputs.
Binary search is a classic example. If you think it’s trivial to get right, you probably aren’t. Knuth has some interesting things to say about it in The Art of Computer Programming.
You have to look at both. If it turns out that the body's behavior can be easily described in terms of the loop control variables (or the reverse), great, but assuming that it does and trying to fix up things when that gets complicated is a disaster.
Of course, if you dislike break, you can fake it with continue and a flag, as long as your loop control guarantees termination. However, that complicates understanding the loop's behavior in terms of said control.
[1] https://batsov.com/articles/2024/01/16/learning-ocaml-verify...
[2] https://www.scala-lang.org/api/current/scala/annotation/tail...
And Scala I haven't looked at in like a decade, but thinking about it I am not surprised it has similar protections. I feel like Clojure also had a keyword to recur as tail but probably been 12 years since I used that language so my memory could be completely faulty
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'.
The recursion in TCO can be implemented with a jump but it requires an explicit stack frame and ultimately it must return a value through that stack frame. Basic loops have no such requirements which allows you to do things like jump from the middle of one loop into the middle of a different one.
Granted, this is rare, and rarely useful in practice, but it occasionally is and the burden of restructuring these forms into TCO would actually reduce their clarity and performance.
> They are literally equivalent.
They are /functionally/ equivalent. The literal differences are meaningful and have definite performance implications.
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.
I'm absolutely sure the people who think tail recursion is any way similar, in complexity, to a while loop have never attempted to teach someone how to program.
The explanation is just as simple translatable, even saving one the words like "while" or "until".
"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.
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.
I'd be very shocked if anyone past the age of 4 or 5 had never heard (and learned to understand) statements like "Wash your hands until they're clean" which is a conditional loop (wash your hands, check if they're still dirty, repeat if they are, stop otherwise). If a teen or adult learning to program has trouble with conditional loops, I'd be very very surprised. The translation into programming languages (syntax) may be a challenge, the correct logical expressions for their intent may be a challenge, but the concept should not be.
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:
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)
int a = 0
while (a != 10) {
a = a + 1
}
I don't think your middle example would be obvious to most people learning about functions until they've had quite some time to get their heads around what functions do, even with the context of the top piece of code.
That may be so, however I was taking issue with the idea that they couldn't possibly understand tail recursive functions first. Many (if not all) of the concepts that loops introduce also get introduced with functions (scoping, regions of code, stack parameters, jump return statements e.g. break/return). The programmers just may not have words for all of them with loops, however these concepts are usually explicitly covered with functions.
Loops are particularly useful in applications of batch processing or indirectly for parallelization (again, actually functions are more useful here), so they may learn them for a business use case first, but that doesn't mean they couldn't learn to master both functions and tail recursive variants first. As a sibling commenter pointed out, if you were to come from math's background you might even naturally prefer this construct.
Most people don't start out thinking like computers, so I think it's probably more important for a new student to understand how code describes a particular series of operations and then help them translate that into how a computer "thinks" about those operations.
Everyone who has followed a sequential list of instructions would strongly disagree.
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.
I rarely use them because I became tired of having to explain them to others, where I've never had to explain a simple while loop that accomplishes the same thing with, usually literally, a couple more lines of code.
From all of my experience, recursion is usually at the expense of clarity, and not needed.
I think it's related to the door memory effect [1]: you loose the sense of state when hopping into the function, even though it's itself.
[1] https://www.scientificamerican.com/article/why-walking-throu...
Fundamentally, the actual state of the program does not match the abstract state used when programming a recursive function. You are recursively solving subproblems, but when something goes wrong, it becomes very hard to reason about all the partial solutions within the whole problem.
Hmm. This is a real issue, for the simple case. If tail recursion is not optimized correctly then you end up with a bunch of stack frames, wasted memory...
I propose partially this is a tooling issue, not a fundamental problem with recursion. For tail recursion the frames could be optimized away and a virtual counter employed.
For more complex cases, I'd argue it matters less. Saving on stack frames is still preferable, however this can be acheived with judicious use of inlining. But the looping construct is worse here, as you cannot see prior invocations of the loop, and so have generally no idea of program execution without resorting to log tracing, while even the inlined recusion will provide some idea of the previous execution path.
I am tech lead and architect for large financial systems written in Java but have done a bunch of Common Lisp and Clojure projects in the past. I will still avoid any recursion and as people to remove recursion from their PRs unless it is absolutely best way to get readable and verifiable code.
As a developer your job is not to look for intellectual rewards when writing code and your job is not to find elegant solutions to problems (although frequently elegant solutions are the best ones). Your job is taking responsibility for the reliability, performance and future maintenance of whatever you create.
In my experience there is nothing worse than having bright engineers on a project who don't understand they are creating for other less bright engineers who will be working with it after the bright engineer gets bored with the project and moves on to another green field, rewarding task.
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.
Modern compilers optimise this for you, exactly as you said.
Back in the 80s compilers didn't do this. There really was a difference between the machine code emitted for a naive loop and a tail call loop.
A lot of advice to rewrite naive loops to do tail calls is based on that 1980s compiler behaviour, not on the optimising 2020s compiler behaviour.
for (int i = 0; i < 5; i++) {...}
vs
```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.
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.
for (i = 0; i < n; ++i)
for (i = n; i--; )
i = 0;
a: <body>
++i;
if (i < n)
goto a;
i = n;
b: --i;
<body>
if (i > 0)
goto b;
'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.
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...
void printManyStrsWithCommas(char *s[], int n /* trusted to be positive */)
{
int i = 0;
a: printOneStr(s[i]);
++i;
if (i < n) {
printOneStr(", ");
goto a;
}
}
- Somehow cram it into the loop expression with the comma operator. This is very limited because it is an expression. For example, what if 'printOneString' can err?
- Somehow use 'while(1)' with 'break'. It may even compile to the same code as with 'goto'. But why, then, we have to use an unbounded loop syntax with a clearly bounded sequence?
- Somehow add additional variables and tests and either lose efficiency or trust the compiler to lead us out.
With 'goto' the code does only what is necessary. What 'goto' does not do is that it does not immediately convey a clear idea that the code repeats certain steps.
1:
while (printOneStr(s[i]), ++i < n)
printOneStr(", ");
goto start;
do {
printOneStr(", ");
start:
printOneStr(s[i]);
++i;
} while (i < n);
do {
printOneStr(s[i]);
++i;
} while (i < n) {
printOneStr(", ");
}
for (i = 0; i < n; ++i);
for (i = n; i >= 0; --i);
for (i = 0; i < n; i++)
for (i = n; --i >= 0; )
for (i = n - 1; i >= 0; i--)
for (i = 0; i <= n-1; i++)
for (i = n-1; i >= 0; i--) for (i = -1; ++i != n; )
for (i = n; --i != -1; )Your reverse iteration would result in an out of bounds access as well as unsigned integer overflow which results in an infinite loop.