Add some libraries of plain old design patterns

[Atry]

Recently I reinvented an old approach to encode type class, which, in my honest opinion, obsoletes cats, spire-math and all libraries that use implicit parameter representation of type classes (including my Binding.scala).

The point of this approach is to create facades from abstract factories instead of implicit parameters, where facade and abstract factory are two design patterns described in GoF's book Design Patterns. The factory pattern part of this approach has been widely used in Scala 2's nsc compiler many years ago.

I have created a prototype of this approach at https://github.com/ThoughtWorksInc/DesignPattern.scala . This approach is very straightforward. I expect Typelevel maintainers and contributors may quickly understand the point, if you have a look at the source file of covariant functors.

The advantage of this approach including:

• Libraries created in this approach are available in Java language.
• Almost zero boilerplate code.
• No obscure implicit resolution error message.
• Almost zero cost abstractions. Facades can be AnyVals. As a result, it runs twice faster than Scalaz in this benchmark.
• Fast compilation. The user code compiles twice faster than Scalaz in that benchmark, even if complicated Scalaz types are already hiden in a case class.

I am glad to contribute my work as a prototype, but I'm not intending to submit a project to Typelevel. Instead, I am here to ask existing typelevel projects to evolve into something new, not only for Scala hackers, but also influencing the entire Java world.

Share your thought seeing what we can build in the future, please.

[milessabin]

I think it would help me to understand your proposal if you gave some simple examples of code using the existing Cats type class encoding and showed how that would be translated into your new scheme. I was looking for a simple Functor-based example in your project but couldn't see one ... apologies if I missed it.

[Atry]

For example, if you want to create an asynchronous IO type, a naive implementation is use an EitherT transformed Continuation. In Scalaz, you can define the asynchronous IO like this:

• https://github.com/ThoughtWorksInc/DesignPattern.scala/blob/c8a1c69/benchmark-asyncio-scalaz/src/main/scala/com/thoughtworks/designpattern/benchmark/asyncio/scalaz.scala

and the new approach is:

• https://github.com/ThoughtWorksInc/DesignPattern.scala/blob/master/benchmark-asyncio-designpattern/src/main/scala/com/thoughtworks/designpattern/benchmark/asyncio/designpattern.scala

[Atry]

Note that the concept of type class corresponds to factory pattern in GoF's design pattern, and transformer corresponds to decorator pattern, thus the name FactoryDecorator refers to monad transformer.

[Atry]

The usage of the two versions are ported from @alexandru's Monix benchmark: https://github.com/ThoughtWorksInc/DesignPattern.scala/blob/c8a1c69/benchmark-Main/src/main/scala/com/thoughtworks/designpattern/benchmark/Main.scala

[milessabin]

Those are all somewhat elaborate examples. A lot of the power of type classes comes from their use "in the small" ... so it would help to see a comparison on some simpler examples.

[Atry]

I don't know what does "in the small" exactly mean. Could you describe a scenario, please?

2017-09-05 21:59 GMT+08:00 Miles Sabin notifications@github.com:

Those are all somewhat elaborate examples. A lot of the power of type classes comes from their use "in the small" ... so it would help to see a comparison on some simpler examples.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/typelevel/general/issues/81#issuecomment-327183809, or mute the thread https://github.com/notifications/unsubscribe-auth/AAktuvXD35VoyY_Ipv2OE65iHu0t2_ncks5sfVOlgaJpZM4PMYGV .

-- 杨博 (Yang Bo)

[SystemFw]

Here are some things I'd like to see (hope you don't mind the many questions, your proposal seems ambitious so I'd like to understand it :) )

• How to declare type classes, and type classes hierarchies (this is covered in the covariant snippet I feel)
• How to declare type class instances (The IO example is quite elaborate)
• How to write code that uses a specific data type, and calls a type class method on it
• How to write code that is generic in the type class instance (e.g. F[_]: Monad)
• How to write an instance that depends on other instances (i.e. instance (Foo a) => instance Bar a)
• How to write code with return type polymorphism (e..g 3.pure[IO])

I'm also curious to see if your approach can replace advanced uses of type classes like type level programming a la shapeless

[milessabin]

Just a simple Functor example would help.

[Atry]

@milessabin There are map calls on AsyncIO, which is a Functor: https://github.com/ThoughtWorksInc/DesignPattern.scala/blob/c8a1c69/benchmark-Main/src/main/scala/com/thoughtworks/designpattern/benchmark/Main.scala

[kailuowang]

