An implementation of Computation Expressions in Scala.
Scala
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
project
src
.gitignore
README.md
build.sbt
shippable.yml

README.md

Expressions

Expressions are an alternative for Scala for-comprehensions.

Scala for-comprehensions have three drawbacks that I have identified:

  • They only use flatMap which can be unnecessarily restrictive
  • They don't play very well with if and match statements
  • It's not possible to manipulate the context from within a for-comprehension

They also have some advantages:

  • Greater control over how effects are sequenced

You should use Expressions when you don't care about the ordering of effects, you just want to operate over values in a Context and have the Contexts be merged in a sensible way.

The concepts behind Expressions are loosely related to Computation Expressions from F# which is the inspiration for the name.

Background on Computation Expressions:

Features

Note that the examples below do not explicit the type parameters of the Expression application. For some reason, these need to be explicit, I am still investigating why, so in reality, you need to do Expression[Future, Int]{ combine(a,b,c) }.

Flexible use of abstractions

For-comprehensions are based on the notion of do-notation you may be familiar with from Haskell. This notation allows one to work with values within some kind of "context" which can be treated as a Monad. A Monad is any abstraction that supports the two following methods point[A](a: A): F[A] and bind[A](fa: F[A])(f: A => F[B]): F[B] (also known as flatMap). Both do-notation and for-comprehensions thus rewrite the "sugared" code into applications of point and bind. Unfortunately, while bind is a very powerful method and can be used to rewrite any expressions, its power comes at the cost of flexibility in its implementation. Applicative offers a less powerful abstraction that does however give more flexibility to its implementation. What does this all mean, let's look at an example:

a: Future[A]
b: Future[B]
c: Future[C]
for {aa <- a
     bb <- b
     cc <- c} yield combine(a, b, c)

Let's assume Future[A] takes 5 seconds but Future[C] fails after 1 second. Let's assume we want it to "fail-fast", that is, we want the whole thing to fail immediately if Future[C] fails after 1 second. This behavior is simply impossible with the above code because bind does not support failing fast. Please see my talk at PNWScala for a more in depth explanation of why this is.

Now let's look at the same example using Expressions:

a: Future[A]
b: Future[B]
c: Future[C]
Expression { combine(a,b,c) }

This code will "fail-fast" because Expressions uses ap to combine these Futures which does support failing-fast

Playing well with if statements and match statements

Let's consider the following piece of code:

a: Future[A]
b: Future[B]
c: Future[C]
for {aa <- a
     bb <- b
     cc <- c} yield if (aa == something) polish(bb) else polish(cc)

The above code will wait on the result of all three Future's before deciding to pick either the result from b or c. That's not ideal as far as I am concerned. I would rather if it waited on a and then waited on either b or c because at that point we know the result of the other one is of no importance.

We can fix this like this:

 a: Future[A]
 b: Future[B]
 c: Future[C]
 (for (aa <- a) yield
   if (aa == something) for (bb <- b) yield polish(bb)
   else for (cc <- c) yield polish(cc)).flatMap(identity)

This code will do the right thing when it comes to discarding unnecessary Futures. In my book though, this is overly ceremonious.

Instead, we can do this:

a: Future[A]
b: Future[B]
c: Future[C]
Expression { if(extract(a) == something) polish(b) else polish(c) }
  • Here is an example of somewhere automatic extraction is not triggered due to == being untyped. An explicit extract is required.

Manipulating Context within an Expression (TODO)

Let's move away from Futures now because this notation supports any Context. Let's consider the Writer Monad. This Monad is typically used for logging.

for-comprehension version:

a: Writer[String, Int] = 8.set("This is a magic value")
b: Writer[String, Int] = random().set("I got this value from a dirty function")
c: Writer[String, String] = "Hello World".set("Hello World...")
for {
  aa <- a
  bb <- b
  div <- if (b == 0) {
      5.set("We avoided a division by zero, yay!")
    } else Write("", aa / bb)
  cc <- c
} yield cc * div

Now with Expressions:

a: Writer[String, Int] = 8.set("This is a magic value")
b: Writer[String, Int] = random().set("I got this value from a dirty function")
c: Writer[String, String] = "Hello World".set("Hello World...")
Expression {
  val div = if (b == 0) {
    ctx :++> "We avoided a division by zero, yay!"
    5
  } else a / b
  c * div
}

Conversely for Futures:

for comprehension:

a: Future[Int]
b: Future[Int]
c: Future[String]
for {
  aa <- a
  bb <- b
  div <- if (bb == 0) {
    Future.failed(new Exception("Division by zero :-("))
  } else Future.now(aa / bb)
  cc <- c
} yield cc * div

Now with Expressions:

a: Future[Int]
b: Future[Int]
c: Future[String]
Expression {
  val div = if (b == 0) {
    // return is a special function on the ctx that allows to change the whole Context to the value passed to it
    ctx.return(Future.failed(new Exception("Division by zero :-(")))
  } else a / b
  c * div
}

An example where it is better to use a for-comprehension

Here is a snippert of code from Remotely

