Solution to the Expression Problem

[shelby3]

There is a summary in the 'Commentary' for typeclass, and the link to the full description.

P.S. I found the early genesis for the idea for my solution to the Expression Problem. And the key link is the one from 2011 (which is dead, but this is the archive.org for it) when I was explaining to the creator of Kotlin that Extension Methods were insufficient and I started to explain my idea for a complete solution (but it wasn't fully fleshed out because I wasn't aware at that time that I was building on typeclasses).

^{What is really sad for me is on that day (May 1, 2012) that I invented and finally wrote down my solution to the Expression Problem, after writing that and uploading it, I laid down to sleep and within 1 hour I was in an ambulance rushed to ER for an acute peptic ulcer that had ruptured and was leaking acid into my abdomen. 4 years of hell since then... (note I was off and on sick before that, but not obliterated)}

I will now go find my emails from 2011 with andrey.breslav@xxxbrains.com and copy them into this thread, so there is a permanent public record.

The emails I think should make it clear I was thinking about conceptually how to change the implementation at the use-site function call.

^{Archive.org was returning the archived page, then it was redirecting after that. So I had to use web-sniffer.net to capture the page and then I uploaded it to my host.}

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Extension discussion: suggesting vtable and mixins From: "Shelby Moore" shelby@xxxxpage.com Date: Tue, September 27, 2011 4:37 am To: "Andrey Breslav of Kotlin" andrey.breslav@xxxbrains.com .--------------------------------------------------------------------------

Hi Andrey,

This is Shelby Moore III from the discussion at the following link:

http://confluence.jetbrains.net/display/Kotlin/Extension+functions?focusedCommentId=41488305&#comment-41488305

When you read the following which is an internal note for my Copute language design, an 'interface' and 'mixin' are essentially are each a Scala trait but they can only have unimplemented and implemented methods respectively. They can never have val or var. (tangentially in Copute, only a class can have constructor parameters, and they always val, i.e. immutable, which may be relevant below).

The idea is that mixin methods are functions that input this as first parameter. And mixins are orthogonal to everything except any interface they inherit from. So this solves your issue, and generalizes it to full compositionality, as well it eliminates the importing issue.

39) Compositionality fundamentally requires the ability to add methods to an existing interface. One way is via import of static functions (e.g. singleton object methods), that take an existing interface as the first input parameter:

http://confluence.jetbrains.net/display/Kotlin/Extension+functions?focusedCommentId=41488170&#comment-41488170

But that doesn't provide to the caller the inversion-of-control, i.e. the 'D' for dependency injection of SOLID.

The solution is for each function to specify the interface it requires of each input. But the problem is that the caller may have an object, or a higher-kinded object with a type parameter, whose type does not have the interface required by a function's parameter. There are two orthogonal issues.

1. How to most efficiently convert an object to an extended interface.
2. How to most efficiently apply an extended interface to an existing object, without converting it to the extended interface (i.e. "view bound").

The solution lies in the vtable and the mixin. Each object has a pointer to a vtable which is an array of pointers to the functions which implement the methods of the object's interface. A mixin (in Copute) adds no constructor parameters, thus only adds methods which rely on the interfaces inherited by the mixin.

Thus to convert an object to an extended interface, specify which mixin(s) to combine with the object (assuming all inherited interfaces are implemented in the object being converted and/or by the specified mixins) which fully implement the extended interface. Then the object need only be copied and its vtable pointer changed to the one for this set of mixins. Realize the vtable is orthogonal to the constructor parameters of a class. The object data structure may even be optimized for classes with many constructor parameters with double-indirection to its constructor parameters, so only the pointer has to be copied.

To view an object as having an extended interface, there is no need to copy the object, just at compile-time use the alternative vtable.

I have no idea if this can be done efficiently on the current version of the JVM. It can be less efficiently simulated by instantiating a dummy class, that has the non-extended interface as a constructor parameter, with each method calling each inherited method on this constructor parameter.

So the syntax should be as follows (not supported by Scala), where Extended and NonExtended are interfaces and Extensions are mixin(s):

val x : Extended = non_extended : NonExtended, Extensions,... // In Scala ',' is 'with'

The caller can convert before sending the input, which means the function being called requests the input type Extended. But this costs conversion when the extended interface is not always accessed within the function that inputs it, or the extended interface is required on a type parameter of the input type. See "view bound" on page 483 of Programming in Scala. In this case, or in the case that the conversion is also needed within the called function, there should be a syntax for passing the conversion to the function as an additional parameter. The compiler can convert this ideally to a vtable parameter, or simulate by passing a conversion function. I suggest the syntax, NonExtended : Extended is the type signature for a conversion parameter, and (_ , Extensions, ...) is the value.

We should over time make our compiler smart enough to automatically recognize where an alternative version of a function could be offered, where it will input such a conversion, replacing an upper bound on a type parameter of an input, or instead of inputting a more narrow (sub-) type.

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: Extension discussion: suggesting vtable and mixins From: "Andrey Breslav" andrey.breslav@xxxbrains.com Date: Tue, September 27, 2011 7:55 am To: shelby@xxxxpage.com .--------------------------------------------------------------------------

Hi Shelby,

Thus to convert an object to an extended interface, specify which mixin(s) to combine with the object (assuming all inherited interfaces are implemented in the object being converted and/or by the specified mixins) which fully implement the extended interface. Then the object need only be copied and its vtable pointer changed to the one for this set of mixins.

I have some questions here: What happens to object's identity (if you have it in Copute)? What if the initial object partially implemented the interface? Do you choose which methods to take from mixin dynamically? How slowly does this work?

To view an object as having an extended interface, there is no need to copy the object, just at compile-time use the alternative vtable.

I am aware of no way of using a vtable at compile time.

I have no idea if this can be done efficiently on the current version of the JVM. It can be less efficiently simulated by instantiating a dummy class, that has the non-extended interface as a constructor parameter, with each method calling each inherited method on this constructor parameter.

The same problems here: identity will be lost, and it is unclear what to do with those methods of the target interface that were present in the original object. Plus it will emit very many classes.

We should over time make our compiler smart enough to automatically recognize where an alternative version of a function could be offered, where it will input such a conversion, replacing an upper bound on a type parameter of an input, or instead of inputting a more narrow (sub-) type.

