Stack safety for free? | Hacker News Reader

Stack safety for free?

hurryabit.github.io

48 pointstekkertje45 comments

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.

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.

Not having to explicitly pass around your state everywhere when you need to resume one routine after calling another is why stacks were invented in the first place! And then when systems began adding concurrent execution of tasks they added these things called processes and threads. And then later the underlying concepts were identified as continuations, generators and coroutines (in order of language-level usefulness).

20 years ago the new, cool advice was that processes and threads were bad. Today, the new, cool advice is that even stacks are bad and it's better to use promises or explicit CPS even in languages that predominately rely on implicit function call stacks. Yet function call stack semantics work so exceedingly well that the people who dislike them rely on them in ways they can't even appreciate. Ditto for processes/threads.

Fortunately there are a few languages where the designers and maintainers have the good sense to understand the original function of those abstractions, their relationship to concurrency, and to carry them forth; such as Java (Project Loom) and OCaml (new async runtime--see "One-shot Algebraic Effects as [Stackful, Asymmetric] Coroutines"). Of course, underneath they use simpler mechanisms (e.g. CPS) to present those abstractions, but the majority of the time that's exactly what you want--the OS and compiler to deal with that crap (mostly low-level, irreducible instrumentation for invoking functions) so you don't have to.

I feel you aren't being fair here. Stacks are an implementation of being able to resume execution after a unit of work is done. That is what is wanted.

Rust has generators and async await which covers the most popular form of them. General generators aren't in only due to Rust having a hardcore backwards compatibility guarantee that other than not having an ABI is one of the strongest out there.

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.

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.

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.

> I demonstrate how to (ab)use generators/coroutines to transform any recursive function into an iterative function with nearly zero code changes.

That's not abuse. Reversing consumer/producer calling protocols (i.e. reversing caller/callee relationship) is exactly the fundamental purpose of generators and coroutines. It's a useful insight, nonetheless, for those exploring the fundamental problem and solution space regarding concurrency and, more generally, the reification of execution flow.

I want this guy to duke it out with the developers of chicken scheme

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.

Kotlin were the first to introduce the idea in my knowledge https://elizarov.medium.com/deep-recursion-with-coroutines-7...

Could this trick be used by ABCL (a Common Lisp implementation on the JVM) to allow for tail-call optimization?

Should be able to. Clojure used trampolines for tail recursion at least.

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).

Right and it uses a trampoline under the hood.

Since "recur" only allows to recurse to the closest recursion point (a loop or the enclosing function definition), what if it just used JVM's "goto"? Or, if the JVM didn't have a goto, but any kind of iteration construct, used that instead? Then it doesn't have to use a custom stack or allocate anything on the heap.

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.

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.

If I can make my functions easily tail recursive, then I can also just write an iteration.

Iteration is just a special case of tail recursion.

And tail recursion a special case of iteration.

No, tail recursion is more general than iteration—it can be used to implement arbitrary control structures, without needing extra constructs such as conditions. (E.g., this is how Smalltalk implements if/then/else with only blocks and methods.)

I am not sure that it is more general than iteration; after all, you still need to test a condition for if/then/else, otherwise it is not if/then/else.

Anyway, I am all for allowing tail recursion in a language, if it is supported properly by the compiler/interpreter. Just forbid general recursion, if you don't intend to support it properly.

> after all, you still need to test a condition for if/then/else, otherwise it is not if/then/else

The way this works in Smalltalk is that primitives (e.g. equality on numbers) return an object which is either `true` or `false`. These object each have their own implementations of methods such as `ifTrue:` and `ifFalse:` which accept code blocks. `true ifTrue: [ … ]` always runs the given code block, while `false ifTrue: [ … ]` never runs it. At a machine-code level the comparison primitives are most likely implemented with native conditions and branches, and the VM bytecode does include conditional branches for the sake of optimization, but in terms of the high-level language it's all based on the equivalent of C++ virtual method calls or C function pointers. Smalltalk has no syntax for conditions, or any syntactic equivalent of the C switch statement. (A dictionary or array of code blocks is typically used instead.)

