11 ms·
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
by diffxx 2y 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.
- Akronymus 2y agoIMO 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 2y agoHow do you know it’s easier?
- bowsamic 2y agoThere 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 2y agoIt'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.
- knome 2y ago>you'll quickly have to introduce routines, modules, objects of whatever to have some control over side effects 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.
- zogrodea 2y agoI think, because of the mention about controlling mutability/side-effects, "object" in that post means OOP-style objects which mutable state. It's not an issue with immutable objects/structs (or I guess "records" which is the term I'm used to with functional languages).
- knome 2y agofunctional languages still have to deal with storing and manipulating changing value and state, and it is still often advantageous to hide the complexities of that storage and manipulation behind simple interfaces throughout the codebase, using opaque values with helper functions to manipulate them. 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.
- zogrodea 2y agoI just use simple tail-recursion in an event loop to help manage state. 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.
- xigoi 2y agoFunctional programming is not just about monads. I bet it’s easier to explain numbers.map(x => x * x) than let result = []; for (let i = 0; i < numbers.length; ++i) { result.push(numbers[i] * numbers[i]); }
- bowsamic 2y agoPerhaps, but this is a somewhat contrived example. No side effects, no complicated data structures, etc. Sure, in the specific case of "parallelised" operations on an array it is simple. But anything more complicated and suddenly you're in a bad situation. 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.
- xigoi 2y agonumbers.map(x => { console.log(x); return x * x; }) Still easier to understand than the for loop.
- bowsamic 2y agoOkay but now this is just imperative lol, it's no longer functional at all, since your function is now just a sequence of instructions, i.e. it's a procedure rather than a pure function. You've just proved my point
- xigoi 2y agoIt’s a mix of functional and imperative style. Most functional languages (other than Haskell) allow you to easily write code like this.
- Iceland_jack 2y agoI write this in my Haskell day job every day.
- 2y ago
- LtWorf 2y agoHe likes it more.
- Akronymus 2y agoBecause I know what opinion I have.
- demi56 2y agoYou don’t have to worry people have been saying this for more than a decade now and I see no action about it
- russdill 2y agoIf you're teaching someone c, tail recursion is just handing them another gun to shoot themselves in the foot with.
- dist-epoch 2y agoThat'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 2y agoC 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.
- paulddraper 2y agoRecursion 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 2y agoHow 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 2y ago> 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.
- Jtsummers 2y 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.
- User23 2y agoBreak 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 2y agoTrue, 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 2y agoIf 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 2y agoI 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 2y agoBut 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 2y agoC compilers may not optimize tail recursion properly, so it's not necessarily safe to teach C programmers to do that.
- speed_spread 2y agoTail 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 2y agoWithout 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.
- nequo 2y agoOCaml[1] and Scala[2] have had this too. [1] https://batsov.com/articles/2024/01/16/learning-ocaml-verifying-tail-recursion-with-tailcall/ https://batsov.com/articles/2024/01/16/learning-ocaml-verify... [2] https://www.scala-lang.org/api/current/scala/annotation/tailrec.html https://www.scala-lang.org/api/current/scala/annotation/tail...
- runevault 2y agoI was pretty sure OCaml had it but I'm less than a newbie with it (touched dune a little bit and built tiny apps but nothing real) so didn't want to bring up something I wasn't sure about. 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
- akira2501 2y 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'.
- WJW 2y agoDo 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 2y agoDepends 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.
- akira2501 2y ago> 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 2y agoI don't think many people consider tail calls more intuitive than a while loop. The opposite is more obvious.
- aleph_minus_one 2y 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.
- gabrielhidasy 2y agoWhile 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()'
- nomel 2y agoI've successfully explained a while loop to many a child, and adult, with no experience in programming, within about 5 minutes. 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.
- zelphirkalt 2y agoadd salt; not salty enough?; do same again! The explanation is just as simple translatable, even saving one the words like "while" or "until".
- kimixa 2y agoI 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.
- onetimeuse92304 2y agoHow 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 2y agoMost 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 2y ago> 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.
- zelphirkalt 2y agoI happen to know (due to job), that many adults have problems grasping for loops (in Python) when learning programming. It is one of the main points where problems arise in programming introductions. It may all depend on how it is explained for what person, as different people understand different explanations better than others. Or it may be syntax related. Or that people for the first time fathom how they can make the computer do things in such a time saving manner. Who knows.
- smaudet 2y 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.
- deleted 2y ago[deleted]
- jameshart 2y agoIf 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 2y agoIn 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.
- guntars 2y agoHow can tail recursion have better performance if they both compile to the same machine instruction - a conditional jump?
- suprjami 2y agoBecause it results in a tail call and you don't have to build a new stack frame.
- guntars 2y agoA loop didn’t have to build a stack frame in the first place. Once the optimizer has done it’s job, both the TCO optimized tail call and a basic loop will have the same instructions, hence the performance will be the same.
- suprjami 2y agoYes, that's exactly the point I am making. 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.
- CyberDildonics 2y agoUsing 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 2y agoLoops are more intuitive for similar reasons that ∑ and ∏ are more intuitive than the equivalent recursive formulation.
- dboreham 2y agoPerhaps they just want to write programs that work without becoming confused?
- zogrodea 2y agoI 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++) {...} 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.
- ummonk 2y agoAren’t you leaving out the initialization in your recursive example though?
- zogrodea 2y agoYou're right. I didn't notice that, but I guess the initialisation would be the caller function's responsibility or there would be a wrapper function with a default initialisation value (maybe with the recursive example nested inside the wrapper).
- nomel 2y agoWith 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_Edoshin 2y agoLoops 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.
- trealira 2y agoI 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 https://cs.stanford.edu/%7Eknuth/fasc5b.ps.gz [1]: https://stackoverflow.com/questions/78614303/can-knuths-algorithm-b-be-written-without-goto-statements-or-recursion https://stackoverflow.com/questions/78614303/can-knuths-algo...
- Mikhail_Edoshin 2y agoThis is absolutely true. Even advanced loop syntax implies nesting; but control flow in general is not hierarchical. Simple loop syntax in C is even more limited, because it uses a fixed place for the loop condition test: either at the start or at the end of the body. As a result if we need to do something, then test the condition, then do something extra, we are stuck. For example, we may want to print a list of stings separated with commas: void printManyStrsWithCommas(char *s[], int n /* trusted to be positive */) { int i = 0; a: printOneStr(s[i]); ++i; if (i < n) { printOneStr(", "); goto a; } } Here the loop condition is 'i < n', but when it is true, we need to do one more thing (print a comma) before resuming the loop. If we are to stick with non-'goto' syntax we have the following options: - 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.