CoRecursive: Coding Stories

Episode: Tech Talk: Generic Programming with Miles Sabin

Host: Adam Gordon Bell | Guest: Miles Sabin

Date: March 7, 2018

Overview

In this episode, Adam Gordon Bell chats with Miles Sabin, creator of the influential Scala library Shapeless, about generic programming, type systems, and pushing the boundaries of what Scala can do. Through stories and technical deep dives, Miles shares how a bit of conference-pressure led to real innovation, the nuanced difference between sums and coproducts, and how his work helps gradually shape the language itself. If you’ve ever struggled with tuples, boilerplate, or dreamed of more expressive type systems, this is the episode for you.

Key Discussion Points & Insights

1. Origin of Shapeless: Innovation by Necessity

• The Conference Proposal Bluff:
  Miles submitted a talk proposal on implementing the “Scrap Your Boilerplate” pattern in Scala, before actually figuring it out. The deadline—and the fact that Simon Peyton Jones would be in the audience—forced him to finish it.

  • Quote [00:00] Miles Sabin: “I put in a talk proposal...with the idea of forcing myself to sit down and work out how to make this thing work. Otherwise I was going to be extremely embarrassed...”

• Defining Generic Programming:

  • It’s essentially the “kinds of polymorphism your language doesn’t support yet.”
  • Goes beyond parametric and subtype polymorphism: it’s about “ways of abstracting which are perhaps richer than we're used to.”
    • Quote [02:20] “Generic programming is kinds of polymorphism that your programming language doesn’t support yet.”

2. Abstracting Over Data Structures: Tuples, Products, and Sums

• Adam’s Tuple Problem:
  Adam shares a real-world motivation: “I had a list of tuples and I needed to kind of group it by the first element into a map... I should be able to write something generic over this.”

  • Quote [00:31] Adam Gordon Bell

• Products vs. Sums (and Coproducts):

  • Product: Represents a combination (e.g., a tuple contains all its parts).
  • Sum (Coproduct): Represents a choice (e.g., an algebraic data type with several options).
  • Coproducts (“sum types” with order/distinction) vs. Sums (unordered, no duplicates).
    • Quote [09:21] Miles Sabin: “A sum type represents A is a CO product. It’s something which represents a choice between different possibilities. A product is something which represents several things.”

• Structural Abstraction:
  Even if types like tuple2 and tuple3 don’t share much in the language, there is a shared structure (product-ness) that generic programming can exploit.

  • Quote [06:32] Miles Sabin: “...what they have in common is that they are both product types...You can think of them as being...represented by a product of the different dimensions.”

3. Scala, Dependent Types, and Language Evolution

• Dependent Types in Scala:
  While Scala doesn’t have full-spectrum dependent types (like Idris), it’s always had forms of them: path-dependent types, etc.

  • Quote [10:38] Miles Sabin: “Dependent types have been a part of Scala since the very beginning...path dependent types have been part of the Scala language specification since 2004 and they really are dependent types.”

• On Complexity and Language Design:
  Miles makes the case that adding advanced abstractions often reduces overall complexity, as it bakes expressiveness into the language rather than encoding it in complex, error-prone workarounds.

  • Quote [17:25] “Typically people are faced with solving pre-existing problems which have a degree of intrinsic complexity...If there is a natural way of expressing something, then the resulting program...is simpler.”

• Macros, Binary Implicits, and Language Progression:
  Shapeless leans on Scala macros, but Miles seeks to reduce this reliance by encouraging features like “by-name implicits” be added to the language proper for typeclass derivation, recursion, and more (see [47:45] and following).

  • Quote [49:33] “It's always been in the back of my mind that I've wanted to try and work out some mechanism for basically adding the minimal set of additional primitives to Scala to be able to...eliminate the need for macros and Shapeless altogether.”

4. Lessons from Shapeless and Generic Programming

• Typeclass Derivation:
  One of Shapeless’s main applications is deriving typeclass instances for Scala types (such as automatic JSON codecs in Circe), eliminating boilerplate.

  • Quote [41:43] Miles Sabin: “So there the idea is...you should be able to present your serialization deserialization library with a value of some data type it knows nothing about, and have the library infer the appropriate serializer and deserializer typeclass instances for that data type without any runtime reflection.”

