Get current contiuation in Scala

Question

Haskell has a function for getting the current continuation

getCC = callCC (\c -> let x = c x in return x)

How to write a similar function in Scala?

E.g. function callCC presents in cats.ContT. How could we use it?

I've tried many ways, but I can't make ends meet..

Mateusz Kubuszok · Accepted Answer

Let's implement this getCC ("get current continuation") in Scala.

For starters, let's understand what is actually happening in Haskell. When we look at the docs and sources we'll find:

newtype ContT (r :: k) (m :: k -> Type) a // or
newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r }

class Monad m => MonadCont (m :: Type -> Type) where
  callCC :: ((a -> m b) -> m a) -> m a

instance forall k (r :: k) (m :: (k -> Type)) . MonadCont (ContT r m) where
  callCC = ContT.callCC

MonadCont (ContT r m)
  callCC :: ((a -> ContT r m b) -> ContT r m a) -> ContT r m a

So what we see here:

we are defining a newtype, a way of using an existing type, giving it a new name and then hiding from the rest of the code the actual type, so that all interaction with that type will go only through our API - Scala 3's counterpart would be opaque type, but in the past it was often done with wrappers extending AnyVal, or sometimes plain wrappers. Cats' decided to use a plain class:

// counterpart to
//   newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r }
// where
//   r becomes A
//   m becomes M[_]
//   a becomes +B
//   runContT :: (a -> m r) -> m r becomes protected def runAndThen: AndThen[B => M[A], M[A]]
sealed abstract class ContT[M[_], A, +B] extends Serializable {
  final def run: (B => M[A]) => M[A] = runAndThen
  protected def runAndThen: AndThen[B => M[A], M[A]]
  // ...
}

but we are not defining all that continuation magic for ContT type only, no, we are creating a separate type class MonadCont which defines function callCC, and you could provide an instance for various different types. ContT is just one of them. If we wanted to express it in Scala 3, it would be:

trait MonadCont[M[_]: Monad]:
  def callCC[A, B](f: (A => M[B]) => M[A]): M[A]

object MonadCount:
  // If you are comparing the code:
  // Haskell uses name r like result
  given [R]: MonadCont[[A] =>> ContT[M, R, A]] with
    def callCC[A, B](f: (A => ContT[M, R, B]) => ContT[M, R, A]): ContT[M, R, A] = ???

in Cats however things are a bit simpler, so callCC is defined directly in ContT companion object, and it is defined only for ContT so it looks like this:
```
def callCC[M[_], A, B, C](f: (B => ContT[M, A, C]) => ContT[M, A, B])(implicit M: Defer[M]): ContT[M, A, B] =
```
just by comparing the code we can see, that when Haskell code uses generic m in context of ContT[M, R, A] it is NOT just M but WHOLE ContT[M, R, *]

Ok, so let's move to getCC part:

getCC is defined in Haskell more or less as

getCC: m -> m (m a)
getCC = callCC (\c -> let x = c x in return x)

that m -> m (m a) is important but only with the knowledge that m is ContT[M, R, *] we can actually decode the type signature, and what it would look like in Scala:
```
def getCC[M[_], R, A]: ContT[M, R, ContT[M, R, A]] = ???
```

now we must use types to guide our implementation. We'll start with some stubs:

def getCC[M[_]: Defer, R, A]: ContT[M, R, ContT[M, R, A]] =
  // We'll start with abstract types, and then figure out
  // the concrete types that would make them work
  type X
  type Y
  type Z
  // reminder what callCC signature looked like:
  // def callCC[M[_], A, B, C](f: (B => ContT[M, A, C]) => ContT[M, A, B])(implicit M: Defer[M]): ContT[M, A, B]
  ContT.callCC[M, X, Y, Z] { (c: (Y => ContT[M, X, Z]) =>
    // I only created this val to annotate the returned type.
    // We'll get rid of it soon.
    val result: ContT[M, X, Y]) = ???

    result 
  }

but we know what our result type has to be - ContT[M, R, ContT[M, R, A]] - so what values of X and Z would make it type check?

def getCC[M[_]: Defer, R, A]: ContT[M, R, ContT[M, R, A]] =
  type X = R
  type Y = ContT[M, R, A]
  type Z
  ContT.callCC[M, X, Y, Z] { (c: (Y => ContT[M, X, Z]) =>
    // this is: ContT[M, R, ContT[M, R, A]]
    val result: ContT[M, X, Y]) = ???

    result 
  }

let's substitute X and Y and eliminate type aliases:

def getCC[M[_]: Defer, R, A]: ContT[M, R, ContT[M, R, A]] =
  type Z
  ContT.callCC[M, R, ContT[M, R, A], Z] { (c: (ContT[M, R, A] => ContT[M, R, Z]) =>
    val result: ContT[M, R, ContT[M, R, A]]) = ???

    result 
  }

before we figure out Z we need to stop for a moment. The implementation code was:
```
getCC = callCC (\c -> let x = c x in return x)
```
We have to be reminded that in Haskell return is a function from Monad typeclass used to... wrap the value returned in do comprehension. In other word it's what Cats knows as def pure method in the Monad type class. So that lets us adjust the code to this:
```
def getCC[M[_]: Defer, R, A]: ContT[M, R, ContT[M, R, A]] =
  type Z
  ContT.callCC[M, R, ContT[M, R, A], Z] { (c: (ContT[M, R, A] => ContT[M, R, Z]) =>
    val x = ???

    val result: ContT[M, R, ContT[M, R, A]]) = ContT.pure(x)

    result 
  }
```

