[HN Gopher] Misconceptions about loops in C
___________________________________________________________________
Misconceptions about loops in C
Author : matt_d
Score : 99 points
Date : 2024-06-27 17:46 UTC (5 hours ago)
(HTM) web link (dl.acm.org)
(TXT) w3m dump (dl.acm.org)
| Dylan16807 wrote:
| 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 wrote:
| 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.
| Akronymus wrote:
| 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 wrote:
| How do you know it's easier?
| bowsamic wrote:
| There seems to be this weird notion going around that the
| only reason imperative languages seem easier to people is
| because they're taught them first, and that if we teach
| Haskell or Scheme to everyone first then they would find
| imperative programming unintuitive. I honestly think it's a
| load of rubbish. The fact that humans easily understand "a
| list of instructions executed one after the other" over
| monads and tail recursion is not because they are taught C
| first, but because that's just the basic instructions we
| communicate actions with. Recipes, directions, instructions
| for how to tie your shoe laces, etc. They're all imperative
| agumonkey wrote:
| It's a complex topic. The thing is that sequential
| mutable state doesn't scale, and you'll quickly have to
| introduce routines, modules, objects of whatever to have
| some control over side effects. The natural aspect of a
| list of instruction is exhilarating for many but is also
| rope to hang your self because you won't try to separate
| concepts and scopes since everything is accessible. So
| much stuff just doesn't happen when you don't use this
| paradigm. Instead of drowning in state variable
| improperly synchronised, you suddenly rise above and
| start rewriting trees.
| LtWorf wrote:
| He likes it more.
| Akronymus wrote:
| Because I know what opinion I have.
| russdill wrote:
| If you're teaching someone c, tail recursion is just handing
| them another gun to shoot themselves in the foot with.
| dist-epoch wrote:
| 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.
| svachalek wrote:
| 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.
| tedunangst wrote:
| This is what happens when we eliminate shop class. Sand
| this table leg. Good. Now do that three more times. Kids
| used to know loops before they ever touched a computer.
| klyrs wrote:
| Exactly. Go make a table with 4 legs and also every leg
| has 4 legs. Now you get recursion and a very steady
| table.
|
| You were a kid in shop class. Now you want your kids to
| take shop class. Because, recursion.
| adwn wrote:
| > _Go make a table with 4 legs and also every leg has 4
| legs._
|
| 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.
| nequo wrote:
| How is it not recursion? def spawn():
| take_shop_class() return spawn()
| klyrs wrote:
| The first paragraph was more of a parody of your just-so
| argument than point per se; but the second paragraph is
| literally recursion.
| paulddraper wrote:
| Recursion is more beautiful.
|
| But take a newbie, and "do this 3 times" in a loop is far
| more clear than the recursive equivalent.
| pineapple_sauce wrote:
| How do you measure beauty? You can't: "beauty" is
| subjective. And even if you try e.g. count the times you
| use recursion vs. iteration: that metric is subjective
| and not grounded in reality.
|
| 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).
| mbivert wrote:
| > How do you measure beauty? You can't: "beauty" is
| subjective
|
| 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.
| mbivert wrote:
| Iteration is more natural for most people than recursion.
| There are a few aliens for whom recursion is more natural,
| but iteration matches more closely daily life.
| Gibbon1 wrote:
| People that see programming as math get really excited
| about recursion.
|
| Everyone else doesn't care, shouldn't care.
| timeinput wrote:
| There's this summation notation that these people who see
| programming as math and get excited about recursion
| forget about too.
| mbivert wrote:
| I think recursion is just another tool in the toolbox:
| sometimes, some solutions are easier to think of
| recursively, and so it makes sense to use it, at least
| for the first prototype.
|
| But yeah, using it systematically (in a non-functional
| language) is unwise.
| eigenket wrote:
| I think its fairly clear that loops are more natural and
| obvious for most people for most tasks.
|
| 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.
| playingalong wrote:
| Rinse and repeat.
| KineticLensman wrote:
| > for example you get things which are basically loops in
| knitting patterns
|
| 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
| warkdarrior wrote:
| You guys should write these crochet patterns in
| continuation passing style!
| photochemsyn wrote:
| 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.
| chongli wrote:
| 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.
| atorodius wrote:
| I don't think this is true at all. I remember vividly when
| I learned about loops (,,oh it is just the statement
| multiple times") vs learning recursion (spending 3d on an
| assignment from uni and scratching my head and not getting
| how the heck this makes sense)
| slashdave wrote:
| So natural, yet the specific example you provide is broken
| AlotOfReading wrote:
| I'm surprised you consider that construction "simple".
| Recursive relationships like that are used for brain
| teasers and even a famously absurd joke in Spaceballs.
| 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.
|
| In fact, standard English tends to avoid recursive
| relationships with specialized kinship terms based on
| ordinals like first cousins, first cousins once removed,
| great-, and so on.
| chongli wrote:
| _I 'm surprised you consider that construction "simple"._
|
| 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.
| com2kid wrote:
| > 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_.
| com2kid wrote:
| 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.
| Jtsummers wrote:
| > 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.
| User23 wrote:
| 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.
| Jtsummers wrote:
| True, but the person I responded to wants multiple exits in
| tail-recursive functions which introduces the same
| complications as multiple exits in loops, non-recursive
| functions, and non-tail-recursive functions.
| titzer wrote:
| If you're trying to do control flow analysis on an AST,
| you're going to have a bad time. The article is a blinking
| red advertisement to not try to analyze loops at the source
| level.
| jcranmer wrote:
| I did spend about half the article going "... why are you
| trying to do analysis based on the AST instead of using a
| control-flow-graph-based IR?"
| ape4 wrote:
| But for a programmer break is wonderful. Maybe you have a
| loop condition for a normal exit and use break if an
| unusual condition (eg EOF) occurs.
| KerrAvon wrote:
| C compilers may not optimize tail recursion properly, so it's
| not necessarily safe to teach C programmers to do that.
| speed_spread wrote:
| 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.
| runevault wrote:
| 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.
| akira2501 wrote:
| > 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'.
| WJW wrote:
| 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.
| murderfs wrote:
| Depends on the assembly and depends on the loop. x86 has
| multiple instructions that hint at knowing about loops:
| e.g. the `loop` instruction that does a decrement and jump,
| and the rep prefixes that let you implement memcpyish
| functions in a single instruction.
| WJW wrote:
| Fair point. The higher level languages have been leaking
| back down into assembly.
| orhmeh09 wrote:
| For a very long time, even PDP7, on which C was created,
| with ISZ - Increment the memory operand and Skip next
| instruction if result is Zero.
| akira2501 wrote:
| > And recursion is basically a jump too, even more so if
| you manually do the TCO.
|
| 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.
| duped wrote:
| I don't think many people consider tail calls more intuitive
| than a while loop. The opposite is more obvious.
| aleph_minus_one wrote:
| > 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.
| gabrielhidasy wrote:
| While the formal concept of applying a function that calls
| itself may be more familiar to someone trained in classic
| mathematics, everyone is somewhat familiar with while
| loops, from basic life things like 'while hungry, eat' or
| 'salt to taste -> while (not_salty_enough()): add_salt()'
| onetimeuse92304 wrote:
| 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 wrote:
| 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.
| Jtsummers wrote:
| > Conditional loops are a (relatively) big jump.
|
| 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.
| smaudet wrote:
| > 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.
| dajtxx wrote:
| I think most people learn about loops before they've
| learned about functions because your first example maps
| obviously to your last.
|
| 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.
| Farmadupe wrote:
| 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.
| dajtxx wrote:
| I don't agree with your last statement. I've been
| programming forever, and I understand recursion, and I use
| it, but I never equate it with loops in my mind (unless I'm
| deliberately thinking that way, like now) and I always find
| it more difficult to think about than loops.
| jameshart wrote:
| 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.
| suprjami wrote:
| 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.
| CyberDildonics wrote:
| 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.
| pizlonator wrote:
| 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.
| almostgotcaught wrote:
| 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.
| pizlonator wrote:
| 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.
| almostgotcaught wrote:
| > folks who practice the craft so in that sense it is not
| research
|
| 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.
| pizlonator wrote:
| There are lots of well written detailed articles that
| don't call themselves research.
| almostgotcaught wrote:
| There are also lots of horribly written, superficial
| articles that _do_ call themselves research. Hence my
| overarching point: let 's quit with the dog and pony
| show.
|
| 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.
| pizlonator wrote:
| I don't put any stock in PLDI.
|
| 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.
| almostgotcaught wrote:
| > 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.
|
| 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.
| pizlonator wrote:
| I'm not on the PLDI review committee. Haven't ever been.
| almostgotcaught wrote:
| > i.e. encourage them to relax their requirements
| marmaduke wrote:
| Yes, amen
|
| There's not having to exaggerate and moreover there's value
| in rehashing known but tricky stuff
| slashdave wrote:
| I wouldn't call this a research paper. It doesn't include any
| research.
| almostgotcaught wrote:
| PLDI disagrees with you. I generally don't care about
| institutional pedigree but I think in this case I'll defer
| to them over u/slashdave.
| deredede wrote:
| This is not published at PLDI but at the co-located SOAP
| workshop.
| almostgotcaught wrote:
| Literally who cares? It's again the same thing: some kind
| of weird elitism about what qualifies as real research
| and who qualifies it. It's so simple in my mind: people
| did good work and they're willing to share it with the
| world without much in return (just a venue and 30 minutes
| to talk about it). Cool great I'm all for it no matter
| whomever/wherever/whatever. There is exactly zero
| scarcity here anymore that necessitates ranking anything
| at all.
| slashdave wrote:
| I didn't say it wasn't good work, I just said it wasn't
| research
| deredede wrote:
| I don't care where papers are published (in fact I mostly
| agree with you, I think that the idea that research needs
| to be novel to everyone currently in the field is harmful
| and leads to gate-keeping, self-censorship and
| unpublished folklore). I am merely pointing out that
| appealing to the authority of PLDI as the premier PL
| research conference to qualify the paper as research does
| not work since PLDI did not publish it.
| almostgotcaught wrote:
| > I am merely pointing out that appealing to the
| authority of PLDI as the premier PL research conference
| to qualify the paper as research
|
| I wasn't actually - I was pointing out the contradiction
| in supporting gatekeeping and then the second-guessing
| the gatekeepers.
| IshKebab wrote:
| 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- wrote:
| For the first time, I used a c style loop in a bash script today.
| What a coincidence
| ssahoo wrote:
| 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 wrote:
| 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.
| tgol wrote:
| ### Summary of "Misconceptions about Loops in C" by ChatGPT ;)
|
| #### Authors: - Martin Brain, City, University of London - Mahdi
| Malkawi, City, University of London
|
| #### Abstract: The paper addresses the key challenges in loop
| analysis within static analysis tools, particularly focusing on
| the misconceptions and rare edge cases that lead to significant
| algorithmic bugs. The authors present a collection of examples
| and challenges to aid in understanding and improving loop
| analysis.
|
| #### Introduction: The introduction discusses the challenges
| developers face as static analysis tools transition from academic
| prototypes to production-ready systems. It highlights the
| importance of early bug detection to prevent complex and time-
| consuming bugs, emphasizing that correctness bugs in core
| algorithms are particularly difficult to address and often emerge
| late in the development process. The paper aims to address bugs
| stemming from incorrect assumptions about loops and their
| structure, drawing on experiences with tools like CBMC, SPARK,
| 2LS, and goto-analyzer[(7:1+source)] [(7:2+source)] .
|
| #### Section 2: What Are Loops? This section reviews various
| definitions of loops across different program representations,
| using examples to highlight their differences. It explains
| classical features of loops, such as loop conditions and bodies,
| and discusses alternative representations like instruction lists
| and control flow graphs (CFGs). The section emphasizes that loop
| definitions can vary significantly and are not always equivalent,
| which can lead to misunderstandings and bugs when combining
| different tools[(7:0+source)] [(7:5+source)] [(7:6+source)] .
|
| #### Section 3: Common Mistakes About Loop Structure This section
| categorizes common mistakes into four main areas: 1. *Entering
| Loops*: Misunderstandings about how loops are initiated. 2.
| *Inside Loops*: Errors related to the loop body and its
| execution. 3. *Exiting Loops*: Incorrect assumptions about loop
| termination. 4. *Simplification, Preprocessing, and
| Optimization*: Issues arising from various transformations and
| optimizations applied to loops[(7:2+source)] [(7:3+source)] .
|
| #### Section 4: Recommendations The authors provide several
| recommendations for improving loop analysis: 1. *Design for
| General Cases*: Ensure that the loop analysis handles the most
| general cases. 2. *Explicit Case Handling*: Clearly document and
| handle specific cases, particularly edge cases. 3. *Translation
| Handling*: Properly manage the translation between different loop
| representations. 4. *Systematic Testing*: Employ careful and
| systematic testing, using a provided test suite to check for edge
| cases and ensure the reliability of the static analysis
| tools[(7:4+source)] [(7:5+source)] .
|
| #### Conclusion The paper concludes by emphasizing the importance
| of understanding the diverse and complex nature of loops in
| programming to avoid significant bugs in static analysis tools.
| It also acknowledges the support from an Amazon Research Award
| and contributions from various individuals who provided input and
| feedback[(7:3+source)] [(7:4+source)] .
|
| ### Recommendations for Further Reading: - For detailed examples
| and test cases, refer to the provided test suite linked in the
| recommendations section of the paper. - Explore referenced tools
| and studies like CBMC, SPARK, and 2LS for practical insights into
| loop analysis challenges.
| dang wrote:
| Please don't do this here.
| WalterBright wrote:
| 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.
___________________________________________________________________
(page generated 2024-06-27 23:01 UTC)