• Singleton Types/Literal Types:
  Literal types (e.g., type "foo") are now in Scala through persistent community effort—the process involved iterating in compiler forks like Typelevel Scala and then pushing features upstream.

  • Quote [56:35] “Singleton types are making their way...into Scala both in DOTI and just recently in Scala 2.13 by way of the literal types language extension...”

5. Sums vs. Coproducts: Subtle Distinctions

• Why CoProducts Matter:
  Coproducts distinguish order and duplication in type structure, allowing generic programming to treat them dually to products—a foundation for automatic, type-driven computations and simplifications.

  • Quote [25:00] Miles Sabin: “Coproduts and products are essentially dual to one another. It's the usual flip all the arrows and you preserve truths.”

• Nested Structure and Duality:
  The structure of HLists and Coproducts in Shapeless allows most generic operations (concatenation, length, etc.) to be defined in parallel ways.

  • Quote [27:54] “If you look at the structure of the type classes in the instances...they are essentially identical. Modulo the fact that one is parameterized in terms of H lists and the other is parameterized in terms of co product.”

6. Recursion, Implicit Divergence, and ‘Lazy’

• Typeclass Derivation and Recursion:
  Dealing with recursive data types (e.g., lists) in typeclass derivation exposes problems with implicit resolution—Scala’s compiler will halt to avoid infinite recursion.

  • Quote [37:14] “...implicit resolution is almost immediately going to basically fail for you, as you’re trying to summon a type class instance for a recursive data type...compiler will bail with a diverging implicit expansion error...”

• The ‘Lazy’ Workaround and Push for Better Language Support:
  Shapeless introduced a Lazy type constructor using macros to enable recursive values in implicit resolution—a hacky but crucial innovation that Miles hopes to replace with language features like by-name implicit arguments.

7. The Path from Library to Language Feature

• From Typelevel Scala to Scala Proper:
  Features like literal types and by-name implicits begin as experiments in forks, with the end goal of integrating them into official Scala releases.

  • Quote [58:42] “Most of my effort is actually involved on getting things out of the type level Scala compiler fork and into the language proper...”

• Miles’s Vision:
  True success for Shapeless is when it becomes obsolete—all of its power absorbed into the language.

  • Quote [52:11] “I would actually be very, very pleased to see Shapeless disappear, more or less. It just simply become a bunch of ways of just using first class features of the language itself.”

Notable Quotes & Memorable Moments

• [00:00] Miles on Deadlines:
  “I put in a talk proposal...with the idea of forcing myself to sit down and work out how to make this thing work. Otherwise I was going to be extremely embarrassed...”

• [02:20] On Generic Programming:
  “Generic programming is kinds of polymorphism that your programming language doesn’t support yet.”

• [17:25] On Complexity:
  “If there is a natural way of expressing something, then the resulting program is...simpler.”

• [47:45] On Macros and Language Design:
  “It’s always been in the back of my mind that I’ve wanted to try and work out some mechanism for basically adding the minimal set of additional primitives to Scala...”

• [52:11] On Shapeless’s Future:
  “I would actually be very, very pleased to see Shapeless disappear, more or less.”

• [60:12] Final Advice:
  “Absolutely do it. Yes, I highly recommend it.” — On submitting conference talks for things you haven’t built yet.

Important Timestamps

• 00:00-02:20: Miles’s origin story for Shapeless—the motivating conference bluff.
• 06:06-09:21: Explaining generic abstraction over tuples, products, and sums.
• 10:23-16:29: Dependent types in Scala vs. Idris, complexity in language vs. code.
• 20:01-21:18: Shapeless macros vs. built in language features (binary implicits).
• 25:00-29:10: Sums, coproducts, their distinction, and why it matters.
• 37:14-42:22: Typeclass derivation, implicit recursion, and the role of the Lazy construct.
• 47:45-56:35: The process of getting features from Shapeless into Scala proper, with literal types as a case study.
• 58:42-60:20: The role of Typelevel Scala and lessons on innovation through public commitment.

Summary

This episode is an insightful, candid exploration of modern generic programming, told through the story of Shapeless and its creator. Miles Sabin’s work illustrates how passionate developers can drive the evolution of a language—even if it means writing code “just in time” for a conference talk. It’s a must-listen for anyone interested in functional programming, type systems, or the design of programming languages.