This algorithm should be pretty clever. I would be interested in how you can do that efficiently.

Thanks for your time.

Andrey Breslav JetBrains, Inc. http://www.jetbrains.com "Develop with pleasure!"

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: Extension discussion: suggesting vtable and mixins From: "Shelby Moore" shelby@xxxxpage.com Date: Tue, September 27, 2011 1:55 pm To: "Andrey Breslav" andrey.breslav@xxxbrains.com .--------------------------------------------------------------------------

Hi Shelby,

Thus to convert an object to an extended interface, specify which mixin(s) to combine with the object (assuming all inherited interfaces are implemented in the object being converted and/or by the specified mixins) which fully implement the extended interface. Then the object need only be copied and its vtable pointer changed to the one for this set of mixins. I have some questions here: What happens to object's identity (if you have it in Copute)?

The original object does not change.

The idea is to copy the object and change the vtable in the copy to the one with the extended interface, that includes the specified mixins.

I understand that conceptually, an object is a structure of data fields and vtable pointer. The vtable contains pointers to each method implementation.

Conceptually, an object could be two pointers, one to its data, and another to its vtable. In such a virtual machine, we can simply copy the data pointer, and set the new vtable pointer. Very efficient.

And this is only for conversions. I also wrote below about compile-time use of the alternate vtable pointer without copying the object.

I briefly looked at the JVM spec and I don't think it supports this direct manipulation of the vtable. But I provided an less efficient substitute that could be used until VMs catch up. If I am correct that this is the correct way to do extension, then VMs will catch up.

What if the initial object partially implemented the interface? Do you choose which methods to take from mixin dynamically? How slowly does this work?

The programmer is specifying this, just as they do when they declare a class and inherit from an existing class and do multiple inheritance of mixins. Each language decides its policy on such collisions.

This is all resolved at compile-time, so it isn't slowed at all afaics.

In the following, the vtable for "Extended = NonExtended, Extensions,..." is decided at compile-time.

val x : Extended = non_extended : NonExtended, Extensions,...

It is analogous to declaring a mixin, where NonExtended is now a mixin (i.e. has implementation) and not an interface as it was above:

mixin Extended inherits NonExtended, Extensions,... { }

To view an object as having an extended interface, there is no need to copy the object, just at compile-time use the alternative vtable. I am aware of no way of using a vtable at compile time.

When we define a class at compile-time, we are setting the vtable for all instances of that class.

Apparently JVM does not give us the control to say "view this object's data as this vtable". But that doesn't mean it can't be done a VM. So with the current JVM we won't get compile-time optimization.

But I am not interested in the past, I am interested in the future, and what is the correct way to get Web3.0 (Reeds Law) scale compositionality.

I think going down the road of past spaghetti (i.e. not generalized to inversion-of-control) methods of extension, is failure directed and will have a short half-life.

I have no idea if this can be done efficiently on the current version of the JVM. It can be less efficiently simulated by instantiating a dummy class, that has the non-extended interface as a constructor parameter, with each method calling each inherited method on this constructor parameter. The same problems here: identity will be lost,

I am not clear what you mean. Do you mean the original object will be modified? I am saying we copy the object (as efficiently as possible). And for the view bound, we don't even copy the object. Of course we need a VM that cooperates, but we can simulate less efficiently on JVM in the meantimes.

and it is unclear what to do with those methods of the target interface that were present in the original object.

This depends on the language's specification. There is no problem here that isn't also in multiple inheritance of mixins.

Plus it will emit very many classes.

That is a good thing. Absolutely necessary for wide-scale compositionality.

But this can be anonymous classes (at least at the layer of our language, if our VM does not comprehend):

val x = non_extended : NonExtended, Extensions,...

We should over time make our compiler smart enough to automatically recognize where an alternative version of a function could be offered, where it will input such a conversion, replacing an upper bound on a type parameter of an input, or instead of inputting a more narrow (sub-) type.

This algorithm should be pretty clever. I would be interested in how you can do that efficiently.

This isn't central to the idea. Just a note I added to myself for an area of future investigation. For upper bounds, it seems probably to be straightforward.

The more key thing I want to present is that only this mixin + vtable solution is going to fully generalize compositionality in the most efficient runtime and also be explicit. Scala's implicit functions and view bounds suffer both from being not explicit, and ALWAYS requiring runtime conversions (slow) and these conversions are not optimized at the vtable level of abstraction. Scala is offering a generalized conversion function, whereas I am suggesting subtyped extension, thus more narrowly focused to the extension issue (and thus vtable optimizable, which Scala's implicits never can be).

Thanks for your time.

Ditto. Interested to hear any feedback, if you have.

Andrey Breslav JetBrains, Inc. http://www.jetbrains.com "Develop with pleasure!"

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: Extension discussion: suggesting vtable and mixins From: "Andrey Breslav" andrey.breslav@xxxbrains.com Date: Tue, September 27, 2011 2:38 pm To: shelby@xxxxpage.com .--------------------------------------------------------------------------

Hi Shelby,

But I am not interested in the past, I am interested in the future, and what is the correct way to get Web3.0 (Reeds Law) scale compositionality.

I think going down the road of past spaghetti (i.e. not generalized to inversion-of-control) methods of extension, is failure directed and will have a short half-life.

Your idea about switching vtables at runtime is nice, indeed. It lies very close to metaclasses (as in Smalltalk). Did you have a look at CLOS and its Meta-object protocols? You might enjoy it a lot. Unfortunately, it is hard to implement anything like that efficiently on the JVM. LLVM could work, though.

Another problem would be: how do the method implementations available in mixins know what data is available in the object they are attached to and how it is laid out in memory. I mean, a single mixin may be extending many objects with different sets of fields, and how to access those fields is unclear from the perspective of the mixin code. I guess, you need some static declarations of fields (or like) on the mixin side, as well as something to resolve memory layout problems on the runtime side.

I have no idea if this can be done efficiently on the current version of the JVM. It can be less efficiently simulated by instantiating a dummy class, that has the non-extended interface as a constructor parameter, with each method calling each inherited method on this constructor parameter. The same problems here: identity will be lost, I am not clear what you mean. Do you mean the original object will be modified?

