Effect Polymorphism

A main goal of the effect system for Scala is to support polymorphic effects with lightweight syntax.

Effect parameters

The most common solution for polymorphic effects (Polymorphic Effect Systems, Lucassen and Gifford, POPL, 1988) is to introduce a new kind of parameters, namely effect type parameters. In Scala, this could look as follows:

trait Function1[A, R]<E> {       // effect parameters in angle brackets
  def apply(a: A): R ! E         // latent effect annotation on the return type, using !
}
class List[A] {
  def map[B]<E>(f: Function1[A, B]<E>): List[B] ! E = ...
}

This technique is relatively heavy in syntax and would require fundamental changes to existing code, starting with the introduction of an effect parameter to the Function traits.

@pc annotations

So instead we introduce a more lightweight annotation system which is based on a simple observation: The side-effect of map (in the above example) is defined by the side-effect of the function f that is passed into it. Or, more precisely, the side-effect of map is the same as the side-effect of the apply method of parameter f. This exact statement is expressed using the @pc annotations, where "pc" stands for "parameter call", a method call on a parameter. The map method looks as follows:

class List[A] {
  def map[B](f: Function1[A, B]): List[B] @pc(f.apply(%))
}

No change is required to the Function1 trait.

Note that this is a valid receiver for a parameter call, i.e. one can write @pc(this.m()).

The % symbol

Note the special symbol %: there's nothing magic to it, it is simply defined in package object annotation.effects.pc as

def % : Nothing = throw new Error("% should never be called")

The reason for its existence is that the expression we put into the @pc annotation has to be of valid Scala syntax, it has to type-check. So the application to a method needs arguments, and % just expresses an unknown value. There are (at least) two more idiomatic ways to express the same thing, but both of them have drawbacks:

• Existential abstraction: the return type can be an existential type which defines the unknown argument value. This is very verbose though:

  def map[B](f: Function1[A, B]): List[B] @pc(f.apply(x)) forSome { val x: A }

• Functional abstraction:

  def map[B](f: Function1[A, B]): List[B] @pc(f.apply(_))

  The problem here is that this does not compile, the compiler requires a type annotation on the function's argument. So one needs to write @pc(f.apply(_: A)) or @pc((x: A) => f.apply(x))

Both alternatives are more verbose, for that reason we currently use the special symbol %. This might change in future though.

Combining latent and polymorphic effects

A method can have both, polymorphic effects expressed by @pc annotations and monomorphic, latent effects.

class A {
  def f(): Unit @effect1 = ()
  def g(): Unit @effect2 = ()
}

class A1 extends A {
  override def g(): Unit @pure = ()
}

def m(a: A): Unit @effect1 @pc(a.g()) = {
  a.f()
  a.g()
}

When computing the side-effect of the body of m, the effect of calling a.g() is ignored because it is already represented in the signature by the @pc effect annotation.

When applying method m, the total effect is obtained by adding the latent effect and the effect encoded in the @pc annotation, which depends on the argument passed in:

Expression	Latent, monomorphic effect from @effect1	Polymorphic effect from @pc(a.g())	Total effect
m(new A)	@effect1	effect2	@effect1 @effect2
m(new A1)	@effect1	@pure	@effect1

@TODO: explain the following. For effect systems that use an effect checking environment, we cannot just add the two parts. We don't know in what order they happened, and both of them could change the environment such that the other one would be larger. So we need this worst-case-order combining of effets.

Forwarding parameter calls

When calling a method, the @pc-annotations do not always have to be expanded, but they can be transformed into other @pc annotations:

def f(a1: A): B @pc(a1.m()) = {
  a.m()
}
def g(a2: A): B @pc(a2.m()) = {
  f(a2) // since a2 is a parameter, adapt the @pc(a1.m()) annotation to @pc(a2.m()), don't expand it
}

Similarly, for applications of nested methods, the @pc annotations on outer parameters are not expanded:

def f(a: A): B @pc(a.m()) = {
  def g(): B @pc(a.m()) = a.m()
  g() // since a is a also a parameter here, keep the @pc annotation, don't expand it
}

Parameter calls are like effects, but not quite

The parameter call annotations in fact form also some kind of effect system: think of "calling a method on a parameter" as being the side effect. The @pc-effects fulfill all of the properties required for effects, they are idempotent, there's no ordering and they have "may"-semantics.

However, there's one principal difference: the @pc-effects are not "checked", the compiler will not print errors about non-conforming parameter call effects. For example, let's look again at method m defined earlier:

def m(a: A): Unit @effect1 @pc(a.g()) = {
  a.f()
  a.g()
}

There will not be an error message saying that m should annotate the effect @pc(a.f()), even if method f is called on parameter a in the body. Instead, the @pc annotations influence how side-effects are computed for all other effect systems:

• When computing the effect of a.f(), the system will know that the enclosing method does not mention that parameter call, therefore the expression has effect @effect1.
• For the expression a.g(), the latent effect would be @effect2, however since there is a @pc annotation on the enclosing method covering that application, the effect not included.

Future work and limitations

• Combinator functions like map whose side-effect is entirely defined by the side-effects of the arguments are very common. We might introduce special syntax for this kind of methods that don't add any effect themselves, one idea is to use fun instead of def.

• In some situations it would be helpful to enrich the arguments in a @pc annotation with more information, for instance the locality of the argument. Currently we only support @pc(arg.foo(%)). By adding more information, something like @pc(arg.foo(%: Type @loc(locality))), effects delayed by effect polymorphism could be more precise.

  @TODO: show example

• Currently, parameter calls are identified syntacitcally: p.foo(arg) is only recognized as a call on a parameter when p actually is a parameter. Therefore, the following method is not recognized as being effect-polymorphic:

  def m(p: P) {
    val x = p
    x.foo(arg)
  }

• Support things like @pc(a.f.g)? For example:

  def foo(fs: List[A => B]): B @pc(fs.head.apply(%)) = {
    fs.head.apply(new A)
  }