Subroutine calls in the ancient world, before computers had stacks or heaps
devblogs.microsoft.com
devblogs.microsoft.com
While seemingly obsolete, there are a ton of pre-heap / pre-stack algorithms for dynamically changing arrays or other data structures.
The book also builds up to garbage collection and how to implements Lisp-lists. The kind of encyclopedic knowledge you'd expect from Knuth.
-------
One of my favorites is how to have two Arrays dynamically take up one space.
Have one array grow normally from location#0, and the second array grow backwards from location#End.
Now both arrays take up the statically allocated space efficiently sharing.
This can be extended to an arbitrary number of arrays, but at that point you might as well use Malloc and Realloc. Or at least, the techniques therein are really close to a malloc-like routine IMO.
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 other (but how often is that your use case?).
https://coredumped.dev/2023/08/09/text-showdown-gap-buffers-...
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 actually does its "Find and Replace All" operation, as essentially this same multicursor-select-and-type operation internally. (If you have a large-enough buffer open, you can see it gradually doing it!)
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.
I’m sure there’s some magic key combo in emacs and/or vim to do it, too.
The stack in most ISAs and ABIs grows down from a high address, allowing this trick to be used to divide memory flexibly between heap and stack in single-threaded small-memory systems.
The system allocated the heap (and libraries, I think) at the bottom and the stack at the top of that physical-RAM slice, and off you went.
I believe around system 8 they added a virtualization layer that started to obviate the need for that approach (and of course by the time of MacOSX they were using paged memory like everyone else was and so such fancy tap-dancing was no longer needed). But it's fun to think about the era where this "one weird trick" from Art of Computer Programming was how we allocated RAM for multiple concurrent applications.
Fun fact: Itanium had two stacks, one for manual push/pop and another for cycling through the register file. One stack grew upward, another grew downward. A fascinating architecture, though it never delivered the promised performance.
It wouldn't surprise me if it was a direct inspiration, since their docs cite TAOCP for the btree structure itself.
These are not as obsolete as they might seem to many. In some environments you might still be very restricted and want to avoid all dynamic allocation which could force you to use these types of algorithm so you can work in-place in a static memory block.
IIRC, the first edition of the classic K&R C book, The C Programming Language, had an example of creating a memory allocator and using it.
How recursion got into programming: intrigue, betrayal, and advanced semantics - https://news.ycombinator.com/item?id=33123916 - Oct 2022 (8 comments)
How Recursion Got into Programming (2014) - https://news.ycombinator.com/item?id=23061881 - May 2020 (47 comments)
How recursion got into Algol 60: a comedy of errors - https://news.ycombinator.com/item?id=10131664 - Aug 2015 (124 comments)
How recursion got into programming: a comedy of errors - https://news.ycombinator.com/item?id=8073361 - July 2014 (108 comments)
I would imagine that other compilers took a similar approach which wasn't mentioned.
EDIT: There were some BASIC interpreters which did this as well, implementing a VM and then targetting that instead. P-Code is a similar thing.
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 successive reads (or writes) would bump the pointer by one allowing straightforward transfers of data, but the very fact that most of the system's memory was only accessible in this way made significant programs difficult to write. So, TI's solution was to create an abstract machine called GPL in which memory accesses to this video RAM were more natural. It was interpreted on the TMS9900 and therefore slower than native code, though -- especially given that the CPU can only access the video chip's RAM while the chip itself is not doing scanout to the display, so during horizontal and vertical retrace.
And since all the BASIC code and variables lived in this video memory, guess what the TI-99/4A's BASIC interpreter was written in! Yeah, it wasn't very fast, like at all.
The neat part, apropos of the article's topic, is that there were no actual general-purpose registers on the TMS9900: workspace registers WR0 through WR15 were instead located somewhere in memory, pointed to by the WP (workspace pointer) register. The CPU only had three physical registers: PC (program counter), WP, and a status register. What this amounted to was you could do a very primitive form of register windowing: by using the BLWP (Branch and Load WP) instruction, you can branch to a subroutine in which a new set of "registers" will be active elsewhere in memory -- and the return address will be saved in the new workspace.
If I'm going on about the TI-99/4A a lot recently, it's because I'm writing an assembler for it as a personal project.
The `mux` instruction added computes:
m[operand2] = (m[operand1] & ~selector) | (m[operand2] & selector)
Yep, that's what the PDP-8 did. The evolution of the PDP-8 is arguably a journey in hardware support for recursion.
Initially the JMS instruction stuck the return address in the first word of the function (as an aside, a lot of time caller would put it's arguments after the JMS instruction, and the callee would read arguments offset of the return instruction, incrementing it with each read argument until the return address pointed to code again).
Then it became relatively common to use one of the autoincrement locations (the PDP-8 had 8 memory locations that would increment any time you used them as a pointer) to create a simple stack, and function prologues/epilogues manually managed this stack to allow full recursion.
Then later on hardware stacks were added in the microprocessor implementations like the Harris 6120 to make this more performant.
It can be useful in analyzing algorithms but often in cases like search it is a "second best" answer compared to say, using nondeterminism.
Why? Because my first exposure to programming was the semi-graphical scripting "language" exposed by the game-development tool "RPG Maker 2000."
For those who haven't seen RM2K scripting before: picture a cross between Scratch and Emacs Paredit mode. (E.g. https://forums.rpgmakerweb.com/data/attachments/21/21958-f89...) It's presented as textual, but you can't edit it like text — only as blocks with associated properties dialogs.
And, of course, that scripting language in RPG Maker doesn't have anything so fancy as a stack.
Want some reusable subroutines? Well, you better believe you're allocating secret global variables for their parameters — no re-entrancy for you!
---
Mind you, thinking back on it, it's probably possible to implement both registers and a runtime stack in RPG Maker 2000, given sufficient stubbornness.
Both features seem easy enough at first: you can do pseudo-"registers" like the zero page on a 6502; and you can do a stack through indirect variable access (https://rpgmaker.net/tutorials/523/).
The problem with both of these, though, is that RM2K actually has concurrency in the form of "parallel process" scripts — so any use of either of these abstractions by these parallel processes, will have different "threads" stomping all over one-another's state.
So you'd actually need multiple "zero pages" and "stacks" — one for each "virtual core" — and then you'd need to somehow assign/bind/schedule the "virtual cores" to parallel scripts (i.e. somehow get each script its own privately-known "stack pointer.") Which, to be stable in the face of race conditions, would normally require something like mutexes...
Knowing the bloody-mindedness of RPG Maker gamedevs, I'm sure someone did come up with a way to trick some runtime feature into acting like a mutex. But I'm genuinely scared to know what it was they did.
I can't imagine the amount of energy it took to pull that off and maintain/debug it.
1 GOTO 30
10 LET C = A + B
20 RETURN
30 LET A = 1
40 LET B = 2
50 GOSUB 10
60 LET A = C
70 LET B = 3
80 GOSUB 10
90 PRINT C
RUN
6
Disclaimer 1: the code could be syntactically wrong and hallucinated (40 years are a long time) but it gives the general idea.
Disclaimer 2: The Z80 processor inside the machine had stack management, the BASIC interpreter was really very basic but it could be excused: it had 1 kB RAM and a 8 kB ROM with the OS, the interpreter and everything.
Though some BASICs didn't have a generic stack, instead a fixed array of return pointers and an index to the current one, so there was a fixed depth limit of, say, 7 calls, but from your PoV as the programmer this behaves as a call stack. Obviously this isn't a “proper” stack with local variables/parameters & such which you might expect when someone refers to a stack.
An interesting demo of what happens with nested (including recursive) calls that you could do with BBC BASIC in its native environment was that you could set the location of the stack to the top of display memory, and make sure you didn't do anything that would cause things to be drawn there of course, then you can watch the stack grow as work happens. The display was low-res enough that the pair of bytes for a return address could be seen as (in screen mode 1 or 5) eight chunky pixels (four in mode 2, but they would include flashing colours which is less ideal, sixteen in mode 0, 3, 4, or 6, but seeing individual bits doesn't work as well because a sequence of eight colours repeating amongst others is slightly easier to pick out then a sequence of 16 black/white ones).
* giving rise to "BUGS AND LIMITATIONS"
But knowing the bounds of memory consumption used to be normal for application programmers, too. I mean, you don't want to run out of memory. Ever. What do people do now, just YOLO memory usage?
Yes, literally. Careful allocation has given way to "Use what's there and fail hard if it ain't enough" in the era where machines are cheap and the dominant paradigm is how parallel you can make your algorithm so you can solve your problem with scale.
In the modern era, for most online service software (which is, I'd argue, most software people interface with these days), you write it as fast as you can, prototype it small, start to care about RAM allocation (but build it to just die screaming if it runs out of RAM so you know you need to make a change), and keep scaling up.
You don't care a lot about RAM allocation until you're scaled to a lot of nodes because only at that scale is whether the app takes up a kilobyte less going to start to matter on machines that are swinging gigabytes of storage around.
There are plenty of application spaces where this isn't the status quo (embedded architectures, console gaming), but that tends to be considered specialist engineering in this day and age.
With that said, I also see benefit in having limitations. There is a certain comfort in knowing what a tool can do and cannot do. A hammer cannot become a screwdriver. And that's fine because you can then decide to use a screwdriver. You're capable of selection.
Take PostgreSQL. How many devs today know when it's the right solution? When should they use Redis instead? Or a queue solution? Cloud services add even more confusion. What are the limitations and weaknesses of AWS RDS? Or any AWS service? Ask your typical dev this today and they will give you a blank stare. It's really hard to even know what the right tool is today, when everything is abstracted away and put into fee tiers, ingress/egress charges, etc. etc.
tl;dr: limitations and knowledge of those limitations are an important part of being able to select the right tool for the job
Those are the kinds of limits GNU wanted to remove. Why use a fixed-length buffer when you can alloc() at runtime? It doesn't mean that `ls` should send email.
The benefit of not having a limitation is that the real limits scale with compute power. If you need more than 4GB of memory to process something, add more memory to the computer.
You're looking at isolated parts of a system. In a system, an artificial "limit" in one component becomes a known constraint that other components can leverage as part of their own engineering.
In the example of memory addresses, it might be "artificial" to say that a normal application can only use 32-bit or 48-bit addresses when the hardware running the application operates in 64-bits, but this explicit constraint might enable (say) a runtime or operating system to do clever things with those extra bits -- security, validation, auditing, optimization, etc.
And in many cases, the benefits of being able to engineer a system of constrained components are far more common and far more constructive than the odd occasion that a use case is entirely inhibited by a constraint.
That's not to say that we should blindly accept and perpetuate every constraint ever introduced, or introduce new ones without thoughtful consideration, but it's wrong to believe they have "no benefit" just because they seem "artificial" or "arbitrary".
Don't tell me you've never hammered a screw into a wooden plank? Vice versa, a screwdriver also can be used as a hammer although a quite pathetic one.
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.
(although that is very close to an assembler for the subset of programs consisting only of .byte foo, bar, bletch, ... directives)
Like, I technically know how to convert a recursive algorithm to an iterative one, I've done it before on more resource-constrained stuff, but I don't like it. I think the recursive stuff is generally prettier and for 99% of things it's fast enough (and 100% if your compiler supports tail recursion, though you'd still be stuck maintaining a stack for most of the more interesting stuff).
Occasionally I'll do things to force myself to learn how things were done before I was born. I've been on/off hacking on a Commodore 64 game, but man I feel pretty grateful to be as spoiled as I am with fast, cheap, easy-to-use hardware.
To do recursion in those old machines, one would need to build your own stack mechanism, but there would still be issues to take care of, as there was no native way to use anything but global storage.
Having lived through those times, I don't wish them on anyone.
$ ./gawk --dump-variables 'BEGIN { @let (a, b, c = 1) { } }'
$ cat awkvars.out
$let0001: untyped variable
$let0002: untyped variable
$let0003: 1
ARGC: 1
ARGIND: 0
ARGV: array, 1 elements
BINMODE: 0
[ .. snip many ]
Edit update: Your security infrastructure is broken because I don't know what that is and don't use Twitter. If you check the AS, it's Google Fiber. And I'd appreciate it if you wouldn't dox me.
You could do tail recursion, because only the return address of the first call would be needed to be stored. `branch_with_link` would be used for the initial call, but the recursive calls would have to be regular branches.
Personally, I think it should be avoided in modern compiled languages too.
Haskell is fun to play around on, but it is horrific to consider using in a stable production environment. =)
[1] https://web.archive.org/web/20091206042608/http://projectfor...
There are shorter ways to admit you already sold your soul. lol =)
Your threads, co-routines, interrupt handlers, error handlers, all have to be careful not to stomp on someone else’s use of the same function, even if they’re not directly using a function recursively.
On the other hand, I almost never use naked recursion in Haskell. It typically do recursion indirectly through more familiar combinators such as for loops.
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.
On the other hand, recursion extremely expensive in some languages and Python has a notorious limit that forces library writers to roll their own stack. So despite the above, I'm actually in the anti-recursion camp.
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.
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.
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 =)
At some point you will crash because the runtime won't be able to allocate any more stack. And you can't preflight it because if you could preflight it you wouldn't be doing recursion.
Recursion is a nice toy, but in real life it's a ticking time bomb.
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.
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 may be use cases where it's insecure or has performance concerns, but those are the exception. Most of the time, it's fine.
We don't generally tell programmers that loops are naive, often dangerous, and risk locking up the program. They certainly can, but most just... don't.
Just like loops, recursion can make code much simpler to write, read, and maintain. Every modern language under the sun supports it for very good reasons. Use it.
Parsers are far from immune to these issues.
I think we will have to "agree to disagree" here... =)
def isRecursionOk(problem)
for (subProblem in (breakDownIntoSubProblems(problem))
if ! isRecursionOk(subProblem) return false
return trueMakes 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 trueThere are safer hobbies available like snake juggling =)
with open('lulz.json') as ayy_lmao:
oops = json.load(ayy_lmao)
EDIT: btw you can do the same thing in rust's serde_json if the type you're deserializing into somehow supports the nesting, but you'd have to work for it.
EDIT2: the only (decent) way I can think to mitigate this in the python app's case is to enforce a sufficiently restrictive Content-Length at the edge, which obviously isn't possible of you expect blobs O(100Kb) uncompressed. Or you could pre-parse to detect nesting.
[1] EDIT3: on my machine in ipython right now it's 1485:
import json
def nest(d):
return '{"k":' + str(d) + '}'
def make_mess(n):
v = 1
for _ in range(n):
v = nest(v)
return v
json.loads(make_mess(1485)) # boomYou'll want to cap the maximum allowed nesting depth. Even if not using recursion, you probably don't want untrusted input to be able to make your stack data structure allocate arbitrary amounts of memory.
If you do put a nesting limit in, you can do that equally well using an actual stack or recursion. (For example, I believe v8 still uses recursive descent for parsing JSON and JavaScript. It detects and handles stack overflows to ensure that untrusted input can't blow the stack and crash. I'm not sure if it's using a hardcoded nesting limit or actually trapping the stack/heap collision somehow.)
I've run into similar issues with recursive code in java. The story gets better in C or rust, but there wre still sharp edges. I guess there are sharp edges everywhere though...
Shouldn't you stick to a depth-first branch reply limit until moving to the next fork.
I want to respect your beliefs. =)
And yeah, recursion is avoided in some shops for good reasons.
If you have a binary tree with 1 billion elements, the depth will be 20. In a b-tree with a reasonable node width (eg 16), assuming 50% occupancy the depth will be about 8.
This is, in practice, totally fine. You won't exhaust your stack traversing a balanced 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 you don't have to worry about for almost all scenarios you're likely to encounter.
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.
I didn't actually say that, but even supposing I meant that, walking a 3D mesh in a way that requires you to keep stack context sounds like a pretty unlikely/niche scenario, so it seems even that stronger statement is true.
It's fairly intuitive to walk a mesh recursively by following adjacent edges and you have to keep track of where you've been which means storing a lot of data somewhere. Maybe there are better algorithms but sometimes you just reach for what's most obvious. I suppose there are many analogous applications of traversing a graph structure.
Well, it's about the tradeoffs right? If I have a recursive algorithm that's growing the stack (assuming no TCO, because few languages people actually use in production support it) I'm trading execution time, space, and reliability for economy of expression. In reverse order:
- reliability: if, as you suggest, I implement some hard depth limit (which is necessary because all the processes which are running concurrently need to not exceed my max stack depth), and assuming generally that things grow over time (more users, more concurrent processes, more recursive calls needed to get the job done) we face two issues. (1) theres a complicated relationship between the maximum number of concurrent processes and the maximum allowable recursion depth. Getting it wrong could crash the entire program! If this is a web server that's means we just killed a whole bunch of connections all at once. (2) eventually, over time, we'll need to raise the recursion limit, which entails rebalancing the concurrency limit. Hard walls like this are bad news in systems. If instead this was implemented iteratively the system would degrade softly as the iteration count grows--each process would take longer to complete, but they'd still all complete. Assuming I'm monitoring process execution time I can predict and respond to this proactively instead of being faced with an emergency where the system is just completely broken.
- space: this is obvious I guess, more stack frames == more memory. The problem is worse in some languages than others.
- time: this may be less obvious, and there may be optimizations which render it false, but generally in my experience iterative code gets pipelined better and runs quicker.
> Stack growth is just something you don't have to worry about for almost all scenarios you're likely to encounter.
I guess that depends on the situation. I've encountered hard walls and performance issues from recursion enough times in my career thus far that I make the extra effort to avoid it. I could totally see the value, though, in areas where you know ahead of time how the recursion depth will scale over time. More often than not, though, that's unknowable at implementation time so better err on the side of caution.
EDIT: upon re-reading this I think it might have been clearer if I insted wrote "task" every time I wrote "process"--I'm not talking specifically about any OS feature.
My process for deciding when to use iteration or recursion is simple: if each step needs to keep context then use recursion, otherwise use iteration (unless recursion with TCO is the native idiom of course).
I've never had an issue that wasn't an obvious bug that iteration would have somehow solved. If any bug that terminated a thread was fatal to the whole process then I suggest the thread termination handler should handle this more gracefully.
Increased space usage is a non-issue IMO. Translating a stack frame to a data structure you manage as an explicit stack requires the same space within a small constant factor.
And an oft-ignored factor is the cleanup advantages of allocating on the stack, which offsets any space and time disadvantages you might see with recursion.
Quite likely :)
> And an oft-ignored factor is the cleanup advantages of allocating on the stack, which offsets any space and time disadvantages you might see with recursion.
This is a very good point.
Alright, you've convinced me to start playing with recursion again. Just not in java or python.
So, if you try to unroll naive recursive code, than one wins n-many issues instead of 1 predictably separable one. Sure one could pass in a mutex etc., but it is back to using a global again and a single-core bounded context.
Best of luck, =)
Yes, you can use std::vector or array or similar as a stack, without using recursion (which has some easily reachable depth limit that is much smaller than what your full RAM memory allows, especially in e.g. JS)
Of course ideally programming languages would figure out a way to not have this reachable limit and allow as much recursion as your RAM allows... We're still in the ancient world when it comes to this, it seems
You are not lazy enough to be a good programmer yet. ;-)
Have to think "minimum effort" here... ;-)
That is efficient for most Java programmers. =)
def process_that_tree(my_tree):
def _handle(node):
# do the things
for child in node.children:
_handle(child)
_handle(my_tree.root)
Obviously for the filesystem these kinds of abstractions exist already in shutil/pathlib/glob, but it still can have a place for dealing with other kinds of hierarchies, like a package dependency tree or the like.
Recursion for iteration is just more complicated iteration. I've never seen a good argument for it in modern programming, it just ends up being the classic backwards rationalization of something people want to believe.
Recursion for traversing a tree is just using the call stack as a stack data structure.
Any balanced tree is never going to exceed 64 levels deep (really 48 on a 48 bit memory addressing cpu) and that could easily be put in a static array that gets used as a stack without recursing. This is easier to limit and debug.
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.
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?
> 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
That's what functions do.
often creates finite set of self dependent functions
This doesn't have anything to do with recursion.
all you do is call and pass other functions, that will call each others
You this doesn't have anything to do with recursion.
If you consider `map` or `fold` these create opaque functional processes that operate very automatically.
I think you mean, they iterate for you. They don't use recursion.
On the other hand in OO you needed (until very recently) to create iterators and empty structure to modify step by step.
I really don't understand all this. You know most iteration is done with a for loop right?
PEG parsing where the monadic flavor replaces an externally managed stack
This seems like you're trying to write a satire of someone soaked in haskell. Everyone is else is just writing for loops and moving on.
recursion is compressing the domain so small it eats itself, crafting a small set of function is mirroring this, kinda like grammars
> You this doesn't have anything to do with recursion.
> I think you mean, they iterate for you. They don't use recursion.
afaik map and fold were defined recursively
...
foldl f z (x:xs) = foldl f (f z x) xs
> I really don't understand all this. You know most iteration is done with a for loop right?
that was what i was pointing at, iterators are not encapsulated enough
> This seems like you're trying to write a satire of someone soaked in haskell. Everyone is else is just writing for loops and moving on.
I'd appreciate if you didn't make it personal. Also, you forgot ocaml, lisp, prolog.
I don't think this means anything. At best it's a completely abstract claim with nothing backing it up. It isn't "compressing a domain" to do iteration differently.
afaik map and fold were defined recursively
Fundamentally they are useful because the do the iteration for you. Internally it doesn't matter if the iteration is done in a roundabout way with recursion, they aren't about recursion and don't really have anything to do with them, just because some language decides to do iteration with recursion.
that was what i was pointing at, iterators are not encapsulated enough
You keep saying iterators, I keep saying iteration, but the only difference here is that the recursive version hides the accumulation in the arguments on the function. There isn't any more encapsulation, just a variable moved into the function argument. The brevity is from haskell's type deduction, not recursion.
Map doesn't do iteration.
It's not about Haskell.
https://www.geeksforgeeks.org/python-map-function/
The whole point of map is that it does the iteration for you and you pass it a function. Iteration is literally the reason it exists.
Map doesn't simply iterate (that would be forEach), it creates another piece of information containing f(a) for all a in the input sequence.
What would iterating over a tree yields ? what would mapping over a tree yields ? how do you define the latter ?
Says who? You didn't back this claim up with anything.
Map doesn't simply iterate
No one has ever said it 'only' iterates, you hallucinated this claim. The whole point that I've made is that just because a language like haskell uses recursion for iteration, it doesn't mean iteration and recursion are the same thing or that things that iterate have anything to do with recursion.
Why would I need to back that up ?
> No one has ever said it 'only' iterates, you hallucinated this claim. The whole point that I've made is that just because a language like haskell uses recursion for iteration, it doesn't mean iteration and recursion are the same thing or that things that iterate have anything to do with recursion.
Why the mention of haskell all the time ? I'm not even talking about statically typed languages here.
The original conversation was about the intellectual benefits of recursion, not iteration == recursion. Recursion is a way to think about problems that I find more general, precise, creative and economical I tried to convey why, I'm not the most precise but this is getting nowhere. Feel free to enjoy your life.
Why do you need to back up the things you say? Because if someone believes anything without an explanation then they don't know what's true.
Why the mention of haskell all the time ?
Because you wrote haskell -> foldl f z (x:xs) = foldl f (f z x) xs
The original conversation was about the intellectual benefits of recursion
No, you made very abstract and bizarre claims like recursion is compressing the domain so small it eats itself, it's creating self sustaining computing blocks, and use tiny function that will thread themselves as see fit.
Statements like this that aren't even really coherent sentences, let alone explainable, are the types of things that happen when no one asks anyone to back up what they say. Evangelism starts to bleed into religion and anyone questioning the grandiose hyperbole is dismissed as an adversary.
I just copy pasted the first line of code in wikipedia, the definition is the same in ocaml, and in spirit scheme (list pattern matching syntax aside).
You're forcing your views on me, thinking I'm defending a Haskell cult which I'm not. Most of this came before Haskell was a language name idea. Probably even back to the late 60s.
And yes inductive reasoning is about compressing the domain in a finite set of disjoint cases that "eat itself" because you can reuse other parts of that domain in substructures. Wrapping all required information as function argument makes them self sustainable / encapsulated because nothing leaks out. It's not that much of a bizarre claim.
I'm just asking for something and you haven't given anything but big claims of the benefits of recursion without any explanations or example comparisons.
And yes inductive reasoning is about compressing the domain in a finite set of disjoint cases that "eat itself" because you can reuse other parts of that domain in substructures. Wrapping all required information as function argument makes them self sustainable / encapsulated because nothing leaks out.
This is still a grandiose claim without any explanation of what it is supposed to mean, let alone any explanation of why it is true, especially in comparison to other languages. Every language has functions.
It's just as easy to limit recursion depth, if you need to, just pass along a counter and check it. I haven't found that hand-rolling a second stack, instead of using the program stack, is easier to debug, the opposite if anything, but your mileage may vary on that one.
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 stacks to find data.
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
How can you differentiate between them? How do you account for these two things being isomorphic? Any algorithm that can be defined by calling itself can also be expressed by way of an explicit stack, just as any algorithm defined iteratively can be implemented via recursion (usually tail recursion). Using an explicit stack and the call stack is formally equivalent.
> That's not recursion, that's organization, modularity and all sorts of other descriptions. Where did you get these ideas?
From the same source as you. Namely the thing you quoted below:
>> Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself
I'd say that a "simpler or previous version of itself" would also be smaller since you're trying to get down to the base case.
Like if you're doing stuff with a binary tree, you usually have to consider the left and right subtrees, and whether they're empty or not, and if they're not empty, maybe do something like push a new entry onto a stack so that the left and right subtrees also get processed, and of course with them being empty being the base case.
The structure is inductively defined, which is why recursion is also the natural way to approach it. This of course being in contrast to dealing with codata and corecursion which deals with infinite structures.
One is a concept that means that something is defined in terms of itself, which why I linked you the definition. The other is a data structure where the first item in is the last item out. One is an abstract concept that isn't limited to computer, the other is an ordering.
Why do you think these two completely different things have anything to do with each other? You just keep saying they are the same for some reason. Repeating a claim is not evidence.
How do you account for these two things being isomorphic?
They aren't.
Any algorithm that can be defined by calling itself can also be expressed by way of an explicit stack, just as any algorithm defined iteratively can be implemented via recursion (usually tail recursion).
Being able to do something in a different way with a different tool doesn't make all ways and tools the same. I can hit a nail with a block of wood, that doesn't make the wood a hammer. You can use it as a hammer, but if you ask someone what it is they won't say it's a hammer.
Using an explicit stack and the call stack is formally equivalent.
My point above is that pragmatically they have a big difference, which is that it is easier to debug a static array stack because you can see the whole thing instead of having to walk through a call stack to figure out where the iteration went. It's also probably faster and simpler, but the point is the clarity and the ability to debug.
The structure is inductively defined
The structure is defined by the data. There is nothing "inductive" about it.
which is why recursion is also the natural way to approach it.
Again, what you are really seeing here is that the iteration of a tree matches the first in last out structure of a stack. Recursion just gives you a stack using the call stack, nothing more.
This of course being in contrast to dealing with codata and corecursion which deals with infinite structures.
This has nothing to do with what we are talking about.
Well first of all, both are abstract concepts. In particular, in computer science stacks are considered to be an abstract data type with a push and a pop operation, which both act on the "top" element of the stack.[0] And I'm sure that you already knew this.
The fun part here is, of course, that stacks are also a type that can be defined via structural induction. I.e. that you either have an empty stack, or a stack where the top has an item and then below is another stack which contains the rest of the elements of a stack. So something like this:
data Stack a = Empty | NonEmpty a (Stack a)
There's of course nothing magical about call stacks versus explicitly instantiated stacks. They're both particular manifestations of the abstract data type. Of course, you can easily argue that there's a difference since call stacks of course tend to get special support in hardware, but as per the original article, that was of course not always the case.
And this is not to mention that you can store "call frames" even with an explicit stack and then pop things off of the stack, until it's empty, in a loop. This is for example how usually recursive algorithms such as depth-first search are implemented in a more iterative manner. And this couldn't be recursion because... it's not written as a function calling itself? Do I understand this right? Because to me that feels like a quite arbitrary way to define what it means to "define in terms of itself".
> They aren't.
Well, I'm not going to ask for a full formal proof, but I would appreciate for some expansion of this point.
> Being able to do something in a different way with a different tool doesn't make all ways and tools the same. I can hit a nail with a block of wood, that doesn't make the wood a hammer. You can use it as a hammer, but if you ask someone what it is they won't say it's a hammer.
Well at least to me, it seems that the argument being put forward here is more that you can't use a block of wood to hammer a nail with, because a block of wood is not a hammer, and that you need to explicitly use a hammer to be able to hammer stuff.
> My point above is that pragmatically they have a big difference, which is that it is easier to debug a static array stack because you can see the whole thing instead of having to walk through a call stack to figure out where the iteration went. It's also probably faster and simpler, but the point is the clarity and the ability to debug.
Oh for sure, it's easier to inspect a stack if it's backed by an array. Of course one could also argue that this should be solvable by improving debugging tools, and making them better at showing call frames, but that's neither here nor there.
> The structure is defined by the data. There is nothing "inductive" about it.
Incorrect.[1] Trees are explicitly defined as inductive/recursive data types. And this isn't just the case for binary trees, but trees where you can have arbitrary amounts of children are defined like this, usually by invoking the concept of a "forest" which is a collection of trees.
> Again, what you are really seeing here is that the iteration of a tree matches the first in last out structure of a stack.
Well no, you could also go through a tree in a breadth-first traversal, in which case you wouldn't want a stack, but a queue, which is explicitly a FIFO. But yes, due to the structure of a tree, and it being a recursive data structure, of course you'd usually use recursion to iterate through it. And for that, you want a stack of some sort.
> Recursion just gives you a stack using the call stack, nothing more.
I don't disagree with this. If anything, it just serves my point. There's nothing special about using the call stack for this. Whether using the call stack or an explicit stack, you're still going through the tree in this case in way that takes advantage of its recursive nature of being defined as nodes with other trees as the nodes' children.
We could come up with an alternative name for this, if calling this general idea "recursion" feels odd, since you don't need to necessarily implement it as a function calling itself, but that doesn't fundamentally change the actual thing being done.
> This has nothing to do with what we are talking about.
Heh, fair enough. I just thought how it's interesting that both induction and corecursion deal with data by defining stuff from a base case and then expanding on that, but of course corecursion is based on coinduction, which of course goes the other way around, going from larger objects to smaller ones, which on the other hand is how recursion is usually thought of.
But yeah, not super relevant.
----
[0]: <https://en.wikipedia.org/wiki/Stack_(abstract_data_type)>
[1]: <https://www.cs.princeton.edu/courses/archive/fall21/cos326/l...>
No they aren't. A stack is a specific type of data structure. Recursion isn't even specific to computers.
in computer science stacks are considered to be an abstract data type
I think you meant data structure and they aren't both concepts.
Of course, another way to refer to this kind of a structurally induced data type is to call it recursive.
You are making a linked list. A node in a traditional linked list has data and a pointer to the next node. This is what you are making here. Just because you over complicate a stack by using a linked list, it doesn't mean a 'stack' and 'recursion' are the same thing.
Fundamentally this is functional programming silver bullet syndrome. These things really have nothing to do with recursion, haskell is just putting a square peg in a round hole by using recursion for iteration and linked lists.
It's all fun and games until you get past trivial examples. Then pretending complex iteration and data structures are best done with recursion aren't so fun anymore and you want to control what is actually happening.
One example is this rust quicksort being 40x faster than haskell
Seems very inefficient for the risks it brings.
I think we all agree this is still very interesting to consider. =)
I remember doing something similar to what he describes. My hardware design was basically a Z80, a 2716 EPROM (I may have also had a Parallax EPROM emulator to speed debugging) and a couple of Z80-SIO serial devices. Notice that there is no SRAM chip :-)
The Z80 has enough registers that I could hold all the data I needed internally so I decided against the extra cost of RAM. This was the early 90's, remember. The one thing I was missing was a stack to make function calls. This was done (memory is fuzzy here) by preloading the return address onto a register pair and then calling the function. When the function was done, it would do an indirect jump to the location held in that register pair, which would return to the next instruction after the call.
I don't remember how I passed and returned values, but I probably dedicated a register to that. I have a couple of old hard drives around here somewhere. I should see if I saved the code anywhere; I was quite proud of it.
I wrote a MIDI driver once, and that required dividing a 1MHz external clock, to get the 62.5KHz (I think) serial clock (you couldn’t divide the internal clock).
Their chip had 8 control lines, with each line controlling some aspect of the chip operation. They set it up as the lower 8 bits of the 16-bit address bus, with the upper 8 bits fixed (so you were working with 256 addresses, to control the chip).
So just referencing an address would change the state of the chip.
A lot of hardware limitations influenced software structure, and I’ll bet that a lot of software proclivities have their genesis in weird hardware compromises (like bytes).
This is pretty much what the MIPS `jal` and ARM `BL` do. TMS9900 also did something similar (edit: it had a `BL` instruction too.)
I was fascinated by the fact the Signetics 2650 that had an 8-byte internal stack.
Which customer/sector was your project intended for?
I was so excited to have a freelance job (don't remember how I got the customer either) that I jumped right into it and worked heads down for a couple weeks. Then when I went to tell the customer that I was done and ready to ship, I couldn't reach him. Finally heard back from him about 6-12 months later and he was surprised that I had been working on it without hearing back from him and that he no longer needed the product.
And that, kids, is how I learned to get at least partial payment upfront.
Edit: Very interesting how easily available they still seem to be according to Google.
A "stack" was also a small memory, single thread optimization because it allows you to multiplex memory for function calls. If two functions do not call each other, they can share the memory used for their activation records.
Keeping track of this memory multiplexing in the compilers of the day would have been very hard and highly memory intensive--a stack solves that problem.
Without a stack, your memory usage (static) goes as O(n) with the number of functions. With a stack, your memory usage (dynamic) goes as O(n) with the depth of function calls. The memory usage of these two scenarios is wildly different.
I didn’t read Raymond say anything about security in the present article, but the advantages a clear. No stack or buffer overflow vulnerability for example.
stackless Cobol really did fun things to brains on long term exposure.
I first learned to program on a calculator in a kneecapped version of BASIC which didn't support recursion, function calls, user defined variables (you got 'A' to 'Z' and that was all) or dynamic memory management (other than resizing 'matrices' and 'lists' iirc). I wanted to write Minesweeper on it and to do so I independently invented what I later found out were well know as depth first search and breadth first search, using just some loops and a list as a stack. (I was a kid and we didn't really have the internet yet. :P )
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 that way. You were just on your own.
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 quantity one. Perhaps he meant culturally expensive?
Most people just know the title and simply fetishistically refuse to use a goto (most of the time they are terrible, but not always). But really the paper argues for giving subroutines a single entry point.
Sometimes I write assembly code that falls through into another subroutine, but I don’t want all my assembly to be spaghetti like that.
While this, as you note, often led to mass refusal to use a goto, the effect of the paper led to much discussion and presaged the practice of much better control flow constructs in languages.
One trick I've seen in BIOS code is basically return-oriented programming[1]: before a "call", the stack pointer is set to some location in ROM containing one or more return addresses. The advantage over putting the return address itself in some register is that this way, it can use subroutines ending in a normal RET instruction, that might also be called later when there is an actual stack.
[1] https://en.wikipedia.org/wiki/Return-oriented_programming
That's still what current day allocators are.
Think of RAM as just a byte array in your favorite systems programming language. It's size is that fixed-size buffer (or, when RAM size is unknown due to hardware modularity, its size is the maximum possible and you pinky-promise not to look beyond the end).
The kernel sees all of the RAM as a fixed-size buffer, and an allocator manages what's free etc. These days, userspace processes see virtual addresses and you can think of them as all getting 2*64 bytes as their "fixed-size buffer". brk and mmap are really more hints to the kernel as to what part of the buffer you won't be needing.
I believe 'hidden' is the word he's looking for.
And one doesn't have to go all that far into history to find architectures w/o hardware support for a return stack, see e.g. Parallax Propeller.
And the problem with static variables (hidden or not) is not only that they prevent recursion, but also reentrancy.
I think that article could have benefited from a peer review from one of his colleagues at Microsoft.
Your reference to the Parallax Propeller is domain-specific and a bit anachronic; you're talking about embedded computing, while he is talking about general-purpose computing a few decades prior. The point of the post is that general-purpose computing was different in the past (in a sense, that's the theme for the whole blog! that and compatibility hacks), so going this far back is necessary.
I don't think many people realize just how much of a modern processor is made around supporting preemptive multitasking. Folks know that we have a class of security bugs from it, but a lot of what happens in a CPU is around juggling multiple workloads.
Or they’ll just cargo-cult everything and have no clue what’s happening under the hood.
now I feel old
or at least have an MPU, which is what some microcontrollers have to protect multitasking.
I wonder what programming techniques exist today that will be obsolete in 30 years? I imagine Transformers made a bunch of early ML algorithms completely obsolete?
What else?
I wrote code for a microprocessor that did not have a stack as an actual concept. There are still embedded processors out there today like this. To work around this you stored a value at a zero page location, and when you wanted to jump to a subroutine, you would first load up this value from zero-page, advance it, put the program counter into the memory address now pointing to a new memory location, then execute a simple go to, and at the end of your function, to return, you would load up that value in zero page, then load up your return address, decrement your pointer, store it back to zero page, then go to back to the calling function. Every value you wanted to pass to the subroutine would be either in one of your three registers, or you would pass those values by storing them in memory pointed to by your zero page value. The 6502 offers nice instructions to do these very operations, by turning the assembly/machine code into microcode that does the exact same thing, but more succinctly.
Another trick I used was bank weaving. You only had a limited amount of addressable memory, but you could bank switch ROMs, so you'd write your code to have it reside at a fixed memory location, and another chunk of code at another fixed memory location in a different ROM bank, then your first code would execute down to a point where it would switch banks based on a condition, and when the other ROM bank switched in, your alternative code path would be waiting for you, you'd execute that, then switch the ROM bank again back to the first one, and the PC (program counter) will have advanced several hundred bytes possibly, so you'd return to a point in your code, back in the first ROM bank, that was a completely different point in memory, but still the same calling function.
A few years later I used a similar technique on a large text adventure game, a compiler and a word processor, where the core of the program was always resident, but chunks of code could be loaded in at fixed memory locations from disk. So if you ran a spell check, the spell check functions would load in at a known memory location, various bits were set in RAM to indicate which functions were resident, and the application could perform the spell check, or run the logic for a part of the text adventure game. And functions would automatically unload to make room for new functions based on the last time they were invoked.
I wrote code for a Timex processor that had a "execute the instruction at the following address" opcode, so effectively your instruction here, would execute that instruction over there, but only for one instruction. It made writing the equivalent of switch/case in assembly interesting, and also good for self-modifying code.
Zero-page on some old CPUs was a faster RAM, a few dozen bytes, or even 256 bytes, so if you had a tight loop, you'd copy the code into zero page, perhaps having to move other stuff out of the way first, and execute it there.
I wrote a word processor that stored only a tiny fraction of its data in under 3KB of RAM, the rest was stored on big floppy disks. As you scrolled through the text, it would page through the pages (memory pages, not pages of text) on the floppy disc, but the memory pages were not stored continuously, either in RAM or on disk. The RAM acted more like a cache, and a couple of memory pages were reserved for edit operations and even copy & paste. To copy and paste entire pages was fast, you only had to adjust a few pointers in RAM and on disk, plus a few hundred bytes for head and tail page operations so moving large blocks of text around was very fast, and inserting large blocks of text, or even just typing, was very fast, because the buffers were quite small. It was the only word processor I know of that came with a disk defrag operation built in, but the company called it "housekeeping" in the manual with no explanation to the end user of what it was doing. I learned a lot about "don't mark that as deleted until you are damn sure the operation is completed and you've verified it worked."
I did a 6507 and Z80 emulator on the MIPS R3000 that ran the code in a very pedestrian way, but as the 6507 or Z80 ran through the code, each memory address was added to a list, and the 6507/Z80 opcode found there was translated into an intermediate assembly language, and then I post-processed that intermediate assembly into R3000, which gave me a huge performance boost; post-process dynamic recompilation effectively. I had to do other sneaky things with it too because the original hardware raced the electron beam whereas the target platform just had a big VRAM buffer. Used the same trick to port 6507 code to an early ARM processor for an old handheld too.
There's a lot of other tricks we used to in the before-times, such as LFSR and LCG to permute game objects in seemingly random patterns, cheating on distance checks by counting the clock cycles between two objects drawn on screen, low-rez bitmaps of the screen to speed up collision detection, compiled graphics/sprites, even sprite blitting routines that were hard-coded to specific pixel offsets.
Even modern C compilers for "modern" 8051-derived MCUs work like this :)
And as usual, worth reading at least one or two more times.
Fucking. Legend.
I always assumed that functions did something like this behind the scenes. At the lowest level, all of memory is just a very large, globally-accessible array of numbers. Functions are just JMPs with fancy syntax sugar.
...is that completely wrong? Do modern computers actually have some type of hardware support for functions?
Local variables are placed on the stack as well, this is necessary if you want recursion, and it also typically results in faster/shorter code, because the instruction set and microarchitecture are optimized for this type of memory access.
I sincerely doubt that English is the only language that supports such word play.
One is lead to believe the subject is "the ancient world before computers", as it would be in "the ancient world before computers had gladiators and triremes", but the subject is "computers", and the ancient world is the topic.
All that world was well before computers were a thing (even the human type were called “scribes,” “clerks” etc.)
So of course I read it the same way even though “before computers” was redundant once your comment made me think about it.
I.e. "the ancient world had stacks and heaps" as opposed to "the ancient world had stacks or heaps," which sounds weird.
I understand, why the provided example does not allow for recursion, but doesn't it also prevent a nested call to another subroutine?
If I remember correctly before FORTRAN90 we already had nested subroutine calls. How did that work?
EDIT: I think I get it. The hidden global variables are prefixed with the sub's name. This is pretty wasteful, but as long as a function does not call itself (even indirectly) we are good.
CALL MUL
2
3
BNE 6, FAIL