3 ms·

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

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

auggierose 5y ago
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 https://gitlab.haskell.org/ghc/ghc/-/issues/8189
- nybble41 5y ago
  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_calls_(tail_call_optimisation) https://kangax.github.io/compat-table/es6/#test-proper_tail_...

auggierose 5y ago

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 https://gitlab.haskell.org/ghc/ghc/-/issues/8189

nybble41 5y ago
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_calls_(tail_call_optimisation) https://kangax.github.io/compat-table/es6/#test-proper_tail_...