[HN Gopher] Stack Safety for Free?
___________________________________________________________________
Stack Safety for Free?
Author : tekkertje
Score : 45 points
Date : 2021-12-06 13:26 UTC (9 hours ago)
(HTM) web link (hurryabit.github.io)
(TXT) w3m dump (hurryabit.github.io)
| amalcon wrote:
| I'm sort of hesitant to be "that guy", but I've seen this kind of
| thing be a bit of a trap before. The technique of simulating a
| stack on the heap is useful in some situations, but it's very
| misleading to call it a form of safety. It's important to be
| clear about exactly what this buys you, and what it doesn't buy
| you.
|
| The benefit in a case like this is that you use memory a little
| more efficiently (since your stack frames contain exactly what
| you put in them) and you have a larger maximum size (since the
| heap tends to have more addressable space than the stack). This
| buys you more recursive depth (and therefore a larger input)
| before crashing. You can still run out of memory and crash.
| Arguably on systems like 64-bit Linux this is more dangerous,
| since the OOM killer is less predictable than stack overflow
| handling.
|
| Of course it is often worth it to be able to handle the input you
| happen to have on hand, but that's a functional improvement, not
| a safety improvement. It's no substitute for an algorithm that
| just uses less memory.
| The_rationalist wrote:
| Kotlin were the first to introduce the idea in my knowledge
| https://elizarov.medium.com/deep-recursion-with-coroutines-7...
| tobz1000 wrote:
| This seems like a universal-ish mechanism for queueing your
| recursive function's calls onto a dynamically resizeable stack
| (placed in the process's heap). This is pretty cool, but I
| wouldn't say it's "for free", performance-wise, as demonstrated
| by the performance figures in the article. Although it certainly
| makes the transformation cheap, implementation-wise.
| Gadiguibou wrote:
| This seems like such an obvious abstraction, that it's hard to
| believe noone came up with a macro to do this a long time ago.
|
| However, that seems like a sign of a good or well explained idea.
|
| While, I've never seen something similar being used before, I
| wouldn't call it revolutionary since it's not really making the
| function iterative, it's just moving the call stack to the heap.
|
| It would still be a very nice convenience for functions that are
| more elegantly expressed recursively.
| servytor wrote:
| Could this trick be used by ABCL (a Common Lisp implementation on
| the JVM) to allow for tail-call optimization?
| runevault wrote:
| Should be able to. Clojure used trampolines for tail recursion
| at least.
| servytor wrote:
| But Clojure uses 'recur' because you cannot modify the stack
| in the JVM (at least to my knowledge that is the issue with
| the JVM and TCO).
| runevault wrote:
| Right and it uses a trampoline under the hood.
| auggierose wrote:
| I would like to have the option to just mark some functions to
| run on the heap instead of the stack. Without that option,
| recursive functions are really useless and cannot be used in the
| real world.
| nathcd wrote:
| I mean, if your compiler does TCO and you can make your
| function tail recursive, it's usable in the real world, right?
| That's not all recursive functions, but "useless" seems a
| little extreme.
|
| I write plenty of recursive functions in my (real world) job.
| Sometimes they're not even tail recursive ( _gasp_ ) when I'm
| working with small data.
| auggierose wrote:
| If I can make my functions easily tail recursive, then I can
| also just write an iteration.
| nybble41 wrote:
| Iteration is just a special case of tail recursion.
| auggierose wrote:
| And tail recursion a special case of iteration.
| marcosdumay wrote:
| Yes. But what is your point?
| auggierose wrote:
| I don't need recursion that can equally well be modelled
| as iteration. Just take it out of the language. If you
| allow recursion, support it properly.
| gumby wrote:
| I've been writing recursive code "in the real world" for almost
| 40 years and your statement seems unrealistic to me.
| auggierose wrote:
| Good for you. I've been writing code for only about 30 years,
| so maybe you are onto something.
|
| Personally though, I am fed up with abstractions that cannot
| be used when I really need them. Those abstractions are not
| really abstractions. They are gimmicks.
|
| So yeah, I had to go through thousands of lines of code and
| convert it to trampolined code to make it run on my input. I
| got lucky once, and I could just increase the stacksize to be
| large enough. That's often not possible.
|
| So these days, I only use recursion if a) it's just
| exploratory code or b) I know that the environment can
| support a recursion depth adequate for a computer with 64GB
| Ram or more.
|
| To finish my rant, if you really think my statement is
| unrealistic, then you don't the fuck know what you are
| talking about.
|
| Actually, not finished yet. Anyone building recursion into
| their language, and not making sure that recursion can use up
| all the memory available if so needed, is just not doing
| their job properly.
| astrobe_ wrote:
| > Personally though, I am fed up with abstractions that
| cannot be used when I really need them
|
| Abstractions are often leaky [1], this has been known for
| 20 years. Deal with it?
|
| > Actually, not finished yet. Anyone building recursion
| into their language, and not making sure that recursion can
| use up all the memory available if so needed, is just not
| doing their job properly.
|
| You don't "build recursion into [a] language", that's a
| direct consequence of having any form of subroutine call.
| You don't have to do anything except maybe making sure the
| function "sees itself", if you have lexical scoping. Even
| assembly language has recursion. Which makes recursion...
| Not an abstraction at all.
|
| [1] https://en.wikipedia.org/wiki/Leaky_abstraction
| auggierose wrote:
| Leaky abstractions are for people who are too lazy to
| think. And computing is full of them.
|
| And of course you build it into the language. It might
| happen to you by accident, but if you kill somebody by
| accident, it is still manslaughter. Well, maybe not if
| your name is Alec Baldwin.
|
| Look at Apple Metal and the version of C++ they use for
| it. Try to make a recursive call there. Good luck.
| turminal wrote:
| Retrofitting the execution environment to your abstractions is
| typically not a good idea.
| auggierose wrote:
| Yeah. Like building a computer in the first place. Bad idea.
| flylikeabanana wrote:
| Which is why in FP-land, you are already carrying your effect
| system in every corner of the world, so you just eval in the
| effect monad and call it a day.
| auggierose wrote:
| Yeah, I don't want that either. Monads are a fucking plague.
| lmm wrote:
| Yes, this is a standard technique. It's more or less recovering
| the trampoline monad via continuations as a universal monad. You
| can use the same technique to implement other effects as well, if
| you're working in the kind of crazy language that has
| continuations but no monads.
| gopiandcode wrote:
| I would highly recommend that the author look into continuation-
| passing-style - the general construction they discover in their
| blog just seems to be a reinvention of the pretty old observation
| that we can make any program tail-call recursive if we write it
| in a CPS form. In fact, in languages like OCaml, it's fairly
| common to do this transformation to avoid stack overflow
| (typically paired with a Monad), especially when compiling to JS.
| The requirement of generators isn't actually needed - you just
| need first class functions - although, generators and coroutines
| do allow expressing the code in a slightly more concise way.
| Guvante wrote:
| Generators and such are designed to avoid manually writing
| contuation passing style which is generally difficult when you
| need compound state.
|
| Especially since Rust makes manual contuation passing style
| very complex. Generally function pass around references with
| lifetimes bound to the execution of the function. While
| continuation passing style does satisfy the constraints needed
| the compiler can't deduce that thus requiring unsafe code.
|
| Generators being built into the compiler can perform that
| transformation on your behalf and provide the nicer syntax of
| not having to write out your state explicitly.
| rincewind wrote:
| I want this guy to duke it out with the developers of chicken
| scheme
___________________________________________________________________
(page generated 2021-12-06 23:02 UTC)