Skip to content

Latest commit

 

History

History
1247 lines (923 loc) · 36 KB

slides.gen.md

File metadata and controls

1247 lines (923 loc) · 36 KB

Zero Cost Abstractions

Eliminating runtime overhead in Scala

http://caryrobbins.com/zero-talk

Cary Robbins

June 5, 2019

Me

  • Software development consultant for Estatico Studios
  • Primarily work in Scala and Haskell, but love digging into new languages.
  • Interested in collaborating? Send me a note at: cary@estatico.io

Zero Cost Strategies

  • Polymorphic values
  • NewTypes
  • Generic programming

Note: We're going to discuss 3 different strategies for improving existing abstractions with implementations that do not incur runtime overhead.

WARNING

We will be using

asInstanceOf

a lot.

It's cool don't worry.

But runtime overhead isn't my bottleneck!

Note:

Sure, maybe it's not your bottleneck. Your bottleneck is probably IO. But this doesn't mean we shouldn't discover ways of optimizing our compiled code to eliminate overhead which is truly unnecessary.

But muh Premature Optimization is evil!

Note:

Yes, this is true. Don't optimize for the sake of optimizing, and you should benchmark if you are doing heavy optimizations.

But what we're going to cover here are general optimizations which should not only improve runtime performance, but actually give you new ways of programming that you may not be aware of.

We're talking JVM

(Although, many of these work just as good if not better in ScalaJS)

Polymorphic values


implicit def eitherFunctor[L]: Functor[Either[L, ?]] = new Functor[Either[L, ?]] {
  override def map[A, B](fa: Either[L, A])(f: A => B): Either[L, B] =
    fa.right.map(f)
}
**Problem is...** 

implicitly[Functor[Either[String, ?]]]
// $anon$1@2cf46f9e

implicitly[Functor[Either[String, ?]]]
// $anon$1@7cd0fda6 ← new instance!

Note: Here's an example of a polymorphic type class instance, the Functor instance for Either.

Functor's type argument must be a type which itself takes a single type argument. Either takes two, so we must pass the Left type argument into the implicit def.

Problem is...each time we summon the implicit instance, we alloc a new instance.

Caching Polymorphic Values


private val eitherFunctorCached = new Functor[Either[Nothing, ?]] {
  override def map[A, B](fa: Either[Nothing, A])(f: A => B): Either[Nothing, B] =
    fa.right.map(f)
}

implicit def eitherFunctor[L]: Functor[Either[L, ?]] =
  eitherFunctorCached.asInstanceOf[Functor[Either[L, ?]]]
**As you'd expect...** 

implicitly[Functor[Either[String, ?]]]
// $anon$1@3c466028

implicitly[Functor[Either[String, ?]]]
// $anon$1@3c466028 ← same instance!

Note: Here we implement the same Functor instance, except this time instead of making it polymorphic, we stub in the Nothing type for the Left type param so we can cache it into a val. We then have the implicit def simply call the val and cast it to the appropriate type.

Why does this work?

Type parameters are erased at runtime


implicit def eitherFunctor[L]: Functor[Either[L, ?]] = new Functor[Either[L, ?]] {
  override def map[A, B](fa: Either[L, A])(f: A => B): Either[L, B] =
    fa.right.map(f)
}


// Bytecode
public eitherFunctor()LFunctor;
  NEW $anon$1                      // new anon Functor instance
  DUP
  INVOKESPECIAL $anon$1.<init> ()V // Functor constructor "init"
  ARETURN

Note:

Why does this work? Type parameters are erased at runtime.

Why does this work?


private val eitherFunctorCached = new Functor[Either[Nothing, ?]] {
  override def map[A, B](fa: Either[Nothing, A])(f: A => B): Either[Nothing, B] =
    fa.right.map(f)
}

implicit def eitherFunctor[L]: Functor[Either[L, ?]] =
  eitherFunctorCached.asInstanceOf[Functor[Either[L, ?]]]