I might not have got you right. I thought you are proposing implicit conversion to what is required at a call site. In this case the user if left with an impression of using the same object, but s/he actually isn't, because the function will receive an extension instead. If what you mean is explicit conversion, then this is sort of done conventionally by an Adapter or Decorator patterns. These patterns which suffer from some limitations, which your approach wouldn't have, but speaking of scalability, it's not a huge difference.

and it is unclear what to do with those methods of the target interface that were present in the original object. This depends on the language's specification. There is no problem here that isn't also in multiple inheritance of mixins.

Well, on the JVM multiple inheritance of mixins is a difficult enough business and it introduces significant overhead, unless you do exactly as much as the aforementioned Adapter and Decorator patterns.

Plus it will emit very many classes. That is a good thing. Absolutely necessary for wide-scale compositionality.

Kills performance. No kidding, too many classes on the JVM is a real risk of running out of memory (special kind of it, called PermGenSpace).

The more key thing I want to present is that only this mixin + vtable solution is going to fully generalize compositionality in the most efficient runtime and also be explicit. Scala's implicit functions and view bounds suffer both from being not explicit, and ALWAYS requiring runtime conversions (slow) and these conversions are not optimized at the vtable level of abstraction. Scala is offering a generalized conversion function, whereas I am suggesting subtyped extension, thus more narrowly focused to the extension issue (and thus vtable optimizable, which Scala's implicits never can be).

You are right about Scala's implicits, but what I wonder about is what exactly do you mean by "compositionality". They usually use the term in the context of semantics and various calculi, none of which appears in this discussion.

Andrey Breslav http://jetbrains.com Develop with pleasure!

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: Extension discussion: suggesting vtable and mixins From: "Shelby Moore" shelby@xxxxpage.com Date: Tue, September 27, 2011 11:16 pm To: "Andrey Breslav" andrey.breslav@xxxbrains.com .--------------------------------------------------------------------------

Hi Shelby,

But I am not interested in the past, I am interested in the future, and what is the correct way to get Web3.0 (Reeds Law) scale compositionality.

I think going down the road of past spaghetti (i.e. not generalized to inversion-of-control) methods of extension, is failure directed and will have a short half-life. Your idea about switching vtables at runtime is nice, indeed. It lies very close to metaclasses (as in Smalltalk). Did you have a look at CLOS and its Meta-object protocols? You might enjoy it a lot. Unfortunately, it is hard to implement anything like that efficiently on the JVM. LLVM could work, though.

Thanks very much for that VM insight.

On JVM, to transparently (i.e. low level detail not seen in language syntax) simulate the conversion part of my extension idea, will apparently have the cost of instantiating another class and stub methods. Which is essentially what Scala's implicits can do for this case. At least mine can be optimized on other VMs.

I got the idea by comparing what you want to do and what Scala's implicits do, and interpolating between the two concepts.

Another problem would be: how do the method implementations available in mixins know what data is available in the object they are attached to and how it is laid out in memory. I mean, a single mixin may be extending many objects with different sets of fields, and how to access those fields is unclear from the perspective of the mixin code. I guess, you need some static declarations of fields (or like) on the mixin side, as well as something to resolve memory layout problems on the runtime side.

In Copute, there are no fields. Only classes may have constructor parameters, and no other fields. And these constructor parameters are only accessible via an interface (with method names the same as the constructor parameter names).

So I was only talking about extending an interface (because in Copute only interfaces can ever be referenced). So in my idea, we are only dealing with collections of methods. The mixin accesses the methods it inherits from.

It was one of the key insights I had to separate implementation from interface.

Perhaps it helps that Copute is an immutable language, meaning the constructor parameters are never mutated, so there is no need for a setter. I need to think more about whether this is required.

I need to think more about the optimum low-level VM layout of the class structure. I think optimally the object structure needs to be an array of vtable pointers. Thus to convert and extend the object, must copy this array. Thus extension conversion (as opposed to viewing an object with an extended interface) gets more costly, the more granular the interfaces. Any way, your webpage was dealing with viewing an object with an extended interface, which can be resolved at compile-time (more on that below).

I have no idea if this can be done efficiently on the current version of the JVM. It can be less efficiently simulated by instantiating a dummy class, that has the non-extended interface as a constructor parameter, with each method calling each inherited method on this constructor parameter. The same problems here: identity will be lost, I am not clear what you mean. Do you mean the original object will be modified? I might not have got you right. I thought you are proposing implicit conversion to what is required at a call site. In this case the user if left with an impression of using the same object, but s/he actually isn't, because the function will receive an extension instead. If what you mean is explicit conversion, then this is sort of done conventionally by an Adapter or Decorator patterns. These patterns which suffer from some limitations, which your approach wouldn't have, but speaking of scalability, it's not a huge difference.

The fundamental concept is that the caller is providing the pointer to set of methods that apply to the object also being passed as input to a function which expects those set of methods. So it is the idea from your web page, except instead of linked at compile-time, the table of methods is accessed via a pointer. So the overhead of my idea are additional pointer indirections. But that is the cost of compositionality, because if we don't give callers the ability to inject the implementations of the methods, then then code ends up refactored (i.e. spaghetti) instead of composable.

It should be feasible with a sufficiently tuned VM to replace the double-indirections contained in a loop with static calls to the method.

We may think when writing a function that for example "swap" should only have one meaning ever. But it may turn out that providing for it to be injected into the function, allows some clever composition in the future, to avoid refactoring.

Afaics, the Adapter pattern is essentially what implicits do in this case, and how to simulate my construct on JVM. The Decorator pattern is high-level simulation of the vtable indirections. Agreed, I think this can be much optimized at the low-level. In terms of compositional (avoid refactoring) scalability, agreed these are similar concepts. As I stated below, afaics the Scala's solution is too high-level and not focused on the vtable transformation, thus may not be generally optimizable at the low-level.

and it is unclear what to do with those methods of the target interface that were present in the original object. This depends on the language's specification. There is no problem here that isn't also in multiple inheritance of mixins. Well, on the JVM multiple inheritance of mixins is a difficult enough business and it introduces significant overhead, unless you do exactly as much as the aforementioned Adapter and Decorator patterns.