private def time[A](task: Task[A]): Task[(Duration, A)] = for {
    t1 <- Task.delay(System.currentTimeMillis)
    a  <- task
    t2 <- Task.delay(System.currentTimeMillis)
} yield ((t2 - t1).milliseconds, a)

If Expressions were to be used on this piece of code. The time at which System.currentTimeMillis is executed for the second time is likely to happen before the task is completely and thus would produce incorrect behavior.

Getting Started

Installation

libraryDependencies += "com.github.jedesah" %% "expressions" % NOT-RELEASED-YET

Usage

Now, you can import com.github.jedesah.Expression._ and use it like so:

phoneString: String
lookupPhone: String => Future[Phone]
lookupAddress: Phone => Future[Address]
lookupReputation: Phone => Future[Score]
renderPage: (Phone, Address, Int) => HTML

val response: Future[HTML] = Expression {
    val phone = extract(lookupPhone(phoneString))
    val address = extract(lookupAddress(phone))
    val rep = extract(lookupReputation(phone))
    renderPage(phone, address, rep)
}

or if you prefer even more magic, like so:

import com.github.Expression
import Expression.auto.extract

val response: Future[HTML] = Expression {
    val phone = lookupPhone(phoneString)
    val address = lookupAddress(phone)
    val rep = lookupReputation(phone)
    renderPage(phone, address, rep)
}

Limitations

Although the objective would be to support a maximum subset of the language, in practice we are far from there. Here are a bunch of constructs known to have good enough support as well as some known to have some issues. If a construct is in neither category it's safe to assume it probably has some issues. The hope is that once Macro support improves in Scala (Scala Meta), it will be easier to support all of the language.

Know to work well enough

  • Function application
  • if-else statement
  • function currying
  • String interpolation
  • Blocks
  • basic match statements

Known limitations

  • Does not support value pattern matching => val (a,b) = something
  • The match statement is a challenge to get right in all cases. It should work fine for basic usage, but will start to break down if using stable identifiers and excessive monadic behavior in pattern matches. Value pattern matching is actually desagured to a pattern match which is why it is not supported.

How it works

Expressions is based on a fairly straight forward transformation.

Function applications within an Expression with arguments that contain an extract like this:

Expression { foo(extract(a), b, extract(c) }

are rewritten like so:

instance.apply2(a,c)(foo(_,b,_))

where instance is either Monad[A] or Applicative[A] depending on what is available in scope

Sometimes bind must be used in order to desugar the Expression:

Expression { foo(extract(bar(extract(a))), b, extract(c)) }

In this situation bar takes an A and produces a Something[A]. Here is the desugared code:

instance.apply(instance.bind(a)(bar),c)(foo(_,b,_))

Match statement:

Expression {
    extract(a) match {
        case 1 => extract(b)
        case 2 => extract(c) + 1
    }
}

becomes:

instance.bind(a)(_ match {
    case 1 => b
    case 2 => instance.map(c)(cc => cc + 1)
}

Match statements can get hairy:

Expression {
    val foo = extract(getFoo)
    extract(bar) match {
        case `foo` => extract(b)
        case 2 => extract(c) + 1
    }
}

becomes:

{
    val foo = getFoo
    instance.bind(instance.apply(foo, bar)((_,_)){ case (x$1, x$2) => x$1 match {
        case `x$2` => b
        case 2 => instance.map(c)(cc => cc + 1)
    }
}

Similar Projects

Async/Await

Async/Await is based on a language feature from C#. It basically does the same thing, but specialized for Future's. My experimentation reveals that it is not possible to "fail-fast". It might be better optimized for runtime performance.

Effectful

Effectful generalizes the idea behind Async/Await to any Monad. It currently does not use the least powerful interface and as such fundamentally does not support failing-fast for Futures.

Scala Workflow

Scala Workflow is the most advanced project out there doing a similar thing. It uses the least powerful abstraction and also allows injecting functions available on the abstraction right in the middle of a workflow. Unfortunately, Scala Workflow requires untyped macros which are no longer supported in the latest version of Macro Paradise. It also does more heavy lifting then I believe is necessary. For instance it implements the implicit extraction on its own where as Expressions rely on good old Scala implicit resolution. This means that implicit extraction will break down in Expressions if the code has other unrelated implicit conversions (because Scala does not support multiple implicit conversions). IMHO this is a separate concern and I would rather see a macro or Scala itself support multiple implicit conversions with all the gotchas that come with it. So although Scala Workflow is in theory the most feature-full and generic solution, it has a possibly overly complicated implementation.

TODO

  • Fix limitations
  • Implement ctx
  • Support for nested abstractions
  • Generalize tests
    • Currently the large majority of tests only test the Option context, there is no fundemental reason it could not be generalized to test many Contexts at the same time, although this would require some nifty changes to ScalaCheck or some alternative. See how it's done in Effectful.
  • Make ScalaCheck function generation better
    • Currenlty, ScalaCheck only generates constant functions, this means the properties run a much higher risk of being false positives. It would be possible to create a few function generators for our purposes, but much better would be to fix this issue on ScalaCheck.
  • Use Scala Meta