Technically you can do without the comparison primitives if you encode your data in certain ways, e.g. using Peano numbers (and switching to Lambda Calculus):

  false = λt. λf. f
  true  = λt. λf. t

  zero =     λf. λx. x
  succ = λn. λf. λx. f (n f x)
  one  = succ zero
  two  = succ one
  …

  isZero = λn. n (λx. false) true

Code like `if (n == 0) { A } else { B }` would then become simply `(isZero n) A B`. Which gives you the same result without any language support for conditions, comparisons, or even booleans—just functions.

Church numerals are nice, yes. Try executing 1000000 + 1000000 in Church numeral representation. Will you get a stack overflow?

The following Swift code gives me a "Bad Access", already for 100000. Wouldn't it be nice if that could execute without problems on my 64GB RAM iMac Pro?

    import Foundation

    typealias T = ()

    typealias ChurchNum = ((T) -> T, T) -> T

    func zero() -> ChurchNum {
        return { (f, x) in x }
    }

    func succ(_ g : @escaping ChurchNum) -> ChurchNum {
        return { (f, x) in f(g(f, x)) }
    }

    func add(_ g : @escaping ChurchNum, _ h : @escaping ChurchNum) -> ChurchNum {
        return { (f, x) in h(f, g(f, x)) }
    }

    func numeral(_ n : Int) -> ChurchNum {
        var z : ChurchNum = zero()
        for _ in 0 ..< n {
            z = succ(z)
        }
        return z
    }

    func realise(_ g : ChurchNum) -> Int {
        var n : Int = 0
        func f(_ x : T) -> T {
            n += 1
            return x
        }
        g(f, ())
        return n
    }

    let x : ChurchNum = add(numeral(100000), numeral(100000))

    print("x = \(realise(x))")

