The cake’s problem, dotty design and the approach to modularity.

[Alex Ivanov]

Good morning everyone.

I’m very interested in the topic of modularity in Scala. It’s not a secret that today The Cake Pattern is the most popular way to achieve modularity in the project and, to some extent, a nice way to manage dependencies. On the other hand this way of structuring the application becomes more and more an anti-pattern, but unfortunately there’s not much explanation why. I feel that it’s pretty hard to answer why it’s becomes an anti-pattern without some big, active project (like Scala compiler), but in general i can think of things like - complicated design, not that nice way to manage dependencies, problems with binary compatibility, slower compilation due to inheritance overuse and complex cyclic dependencies, any other issues that i didn’t think of? 

I remember that not so long ago Prof. Odersky mentioned he was also disappointed in the pattern and went a bit different way with a Dotty design. But, unfortunately, i couldn’t find details on this decision, what were the problems and how they were solved with a new design (would be good to read a paper like Scalable Component Abstractions). Anyway the project is open-source, so it’s not hard to take a look and see that there are some differences in the design, some components are packed within modules/objects and it uses less cake-style coupling (beside the Context structure). Could someone please unveil the secrets of the dotty architectural design?

And, i guess, that last question that bothers me, what to use instead of the Cake? In the talk “Scala - the simple parts” i liked the idea on the Scala’s Modular Roots where we can see the mapping between Scala and SML languages. Can’t reason much on this, i’ve just started looking at what we can achieve with this SML-style modularity (maybe someone could explain this as well =)? ), but it looks like a better approach to the modular design, especially in combination with typeclasses. Of course we should “use the right tool for problem”, but it feels like the Cake Pattern, is not good as the essential approach to the application architecture and modularity. 

[martin odersky]

I would not classify cake as an anti-pattern per se. Like any scheme
it is good for something but can be over-used. In fact, cake and
inheritance are quite similar in their benefits and problems.
Here are some points I can think of (I'd be interested in other
arguments people might have).

The good:

- Lets you compose multiple components quickly and with minimal fuss
- no parameters, no forwarders, no imports, just mix slices together.

- Allows for mutual dependencies between slices.

- Is therefore very general: Any set of global definitions with
arbitrary dependencies between them can be lifted into a cake.

The bad:

- Because they are so convenient, cakes tend to get big.

- Dependencies are not declared, so are hard to track for big cakes.

- If cakes contain types, these can be accessed from outside the cake
only with path dependent types. Cakes with mutual type dependencies
between them (as they exist in nsc) are particularly hard to model.

In summary, cakes, like inheritance, are a useful tool to achieve
close coupling of components. It's very easy to link components in one
cake, and it is comparably much harder to access them from the
outside, in particular if types are involved. Cakes are misused in a
situation where weak coupling is preferable (and those situations are
in the majority).

My advice would be: Cakes are fine to model mutual dependencies
between traits. However, care must be exercised to keep them
reasonably small. Furthermore, one should think twice whether
embedding types in cakes is the right way to model things. Nowadays,
I'd do that only if the type was essentially private to the
participants of the cake, or if it was clear that every instance needs
its different opaque type. Otherwise one might end up with awkward
situations, where e.g. the type of symbols in the nsc compiler depends
on the cake that's used. Sometimes you want that isolation, but at
other times you want to communicate a symbol between different
compiler instances (i.e., cakes), and then all you can do is copy an
arbitrary complex graph of symbol dependencies (see the "Importers"
framework in scala.reflect). So, putting types in traits can be a
premature restriction of their usage.

The alternative to cakes is essentially functional abstraction. Have
components parameterized by others. Depending where you come from you
might call that "functors" or "constructor dependency injection".
Implicit parameters can help reduce the boilerplate in function
application.

The dotty compiler uses fine-grained functional abstraction
everywhere, using implicit context arguments. That has turned out to
work quite well so far. Contexts are still cakes, in that they mix
together slices that are modelled around different concerns. But they
are much smaller and tend not to contain types, just methods and
fields.

This writeup got much longer than I meant it to be when I started...

- Martin

> --
> You received this message because you are subscribed to the Google Groups
> "scala-language" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to scala-languag...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.



--
Martin Odersky
EPFL

[Oliver Ruebenacker]

     Hello,

  My problem is still (yeah, still) to figure out what exactly is cake pattern. There is no Wikipedia article on it. I could not find any definition ("Cake pattern is ..."). I saw some examples, and I'm never sure which parts of the discussion apply to dependency injection in general, which parts are specific to cake, and which parts are specific to the particular example.

  I know I asked this before. I could spend some time to dig out what the answer was. But even better would be if those who put examples of cake on the web could explain what makes it cake.

     Best, Oliver

Oliver Ruebenacker

Solutions Architect at Altisource Labs

Be always grateful, but never satisfied.

[Haoyi Li]

> Dependencies are not declared, so are hard to track for big cakes.

Only true if you don't use https://github.com/lihaoyi/acyclic! 

