scala-workflow helps to nicely organize applicative and monadic computations
in Scala with 2.11 macros, resembling for-comprehension and some enhanced
version of idiom brackets.
scala-workflow only requires untyped macros
that is an experimental feature of Macro Paradise.
$ git clone https://github.com/aztek/scala-workflow
$ cd scala-workflow
$ sbt console
import scala.workflow._
Welcome to Scala version 2.11.0
Type in expressions to have them evaluated.
Type :help for more information.
scala> $[List](List(1, 2) * List(4, 5))
res0: List[Int] = List(4, 5, 8, 10)
Import workflow interface.
import workflow._You will now have three macros at hand — context, $ and workflow. Wrap a
block of code in context and the argument of $ will begin to act funny.
context[Option] {
$(Some(42) + 1) should equal (Some(43))
$(Some(10) + Some(5) * Some(2)) should equal (Some(20))
}
context[List] {
$(List(1, 2, 3) * 2) should equal (List(2, 4, 6))
$(List("a", "b") + List("x", "y")) should equal (List("ax", "ay", "bx", "by"))
}Enclosing context macro takes type constructor F[_] as an argument and
makes all the $s inside evaluate their arguments as if everything of type
F[T] there was of type T, except it retains computational effects,
associated with F.
The exact rules of evaluation are defined in an object, that extends special
scala.workflow.Workflow[F[_]] trait. Such objects can either be implicitly
summoned by type constructor name (like the ones shown above), or passed
explicitly, like zipList below.
context(zipList) {
$(List(1, 2, 3, 4) * List(2, 3, 4)) should equal (List(2, 6, 12))
}There are numerous of Workflow[F[_]] objects you can find in instances.scala
file. All of them are instances of functors, applicative functors (also
called idioms), monads and a couple of other intermediate algebraic
structures.
context(map[String]) {
$(Map("foo" → 10, "bar" → 5) * 2) should equal (Map("foo" → 20, "bar" → 10))
}
context(function[String]) {
val chars = (s: String) ⇒ s.length
val letters = (s: String) ⇒ s.count(_.isLetter)
val nonletters = $(chars - letters)
nonletters("R2-D2") should equal (3)
}You can pass complex blocks of code to $.
def divide(x: Double, y: Double) = if (y == 0) None else Some(x / y)
context[Option] {
$ {
val x = divide(1, 2)
val y = divide(4, x)
divide(y, x)
} should equal (Some(16))
}Nested context and $ calls might look awkward, so instead you can use
special syntactic sugar, called workflow.
workflow[Option] {
val x = divide(1, 2)
val y = divide(4, x)
divide(y, x)
} should equal (Some(16))Just like in context, you can pass either type constructor or workflow
object.
The goal of scala-workflow is to provide boilerplate-free syntax for
computations with effects, encoded with monads and idioms. Workflow
abstracts the concept of computation in effectful context.
Instances of Workflow trait provide methods, that are used for desugaring
code in correspondent effectful contexts. The more methods an instance has,
the more powerful it is, and the richer language features can be used.
The ultimate goal is to support the whole set of Scala language features. For
now, however, only literals, function applications and val definitions are
supported. But development of the project is still in progress and you are very
welcome to contribute.
The hierarchy of workflows is built around an empty Workflow[F[_]] trait and
several derived traits, that add methods to it. So far there are four of them:
trait Pointing[F[_]] extends Workflow[F] {
def point[A](a: ⇒ A): F[A]
}
trait Mapping[F[_]] extends Workflow[F] {
def map[A, B](f: A ⇒ B): F[A] ⇒ F[B]
}
trait Applying[F[_]] extends Workflow[F] with Mapping[F] {
def app[A, B](f: F[A ⇒ B]): F[A] ⇒ F[B]
}
trait Binding[F[_]] extends Workflow[F] {
def bind[A, B](f: A ⇒ F[B]): F[A] ⇒ F[B]
}Each method corresponds to a particular feature of workflow context.
-
pointallows to put pure value inside the workflow. It is only generated when you call$(a)for some purea. -
mapis used to map over one lifted value in an expression. This is the samemapyou can find in ScalasList,Optionand other classes. -
appis used to map over more that one independently lifted values within a context. "Independently" means that you can evaluate lifted arguments in any order. Example of an expression with lifted values that depend on each other:$(divide(divide(1, 2), 3))(withdividedefinition taken from "Quick start" section). Bothdividecalls are lifted, but we can only evaluate outmostdivideafter the inner one has been evaluated. Note, thatappcannot be used withoutmap, hence the inheritance of the traits. -
bindis used to desugar expressions with arbitrary many arbitrary dependent lifted values.
You can define workflow instances simply by mixing above-mentioned traits, or using one of predefined shortcuts, representing commonly used algebraic structures.
trait Functor[F[_]] extends Mapping[F]
trait SemiIdiom[F[_]] extends Functor[F] with Applying[F]
trait Idiom[F[_]] extends SemiIdiom[F] with Pointing[F] {
def map[A, B](f: A ⇒ B) = app(point(f))
}
trait SemiMonad[F[_]] extends SemiIdiom[F] with Binding[F]
trait Monad[F[_]] extends Idiom[F] with Binding[F] {
def app[A, B](f: F[A ⇒ B]) = bind(a ⇒ bind((g: A ⇒ B) ⇒ point(g(a)))(f))
}Note, that Functor/Idiom/Monad is merely a shortcut. You are not required
to implement any of it particularly to be able to use workflow contexts. They
are mostly convenient, because have some of the methods already implemented and
can be composed.
One important difference of scala-workflow from similar syntactic extension
is that it always require the least powerful interface of a workflow instance
for generated code. That means, that you can have idiom brackets kind of syntax
for functors (such as Map[A, B]) and for/do-notation kind of syntax for
monads without return (they are called SemiMonads here).
Current implementation uses untyped macros and takes untyped Scala AST as an argument. Then we start by eagerly typechecking all the subexpressions (i.e., starting with the most nested subexpressions) and find, which of them typechecks successfully with the result type corresponding to the type of the workflow. If those are found, they are being replaces with their non-lifted counterparts, and the whole thing starts over again, until the whole expression typechecks correctly and there is a list of lifted values at hand.
Consider the example below.
context(option) {
$(2 * 3 + Some(10) * Some(5))
}All the numbers typecheck and are not inside Option, so they are left as is.
2 * 3 also typechecks to Int and is left as is. Some(10) and Some(5)
both typechecks to Option[Int] (well, technically, Some[Int], but we can
handle that), so both arguments are lifted.
Generated code will look like this.
option.app(
option.map(
(x$1: Int) ⇒ (x$2: Int) ⇒
2 * 3 + x$1 * x$2
)(Some(10))
)(Some(5))Special analysis takes care of dependencies between lifted values to be sure to
produce bind instead of app where needed.
Here are some of other examples of code rewriting within Option context.
Inside the $ |
Generated code | Pure Scala counterpart |
|---|---|---|
$(42) |
option.point(42) |
Some(42) |
$(Some(42) + 1) |
option.map(
(x$1: Int) ⇒
x$1 + 1
)(Some(42)) |
for {
x ← Some(42)
} yield x + 1
|
$(Some(2) * Some(3)) |
option.app(
option.map(
(x$1: Int) ⇒
(x$2: Int) ⇒
x$1 * x$2
)(Some(2))
)(Some(3)) |
for {
x ← Some(2)
y ← Some(3)
} yield x * y
|
$(divide(1, 2)) |
divide(1, 2) |
divide(1, 2) |
$(divide(Some(1.5), 2)) |
option.bind(
(x$1: Double) ⇒
divide(x$1, 2)
)(Some(1.5)) |
for {
x ← Some(1.5)
y ← divide(x, 2)
} yield y
|
$(divide(Some(1.5), Some(2))) |
option.bind(
(x$1: Double) ⇒
option.bind(
(x$2: Int) ⇒
divide(x$1, x$2)
)(Some(2))
)(Some(1.5)) |
for {
x ← Some(1.5)
y ← Some(2)
z ← divide(x, y)
} yield z
|
$(divide(Some(1.5), 2) + 1) |
option.bind(
(x$1: Double) ⇒
option.map(
(x$2: Double) ⇒
x$2 + 1
)(divide(x$1, 2))
)(Some(1.5)) |
for {
x ← Some(1.5)
y ← divide(x, 2)
} yield y + 1
|
Inside the $ |
Generated code | Pure Scala counterpart |
|---|---|---|
$ {
val x = Some(10)
x + 2
} |
option.map(
(x$1: Int) ⇒
x$1 + 2
)(Some(10)) |
for {
x ← Some(10)
} yield x + 2 |
$ {
val x = Some(10)
val y = Some(5)
x + y
} |
option.bind(
(x$1: Int) ⇒
option.map(
(x$2: Int) ⇒
x$1 + x$2
)(Some(5))
)(Some(10)) |
for {
x ← Some(10)
y ← Some(5)
} yield x + y |
$ {
val x = Some(10)
val y = x − 3
x * y
} |
option.map(
(x$1: Int) ⇒
val y = x$1 − 3
x$1 * y
)(Some(10)) |
for {
x ← Some(10)
y = x - 3
} yield x * y |
$(2 + {
val x = Some(10)
x * 2
}) |
option.map(
(x$1: Int) ⇒
2 + x$1
)(option.map(
(x$2: Int) ⇒
x$2 * 2
)(Some(10))) |
for {
y ← for {
x ← Some(10)
} yield x * 2
} yield 2 + y |
Workflow context is defined with context macro that either takes a workflow
instance as an argument, or a type constructor F[_], such that there is some
workflow instance defined somewhere in the implicits scope.
The following examples are equivalent.
context[List] {
$(List(2, 5) * List(3, 7))
}
context(list) {
$(List(2, 5) * List(3, 7))
}Macro $ takes workflow context from the closest context block.
Alternatively, you can provide type constructor, whose workflow instance will
be taken from the implicits scope.
$[List](List(2, 5) * List(3, 7))That way, $ will disregard any enclosing context block and will work within
Workflow[List] context.
Nested applications of context and $ can be replaced with workflow macro.
You are encouraged to do so for complex blocks of code. You are discourage to
use $ inside. workflow either takes a workflow instance as an argument, or
a type constructor F[_] and rewrites the block of code in the same way as $.
workflow(list) { List(2, 5) * List(3, 7) }There are plenty of built-in workflow instances in traits FunctorInstances,
SemiIdiomInstances, IdiomInstances and MonadInstances. They are all
mixed to the package object of scala.workflow, so once you have workflow._
imported, you get access to all of them. Alternatively, you can import just the
macros import workflow.{context, workflow, $} and access workflow instances
from Functor, SemiIdiom, Idiom and Monad objects.
Any pair of functors, semi-idioms or idioms can be composed. That is, for any
type constructors F[_] and G[_] one can build instances of Functor[F[G[_]]]
and Functor[G[F[_]]] with instances of Functor[F] and Functor[G] (the same
for semi-idioms and idioms).
The syntax for workflow composition is f $ g, where f and g are functor,
semi-idiom or idiom instances of type constructors F[_] and G[_]. The result
would be, correspondingly, functor, semi-idiom or idiom of type constructor
F[G[_]].
context(list $ option) {
$(List(Some(2), Some(3), None) * 10) should equal (List(Some(20), Some(30), None))
}You can also combine workflows of different classes with the same syntax, the
result workflow will implement the weaker interface of the two. For instance,
map[String] $ option will implement Functor, because maps Functor is
weaker than options Monad.
$ method has a counterpart method &, that produces G[F[_]] workflow
instance. Naturally, f $ g = g & f.
Monads and semi-monads in general cannot be composed. Instead, some particular
monads can provide their own specific implementation of $ or & method.
However, even having, say, $ method defined, monad might not be able to
define &. That is, Monad[F] can either construct Monad[F[G[_]] or
Monad[G[F[_]]] with arbitrary Monad[G].
To capture this notion, Monad[F] can be extended to either
LeftComposableMonad[F] or RightComposableMonad[F]. In the first case it is
supposed to be able to produce Monad[F[G[_]]] and therefore implement $
method. In the second case it is supposed to be able to produce Monad[G[F[_]]]
and therefore implement $ method.
For example, Option is right-composable, i.e. can implement
def & [G[_]](g: Monad[G]): Monad[G[Option[_]]], whereas
function monad R ⇒ _ is left-composable and can implement
def $ [G[_]](g: Monad[G]): Monad[R ⇒ G[_]].
So, for monads f and g their composition f $ g will be a monad either
when f is left-composable or g is right-composable or visa versa for &.
When in the expression f $ g f is left-composable and g is right-composable,
f's $ method will be used to construct a composition. When in the expression
g & f f is left-composable and g is right-composable, g's & method will
be used to construct a composition.
The same holds for semi-monads.
Check instances.scala
to ensure, which monads are left or right composable and also composition specs
for exact rules of composition of different workflow classes.
Methods $ and & are called monad transformer elsewhere, although
separation of left and right composability is usually not introduced.
Original paper by McBride and Patterson, that introduced idiom brackets, describes a simple evaluator for a language of expressions. Following that example, here's how it would look like here.
We start with the definition of abstract syntax tree of a language with integers, variables and a plus.
sealed trait Expr
case class Var(id: String) extends Expr
case class Val(value: Int) extends Expr
case class Add(lhs: Expr, rhs: Expr) extends ExprVariables are fetched from the environment of type Env.
type Env = Map[String, Int]
def fetch(x: String)(env: Env): Option[Int] = env.get(x)The evaluator itself is a function of type Expr ⇒ Env ⇒ Option[Int].
def eval(expr: Expr)(env: Env): Option[Int] =
expr match {
case Var(x) ⇒ fetch(x)(env)
case Val(value) ⇒ Some(value)
case Add(x, y) ⇒ for {
lhs ← eval(x)(env)
rhs ← eval(y)(env)
} yield lhs + rhs
}Note, that one have to explicitly pass the environment around and to have
rather clumsy syntax to compute the addition. This can be simplified, once
wrapped into the workflow Env ⇒ Option[_], which can either be constructed
by hand, or composed of Env ⇒ _ and Option workflows.
def eval: Expr ⇒ Env ⇒ Option[Int] =
context(function[Env] $ option) {
case Var(x) ⇒ fetch(x)
case Val(value) ⇒ $(value)
case Add(x, y) ⇒ $(eval(x) + eval(y))
}scala-workflow can be used as syntactic sugar for external libraries and
programming paradigms. In this example, a very simple version of Functional
reactive programming
framework is implemented as Idiom instance.
Cell trait defines a unit of data, that can be assigned with := and fetched
with !. Cells can depend on each others values, much like they do in
spreadsheets.
trait Cell[T] {
def ! : T
def := (value: T) { throw new UnsupportedOperationException }
}Workflow instance, implemented as Idiom, defines cells, that either contain
atomic value that can be reassign or dependent cells, that take value of some
other cell to compute their own (reassigning them doesn't make sense, hence
the exception).
val frp = new Idiom[Cell] {
def point[A](a: ⇒ A) = new Cell[A] {
private var value = a
override def := (a: A) { value = a }
def ! = value
}
def app[A, B](f: Cell[A ⇒ B]) = a ⇒ new Cell[B] {
def ! = f!(a!)
}
}With that instance we can organize reactive computations with simple syntax.
context(frp) {
val a = $(10)
val b = $(5)
val c = $(a + b * 2)
(c!) should equal (20)
b := 7
(c!) should equal (24)
}If you enjoy embedding monadic domain-specific languages in your Scala programs,
you might like syntactical perks scala-workflow could offer. Consider a
little embedded stack programming language.
We represent stack as a regular List, and the result of a program, that
manipulates with a stack, as either a modified stack or an error message
(such as "stack underflow").
type Stack = List[Int]
type State = Either[String, Stack]The evaluation of the program will use state monad, that will disregard
the result of any command, but preserve the state of the stack.
val stackLang = state[State]Unlike State monad in Haskell or scalaz, state doesn't use any specific
wrappers to represent the result of the computation, but rather works with bare
functions.
We would like to define stack operators as Stack ⇒ State functions. To be
able to use them within some workflow, we need to lift them into the monad.
In this example we are only interested in the modified state of the computation,
so the result is always set to ().
def command(f: Stack ⇒ State) = (st: State) ⇒ ((), either[String].bind(f)(st))With command helper we can now define a bunch of commands, working with stack.
def put(value: Int) = command {
case stack ⇒ Right(value :: stack)
}
def dup = command {
case a :: stack ⇒ Right(a :: a :: stack)
case _ ⇒ Left("Stack underflow while executing `dup`")
}
def rot = command {
case a :: b :: stack ⇒ Right(b :: a :: stack)
case _ ⇒ Left("Stack underflow while executing `rot`")
}
def sub = command {
case a :: b :: stack ⇒ Right((b - a) :: stack)
case _ ⇒ Left("Stack underflow while executing `sub`")
}Execution of the program on the empty stack simply takes the modified stack.
def execute(program: State ⇒ (Unit, State)) = {
val (_, state) = program(Right(Nil))
state
}Now, working inside stackLang context we can write programs as sequences of
stack commands and execute them to get modified state of the stack.
context(stackLang) {
val programA = $ { put(5); dup; put(7); rot; sub }
execute(programA) should equal(Right(List(2, 5)))
val programB = $ { put(5); dup; sub; rot; dup }
execute(programB) should equal(Left("Stack underflow while executing `rot`"))
}If you're familiar with SKI-calculus,
you might notice, that point and app methods of function[R] workflow
are in fact K and S combinators. This means that you can construct any
closed lambda-term (in other words, any function) with just those two methods.
For instance, here's how you can define I-combinator (the identity function):
// I = S K K
def id[T] = function[T].app(function[T ⇒ T].point)(function[T].point)Or B-combinator (Scalas Function.compose method or Haskells (.)):
// B = S (K S) K
def b[A, B, C] = function[A ⇒ B].app(function[A ⇒ B].point(function[C].app[A, B]))(function[C].point)
// More concisely with map
def b[A, B, C] = function[A ⇒ B].map(function[C].app[A, B])(function[C].point)Aside from mind-boggling examples like that, there's actually a useful application for these workflows — they can be used in point-free notation, i.e. for construction of complex functions with no function arguments specified.
Point-free notation support is rather limited in Scala, compared to Haskell, but some things still could be done. Here are some examples to get you inspired.
context(function[Char]) {
val isLetter: Char ⇒ Boolean = _.isLetter
val isDigit: Char ⇒ Boolean = _.isDigit
// Traditionally
val isLetterOrDigit = (ch: Char) ⇒ isLetter(ch) || isDigit(ch)
// Combinatorially
val isLetterOrDigit = $(isLetter || isDigit)
}Scalas Function.compose and Function.andThen also come in handy.
context(function[Double]) {
val sqrt: Double ⇒ Double = x ⇒ math.sqrt(x)
val sqr: Double ⇒ Double = x ⇒ x * x
val log: Double ⇒ Double = x ⇒ math.log(x)
// Traditionally
val f = (x: Double) ⇒ sqrt((sqr(x) - 1) / (sqr(x) + 1))
// Combinatorially
val f = sqrt compose $((sqr - 1) / (sqr + 1))
// Traditionally
val g = (x: Double) ⇒ (sqr(log(x)) - 1) / (sqr(log(x)) + 1)
// Combinatorially
val g = log andThen $((sqr - 1) / (sqr + 1))
}It is no secret for a functional programmer that monads are extremely powerful. In fact, most of the features of imperative programming languages, that are usually implemented with variations of mutable state and uncontrolled side effects can be expressed with monads. However, functional purity often comes with the price of rather cumbersome syntax, compared to equivalent imperative constructs.
scala-workflow among other things tries to bridge this gap. In this example
it is used to allow snippets of imperative-looking code to mix pure computations
and logging in purely functional manner.
Workflow instance for this example will be accumulator.
val logging = accumulator[List[String]]Accumulator monad (called Writer monad elsewhere) captures a computation that
aside from producing the result, accumulates some auxiliary output. In this case
it's message in a log, represented as plain list of strings. In general case,
type with defined Monoid instance is expected.
Regular functions naturally don't produce any log messages in accumulator
monad sense. To produce log message, a function must return a tuple of result
of the computation and a list.
def mult(x: Int, y: Int) = (x * y, List(s"Calculating $x * $y"))Functions, that produce no result and some log messages should return a tuple with unit result.
def info(message: String) = (Unit, List(message))Having a snippet of code wrapped in workflow(logging), we can intersperse
pure computations with writing to a log, much like we would do with log4j or
similar framework.
val (result, log) = workflow(logging) {
info("Lets define a variable")
val x = 2
info("And calculate a square of it")
val square = mult(x, x)
info("Also a cube and add them together")
val cube = mult(mult(x, x), x)
val sum = square + cube
info("This is all so silly")
sum / 2
}The result of computation is now stored in result and the log is in
log. Note, that no side effects or mutable state whatsoever were
involved in this example.
result should equal (6)
log should equal (List("Lets define a variable",
"And calculate a square of it",
"Calculating 2 * 2",
"Also a cube and add them together",
"Calculating 2 * 2",
"Calculating 4 * 2",
"This is all so silly"))This project is very experimental and your comments and suggestions are highly appreciated. Drop me a line on twitter or by email, or open an issue here on GitHub. I'm also occasionally on #scala IRC channel on Freenode.