On the other hand, this nearly identical program in Haskell runs just fine on my system in interpreted mode with a maximum resident size of about 160M, and less than 15M when compiled:

  {-# LANGUAGE RankNTypes #-}
  module Main where
  
  type ChurchNum = forall x. (x -> x) -> x -> x
  
  zero :: ChurchNum
  zero = \f x -> x
  
  succ' :: ChurchNum -> ChurchNum
  succ' g = \f x -> f (g f x)
  
  add :: ChurchNum -> ChurchNum -> ChurchNum
  add g h = \f x -> h f (g f x)
  
  numeral :: Int -> ChurchNum
  numeral 0 = zero
  numeral n = succ' (numeral (n - 1)) 
  
  realize :: ChurchNum -> Int 
  realize g = g (+1) 0
  
  main :: IO ()
  main = do
     let x = add (numeral 100000) (numeral 100000)
     putStrLn ("x = " <> show (realize x))

I must conclude that there is something wrong with either the Swift compiler or your environment for this to fail with "Bad Access" on such small inputs. The Haskell version works on sums up to at least 20M, though the memory requirements become somewhat alarming (1.3 GiB).

That Haskell implements closures properly should come at no big surprise. I guess the problem is with Swift. I wonder what happens in Java with the same code. Or Kotlin. Or Typescript.

I also wonder, what about recursion in Haskell? Is it limited by the stack size as in more conventional languages?

Probably Haskell just allocates a very large stack size, and does it otherwise in the standard way. Otherwise it should be able to do much more than 20M.

There is some talk about it here: https://gitlab.haskell.org/ghc/ghc/-/issues/8189

Haskell has a traditional C-style stack, but it's usually very small (a few KiB). The evaluation model is very different from most other languages; recursive definitions do not necessarily result in recursive machine code, and almost all allocation is done on the heap. Certain rare forms of pathological code (not recursive definitions in general) can result in stack overflows. The cause is usually something like extensive recursion (which here includes iteration) without any other memory allocation or thunk evaluation.

In any case, the point was not that we should all use recursion on Church-encoded Peano numbers for computation, since that is obviously very inefficient, but rather that tail recursion in particular—which does not result in excessive stack use, when implemented sanely—is a more general construct than iteration. It can be used to implement iteration, of course, but also other control flow patterns like state machines and coroutines which would otherwise require additional language support. The only major obstacle is poor language implementations, mostly for imperative languages (including Java), which insist on storing contextual data on the stack which is provably no longer needed by the program. Kotlin is a bit better but still hampered by the limitations of the JVM, so some kinds of tail calls (not direct recursion) still use stack space. EMCAScript 6 specifies guaranteed tail-call elimination, which should benefit Typescript, but Safari appears to be the only major environment which gets it right so far[0].

[0] https://kangax.github.io/compat-table/es6/#test-proper_tail_...

> Try executing 1000000 + 1000000 in Church numeral representation. Will you get a stack overflow?

The sum is just function composition, so not likely. In terms of using the sum, it depends on the function being applied and whether the evaluation model is lazy or strict. (And your stack size, of course.) The isZero function I gave above, for example, only needs to process the outermost "succ" or "zero" and the rest is ignored, which is perfect for lazy evaluation:

  isZero zero
    = (λn. n (λx. false) true) (λf. λx. x)  -- def. of isZero and zero
    = (λf. λx. x) (λx. false) true          -- β-reduce n
    = (λx. x) true                          -- β-reduce f
    = true                                  -- β-reduce x

  isZero (succ N)                                           -- for any N
    = (λn. n (λx. false) true) ((λn. λf. λx. f (n f x)) N)  -- def. of isZero and succ
    = (λn. λf. λx. f (n f x)) N (λx. false) true            -- β-reduce n
    = (λf. λx. f (N f x)) (λx. false) true                  -- β-reduce n
    = (λx. false) (N (λx. false) true)                      -- β-reduce f
    = false                                                 -- β-reduce x

Of course, you can use other, more efficient representations in place of Peano numbers, such as Church-encoded lists of bits. Peano numbers are better suited for demonstrating the concept due to their simplicity. Lambda calculus doesn't really have a concept of "stack overflow" in any case. The point was that you can express both loops and conditions as well as more general structures such as state machines and continuations through (recursive) function calls, but—at least so far as I am aware—there is no way to similarly model data and generalized control-flow (other than loops, obviously) purely in terms of iteration. This is precisely because iteration constructs are more structured than recursion, and consequently have a narrow range of applications.

If you want to model things, maybe use a logic instead.

If you want to compute, then things like stack overflow matter very much. See my example in Swift.

Is recursion helpful? Of course! Is tail recursion more useful than just the normal control structures like iteration that are already at your disposal? I doubt it, but as I said before, I wouldn't mind having properly implemented tail recursion at my disposal.

Yes. But what is your point?

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.

"X is optional" is completely different from "X is not suitable for the real world".

Everything in a modern language is optional, but people are not rushing to program in a assembly.

Recursion that cannot support arbitrary recursion depths is not optional, but broken. Going from a high-level programming language to assembly is going down the level of abstraction. I don't recommend that, unless there is a really good reason to. Iteration and tail recursion is the same level of abstraction.

I am not arguing against recursion. I am saying, do it right. Otherwise it is useless.

Retrofitting the execution environment to your abstractions is typically not a good idea.

Yeah. Like building a computer in the first place. Bad idea.

I’ve been writing recursive code “in the real world” for almost 40 years and your statement seems unrealistic to me.

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.

> 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

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.

> Leaky abstractions are for people who are too lazy to think

Worthless blanket statement.

> Look at Apple Metal and the version of C++ they use for it.

That's a very specific case of a shader compiler that is disguised as C++. It has a terrifying list of restrictions (for a C++ programmer), and I would say that recursive calls are the least of your problems there.

Obviously, it is not a design failure but a set of hard constrains that lead to those restrictions. Of course they would give you recursion happily if they could. People who can do that sort of compiler are not idiots.

It just shows that you understand little about languages. Yet you think you are in position to comment on language implementers' and designers' jobs. Say hello to Dunning and Kruger.

My example shows that recursion is a design choice. It doesn't "just happen to you".

But you are right. You can implement recursion properly by just implementing function calls properly, and making sure that you are not limited by an arbitrary and usually small stack size. It's just that if you don't have recursion, you usually don't have a need for deep stack sizes either.

By the way, citing tropes like "leaky abstraction" and "Dunning and Kruger" is exactly the kind of lazy thinking I am talking about.

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.

Yeah, I don't want that either. Monads are a fucking plague.

Reply on news.ycombinator.com