I'm sure you're sick of me pitching my library, but banning circular dependencies between files solves exactly this problem. You can not longer take a dependency on Global on every single Slice, because Global needs a dependency on every Slice in order to extend it. Thus you are forced by acyclic to keep each slice only depending on the smaller slices that you truly need, in a controlled fashion, or explicitly spelling out dependencies into abstract members. This solves your problem entirely.

>  - If cakes contain types, these can be accessed from outside the cake only with path dependent types. Cakes with mutual type dependencies between them (as they exist in nsc) are particularly hard to model.

I feel that this is more a problem with path-dependent types rather than with cakes. This is true, but you can often avoid path dependent types in many scenarios by declaring all your "real" types/interfaces outside the cakes, and then the cakes become a lazy way of doing constructor injection (2 lines per file, rather than 1 per class) without any of the weirdness you find in tools.nsc.Global

[Oliver Ruebenacker]

     Hello,

On Tue, May 12, 2015 at 10:31 AM, Haoyi Li <haoy...@gmail.com> wrote:

> Dependencies are not declared, so are hard to track for big cakes.

Only true if you don't use https://github.com/lihaoyi/acyclic! 

I'm sure you're sick of me pitching my library, but banning circular dependencies between files solves exactly this problem. You can not longer take a dependency on Global on every single Slice, because Global needs a dependency on every Slice in order to extend it. Thus you are forced by acyclic to keep each slice only depending on the smaller slices that you truly need, in a controlled fashion, or explicitly spelling out dependencies into abstract members. This solves your problem entirely.

>  - If cakes contain types, these can be accessed from outside the cake only with path dependent types. Cakes with mutual type dependencies between them (as they exist in nsc) are particularly hard to model.

I feel that this is more a problem with path-dependent types rather than with cakes. This is true, but you can often avoid path dependent types in many scenarios by declaring all your "real" types/interfaces outside the cakes, and then the cakes become a lazy way of doing constructor injection (2 lines per file, rather than 1 per class) without any of the weirdness you find in tools.nsc.Global

  The path-dependent types in Global have path-independent traits (e.g. Tree.TreeApi for Global.Tree).

     Best, Oliver 

--

[Eugene Burmako]

Well, TreeApi is still part of the cake, because some parameters / return types of its methods are cake-dependent.

[martin odersky]

On Tue, May 12, 2015 at 4:18 PM, Oliver Ruebenacker <cur...@gmail.com> wrote:
>
> Hello,
>
> My problem is still (yeah, still) to figure out what exactly is cake
> pattern. There is no Wikipedia article on it. I could not find any
> definition ("Cake pattern is ..."). I saw some examples, and I'm never sure
> which parts of the discussion apply to dependency injection in general,
> which parts are specific to cake, and which parts are specific to the
> particular example.
>
> I know I asked this before. I could spend some time to dig out what the
> answer was. But even better would be if those who put examples of cake on
> the web could explain what makes it cake.
>

For me a cake is simply a mixin composition of traits that refer to
members of other traits in the cake using their self types.

Cheers

- Martin

[martin odersky]

On Tue, May 12, 2015 at 4:31 PM, Haoyi Li <haoy...@gmail.com> wrote:
>> Dependencies are not declared, so are hard to track for big cakes.
>
> Only true if you don't use https://github.com/lihaoyi/acyclic!
>
> I'm sure you're sick of me pitching my library, but banning circular
> dependencies between files solves exactly this problem. You can not longer
> take a dependency on Global on every single Slice, because Global needs a
> dependency on every Slice in order to extend it. Thus you are forced by
> acyclic to keep each slice only depending on the smaller slices that you
> truly need, in a controlled fashion, or explicitly spelling out dependencies
> into abstract members. This solves your problem entirely.

But if you ban circular dependencies you don't need a cake - you can
just use normal inheritance. A strong point of cakes is for me is that
they support circular dependencies. Also, even if your dependencies
are non-circular, and even if you just use plain inheritance,
dependencies are still sometimes hard to track because there are no
explicit declarations what they are.

>
>> - If cakes contain types, these can be accessed from outside the cake
>> only with path dependent types. Cakes with mutual type dependencies between
>> them (as they exist in nsc) are particularly hard to model.
>
> I feel that this is more a problem with path-dependent types rather than
> with cakes. This is true, but you can often avoid path dependent types in
> many scenarios by declaring all your "real" types/interfaces outside the
> cakes, and then the cakes become a lazy way of doing constructor injection
> (2 lines per file, rather than 1 per class) without any of the weirdness you
> find in tools.nsc.Global

Absolutely. That's what I advocate, and that's how it is done in
dotty. Put the types outside the cakes.

Cheers

[Jon Pretty]

This adds little over what Martin said, but for me, the general problem with the Cake Pattern is the other side of the same coin that makes it so convenient: that it is very easy to introduce new dependencies.

It's very convenient when constructing a cake that you don't have to define interfaces before you use them, and still have soundness enforced at compile time. But this does nothing to promote well-designed or clean interfaces, and consequently they don't arise naturally. Should you ever have to untangle a cake during a refactoring, you will probably find it unpleasantly difficult.