further analysis of types lets us figure out the types that needs to be passed into pure to get the expected result - in particular what is x:

def getCC[M[_]: Defer, R, A]: ContT[M, R, ContT[M, R, A]] =
  type Z
  ContT.callCC[M, R, ContT[M, R, A], Z] { (c: (ContT[M, R, A] => ContT[M, R, Z]) =>
    val x: ContT[M, R, A] = ???

    // we can drop "val result = ...; result" from now on
    ContT.pure[M, R, ContT[M, R, A]](x)
  }

so far, so good, now we only need to figure out how x comes to be and what is Z. The hint is in Haskell definition: let x = c x. Lets try to write it in Scala:

def getCC[M[_]: Defer, R, A]: ContT[M, R, ContT[M, R, A]] =
  type Z
  ContT.callCC[M, R, ContT[M, R, A], Z] { (c: (ContT[M, R, A] => ContT[M, R, Z]) =>
    val x: ContT[M, R, A] = c(x) // doesn't compile

    ContT.pure[M, R, ContT[M, R, A]](x)
  }

putting compiler warnings aside (using val x in its own definition is not allowed) this code would make sense if c method returned ContT[M, R, A]]... but it returns ContT[M, R, Z]]... so Z = A

def getCC[M[_]: Defer, R, A]: ContT[M, R, ContT[M, R, A]] =
  ContT.callCC[M, R, ContT[M, R, A], A] { (c: (ContT[M, R, A] => ContT[M, R, A]) =>
    val x: ContT[M, R, A]] = c(x) // still doesn't compile

    ContT.pure[M, R, ContT[M, R, A]](x)
  }

now we only have to solve the last issue - make val x = c(x) compile. The problem comes from an eager evaluation - in Haskell everything is lazy, so there is no such issue that when we evaluate x we are immediately calling c(x), but to evaluate c(x) we need to know the value of x, etc. It's one of the reasons why ContT uses Defer[M] a lot - to introduce that lazy evaluation which would let you create the value without a circular dependency in its initialization. So, lets just use some way of deferring the content of x but still creating a reference to x. One such way I found was through lazy val and ContT.later (which happens to take as by-name param, what .run is returning):
```
def getCC[M[_]: Defer, R, A]: ContT[M, R, ContT[M, R, A]] =
  ContT.callCC[M, R, ContT[M, R, A], A] { (c: (ContT[M, R, A] => ContT[M, R, A]) =>
    lazy val x: ContT[M, R, A] = ContT.later(c(x).run)

    ContT.pure[M, R, ContT[M, R, A]](x)
  }
```

Then you can make this method an extension method on ContT companion object, e.g. for Scala 3 it would be

extension (contT: ContT.type)
  def getCC[M[_]: Defer, R, A]: ContT[M, R, ContT[M, R, A]] =
    ContT.callCC[M, R, ContT[M, R, A], A] { (c: (ContT[M, R, A] => ContT[M, R, A])) =>
      lazy val x: ContT[M, R, A] = ContT.later(c(x).run)

      ContT.pure[M, R, ContT[M, R, A]](x)
    }

and as you already verified it works:

import cats.data.ContT
import cats.Defer

extension (contT: ContT.type)
  def getCC[M[_]: Defer, R, A]: ContT[M, R, ContT[M, R, A]] =
    ContT.callCC[M, R, ContT[M, R, A], A] { (c: (ContT[M, R, A] => ContT[M, R, A])) =>
      lazy val x: ContT[M, R, A] = ContT.later(c(x).run)

      ContT.pure[M, R, ContT[M, R, A]](x)
    }

// Testing

import cats.effect.IO
import cats.effect.unsafe.implicits.global
import scala.concurrent.duration.{Duration, MILLISECONDS}
import java.time.LocalDateTime

val start = LocalDateTime.now()

// It ticks for some times
def loop =
  for {
    gotoLabel <- ContT.getCC[IO, Unit, Unit]
    _         <- ContT.liftF(IO.sleep(Duration(1000, MILLISECONDS)))
    _         <- ContT.liftF(IO.println("Tick"))
    now       <- ContT.liftF(IO{LocalDateTime.now()})
    _ <-      if (now.getSecond % 20 != 0) gotoLabel
              else                         ContT.liftF(IO.unit)
  } yield ()
  
loop.run(_ => IO.println("Done")).unsafeRunSync()

I would not be completely sure it always works - I'd suggest putting a lot of tests precisely because we have to manually address this eager vs lazy value problem ourselves, but it should pretty much explain the idea.

Notice, how much effort went into manually resolving all kind of type parameters. (And in understanding what is going on in general, it's pretty counterintuitive, and I have to learn this style anew every time I meet it again.) In Haskell type resolution works in a different way and it allows to just skip it (what other issues it brings I'll leave to Haskellers to explain). But it is definitely opaque to read, hard to debug, and difficult to maintain. I may see its use case in some internal logic that only a few people have to tinker with (and only if it actually brings some value!), but I'd definitely recommend against using it commonly in codebase and in business logic.

Get current contiuation in Scala

Answers (1)

Related Questions