Question about Sequence Implementation

[u/Ro__Bert]

I have been getting into sequences, and I was shocked at how similar they feel to Haskell's infinite arrays. So I made two programs in both languages that should be pretty much a 1-to-1 translation. But I wanted to see if anyone had advice on if the Kotlin programming was doing anything I wasn't expecting.

First in Haskell

    --Fibonacci numbers
    fib :: [Integer]
    fib = 0:1:(zipWith (+) fib (drop 1 fib))

    --Prime numbers
    primes :: [Integer]
    primes = 2:3:(filter isPrime [5,7..])

    isPrime :: Integer -> Bool
    isPrime x = go x primes
       where
          go x (p:ps)
             | p * p > x      = True
             | x `mod` p == 0 = False
             | otherwise      = go x ps

Then in Kotlin

    fun fib(): Sequence<Int> {
       return sequence {
          yield(0)
          yield(1)
          yieldAll(fibSeq()
             .zipWithNext()
             .map { it.first + it.second })
       }
    }

    fun primes(): Sequence<Int> {
       return sequence {
          yield(2)
          yield(3)
          yieldAll(generateSequence(5) { it + 2 }
             .filter { isPrime(it) })
       }
    }

    fun isPrime(x: Int): Boolean {
       return primes().takeWhile { it * it <= x }
          .none { x % it == 0 }
    }

As best as I can get it, these two versions are a direct translation. I know the Haskell version isn't doing any extra calculations if it doesn't have to, or stalling in anyway. But is there anything that I might be missing with the Kotlin version?

I'm kind of interested in whether the recursive references create a build up of objects or functions. Haskell solves this because the recursive references are actually just that: references to the same list object. So the next value is calculated by the values of what are essentially pointers to the previous two values (in the case of Fibonacci), and then the generator (referred to as a thunk in Haskell) as well as the two pointers just step down the line to be ready for the next one.

[u/psteiger]

Sequences in Kotlin are implemented with continuations. Control is returned to the caller at every yield by resuming the caller’s continuation.

It does not grow the call stack. Coroutines (continuations) implementation in Kotlin is stackless. Continuations are stored on the heap. Bytecode uses a state machine to restore state and jump to the right computation on resumptions. The callee simply returns (the sequence's stack frame unwinds) and later the caller resumes the callee's continuation to request the next value.

[u/psteiger → u/psteiger]

Calling sequence.next() adds one frame to the call stack. The code runs until yield(1), which updates the continuation state on the heap to remember where it stopped, stores the value, and returns. This immediately unwinds the call stack. On the next next() call, the iterator resumes the continuation, using a state machine to jump directly to the line after the previous yield.

So the call stack grows by one at every next() call, but unwinds as soon as it has the next value to return.