What is Type Projection in Scala, and Why is it Unsound?

For a very long time, Scala has had a featured named type projection, which lets one refer to a type member defined in an existing type (i.e., to “project it” or “pick it out”). The syntax is T#A, where T is some type that is know to contain a type member named A.

Type projections was shown to be unsound, which means that it can be used to subvert the type system and cause crashes at runtime. The feature is consequently being removed from Scala 3, the upcoming major version of the Scala language.

In this article, I describe how type projection works with several examples, and explain why it is unsound.

This post is meant to be understandable by anyone with basic knowledge of typed programming languages.

Scala Pattern Matching Warts and Improvements

Pattern matching is a central feature in most functional programming languages. Indeed, it is the main tool for expressing data flow, and the core of Functional Programming is thinking about data-flow rather than control-flow, as explained in Haoyi’s excellent blog post.

Scala offers an interesting and powerful take on pattern matching: in Scala, pattern matching is not fundamentally based on algebraic data types (ADT); rather, it is defined in a way that is compatible with Scala’s encoding of ADTs but is also more general. This allows users to abstract pattern definitions, and to define custom “extractor” objects.

Yet, there are many ways in which pattern matching in Scala is currently lacking, or even plainly deficient, compared to other languages. I made a list of such deficiencies below, in the hope that they will eventually be fixed. I separated them into two categories:

Comprehending Monoids with Class

This is a partial transcription of an extended-abstract talk I gave at the TyDe 2018 Type-Driven Development workshop, colocated with ICFP.

The main idea was to revisit an old concept — monoid comprehensions — and to explore what it gives us in the context of a functional programming language with support for type classes, as well as how it compares to the more traditional monad comprehension approach.

In summary, we argue that for expressing queries over collections of data, monoid comprehension can be more flexible, simpler, more efficient, and safer than its monadic counterpart. I substantiate these points in the following blog post, and recapitulate them in the conclusion.

In a future follow-up to this post, I will transcribe the rest of my TyDe talk. We will see how to embed and extend the original monoid comprehension calculus (MCC), using the host language’s static type system to enforce some properties of monoid queries at compile time.

A Dual to Iterator, and How to Abuse For Comprehension

Have you ever wondered why there is no efficient and convenient way of merging unrelated collection traversals in Scala’s standard library? – such as computing the average of a list as its sum divided by its count, but in one pass…

In this post, I show how to abuse for comprehension and leverage the following syntax to define aggregators, the dual to iterators:

def average = for { s <- sum[Double]; c <- count } yield s/c
val ls = List(1.0, 2.0, 3.0)
assert(average(ls) == 2.0)

// `average` can then be composed within bigger loops modularly:
def avgmax = for {
  avg <- average
  m   <- max[Double]
} yield (avg,m)
// this does a single traversal of `ls`:
assert(avgmax(ls) == (2.0, Some(3.0)))

Throwing Other Things than Exceptions, Continued

Yesterday, I demonstrated how abusing the exception facilities of Java could allow us to conveniently encode tagged union types.

Here is a C++11 program demonstrating another use of exceptions for quickly breaking out of nested closure calls.

Algebraic Data Types in Java 6

Motivation

Java is an opinionated programming language, in that it forces users to embrace Object Oriented Programming. Even after the introduction of lambdas in Java 8, it still suffers from a lack of abstractions commonly found in functional programming languages such as Scala and OCaml.

One of these abstractions is Algebraic Data Types – in particular tagged unions (also called sum types), which allow the definition of types that support several possible representations. Tagged unions are similar to Java enums, the only difference being that each of the cases can embed its own data.

Algebraic data types are usually associated with pattern-matching, another feature that programmers used to the functional style miss in Java. However, in this post I will only focus on describing a nice and simple trick that allows us to encode tagged unions in Java (working with versions of Java as old as Java 6 – perhaps even older), supporting exhaustiveness checks and meta cases, but without support for pattern matching.1

  1. Since the introduction of lambda-expressions in Java 8, it has become possible to encode some forms of pattern matching, such as in this blog post