// Bytecode
public eitherFunctor()LFunctor; // ← Runtime type is still Functor
  ALOAD 0
  INVOKESPECIAL eitherFunctorCached ()LFunctor;
  ARETURN            // Same runtime type ↑

The @cached macro


@cached
implicit def eitherFunctor[L]: Functor[Either[L, ?]] = new Functor[Either[L, ?]] {
  override def map[A, B](fa: Either[L, A])(f: A => B): Either[L, B] =
    fa.right.map(f)
}
Expands to... 

implicit def eitherFunctor[L]: Functor[Either[L, ?]] =
  __cached__eitherFunctor.asInstanceOf[Functor[Either[L, ?]]]

private val __cached__eitherFunctor = new Functor[Either[Nothing, ?]] {
override def map[A, B](fa: Either[Nothing, A])(f: A => B): Either[Nothing, B] =
fa.right.map(f)
}

newtypes

NewTypes: A Motivation

Haskell's newtype gives us type safety without the cost


newtype WidgetId = WidgetId String

myId = WidgetId "a"  -- ← Is just a String at runtime

upperId :: WidgetId -> WidgetId
upperId (WidgetId s) = WidgetId (map toUpper s)
-- The unwrap ↑ and rewrap ↑ do not occur at runtime

Note: In Haskell, the newtype keyword allows us to define a new type which incurs no overhead and is just some other type at runtime.

In this case, we're defining a WidgetId to improve type safety so we know that this value is more than just a String.

Wrapping and unwrapping newtype values incurs no overhead at runtime; it is all omitted during compilation.

NewTypes: Specialized type class instances


instance ToJSON WidgetId where
  toJSON (WidgetId s) = object [ "widgetId" .= toJSON s ]


newtype Sum = Sum Int

instance Monoid Sum where
mempty = 0
mappend (Sum x) (Sum y) = Sum (x + y)


newtype Product = Product Int


instance Monoid Product where
mempty = 1
mappend (Product x) (Product y) = Product (x * y)

Note: Another common use case for newtypes is to give us the ability to provide alternative type class implementations.

Here, instead of using String's default ToJSON instance, we can provide our own implementation for our WidgetId.

The canonical example of this is that Int forms a Monoid via addition and multiplication. Instead of having to decide which instance we want Int to use, we can say that Int is not a Monoid on its own, and that only Sum and Product (which are newtype wrappers around Int) are.

NewTypes: O(n) ⇒ O(1) conversions


ids :: [String]
ids = ["a","b","c","d","e"]

xs :: [WidgetId]
xs = coerce ids :: [WidgetId]

Value Classes: NewTypes for Scala?


final case class WidgetId(value: String) extends AnyVal
Usage 

def getWidget(id: WidgetId): Widget = ???


// Bytecode
public getWidget(Ljava/lang/String;)LWidget;

Note: Here is a value class. This allows us to define a new class which, at runtime, should be represented as a String. We can confirm this by looking at the compiled bytecode.

Value Class Pitfalls: Generics


def optId = Option(WidgetId("a"))


// Bytecode
public optId()Lscala/Option;
  GETSTATIC scala/Option$.MODULE$ : Lscala/Option$;
  NEW WidgetId // ← We don't like this
  DUP
  LDC "a"
  INVOKESPECIAL WidgetId.<init> (Ljava/lang/String;)V
  INVOKEVIRTUAL scala/Option$.apply (Ljava/lang/Object;)Lscala/Option;
  ARETURN

Note: Let's see what's wrong with value classes. One of the big problems with them is when you try to use them with generics.

Also remember that since generics are erased at runtime, this method returns Option, not Option of String or WidgetId.

Value Class Pitfalls: Generics


def unOptId = optId.get


// Bytecode
public unOptId()Ljava/lang/String;
  ALOAD 0
  INVOKEVIRTUAL optId ()Lscala/Option;
  INVOKEVIRTUAL scala/Option.get ()Ljava/lang/Object;
  CHECKCAST WidgetId // ← Why the allocation occurs
  INVOKEVIRTUAL WidgetId.value ()Ljava/lang/String;  // ← Unwrap ლ(ಠ益ಠლ)
  ARETURN

