Repository navigation
Solution to the Expression Problem #15
Description
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.
Activity
shelby3 commentedon Sep 26, 2016
---------------------------- 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.
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.
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 commentedon Sep 26, 2016
---------------------------- 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,
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?
I am aware of no way of using a vtable at compile time.
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.
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 commentedon Sep 26, 2016
---------------------------- 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
.--------------------------------------------------------------------------
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.
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,...
{
}
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 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.
This depends on the language's specification. There is no problem here
that isn't also in multiple inheritance of mixins.
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,...
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).
Ditto. Interested to hear any feedback, if you have.
shelby3 commentedon Sep 26, 2016
---------------------------- 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,
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 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.
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.
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).
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 commentedon Sep 26, 2016
---------------------------- 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
.--------------------------------------------------------------------------
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.
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).
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.
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.
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.
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.
shelby3 commentedon Sep 26, 2016
---------------------------- 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, 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.
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).
You might be interested in Eiffel's approach to this problem. Bertrand Meyer is very proud of doing vtables better that C++.
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.
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 commentedon Sep 26, 2016
---------------------------- 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.
I described this in more detail in my latest reply above.
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.
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.
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
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.
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 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.
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.
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 commentedon Sep 26, 2016
---------------------------- 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 commentedon Sep 26, 2016
---------------------------- 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 commentedon Sep 26, 2016
---------------------------- 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
.--------------------------------------------------------------------------
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 commentedon Sep 26, 2016
---------------------------- 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
.--------------------------------------------------------------------------
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.
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 commentedon Sep 26, 2016
---------------------------- 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
.--------------------------------------------------------------------------
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.
Good point.
Andrey Breslav
JetBrains, Inc.
http://www.jetbrains.com
"Develop with pleasure!"
shelby3 commentedon Sep 26, 2016
---------------------------- 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 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.
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.
shelby3 commentedon Sep 26, 2016
---------------------------- 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
.--------------------------------------------------------------------------
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 commentedon Sep 26, 2016
---------------------------- 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
.--------------------------------------------------------------------------
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 commentedon Sep 26, 2016
---------------------------- 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
.--------------------------------------------------------------------------
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.
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 commentedon Sep 26, 2016
---------------------------- 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
.--------------------------------------------------------------------------
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).
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.
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
shelby3 commentedon Sep 26, 2016
---------------------------- 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
.--------------------------------------------------------------------------
I missed this explanation, sorry.
Totally agreed.
Andrey Breslav
http://jetbrains.com
Develop with pleasure!
shelby3 commentedon Sep 26, 2016
---------------------------- 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.
shelby3 commentedon Sep 26, 2016
---------------------------- 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 commentedon Sep 26, 2016
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 commentedon Sep 26, 2016
---------------------------- 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 commentedon Sep 26, 2016
---------------------------- 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:
Andrey Breslav
JetBrains, Inc.
http://www.jetbrains.com
"Develop with pleasure!"
shelby3 commentedon Sep 26, 2016
---------------------------- 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.