From freeing \leftarrow. to better for and unification of direct and monadic style

Language Design
1

It’s a follow-up to the @diesalbla topic PRE-SIP: Comprehensive Function Applications. and a set of discussions arrounf PRE-SIP: Suspended functions and continuations - #135 by MateuszKowalewski and Pre SIP: `for` with Control Flow (an alternative to Scala Async, Scala Continuations and Scala Virtualized)

Next sequence of steps/language changes are possible:

Step1 /SIP NN-1: allow \leftarrow to be used outside for loop:

The definition should have next form:

     def  <- [F[_],A, …U_i ](a:A)(using …u_j): A

where U_i, u_j– optional additional type parameters and given arguments.

The expression: val a <- b is the syntax sugar for val a = <-(b). and a <- b — for a = <-(b).

By conventions, ← should mean extracting from F[_], and another usage should be forbidden.
This can be implemented now with relatively low effort.

The drawback is that developers can ignore conventions and use ← for other purposes. Introducing language import can mitigate this.

Step2 /SIP NN-2: assume that ← is defined in the lexical scope of for loop with the usual semantics of [await/reflect/unlift].

This will allow expressions like:

    for
        x ← fetchData
        c <- isFine(x)
        y <- if (c) then 
                  val  defatils <- fetchDetails(x)
                  pure (details + localDetails(x))
               else
                  failure RuntimeException(s"$x is not fine")
    yield y

This will require implementing cps-transform inside expressions in for loop. The area is relatively well-known, for scala3 exists at least two user-level implementations.

Step 3/SIP NN-3: Make val keyword optional when mutable variables are absent in the current scope.

(motivation: why we need val at all (?) – to prevent mixing value definition and assignments. If we have no mutable values, we have no assignments.)

This will allow:

    for
        x ← fetchData
        c <- isFine(x)
        y <- if (c) then 
                defatils <- fetchDetails(x)
                pure (details + localDetails(x))
            else
                failure RuntimeException(s"$x is not fine")
    yield y

This will give us better-then-haskell for for functional effect lowers.

Step 4/SIP NN-4: Link ← with the capabilities and merge direct and monadic-dsl styles.

Let us have the capability ‘cps’ or ‘suspend’ and provide a way to define ← in terms of that capability for library authors. In this way, we can solve the coloring problem:

def doSomething[F[_]](input:Inout)(using ml:MonadLift[F]): { ml } Output  =
    data <- f(input)
        …

Or even:

def doSomething[F[_]:MonadLift](input: Input): { suspend } Output = 
    data <-  f(input)
        ….

where suspend is some global capacity.

It can be used the same as the other form without capacity:

def doSomethingM[F[_]:MonadLift](input: Input): F[Output] = async[F]{
   data <-  f(input)
        ….
   }

The capability elimination step can be runtime or compile-time, depending on monads and runtime properties.
For compile-time, we should have a compiler pass that selective does cps transformation when an appropriative capacity is used.

And now direct and monadic styles are the same, for become a special kind of async/reify/lift with restrictions for children’s expressions.

Of course, the last is a very broad description connected to an open research theme with many unknowns, but I think the idea is understandable.

8 Likes
2

I feel like that we need to improve the for-comprehension itself. It should be generalized to match the other syntactic/control flow constructs in Scala.

The regular Scala constructs, like val, if, throw would have their counterparts with !, like val! (currently <-, flatMap), if! (ifM), throw! (raiseError), etc…

The beauty of this approach is that it builds on top of the already existing concept of for-comprehensions and uses similarly named keywords for analogous things (there is just ! appended), so it’s highly regular.

  for
    val! x = fetchData
    val! y = if! isFine(x)
      then
        for
          val! defatils = fetchDetails(x)
          yield details + localDetails(x)
      else
         throw! RuntimeException(s"$x is not fine")
    yield y
ordinary code analogue for-comprehension sugar for
val ... = ... val! ... = ... (legacy ... <- ...) flatMap
if ... then ... else ... if! ... then ... else ... ifM
throw ... throw! ... raiseError
try ... catch ... try! ... catch ... handleErrorWith
while ... do ... while! ... do ... whileM
…

This is how other languages do it, like F#. It also uses ! appended, although Scala could choose other symbol or prepending it instead of appending it, but that’s an insignificant detail at this point.

3

– What is the value of having two syntaxes instead one?

4

