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

191–200 of 241 posts

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

#191

Post by klyrs »

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…

I spent several years in the web dev trenches; my opinion is not an out of hand dismissal.

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

#192

Post by DiggyJohnson »

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…

Are you arguing against the notion that some branches of programming are going to have to handle complex data structures more often than others?

It seems like you're just trying to smooth over a relatively inoffensive point. I don't think most web developers would disagree with GP. You're the one being rude and dismissive of the person you're replying to, frankly.

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

#193

Post by Joel_Mckay »

CyberDildonics wrote: post #181
sham1 wrote: post #165

Earlier quoted context omitted.

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 organizati…

Except on most modern large CPUs on each recursive call the entire processor register state including program counter offset etc. are pushed onto the stack.

Seems very inefficient for the risks it brings.

I think we all agree this is still very interesting to consider. =)

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

#194

Post by Narishma »

froh wrote: post #164
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.

wait what? you're right! 386 came 1985, 45 years later is 2030 now I feel old

Why the 386? You could do preemptive multitasking on a 286 or even an 8088.

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

#195

Post by 082349872349872 »

blueflow wrote: post #172
082349872349872 wrote: post #80

Earlier quoted context omitted.

I once wrote a 16-bit assembler as a recursive function, which emitted code and fixed data on the way down and patched in relative offsets on the way back up. In principle, one might worry about blowing the stack, but as the sole purpose of this function was to assemble at most a half-k boot sector, in practice they fit.

Im curious about that. At which point did you do the recursion? "Assemble everything after this line and tell me offset of symbol X when you are done" ?

Yes. (well: tell me the entire symtab when you are done, but you probably could've guessed that)

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

#196

Post by kragen »

082349872349872 wrote: post #80
layer8 wrote: post #73

Earlier quoted context omitted.

In particular input to assemblers, compilers, and interpreters.

I once wrote a 16-bit assembler as a recursive function, which emitted code and fixed data on the way down and patched in relative offsets on the way back up. In principle, one might worry about blowing the stack, but as the sole purpose of this function was to assemble at most a half-k boot sector, in practice they fit.

i seem to recall you wrote a sort of 16-bit assembler in machine code consisting entirely of printable ascii, except for a couple of places where it had to use printable ascii instructions to modify itself to add instructions like int 21 that couldn't be done that way. but that was a different one, wasn't it?

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

#197

Post by User23 »

derefr wrote: post #149
shadowgovt wrote: post #98

Earlier quoted context omitted.

emacs still does this IIUC. The beating heart of the emacs edit model is a "gap buffer" at the cursor. There's a neat compare-and-contrast someone did awhile back on the gap buffer approach vs. the other approach often taken for code IDEs ("ropes"). The tl;dr is that gap buffers are actually really performant for a lot of cases except for having to edit at a lot of randomly-chosen cursor points far apart from each ot…

> except for having to edit at a lot of randomly-chosen cursor points far apart from each other (but how often is that your use case?) I use Sublime, and pretty often I do a "Find All" for some term; then Multiselect (Cmd+L); then select from cursor (Shift+RightArrow); and then type something. Which is essentially "editing at a lot of randomly [or at least arbitrarily]-chosen cursor points." That, and IIRC Sublime ac…

I’ve never noticed any perceptible latency using iedit[1] in Emacs, which does what it sounds to me like you are describing.

It does suggest a possible multigap buffer structure though for efficiently doing simultaneous edits of distant locations in very large files. In that case though I’d probably be iediting a small wgrep[2] buffer anyhow so it might not really matter.

[1] https://github.com/victorhge/iedit

[2] https://github.com/mhayashi1120/Emacs-wgrep

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

#198

Post by agumonkey »

CyberDildonics wrote: post #114
agumonkey wrote: post #93

Earlier quoted context omitted.

To my poor eyes it's creating self sustaining computing blocks. You could recurse using an explicit stack or use tiny function that will thread themselves as see fit. In a way it's more encapsulating than languages preaching encapsulation.

Are you saying recursion creates "self sustaining computing blocks" ? What does that mean and how does it do it? that will thread themselves as see fit.* What does this mean? In a way it's more encapsulating than languages preaching encapsulation. Recursion does this? Are you talking about not depending on a stack structure in this specific instance or something else?

I'm trying to make my ideas clearer but I'm not sure it will be :)

> Are you talking about not depending on a stack structure in this specific instance or something else?

- using recursion involves functions as basic block of logic, that represent sub-parts of a domain

- often creates finite set of self dependent functions

- all you do is call and pass other functions, that will call each others

> In a way it's more encapsulating than languages preaching encapsulation.

If you consider `map` or `fold` these create opaque functional processes that operate very automatically. It's all inductive logic at work to me. On the other hand in OO you needed (until very recently) to create iterators and empty structure to modify step by step.

> Are you talking about not depending on a stack structure in this specific instance or something else?

PEG parsing where the monadic flavor replaces an externally managed stack

ps: maybe i'm still too high on lambda calc

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

#199

Post by nerpderp82 »

Joel_Mckay wrote: post #57
nerpderp82 wrote: post #44

Earlier quoted context omitted.

Recursion is like an inductive proof, you can show it is correct and it normally fits on half of a small screen.

There is an argument that all recursive proofs can be made iterative due to isomorphism. You are not lazy enough to be a good programmer yet. ;-)

Yeah, but that is error prone and more complex. A compiler can make those same transformations. I'd argue that the properly lazy programmer is the one using recursion. To get even lazier, one should move into relational algebra.

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

#200

Post by snowAbstraction »

bitwize wrote: post #162
howerj wrote: post #15

I wrote a Forth interpreter for a SUBLEQ machine ( https://github.com/howerj/subleq ), and for a bit-serial machine ( https://github.com/howerj/bit-serial ), both of which do not have a function call stack which is a requirement of Forth. SUBLEQ also does not allow indirect loading and stores as well and requires self-modifying code to do anything non-trivial. The approach I took for both machines was to build a virt…

> EDIT: There were some BASIC interpreters which did this as well, implementing a VM and then targetting that instead. The TI-99/4A had 256 bytes (128 words) of main, CPU-accessible RAM. Most of the base system's memory was video RAM, accessible by a relatively cumbersome process of poking and peeking registers on the system's video chip. The video chip maintained an autoincrementing current memory pointer, so succes…

Interesting. For other readers, this is about an early 80s Texas Instruments computer and not a graphing calculator as I first thought.
Post reply on HN