I haven't studied this. I haven't studied how Scala performs in this regard.

If so, this will need to improve, if I am correct that mixin scalability is critically required.

Plus it will emit very many classes. That is a good thing. Absolutely necessary for wide-scale compositionality. Kills performance. No kidding, too many classes on the JVM is a real risk of running out of memory (special kind of it, called PermGenSpace).

I don't know what is the technical reason for a tradeoff on performance here. These vtables should be referenced by pointer. Perhaps these are swapped into virtual memory. It would seem that these should be tracked by time between accesses, and keep in such generational groupings for virtual memory page swapping.

On the surface this sounds like a low-level optimization issue.

I read that the PermGenSpace can be resized at runtime.

You definitely raise the issue of why the constructor parameters (data) need to be orthogonal to the vtables. I will need to spend more time thinking about the low-level class structure.

I want to assume my idea won't be any worse performing than Scala's implicits and/or view bounds. And it offers the hope of lower-level optimizations. That is handwaving, I should endeavor to understand the low-level issues fully.

The more key thing I want to present is that only this mixin + vtable solution is going to fully generalize compositionality in the most efficient runtime and also be explicit. Scala's implicit functions and view bounds suffer both from being not explicit, and ALWAYS requiring runtime conversions (slow) and these conversions are not optimized at the vtable level of abstraction. Scala is offering a generalized conversion function, whereas I am suggesting subtyped extension, thus more narrowly focused to the extension issue (and thus vtable optimizable, which Scala's implicits never can be). You are right about Scala's implicits, but what I wonder about is what exactly do you mean by "compositionality". They usually use the term in the context of semantics and various calculi, none of which appears in this discussion.

I've seen the term used when discussing operational semantics. Here I am searching for the term which means that the degrees-of-freedom expressed by the high-level denotational semantics is maximized, i.e. refactoring is minimized.

Apologies my reply is less concrete than I want.

Andrey Breslav http://jetbrains.com Develop with pleasure!

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: Extension discussion: suggesting vtable and mixins From: "Andrey Breslav" andrey.breslav@xxxbrains.com Date: Wed, September 28, 2011 1:06 am To: shelby@xxxxpage.com .--------------------------------------------------------------------------

Hi Shelby,

So I was only talking about extending an interface (because in Copute only interfaces can ever be referenced). So in my idea, we are only dealing with collections of methods. The mixin accesses the methods it inherits from.

It was one of the key insights I had to separate implementation from interface.

So, in the vtable for an extended object you'd have the methods of the original object that would access the data, and all the other methods would call those ones. OK.

Perhaps it helps that Copute is an immutable language, meaning the constructor parameters are never mutated, so there is no need for a setter. I need to think more about whether this is required.

It is required, because if you allow mutable state, your classes would want some state that is not passed as a constructor argument at all, but is implemented internally (e.g. a cache or something like that).

I need to think more about the optimum low-level VM layout of the class structure. I think optimally the object structure needs to be an array of vtable pointers. Thus to convert and extend the object, must copy this array. Thus extension conversion (as opposed to viewing an object with an extended interface) gets more costly, the more granular the interfaces.

You might be interested in Eiffel's approach to this problem. Bertrand Meyer is very proud of doing vtables better that C++.

imperative language. Afaics, the future is an immutable language, and the only competitor is Haskell, and I have explained at my link above why Haskell can't suffice. So the market is wide-open for a mainstream immutable language. Thus not knowing what you know about your markets, and while acknowledging the huge Java imperative market, I somehow think you have better chance of major success by implementing Copute's design instead :) I didn't originally contact you with the intent of saying this.

There are quite a few immutable languages out there. ML dialects are very successful, especially OCaml and recently F#. Yes, they have mutability with references, but this is a pretty isolated feature. Erlang totally rocks in some application domains.

They say Fantom is successfully applied. Haskell is the most sophisticated and the only lazy language, and that's it. There are very many alternatives.

The fundamental concept is that the caller is providing the pointer to set of methods that apply to the object also being passed as input to a function which expects those set of methods.

This sounds a lot like structural typing. You might want to look at the Go language, they have interfaces and classes similar to what you have and typing is structural.

Andrey Breslav http://jetbrains.com Develop with pleasure!

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: Extension discussion: suggesting vtable and mixins From: "Shelby Moore" shelby@xxxxpage.com Date: Wed, September 28, 2011 10:17 am To: "Andrey Breslav" andrey.breslav@xxxbrains.com .--------------------------------------------------------------------------

Hi Andrey,

Due to linearized multiple inheritance, the order of interfaces in the vtable isn't determined until the class's total hierarchy is known, because if "trait A extends C with D with E" and "trait B extends D with C", then "class F extends A with B" would effectively reverse the order of linearized inheritance of and insert B into "trait A extends E with B with D with C".[1]

Thus, when referencing an interface that extends another interface, the above implies inconsistent method order of the vtable for supertype portions of an interface, since it depends on the inheritance tree of the class implementing that interface. This problem apparently applies to Java's interfaces, and various strategies have been employed.[2]

It seems to me that each interface could have a consistent method order, by duplicating the method entries for the the supertype interfaces contained within each interface. Perhaps this is what C++ did.[3]

Since member values (i.e. non-method data that change on each instance of a class) can not be multiply inherited, then each class method which accesses a class member value (these are only immutable class constructor parameters in Copute), will know the offset of that member in the data structure of the class.

So if we have a function that requires an Extended interface, and the caller has a NonExtended interface, then our choices are as follows.

A) Statically call extended methods, by passing the NonExtended interface as input, e.g. Kotlin's extension feature. Extension is hard-coded and modularity of typing is lost, which can domino into gridlock spaghetti, forcing refactoring. The feature is optional and Adapter and Decorator design patterns can be used to simulate B and C below, but perhaps less optimally.

B) Use some dynamic dispatch mechanism to apply an Extended interface to a NonExtended interface. One option is for the caller to wrap by reference a NonExtended in an Extended, and use delegate methods (these delegates might get inlined by the JIT). Another option is pass the NonExtended instance to the function, along with a vtable of extension functions, i.e. resolve the delegates inline at compile-time inside the function.