Note:

  • The allocation must occur so the JVM can validate that we actually have a WidgetId at runtime.
  • Interestingly enough, we then just unwrap the value we had, getting back the String we wrapped to begin with.

Value Class Pitfalls: O(n) conversions


def convIdList(xs: List[String]): List[WidgetId] =
  xs.map(WidgetId.apply) // ← Hey JIT, try to optimize this

Note: Any time we need to convert container elements to value class instances, we'll always incur a performance overhead; this just can't be optimized away, not even by the JIT.

Tagged Types


// Adapted from scalaz
type @@[A, T] = { type Tag = T; type Self = A }
def tag[A, T](a: A): A @@ T = a.asInstanceOf[A @@ T]

trait WidgetIdTag
type WidgetId = String @@ WidgetIdTag
def WidgetId(s: String): WidgetId = tag[String, WidgetIdTag](s)

Note: Scalaz and shapeless provide something called tagged types. Note that Scalaz's and shapeless' implementation of tagged types are different, but we'll cover the difference later.

A tagged type will be defined with this @@ type operator. We'll use a refinement to hold onto the types passed in but not expose it so the compiler sees this as a unique type. This refinement will be represented as a java Object at runtime.

To construct one, we'll just perform a cast using .asInstanceOf. This ends up being fine since any value we pass in will be an instance of Object.

Tagged Types: Under the hood


def tag[A, T](a: A): A @@ T = a.asInstanceOf[A @@ T]


// Bytecode
public tag(Ljava/lang/Object;)Ljava/lang/Object;
  ALOAD 1
  ARETURN


def WidgetId(s: String): WidgetId = tag[String, WidgetIdTag](s)


// Bytecode
public WidgetId(Ljava/lang/String;)Ljava/lang/Object;
  ALOAD 0
  ALOAD 1
  INVOKEVIRTUAL tag (Ljava/lang/Object;)Ljava/lang/Object;
  ARETURN

Tagged Types: Under the hood


def optId = Option(WidgetId("a"))


// Bytecode
public optId()Lscala/Option;
  GETSTATIC scala/Option$.MODULE$ : Lscala/Option$;
  ALOAD 0
  LDC "a"
  INVOKEVIRTUAL WidgetId (Ljava/lang/String;)Ljava/lang/Object;
  INVOKEVIRTUAL scala/Option$.apply (Ljava/lang/Object;)Lscala/Option;
  ARETURN

Tagged Types: Under the hood


def unOptId = optId.get


// Bytecode
public unOptId()Ljava/lang/Object;
  ALOAD 0
  INVOKEVIRTUAL optId ()Lscala/Option;
  INVOKEVIRTUAL scala/Option.get ()Ljava/lang/Object;
  ARETURN

Tagged Types: Faster conversions


def convIdList(ids: List[String]): List[WidgetId] =
  ids.asInstanceOf[List[WidgetId]]


// Bytecode
public convIdList(Lscala/collection/immutable/List;)Lscala/collection/immutable/List;
  ALOAD 1
  ARETURN

Note: So far this isn't looking too bad. These are all constant operations that are really easy for the JIT to inline. We have no new allocations and no checkcasts.

Tagged Types: Things left to be desired

  • How do we deal with type class instances/implicits?
  • How do we add methods?
  • Can we make casting safer?
  • Can we make it less ad hoc and reduce boilerplate?

NewType: Formalizing the approach


type WidgetId = WidgetId.Type
object WidgetId {
  type Base = Any { type WidgetId$newtype }
  trait Tag extends Any
  type Type <: Base with Tag

  def apply(value: String): WidgetId = value.asInstanceOf[WidgetId]

  implicit final class Ops(private val me: WidgetId) extends AnyVal {
    def value: String = me.asInstanceOf[String]
  }
}

Note:

Let's start with a companion object. This should be where implicits are defined for our newtype.

