5 ms·

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

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 5y ago
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 5y ago
  If I can make my functions easily tail recursive, then I can also just write an iteration.
  - nybble41 5y ago
    Iteration is just a special case of tail recursion.
    - auggierose 5y ago
      And tail recursion a special case of iteration.
      - nybble41 5y ago
        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.)
        auggierose 5y ago
        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.
        nybble41 5y ago
        > 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.
        auggierose 5y ago
        Church numerals are nice, yes. Try executing 1000000 + 1000000 in Church numeral representation. Will you get a stack overflow?
        auggierose 5y ago
  - marcosdumay 5y ago
    Yes. But what is your point?
    - auggierose 5y ago
      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.
      - marcosdumay 5y ago
        "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.
        auggierose 5y ago
        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.
turminal 5y ago
Retrofitting the execution environment to your abstractions is typically not a good idea.
- auggierose 5y ago
  Yeah. Like building a computer in the first place. Bad idea.
gumby 5y ago
I’ve been writing recursive code “in the real world” for almost 40 years and your statement seems unrealistic to me.
- auggierose 5y ago
  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_ 5y ago
    > 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 https://en.wikipedia.org/wiki/Leaky_abstraction
    - auggierose 5y ago
      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.
flylikeabanana 5y ago
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 5y ago
  Yeah, I don't want that either. Monads are a fucking plague.

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 5y ago

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 5y ago
If I can make my functions easily tail recursive, then I can also just write an iteration.
- nybble41 5y ago
  Iteration is just a special case of tail recursion.
  - auggierose 5y ago
    And tail recursion a special case of iteration.
    - nybble41 5y ago
      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.)
      - auggierose 5y ago
        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.
        nybble41 5y ago
        > 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.
        auggierose 5y ago
        Church numerals are nice, yes. Try executing 1000000 + 1000000 in Church numeral representation. Will you get a stack overflow?
        auggierose 5y ago
- marcosdumay 5y ago
  Yes. But what is your point?
  - auggierose 5y ago
    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.
    - marcosdumay 5y ago
      "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.
      - auggierose 5y ago
        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.

turminal 5y ago

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

auggierose 5y ago
Yeah. Like building a computer in the first place. Bad idea.

gumby 5y ago

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

auggierose 5y ago
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_ 5y ago
  > 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 https://en.wikipedia.org/wiki/Leaky_abstraction
  - auggierose 5y ago
    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.

flylikeabanana 5y ago

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 5y ago
Yeah, I don't want that either. Monads are a fucking plague.