These functions are not mixins, because a mixin which inherits from NonExtended, also expects its own methods to be members of the vtable of 'this'. But if the low-level semantics is as stated in the prior paragraph, to pass a separate vtable for the extension functions, we could compile mixins to this low-level semantic. So this is what I originally intended to suggest as the generalization of A. This does not change the identity of the NonExtended object.

The choice for NonExtended may be arbitrary. To enable the most compositional degrees-of-freedom, a function specialized on each supertype of Extended should be provided. Afaics, this could be automated, and provided on demand at compile-time, assuming C is also available.

C) Caller could convert the NonExtended to an Extended. Same as for B, the caller can do a wrapping with delegates. Or most optimally the vtable for the object could be copied and appended with the Extended vtable. This was the other aspect to my original suggestion.

Below the footnotes, I respond to your responses interleaved.

[1] "Why not multiple inheritance?" in chapter on Traits in Programming in Scala.

[2] http://www.research.ibm.com/people/d/dgrove/papers/oopsla01.pdf http://stackoverflow.com/questions/1504633/what-is-the-point-of-invokeinterface/1505476#1505476

[3] Section "4.4 Multiple Inheritance in C++"[2], and A.C.Myers proposed space optimizations.

Hi Shelby,

So I was only talking about extending an interface (because in Copute only interfaces can ever be referenced). So in my idea, we are only dealing with collections of methods. The mixin accesses the methods it inherits from. It was one of the key insights I had to separate implementation from interface.

So, in the vtable for an extended object you'd have the methods of the original object that would access the data, and all the other methods would call those ones. OK.

I described this in more detail in my latest reply above.

Perhaps it helps that Copute is an immutable language, meaning the constructor parameters are never mutated, so there is no need for a setter. I need to think more about whether this is required. It is required, because if you allow mutable state, your classes would want some state that is not passed as a constructor argument at all, but is implemented internally (e.g. a cache or something like that).

Static fields are an anti-pattern. If that is what you mean, I hope you won't have them in Kotlin.

http://lambda-the-ultimate.org/node/2678 http://gbracha.blogspot.com/2008/02/cutting-out-static.html

Without static fields (i.e. global state), I don't think my idea is impacted by whether the language has mutable class member fields.

I need to think more about the optimum low-level VM layout of the class structure. I think optimally the object structure needs to be an array of vtable pointers. Thus to convert and extend the object, must copy this array. Thus extension conversion (as opposed to viewing an object with an extended interface) gets more costly, the more granular the interfaces. You might be interested in Eiffel's approach to this problem. Bertrand Meyer is very proud of doing vtables better that C++. imperative language. Afaics, the future is an immutable language, and the only competitor is Haskell, and I have explained at my link above why Haskell can't suffice. So the market is wide-open for a mainstream immutable language. Thus not knowing what you know about your markets, and while acknowledging the huge Java imperative market, I somehow think you have better chance of major success by implementing Copute's design instead :) I didn't originally contact you with the intent of saying this. There are quite a few immutable languages out there.

There are only 3 I know of Haskell, Clean, and Mercury:

http://james-iry.blogspot.com/2010/05/types-la-chart.html

And none of those could ever go mainstream. They are too obtuse.

ML dialects are very successful, especially OCaml and recently F#. Yes, they have mutability with references, but this is a pretty isolated feature.

None of those are immutable (i.e. declarative), but rather imperative languages (see "paradigms" in upper, right corner):

http://en.wikipedia.org/wiki/OCaml http://en.wikipedia.org/wiki/F_Sharp_programming_language

Erlang totally rocks in some application domains. They say Fantom is successfully applied.

Fantom's and Erlang's immutability is I think only optional, which defeats the point. Fantom supports imperative statements, such as for, while, break, continue, etc.. An pure functional language should use tail recursion for all loops. It is impossible to use a loop and the code to be immutable. Fantom has a Void function output type, which is impossible in an immutable language, because such a function can only create side-effects. Fan even supports static fields, i.e. global state. That is the anti-pattern of referential transparency.

Fantom's type system has many corner cases, holes, and incomplete. Doesn't even support generics, must less higher-kinds:

http://fantom.org/sidewalk/topic/675#c4549 http://fantom.org/sidewalk/topic/1433

The Actor model addresses concurrency, not parallelism:

http://existentialtype.wordpress.com/2011/03/17/parallelism-is-not-concurrency/

