P∀scal

Concise syntax for polymorphic, a.k.a. universally quantified (∀), values in Scala.

Introduction: Polymorphic values

A polymorphic (also universally quantified) value a of type ∀A. F[A] is a value that qualifies as a value of type F[A] for any type A. That is, a single value that is an instance of F[Int], F[String], F[List[Boolean]], ... simultaneously.

Parametric polymorphism was introduced in System F with the following syntax:

Λα. t : ∀α. T

where t is a term, T is a type, and α is a type variable that can occur in both t and T. (Τhe expression after the colon is the type of the lambda expression preceding it.)

For example, the following is the identity function:

Λα. λ(x:α). x : ∀α. α -> α

Encoding polymorphic values in Scala

Scala lacks direct support for polymorphic values. It has generic types (class Foo[A]) and methods (def foo[A]). These are sufficient for some use cases. For example, the above polymorphic identity function can be written as a polymorphic method:

def identity[α](x: α): α = x

or, alternatively

def identity[α]: (α => α) = (x: α) => x

The shortcoming is that a method cannot be passed as an argument (i.e. value) to another method. The usual solution is to wrap the method in an object, which can be passed around as a value:

trait ForAll[F[_]] {
  def apply[A]: F[A]
}

type IdentityFun[A] = A => A

val identity: ForAll[IdentityFun] = new ForAll[IdentityFun] {
  def apply[A]: IdentityFun[A] = x => x
}

// usage
identity[Int](42)

Now identity is a value that can be freely passed to other methods or functions.

This encoding, however, has several drawbacks:

1. Verbose syntax for creating polymorphic values (an anonymous class implementing the interface).
2. Requires a dedicated wrapper type for each arity of type parameters. In the example above, we used ForAll[F[_]], but elsewhere we might also need ForAll2[F[_, _]], ForAllH[F[_[_]]], etc.
3. Specialization of polymorphic values (ForAll[F]) to a specific type (e.g. F[Int]) may in general allocate new objects.

This project addresses (only) the first problem, namely the verbosity of polymorphic value creation.

The second problem would be addressed by kind-polymorphism (which, unfortunately, Scala also lacks).

The third problem can be addressed by other methods, e.g. scalaz/scalaz#1417.

More concise syntax

This project provides more concise syntax for creation of polymorphic values (in the usual encoding (see above)). It tries to approximate the System F syntax mentioned above (Λα. t : ∀α. T).

It works as a compiler plugin that performs the following rewrites:

Λ[α](t): T

is analogous to System F's

Λα. t : T

(where T is of the form ∀α. U) and is rewritten to

new T { def apply[α] = t }

For example

Λ[α](x => x): ForAll[IdentityFun]

is rewritten to

new ForAll[IdentityFun] { def apply[α] = x => x }

Generalizing to multiple type parameters of arbitrary kinds,

Λ[A, B[_], ...](t): T

is rewritten to

new T { def apply[A, B[_], ...] = t }

Note that the type ascription (: T) of the Λ-expression cannot be omitted (it cannot be inferred, since P∀scal runs before typer).

We see that we are basically just providing a more concise syntax for instantiating types with a single abstract generic parameterless method named apply.

In addition to the Λ-syntax above, we provide an alternative ν-syntax that reads more like the expression that it is rewritten to:

ν[T][A, B[_], ...](t)

is rewritten to

new T { def apply[A, B[_], ...] = t }

"ν" is the Greek lowercase letter "Nu", pronounced "new".

In the common case when the generic method has a single monomorphic (i.e. of kind *) type parameter which is not referenced in the method body (t), the ν-syntax allows one to omit the type parameter:

ν[T](t)

is rewritten to

new T { def apply[A] = t }

where A is a fresh name.

The ν-syntax also allows one to specify the method name in case it is different from apply:

ν[T].foo[A, B[_], ...](t)

is rewritten to

new T { def foo[A, B[_], ...] = t }

See the test cases for some examples.

Self-references

It is possible for a polymorphic value to reference itself. For this, add a self-identifier and '=' before the polymorphic body. For example:

ν[T].foo[A](self = t)

where the term t can use the identifier self to refer to itself. It is rewritten to

new T { self =>
  def foo[A] = t
}

Using the plugin

To use this plugin in your project, add the following line to your build.sbt file:

addCompilerPlugin("com.github.tomasmikula" % "pascal" % "0.4.0" cross CrossVersion.full)

Relation to kind-projector

kind-projector's polymorphic lambdas provide similar functionality to this plugin. Our approach is more general in the following respects:

• Polymorphic values generalize polymorphic functions.
• We support quantification over:
  • multiple type parameters;
  • type parameters of arbitrary kinds.
• We support referencing type parameters from the method body.

Actually, this work started as a PR at kind-projector. For the lack of interest and for the sake of separation of concerns, I eventually published this as a separate project. This project borrows some code directly from kind-projector and is distributed under the same license (MIT) and original author's copyright notice.