Feature Request: Support for custom free operators

[anatoliykmetyuk]

Hi everyone.

We have discussed the question I am about to rise earlier on Gitter. It keeps popping up on every corner for me, and if solved will probably greatly increase the flexibility of Freestyle. So it would be nice to have a more in-depth discussion of the problem.

Motivation

Freestyle can be used to describe what needs to be done without describing how. This is achieved via two things:

1. Abstract primitive actions - F[A], they are defined under the free traits.
2. Free operators to glue them together. Currently Freestyle expresses everything as Free[FreeApplicative[F, ?], A]. So the free operators available are point, flatMap and ap (and those you can derive from them).

In practice however these operators don't seem to be quite enough.

ApplicativeError Examples

CRUD website Update operation

Consider that you are writing a web server. You want to write a handler for an operation that updates some entity, say a forum post. Normally you would like to check the authorization of the user, then validate their data, then write to the database. If everything went fine, you return "Success" text, otherwise your return text depends on an error. If validation went wrong, you return the update form with bad fields highlighted, if the user does not have a proper authorization, you redirect them to the login page, and if the database write failed, you return an "Internal error" text.

Here's how this code in freestyle would look like:

def postUpdateHandler[F[_]: Application]: PartialFunction[Request, FS[F, Response]] =
	for {
	  user      <- app.req.getUser(request)        // Error effect: not logged in
	  _         <- app.auth.isModerator(user)      // Error effect: not a moderator
	  post      <- app.req.get[ForumPost](request) // Error effect: some fields are missing
	  postValid <- app.post.validate(post)         // Error effect: some fields are invalid
	  _         <- app.db.write(post)              // Error effect: database error
	} yield Redirect(router.post.read(post))       // Redirect to the updated post

Now imagine you have many such handlers, for every of your pages. At some point, in the server, you match the incoming request against these handlers, obtain the corresponding FS[F, Response], interpret it under some H, extract Response from H[Response] and respond with it.

Since our freestyle code had error effects, H will also have them. So during extraction, we'll need to also do error handling. Problem is, some errors are too local to be handled on the global scope. For example, a validation error of a forum post should result in responding by the form that caused the error with the bad fields highlighted. This would be hard to do from the central point in the server where requests are handled (precisely, will require to store all the relevant information - which URL the form came from, what was the original input - in the error itself. We'd rather have the concerns separated).

To localize error handling, we can use ApplicativeError:

def postUpdateHandler[F[_]: Application]: PartialFunction[Request, FS[F, Response]] =
	(for {
	  user      <- app.req.getUser(request)        // Error effect: not logged in
	  _         <- app.auth.isModerator(user)      // Error effect: not a moderator
	  post      <- app.req.get[ForumPost](request) // Error effect: some fields are missing
	  postValid <- app.post.validate(post)         // Error effect: some fields are invalid
	  _         <- app.db.write(post)              // Error effect: database error
	} yield Redirect(router.post.read(post))       // Redirect to the updated post
	).recoverWith { case ValidationError(...) => ... }

So in this case, the errors that are reasonable to handle globally are still propagated, whereas the local errors - ValidationError - get handled locally. This allows to display generic pages for global errors (e.g. "Please log in", "Internal server error happened"), whereas local errors get more specific pages (e.g. the form with highlighted bad fields, possibly preserving the original user input).

However, recoverWith is an operator of ApplicativeError, and is not supported by freestyle.

A solution suggested to me was to just return all the results in Either or Try. However, this would mean it will not be possible to decide on the spot which errors to propagate and which to handle locally. Also, in the above monadic flow, 5 statements potentially return an error. If we wrap them all in Either or Try, the entire point of monadic flow is lost.

Mass processing with Traverse

Consider you have a list of websites and you need to navigate to each of them and parse certain data.

There are lots of websites, and some of them may not conform to the pattern you expect, so you'll get an exception when trying to parse the data. Some websites may be dead and you'll get an exception trying to connect to them.

In other words, in large datasets unexpected exceptions can happen. You don't want to lose all the data you processed so far, so you want to just drop all the results that threw exceptions.

You have your processing algorithm implemented for a single URL in freestyle:

def process[F[_]: Application](url: URL): FS[F, Data] = ???

Obviously you catch all the exceptions under ErrorM effect, so the code is pure. Now you can use traverse to process the entire list:

val list: List[URL] = ???
val result: FS[F, List[Data]] = list.traverse(process)

However for most types (I tried Either and Future), the behavior of Applicative in a |@| b is to drop both results if at least one is erroneous. Which means list.traverse(process) will drop all the data on first error, and replace it with that error.