Base -

  • A unique type that gets compiled as Object in the bytecode
  • Any
    • Signals we want Object
    • Aid in array construction for primitives
  • Refinement
    • Ensures that Any is actually used as the base type instead of trait mixins

Tag

  • A unique trait that we'll mix into our newtype to aid in implicit resolution.
  • Similarly as with Base above it, we need to extend Any to help with primitives.

Type -

  • This is our final newtype
  • Defined as an abstract type to prevent scalac from expanding the type alias which would break implicit resolution

WidigetId - Top-level type alias for convenience and simplicity

apply - Smart constructor for our newtype

Ops - Extension methods for our newtype

NewType: Type semantics


WidgetId("a").toUpperCase // Does not compile
WidgetId("a").value.toUpperCase // Compiles

def upperStr(s: String) = s.toUpperCase
upperStr("a") // Compiles
upperStr(WidgetId("a")) // Does not compile

def upperWidgetId(id: WidgetId) = WidgetId(id.value.toUpperCase)
upperWidgetId("a") // Does not compile
upperWidgetId(WidgetId("a")) // Compiles

NewType: Builder trait


trait NewType[Repr] {
  type Base = Any { type Repr$newtype = Repr }
  trait Tag extends Any
  type Type <: Base with Tag
  def apply(value: Repr): Type = value.asInstanceOf[Type]
  def repr(x: Type): Repr = x.asInstanceOf[Repr]
}
Usage 

type WidgetId = WidgetId.Type
object WidgetId extends NewType[String] {
  implicit final class Ops(private val me: WidgetId) extends AnyVal {
    def value: Repr = repr(me)
  }
}

Note:

So what does this buy us?

We get a smart constructor and destructure for free. We get safe casts for collection types. We get an idiomatic companion object that just works for implicit resolution.

NewType: At runtime


public apply(Ljava/lang/Object;)Ljava/lang/Object;
  ALOAD 0
  ALOAD 1
  INVOKESTATIC NewType.apply$ (LNewType;Ljava/lang/Object;)Ljava/lang/Object;
  ARETURN

public static synthetic apply$(LNewType;Ljava/lang/Object;)Ljava/lang/Object;
  ALOAD 0
  ALOAD 1
  INVOKESPECIAL NewType.apply (Ljava/lang/Object;)Ljava/lang/Object;
  ARETURN

public default apply(Ljava/lang/Object;)Ljava/lang/Object;
  ALOAD 1
  ARETURN

NewType: Extension Methods


def widgetIdValue = WidgetId("a").value


// Bytecode
public widgetIdValue()Ljava/lang/String;
  GETSTATIC WidgetId$.MODULE$ : LWidgetId$;
  GETSTATIC WidgetId$.MODULE$ : LWidgetId$;
  LDC "a"
  INVOKEVIRTUAL WidgetId$.apply (Ljava/lang/Object;)Ljava/lang/Object;
  INVOKEVIRTUAL WidgetId$.Ops (Ljava/lang/Object;)Ljava/lang/Object;
  INVOKEVIRTUAL WidgetId$Ops$.value$extension (Ljava/lang/Object;)Ljava/lang/String;

NewType: Extension Methods


implicit final class Ops(private val self: Type) extends AnyVal {
  def value: Repr = repr(self)
}


// Bytecode
public final value$extension(Ljava/lang/Object;)Ljava/lang/String;
  GETSTATIC WidgetId$.MODULE$ : LWidgetId$;
  ALOAD 1
  INVOKEVIRTUAL WidgetId$.repr (Ljava/lang/Object;)Ljava/lang/Object;
  CHECKCAST java/lang/String
  ARETURN

NewType: Generics


def optId = Option(WidgetId("a"))


// Bytecode
public optId()Lscala/Option;
  GETSTATIC scala/Option$.MODULE$ : Lscala/Option$;
  GETSTATIC WidgetId$.MODULE$ : LWidgetId$;
  LDC "a"
  INVOKEVIRTUAL WidgetId$.apply (Ljava/lang/Object;)Ljava/lang/Object;
  INVOKEVIRTUAL scala/Option$.apply (Ljava/lang/Object;)Lscala/Option;
  ARETURN