Oliver: The Cake Pattern is a nebulous concept. (You've probably discovered at least that much...) Have you read this paper? It predates the name "Cake" but describes the pattern's usage in the compiler:

  http://lampwww.epfl.ch/~odersky/papers/ScalableComponent.pdf

In addition to Martin's description, I envisaged the trait "slices" of the cake potentially having inner traits which can themselves be combined in parallel with the mixin of the outer traits. These were intended to be "layers", though they're not really an essential part of the pattern.

Cheers,

Jon

Jon Pretty | @propensive

[Haoyi Li]

> But if you ban circular dependencies you don't need a cake - you can
> just use normal inheritance. A strong point of cakes is for me is that
> they support circular dependencies. Also, even if your dependencies
> are non-circular, and even if you just use plain inheritance,
> dependencies are still sometimes hard to track because there are no
> explicit declarations what they are.

You can ban circular dependencies within files without banning circular dependencies at runtime, by ensuring that the circular dependencies depend on abstract methods! 

e.g. ScalaParse's Literals.scala has a circular dependency on Scala since you need to be able to parse anything in the world to be able to parse a string literal (lol) but it's kept as an abstract def and only filled in when the cake is put together. As you can see, you get the circular dependency we want, together with a well-designed interface and controlled circularity/ugliness, all because Acyclic forced us into this shape. 

If the abstract defs start getting annoying due to repetition over and over at the top of every trait, pull them out into their own trait! Maybe you no longer consider it a trait when the self-type is an totally-abstract interface-trait and not some concrete Global trait, but it's really the same except without the circular dependency hell.

I agree it is very easy to fall into the "everything depends on everything else" trap that scala.tools.nsc.Global is in. Scalac will not complain. Acyclic, on the other hand, will not let you! In fact forces you into the "well designed interfaces" whether you like it or not =D 

[martin odersky]

On Tue, May 12, 2015 at 8:19 PM, Haoyi Li <haoy...@gmail.com> wrote:
>> But if you ban circular dependencies you don't need a cake - you can
>> just use normal inheritance. A strong point of cakes is for me is that
>> they support circular dependencies. Also, even if your dependencies
>> are non-circular, and even if you just use plain inheritance,
>> dependencies are still sometimes hard to track because there are no
>> explicit declarations what they are.
>
> You can ban circular dependencies within files without banning circular
> dependencies at runtime, by ensuring that the circular dependencies depend
> on abstract methods!
>

Sure. But the core part of nsc has circular dependencies between
types: Symbol depends on Type and Type depends on Symbol, and each is
in its own (rather large) trait. That cake supports this is both its
strength (because it is a very general composition mechanism) and its
weakness (because it invites abuse).

Cheers

- Martin

[przemek.pokrywka]

Thanks Martin. "Invites abuse" is the best summary of Cake pattern I have seen so far.

Many traps have been listed here already. I'd like to mention another one. In many examples you will find Cakes, that provide one or more member vals for other Cake layers. Say Database trait has connection val. That seemingly innocent construct actually means, that the entire Cake is now unable to use more than one database, because traits can be mixed-in only once.
This is an example of Robot Legs Problem, to which Cake pattern doesn't offer a solution. For code example please see:

http://stackoverflow.com/questions/5190328/can-the-cake-pattern-be-used-for-non-singleton-style-dependencies/5200297#5200297

Przemek

[przemek.pokrywka]

What to use instead? The approaches presented at:
http://aloiscochard.blogspot.com/2014/12/the-cake-is-lie.html?m=1
http://di-in-scala.github.io

had both worked very well for me so far. Note, that they don't support dependency cycles if you need to have some though.

Przemek

[Justin du coeur]

On Tue, May 12, 2015 at 1:58 PM, Jon Pretty <prope...@gmail.com> wrote:

This adds little over what Martin said, but for me, the general problem with the Cake Pattern is the other side of the same coin that makes it so convenient: that it is very easy to introduce new dependencies.

It's very convenient when constructing a cake that you don't have to define interfaces before you use them, and still have soundness enforced at compile time. But this does nothing to promote well-designed or clean interfaces, and consequently they don't arise naturally. Should you ever have to untangle a cake during a refactoring, you will probably find it unpleasantly difficult.

+1.  As Querki grew from a nice little prototype into a fairly complex application (28k SLOC on the server, 50+ major functional areas, heavily inter-related), I grew more and more dissatisfied with simple-seeming answers like the Cake pattern, which turned out to be easier to write than maintain.

Frankly, I wound up backing off to the same "Ecology Pattern" -- basically a variant of the Resource Locator / Dependency Injection pattern -- that I've been using since the late 90s, in half a dozen different languages.  It's more explicit than some folks might like, but it's rock-solid, easy to use, and promotes good code behavior.  Core concepts are:

-- There is an overall Ecology, which is basically a container of "Ecots" (jargon for "member of the Ecology").

-- Each Ecot is conceptually a self-contained bit of system-singleton logic, in a class.

-- Ecots may expose public traits (EcologyInterfaces) that they extend.  These are typically pure interfaces, but cheating is allowed when convenient.

-- No code is *ever* allowed to refer directly to an Ecot, only to an EcologyInterface.

-- EcologyInterfaces are fetched from the Ecology, and are usually then cached, since they are stable throughout runtime.

-- Ecots may declare initialization-time dependencies on specific EcologyInterfaces.

It may seem slightly primitive, but this model (a) promotes good interface/implementation separation, and thus usually much better separation of concerns; (b) provides for a well-defined, reliable and non-cyclic initialization order without requiring anybody to have godly knowledge of dependencies; (c) allows for mutual dependencies while keeping compile times under control.  It's easy to mock EcologyInterfaces for unit testing, and even to run parallel Ecologies for testing if needed.  (Although that's rarely necessary these days.)