Afaics, parallelism is much more important, because we are headed towards massively multicore (doubling # of cores every 18 months or faster). For this you need a category theory collections API, and for this I find without higher-kinded generics, it gets real ugly (e.g. Scalaz nightmare complexity). Afaik, only Scala, Haskel, and ML have higher-kinded generics.

Haskell is the most sophisticated and the only lazy language, and that's it.

It is not the most sophisticated in some key ways (although it may be the most sophisticated immutable language). It can't do multiple inheritance for one thing. I covered the comparison of Copute to Scala, Haskell, and ML at the linked document I shared with you. And Bob Harper argues (and I concur) that lazy is inferior:

http://augustss.blogspot.com/2011/05/more-points-for-lazy-evaluation-in.html#4642367335333855323

http://existentialtype.wordpress.com/2011/04/24/the-real-point-of-laziness/

I studied Filinkski's paper, and summarized the conclusions at Copute's document.

There are very many alternatives.

There is nothing for the mainstream programmer at all. Big fat zero.

I didn't want to create a language. But nobody will make the language we application developers really need. I got tired of asking.

Scala is the best I've seen by far. But it is not enforcing immutability and it is a bit too complex and some odd syntax gotchas.

People are attracted to Clojure because it is simpler and more focused on functional programming. I have that in spades with the LISP parenthesis maze.

Copute is basically Scala with a cleaned syntax and no mutability. And the type system power is retained.

The fundamental concept is that the caller is providing the pointer to set of methods that apply to the object also being passed as input to a function which expects those set of methods. This sounds a lot like structural typing.

Afaik, structual typing doesn't have vtables known at compile-time, which is why it is so slow on JVM. Scala has it, but it is very slow.

You might want to look at the Go language, they have interfaces and classes similar to what you have and typing is structural.

Structural typing is bad because it breaks behavioral covariance (Liskov Substitution Principle).

I don't allow structural typing in Copute.

Consider supplying an instance of List with count() member and Iterator with count() member to a function that inputs a structural type containing an count() member. The count of elements in a set is not a compatible semantic to the count of iterations completed or remaining.

The interface type implies a meaning. To structurally match on methods of an interface, loses that meaning.

I do think it would useful to support some kind of partial interface type. Where it is possible to inherit from and reference only some methods of an interface. Then the meaning of the interface identifier is not lost.

This would then have the same vtable format at compile-time as the full interface, but would allow null references for the unused methods. Thus a full interface could still be input to a partial interface type.

Actually this is a new idea, that you just caused me to articulate. I had it vaguely in my mind for a while now.

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Fantom From: "Shelby Moore" shelby@xxxxpage.com Date: Wed, September 28, 2011 9:48 pm To: "Andrey Breslav" andrey.breslav@xxxbrains.com .--------------------------------------------------------------------------

I decided to become opinionated, when Fantom developer argued that dynamic typing is better than static typing:

http://fantom.org/sidewalk/topic/675#c11391

[shelby3]

---------------------------- Original Message ---------------------------- Subject: followup From: "Shelby Moore" shelby@xxxxpage.com Date: Fri, September 30, 2011 1:03 am To: "Andrey Breslav" andrey.breslav@xxxbrains.com .--------------------------------------------------------------------------

Clarified the issue of extension:

http://fantom.org/sidewalk/topic/675#c11399 http://fantom.org/sidewalk/topic/675#c11396 http://fantom.org/sidewalk/topic/675#c11391

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: corrections and more... Re: Extension discussion: suggesting vtable and mixins From: "Andrey Breslav" andrey.breslav@xxxbrains.com Date: Fri, September 30, 2011 1:47 am To: shelby@xxxxpage.com .--------------------------------------------------------------------------

Perhaps it helps that Copute is an immutable language, meaning the constructor parameters are never mutated, so there is no need for a setter. I need to think more about whether this is required. It is required, because if you allow mutable state, your classes would want some state that is not passed as a constructor argument at all, but is implemented internally (e.g. a cache or something like that).

Static fields are an anti-pattern. If that is what you mean, I hope you won't have them in Kotlin.

I don't mean static fields. I mean mutable instance fields, that have to internal to the class for it to maintain its invariants.

Think of ArrayList that has two mutable fields: array reference and a number of cells used so far. Both must be maintained consistently, and not passed from the outside.

As of immutable languages, have a closer look at Erlang.

Andrey Breslav http://jetbrains.com Develop with pleasure!

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: corrections and more... Re: Extension discussion: suggesting vtable and mixins From: "Shelby Moore" shelby@xxxxpage.com Date: Fri, September 30, 2011 2:12 am To: "Andrey Breslav" andrey.breslav@xxxbrains.com .--------------------------------------------------------------------------

Perhaps it helps that Copute is an immutable language, meaning the constructor parameters are never mutated, so there is no need for a setter. I need to think more about whether this is required. It is required, because if you allow mutable state, your classes would want some state that is not passed as a constructor argument at all, but is implemented internally (e.g. a cache or something like that).

Static fields are an anti-pattern. If that is what you mean, I hope you won't have them in Kotlin. I don't mean static fields. I mean mutable instance fields, that have to internal to the class for it to maintain its invariants. Think of ArrayList that has two mutable fields: array reference and a number of cells used so far. Both must be maintained consistently, and not passed from the outside.

The invariants are maintained because necessarily the extension methods added, must access the mutable fields only via the public methods and fields of the class.

I can see your concern, if this restriction was not enforced, i.e. if the mixins were able to mutate 'protected' access fields. The extension could then violate the invariants of the non-extended class. Good point.

As of immutable languages, have a closer look at Erlang.

It is dynamically typed, and thus it is fail. Refer to the linked comments I sent you in the prior email. Dynamic (uni-) typing can not scale modular composition.

Also Erlang is geared for concurrency, and imo parallelism is more important. I covered that in the linked comments I emailed you.

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: corrections and more... Re: Extension discussion: suggesting vtable and mixins From: "Andrey Breslav" andrey.breslav@xxxbrains.com Date: Fri, September 30, 2011 5:48 am To: shelby@xxxxpage.com .--------------------------------------------------------------------------

I can see your concern, if this restriction was not enforced, i.e. if the mixins were able to mutate 'protected' access fields. The extension could then violate the invariants of the non-extended class. Good point.

Not only this. If all the fields are constructor parameters, this means that their initial values are passed in by an uncontrolled party, that does not guarantee any invariants. On the contrary, if there are fields that are not passed from the outside directly, the class can properly initialize them to guarantee the initial fulfillment of the invariant.

As of immutable languages, have a closer look at Erlang. It is dynamically typed, and thus it is fail. Refer to the linked comments I sent you in the prior email. Dynamic (uni-) typing can not scale modular composition.

Good point.

Andrey Breslav JetBrains, Inc. http://www.jetbrains.com "Develop with pleasure!"

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: corrections and more... Re: Extension discussion: suggesting vtable and mixins From: "Shelby Moore" shelby@xxxxpage.com Date: Fri, September 30, 2011 8:58 am To: "Andrey Breslav" andrey.breslav@xxxbrains.com .--------------------------------------------------------------------------

I can see your concern, if this restriction was not enforced, i.e. if the mixins were able to mutate 'protected' access fields. The extension could then violate the invariants of the non-extended class. Good point. Not only this. If all the fields are constructor parameters, this means that their initial values are passed in by an uncontrolled party, that does not guarantee any invariants.

I do not understand this. The constructor parameters always fulfill the invariants, because the type of the constructor parameters determines their allowed values.

Perhaps you are thinking that in some languages, the constructor parameters are not accessible and only exist as inputs for the constructor function to initialize the class member instance fields. But I still don't see how that applies.

On the contrary, if there are fields that are not passed from the outside directly, the class can properly initialize them to guarantee the initial fulfillment of the invariant.

But I don't see how the constructor has anything to do with the "view bound" form of extension, where we treat the NonExtended interface as an input to the extension functions? The extension functions only access the public interface of NonExtended.

Which is the also the case if we create an Extended instance, with a constructor function that stores a reference to the NonExtended instance, and the Extended class has delegate methods.

All I have done in the "view bound" case is take your idea for extension functions, and pass the pointer to array of such functions as input to the function using them, instead of linking to them statically at compile-time.

As of immutable languages, have a closer look at Erlang. It is dynamically typed, and thus it is fail. Refer to the linked comments I sent you in the prior email. Dynamic (uni-) typing can not scale modular composition. Good point.

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: corrections and more... Re: Extension discussion: suggesting vtable and mixins From: "Andrey Breslav" andrey.breslav@xxxbrains.com Date: Fri, September 30, 2011 9:03 am To: shelby@xxxxpage.com .--------------------------------------------------------------------------

I do not understand this. The constructor parameters always fulfill the invariants, because the type of the constructor parameters determines their allowed values.

If only it could be so :)