NewType: Generics


def unOptId = optId.get


public unOptId()Ljava/lang/Object;
  ALOAD 0
  INVOKEVIRTUAL optId ()Lscala/Option;
  INVOKEVIRTUAL scala/Option.get ()Ljava/lang/Object;
  ARETURN

NewType: Constant-time conversions


def convIdList(ids: List[String]): List[WidgetId] = ids.asInstanceOf[List[WidgetId]]


// Bytecode
public convIdList(Lscala/collection/immutable/List;)Lscala/collection/immutable/List;
  ALOAD 1
  ARETURN

NewTypes: Primitive Problems


type Feet = Feet.Type
object Feet extends NewType.Of[Int]


def mkFeet = Feet(12)


// Bytecode
public mkFeet()Ljava/lang/Object;
  GETSTATIC Feet$.MODULE$ : LFeet$;
  BIPUSH 12
  INVOKESTATIC scala/runtime/BoxesRunTime.boxToInteger (I)Ljava/lang/Integer;
  INVOKEVIRTUAL Feet$.apply (Ljava/lang/Object;)Ljava/lang/Object;
  ARETURN

NewSubType: An Attempt


trait NewSubType[Repr] {
  trait Tag extends Any
  type Type <: Repr with Tag

  def apply(x: Repr): Type = x.asInstanceOf[Type]
  def repr(x: Type): Repr = x.asInstanceOf[Repr]
}

NewSubType


type Feet = Feet.Type
object Feet extends NewSubType[Int] {
  implicit final class Ops(private val me: Feet) extends AnyVal {
    def value: Int = repr(me)
  }
}


Feet(1).signum // Compiles, returns Int

def add(x: Int, y: Int): Int = x + y
add(Feet(1), Feet(2)) // Compiles, returns Int


def addFeet(x: Feet, y: Feet): Feet = Feet(x.value + y.value)
addFeet(Feet(1), Feet(2)) // Compiles, returns Feet
addFeet(1, 2) // Does not compile

NewSubType: Is it really zero cost?


def mkFeet = Feet(12)


// Bytecode
public mkFeet()I
  GETSTATIC Feet$.MODULE$ : LFeet$;
  BIPUSH 12
  INVOKESTATIC scala/runtime/BoxesRunTime.boxToInteger (I)Ljava/lang/Integer;
  INVOKEVIRTUAL Feet$.apply (Ljava/lang/Object;)Ljava/lang/Object; // oh
  INVOKESTATIC scala/runtime/BoxesRunTime.unboxToInt (Ljava/lang/Object;)I // wat
  IRETURN

NewSubType: Fixing our broken ctor


type Feet = Feet.Type
object Feet extends NewSubType[Int] {
  override def apply(x: Int): Feet = x.asInstanceOf[Feet]
}


public apply(I)I
  ILOAD 1
  INVOKESTATIC scala/runtime/BoxesRunTime.boxToInteger (I)Ljava/lang/Integer;
  INVOKESTATIC scala/runtime/BoxesRunTime.unboxToInt (Ljava/lang/Object;)I // srsly
  IRETURN

NewSubType: Giving scalac a hand


type Feet = Feet.Type
object Feet extends NewSubType.Of[Int] {
  override def apply(x: Int): Feet = x.asInstanceOf[Feet]
}


% scalac -opt:l:inline ...


public apply(I)I
  ILOAD 1
  IRETURN // ...Did we just get it to work?


def mkFeet = Feet(12)


public mkFeet()I
  GETSTATIC Feet$.MODULE$ : LFeet$;
  BIPUSH 12
  INVOKEVIRTUAL Feet$.apply (I)I
  IRETURN // ...We did!

Coercible: Abstracting over newtypes


trait Coercible[A, B] {
  final def apply(a: A): B = a.asInstanceOf[B]
}

Generated Coercible instances