What we want is to recover the error to Option - have Some[Data] in case of success and None in case of failure. Than we can have a List[Option[Data]], which we can flatten.

One solution is to modify process to return FS[F, Option[Data]]. But what if this list is not the only place it is used at? What if we have a large project and don't want the signature modified?

ApplicativeError would have been of help again:

def processSafe[F[_]: Appliaction](url: URL): FS[F, Option[Data]] = process(url).map(Some).handleError(_ => None)
val result: FS[F, List[Data]] = list.traverse(process).map(_.flatten)

Nice, composable solution where we build upon an existing function to get a new one. Instead of modifying the existing function, potentially breaking dependencies.

However the same problem: freestyle does not support ApplicativeError.

Fetching data from many data sources

Similar example to the previous one. Consider that for a given URL, you need to fetch some data from it, but also some statistics on that URL from alexa.com. If either is not available, just return "N/A".

You may have two functions for the two tasks:

def data [F[_]: Application](url: URL): FS[F, Data ] = ???
def alexa[F[_]: Application](url: URL): FS[F, Alexa] = ???

Next you may unite them via applicative to get the unified result:

def process[F[_]: Application](url: URL): FS[F, String] =
  (data(url) |@| alexa(url)).map { (dataRes, alexaRes) => ... }

The problem, as previously, is that if either data or alexa have Error effect, the applicative for most implementations will simply drop the other one too. Same situation as in the previous example: you need to recover from the error with a default value ("N/A").

Custom operators. Parallel & GUI Programming Examples

The examples below are inspired by SubScript syntax, as it proved to be really good for GUI and workflow description.

Interruption

Consider you want to describe a GUI application in freestyle. You have three buttons, "A", "B" and "Cancel". The idea is that the user should press "A", then "B" will get activated and they will be able to press it. But if they press "Cancel" between "A" and "B", "B" will deactivate and "A" will activate again.

Hardly you can describe it with freestyle without introducing new operators. If you however have a possibility to add new operators, you can add /, interruption operator. And write something as follows:

aButtonPressed.flatMap(_ => bButtonPressed) / cancelButtonPressed

How / will work? Depends on the implementation. The job of freestyle is to preserve the structure of the operations performed, not the semantics. So it will only need to remember that the / operation was called. On interpretation it will consult a concrete type class implementation that knows what it means to do /(f1: F[A], f2: F[A]).

Choice

Now consider you have a GUI application with two buttons, "A" and "B". If "A" is pressed, "Hello" should be printed to the command line. "B" prints "World". The user may press whichever button they like, however they won't be able to press the other button after their choice.

Normally you would be able to do something as follows:

a.flatMap(_ => println("Hello")) |@| b.flatMap(_ => println("World"))

However this way the user will be able to press both of the buttons.

You may want another custom operator: +, that allows only one of the two F[A]'s to be chosen. What it means is defined by type classes, as always.

a.flatMap(_ => println("Hello")) + b.flatMap(_ => println("World"))

Solution

By these examples, I wanted to show that the standard Free[FreeApplicative[F, ?], A] view of programs is too rigid and inflexibly. If you aim to write the majority of your code in freestyle, you quickly discover that a lot of programs cannot be generalized as a sequence of parallel fragments. First, you have error handling. Second, you need more advanced control structures: we have discussed choice and interruption, but more standard structures include loops and forks. Third, you may very well want any of the known type classes to be used in freestyle, not only ApplicativeError.

Proposed Implementation

Idea

Free[FreeApplicative[F, ?], A] denotes a type level tree, where operators are flatMap, ap and others, and operands are F[A]'s.

More precisely, this is a tree of depth at least 2. On the first level, the operators are flatMap, map, pure - the monadic ones. The operands are FreeApplicative[F, A]. On the second level, the operators are ap (and others?) and the operands - F[A]. If F is another FreeS[F, A], you can potentially have a tree of unlimited depth.

So, if the operators that can be used are controlled by the type we are working under (FreeS = Free[FreeApplicative[F, ?], A]), an obvious way to extend the system will be to allow working under any type (as long as it conforms to framework restrictions).

If one wants to use ApplicativeError, one can use say FreeApplicativeError[Free[FreeApplicative[F, ?], ?], A]. If one wants to use interrupt or choice, one may want to stack FreeInterrupt and FreeChoice on top (or in the middle?) of their existing stack in a similar way.

Implementation

Here's how I see it working.

You start with a type class (say ApplicativeError), and you want to use its free alternative in your freestyle app.

