Caprese Alternative

[fwbrasil]

Caprese is a major risk for Kyo's progress. Its development has been happening with little involvement from effect system developers, the proposed abstractions don't seem principled in the FP sense of programming with values, nor are they reusable in Kyo, and it might end up baking in a concrete effect system into the language itself.

In order to provide a new avenue for Kyo's evolution that mitigates this risk, the goal of this ticket is to provide a research compiler plugin to enable seamless direct syntax. The plugin should be generic and reusable with other effect systems as an alternative to Caprese. Initial design idea:

First-class Purity

A key challenge when performing the transformation from direct syntax to monadic composition is the risk of impure code changing the execution control flow and making the transformation invalid. Kyo and other effect systems rely on the user's discipline to suspend any impure code in an IO effect, but that's an error-prone approach that requires a level of discipline newcomers are typically not accustomed to. The convenience of the direct syntax and similarities to solutions in languages like Python make misuse even more likely to happen.

I've been thinking about the different ways we could introduce first-class support for expressing pure code in Scala to overcome this challenge. One alternative is introducing something like a fun keyword to be used in place of def or defining a new kind of pure function like T ~> U instead of T => U (I think I saw something like that in Caprese some time ago). The main challenge of such approaches is being able to also express that a class constructor is pure.

I'm leaning more towards introducing a new pure keyword to be used as a modifier for classes, constructors, and methods:

// an example of a pure method
pure def myPureFunction(i: Int) = i + 1

// all members, including the constructor, are automatically marked as pure as well
pure class MyPureClass(v: Int):
         def alsoPure = 42

// an example of a class with pure and impure members
class MyMixedClass pure (i: Int): // note the pure constructor
	pure def aPureMethod(j: Int) = i + j
	def anImpureMethod(j: Int) = println(i + j)

// we'd also need a way to declare pure anon functions
pure trait ~>[T, U]:
	def apply(v: T): U

It seems the rules for validating purity could be relatively straightforward:

1. A pure member can only invoke other members also marked as pure, including constructors.
2. For compatibility with pure code not using the pure modifier, which includes standard library APIs, we could compile a static set of pure symbols and add it to the plugin.
3. We should also provide a way for users to extend the static set of pure symbols.
4. Impure language constructs like var, try, throw, etc., would be disallowed in pure members.

Effectful Types

Effectful types like Kyo’s pending type, ZIO, and IO would need to provide APIs the same way they do for for-comprehensions, with no need for an implicit Monad or specific interface. It's not clear to me what would be a good syntax to express them, but we'd need a way to mark the type parameter that specifies the "result" type of the computation:

// maybe as an annotation?
type <[+T @effectful, -S]

type ZIO[+R, -E, T @effectful]

type IO[T @effectful]

Effectful types would have special type-checking behaviors:

1. Impure code would see the effectful type with its regular methods and type signature.
2. Pure code would be able to reference an effectful type only by its "result" type.
3. Methods that return an effectful type can use impure by-name parameters, allowing IOs(println(1)) for example.
4. Effectful types would be considered pure by default, without the need for the modifier, although they may use impure code internally. The developers of effectful types would be responsible for ensuring their purity.

With these building blocks, Kyo could be used in the following way:

// regular monadic composition (`Fibers.init` returns a `Fiber`)
def a: Int < Fibers = Fibers.init(1).flatMap(_.get).map(_ + 1)

// it’d continue invalid to reference an effectful type by its result type in impure code
def b = Fibers.init(1).get + 1 // compilation failure

// but a pure member can only reference the effectful type by its result type (`Fiber`)
pure def c: Int < Fibers = Fibers.init(1).get + 1

// even the regular members of the effectful type wouldn’t be accessible in a pure member
pure def c = Fibers.init(1).map(_.get) // compilation failure

// by-name parameters of methods that return effectful types would allow impure code
pure def d: Int < IOs = IOs(scala.Console.in.readLine()).toInt

Essentially, types like Int < Fibers, ZIO[Any, Throwable, Int], and IO[Int] would behave as Int in pure members. Any and every use of them implies a monadic bind by the syntax sugar transformation. An important imitation is that a pure member must use at most one effectful type, as it’s not possible to mix different monads like Kyo’s pending type and ZIO.