trait NewType[Repr] {
  type Base = Any { type Repr$newtype = Repr }
  trait Tag extends Any
  type Type <: Base with Tag
  def apply(value: Repr): Type = value.asInstanceOf[Type]
  def repr(x: Type): Repr = x.asInstanceOf[Repr]

  implicit val coerceTo:   Coercible[Repr, Type] = Coercible.instance
  implicit val coerceFrom: Coercible[Type, Repr] = Coercible.instance
}

Coercible in action



WidgetId("foo").coerce[String].toUpperCase

def upper(s: String) = s.toUpperCase

upper(WidgetId("foo").coerce) // Compiles, returns String

implicit def coercibleListTo[A, B](
  implicit ev: Coercible[A, B]
): Coercible[List[A], List[B]] = Coercible.instance

List("a","b","c").coerce[List[WidgetId]]

Aside on type roles

estatico/scala-newtype#29


trait TypeRole[A] {
  type Role
}

object TypeRole {

  def mk[A, R]: TypeRole[A] { type Role = R } =
    _instance.asInstanceOf[TypeRole[A] { type Role = R }]

  private val _instance = new TypeRole[Nothing] {}

  type Nominal[A] = TypeRole[A] { type Role = types.Nominal }
  type Representational[A] = TypeRole[A] { type Role = types.Representational }

  object types {
    sealed trait Representational
    sealed trait Nominal
  }
}

Shilling for @newtype

https://github.com/estatico/scala-newtype


import io.estatico.newtype.macros._

@newtype case class WidgetId(value: String)

@newsubtype case class Feet(value: Int)

@newtype: inspecting generated code


@newtype(debug = true) case class WidgetId(value: String)


type WidgetId = WidgetId.Type
object WidgetId {
  type Repr = String
  type Base = Any { type WidgetId$newtype }
  abstract trait Tag extends Any
  type Type <: Base with Tag

def apply(value: String): WidgetId = value.asInstanceOf[WidgetId];


def deriving[TC[_]](implicit ev: TC[Repr]): TC[Type] = ev.asInstanceOf[TC[Type]]


// ...
}

@newtype: deriving type class instances


@newtype case class Attributes(toList: List[(String, String)])
object Attributes {
  implicit val monoid: Monoid[Attributes] = deriving
}

@newtype: derivingK


@newtype case class Slice[A](toVector: Vector[A])
object Slice {
  implicit val monad: Monad[Slice] = derivingK
}

customized smart constructors


@newsubtype class PosInt(val toInt: Int)
object PosInt {
  def of(x: Int): Option[PosInt] =
    if (x < 0) None else Some(x.coerce[PosInt])
}


PosInt(1) // Compile error: PosInt.type does not take parameters

PosInt.of(1)  // Some(1): Option[PosInt]
PosInt.of(-1) // None:    Option[PosInt]

Unboxed Maybe type


@newtype class Maybe[A](val unsafeGet: A) {
  def isEmpty:   Boolean = unsafeGet == Maybe._empty
  def isDefined: Boolean = unsafeGet != Maybe._empty

  def map[B](f: A => B): Maybe[B] =
    if (isEmpty) Maybe.empty else Maybe(f(unsafeGet))

  def filter(p: A => Boolean): Maybe[A] =
    if (isEmpty || !p(unsafeGet)) Maybe.empty else this
  ...
}


object Maybe {
  def apply[A](a: A): Maybe[A] = if (a == null) empty else unsafe(a)
  def unsafe[A](a: A): Maybe[A] = a.asInstanceOf[Maybe[A]]
  def empty[A]: Maybe[A] = _empty.asInstanceOf[Maybe[A]]
  private val _empty = new Empty
  private final class Empty { override def toString = "Maybe.empty" }
}

NewType Transformers


@newtype case class OptionT[F[_], A](value: F[Option[A]]) {

  def map[B](f: A => B)(implicit F: Functor[F]): OptionT[F, B] =
    OptionT(F.map(value)(_.map(f)))

  def flatMapF[B](f: A => F[Option[B]])(implicit F: Monad[F]): OptionT[F, B] =
    OptionT(F.flatMap(value)(_.fold(F.pure[Option[B]](None))(f)))

  def flatMap[B](f: A => OptionT[F, B])(implicit F: Monad[F]): OptionT[F, B] =
    flatMapF(a => f(a).value)

  ...
}

