# P∀scal

Concise syntax for **p**olymorphic, a.k.a. universally quantified (**∀**), values in **Scal**a.

## 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:

**Verbose syntax**for creating polymorphic values (an anonymous class implementing the interface).- 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. - 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. https://github.com/scalaz/scalaz/pull/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)`

If your project uses Scala 2.10, also add

```
libraryDependencies ++= (scalaBinaryVersion.value match {
case "2.10" =>
compilerPlugin("org.scalamacros" % "paradise" % "2.1.0" cross CrossVersion.full) :: Nil
case _ =>
Nil
})
```

`kind-projector`

Relation to `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.