Notes

• Please don't take this design as set in stone. The goal here is to explore something in this direction, not prescribe the final design.
• I think dotty-cps-async might have something similar. I saw a compiler plugin but I couldn't find documentation for it.
• I wonder if we could build something similar using annotation macros instead, since it might be easier to maintain in the long term.
• I'd prefer to have an initial implementation of the solution before considering submitting it as a SIP proposal. I wouldn't rule out Kyo using the research plugin in the long term or even forking the compiler if needed to guarantee the success of the project.
• We'd need to check if the transformation from direct to monadic can be done generically for effectful types with multiple type parameters with different variance annotations like ZIO.
• I think an important challenge is ensuring the new type checking behavior would work well in IDEs, but I don't think that should block the development and could be addressed as a follow-up.

[rssh]

One-page documentation about the dotty-cps-async compiler plugin here: https://rssh.github.io/dotty-cps-async/BasicUsage.html#direct-context-encoding-experimental. In short, when we see a method with implicit CpsDirect[F] parameters (can be with carrying, i.e., a method which returns context function), let's it m(a:A)(using CpsDirect[F]): B then we transform this method into a monadic form: m(a:A)(using CpsMonadContext[F]):F[B].

Note that with an effect system, we can do better than dotty-cps-async: we can catch not application of F[_] (in effect-system case, F[_] is something like the composition of effects, In kyo terms we can say something like: F[X] = (A>B> .. )[X], so we can catch in parameters something like CpsDirect[A], CpsDirect[B], ...C, and assemble an F[(set-of-used-effects)] for each transformed method. This can be one of the possible student projects in GSoC-2024.

Ok, not let's try to understand the approach described here as @effectfull and how this differ from Capreso.

1. What means T@effecfull: Does this means that the annotated effect type is something like type of effect (i.e. IO, FileSystem, ...etc). If yes, how does this differ from the capreso definition: T {*} ? At first glance, this is the same.
2. Pure functions. As I understand:
   pure def c: Int < IOs = IOs(i + 1) + 1
   is analog to
   def c: (x:IOs') ?=> IOs(i+1)+1
   in Capresso encoding. (where IOs' is the type that tracks the IO effect).
   Or not -- maybe from description it's more like
   def c: (x:IOs' =>. IOs(i+1) ) + 1
   I.e., it looks like we have IO(x+1) in the proposed syntax. [without call methods on IO] in Carpeso is represented by context function from effect context.

Alternative encoding makes sense because using context functions for pure computations can be annoying, especially when we have many effects.

I can imagine this as syntax sugar on top of Capreso's capabilities. Could this be semantically different from capabilities (?)—need to think. (Find an illustrative example.)

• Using annotation macroses: currently, they are useless for this case because changes from annotated types are local to type and can not be propagated to the other part of the program. (I.e., it is impossible to change how types are visible from the outside via annotation macros). But here we need a global program transformation.

Interesting. I will think about this. A helpful step might be to write a few simple examples in such a hypothetical style and compare them with other approaches.

[rssh]

also, after some thinking, I can't understand the example.
I.e.

// even the regular members of the effectful type wouldn’t be accessible in a pure member
pure def c = Fibers.init(1).map(_ + 1) // compilation failure

If the result type of Fibers.init is. <[Int, Fiber] then a map is totally fine. (pure function over monad]).
The compilation failure should be:

pure def c = Fibers.init(1) + 1   //. real compilation failure.

UPD 1: Now I understand

Axx, things changes when you start thinking that pure should mean 'monadic' or effect-gathering, not 'pure'.

effect-gathering def c:  = Fibers.init(1) + 1   //correct,  

effect-gathering def c:  = Fibers.init(1).map(_ + 1)   // incorrect,  becoise Fibers.inif(). is int here.   

Ok, dotty-cps-async does something similar. (analog of pure (which I understand as effect-gathering using CpsDirect[F] in parameter)

The difference is the result type. In dotty-cps-async compiler plugin returns the result type visible to the user as return type, therefore we receive
In dotty-cps-async:

def c(x:Int)(using CpsDirect[F]):Int  =  op-in-F(x) + 1  
//. c:  Int => CpsDirect[F]. ?=> Int.   //. for user
//. c:  Int => CpsMonadContext[F]. ?=> F[Int]   //. In the compiler

in proposed syntxt:

effect-gathering[F] def c(x:Int): F[Int]  =  op-in-F(x) + 1  
//. c:  Int => F[Int] 

This solves the problem of (choosing a type of coloring), which appeared when using the cps-async-plugin: you always have two ways of writing a function, in the direct style or monadically. Result types are different; therefore, if you write a library, you should know what result types are preferable to the clients of these libraries.

Proposed encoding solves this problem on the price of changing the function signatures and possibly changing the core typing rules for monadic. There exists yet one interesting way of interpretation (this can be a special case for a set of implicit conversions. enabled inside effect-gathering function).

UPD 2

I.e. if we have enabled implicit conversion from F[Int] to Int inside effect-gathering function (or for each operation on int write a wrapper operation over F[Int] with the same number of parameters), then this will become possible in the current scala after typing:

given monadicUnlift[F[_],X](using Purifier[F]):Conversion[F[X],X] = {
     @compileTimeOnly(...)
}

@effectgathering
def  c(x:Int)(using Puryfier[F]): F[Int] =
   op-inside-F(x) + 1

   

In such case this will be possible with macro-annotations.

Upd 4

(Sorry for the set of updates, it's reflect that I'm slow)

Interesting, that this functionality was already implemented in the dotty-cps-async as automatic coloring. And later - dropped in the favor of direct context encoding. (some history is https://github.com/rssh/notes/blob/master/2021_06_27_automatic-coloring-for-effects.md and current state is here: https://rssh.github.io/dotty-cps-async/AutomaticColoring.html
)

It's. was dropped for social reasons: people were afraid to use it, despite of existence of preliminary analysis which flags incorrect usage. Your idea is solving this too: when we have a Purifier[F] in the scope, then another usage (i.e., map, passing as parameters, etc.) is illegal, so probably fear of incorrect usage will be eliminated.

[rssh]

Upd.5. (will switch to many-comment mode)

If we want implement this in macros (i.e. after typing), we have two visible problems (except need for extra Purifier) clause:

1. assigning to variables:

//inside effect-gathering fun:
val. x = F[doSomething]
val y = x+1 
val z = x+2 

Implicit conversions for satisfying typer will be inserted in y and z , so we will need a technique for reverting this (i.e. memoization of x)]
2. discarding values. i.e.

   def fprints(s:String):  F[Unit]
// inside efffect-gatherign fun:

 fprings('Hello')

Macros can insert a call to effect here, but a compiler with enabled '-Wnounit-statement -Wno-value-discard' will produce warnings (Maybe in lucky way this warning are after inlining -- need to check). Hmm, maybe for lucky cases, we need even 'after typer' because of macros (but not annotation macros). can be transparent inline, which works inside typer.

[fwbrasil]

hey @rssh! Nice to see you here :) Thank you for your work on dotty-cps-async, it has been an instrumental solution in Kyo's development!

Yes, Caprese and Kyo are solutions in the same domain and thus share major similarities. For example, Caprese's Capabilities is equivalent to Kyo's pending effect set and both require a suspension mechanism. It's a bit difficult to form a complete picture of Caprese so I'm basing this reply on this recent talk. The fundamental issues I see with Caprese's design are how prescriptive and restrictive it is while still not addressing the two main challenges it sets out to solve:

1. Effect Composability

Building an effect system where multiple effects can be composed in a safe and principled way is quite challenging. It's necessary to ensure handlers are pure and impure code doesn't introduce invalid control flow when effects are handled. Caprese's current design does not address that. Handlers are based on impure short circuiting via exceptions and mutable internal state. Examples from the talk:

// Impure short circuiting via exceptions
object boundary:
  final class Label[-T]
  def break[T](value: T)(using label: Label[T]): Nothing =
    throw Break(label, value)
  inline def apply[T](inline body: Label[T] ?=> T): T = ...
end boundary

// Handlers rely on mutable internal state
trait Produce[-T]:
  def produce(x: T): Unit

def generate[T](body: () => Unit) = new Generator[T]:
  def nextOption: Option[T] = step()
  var step: () => Option[T] = () =>
    boundary:
      given Produce[T] with  // handler
        def produce(x: T): Unit =
          suspend[Unit, Option[T]]: k =>
            step = () => k.resume(())
            Some(x)
      body
    None

This approach to effects does not compose. If both boundaries and generators are used in the same computation, the behavior seems undefined since Caprese doesn't even offer a way to handle the fact that the continuation itself might have other effects. The solution doesn't seem useful other than in non-nested and locally-scoped handlers. It also doesn't enable programming with values in the FP sense and relies on fragile control flow primitives instead. For comparison, here's the equivalent in Kyo:

// a pure and composable boundary/break effect in Kyo
class Boundary[V]() extends Effect[Boundary[V]]:
    opaque type Command[T] = Left[V, Nothing]

    def break(value: V): Nothing < Boundary[V] =
        suspend(this)(Left(value))

    def run[T: Flat, S](v: T < (Boundary[V] & S)): Either[V, T] < S =
        handle(handler, v)

    private val handler =
        new ResultHandler[Const[Left[V, Nothing]], [T] =>> Either[V, T], Boundary[V], Any]:
            def pure[T](v: T) = Right(v)

            def resume[T, U: Flat, S](
                command: Left[V, Nothing],
                k: T => U < (Boundary[V] & S) // notice the continuation as a pure function
            ) = command // short circuit by ignoring the continuation

// pure generators (borrowed from @kitlangton)
class Generators[Input: Tag, Output: Tag]() extends Effect[Generators[Input, Output]]:
    opaque type Command[A] = Yield[Input, A]
    case class Yield[Input, Output](value: Input)

    def yield_(value: Input): Output < Generators[Input, Output] =
        suspend(this)(Yield(value))

    def run[Input: Tag, Output: Tag, T: Flat, S](
        value: T < (Generators[Input, Output] & S)
    )(
        handler: Input => Output < S
    ): T < S =
        val h = new Handler[[T] =>> Yield[Input, T], Generators[Input, Output], S]:
            def resume[T, U: Flat, S2](
                command: Yield[Input, T],
                k: T => U < (Generators[Input, Output] & S2)
            ) =
                handle(
                    handler(command.value)
                        .map(output => k(output.asInstanceOf[T]))
                )
        handle(h, value)

Another important difference between Caprese and Kyo at the current phase of the projects is that both these implementations are already fully functional in Kyo without the need for any language changes and in a purely functional manner.

2. Effect Suspension

Caprese's answer to how to introduce suspension is still unaddressed. Its design locks in to a significantly more limited form of suspension than Kyo's that can only be provided by an underlying runtime:

// Caprese's runtime-based suspension API
class Suspension[-T, +R]:
  def resume(arg: T): R = ???
  
def suspend[T, R](body: Suspension[T, R] => R)(using label: Label[R]): T

Note how the methods return values directly, which means the suspension can only happen by pausing the execution in the runtime itself. In Kyo, suspensions use the typical building block to perform suspensions: monads. I believe other languages like Unison and Koka adopt a similar approach and model the execution of algebraic effects on top of a monadic runtime.

Caprese's design seems to come from a misconception regarding the performance characteristics of monadic runtimes. Fine-grained effect suspensions like what Kyo and Caprese want to offer would have significantly worse performance using Loom's suspension for example. Although I'm a big fan of Loom and think it's one of the major improvements of the JVM in recent years, it seems only appropriate for coarse-grained effects like async, where its overhead is generally acceptable.

In contrast, Kyo's suspensions are pure values:

// Kyo's pure value-level suspension
def suspend[E <: Effect[E], T](e: E)(v: e.Command[T])(
    using _tag: Tag[E]
): T < E =
    new Root[e.Command, T, E]:
        def command = v
        def tag     = _tag

This characteristic enables a more powerful form of suspension. Handlers receive a regular function as the continuation, which provides a high degree of freedom. Essentially, it enables proper multi-shot continuations.

In addition to the more flexible algebraic effect mechanism, Kyo's monadic encoding has significantly better performance than traditional effect systems.

Conclusion

Caprese's current work seems to prioritize defining APIs and abstractions over addressing the main challenges of the problem. While this approach may help iterate quickly and produce papers, it seems to be leading to major limitations. The work on this ticket is intended to provide an alternative that works seamlessly with Kyo and other effect systems rather than baking in an impure effect system in the language, which can't be reused by them. Addressing first-class support for purity is also a necessary step to make the transformation from direct to monadic in a principled way.

[fwbrasil]

If we want implement this in macros (i.e. after typing), we have two visible problems (except need for extra Purifier) clause:

I was thinking about your suggestions and I’m afraid it’d be too fragile to do that via macros and implicit conversions. The usability wouldn’t be great since it wouldn’t be able to prevent mistakes and macros can’t express the effectful type mechanism properly. Maybe we should aim for a plugin directly.

The purity check would also be necessary. I’ve taught newcomers to use Kyo and one of the first things they normally do is mix impure code. The direct syntax seems to encourage that given the similarities with other languages.

[rssh]

A purity check can be implemented in macros (we have all trees there, so it's relatively easy).

Also, I forgot about the third problem, which is inferring function type via the last expression in the block.
The last expression can be monadic or non-monadic, therefore if the return type of the `pure/effect-gathering' method is not set, it will be inferred differently for these two cases, and we can do nothing with this, because all types of macroses started
to work after typing.

So yes, implementing on top of implicit conversion is more fighting with existing typing than developing.

Thinking about finding another way of typing F[X] as X other than implicit conversions without language change
(something like. Ext[F[_]] ?=> X ). -- Now I don't think this is possible, but ... need to think more.

[rssh]

If we want to escape implicit conversion, we should change the primary representation of effect total values to be compatible by assignment with its result. (Also, the idea to have a type defined differently in different compile-time environments, but it look like this required a huge amount of boilerplate)

Two possible variants of typing should be used instead of IOs[A]. I see now:
A) 'IOs.Context ?=> A'
B). A^ { IOs.Capability }. [In this case ,^ is capreso effect tracking annotation. All 'normal' values in 'pure' functions actually will have such type].

[fwbrasil]

If we want to escape implicit conversion

I think we'd need to change the type inference of effectful types via a research plugin for the proposed solution to have a reasonable usability. I wonder if it's really very complicated since pure is similar syntactic sugar transformation. Maybe having a phase that handles the pure modifier and performs the direct to monadic transformation as syntactic sugar would be enough.

Two possible variants of typing should be used instead of IOs[A]. I see now:
A) 'IOs.Context ?=> A'
B). A^ { IOs.Capability }. [In this case ,^ is capreso effect tracking annotation. All 'normal' values in 'pure' functions actually will have such type].

Both options do not seem viable. The fundamental impedance mismatch between Kyo and Caprese/Capabilities is that Kyo uses suspended computations as pure values. A type like Int < Fibers can internally be either a pure value Int or a suspended computation with the Fibers effect pending. The equivalent in Caprese would be Int ^ { Fibers.capability }, which can not be anything other than Int afaics. The effect tracking in Caprese seems meant to be compatible only with control-flow based handlers, not suspended computations via monads.

[rssh]

A type like Int < Fibers can internally be either a pure value Int or a suspended computation with the Fibers effect pending. > The equivalent in Caprese would be Int ^ { Fibers.capability }, which can not be anything other than Int afaics.

For the programmer.
It is possible to write a standalone plugin that internally transforms such values into monadic form.

[rssh]

I.e. exists 3 options:

1. phase before types. (problem -- the transformation of high-order functions uses typing. Maybe it is possible to streamline this or isolate and move to a later stage. )
2. Change types. It's unclear if this is possible without substituting unmodified typers in phase. And is it possible to find minimal changes to the type system that can be clearly described?
3. Find a way in type system to represent monadic values in a form, compatible with direct values and then transform such values after typing and capture checking.

(can we find more ways to choose from ?)

[fwbrasil]

@rssh thank you for following up on this! I was taking a look at capabilities and, besides the issue with it not being designed to represent monadic effects, there are some important usage patterns of the pending effect set in Kyo that might not be possible to express with capabilities:

1. Restricting Effects

Some methods in Kyo require restricting the effects that are allowed to be present in a computation. This is an essential feature to have proper support for fibers for example since forking with effects requires special handling. The Fibers.init method uses an implicit evidence to enforce that:

object Fibers {
    def init[T, S](v: => T < (Fibers & S))(
        using
        @implicitNotFound(
            "Fibers.init only accepts Fibers and IOs-based effects. Found: ${S}"
        ) ev: S => IOs,
        f: Flat[T < (Fibers & S)]
    ): Fiber[T] < (IOs & S) = ...
}

When this method is called with effects that aren't Fibers or IOs (or based on them), the compilation fails. For instance, without this mechanism a Vars[Int] effect could be "propagated" to a fiber, which wouldn't make sense since it's not possible to safely update state across different threads.

Something remarkable about this approach is how it offers a mechanism similar to Rust's borrow checking to ensure safe use of state but without the significant usability issues that comes with it.

2. Aliased Effect Sets

Since Kyo's pending type leverages the type system itself, it's easy to refactor sets of effects using regular type aliases:

type Databases = Envs[Database] & Aborts[DBException] & IOs

def countPeople: Int < Databases = Envs[Database].use(_.countPeople)

This approach becomes even more powerful when paired with opaque types. For example, the Resources effect is internally 100% based on IOs but Kyo ensures users have to handle the effect by using an opaque type:

opaque type Resources <: IOs = IOs

val a: Int < (Databases & Resources) = Resources.acquire(new Database).map(_.countPeople)

val b: Int < (Databases & IOs) = Resources.run(a)

Note how Resources also indicates that it's internally IOs via type bound, which enables calling Fibers.init with a Resources effect pending as well.

3. Parametrized Effects

Kyo offers effects with a type parameter like Envs[Database & Cache], which is equivalent to Envs[Database] & Envs[Cache]. This is crucial for usability since it aids in reducing the number of elements in the pending set and still allows Kyo to define methods that operate on a single environment value:

def t1(v: Int < Envs[Int & String]): Int < Envs[String] = 
    Envs[Int].run(1)(v)
def t2(v: Int < (Envs[Int] & Envs[String])): Int < Envs[Int] = 
    Envs[String].run("s")(v)

Conclusion

I'm not convinced that Capabilities are reusable in Kyo and I think it's likely they'll require major redesigning to achieve reasonable usability. If we build the plugin on top of it, we risk degrading user experience and maintaining the plugin can become quite challenging as Capabilities will likely still have major changes.

That said, capture checking would still be valuable in Kyo since it'd enable a safer Resources effect for example. I think it'd make sense to explore if we could apply it to specific scenarios but I don't envision eventually migrating to Capabilities since Kyo's approach using type-level set serves library's needs quite well.

[fwbrasil]

phase before types. (problem -- the transformation of high-order functions uses typing. Maybe it is possible to streamline this or isolate and move to a later stage. )
Change types. It's unclear if this is possible without substituting unmodified typers in phase. And is it possible to find minimal changes to the type system that can be clearly described?
Find a way in type system to represent monadic values in a form, compatible with direct values and then transform such values after typing and capture checking.
(can we find more ways to choose from ?)

I don't know the compiler's internals but wouldn't it be possible to treat pure as syntactic sugar in the Desugar phase similarly to for-comprehensions? If we output the tree with the equivalent monadic composition, it'd fail in case the effectful types are not used as their "result" type in a pure member.

[rssh]

I don't know the compiler's internals but wouldn't it be possible to treat pure as syntactic sugar in the Desugar phase similarly to for-comprehensions?

The question - how we would know without typer, that we extract something from monad or we use plain values?
This will mean that we should have a syntax-only way to describe monadic computations. I.e. in next block of code:

[*] def  askValue1():  Int < IOs

[*] def askValue2(): Int.  // fake

[*] def increment1(x: Int ): Int = {
     askValue1() + 1
}

[*] def increment2(x: Int ): Int = {
     askValue2() + 1
}

Is impossible, because increment1 and ìncement2` should be syntaxically different.

Of course, we can reuse <- and. write a <- b when we want extract value. It can be a cool addition in 'scala' style for for-comprehartion (related topic on scala-contributirs: https://contributors.scala-lang.org/t/pre-sip-for-with-control-flow-an-alternative-to-scala-async-scala-continuations-and-scala-virtualized/4423 , https://contributors.scala-lang.org/t/from-freeing-leftarrow-to-better-for-and-unification-of-direct-and-monadic-style/5922 ), but is this solve the goal of make monadic computation like non-monadic ? They should be syntaxically differ. I.e. something like:

[*] def  askValue1():  Int < IOs

[*] def askValue2(): Int.  // fake

[*] def increment1(x: Int ): Int = {
     val x <- askValue1() 
     x + 1
}

[*] def increment2(x: Int ): Int = {
     askValue2() + 1
}

And if we have syntax for extracting value from some monads, we don't need a { 'pure' , 'effect-gathering' } markers for functions: if we use <- inside function, then one is effect-gathering. In principle we can generate two versions of. increment1 -- monadic and non-monadic.

Syntax-only way is cool ;). But how is it suitable for kyo goals is unclear.

[rssh]

Yet one way - think that in effect-gathering function any non-constant value is wrapped in a monad (and use = instead '<-' ). It's a way of 'scala-virtualized' . Potential problem is performance of extracting all possible non-constant values from monad.

[fwbrasil]

good point! I've been discussing this proposal with other people and a common concern is the lack of an await call to make it clear that an effectful type is in use. I wanted to avoid the syntax noise of the await calls but I don't think having it would be too problematic since other languages follow the same approach. Maybe we cloud explore making both pure and await keywords that trigger the syntactic sugar? I'd avoid <- since it seems less straightforward to understand than await.

It seems with this approach we wouldn't need @effectful as well but we'd still need a way to ensure all effectful types in a computation are wrapped into an await call.

[fwbrasil]

Potential problem is performance of extracting all possible non-constant values from monad.

I'm not sure what you mean by this but I don't foresee any performance issues with the translation. It'd be Kyo's regular monadic composition under the hood, which is efficiently executed.

[rssh]

I'm not sure what you mean by this but I don't foresee any performance issues with the translation. It'd be Kyo's regular monadic composition under the hood, which is efficiently executed.

[*]. def  calc3(x:Int, y:Int, z:Int): Int = (x+y+z)*otherFun(x,y)

translation:

  def calc3[F[_]](x:F[Int], y:F[Int], z:F[Int]):F[Int] = async[F] {
    val x1 = await(x)
    val y1 = await(y)
    val z1 = await(z)
    z1 + y1 + z1 + await(otherFun(x1,y1))
 }

[fwbrasil]

It's still not clear to me but I think you're assuming that the transformation would need to lift all parameters into the monad? That wouldn't be the case, declaring which effects each parameter can have is an important aspect of how Kyo provides effects. What I'd expect of the transformation:

pure def calc1(x: Int < Fibers, y: Int): Int < Fibers =
    await(x) + y

// translation
def calc1(x: Int < Fibers, y: Int): Int < Fibers =
    x.map(v => v + y)

pure def calc2(x: Int < Fibers, y: Int < IOs): Int < (Fibers & IOs) =
    await(x) + await(y)

// translation
def calc1(x: Int < Fibers, y: Int < IOs): Int < (Fibers & IOs) =
    x.map(v1 => y.map(v2 => v1 + v2)) // Kyo's map is equivalent to flatMap

pure def otherFun(x: Int, y: Int): Int < Fibers = ...

pure def calc3(x:Int, y:Int, z:Int): Int < Fibers = 
    (x+y+z) * await(otherFun(x,y))

// translation
def calc3(x: Int, y: Int, z: Int): Int < Fibers =
    otherFun(x, y).map(v => (x+y+z) + v)

And if we have syntax for extracting value from some monads, we don't need a { 'pure' , 'effect-gathering' } markers for functions: if we use <- inside function, then one is effect-gathering. In principle we can generate two versions of. increment1 -- monadic and non-monadic.

I think we'd still need pure since the purity check is necessary to safely translate from direct to monadic.

[rssh]

Ohh, in first comment (with askValue primer) I say, that some syntax form of monadic wrapping is needed.
In the second (to which you replied), I realized we could assume that any value is wrapped in a monad.
Therefore, we can have some function annotation with semantics which you name 'pure' (pure/effect-gathering... actually need to find the best word). Sorry for the mess. It was two different encodings. In the first comment -- with syntax sugar for await/reflect/uplift, in the second -- assuming that all values are wrapped in await/reflect/uplift. (and await, of course, translated to map) and we don't need syntax sugar.
Now, I am thinking about the third encoding: we can assume that values are pure. (simular to your translation), so we have:

pure def otherFun(x: Int, y: Int): Int = ...

pure def calc3(x:Int, y:Int, z:Int): Int = 
    (x+y+z) * otherFun(x,y)

// translation. (if we  have no used Fiber inside)
def calc3_withEffects[F[_]](x: Int, y: Int, z: Int): F[Int] =
    otherFun_withEffects[F](x, y).map(v => (x+y+z) + v)

If we use Fibers:

pure def c(x:Int): Int < Fibers = Fibers.init(x).get + 1

// translation
def c_wihtEffect[F[_]:HasFibers](x:Int):F[Int] = 
    // await(Fibers.init(x)).get+1
    HasFiber[F].lift(Fibers.init(x).map(_.get + 1))

[rssh]

Type parameter is needed for case, when we want to call f form Int < Fibers < Either.
I will think, is it possible without..... maybe if all 'widening'. are put on the caller side, I'm not sure that this is possible without caveats of implicit conversions or syntax noise.

[fwbrasil]

I think I understand now. Kyo is different from other effect systems because you don't need to lift pure values into the monad since any type T is also a T < Any (no pending effects). Other effect systems would indeed need to provide a way to lift pure values to perform the transformation. Maybe we could assume that their companion object has to provide an apply or pure method? I'd like to avoid having to provide implicits and have a mechanism similar to for-comprehensions that only requires source compatibility.

[rssh]

Hmm, if we generate a copy of function, then we can do this after typing

[rssh]

About variation of (1). [before typing].

Example with sum will be more verbose than I have wrote:

pure def calc3(x:Int, y:Int, z:Int): Int < Fibers = 
    (x+y+z) * otherFun(x,y)

def calc3_ef[F[_]](x: Int, y: Int, z: Int): F[Int] =
       ((plus_ef(x,y).flatMap( xy => plus_ef(xy,z)).flatMap(xyz => multiple_ef[F](xyz, otherFun(x,y))
   )

because before typing we don't know -- is '+' return us monadic value or not.

[rssh]

So, among the options to most simple solutions that are very close to the original idea:

Variant A:

4:
- use standard plugin and represent F[_] as it now.
- use underlying implicit conversions for plumbing such functions be compilable (maybe insert imorts in the body before typing).
- Copy function and do the usual recursive top-down transformation for cps and erasing implicit conversions.
(i.e. in

  val. x = F[doSomething]
  val y = x+1 
  val z = x+2  

compiler after typing will generate

  val x: F[Int] = F[doSomething]
  val y:Int = convert[F[Int],Int](x)+1 
  val z:Int = convert[F[Int],Int](x)+2  

but we will fully remap it to normal 'virtual' representation in the near-generated method:

  val x:Int = await(F[doSomething])
  val y = (x)+1 
  val z = (x)+2  

which eventually become

  F[doSomething].map{ x1 =>
    val x = x1
    val y = (x)+1 
    val z = (x)+2 

  }

And old method will make compiletime-only.

[fwbrasil]

/bounty $2000

[fwbrasil]

Bounty requirements:

1. A new compiler plugin implementation from scratch.
2. The pure modifier as described with the validations to deny the use of impure language constructs.
3. Effectful types with custom inference behavior within pure members.
4. No major performance regression with the transformations.

[fwbrasil]

@kitlangton I'm redistributing Kyo's bounties. Have you been able to work on this? If not, can you cancel the attempt? Thank you!

[fwbrasil]

Cancelling the bounty for now. This is still desirable but I don't think we'd be able to build something on time for 1.0.