7 ms·

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 "

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