4 ms·

Iteration is just a special case of tail recursion.

by nybble41 5y ago

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))")
        nybble41 5y ago
        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).

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))")
        nybble41 5y ago
        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).