Generic Programming: Shapeless


import shapeless._

case class Foo(a: Int, b: String)

val foo = Foo(1, "hey")
val g = Generic[Foo].to(foo)
// g: Int :: String :: HNil
//  = 1   :: "hey"  :: HNil

foo eq g
// false

HList allocations


(1 :: "hey" :: HNil) == g
// true

new ::(1, new ::("hey", HNil)) == g
// true

HList: An alternative


sealed trait HList
final case class ::[+H, +T <: HList](head : H, tail : T) extends HList
sealed trait HNil extends HList
Alternatively... 

sealed trait GList
sealed trait #:[H, T <: GList] extends GList
sealed trait GNil extends GList
object GList {
  @newtype case class Of[A, L <: GList](value: A)
  object Of {           //  ^ phantom type
    // It's valid (and desirable) to coerce to the tail of our GList
    implicit def coerceToTail[A, H, T <: GList]: Coercible[Of[A, H #: T], Of[A, T]] =
        Coercible.instance
  }
}

Generic Products


trait GProduct[A] { type Repr <: GList }

object GProduct {

  type Aux[A, R <: GList] = GProduct[A] { type Repr = R }

  def to[A](a: A)(implicit ev: GProduct[A]): GList.Of[A, ev.Repr] = GList.Of(a)
}

Accessing Fields Generically


trait IsGCons[A] {
  type Head
  type Tail <: GList
  def head(a: GList.Of[A, Head #: Tail]): Head
  final def tail(a: GList.Of[A, Head #: Tail]): GList.Of[A, Tail] =
    a.coerce[GList.Of[A, Tail]]
}

object IsGCons {
  type Aux[A, H, T <: GList] = IsGCons[A] { type Head = H ; type Tail = T }
}

Deriving GProduct and IsGCons


@DeriveGProduct case class Foo(a: String, b: Int, c: Float, d: Double)


object Foo {
  implicit val isGCons4: IsGCons.Aux[Foo, String, Int #: Float #: Double #: GNil] =
    IsGCons.instance(_.a)
  implicit val isGCons3: IsGCons.Aux[Foo, Int, Float #: Double #: GNil] =
    IsGCons.instance(_.b)
  implicit val isGCons2: IsGCons.Aux[Foo, Float, Double #: GNil] =
    IsGCons.instance(_.c)
  implicit val isGCons1: IsGCons.Aux[Foo, Double, GNil] =
    IsGCons.instance(_.d)
  implicit def gProduct: GProduct.Aux[Foo, String #: Int #: Float #: Double #: GNil] =
    GProduct.instance
};

Deriving new type class instances


trait CsvEncoder[A] {
  def encode(a: A): String
}

Deriving new type class instances


implicit def gCons[A, H, T <: GList](
  implicit
  hEnc: CsvEncoder[H],
  tEnc: CsvEncoder[GList.Of[A, T]],
  isGCons: IsGCons.Aux[A, H, T]
): CsvEncoder[GList.Of[A, H #: T]] =
  CsvEncoder.instance(a => hEnc.encode(a.head) + ',' + tEnc.encode(a.tail))

implicit def gSingle[A, H](
  implicit
  hEnc: CsvEncoder[H],
  isGCons: IsGCons.Aux[A, H, GNil]
): CsvEncoder[GList.Of[A, H #: GNil]] =
  CsvEncoder.instance(a => hEnc.encode(a.head))

It works!


@DeriveGProduct case class Foo(a: String, b: Int, c: Float, d: Double)
object Foo {
  implicit val csvFoo = CsvEncoder[Foo] = CsvEncoder.derive[Foo]
}

CsvEncoder.encode(Foo("ya", 2, 8.2f, 7.6))
// "ya,2,8.2,7.6"

Thank you!