[HN Gopher] Subroutine calls in the ancient world, before comput...
___________________________________________________________________
Subroutine calls in the ancient world, before computers had stacks
or heaps
Author : signa11
Score : 282 points
Date : 2024-04-03 04:33 UTC (18 hours ago)
(HTM) web link (devblogs.microsoft.com)
(TXT) w3m dump (devblogs.microsoft.com)
| 082349872349872 wrote:
| Note that before we had arbitrarily extensible heaps, programmers
| always did at least a little engineering, in that they had to
| consider the probable distribution of inputs and size* all their
| intermediate storage appropriately.
|
| * giving rise to "BUGS _AND LIMITATIONS_ "
| eschneider wrote:
| Those before times are still today, depending on what you're
| doing. For hard real-time, dynamic memory is (almost) never
| used, mostly because the time needed to alloc/free memory isn't
| deterministic. So everything is statically allocated at compile
| time and yeah, you've got to know how much memory your inputs
| are going to consume.
|
| 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?
| shadowgovt wrote:
| > 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.
| kstrauser wrote:
| Historically, that was also a big goal of GNU. It aimed to get
| rid of artificial limitations in core utilities. That was a big
| improvement over (made up example) sed having a finite and
| short maximum command length.
| deckard1 wrote:
| I can understand why people wanted that, and the benefit of
| doing that.
|
| 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
| Joker_vD wrote:
| > A hammer cannot become a screwdriver.
|
| 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.
| kstrauser wrote:
| I see zero benefit in having artificial functionality
| limitations. In my hypothetical example, imagine that `sed
| 's/foo/bar/'` works but `sed 's/foo/bark/'` does not
| because it's 1 character too long. There's not a plausible
| scenario where that helps me. You wouldn't want to expand
| sed to add a fullscreen text editor because that's outside
| its scope. Within its scope, limitations only prevent you
| from using it where you need it. It would be more like a
| hammer that cannot be made to hammer 3 inch nails because
| it has a hard limit of 2.5 inches.
|
| 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.
| kryptiskt wrote:
| There's a major benefit: you can test that a program with
| an artificial limit works up to the limit, and fails in a
| well-defined manner above the limit. A program without
| any hardcoded limit will also fail at some point, but you
| don't know where and how.
| mywittyname wrote:
| Imagine using a program that can only allocate 4GB of ram
| because it has 32-bit address space. There's no benefit to
| that limitation, it's an arbitrary limit imposed by the
| trades-offs made in the 80s. It just means that someone
| will need to build another layer to their program to chunk
| their input data then recombine the output. It's a needless
| waste of resources.
|
| 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.
| swatcoder wrote:
| > Imagine using a program that can only allocate 4GB of
| ram because it has 32-bit address space. There's no
| benefit to that limitation
|
| 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".
| lenerdenator wrote:
| Really, the mistake was letting humans provide input to
| computer programs.
| layer8 wrote:
| In particular input to assemblers, compilers, and
| interpreters.
| 082349872349872 wrote:
| 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.
| 01HNNWZ0MV43FF wrote:
| This was posted yesterday
| joeatwork wrote:
| Getting recursive functions into ALGOL turns out to have been a
| controversial move that made for a fun story:
| https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...
| robocat wrote:
| Definitely "a tale of intrigue, betrayal, and advanced
| programming-language semantics"
| dang wrote:
| Related:
|
| _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)
| dragontamer wrote:
| I really liked the Art of Computer Programming with regards to
| this subject.
|
| 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.
| Retr0id wrote:
| SQLite's on-disk format uses a similar array technique for
| storing the contents of table btree leaf node pages. Within a
| fixed-size page, there's an array of offsets growing forwards,
| and an array of (variable length) row values growing backwards
| from the end - the latter of which may end up with holes when
| rows are deleted (iiuc).
|
| It wouldn't surprise me if it was a direct inspiration, since
| their docs cite TAOCP for the btree structure itself.
| hiAndrewQuinn wrote:
| We know from the Corecursive podcast on the hidden story of
| SQLite that Dr. Hipp did indeed reference and pull at least
| one alg straight from Knuth's books, which he had behind his
| desk. What a different world that must have been!
| andrewshadura wrote:
| FYI, he's D. R. Hipp, not Dr. Hipp.
| jcgrillo wrote:
| More like Dr. D. R. Hipp, actually.
| felixge wrote:
| This sounds like it was copied from PostreSQL which SQLite
| cites as a strong source of inspiration.
| tanelpoder wrote:
| Oracle does this as well and I suspect many other row-major
| RDBMS storage engines do too.
| suncherta wrote:
| As others have already mentioned this is used in a lot
| (most?) of databases. It is called "slotted-page". Searching
| for it gives good discussions/explanations of it.
| shadowgovt wrote:
| 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 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.
| bewaretheirs wrote:
| > Have one array grow normally from location#0, and the second
| array grow backwards from location#End.
|
| 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.
| yongjik wrote:
| > Have one array grow normally from location#0, and the second
| array grow backwards from location#End.
|
| 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.
| masfuerte wrote:
| Some word processors on 8-bit computers worked like this. Your
| document took all of the available RAM. Text before the cursor
| was at the start of RAM and text after the cursor was at the
| end of RAM. Insertions and pastes didn't need to shuffle data
| around but navigation did. It worked well.
| shadowgovt wrote:
| 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 other (but how often is that your use case?).
|
| https://coredumped.dev/2023/08/09/text-showdown-gap-
| buffers-...
| cerved wrote:
| seems like Vim does too
| gigel82 wrote:
| Am I the only one who read it as the ancient world before
| computers _existed_ had stacks or heaps? English is so weird
| sometimes...
| ivanjermakov wrote:
| Me too clicked the link expecting stories of heap and stack
| uses before computers.
| grraaaaahhh wrote:
| Yeah, I was all ready to learn about how the ancient Egyptians
| used stacks to build the pyramids or something.
| nerpderp82 wrote:
| Technically they did.
| trealira wrote:
| I was expecting some ancient Greek algorithms that used stacks
| or priority queues, haha.
| dfxm12 wrote:
| I don't find the ambiguity weird, but rather poetic. Perhaps it
| is intentional. After all, computer technology has come such a
| long way in just our lifetime. A modern computer would probably
| be just as alien to someone in the 1920s as the 20s. In the
| same way, an average person today would be just as baffled by
| the ENIAC as they would an Antikythera mechanism...
|
| I sincerely doubt that English is the only language that
| supports such word play.
| glhaynes wrote:
| I'm no grammarian but I think it should have a comma after
| "world".
| perihelions wrote:
| "Novel analysis of the Antikythera mechanism suggests all of
| its wheels were statically allocated at construction time"
| brudgers wrote:
| The ordinarily "The Ancient World" means an era ending with the
| fall of the Western Roman Empire circa 476 CE.
|
| 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.
| anthk wrote:
| They had abaci with stacks.
| marcellus23 wrote:
| This has nothing to do with English, it's just syntactic
| ambiguity. Every language has it.
| samatman wrote:
| It's a garden-path sentence:
| https://en.wikipedia.org/wiki/Garden-path_sentence
|
| 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.
| Toorkit wrote:
| If that had been the way it was intended, I think it would have
| been phrased "stacks and heaps."
|
| I.e. "the ancient world had stacks and heaps" as opposed to
| "the ancient world had stacks or heaps," which sounds weird.
| kazinator wrote:
| In the @let feature in Enhanced GNU Awk, for those @let blocks
| that are outside of a function, like in BEGIN or END blocks, I
| have the compiler allocate secret global variables. They are
| reused as much as possible between blocks. $
| ./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 ]
|
| https://www.kylheku.com/cgit/egawk/about/
| weinzierl wrote:
| The article does not distinguish between recursive and nested
| subroutine calls.
|
| 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.
| comex wrote:
| It does allow nested calls, because each function has its own
| storage for the return address and local variables.
| dbcurtis wrote:
| Nor reentrant. In machines where the JSR that stores the return
| address at the jump target, usually interrupts are locked for 1
| following instruction so that you have a chance to load the
| return address into the accumulator. Back in the day I worked
| with a RTOS on one of those beasties.
| kps wrote:
| On some systems, arguments were stored at the call site,
| typically immediately after the call instruction, where the
| callee could use the return address to find and skip over them.
| This made calls using constant arguments easy.
| CALL MUL 2 3 BNE 6, FAIL
| howerj wrote:
| 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 virtual machine
| that could do those things, along with cooperative
| multithreading. The heap, if required, is written in Forth, along
| with a floating point word-set (various MCUs not having
| instructions for floating point numbers is still fairly common,
| and can be implemented as calls to software functions that
| implement them instead).
|
| 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.
| anthk wrote:
| I was about to talk about subleq, but it's damn difficult even
| to write a "Hello world".
| howerj wrote:
| Yeah, it really is a pain to do anything in it. I got around
| that by writing in another language instead as soon as
| possible. You can paper over many issues with a VM, although
| it will slow things down on such limited computers.
| anthk wrote:
| How does muxleq work? It looks like a 'concurrent'
| subleq...
| howerj wrote:
| I am not sure what you mean by concurrent in this case,
| muxleq is just subleq with one extra instruction. The
| extra instruction is based off of multiplexing (see
| https://en.wikipedia.org/wiki/Multiplexer). Subleq as you
| know is incredibly inefficient, muxleq is an experiment
| to add a single instruction to Subleq in order to greatly
| improve its efficiency.
|
| The `mux` instruction added computes:
| m[operand2] = (m[operand1] & ~selector) | (m[operand2] &
| selector)
|
| As multiplexing is a universal gate (so long as you have
| access to true and false as constants) you can use this
| to calculate AND/OR/XOR, which are very expensive to do
| in a pure Subleq machine. It also means you can do a MOV
| in a single instruction instead of four (set the
| `selector` to zero in this case). This in turns speeds up
| indirect loads and stores.
| parlortricks wrote:
| I came across your works learning and consuming all things
| Forth and Subleq. It was great to read over how you approach
| things. I wanted to purchase your book but Amazon says
| no...will there be another run?
| howerj wrote:
| Thanks! You should still be able buy it, you might have to
| either click on "Paperback" or "Hardcover", if you want to
| get the kindle edition you have to go to the Amazon webpage
| that serves you country (e.g. if you are in the UK and you
| are on amazon.com you get "This title is not currently
| available for purchase", but if you go to amazon.co.uk, you
| get buy it). That's an odd user interface issue...
| parlortricks wrote:
| Ahhhh Amazon weirdness...all good, i managed to sort it
| out, paperback on its way!
| weinzierl wrote:
| _" There was just one catch: You can't do recursion."_
|
| 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.
| Joel_Mckay wrote:
| Most recursion is about as bad as goto coding methodologies.
|
| 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. =)
| autoexecbat wrote:
| Outside of a university course, if I see recursion in a non-
| FP language I consider it a code-smell
| mikepurvis wrote:
| The only time I ever do it is for tree walking, and then
| it's always a private internal function, so like:
| def process_that_tree(my_tree): def
| _handle(node): # do the things for
| child in node.children: _handle(child)
| _handle(my_tree.root)
|
| The processing can even be brought outside sometimes, or
| the walker can just become a generator, yielding nodes out
| to a regular loop doing the actual work. Either way, the
| recursive part is kept very minimal and easy to reason
| about.
|
| 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.
| munificent wrote:
| 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.
| Arnavion wrote:
| Tree traversal uses stacks / queues unless you're dealing
| with a small tree such that you're sure recursion won't
| blow your stack, or your algorithm can work with tail
| calls and your language guarantees TCO.
| josephg wrote:
| Any balanced tree will be shallow enough that this isn't
| a problem in practice. You'll run out of RAM / hard disk
| space to store your tree before you run out of stack
| space.
| Arnavion wrote:
| There are lots of trees that can't be balanced, like
| tries.
| mannyv wrote:
| Recursion in production code is bad news, because you
| can't control the depth of your call tree.
|
| 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.
| josephg wrote:
| If you're using some sort of balanced tree (red-black,
| AVL or a b-tree of some sort), the depth of the tree is
| guaranteed to be log(n) where n is the number of items.
| If you recursively descend down the tree, the number of
| stack frames involved will never exceed the height of the
| tree.
|
| 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.
| munificent wrote:
| 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_.
| Joel_Mckay wrote:
| "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
|
| =)
| munificent wrote:
| If you're going to make a generalization, I think
| recursion is fine, efficient, and rarely dangerous.
|
| 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.
| Joel_Mckay wrote:
| For many reasons, people often add nesting limits in
| recursive structures to at least constrain how bad they
| behave when something eventually does go wrong.
|
| Parsers are far from immune to these issues.
|
| I think we will have to "agree to disagree" here... =)
| jcgrillo wrote:
| For a fun time, make a nested json blob about 1000 layers
| deep and in python: with
| open('lulz.json') as ayy_lmao: oops =
| json.load(ayy_lmao)
|
| If you parse arbitrary json bytes from the Internet (for
| example, if you have some public Python API with no auth)
| then you have given the world a fun little stacktrace
| generator, and a way to lessen your server room's heating
| bill.
|
| 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.
| naasking wrote:
| > 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 you don't have to worry about for almost
| all scenarios you're likely to encounter.
| klyrs wrote:
| 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 notorious limit that forces
| library writers to roll their own stack. So despite the
| above, I'm actually in the anti-recursion camp.
| hehhehaha wrote:
| Tree traversal almost never makes use of tail call
| recursion. Also, most of the times, you can just use a
| stack object instead of the program stack which saves you
| from insane stacktraces, arbitrary stack limits, and a
| bunch of wasted memory in call frames
| II2II wrote:
| While I am not a fan of recursion, the call stack that
| enables it sounds infinitely better than statically
| allocating space for parameters and return values. Besides,
| it makes some algorithms clearer. That is certainly useful
| in learning environments, including early academic
| research.
| Joel_Mckay wrote:
| Depends on the CPU, in some architectures the stack
| pointers had low finite capacity before overflowing.
| nerpderp82 wrote:
| Recursion is like an inductive proof, you can show it is
| correct and it normally fits on half of a small screen.
| Joel_Mckay wrote:
| 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. ;-)
| EdwardCoffin wrote:
| I'd recommend you read Guy Steele's blog post Why Object-
| Oriented Languages Need Tail Calls [1] and perhaps the essay
| by William Cook [2] and the discussion over on Lambda the
| Ultimate [3]
|
| [1] https://web.archive.org/web/20091206042608/http://project
| for...
|
| [2] https://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf
|
| [3] http://lambda-the-ultimate.org/node/3702
| Joel_Mckay wrote:
| Sure, or just add a polymorphic functor to walk a tree
| autonomously.
|
| There are shorter ways to admit you already sold your soul.
| lol =)
| tome wrote:
| It's interesting because I love using Haskell in a stable
| production environment. In fact I'd hate to use anything
| else!
|
| 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.
| Joel_Mckay wrote:
| I like Haskell in many ways as it shifts ones perspectives,
| but it is just way too easy to leave unpredictable
| behaviors unconstrained. =)
| CyberDildonics wrote:
| I agree. People love making things clever instead of making
| things done.
|
| 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.
| samatman wrote:
| The same argument suggests that a recursive stack traversal
| will never consume more than 64 stack frames, so consuming
| stack frames is no reason not to use a recursive function.
|
| 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.
| CyberDildonics wrote:
| _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 stacks to find data.
| agumonkey wrote:
| 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.
| CyberDildonics wrote:
| 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?
| twoodfin wrote:
| This limitation doesn't just proscribe traditional recursive
| algorithms: Any reentrancy is impossible.
|
| 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.
| ginko wrote:
| If you write a GPU shader in most graphics APIs today you will
| also not have a stack or heap.
| elvis70 wrote:
| And to think that's where we come from. The Intel 8008, the
| ancestor of the x86 processor family, just has a 7-level call
| hardware stack only used by the unconditional and conditional
| call and return instructions. So, there is no push and pop
| instructions. As the only way to access a byte in memory was to
| store the address in the HL register pair (no absolute addressing
| mode) before the load or store instruction and as there was no
| way to disable hardware interrupts, it was almost impossible to
| write useful interrupt routines without some external hardware
| trick.
| PaulHoule wrote:
| For the kind of programs I write for AVR-8 it seems insane to use
| the calling conventions of C, so if I write assembly I can
| sometimes keep the inner loop variables in registers (big
| register file) and otherwise use the methods he describes. I like
| "coloring" functions in an app like that, if I know a red and a
| green function will never be active at once I can reuse
| locals/parameters for them.
| thadt wrote:
| Yes, C's stack usage can be unintuitive when working in a
| constrained environment, especially when accustomed to the
| affordances of desktop operating system. I once joined a
| project where several developers had spent a couple weeks
| trying to track really hard to pin down bugs in several
| subsystems they were developing in a microcontroller codebase.
| They would move things around and the bugs would move. After
| tracing things a bit and setting a trap, I found the places in
| the codebase where the call stack got too deep and was
| scribbling over other data structures.
| JonChesterfield wrote:
| Putting a `out-of-stack? branch` check in every function
| prolog made an embedded chip programmed in C much nicer to
| work with. Cost a few instructions which was contentious but
| definitely a development aid.
| PaulHoule wrote:
| Recursion is a bad thing in embedded systems and generally
| overrated in CS pedagogy.
|
| It can be useful in analyzing algorithms but often in cases
| like search it is a "second best" answer compared to say,
| using nondeterminism.
| dhosek wrote:
| My first assembly was 6502 which kept a call stack in page 3 (128
| levels deep being the maximum call depth as a consequence). When
| I learned 370 assembly, I remember being shocked to discover that
| an application was responsible for maintaining its own call
| stack.
| dhosek wrote:
| (D'oh, not page 3, page _one_. Page 3 on the Apple ][ was
| reserved for & handlers and, IIRC page 2 was the input buffer.
| not2b wrote:
| When I was first starting out a very long time ago, I wrote a lot
| of Fortran (mainly for digital signal processing applications),
| and a couple of times I had to work around the lack of recursion
| by building my own stacks for intermediate results, with arrays
| and a position to keep track of where I was. It was ugly.
| caycep wrote:
| the headline reminded me of "ancient computers" in sci fi games,
| which was essentially a tower of Hanoi problem inmplemented in-
| game
| Ericson2314 wrote:
| Whenever Raymond Chen retires, I am going to be really sad.
| abhinavk wrote:
| Why? I feel he will able to write more.
| Ericson2314 wrote:
| I mean when he stops writing. Fair enough if he does it for
| fun afterwards.
| JoeAltmaier wrote:
| 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 that way. You
| were just on your own.
| benreesman wrote:
| Raymond Chen has to be one of the few OG legends where the title
| of the post alone is just like: "Today is Old New Thing day, and
| that's just going to be the coolest thing I learn today." I
| started salivating before my eyes scanned so far as the domain
| name.
|
| And as usual, worth reading at least one or two more times.
|
| Fucking. Legend.
| le-mark wrote:
| Cobol upto and including the 85 Standard was stackless and
| heapless which is quite a cognitive divide. For those going to
| and coming from that language.
|
| 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.
| tedunangst wrote:
| Just fixed size static buffers guaranteed to overflow.
| HeyLaughingBoy wrote:
| A long time ago (1991 maybe?) one of my first freelance projects
| during my first job out of college was to design an RS232 serial
| multiplexer -- take an incoming serial datastream, parse it, and
| redirect it to one of n outputs based on its header.
|
| 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.
| Sponge5 wrote:
| You should be proud of it, I can't even begin to think about
| programming with these constraints, and I work in embedded.
| billforsternz wrote:
| That is very cool and I say that as someone whose first project
| in my first job (1982) was to write the code for a serial
| multiplexer with a Z80, a 2716 EPROM, Zilog SIOs (or maybe
| DUARTs actually).... and 2K of static RAM. I basically learned
| my craft on the job and there's no way I could have done it
| without the RAM. A few years later I would have relished the
| challenge. Although you are really limiting the complexity of
| the protocol you can deal with ... (perhaps not such a terrible
| thing:).
| smcin wrote:
| '2716 EPROM' was a 16K (2kb x 8) EPROM.
|
| Which customer/sector was your project intended for?
| mytailorisrich wrote:
| Yes, the xx(x) number in the 27xx(x) EPROM series indicates
| the kilo (1024) bits. So indeed this is 2 KiB. This sounds OK
| for the application described, especially as it was no doubt
| written in assembly and obviously bare metal. When it does
| not fit but not far off it's when the fun of code
| optimisation kicks in ;)
|
| Edit: Very interesting how easily available they still seem
| to be according to Google.
| RiverCrochet wrote:
| > 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.
|
| 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.
| greesil wrote:
| It's not ancient if you still do embedded development
| dnedic wrote:
| It really depends on what you classify under embedded.
| Everything more expensive than a Padauk or newer than PIC will
| have hardware support for the stack, and also most likely have
| the heap provided by newlib.
| monocasa wrote:
| > As I recall, some processors stored the return address at the
| word before the first instruction of the subroutine.
|
| 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.
| bsder wrote:
| One of the things that people miss is that a "stack" was not
| _just_ for recursion.
|
| 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.
| deanCommie wrote:
| Another commenter said: "I really liked the Art of Computer
| Programming with regards to this subject. While seemingly
| obsolete, there are a ton of pre-heap / pre-stack algorithms for
| dynamically changing arrays or other data structures."
|
| 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?
| mirkodrummer wrote:
| Very unfortunate that the mobile layout of the devblog has so
| many fixed elements on the side, they are distracting and can't
| navigate the page without feeling some discomfort
| tombert wrote:
| I've been doing functional programming so long that I genuinely
| have a hard time thinking about how I would write things without
| recursion.
|
| 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.
| taeric wrote:
| If it blows your mind to consider the time before call stacks
| were somewhat the norm in computers, you should look into the
| time from before register renaming.
|
| 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.
| gumby wrote:
| This post happens to describe the world of the famous "Goto
| considered harmful" paper.
|
| 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.
___________________________________________________________________
(page generated 2024-04-03 23:00 UTC)