I completely agree with @SystemFw. Having all these examples in one place would be of great help for the discussion. e.g. I couldn't find an example of "How to write code that is generic in the type class instance (e.g. F[_]: Monad)" in your code base. That's a main concern for implicit based type class encoding.

[SystemFw]

I'm also really curious how you would cover one of the main strengths of type classes, namely type-directed program synthesis, without some form of implicits/proof search/native type class functionality.

[Atry]

How to write code that is generic in the type class instance (e.g. F[_]: Monad)

Don't do that!

In Scala, you can easily access a path-dependent type from values, however, "summon" an implicit instance from type is quite vulnerable.

The point of this proposal is avoiding defining complex "raw" type like EitherT[ContT[Trampoline, Unit, ?], Throwable, ?]. Instead, those types should always settle in factory objects, and the Scala compiler should never see those complex types.

2017-09-05 22:15 GMT+08:00 Kai(luo) Wang notifications@github.com:

I completely agree with @SystemFw https://github.com/systemfw. Having all these examples in one place would be of great help for the discussion. e.g. I couldn't find an example of "How to write code that is generic in the type class instance (e.g. F[_]: Monad)" in your code base. That's a main concern for implicit based type class encoding.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/typelevel/general/issues/81#issuecomment-327188683, or mute the thread https://github.com/notifications/unsubscribe-auth/AAktugA2IhDEebA8Owl59Gl19YLrIi50ks5sfVdjgaJpZM4PMYGV .

-- 杨博 (Yang Bo)

[Atry]

The type information should be stored in singleton objects instead of "raw" type aliases.

2017-09-05 22:21 GMT+08:00 杨博 pop.atry@gmail.com:

How to write code that is generic in the type class instance (e.g. F[_]:

Monad)

Don't do that!

In Scala, you can easily access a path-dependent type from values, however, "summon" an implicit instance from type is quite vulnerable.

The point of this proposal is avoiding defining complex "raw" type like EitherT[ContT[Trampoline, Unit, ?], Throwable, ?]. Instead, in those type should always settle in factory objects, the Scala compiler should never see those complex type.

2017-09-05 22:15 GMT+08:00 Kai(luo) Wang notifications@github.com:

I completely agree with @SystemFw https://github.com/systemfw. Having all these examples in one place would be of great help for the discussion. e.g. I couldn't find an example of "How to write code that is generic in the type class instance (e.g. F[_]: Monad)" in your code base. That's a main concern for implicit based type class encoding.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/typelevel/general/issues/81#issuecomment-327188683, or mute the thread https://github.com/notifications/unsubscribe-auth/AAktugA2IhDEebA8Owl59Gl19YLrIi50ks5sfVdjgaJpZM4PMYGV .

-- 杨博 (Yang Bo)

-- 杨博 (Yang Bo)

[kailuowang]

Not sure if we are talking about the same thing. I am not talking about complex types like EitherT[ContT[Trampoline, Unit, ?], Throwable, ?]. a simple

def myProgram[F: Monad, A](fa: F[A]): XXX

And if you say don't do that, what's the alternative, don't abstract over F?

[Atry]

2017-09-05 22:24 GMT+08:00 Kai(luo) Wang notifications@github.com:

Not sure if we are talking about the same thing. I am not talking about complex types like EitherT[ContT[Trampoline, Unit, ?], Throwable, ?]. a simple

def myProgram[F: Monad, a: A](fa: Monad[A]): ????

Don't do that.

If you are writing some generic code for different types of certain constraint, you should create a mix-in-able trait, like a DeepLearning.scala plugin. So your API is a trait, you can declare type constraint with <:.

If you are writing an "application", which works with a specific type, then you mix-in all the trait you need together to "gathering" all the features you need.

—

You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/typelevel/general/issues/81#issuecomment-327191798, or mute the thread https://github.com/notifications/unsubscribe-auth/AAkturf5pxMTzOuyQdaO065DfOJKA_Iuks5sfVm5gaJpZM4PMYGV .

-- 杨博 (Yang Bo)

[milessabin]

OK, but could you show us how you would rewrite @kailuowang's simple example into your new encoding?

[Atry]

trait MyPlugin extends MonadFactory { type Facade[+A] <: Monad[+A] def myProgram[A](fa: Facade[A]) = ??? }

2017-09-05 22:33 GMT+08:00 Miles Sabin notifications@github.com:

OK, but could you show us how you would rewrite @kailuowang https://github.com/kailuowang's simple example into your new encoding?

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/typelevel/general/issues/81#issuecomment-327194714, or mute the thread https://github.com/notifications/unsubscribe-auth/AAktuh8ApgYtFVnCWjrOIFcU7SQPtoMpks5sfVu7gaJpZM4PMYGV .