Yes, technically there are two syntaxes.
(A) One is for “direct” style and its semantics is baked into Scala and cannot be changed.
(B) The other is for Monads (and specializations thereof) and is defined by the user/libraries, as if “in userspace”. This makes Scala very extensible (but still in an orderly manner).
But the fact that there are two is an important part of the design, because they in the end do different things.
For example, there is a difference between just val ... = ... and flatMap. And you can’t reliably guess what the user meant with an algorithm. Contrast

for
  val! x = f1
  val y = f2(x) // y contains `M[A]`
  yield f3(x, y)

vs

for
  val! x = f1
  val! y = f2(x) // y contains just an `A`
  yield f3(x, y)

Even though there are two, they are intentionally made to look and behave in a similar manner. That way, user’s intuition from “direct style” translate well into Monads. Thus the overall complexity burden on users from having two syntaxes is not twice as big.

5

Thanks @rssh @sideeffffect , this looks very interesting and inline with what was previously proposed.

def doSomething[F[_]:MonadLift](input: Input): { suspend } Output

If we have the suspend capability, then we would not need F[_] or its constraints?

How can we handle different monadic data types in the same scope?

How would this interop with try/catch and other lang control structures?

So far, the continuations-based solution is the only one that can bring non-blocking async with direct style at the expression level. I’m curious as to what this example would look like with this syntax and what the return type of the function may be:

def getCountryCodeDirect(futurePerson: Future[Person])
     (using Structured, Control[NotFound.type | None.type]): { suspend } String =
  val person = futurePerson.bind
  val address = person.address.bind
  val country = address.country.bind
  country.code.bind
6
  1. The role of MonadLift was to pass capacity and operations on it to doSomething. Without this parameter it to doSomething. … , we can have something like { suspend } generator in a library.

Yes, technically, design, where capacity is created not by parameter but by API output, looks possible, one question:

  • effect / non-effect monads. If we have no F[_]. in the signature, we should choose what kind of monads we use by default; from another side, this can be solved by using different capacities for different monads. I think people will continue to use different monads.
    //. I’m afraid odersky will ban me if I start to speak about high-kind capabilities: suspend[IO] vs suspend[Future], so. better to be calm in this direction :wink:

In fact, exists at least 3 variants of appropriative capacity:

  • suspend. as in kotlin. Future: { suspend } Output. represent an already started computation.
  • suspend for effect: IO/ZIO' : { effect } Output`. represent a computation that should-be started later.
  • cps: List, Channel ..: {cps Output} means that output and all previous computation should be cps-transformed.

suspend < effect < cps
- you can’t. make. effect from suspended application, it’s. already started.
- you can use suspended applications in effect
- you can’t. make. list from effect (i.e., equality classes of multi-shot/one-shot continuations ).
\footnote{. actually should be 5: one-shot continuations, delay + one-shot, multi-shot, delay + multi-shot, cps ; forgive me, strictly following technical details is hard. }

So, choosing one as a base for doSomething is possible, from the other side – suspend is the least powerful of this. I.e., you will not be able to use {suspend}. in {effect}. If we want that our function was callable from a maximum set of monads, we should use the most powerful capacity.

Maybe this will be a source of analog of today’s monad-wars, and people will argue about suspend / effect/cps. as now they argue about Future/IO/ZIO. and passing F[_]. will be an analog of tagless-final.

Inside for <- should be from cps capacity because we should be able to process collections.

How do we handle this now?

  • by making async/reify and for to create a lexical scope (where our monad is the main monad, and values for other monads should be convertible to the value of our main monad). Better say computations instead values.

All control-flow operations except. try/catch can be expressed in terms of monadic operations.
For try/catch we need our monad to support two additional operations – raising and catching error (in cats this is MonadError, in dotty-cps-async it’s named CpsTryMonad). All known async monads (i.e. Future, IO, ZIO) have such methods. Collections (List/Map/Iterable …) – no.

Interesting question - how to interpret a raising of exception in the lexical scope of monad, which does not supports raising/handling error. [as List].
Now for loop propagates the exception to the upper level. (i.e., to the monad of enclosing scope), if we assume that at the top scope we have an Id monad.

Many styles are possible. In suspend style:

def getCountryCodeDirect(futurePersion: Future[Person]): {suspend }  String =
   person <- futurePerson
   address <- person.address
   country <- addres.country
   country.code

Here suspend. capacity can be synthesized from implicit Extractor for. future.
I.e. if we have

  def  <-[F[_],T](ft:F[T])(using e: Extractor[F]) :  { e } T