I haven't talked it up much here, because it's a bit old-fashioned, but I've found myself dissatisfied with the alternatives for large-scale process structure.  I'm currently using it in pretty complex environments on both the server/ScalaJVM+Play+Akka and client/ScalaJS sides; it just plain works well.  The core code is here; one of these days, I should probably pull it out into a library...

[Shelby]

Reading this thread (and the linked Scalable Component Abstractions paper) is my first exposure to the "Cake pattern". Gulp. Burp.

I try to search for a generative essence of each issue I study. I am thinking (Dunning-Kruger effect?) the more general premature restriction is requiring types implement interfaces, i.e. the more general notion of an existential type (http://stackoverflow.com/questions/292274/what-is-an-existential-type/30837163#30837163).

For example, afaik a function which requires a type with a specific interface can only be adapted to other types by using the hack "pimp my library" pattern in Scala:

implicit pimp(a: Other) = new Desired ...

def f(a: Desired) ...

And "pimp my library" doesn't play well with containers:

def f(a: List[Desired]) ...

Whereas, the modular design is inversion-of-control where the desired interface dependency is injected orthogonal to the other types the caller may possess:

def f[T](a: List[T], b: Desired[T]) ...

I note that the Dotty Dependent Object Types calculus is orthogonal to mixin inheritance modeling because of the potential for overlapping premature specialization. Also I note that typeclasses are nearly a complete solution to the Expression Problem and I do not recall which of the "issues" (are even really issues?) I had enumerated are due to the typeclass pattern and/or the coinductive type system of Haskell (where _|_ is the Top type, not Bottom as in an inductive language such as Scala):

http://www.coolpage.com/copute/dev/docs/Copute/ref/Complete%20solutions%20to%20the%20%93Expression%20Problem.htm

(luckily I was able to capture the above document from a google cache after stackoverflow deleted it)

A typeclass in Scala appears to me to just be a way of specifying an interface that many types can implement (and types can implement more than one interface without conflating them with their existential type) and then providing an implicit function to automatically inject them into the context where they are used:

https://blog.safaribooksonline.com/2013/05/28/scala-type-classes-demystified/

But as noted in my linked document above, automatic injection for Haskell doesn't play well with containers and perhaps inheritance (although perhaps that is due to other factors such as the coinductive type system).

Thus it appears to me that explicit injection via functional programming is the most modular. Is the reason I find Haskell so confusing is because it is obscuring the boilerplate in invisible implicit typing?

Did we somehow lose the plot along the way with Scala and the concept of merging functional with object oriented programming?

I don't know the answer to that question, but here is one rabbit hole I found:

https://apocalisp.wordpress.com/2010/07/02/higher-rank-polymorphism-in-scala/

My current thinking (subject to change as I learn more) is the Scala roadmap towards Dependent Object Types is appropriate because it simplifies to intersections and unions of types, which appears to me to be an unavoidable consequence of covariant and contravariant container cases. I am not clear how much of the rest of Scala is not more harmful than needed?

If the basic syntax and compiler could be radically simplified (thus hopefully must faster too), perhaps this could make Scala more appealing to a wider audience and use-cases[1]. Conceptually for the separation-of-concerns perhaps the other "features" could be done with macros operating on the AST. Appears by not modeling inheritance in DOT, this may be the conceptional direction being toyed with?

I am trying to wrap my head around what would be the idea language for programming the "web 4.0" which I visualize as unification of app programming and server programming[1]. It should be light weight, because one thing that drives many startups away from Java is the heaviness of the toolset and learning curve as compared to Javascript.

P.S. there may a lot (≈$millions) of money available to throw at this, if someone can elucidate the issues and optimal direction succinctly.

[1] http://www.infoq.com/interviews/bracha-javascript-future

[Shelby]

On further thought, why can't the future compiler expand that boilerplate for us, even the match-cash boilerplate (done at caller site thus VM type erasure is irrelevant) where T is an intersection types that each have an implementation of Desired[_] available in the current scope, so then we only need to write:

def f[T](a: List[T])(implicit b: Desired[T])

Or better yet the sugar where the compiler does the boilerplate internal to the function too:

def f(a: List[Desired])

It seems Haskell has modularity correct with typeclasses instead of inheritance?

[Shelby]

Thinking about how this relates to the problem of loss of specialization (restriction) due to inheritance subsumption:

http://stackoverflow.com/questions/8360413/selectively-disable-subsumption-in-scala-correctly-type-list-contains

Afaics, the generalized, paradigmatic solution to the above linked problem is:

List[+A] {

  def contains[B <: A](x: B)(implicit areEqual: (A, B) => Bool): Bool

}

where inheritance is not used for the types of A and B. For example, a Number can implement a Ordered and an OrderedDivisable typeclass (which can be tested with an implicit input parameter), but it doesn't inherit from those interfaces. Whereas, the type of A is covariant so that we may assign return values of type List[T] which BTW should be intersections of types in the container instead of a subsumption of types in the container (as is now the case in Scala 2.11).

Again it would be ideal if the future compiler would automatically create the apropos areEqual with the requisite match-case boilerplate to extract the types from the intersection and call the extant instances of areEqual for each type in the intersection.

In other words, it appears the intersection and union types of DOT are essential to play correctly with forsaking premature restriction via premature inheritance of types. Inheritance should only come into play where it is unavoidable due to Liskov Substitution Principle and therein the compiler should automatically do the match-case boilerplate for us.

Thoughts please?

On Tuesday, June 16, 2015 at 9:00:25 AM UTC+8, Shelby wrote:

[Shelby]

As an aside, I have taken into consideration Bracha's point that Bool should be considered harmful because it unnecessarily discards information. Thus I would prefer:

def contains[B >: A](x: B)(implicit areEqual: (A, B) => Option[A]): Option[A]

This works because although the return value is contravariant, the use of A in a type parameter is covariant. However my assumption about the caller knowing the actual intersection type of A falls apart due to erasure if A was only received by the caller's function as a type parameter.

I've noticed a fundamental problem with my idea in that I proposed the types in the intersection of type B won't inherit from A (although B can be subtype of A because A can be an intersection), thus B must invariantly be one of those types in the intersection. The problem is that extant areEqual (and I should probably be modeling it as method instead) could relate types not in the intersection, e.g. two types that both implement the Ord interface (one in the intersection of types in A and the other B). Thus that appears to be the weakness of Haskell's inability to inherit is we can't support Liskov Substitution Principle.

Thus apparently the only viable solution to the above problem is to abandon the idea for typeclasses and retain the one Martin proposed:

def contains[B >: A](x: B)(implicit ev: Eq[B]): Option[A]

wherein we must be careful about the semantics of interplay between extant Eq[_] and inheritance.

Also note the correction of the typo below from <: to >:.

[Shelby]

Or better yet, retain my idea and eliminate the covariant requirement on B:

def contains[B](x: B)(implicit areEqual: (A, B) => Option[A]): Option[A]

Then we (not only eliminate the harmful intermediate use of Bool in Martin's solution and also) unconflate the covariance of the contain List and the multiple relationships that can be expressed with typeclasses.

Hmmm. Then the advantage of Scala over Haskell is that we can marry covariance for containers (i.e. object oriented programming) with the freedom to break out of that linear relationship on inheritance for multiple interfaces (relationships) on data.

Am I homing in on the generative essence? Nobody has been able to succinctly and concretely explain to me why I need Scala and not Haskell disregarding the Java compatibility or lazy by default differences.

[Raoul Duke]

> Hmmm. Then the advantage of Scala over Haskell is that we can marry
> covariance for containers (i.e. object oriented programming) with the
> freedom to break out of that linear relationship on inheritance for multiple
> interfaces (relationships) on data.
>
> Am I homing in on the generative essence? Nobody has been able to succinctly
> and concretely explain to me why I need Scala and not Haskell disregarding
> the Java compatibility or lazy by default differences.

I am too clueless to know. But for whatever it is worth I am also
curious, and very much appreciate it when people do try to mull around
the possibilities to see what good can be brought forth.

[Rex Kerr]

On Tue, Jun 16, 2015 at 12:53 AM, Shelby <she...@coolpage.com> wrote:

Am I homing in on the generative essence? Nobody has been able to succinctly and concretely explain to me why I need Scala and not Haskell disregarding the Java compatibility or lazy by default differences.

This is kind of off-topic for the original thread, but:

Inheritance provides a way to automatically assemble chains of mutually-dependent functionality without having to worry about the details.  It's a somewhat fragile solution, but nothing other than extremely late binding via (something computationally equivalent to) vtable lookup really does the trick.

So if you have, for example, a bunch of drawable windowing components with all sorts of elaboration therein, you can still have a xs: List[Component] and get something sensible with xs.sortBy(_.zDepth).foreach(draw).

It's not the only way to solve the problem at all, since any problem you can solve with inheritance you can also solve with composition, but with OO it's really easy to make most everything overridable so you have to go back and modify your library less often.  (Unfortunately, due to a lack of a really robust way to specify logical dependencies, you often need the source code to the library anyway so you know what is safe to override alone, what must be overridden in pairs, etc.).

It also doesn't play terribly nicely with immutability because you lose track of which constructor you ought to use.  The whole _point_ of OO is to lose track so you don't have to worry about it, but then when you need to worry...well...you're stuck.  A classic example is

  List(new A, new A{ override def foo = "different" }).map(x.asCapitalA)

If `asCapitalA` has mutating side-effects, you retain the distinct `foo` behavior.  If, in contrast, it creates a new immutable A, your unique `foo` behavior is lost.

So you might just reject OO as a tool that helps you most in a situation that you avoid anyway.  But that doesn't mean that there are equivalently easy functional or monadic or other ways to do the same thing.  Everything else is harder.

  --Rex

 

[Raoul Duke]

> (Unfortunately, due to a lack of a really
> robust way to specify logical dependencies, you often need the source code
> to the library anyway so you know what is safe to override alone, what must
> be overridden in pairs, etc.).

er, hmmm, isn't that part of the larger indictment of inheritance
(subclassing+subtyping all in one)? Vs. e.g. traits, right? That kind
of inheritance seems to be viewed by most folks I think I respect well
enough, to be something basically evil. Maybe a path that seems paved
with good intentions, but turns into a cesspit all too soon. No?

[Rex Kerr]

Well, the idea that you provide the present capabilities and _nothing more_ is not inherent in the idea of OO, even if pragmatically it is the more straightforward approach.

But there's no particular reason you can't have the compiler help you out by checking that various invariants or dependencies (computed or specified by the programmer) are followed.  You don't _necessarily_ have to manually try to encode that information in types.  But doing such things are research-level hard.

One can still gain most of the benefits of OO while avoiding most of the drawbacks by exercising a certain amount of discipline in design and documentation.

(Also, the idea that traits in Scala don't mix subclassing and subtyping is wrong.  Interfaces in Java, before there were default methods, did not mix.)

  --Rex

[Shelby]

In my previous messages, I expressed an idea for injecting the draw interface(s) to the function for the type(s) in the collection(s) input to the function. I also suggested the compiler could do this automatically, for example the function:

def f(a: List[Drawable]) ...

I proposed that example function could be invoked by a caller possessing any List[T] where T could be an intersection of types which implement the Drawable interface, and the compiler would automatically compile to a function that supports manual injection as follows and automatically implement the boilerplate (both within the function and at the call site) to make it seamless.

def f(a: List[T])(implicit b: Drawable[T]) ...

Note the implementation of Drawable[T] is a object and not a supertype of T, i.e. a typeclass.

Afaics this solves the Expression Problem in that any new interface can be added for any pre-existing type T without touching nor recompiling the source code for T or any existing functions that consume existing interfaces implemented for T.

Any reaction or thoughts on this idea?

The only problem I thought of so far is that due to type erasure when compiled to virtual machines (VMs) that erase types such as Java's, the call site may not know the actually type of T in a collection and thus be unable to construct the match-case boiler plate to apply the correct Drawable[T] object implementation for each type in the intersection of types in T. Type erasure can be worked around with implicit manifests so this isn't a show stopper afaics.

Virtual inheritance appears to me to be an anti-pattern. It breaks semantics quite easily. For example the common example that a square virtually inherits from a rectangle. Then square has the semantics that you can't set the width and height independently, thus the invariants of the semantics of setWidth or setHeight virtual methods is broken.

As I wrote previously, it seems we still need subtyping for parameterized types (what I referred to as a container, e.g. List[T]) because otherwise we can't add new types to the intersection of types in T at runtime (i.e. T would need to be invariant).

Note when I am referring to T of List[T] being an intersection of types, I mean for the new DOT (Dotty) calculus. We all know the existing Scala subsumes the types (usually to Any) that are added to parameterized types such as List[T].

Thus it seems to me DOT (Dotty) is the correct direction to go and we need to decide what else we should throw away from the existing Scala features. I mean I would like to see a base of features for something that is not Scale (i.e. is Dotty) and then you can build the compatibility features for the legacy Scala orthogonal to the base so we can keep the base mean, clean, and awesome.

I may be interested to fund this if we can some clear understanding. I am not expert enough to know if what I am proposing is even correct.

Apologies for being so audacious. I am rushed and just trying to be a high level (generalist) thinker here. You all are down in trenches with this and can better access. i have the capacity to learn and understand if I drill down but not the time to do so because I am spread out on many big projects (currently in the Bitcoin space mostly which is where the potential funding might come from).

[Shelby]

Apologies I realized my myopia. If the call site is receiving a manifest of types at runtime, then it can't know which types to compile into match-case boilerplate at compile time. Thus we still need some sort of vtable.

But why can't we make a vtable for types that is global and thus not tied to each instance of a type, a.k.a. not virtual inheritance nor subclassing?

So we have a manifest which is a lot of types and our compile time boilerplate enumerates the list. Each type has a globally UID for indexing a global vtable. Each interface has a globally UID which we can search for in our copy of the global vtable. The vtable should always be injected into each function, so that legacy code doesn't need to be recompiled.

I have not thought out how the above would interopt with types that are complex combinations of intersections and unions. I haven't even thought through the scenarios where unions will arise.

Apologies I am not writing out code examples for all my statements. If anything I've written is not clear, please ask me to clarify.

[Shelby]

If we think about the gains that have been made lately in terms of reactive programming and modularity, it is about inverting the control so that the inner immutable doesn't have to morph to control the outer composition.

It appears conceptually this is what is being done by moving the vtable out of the instance of a type (aka virtual inheritance) and into an outer composition vtable list of implemented interfaces on known types.

I think this point is precisely on point with the opening post of this thread, because we are relating how the removal of inheritance modeling and the insertion of conjunction and disjunction modeling in the new DOT (Dotty) calculus, is intimately related with forsaking the Cake pattern and its inherent limits on extensibility of composition.

[Rex Kerr]

On Wed, Jun 17, 2015 at 7:58 PM, Shelby <she...@coolpage.com> wrote:

Apologies I realized my myopia. If the call site is receiving a manifest of types at runtime, then it can't know which types to compile into match-case boilerplate at compile time. Thus we still need some sort of vtable.

Yes, I was about to comment that you were just reinventing a vtable.

 

But why can't we make a vtable for types that is global and thus not tied to each instance of a type, a.k.a. not virtual inheritance nor subclassing?

That's approximately how it works already (unless you allow monkeypatching).  The vtable for each type is global, and the instance only contains a pointer to the vtable which doubles as the way to perform run-time type identification.  (Or, at least, this is one way to implement it.)

If you're suggesting to rip the vtable pointers out of the objects so you need to mirror your data and dispatching data structures for every operation--well, yes, you could do that.  But the key of OO is that you don't need to; the information you need is carried along locally.  This is vastly more convenient, so you need to have a good reason for separating the two.

And there may be such a reason: if you don't lose track of your types at compile-time, you don't need to carry along a pointer to the vtable at runtime.  (This is true in C++, incidentally--only virtual methods are in the vtable.)

Regarding squares and rectangles--doing it the way you stated violates LSP.  That there are oodles of OO tutorials that violate LSP with their very first example is depressing, though, and in a way is one of the most damning indictments of OO.  (Or maybe it's just a case of poor naming: real objects gain and lose properties willy-nilly, and our names for the various groupings violate LSP like crazy. 

  --Rex

 

[Shelby]

And the reason to do that is because then you can add new interfaces to the vtable at the call site, where the available interfaces on a type are scoped, i.e. invert the control but with local control over composition collisions.

Whereas, hardcoding the vtable with the instance of the data type means you can't invert the control and compose preexisting code with new functionality.

And afaics, the conjunctions and disjunctions of Dotty (DOT calculus) are essential to tracking types precisely, because as I wrote previously for example there is no way to add hetereogeneous types T to for example a List[T] at runtime (unless you subsume to Any as Scala does now thus losing the types).

I want to experiment with such a solution to the Expression Problem. Does anyone think the idea has promise and worth funding as an experiment alongside Dotty (hopefully orthogonal experiments can be accomodated in Dotty's design)?

Thanks for the feedback. I am hoping for some real big win on language. Does Haskell already offer this paradigm with all the boilerplate taken care of by the compiler?

[Shelby]

Coming back to this ... and sorry no time to construct a blog too rushed ...

To summarize ideas against premature specialization (not claiming these are original ideas):

1. Don't use subclassing, i.e. don't implement any method in a supertype (e.g. `trait`) that isn't `final`, thus all methods are final (closed) in their existential type[1].

2. Subtyping should only be injected locally at the call site with inversion-of-control (c.f. my ideas upthread for potential new forms of compiler assistance), or globally due to the Liskov Substitution Principle resulting from type constructors of kind >= 0 (a.k.a. type parametrization) and first-class functions (a.k.a. functional programming, i.e. functions can evaluate and return functions).

3. Functional programming is differentiated from imperative programming in that the semantics are expressed more unified (atomically, i.e. higher-level) — of which premature specialization employing discarded semantics[2] (which includes unrolling function recursion replaced with loops and mutable variables), mutable variables[3], or referential opaqueness are egregious cases. Category theory can raise this up another level.

Several resources[1][4] seems to confirm the criticism that Scala while being high-level, introduces more complexity than Haskell.

Most of the aforementioned premature specializations Haskell makes difficult to introduce (which the Scala programmer could choose to avoid but isn't discouraged from doing so), except apparently Haskell can't do the implicit global subtyping due to LSP (in #2)—such as adding elements of different types to a list—because refinement types are impossible due to bottom populating all types, i.e. Haskell can't do the new injunction and disjunction types of the DOT calculus (Dotty)![5] Other than highly discouraging premature specializations and the universal type inference due to the lack of availability of subtyping—being by default pure, lazy, total, memoized—Haskell can elegantly express coinductive or infinite constructs (e.g. `fib 0 = 0; fib 1 = 1; fib n = fib (n-1) + fib (n-2)`) which can also be expressed more verbosely with obscured semantics (i.e. more imperatively) in the by default impure, eager, strict, non-memoized Scala[6]. Also laziness provides a performance advantage for functional composition[7]. Laziness introduces timing indeterminism at runtime. Totality makes non-termination (Haskell's `undefined` value synonymous to Scala's `Nothing` type) a value (not a type) and its type bottom _|_ is at top of the hierarchy of inductive types[8], thus an exception when using a value can occur at runtime far removed from the source of the non-termination (another form of indeterminism). It also has deeper negative implications that I don't completely grasp[9]. Haskell's pure, lazy, totality can be selectively disabled but more verbosely with obscured semantics. So comparing the two, what one taketh then other giveth and vice versa. Except apparently the lack of subtyping (refinement types) in Haskell is a major weakness (even after we remove subclassing, which is an anti-pattern) which means DOT (Dotty) could potentially take a big leap ahead? Is this paucity the price paid for Haskell's revered brevity?

[1] https://existentialtype.wordpress.com/2011/03/16/what-is-a-functional-language/

"5. It should have a rich type structure that permits introduction of new abstract types and which supports modular program development.  By giving short shrift to expressions and evaluation, imperative language have an impoverished notion of type—and not support for modularity.  Worse, object-oriented programming, a species of imperative programming, is fundamentally antimodular because of the absurd emphasis on inheritance and the reliance on class-based organizations in which functionality metastasizes throughout a program."

http://tonymorris.github.io/blog/posts/what-kind-of-things-are-easy-in-haskell-and-hard-in-scala-and-vice-versa/index.html

"Scala also has the ability to namespace a function by giving special status to one of its arguments (some people call this OO, then don’t, in the very next breath – I never get it). What I mean is, you may have two functions with the same name, which are disambiguated at the call site by the type of the argument to the left of the dot. I am deliberately not calling this by any special name, but rather focussing on its utility – Haskell can do this with qualified imports – not quite so nice. I am usually, though not always, particularly unimaginative when it comes to inventing function names – allowing me to reuse one without a penalty is very handy indeed. Note here I do not mean overloading – I think the Scala community has worked out that overloading is just not worth it – do not do it, ever."

[2] https://existentialtype.wordpress.com/2011/03/15/boolean-blindness/

"I must associate a provenance with that bit in order to give it meaning.  “This bit being true means that e and e’ are equal, whereas this other bit being false means that some other two expressions are not equal.”  Keeping track of this information (or attempting to recover it using any number of program analysis techniques) is notoriously difficult.  The only thing you can do with a bit is to branch on it, and pretty soon you’re lost in a thicket of if-the-else’s, and you lose track of what’s what.  Evolve the program a little, and you’re soon out to sea, and find yourself in need of sat solvers to figure out what the hell is going on."

"It’s just that Boolean thinking has infected the software world to such an extent that I feel that I have to fight back. Just the idea of comparison to “null” to obtain a Boolean is absurd, even if you think you need a “null” pointer (which you don’t, in a properly designed language)."

[3] https://existentialtype.wordpress.com/2011/03/16/what-is-a-functional-language/

"2. It should support both computation by evaluation and computation by execution.  Evaluation is a smooth generalization of high school- and university-level mathematics, and is defined in terms of standard mathematical concepts such as tuples, functions, numbers, and so forth.  Variables are given meaning by substitution, and evaluation consists of simplifying expressions.  Execution is the action of a program on another agent or data structure conceived of as existing independently of the program itself.  The data lives “over there” and the program “over here” diddles that data.  Assignables (my word for what in imperative languges are wrongly called variables) are given meaning by get and put operations (fetch and store), not by substitution.  Execution consists of performing these operations."

[4] http://hammerprinciple.com/therighttool

http://joshbassett.info/2013/hello-haskell-goodbye-scala/

http://blog.samibadawi.com/2013/02/scala-vs-haskell-vs-python.html

http://jnordenberg.blogspot.com/2012/05/my-take-on-haskell-vs-scala.html

http://blog.srinivasan.biz/software/if-you-have-to-learn-just-one-programming-language

http://tonymorris.github.io/blog/posts/what-kind-of-things-are-easy-in-haskell-and-hard-in-scala-and-vice-versa/index.html

"These tools exist and are as useful as they are, because of certain fundamental properties of Haskell itself. Here I mean, the hoogle function is only as useful as it is because Haskell tags IO effects in the type delineating values with types IO t and t, so hoogling for say, [a] -> Int eliminates a lot of candidate functions that would have this type in other environments. In Scala, without the delineation between an Int that has been computed with its arguments, and an Int that has been computed with the entire universe, a hoogle-equivalent would not be as useful"

[5] https://www.reddit.com/r/haskell/comments/3aqj67/in_what_ways_does_haskell_support_intersection/

[6] arr(0) = 0; arr(1) = 1; def fib(n: Int): Int = if (n <= 1) n else if (n - 1 >= arr.length) fib(n - 1); arr(n) = arr(n - 1) + arr(n - 2) } // complication of array upsizing not shown

[7] http://augustss.blogspot.com/2011/05/more-points-for-lazy-evaluation-in.html

[8] https://existentialtype.wordpress.com/2011/04/24/the-real-point-of-laziness/#comment-770

[9] https://wiki.haskell.org/Hask#Hask_is_not_Cartesian_closed

[Dmitriy Parenskiy]

Hi, all

Take another cup cake pattern.

Links to it: 

http://stackoverflow.com/a/26022355/5266

and

https://github.com/dickwall/activator-akka-scala-parfait

вторник, 12 мая 2015 г., 17:13:34 UTC+10 пользователь Alex Ivanov написал:

[Shelby]

I didn't have time to study your idea, but it is on my todo list to think about how category theory might help achieve the local ("call site") injection of dependencies that I referred to, instead of some compiler assisted specialization. Conceptually I am assuming any compiler macros that could be invented would be more fragile than some category theory approach. I am also hoping that might help me unifying more my comparison to Haskell. I really want to get to the bottom of this (pun intended).