-- 杨博 (Yang Bo)

[Atry]

Or more OO style:

trait MyPlugin extends MonadFactory {
  type Facade[+A] <: MyMonad[+A]
  trait MyMonad[+A] extends Monad[+A] {
    def myProgram[A] = ???
  }
}

[tpolecat]

How would you represent something with more than one abstracted type constructor?

def sequence[F[_]: Traverse, G[_]: Applicative, A](fa: F[G[A]]): G[F[A]] = ...

[Atry]

@tpolecat, good question, it's a scenario I haven't covered in my current implementation.

I guess it can be written as something like this:

trait TraverseFactory {
  type Facade[+A] <: Traverse[A]
  trait Traverse[+A] extends Functor[A] {
    def sequence[That[+A] <: ApplicativeFactory#Facade[A]](
      implicit asFa: this.type <:< Facade[That[A]]
    ): That[Facade[A]]
  }
}

[SystemFw]

That's declaration site, but what about call site? Do you need to manually mix in all the Traits carrying the instances? The fact that this is done for you by implicits is a major strength of type classes (type directed program synthesis) :

• Simple example, Json serialisers for list, tuple and option allow you to cover all the combinations of these types
• Complex example, basically all of shapeless

[Atry]

That's declaration site, but what about call site? Do you need to manually mix in all the Traits carrying the instances?

If you are using a built-in type, then the instance was there, UnitContinuation for example.

If you are creating some custom types, then, yes, you may have to choose the features you need manually. There is a syntactic sugar called Factory for it. You may have a look at this tutorial for usage.

At the moment Factory should work with the example implementation. However it is only able to create class Facade as an AnyRef by nested @inject Factory, which will performance a bit worse than manually created AnyVals.

[Atry]

I haven't discovered the combination of this factory approach with dependent-type type class. It may be possible, maybe not, maybe need other helper macros.

[Atry]

2017-09-05 23:25 GMT+08:00 Fabio Labella notifications@github.com:

The fact that this is done for you by implicits is a major strength of type classes (type directed program synthesis) :

It is a strength or weakness varies depending on your programming style. The factory pattern approach replaces complex type definition with mixin instantiation expressions.

I cannot say which style is "a major strength" if they contain equal information.

-- 杨博 (Yang Bo)

[SystemFw]

I'm not sure that answers my question, I'm talking about the following scenario, where I have in scope:

implicit def ints: ToJson[Int] = ???
implicit def bools: ToJson[Bool] = ???
implicit def  tuples[A: ToJson, B: ToJson]: ToJson[(A, B)] = ???
implicit def lists[A: ToJson] : ToJson[List[A]] = ???

And I can serialise, without any extra code, lists of tuples of ints and bools, tuples of lists of ints and lists of bools, tuples of ints and lists of tuples of ints and bools, and so on.

Can one do the same with your approach? And what is the boilerplate cost? (which seems to be raising already with parameterised code)

On 5 Sep 2017 17:33, "杨博 (Yang Bo)" notifications@github.com wrote:

That's declaration site, but what about call site? Do you need to manually mix in all the Traits carrying the instances?

If you are using a built-in type, then the instance was there, UnitContinuation https://github.com/ThoughtWorksInc/DesignPattern.scala/blob/9f1a44c56a6a833cc7eb5c9d5013cf2ba1a44d71/designpattern/src/main/scala/com/thoughtworks/designpattern/continuation.scala#L44 for example.

If you are creating some custom type, then, yes, you may need choose the features you need manually. There is a syntax sugar called Factory https://javadoc.io/page/com.thoughtworks.feature/factory_2.11/latest/com/thoughtworks/feature/Factory.html for it. You may have a look at this tutorial http://deeplearning.thoughtworks.school/plugins for usage.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/typelevel/general/issues/81#issuecomment-327213792, or mute the https://github.com/notifications/unsubscribe-auth/AHaN7kuiK6XhQwMj9bR8l3btUyGbOs3nks5sfWnOgaJpZM4PMYGV threads.

[Atry]

From another point of view, Scala has a path-dependent type system. If you always use values, then it already contains type information inside it. As a result, you may feel you are using a full dependent-type language. However, if you use types as primary construct, Scala may disappoint you due to its vulnerable implicit resolution.

2017-09-05 23:50 GMT+08:00 杨博 pop.atry@gmail.com:

2017-09-05 23:25 GMT+08:00 Fabio Labella notifications@github.com:

The fact that this is done for you by implicits is a major strength of type classes (type directed program synthesis) :

It is a strength or weakness varies depending on your programming style. The factory pattern approach replaces complex type definition with mixin instantiation expressions.

I cannot say which style is "a major strength" if they contain equal information.

-- 杨博 (Yang Bo)

-- 杨博 (Yang Bo)

[Atry]

@SystemFw Auto derivation is definely the case that requires implicit. Unfortunately this feature is not available in Java.

Fortunately this factory approach can also provide those kind of implicit methods.

In DeepLearning.scala, You can mixin plugins to manage implicits like this:

val hyperparameters = Factory[INDArrayWeights with DoubleLiterals with FloatLayers].newInstance()
import hyperparameters.implicits._
// Now you have DeepLearning type class implicit methods for DeepLearning.Aux[INDArrayWeight], DeepLearning.Aux[DoubleLiterals], DeepLearning.Aux[FloatLayers] 

See https://static.javadoc.io/com.thoughtworks.deeplearning/deeplearning_2.11/2.0.1/com/thoughtworks/deeplearning/plugins/Builtins.html and you can see it contains implicits that come from different transitive plugin dependencies.

[Atry]

Have a look at https://static.javadoc.io/com.thoughtworks.deeplearning/deeplearning_2.11/2.0.1/com/thoughtworks/deeplearning/plugins/Builtins$Implicits.html , you may notice those methods are defined in different traits. For example, some of them are from INArrayLayers.ImplicitApi, some of them are from DoubleLayers.ImplicitApi.

[Atry]

That is to say, I still keep dependent-type type classes as implicits inside factories. While other features are turned into normal OO methods without the requirement of implicits.

[Atry]

From result of some random searches for "scala type class":

I don't know, I've never minded the java/scala type class approach, but I have weird opinions about boilerplate!

https://twitter.com/aaronmblevin/status/903118605394604032

[aaronlevin]

oh, hey, that's me quoted! Having given several talks on "typeclass induction" I have to say I'm firmly in the camp of "type directed program synthesis," and it's unclear how this would work in your method.

But, let me say: it's really cool to see people coming up with new solutions to the typeclass encoding problem! What's super exciting about this space is I don't think we've really exhausted all the points in the design space, and your ideas are a great example of an approach many haven't considered!

With the above in mind, I think what's challenging about your idea is that the examples you point towards are quite complex. It would be really helpful to have an example of, like, the definition of Functor, an implementation of Functor for Option.

I also want to echo that the program @tpolecat pasted (def sequence[F[_]: Traverse, G[_]: Applicative, A](fa: F[G[A]]): G[F[A]] = ...) is a pretty test for your design.

I think there are interesting ideas in what you've drafted, so it would be cool to scope down the examples so we can get to the heart of your idea!!

[TomasMikula]

So you rewrote

def myProgram[F: Monad, A](fa: F[A]): XXX

to

trait MyPlugin extends MonadFactory {
  type Facade[+A] <: Monad[+A]
  def myProgram[A](fa: Facade[A]) = ???
}

Now you can only ever call myProgram on a value that implements the Monad interface. So I can't call myProgram on, say, a List[Int], because List is not a subtype of Monad.

Could your approach model that sort of ad-hoc polymorphism, giving behavior (e.g. monad) to a type I don't own (e.g. List)?

[Atry]

@TomasMikula

1. There is an implicit method to create a Facade for that purpose: https://github.com/ThoughtWorksInc/FunctionalPattern/blob/9f1a44c/designpattern/src/main/scala/com/thoughtworks/designpattern/covariant.scala#L18
2. Facades are able to implement other traits, so it is possible to create something like:

   trait SeqTraverseFactory {
   type Facade[+A] <: SeqTraverse[A]
   trait SeqTraverse[+A] extends Traverse[A] with Monad[A] with Seq[A] {
   // Forward Seq calls to underlying Seq
   }
   }

[Atry]

@TomasMikula The situation is like ArrayOps in Scala standard library, where ArrayOps extends SeqLike. Maybe we can create a Monad as well.

[SystemFw]

I'm getting a bit confused. I thought a big part of the rationale for this proposal was to eschew implicits, but I've seen them pop up in three different occasions:

