News for hackers. Stuff that matters.
Re:Stack safety for free? by auggierose on Monday December 06, 2021 @10:31AM (#29460931)
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.
Re:Stack safety for free? by nathcd on Monday December 06, 2021 @11:11AM (#29461505)
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.

Re:Stack safety for free? by auggierose on Monday December 06, 2021 @12:15PM (#29462525)
If I can make my functions easily tail recursive, then I can also just write an iteration.
Re:Stack safety for free? by nybble41 on Monday December 06, 2021 @01:44PM (#29463841)
Iteration is just a special case of tail recursion.
Re:Stack safety for free? by auggierose on Monday December 06, 2021 @05:30PM (#29466561)
And tail recursion a special case of iteration.
Re:Stack safety for free? by nybble41 on Monday December 06, 2021 @08:26PM (#29468108)
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.)
Re:Stack safety for free? by auggierose on Tuesday December 07, 2021 @05:21AM (#29470896)
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.

Re:Stack safety for free? by nybble41 on Tuesday December 07, 2021 @11:36AM (#29474577)
> 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.
Re:Stack safety for free? by auggierose on Tuesday December 07, 2021 @01:15PM (#29476110)
Church numerals are nice, yes. Try executing 1000000 + 1000000 in Church numeral representation. Will you get a stack overflow?
Re:Stack safety for free? by auggierose on Tuesday December 07, 2021 @01:53PM (#29476634)
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))")
Re:Stack safety for free? by nybble41 on Tuesday December 07, 2021 @02:39PM (#29477218)
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).
Re:Stack safety for free? by auggierose on Tuesday December 07, 2021 @04:09PM (#29478262)
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

Re:Stack safety for free? by nybble41 on Tuesday December 07, 2021 @05:58PM (#29479264)
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_...

Re:Stack safety for free? by nybble41 on Tuesday December 07, 2021 @02:18PM (#29476963)
> 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.
Re:Stack safety for free? by auggierose on Tuesday December 07, 2021 @04:00PM (#29478167)
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.

Re:Stack safety for free? by marcosdumay on Monday December 06, 2021 @01:46PM (#29463881)
Yes. But what is your point?
Re:Stack safety for free? by auggierose on Monday December 06, 2021 @05:27PM (#29466523)
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.
Re:Stack safety for free? by marcosdumay on Monday December 06, 2021 @06:06PM (#29466934)
"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.

Re:Stack safety for free? by auggierose on Monday December 06, 2021 @06:23PM (#29467090)
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.

Re:Stack safety for free? by flylikeabanana on Monday December 06, 2021 @01:22PM (#29463544)
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.
Re:Stack safety for free? by auggierose on Monday December 06, 2021 @05:32PM (#29466578)
Yeah, I don't want that either. Monads are a fucking plague.
Re:Stack safety for free? by gumby on Monday December 06, 2021 @11:44AM (#29462017)
I’ve been writing recursive code “in the real world” for almost 40 years and your statement seems unrealistic to me.
Re:Stack safety for free? by auggierose on Monday December 06, 2021 @12:16PM (#29462536)
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.

Re:Stack safety for free? by astrobe_ on Monday December 06, 2021 @01:47PM (#29463894)
> 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

Re:Stack safety for free? by auggierose on Monday December 06, 2021 @05:25PM (#29466508)
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.

Re:Stack safety for free? by astrobe_ on Tuesday December 07, 2021 @01:56PM (#29476686)
> 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.

Re:Stack safety for free? by auggierose on Tuesday December 07, 2021 @05:15PM (#29478913)
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.

Re:Stack safety for free? by turminal on Monday December 06, 2021 @11:28AM (#29461744)
Retrofitting the execution environment to your abstractions is typically not a good idea.
Re:Stack safety for free? by auggierose on Monday December 06, 2021 @12:13PM (#29462485)
Yeah. Like building a computer in the first place. Bad idea.