Let's look at ArrayList. It has two fields: size and array. So, in Copute, its constructor would have two parameters. Now, assume I call it this way:

new ArrayList(10, new Object[5])

My invariants are totally broken at this point, although the types are respected.

On the other hand, if I had a constructor with one parameter, size, and a non-parameter field, it would be fine, because the constructor could initialize the field in accordance with the invariant.

Andrey Breslav JetBrains, Inc. http://www.jetbrains.com "Develop with pleasure!"

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: corrections and more... Re: Extension discussion: suggesting vtable and mixins From: "Shelby Moore" shelby@xxxxpage.com Date: Fri, September 30, 2011 4:29 pm To: "Andrey Breslav" andrey.breslav@xxxbrains.com .--------------------------------------------------------------------------

I do not understand this. The constructor parameters always fulfill the invariants, because the type of the constructor parameters determines their allowed values. If only it could be so :)

Let's look at ArrayList. It has two fields: size and array. So, in Copute, its constructor would have two parameters. Now, assume I call it this way:

new ArrayList(10, new Object[5])

My invariants are totally broken at this point, although the types are respected.

On the other hand, if I had a constructor with one parameter, size, and a non-parameter field, it would be fine, because the constructor could initialize the field in accordance with the invariant.

Or if you had dependent-typing, that the type of the second parameter could be typed and enforced by the compiler. Actually you can type this in Scala, as there is a complex way to simulate dependent-typing. Also I read that someone is working on dependent typing for Scala. But I am not a fan of dependent-typing, because it has a compile-time domino effect and will spread its tentacles out into the entire code base. I don't want to program in Epigraph or Coq.

Imo, the invariants are not broken, because the ArrayList has not declared sufficient invariants for the semantics it wishes to have. What I am saying is that the type system defines the invariants. The library designer has to work within the limitations of the type system, else the library will have holes, i.e. bugs. From my perspective, that design for ArrayList is a bug.

The correct design for ArrayList is to not have a separate parameter for length, because the second parameter already has a length field. In general if there are necessary computed (i.e. dependent) fields, then make the constructor private and provide a static factory method (which has access to call the constructor) that inputs the non-computed (independent) parameters.

In any case, I don't see how this applies to the extension discussion. The extension functions don't constructor a new instance of the non-extended instance, they simply access its public interface.

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: corrections and more... Re: Extension discussion: suggesting vtable and mixins From: "Andrey Breslav" andrey.breslav@xxxbrains.com Date: Sat, October 1, 2011 1:36 am To: shelby@xxxxpage.com .--------------------------------------------------------------------------

The correct design for ArrayList is to not have a separate parameter for length, because the second parameter already has a length field. In general if there are necessary computed (i.e. dependent) fields, then make the constructor private and provide a static factory method (which has access to call the constructor) that inputs the non-computed (independent) parameters.

Well, you know, an ArrayList has to have a separate size field that is not equal (but not greater) than the array length. This is the only way to implement array expansion efficiently.

And the statement you make here is very counter-practical. no type system will ever guarantee the invariants a programmer wants to guarantee. Even dependent types which, by the way, can not be fully powerful and sound at the same time if your language is Turing-complete.

In any case, I don't see how this applies to the extension discussion. The extension functions don't constructor a new instance of the non-extended instance, they simply access its public interface.

We got pretty far in this discussion, and I'd like to remind you that we started from considering your approach to having only constructor parameters for the case of mutable fields.

Andrey Breslav http://jetbrains.com Develop with pleasure!

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: corrections and more... Re: Extension discussion: suggesting vtable and mixins From: "Shelby Moore" shelby@xxxxpage.com Date: Sat, October 1, 2011 6:02 am To: "Andrey Breslav" andrey.breslav@xxxbrains.com .--------------------------------------------------------------------------

The correct design for ArrayList is to not have a separate parameter for length, because the second parameter already has a length field. In general if there are necessary computed (i.e. dependent) fields, then make the constructor private and provide a static factory method (which has access to call the constructor) that inputs the non-computed (independent) parameters. Well, you know, an ArrayList has to have a separate size field that is not equal (but not greater) than the array length. This is the only way to implement array expansion efficiently.

And I have already explained how to do that in a operationally type safe way. Make the constructor private, and only give the permission to call it to a function or functions which have been verified to have the correct semantics. That verified function can then be called publicly.

As you note below, there is no way to make a language both turing complete and provable.

Tangentially, this is really just Godel's theorem, which is another way of stating the Entropic force (you may not be aware of it, it is newly proven by Erik Verlinde since 2010, causing quite a stir, and was my theory since 2006/8).

And the statement you make here is very counter-practical. no type system will ever guarantee the invariants a programmer wants to guarantee. Even dependent types which, by the way, can not be fully powerful and sound at the same time if your language is Turing-complete.

The type system guarantees the invariants that it models, but of course there can never be 100% coverage of any phenomenon, because the cost is asymptotic. If the cost to move from 99% to 100% coverage (of any phenomenon) was the same as 98% to 99%, then nothing would exist. If everything was a single color, there would be no colors. Absolute coverage of uniform distributions are impossible in nature. This is because the universe is trending to maximum independent possibilities, i.e. degrees-of-freedom, i.e. disorder a/k/a entropy. This is an 1856 law of thermodynamics.

The key is to design in a way that maximizes degrees-of-freedom, because it is where your the hinges are not (where you chain link does not bend), that the leakage of disorder will appear.

