Mutating a continuation?

[omentic]

I've been trying to figure out how to implement something like Rust's .next() and .peek() explicit-iterator methods effectfully.

In the fake language I've been using to prototype things before implementing them in Effekt, considering continuations as first-class values that are mutated by .resume() and can be assigned to seems to allow for semantics compatible with both effectful, lazy iterators and also explicit .next() and .peek() methods. That linearity / ownership is preserved seems very hard to deal with (but possible?? i saw a recent paper) but also not super relevant for the main conceptual issue I'm hitting.

pub effect Yield[T] {
  yield(T)
}

pub func iter[T](self: List[T]) {
  if let Cons(head, tail) = self {
    do yield(head)
    tail.iter()
  }
}

pub func next[T](self: mut Continuation[()] / Yield[T]): T? {
  // mutates `self`. thus, multiple calls to `.next()` can be chained
  try self.resume() {
    // ownership over `self` is given up upon catching an effect, or evaluating to a value
    yield(x) => some(x)
    // this is matching the value `()` (empty tuple) of type `()` (unit)
    () => none
  }
}

pub func peek[T](self: mut Continuation[()] / Yield[T]): T? {
  // we mutate self here.
  try self.resume() {
    // upon catching a raised effect, `self` is no longer being mutated.
    yield(x) => {
      func wrapped() {
        do yield(x)
        // so we can uniquely mutate `self` again here to resume.
        self.resume()
      }
      // this might not work wrt. ownership and also efficiency
      self = Continuation(wrapped())
      some(x)
    }
    _ => none
  }
}

// An explicit Continuation constructor converts this computation of type () to a Continuation[()].
// Really, this would be implicit, I think - any func taking in a Continuation would wrap its arg in this.
// This is kinda similar to Effekt's blocks??
let iterator = Continuation([1, 2, 3].iter())
assert iterator.next() is some(1)
assert iterator.next() is some(2)
assert iterator.peek() is some(3)
assert iterator.next() is some(3)
assert iterator.next() is none

But this is very far from Effekt's semantics... since there isn't an explicit Continuation type, and instead computations that are treated as zero-arity functions when passed to a function through a {} block, and are called as a standard function instead of with .resume(), with the target of the resume keyword instead implicit in the effect handler. So I'm kind of wondering, is this sort of thing possible to express in Effekt? Are there different features of Effekt's effect-and-handler system that I haven't stumbled across that might be relevant here? Or is this entirely the wrong approach to the issue, conceptually, and does something like .next() and .peek() necessitate operating on some concrete iterator struct?

[omentic]

Does Effekt have some way to express mutable parameters?

I've finally wrapped my head around #108 and was able to implement .zip() using a similar trick. I think that + mutable parameters is all that is needed to implement a .next() and .peek() effectfully... I'd like to be able to write something like this, basically.

def next[T]() {mut self: => Unit / Yield[T]}: Option[T] = {
  try {self(); None()} with Yield[T] {
    def yield(x) = {
      self = fun() { resume(()) }
      Some(x)
    }
  }
}

def peek[T]() {mut self: => Unit / Yield[T]}: Option[T] = {
  try {self(); None()} with Yield[T] {
    def yield(x) = {
      self = fun() { yield(x); resume(()) }
      Some(x)
    }
  }
}

[omentic]

I suppose this doesn't actually make very much sense with "computations" being distinct from "values"... hmm. Unless instead of yielding values directly a .iter() method (or equivalent) instead returned a thunk?

[b-studios]

Hey, sorry for the late response. We have multiple examples of "mutable continuations" hidden somewhere in this repo. For instance here:

https://github.com/effekt-lang/effekt/blob/master/examples/benchmarks/other/generator.effekt

or in a variation also here:

effekt/examples/casestudies/scheduler.effekt.md

Lines 38 to 61 in a41dde5

	def scheduler { prog: => Unit / Proc } = region this {
	var queue: Dequeue[() => Unit at {this, prog}] in this = emptyQueue();
	def run(): Unit = queue.popBack match {
	case None() => ()
	case Some((k, q)) =>
	queue = q
	k();
	run()
	}
	try { prog() } with Proc {
	def yield() = {
	queue = queue.pushFront(box { resume(()) })
	}
	def fork() = {
	queue = queue
	.pushFront(box { resume(true) })
	.pushFront(box { resume(false) })
	}
	def exit() = ()
	}
	run()
	}

and in the issue (#108) that you linked.

Currently computation is always considered immutable, while for values we have vars and the Ref type in the standard library. Your point is interesting, though, and I have to think a bit more about it.

[phischu]

We have just merged #527 (thank you for your comments on that one). It contains a function source, which does what you want (I think), but not in the way you want it (sadly). It has type

def source[A, R] { stream: () => Unit / emit[A] } { reader: () => R / read[A] }: R

and takes a stream that pushes values with emit and a reader that reads values with read and connects the two. You would use it like this:

import stream

def main() = {
  val _ = {
    with boundary
    with source[Int, Unit] { range(0, 100) }
    println(do read[Int]())
    println(do read[Int]())
    println(do read[Int]())
  }
  println("done")
}

The ability to read values is only available in a limited scope, because we allocate the mutable variable next (in your example self) on the stack, and because doing so might use other effects, which are not available in wider scopes.

All that said, we are very happy about feedback on this issue and in general.