Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Subroutine calls in the ancient world, before computers had stacks or heaps

devblogs.microsoft.com

Post reply on HN
Print view View original

181–190 of 241 posts

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#181

Post by CyberDildonics »

sham1 wrote: post #165
CyberDildonics wrote: post #108

Earlier quoted context omitted.

so consuming stack frames is no reason not to use a recursive function. Saving stack memory isn't the point (even though a static array definitely does, because instead of multiple pointers and variables on the stack it only would have to store the node index of a tree). The point is that you can see the whole stack and all the data that you're using at one time in a debugger instead of trying switch through call sta…

Well, it's still recursion whether you're using the call stack or are using an explicit stack structure. You're still breaking the problem down into smaller subproblems inductively. I feel that people focus on the wrong things when talking about recursion, focusing on the aspect of having a function calling itself instead of the idea of having the problem solved by way of breaking it down into smaller problems.

it's still recursion whether you're using the call stack or are using an explicit stack structure

Recursion means defining something in terms of itself, so no, using a stack isn't recursion. The call stack of lots of different function calls in a normal program isn't called recursion either.

the idea of having the problem solved by way of breaking it down into smaller problems.

That's not recursion, that's organization, modularity and all sorts of other descriptions. Where did you get these ideas?

https://en.wikipedia.org/wiki/Recursion

Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#182

Post by jameshart »

klyrs wrote: post #83
munificent wrote: post #34

Earlier quoted context omitted.

This opinion is totally wild to me. Do you never work with tree data structures? I can't think of a non-trivial program I've written in the past two decades that didn't have some recursive tree traversal in it.

I think there are a lot of web devs here who never do anything more complicated than process data in a loop, and complexity analysis can be accomplished by counting indentation levels. When this viewpoint is applied with a wide brush to all programmers or the whole practice of programming, it results in some pretty spicy takes. On the other hand, recursion extremely expensive in some languages and Python has a notori…

There are developers in every field who only work on trivial problems. I bet there are scientific programmers and quants and ML developers who never need more than loops in their work. Loops are powerful tools.

But it does you no credit to dismiss ‘web devs’ as more likely to be doing that kind of work. You know the web is full of hierarchies, right? Domain names, the DOM, JSON structures, file directories? And ‘web devs’ build complicated sites with navigation hierarchies and taxonomies and comment threads and team based permissions and complex data visualizations - because web devs build applications that model real world businesses and data all the time, and those things are complex and hierarchical and fractal.

Web devs have plenty of uses for recursion. Don’t be dismissive.

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#183

Post by jameshart »

Joel_Mckay wrote: post #107
munificent wrote: post #96

Earlier quoted context omitted.

This is just bananas. I work in programming languages. I currently have open in my editor a code formatter that I maintain that uses at least half a dozen recursive algorithms to traverse syntax trees and other data structures. This program is used by almost every user of our language, invoked on every save, and probably executed billions of times a day. Recursion is fine .

"Recursion is fine [for your use-case]." In general it is naive, often dangerous, and an inefficient space/time trade-off. I have been writing software for several decades... does that make one less insightful or more biased? https://youtu.be/pmu5sRIizdw?feature=shared&t=31 =)