So what I have shown is that my design does not limit the feature (degree-of-freedom) for the ArrayList. And yet still operationally maintains the type safety to enforce the invariants.

In any case, I don't see how this applies to the extension discussion. The extension functions don't constructor a new instance of the non-extended instance, they simply access its public interface.

We got pretty far in this discussion, and I'd like to remind you that we started from considering your approach to having only constructor parameters for the case of mutable fields.

I assume what you are thinking here is that constructor parameters are not sufficient to implement a class, per the ArrayList example. But I have argued that all such functionality can in an external (i.e. static) function.

It is possible there is some major hole in what I have been thinking about. I am very interested to hear if you find one.

Btw, I don't see this a competition as much as I want to collaborate. I think people bring different experiences, perspectives, and skill sets to bear of advancing the state-of-the-art. I try to find the maximum division-of-labor.

Best, Shelby

Andrey Breslav http://jetbrains.com Develop with pleasure!

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: corrections and more... Re: Extension discussion: suggesting vtable and mixins From: "Andrey Breslav" andrey.breslav@xxxbrains.com Date: Sat, October 1, 2011 12:31 pm To: shelby@xxxxpage.com .--------------------------------------------------------------------------

And I have already explained how to do that in a operationally type safe way. Make the constructor private, and only give the permission to call it to a function or functions which have been verified to have the correct semantics. That verified function can then be called publicly.

I missed this explanation, sorry.

Btw, I don't see this a competition as much as I want to collaborate. I think people bring different experiences, perspectives, and skill sets to bear of advancing the state-of-the-art. I try to find the maximum division-of-labor.

Totally agreed.

Andrey Breslav http://jetbrains.com Develop with pleasure!

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: corrections and more... Re: Extension discussion: suggesting vtable and mixins From: "Shelby Moore" shelby@xxxxpage.com Date: Sat, October 1, 2011 4:18 pm To: "Andrey Breslav" andrey.breslav@xxxbrains.com .--------------------------------------------------------------------------

Thanks also for the discussion. You helped to refine two important concepts in my work. Hope you get some practical benefit from the discussion.

And I have already explained how to do that in a operationally type safe way. Make the constructor private, and only give the permission to call it to a function or functions which have been verified to have the correct semantics. That verified function can then be called publicly. I missed this explanation, sorry.

Btw, I don't see this a competition as much as I want to collaborate. I think people bring different experiences, perspectives, and skill sets to bear of advancing the state-of-the-art. I try to find the maximum division-of-labor. Totally agreed.

Andrey Breslav http://jetbrains.com Develop with pleasure!

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Scala does not quite solve the Expression Problem From: "Shelby Moore" shelby@xxxxpage.com Date: Wed, December 7, 2011 1:05 am To: "Andrey Breslav of Kotlin" andrey.breslav@xxxbrains.com .--------------------------------------------------------------------------

FYI, what we were talking about before. I am have very simple code examples now and a well organized exposition at the link below.

I think I noticed an oversight in the paper about Scala's solution to the Expression Problem:

http://stackoverflow.com/questions/8409822/complete-solutions-to-the-expression-problem

Afaics, the Scala solution does not address interoperability of the non-extended objects with the extended types, thus really doesn't have extension.

I think the paper made the wrong conclusion about multimethods, when they are scoped at the use site. I think that is the only way to truely solve the Expression Problem.

-Shelby

[shelby3]

The stackoverflow.com link in the prior email is dead (SO censored it!), so I saved a copy here:

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

[shelby3]

---------------------------- Original Message ---------------------------- Subject: 100% clear now on extension From: "Shelby Moore" shelby@xxxxpage.com Date: Thu, December 8, 2011 4:17 am To: "Andrey Breslav of Kotlin" andrey.breslav@xxxbrains.com .--------------------------------------------------------------------------

I have added a "tradeoff rule" to my answer, and now I think it is correct and it makes everything we were talking about before 100% clear:

http://stackoverflow.com/questions/8409822/complete-solutions-to-the-expression-problem

You see the vtable swap that I was talking about, only applies in the match-case to convert an Interface to an Interface with Interface2. We always end up with a default case.

-Shelby

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: 100% clear now on extension From: "Andrey Breslav" andrey.breslav@xxxbrains.com Date: Thu, December 8, 2011 7:00 am To: shelby@xxxxpage.com .--------------------------------------------------------------------------

Did you have a look at this paper? http://lambda-the-ultimate.org/node/4394

On Dec 8, 2011, at 12:17 , Shelby Moore wrote:

I have added a "tradeoff rule" to my answer, and now I think it is correct and it makes everything we were talking about before 100% clear:

http://stackoverflow.com/questions/8409822/complete-solutions-to-the-expression-problem

You see the vtable swap that I was talking about, only applies in the match-case to convert an Interface to an Interface with Interface2. We always end up with a default case.

-Shelby

Andrey Breslav JetBrains, Inc. http://www.jetbrains.com "Develop with pleasure!"

[shelby3]

---------------------------- Original Message ---------------------------- Subject: Re: 100% clear now on extension From: "Shelby Moore" shelby@xxxxpage.com Date: Thu, December 8, 2011 8:40 am To: "Andrey Breslav" andrey.breslav@xxxbrains.com .--------------------------------------------------------------------------

It was that LtU thread that caused me to write that Q&A on SO, but I had forgotten to come back and actually read the article.

Turns out that my tradeoff rule holds true, please see the comment I added below my answer:

http://stackoverflow.com/questions/8409822/complete-solutions-to-the-expression-problem/8409828#8409828

Thanks for reminding me.

Did you have a look at this paper? http://lambda-the-ultimate.org/node/4394

On Dec 8, 2011, at 12:17 , Shelby Moore wrote:

I have added a "tradeoff rule" to my answer, and now I think it is correct and it makes everything we were talking about before 100% clear:

http://stackoverflow.com/questions/8409822/complete-solutions-to-the-expression-problem

You see the vtable swap that I was talking about, only applies in the match-case to convert an Interface to an Interface with Interface2. We always end up with a default case.

-Shelby

Andrey Breslav JetBrains, Inc. http://www.jetbrains.com "Develop with pleasure!"