First step then is to define this free alternative:

@algebra[ApplicativeError] trait FreeApplicativeError[F[_], E, A]

@algebra does some free object specific magic. It will track down all the abstract methods and will reify them into case classes.

ApplicativeError has the following abstract methods:

abstract def handleErrorWith[A](fa: F[A])(f: (E) ⇒ F[A]): F[A]
abstract def raiseError[A](e: E): F[A]

So they may be reified to the following classes:

case class HandleErrorWith[F[_], E, A](fa: F[A], f: (E) ⇒ F[A]) extends FreeApplicativeError[F, E, A]
case class RaiseError[F[_], E, A](e: E) extends FreeApplicativeError[F, E, A]

Also this macro will create a default type class ApplicativeError for FreeApplicativeError that will translate method calls to the case classes above.

@algebra[ApplicativeError] may not be possible to implement in that precise form, but the main idea is to provide the macro with the knowledge of which type class you are trying to make free.

Next thing you'll need to do is to specify how to interpret the free object in presence of a concrete type class:

trait Interpret[F[_], H[_]] {
  def interpret[A](fa: F[A]): H[A]
}

implicit def freeApplicativeErrorInterpreter
[F[_]: Interpret[?, H], H[_]: ApplicativeError, E]:
Interpret[FreeApplicativeError[F, E, ?], H] =
new Interpret[FreeApplicativeError[F, E, ?], H] {
  def interpret[A](f: FreeApplicativeError[F, E, A]) = f match {
    case HandleErrorWith(fa, f) => fa.interpret[H].handleErrorWith(f)
    case RaiseError(e) => ApplicativeError[H].raiseError(e)
  }
}

So in order to interpret a free object under H, you need to be able to interpret the higher-kinded type F in its monad transformer position (the one this free object encapsulates). Also you'll need a type class for H which knows the meaning of the operations your free algebra reifies.

And basically that's it. All you need to do (the inputs that the computer can not derive) is to:

1. Define the @algebra trait, and in this definition specify the name of the type class you are targeting.
2. Define the Interpret type class (or define the semantics of interpretation in any other way) which tells what to do with the case classes that represent operations.

This way, you can have a tree with arbitrary operators of arbitrary depth. Each operators reside on their own layer. And it will be executed layer by layer.

Conclusion

Thanks for reading this long post! I think Freestyle has a potential to describe any program without executing them. Decoupling semantics from description allows to plug in any semantics you like, enabling aspect-oriented programming. This is an awesome idea, and I think it could benefit greatly from the ideas outlined above. It is easy to think of Freestyle as of a programming language of its own, but it is hard to work with a programming language that has only sequence and parallelism control structures, without error handling (as in try) or other more conventional control structures (as in while, for, if etc).

Eager to know what you think about this idea.

[raulraja]

@anatoliykmetyuk we are impressed and thank you for such detailed explanation!

While we could definitely model things as you proposed I think there may be a simpler approach by defining Choice / Interrupt and other as effects in the freestyle-effects.

Handlers for those effects can be recursive and expressed as natural transformations therefore allowing reification of the Choice and interrupt combinators and algebras can also receive implicit args that can be passed onto handlers. We have a current limitation of not being able to send FS programs as parameters to algebras but if we can figure a way to do that we don't need to change the type signature or introduce variations of what FS means. I think we should discuss this over chat but we are very much interested in finding a solution to this issue. Ultimately freestyle main goal is to be approachable to newcomers and allow people learning scala to use pure FP with a very simple an concise syntax.

Since all typeclasses can be expressed as algebras and constrains such as ApplicativeError are pushed to handlers as evidences in the runtime we should be able to model Choice, interrupt and many others effects as free algebras combinators.

As for @algebra[ApplicativeError] trait FreeApplicativeError[F[_], E, A] I think is also a great idea.
I think a more flexible approach would be something like:
@free[MonadError[Throwable, ?]] trait ErrorM so we can automatically reifiy any typeclass to Freestyle. This will allow us to remove most declarations in our effects module. Something to be solved in this area would be type constructors with arity > 1 which we are currently solving by using path dependent types and forcing the user to specify first the Error type to which all the algebras get materialized.

Looking forward to seeing you on gitter and discussing how we can make all of this happen keeping it easy for users to use. Cheers! and again, impressed and thank you so much!

[raulraja]

@anatoliykmetyuk Also whatever we end up implementing we'd be honored if you champion that effort
:) 🍻

[peterneyens]

Relevant to this discussion is John De Goes' "post Free" presentation (talk, slides).