6 ms·
This is actually (in the abstract) exactly how I’ve read and understood it in FP, with the necessary added note that when you TCO without recursion you lose his
by eyelidlessness 6y ago
This is actually (in the abstract) exactly how I’ve read and understood it in FP, with the necessary added note that when you TCO without recursion you lose history for eg stack traces and debuggers.
It’s also astonishing to me that people in a position to explain even moderately complex computing ideas continue to treat recursion as somehow hard to reason about. It’s calling a function. A function that calls itself is still just a function calling another function. Two mutually recursive functions calling each other are just two functions calling two other functions. That’s so much easier to follow than state changing in a single function call.
- kevin_thibedeau 6y agoA better mind bender is an async promise calling itself.
- eyelidlessness 6y agoWait, I’m confused. Like one promise/future/whatever monadish-eventually-fulfilled value referencing its own value? Or a polymorphic promise/etc referencing the same construct that created it to map its resolution into a new value?
- bhawks 6y agoI've seen people hung up on the calling yourself while defining yourself concept. Talking through that often highlighted a mental model of functions where they were sort of almost cut'n'pasting the other function into their code. Basically their model was too low level and the understanding of defining and calling functions were unnecessarily conjoined.
- eyelidlessness 6y agoI guess the way I’d try to help those people understand it is with the fiction I tell myself (which I alluded to upthread): I mentally model the “outer” function and the “inner” recursion as referencing different functions that have the same signature and the same body. The definition is concrete and self sufficient, it just dependency-injects a contract in its own image to delegate future work to. It’s even easy to literally implement that way in languages with first class functions, because you can just bind fn a to b and call b within a.
- FeepingCreature 6y ago> It’s also astonishing to me that people in a position to explain even moderately complex computing ideas continue to treat recursion as somehow hard to reason about. It’s calling a function. Calling a function can be easily, and incorrectly, modeled by representing the arguments as variables stored at a fixed position in memory. (As function calls used to work.) Once you introduce recursion, this model breaks down and you are forced to think in terms of activation records/stackframes. Probably those people learnt function calls in the former way first, meaning that recursion represented a conceptual leap for them.
- eyelidlessness 6y agoMaybe it’s more of me showing my naivety but I still think of a recursive function call as bindings and computation. My mental model is f(x) -> f(y(x)) = f(x) -> g(x), where g is a function wrapping the body of f. It’s surely not what the compiler does, but it makes thinking about recursion no more complicated than thinking about any old function. Then the only thing I need to think about beyond that is “does my environment support TCO, or am I certain my data fits in the call stack?”
- manwe150 6y agoConsider that some processors were too small to fit a stack. Some languages (notably BASIC), only had what you might call 'static' variables (to use the C name), so when you recursed into them, the variables would be shared across all calls to that function.
- eyelidlessness 6y agoAnd that’s a good case for supporting recursion but eliminating branching! You can goto and rebind to your heart’s content as long as you don’t have to back out of a condition
- mcguire 6y agoOr expressions.
- brundolf 6y agoThe human intuition starts out naturally oriented around cause and effect, linear timelines of events, and state change over time, because that's how we've evolved to conceptualize the physical world around us. When you're designing large systems this model doesn't scale, but it's absolutely the most intuitive on the small-scale. This is why languages like Python and Basic are so accessible for newcomers.
- eyelidlessness 6y agoI’d say that you can model conceptually the same way with a time traveling debugger and get really comfortable. A recusing function is just an event loop where you know how the data is being mutated.
- Scarbutt 6y agoyou lose history for eg stack traces and debuggers. I remember javascriptcore solving this issue by using a "shadow stack"
- aste-risk 6y agohow do modern compilers like clang/gcc handle the debug info while still doing TCO? Any description or links appreciated.
- millstone 6y agoThey don't. The whole point of TCO is to discard stack frames, which means local variables cannot be recovered. Optimize or debug, pick one.
- eyelidlessness 6y agoWell, the point of TCO is to discard stack pressure. Discarding stack frames is just an unfortunate side effect.
- manwe150 6y agoMy recollection (without references) is that they can do some amount of guess work. They might see the stack says A->C, but can see the code of A actually calls B, so logically it must have been A->B->C at some point. Or you can use the rr-debugger, and just return back to the exact sequence of calls, and reject the need to pick between optimization and debugging :D
- Geminidog 6y agoclang will actually optimize non tail recursive function as well. Check out the code in this question. It will not stack overflow. https://stackoverflow.com/questions/65225761/trying-to-deliberately-induce-memory-leak-and-stackoverflow-but-not-seeing-memor?noredirect=1#comment115313850_65225761 https://stackoverflow.com/questions/65225761/trying-to-delib...
- Geminidog 6y ago>It’s also astonishing to me that people in a position to explain even moderately complex computing ideas continue to treat recursion as somehow hard to reason about. This is because you don't understand humans. Which is more clear to you? repeat special-task 5 times. (do special-task n times) = (do special-task n - 1 times) (do special-task 0 times) = Don't do anything. do special-task 5 times. Clearly when we communicate with others using regular language we use a repeat keyword rather then recursive grammar. No natural language on the face of the earth ever communicates the concept of repetition via recursion* There's always some keyword or number for repeating something. *(not 100% sure on this, HNers, prove me wrong if possible, I'm open to being wrong).
- lmm 6y agoI don't think anyone's opposed to having a function for "repeat this thing 5 times". But if you did see a function that called itself, why would that be any more confusing than seeing a function that calls another function? That's all it is.
- rcxdude 6y agoI think it's because for beginners it's hard to see why it would be useful (or not just turn into infinite regression). Proof by induction is often similarly difficult for maths students to grasp. The idea of solving a problem by breaking it down into smaller problems until each part of it becomes trivial is not something which comes naturally to most people, it's a learned and ingrained habit in those who have been taught it and used it.
- eyelidlessness 6y ago> I think it's because for beginners it's hard to see why it would be useful (or not just turn into infinite regression). And that, in turn, I think is because most beginners are first introduced to mutation and statements and all kinds of “do” stuff instead of trivial algebra with trivial types. If the core primitives at the start are: 1. Computation producing output 2. Computation of input producing output 3. Wrapping #2 in a function I could see introducing recursion in an easily understandable way on day one.
- avhon1 6y agoIMO, the two challenging parts of recursion are: First, realizing that you can have separate instances of functions at the same time -- different stack frames. Making the mental leap from "the content of x in function f" to "the content of x in f(0), and also the content of x in f(1)" is a leap of abstraction, but not necessarily a tremendous one. Second, mentally modeling recursion when it gets complicated. Simple recursive cases are easy to model in your head, because either there is little state to keep track of, or because you can extrapolate the pattern between function calls, mentally compressing the state of the whole call tree. Tail-call optimization, for example, is really easy to mentally model because you only have to keep track of the state of one function's variables at a time -- unless you start passing continuations or thunks into your function calls, in which case you're carrying a stack of unlimited complexity into each function call. It's still just a function call, with the same number and types of arguments, but now one or more of those arguments contains turing-complete, recursive programs of unlimited complexity. This similar to the worst-case mentally-complicated recursion without TCO, where you can build a complex graph of function calls, scopes, shared data accesses, and mutated copies of what used to be the same data, that can all be present at once, and where you might need to keep track of all of them in order to track down and understand something that you need to understand. You can, of course, build similarly tangled-up structures in a purely-iterative manner, but the upside is that the complexity will be confined to the data state -- there will be no call tree to mentally model, and no need to track variable scope. --- Shorter version: if the efficiency and elegance of recursion (with appropriate compiler/runtime optimizations, like TCO) is like zip compression for your mental model of code complexity, then there exist recursive-program equivalents of zip bombs. --- Even shorter version: recursion itself isn't hard to reason about, but recursive programs can be very hard to reason about