and Extractor[Future]. is marked by ‘{ suspend }’ capacity.

I’m not sure that exists syntax for coming from {e}. to { suspend }. and the use-case for global capacity was not planned. Hypothetically, this part of the infrastructure should be developed by Epfl.

7

Yet one variant

def getCountryCodeDirect(futurePersion: Future[Person]): { summon[Extractor[Future]] }  String =
   person <- futurePerson
   address <- person.address
   country <- addres.country
   country.code

but this is outside of the current definition of capabilities.

And why futurePerson is in monad form? When all in direct, it should be:

def getCountryCodeDirect(person: {c} Person): {c}  String =
   address <- person.address
   country <- addres.country
   country.code

and will work with any type of monad.
(also. outside of current definitions)

8

The issue I see in general with the <- syntax is that it forces to bind to a variable, it’s not the same as a suspended function application that can be expressed as:

def getCountryCodeDirect(futurePersion: Future[Person]) (using Structured, Control[NotFound.type | None.type]): { suspended }  String =
   futurePerson().address().country().code

This means that when we want apply simple operators to the result of functions we still need to explicitly bind:

a <- fa
b <- fb
a + b

instead of just

fa() + fb()

This is not an issue if instead of for we use CPS on the entire function and the CPS transformations also rewrite the internal function signature to be continuation based.

Is there a way in which we can support suspension or binding at the expression level without relying on for?

9

Yes, x <- y is. a shortcut to. x = await(y). (await. also named reflect. and unlift. in other libraries, and you name it bind). Of. course await/bind (or some synonyms) also should be available in the scope of the appropriative monad.

The basic is two functions with signatures like:

def  <async/reify/lift>[F[_]](using ml: MonadLift[F])(  t:  {ml}  ?=> T):  F[T]

def  <await/reflect/unlift/bind>[F[_]](ft:F[T])(using ml: MonadLift[F]):  {ml}. T

Ohh, looks like I use Extractor. in previous snippet. and MonadLift in this, It’s should be the same

10

Excellent, thanks, @rssh. If that is possible at the expression level using function application and the suspend CPS, then this satisfies what we are looking for in PRE-SIP: Suspended functions and continuations

11

To clarify, the only concerning bind to us is the one for async futures. The rest of bind operators for types like Either, Option, etc. can be implemented in terms of Control[-R] with a throwable already in Scala without changes.

12

@rssh Is there a way to get rid of the async { } wrapping requirement and instead bring the macro transformation from an expression to the entire function? It may require a compiler plugin.
I can’t implement bind with dotty-cps-async because async[F] is a requirement to call await
, which ultimately results in F[A]. The bind extension should return A or CpsAsync[F] ?=> A

import cps._

extension [F[_], A](fa: F[A])
  def bind(using cps : CpsAsyncMonad[F]): A = ???

How could we encode a function that does not return on the context of F[A] but instead just returns A?

13

Ability to ‘flip’. between F[A] / { capability[F] } A. representation. is an essence of capability projects.
But currently reflect API and capabilities are not linked. So, now from macros, this is impossible. From compiler plugin - maybe.

extension [F[_], A](fa: F[A])
  def bind(using cps : CpsAsyncMonad[F]): A = { cps }  A

but now we have no public API for this,

{c} A also can limitations to use. We can’t transform {c} A to A, but

  • a function. which accept =>A can accept A with any capabilities.
  • a function that uses c can accept. {c} A
14

Also I have assumed some properties of capability that not exists (yet?)

  1. Global capabilities. I thought that this is straightforward addition, but after rereading the paper about capabilities, understand that it can be not. So, { suspend } should be passed as input capability in all examples.
    The correct. getCountryDirect. signature will be:
def getCountryCodeDirect(futurePersion: Future[Person]) 
          (using suspended: MonadLift[Future]): { suspended }  String =
   .......

Ohh, the current conventions that now. MonadLift better be named MonadContext,

def getCountryCodeDirect(futurePersion: Future[Person]) 
            (using suspended: MonadContext[Future]): { suspended }  String =
   .......
  1. It should be some syntax, for passing parameters of some type and showing this parameter as capacity. (same as throws for CanThrows but generic) Because otherwise, we need to write this parameter twice.

Maybe using clause in capabilities position:

 def getCountryCodeDirect(futurePersion: Future[Person]) : 
                                     { using MonadContext[Future] }  String =
     ...