Providing Co-Monadic Comprehensions

Proposal for adding support for co-monadic comprehensions to Scala.
copied from: https://github.com/scala/scala/pull/5725

This is a proposal (POC) to provide a new keyword (cofor) for co-monadic comprehensions in Scala.
The work is based over Dominic Orchard and Alan Mycroft paper: https://www.cl.cam.ac.uk/~dao29/publ/codo-notation-orchard-ifl12.pdf

If you find the implementation flawed, it is me to blame and not them!

the cofor expression returns a function: (T[A] => B).
The function’s type MUST be stated explicitly in the call-site. e.g.:

val result: Zipper[Person] => Boolean = cofor...

the syntax:

cofor(inputpatten) {
  pattern1 <- gen1
  pattern2 <- gen2
  ...
} yield body

the ‘cofor’ and generator must use types that provide:

def map(A => B)
def extract: A
def coflatMap(T[A] => B)

implementation is much more complex than for desugaring as stated in the paper.

current implementation supports full Scala patterns in the input and generator patterns.
missing:

desugared tree positioning validation (should not affect surrounding code)
quasiquotes/macros/reification – this is the next phase in the implementation.
the flag to control the keyword: -Ycofor-extension
if the flag is not enabled, current Scala code should not be affected.

Plz let me know your thoughts on this.

1 Like

Can someone explain this in English? :wink:

1 Like

Hey @shimib, I’d wager to say that most people in the Scala community aren’t academics. So they’d probably find reading a PL research paper as a prerequisite a bit daunting. Would you be interested in writing up a short summary of co-monadic comprehensions for people here? The worst case scenario would be that everyone learns something :slight_smile:

2 Likes

sure. in a couple of hours :slight_smile:

Also, as a general note, any proposal to change the language must go through the Scala Improvement Process. So if you’re going to write up a summary, consider shaping it into a SIP document :slight_smile:

@heathermiller sure. I’ll start forming a SIP doc. I think i’ll also post an introduction (with example) here.

Motivation:
Consider the following class:
case class StreamZipper[A](left: Stream[A], focus: A, right: Stream[A])
It represents a non-empty stream with a cursor (focus). I.e., there may be elements to the left (stored in reverse order) and maybe elements to the right.

Now, consider the following methods (only signatures):

def map[B](f: A => B): StreamZipper[B]
def extract: A = focus 
def coflatMap(f: StreamZipper[A] => B): StreamZipper[B]

The map method will return a StreamZipper[B] which contains the results of invocation of f over the respective elements of this.
The extract method returns the element at the cursor position.
The coflatMap method returns a StreamZipper[B] which contains the result of invoking f over all the possible cursors.

Now, let’s say we have the following functions:

// returns whether the current cursor in a zipper of ints is between the previous
// and the next numbers.
def isInMiddle(z : StreamZipper[Int]): Boolean = 
  z match {
    case StreamZipper(pi +: _, i, ni +: _) if (pi < i && i < ni) => true
    case _ => false
  }

// counts how many consecutive values of `true` starting from the cursor
def countConsecutiveTrues(z: StreamZipper[Boolean]) : Int  = 
    if (z.focus) 1 + z.right.takeWhile(true ==).size else 0 

and let’s say that we have a zipper of people:

val people : StreamZipper[Person] = ???

We would like to reuse the previous function to get: StreamZipper[(Person, Boolean, Int)] in which every person will be annotated whether its age is inbetween the previous and the next and how many consecutive ‘persons’ are tagged with true!

Without cofor extension:

people.map(p => (p, p.age)).coflatMap { zipperOfTuple =>
  val ages = zipperOfTuple.map(_._2)
  (zipperOfTuple.extract._1, isInMiddle(ages))
}.coflatMap { zipperOfTuple =>
  val tags = zipperOfTuple.map(_._2)
  val persons = zipperOfTuple.map(_._1)
  val count = countConsecutiveTrues(tags)
  (persons.extract, tags.extract, count)
}

With cofor:

val result : StreamZipper[Person] => (Person, Boolean, Int) =
  cofor (p @ Person(_, age)) {
    tag <- isInBetween(age)
    count <- countConsecutiveTrues(tag)
  } yield (p.extract, tag.extract, count.extract)

people.coflatMap(result)

Hi, thanks for this compelling example. (I edited the post to fix formatting and code highlighting)

I think this is something very interesting. That would be great to have support for more « comprehension » syntaxes than just monads (e.g. arrows, applicatives and comonads). I have no idea of how to support them with the fewest possible changes in the core language. One point that I don’t like in your proposal is the fact that you allow developers to write a pattern in an expression position (in cofor (p @ Person(_, age))). This too different from the way Scala usually works. I think we should only support the following, if any:

cofor { p =>
  Person(_, age) <- p
  tag <- isInBetween(age)
  count <- numberOfTruth(tag)
} yield (p.extract, tag.extract, count.extract)

Or maybe?