There’s an easy way to figure out if recursion is fine for your usecase

   def isRecursionOk(problem)
       for (subProblem in (breakDownIntoSubProblems(problem))
           if ! isRecursionOk(subProblem) return false
       return true

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#184

Post by JoeAltmaier »

wglb wrote: post #141
JoeAltmaier wrote: post #61

The old IMB 360 use a 'display' where you just chose a register by convention, pointed it at some memory then did your own linked list on call and return. In fact call was really jump-and-link(?) where you got the return address in a register. Anticipating that if your subroutine took more than a little code you'd just store it temporarily in your allocated 'display'. No push/pop at all! Unless you wanted to write it…

> In fact call was really jump-and-link(?) Yes, technically "BALR" for Branch and Link Register. (I knew a guy who had been a 360 assembly language programmer who called his consulting firm BALR consulting, referring to that instruction.) Interestingly, Gene Amdahl was asked why the 360 architecture didn't have a stack. "Too expensive" he said. I found this amusing at the time you could buy an 8085 for $5 retail quan…

The ol 360 used core memory if I recall. A stack would likely have meant, another whole cabinet on your computer room floor!

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#185

Post by munificent »

EnigmaFlare wrote: post #147
naasking wrote: post #120

Earlier quoted context omitted.

> Recursion in production code is bad news, because you can't control the depth of your call tree. Of course you can, if you wanted to , just like you can control the iteration count of a loop. It's not even hard. This is simply a non-issue. Some algorithms are much more naturally expressed recursively and writing the imperative equivalent with manual stack handling is just annoying. Stack growth is just something yo…

That sounds awfully complicated modifying a recursive algorithm to control the recursion depth. By that, I mean, if sometimes the data happens to be a very deep unbalanced tree that would cause a stack overflow with a naive recursive algorithm, you detect that situation and make it work. Isn't that much harder than just using your own stack (from a library/framework)?

> That sounds awfully complicated modifying a recursive algorithm to control the recursion depth.

An easy way to do it is to just pass a separate "depth" integer parameter into the recursive function. It then passes that +1 when it makes a recursive call. At the top of the function, if the depth is above your chosen limit, you bail out in some way instead of continuing to recurse.

> you detect that situation and make it work.

If you really do need to "make it work" for arbitrarily-deeply nested inputs, then you are actually better off using a heap-allocated stack instead of recursion.

But in most cases, a recursive implementation will only exceed the stack if the input is malicious or pathological and you can just fail in that case.

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#186

Post by taeric »

Tabular-Iceberg wrote: post #174
mr_toad wrote: post #144

Earlier quoted context omitted.

In ten years or so all the people who worked on machines without preemptive multitasking will be retired.

Cooperative multitasking is in fashion now, so we might get a whole new generation to take over. Or they’ll just cargo-cult everything and have no clue what’s happening under the hood.

To be fair, I doubt I fully understand what is going on fully under the hood. I usually bring this line up when folks lament that we don't have abstractions that fits the instruction set of the computer. Ignoring that many of the abstractions of the computer are orthogonal to isolated instructions, at this point. https://stackoverflow.com/questions/72423227/is-a-schedulabl... was a fun read as I was looking for something that would explore some of that for me.

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#187

Post by shadowgovt »

sgerenser wrote: post #176
shadowgovt wrote: post #28

Earlier quoted context omitted.

This succinctly describes how old MacOS allocated per-application resources. Each app had a minimum and preferred RAM requirement tagged to it. When launched, it would take up the whole preferred slot, unless that amount wasn't available in which case it'd take up less than preferred (and fail to launch if it couldn't get minimum). The system allocated the heap (and libraries, I think) at the bottom and the stack at…

Pretty sure even with virtual memory (which was actually added sometime in the System 7 days), you still could manually set the minimum and desired memory sizes for each app. Maybe it made less of a difference than it used to, but I still remember tweaking those values for certain apps (like trying to open a large file in Photoshop) even after MacOS 8 and 9 were out. MacOS X was a breath of fresh air by comparison.

You definitely could. I can't remember right now what effect that had, because the whole thing was running atop a virtual memory layer at that point... I can't recall if it was a lie (i.e. feature existed but had no effect) or if it had some effect on how long it'd be before an app started resorting to paging out RAM pages.

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#188

Post by Joel_Mckay »

jameshart wrote: post #182
klyrs wrote: post #83

Earlier quoted context omitted.

I think there are a lot of web devs here who never do anything more complicated than process data in a loop, and complexity analysis can be accomplished by counting indentation levels. When this viewpoint is applied with a wide brush to all programmers or the whole practice of programming, it results in some pretty spicy takes. On the other hand, recursion extremely expensive in some languages and Python has a notori…

There are developers in every field who only work on trivial problems. I bet there are scientific programmers and quants and ML developers who never need more than loops in their work. Loops are powerful tools. But it does you no credit to dismiss ‘web devs’ as more likely to be doing that kind of work. You know the web is full of hierarchies, right? Domain names, the DOM, JSON structures, file directories? And ‘web…

ML research can be super boring and hard to actually generalize/replicate, but recently became a lucrative field.

All commercial projects eventually become "work" when they are no longer fun, and you wouldn't show up unless paid.

You also can realize your NDA does not expire on some IP you wrote 15 years ago. lol =)

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#189

Post by hughdbrown »

jameshart wrote: post #183
Joel_Mckay wrote: post #107

Earlier quoted context omitted.

"Recursion is fine [for your use-case]." In general it is naive, often dangerous, and an inefficient space/time trade-off. I have been writing software for several decades... does that make one less insightful or more biased? https://youtu.be/pmu5sRIizdw?feature=shared&t=31 =)

There’s an easy way to figure out if recursion is fine for your usecase def isRecursionOk(problem) for (subProblem in (breakDownIntoSubProblems(problem)) if ! isRecursionOk(subProblem) return false return true

This code terminates only if all child-problems eventually are found not to have subproblems. So either it has infinite subproblems or it returns true. So recursion is good for a use case unless the problem decomposes into infinite subproblems, but in that case this test function never returns false.

Makes more sense to do it as breadth-first with only one return value:

   from collections import deque
   def isRecursionOk(problem):
       q = deque(problem)
       while q:
           problem = q.popleft()
           q.append(list(breakDownIntoSubProblems(problem)))
       return true

Re: Subroutine calls in the ancient world, before computers had stacks or heaps

#190

Post by Joel_Mckay »

jameshart wrote: post #183
Joel_Mckay wrote: post #107

Earlier quoted context omitted.

"Recursion is fine [for your use-case]." In general it is naive, often dangerous, and an inefficient space/time trade-off. I have been writing software for several decades... does that make one less insightful or more biased? https://youtu.be/pmu5sRIizdw?feature=shared&t=31 =)

There’s an easy way to figure out if recursion is fine for your usecase def isRecursionOk(problem) for (subProblem in (breakDownIntoSubProblems(problem)) if ! isRecursionOk(subProblem) return false return true

"kernel: Out of memory: Kill process 9163 (Insulin-pump-task) score 511 or sacrifice child"

There are safer hobbies available like snake juggling =)

Post reply on HN