• To wrap in Facade
• To have type class induction
• To have multiple parameters with constraints (the implicit asFa: this.type <:< Facade[That[A] bit)

[Atry]

• To wrap in Facade

It's a lightweight, optional usage. Actually I prefer manually wrap it to Facade in most cases. For example, I manually wrap the function literal to a Facade, instead of let it implicitly converts to Facade.

Facade { continue =>
  ...
}

https://github.com/ThoughtWorksInc/FunctionalPattern/blob/a3cb2ab/benchmark-asyncio-designpattern/src/main/scala/com/thoughtworks/designpattern/benchmark/asyncio/designpattern.scala#L21

[Atry]

• To have type class induction

If you mean type class auto derivation for serialization, I admit this usage is not covered by this factory pattern.

However, the point of auto derivation is not type class. It's code generator which matters. The task requires macros regardless you use or not use implicit parameters. For example, I created some code generators for serialization many years. All of them generate static functions instead of type class:

• https://github.com/Atry/json-stream
• https://code.google.com/archive/p/protoc-gen-as3/
• https://github.com/Atry/protoc-gen-haxe

[Atry]

• To have multiple parameters with constraints (the implicit asFa: this.type <:< Facade[That[A] bit)

The purpose of <:< is to exposing Scala language features to user space type level programming. I admit it is a valid usage of implicit parameters. And I don't know how to avoid those kind of usage. On the contrary I created a lot of implicit parameter style type class in order to access Scala language features.

Among these language feature type classes, the Factory is most useful tool for creating this factory pattern style mix-ins.

The usage of these implicit parameters do bother me because they do not have a Java alternative.

Do you have any idea? @SystemFw

[SystemFw]

If you mean type class auto derivation for serialisation

Serialisation is just the first example I could think of, but type-directed program synthesis, or type class induction, or whatever you want to call it has a lot of different use cases, from typelevel DSLs, to shapeless, to ordinary FP code (e.g. instance (Monoid b) => Monoid (a -> b) and so on. Anyway, I think it's quite important, so I was just trying to understand if your approach had it covered or not :)

[Atry]

Of course this proposal does not cover type induction, because the point of this proposal is avoiding type inductions.

However it does cover some important usages of type induction by replacing them to ordinary method calls.

[TomasMikula]

There is an implicit method to create a Facade for that purpose:

The situation with current encoding is, I can have N lists and a single Monad[List] instance to perform monadic operations on any of those N lists. That is an overhead of 1 object (the monad instance).

With your approach, it seems, you would have to wrap each of the N lists in a facade that implements Monad. This is an overhead of N objects. Do you measure the impact of this? Or can those allocations be optimized away?

[Atry]

@TomasMikula According to the AsyncIO benchmark, these Facades run very fast, more than twice performance of scalaz.

Facades might be AnyVal, though it may be not possible if you let your Facade extend a proxy Seq. Fortunately, I delicately added a BoxFactory so that a type class implementation is able to unbox those Facades manually, no matter Facades are AnyVals or AnyRefs, preventing Facades being referenced by closures.

The programming style of this proposal is very similar with Scala standard library and Scala compiler. I wonder why @odersky did not include a object-oriented style categorical library in Scala standard library.

[Atry]

Hi @kailuowang , note that the BoxFactory trick can be also applied to scalaz or cats, as long as you add an UnboxableK[_[_]] implicit parameter on each monad transformer, where UnboxableK is an isomorphic natural transformation.

[Atry]

At first, I will create a minimal library of categories in next month, especially monad-related type classes in the new encoding.

[DmytroMitin]

@Atry Did I understand correctly that you proposed to write

  trait FunctorFactory {
    type Facade[+A] <: Functor[A]

    trait Functor[+A] {
      def map[B](mapper: A => B): Facade[B]
    }
  }

  object listFunctor extends FunctorFactory {
    case class Facade[+A](list: List[A]) extends Functor[A] {
      override def map[B](mapper: A => B): Facade[B] = Facade[B](list.map(mapper))
    }
  }

  listFunctor.Facade(List(1, 2, 3)).map(_ + 1)

instead of

  trait Functor[F[_]] {
    def map[A, B](mapper: A => B)(fa: F[A]): F[B]
  }

  object Functor {
    implicit object listFunctor extends Functor[List] {
      override def map[A, B](mapper: A => B)(fa: List[A]): List[B] = fa.map(mapper)
    }
  }

  implicitly[Functor[List]].map((_ : Int) + 1)(List(1, 2, 3))

?

Sounds like emulating higher-order generics.

[Atry]

@DmytroMitin Not really. I use higher kinded abstract types here like Facade. This is a more powerful feature than higher kinded type parameter. No need to emulate.

[rossabaker]

Closing stale issue.