for case p @ Person(_, age) => {
  tag <- isInBetween(age)
  count <- numberOfTruth(tag)
} yield (p.extract, tag.extract, count.extract)

Also, in the pattern p @ Person(_, age) p appears to get bound to a Person instance. But its usage later on in the comprehension suggests that p is actually a StreamZipper[Person].

Good point @Jasper-M!

Then I would stick to my first proposition:

cofor { p =>
  Person(_, age) <- p
  tag <- isInBetween(age)
  count <- numberOfTruth(tag)
} yield (p.extract, tag.extract, count.extract)

After having a look at the paper it seems to also be the one that’s used by codo .

1 Like

Hi @julienrf, we have to keep in mind that cofor returns a function from a comonad (let’s use Zipper in this example) to some value.

The first “expression” (i’ll refer to it as input is a pattern over the function’s argument.
We can either choose to avoid extraction over the argument (which i think is one of the advantages of this proposal) or use an external extract function in the first generator.

Currently the generators must return a simple value and the patterns on the left of (<- ) are extraction patterns to create different Zippers for each of the pattern variables.

The referenced paper also uses a pattern (only tuples) for the input but states that arbitrary patterns can be supported. I’ve implemented arbitrary patterns into both the input and the generators patterns.

I agree that this is not the conventional use of patterns, however, we are already using this syntax in for generators and i think we can adapt it also to input.
I really that there is much to gain with patterns on the input.

Hi @Jasper-M, patterns in both input and generators describe how to deconstruct A in Zipper[A].
Let’s say that the pattern is p @ Person(n, a) on Zipper[Person].

The desugaring will create:

p: Zipper[Person]
a: Zipper[Int]
n: Zipper[String]

Which can be used with functions accepting the respective zippers.

First, thanks for the explanation! I had seen a link to that work, but hadn’t gotten a chance to understand it—your explanation was helpful (though I won’t claim to get comonads too well).

Second, a general comment: in Haskell, comonadic comprehensions were not added to the core compiler but through a lightweight extension mechanisms (quasiquotes). In general, it would be cool if Scala had good support for quasiquotes as well for such extensions—right now, IIUC, quasiquotes apply only to quoted strings and have enough restrictions they’re not so appealing for this scenario. As it is, comonadic comprehensions need pass a higher bar in Scala than in Haskell, if they need be merged in Scalac (and then again in Dotty), even though both languages are meant to encourage domain-specific languages and extensions. In any case, I don’t know whether comonadic comprehensions pass this bar, I don’t have a strong opinion.

On the concrete proposal:

I think we agree that p @ Person(_, age) should be a pattern. The problem is just where that pattern is written in the concrete syntax. @julienrf claims that noawadays cofor (p @ Person(_, age)) calls function cofor with argument p @ Person(_, age). Of course one could totally use that concrete syntax, it just doesn’t fit with the rest of the language. In comparison, this fits better:

The other confusing thing, though, is that in ALL examples, p @ Person(_, age) is sort-of “ill-typed”, unlike with for comprehensions, because you’re applying Person not to an Int but to a Zipper[Int]. But that’s not specific to any of the concrete syntaxes so it’s not an argument that distinguishes among those.

Compare type-correct
for {Person(name, age) <- persons} yield Person(name, age)
with type-incorrect cofor { p => Person(name, age) <- p } yield Person(name, age) — the latter needs to be, IIUC, ``cofor { p => Person(name, age) <- p } yield Person(name.extract, age.extract). I know both do nothing, but alreadyfor {Person(name, age) <- persons} yield Person(name, age + 1)` is useful—I think writing this sort of identity map is a useful test for pattern-matching-related language features.

Right now, instead, if I see Person(name, age), either in pattern or in expression position, I can be sure name is a correct argument to Person. This might be worth giving up, but makes me a bit uneasy.

I’ve checked the paper and they don’t discuss this (admittedly not huge) annoyance. And to be sure, this is about codo notation itself, not your port to Scala, which seems pretty cool BTW!

3 Likes

@Blaisorblade thanks for the feedback!

You raise in interesting point about the type-safety of the patterns (I.e., the ability to reconstruct).
However, pattern expressions are not necessarily reversible and i don’t think it’s something “from the spec”. For example, extractors with custom unapply already provide non-reversible “matching”.

Also, custom unapply to a non-case class will bring some weird (but eligible) expressions.

Very impressive example.

@shimib, could you add a comparison between cofor and CoKleisli + for working with StreamZipper? I guess that would help people like me understand the difference.

1 Like

@yangbo CoKleisli + for do not provide a decent extraction mechanism from the carried environment. In the specific example, extracting age from Person will become quite cumbersome.
However, if we had Arrow notation it would be somewhat equivalent to the cofor.
In a more complicated example (especially if you need to delve deep into the carried context) cofor will be much simpler than the corresponding arrow notation.
Btw, i definitely think that arrow comprehension should be also considered as an addition to the language.

1 Like