Orthogonal concepts
Opened this issue · 192 comments
I am trying to nail down in my mind, the fundamental orthogonal semantic concepts of our proposed programming language.
| Concept | Description |
|---|---|
data |
Unified sum, product, recursive, and record data types. No early bound operations other than construction and access. Record types may optionally be mutable. |
typeclass |
Delayed binding of operations to types at the use-site. Contrast to OOP (subclassing) which binds operations at construction of objects. For polymorphic types, typeclass objects delays binding operations until construction of the typeclass object (instead of prematurely binding operations at the construction of an instance of the implementing type); whereas, my posited and proposed solution to the Expression Problem employing unions, in theory further delays binding to the use-site for polymorphic types. Note that delaying is a positive attribute in this context, because it increases degrees-of-freedom. |
module |
Encapsulating data with compile-time (statically) bound operations and access control, enabling more sophisticated types. |
| monadic effect system | #4 (comment) |
Thus I am wondering if module is the most apt name for the concept? I think of a module as a unit of code that is imported separately. We still need to import data and typeclass, so is this done by files? Isn't each file then a module? If so, what is the apt name for the concept of module above? I am thinking the above concept for module is really a class (without the subclassing inheritance anti-pattern). Can't modules extend other modules?
Edit: note also OCaml functors and modules.
Edit#2: on typeclasses, I replied to @keean:
Optional implicit parameters (which Scala has) provide a way of unifying runtime interfaces (passed by value) and monomorphisable interfaces (passed implicitly by type).
I like that summary (in the context of what I had written). We should make sure we frame that and use it in our documentation.
I think it is important to remember that we want to keep implementation of interface (i.e. typeclass) orthogonal to instantiation of data, otherwise we end up with the early binding of subclassing. For example, in subclassing both a rectangle and a square would be subclasses of an interface which provides width and height. Yet a square only has one dimension, not two. Any interfaces which need to operate on the dimensions of rectange and square need to be customized for each, which is what typeclasses do. We will still have subtyping such as when an interface extends another interface then we can subsume to the supertype (which is why we need read-only references and for supersuming then write-only references). Yet references will not have the type of an interface if we don't provide typeclass objects, so then the only case of subtyping will be the subset relationships created by conjunctions and disjunctions of data types.
Yes, I think that is correct. We basically split objects into three orthogonal concepts, data are effectively object properties, typeclass are inferfaces, an modules control data hiding (privite data etc).
Note: Elsewhere I proposed that we can combine the three into a single syntax and generic concept, but lets leave that to one side for now.
Did you see my edits pointing out that 'module' has two meanings? Should we use another keyword than module?
Extension and functors are something ML supports on modules, at the moment I don't think we should. I like the ability to have multiple modules in one file, but effectively modules are able to be separately compiled and linked later. In the simplest form they are like namespaces where you cannot access their private data from outside. A module has to export things to be visible outside, and import the external functions and data in order for them to be visible inside.
Note I added the idea for a monadic effect system. Well I guess it isn't orthogonal in some sense as its implementation relies I suppose on the other 2 or 3 concepts, but the systemic model for handling of impurity is an orthogonal concept.
@shelby3 wrote:
Concept Description typeclassDelayed binding of operations to types at the use-site. Contrast to OOP (subclassing) which binds operations at construction of objects. For polymorphic types, typeclass objects delays binding operations until construction of the typeclass object (instead of prematurely binding operations at the construction of an instance of the implementing type); whereas, my posited and proposed solution to the Expression Problem employing unions, in theory further delays binding to the use-site for polymorphic types. Note that delaying is a positive attribute in this context, because it increases degrees-of-freedom.
I want to raise this conceptualization of solving the Expression Problem to a matrix, so that we can how this plays out on more levels.
Background
Dynamic polymorphism is instituted whenever we bind the interface to an object and refer to the type of that object as the interface; Because whether it be at data type object instantiation for subclassing or typeclass object instantiation (aka Rust trait objects), we then must incur dynamic dispatch because when holding a reference of said interface type at compile-time, there is no static (compile-time) knowledge of the types of data that can be referenced with the said interface type (rather the runtime dynamic dispatch handles the dynamic polymorphism). In subclassing the interface is a supertype and in typeclass objects, the interface is the typeclass bound (constraint) on data types that can be assigned to a reference with said type.
So the lesson that once we bind an interface at compile-time before the function call site, then we forsake static polymorphism and the opportunity for mono-morphisizing the function. More importantly, we lose the axis of the Expression Problem to add new interfaces (operations) to the data types referenced via an interface type. We can add new data types but can't add new operations.
Subclassing binds the interface very early at data type instantiation. Typeclass objects bind later at typeclass object instantiation. And typeclass bounds bind even later at the function call site.
So ideally, we wanted to always delay to typeclass bounds, but this conflicts with polymorphism of adding data types orthogonally when dealing with heterogeneous union types. Thus I pointed out that by retaining the union of data types instead of prematurely subsuming them to the typeclass bound of a typeclass object, then we could delay the binding to the function call site. Thus we can continue to add new orthogonal operations to the union type, unlike for typeclass objects. The trade-off is that adding a new type to a union type requires invariant collections (such as a List); whereas, typeclass objects will interopt fine with arrays because the type of the array doesn't need to change when adding new data types to an exist typeclass object type. I explained this is more detail in prior linked discussion. Readers can refer to the prior explanation, so I don't need to repeat it here.
Matrix Conceptualization
So what we can see is there is a tension with trade-offs between the competing choices of carrying around the specific data types and subsuming to the interface. So both are needed for different situations.
Recently @skaller pointed out another axis of this tension. That is in the case where don't want to discard the data types because we want to leave them open to new operations, but we want to dictate that a specific implementation is used for a specific typeclass where ever it might be needed. Apparently OCaml's functors accomplish this by being first-class and one can pass these along with a module and they will morph the module with the specific constraints desired, while leaving the rest of the module unspecialized, and thus through the chaining of functors, one can get the same effective result as early binding for one typeclass but remaining open to extension for other typeclasses.
So really what we need is to being able to attaching a typeclass object to a data type instance and pass them around as a pair every where a data type is expected. So in other words, dynamic patching of the dictionary for the dynamic dispatch, wherein if that data type is then applied to a trait object at a call site or trait object assignment, then the prior binding is not overwritten and any additional dynamic dispatch bindings are augmented.
So then we no longer view data types and typeclass objects separately. A data type always has a dynamic dictionary attached to it, yet it is augmented at runtime, not with compile-time knowledge. The compiler can only guarantee the required typeclass operations will be available at runtime, but it can't guarantee which implementation was selected, because at runtime when it writes the implementation to the dynamic dictionary of the typeclass object, it can't know if a preexisting one will already exist.
So we have lifted dynamic polymorphism to a 2nd order. We have dynamism of dynamic dispatch.
The matrix is we have two axes of data type and interface, and a third axis of implementations that cojoin the two. This third axis can't be tracked at compile-time without dependent typing, but the compiler only needs to insure that the required interfaces are present in order to insure soundness. So this works.
What this enables is for example @skaller's example of wanting to set the ordering of comparison operations, while leaving the data type open to extension with other typeclasses. @keean's proposed solution also achieves it, but it lacks atomicity of retaining this with the data type. For example, @keean's solution is not generic in type of algorithm that can be applied ex post facto and thus it fails another axis of the tension of solving the Expression Problem.
What we will see generally is that higher order dynamism is required to solve higher order tensions in the Expression Problem.
So the lesson that once we bind an interface at compile-time before the function call site, then we forsake static polymorphism and the opportunity for mono-morphisizing the function.
This is not quite right. We can still mono-morphise even with compile-time interface binding - in fact for the traditional requirement this is a requirement. The point is we can statically know both the interface and the exact type passed, and therefore chose and inline the exact function. Rust does this in all cases exept when dynamic polymorphism in involved.
So we can inline and monomorphise the functions when the interface is statically bound and the type is statically know. If either are false (so dynamic binding to the interface, or dynamic typing) we cannot monomorphise in languages like Rust.
So really what we need is to being able to attaching a typeclass object to a data type instance and pass them around as a pair every where a data type is expected.
This is exactly what adding functions to an objects prototype does in JavaScript.
@keean wrote:
So really what we need is to being able to attaching a typeclass object to a data type instance and pass them around as a pair every where a data type is expected.
This is exactly what adding functions to an objects prototype does in JavaScript.
No it is not the same. The JavaScript prototype impacts all instances. I am referring to impacting only instances which are assigned to the trait bound.
@keean I have decided that it is nearly impossible to try to explain these issues like this. I will need to make detailed code examples and write a white paper. You don't seem to understand me.
No it is not the same. The prototype impacts all instances. I am referring to impacting only instances which are assigned to the trait bound.
So you want the implementation used to depend on the value of the object not just its type.
This is monkey-patching, adding a method directly to the object itself.
@shelby3 wrote:
So the lesson that once we bind an interface at compile-time before the function call site, then we forsake static polymorphism and the opportunity for mono-morphisizing the function.
This is not quite right.
It is right. I just haven't been able to communicate my points to you.
You have written it badly then because
once we bind an interface at compile-time before the function call site, then we forsake static polymorphism and the opportunity for mono-morphisizing the function.
This is exactly the opposite of what is true.
We must bind the interface statically in order to be able to monomorphise and we must statically know the type at the call site as well.
@keean wrote:
The point is we can statically know both the interface and the exact type passed
If you had understood me, you would understand that I already explained that we don't know the exact type passed, that was entirely the point of binding early erasing the data types from further compile-time knowledge and you only have the trait bound remaining. That you didn't even get that point from what I wrote seems really bizarre.
If you had understood me, you would understand that I already explained that you don't know the exact type passed, that was entirely the point. That you didn't even get that point from what I wrote seems really bizarre.
We always know the exact type passed, that is the whole point of parametric polymorphism. The only time we do not is if there is what Rust calls a trait-object or what Haskell calls an existential-type involved.
@keean wrote:
The only time we do not is if there is what Rust calls a trait-object
Bingo. Re-read my long comment again.
So in a traditional system like Rust, if there is a trait object we can never monomorphise, it doesn't matter how early or late the type-class is bound.
@keean wrote:
once we bind an interface at compile-time _before_ the function call site, then we forsake static polymorphism and the opportunity for mono-morphisizing the function.
This is exactly the opposite of what is true.
The word 'before' does not mean 'at'. It means 'before'. I am referring to subsuming to the trait bound before the call site, such as a trait object. But then I generalize it to partial trait objects and 2nd order dynamism.
@keean wrote:
So in a traditional system like Rust, if there is a trait object we can never monomorphise, it doesn't matter how early or late the type-class is bound.
In a system where I have generalized it to partial trait bounds and 2nd order dynamism then we still can't monomorphise but we gain the ability to add operations ex post facto.
Your reading comprehension my long comment was really not adequate. Was it really that badly explained or is it your mind is ossified and not prepared for a generalization?
The word 'before' does not mean 'at'. It means 'before'. I am referring to subsuming to the trait bound before the call site, such as a trait object. But then I generalize it to partial trait objects and 2nd order dynamism.
But if you have dynamic polymorphism you cannot mono-morphise. It doesnt matter whether the interface is bound before or at the call site.
@keean wrote:
But if you have dynamic polymorphism you cannot mono-morphise. It doesnt matter whether the interface is bound before or at the call site.
Precisely. Early binding of interface requires dynamic polymorphism in order to open to adding new data types to the interface bound, e.g. for collections.
Also, you are only considering one of the tradeoffs. You forgot the other one which my long comments states and I have reiterated:
In a system where I have generalized it to partial trait bounds and 2nd order dynamism then we still can't monomorphise but we gain the ability to add operations ex post facto.
But that is not what this sentence says:
So the lesson that once we bind an interface at compile-time before the function call site, then we forsake static polymorphism and the opportunity for mono-morphisizing the function.
This says we cannot mono-morphise if we bind the interface at compile time, when there is dynamic polymorphism. But we cannot mono-morphise at all with dynamic polymorphism, so the logic is wrong.
@keean wrote:
But that is not what this sentence says:
So the lesson that once we bind an interface at compile-time before the function call site, then we forsake static polymorphism and the opportunity for mono-morphisizing the function.
This says we cannot mono-morphise if we bind the interface at compile time, when there is dynamic polymorphism.
Correct.
But we cannot mono-morphise at all with dynamic polymorphism,
Correct.
so the logic is wrong.
What is wrong? You just didn't apparently understand that the goal is not to achieve monomorphism but rather to solve the Expression Problem and keep the extension open to new trait bounds even though we've partially bound to some typeclasses:
@shelby3 wrote:
Precisely. Early binding of interface requires dynamic polymorphism in order to open to adding new data types to the interface bound, e.g. for collections.
The point is that we always pass a data type along with a dictionary, but that dictionary can be incomplete and we don't track at compile-time what may already be in that dictionary. When we are ready to bind some trait bounds at a call site, then we write some code which will add these implementations to the dictionary at runtime (insuring they will be available as required for compile-time soundness), but will not overwrite any that already existed in the dictionary.
The point of this is that our caller can set preferential implementations (such as which direction of ordering for lessThan operation), yet the code that is called doesn't have to prematurely specialize on any trait bound signatures. Premature specialization is the antithesis of combinatorial composition as per @skaller's excellent point.
I think we aren't actually attaching the dictionaries to the data objects. Rather the data objects are tagged (instanceof) and the dictionaries are passed in as arguments to each function. Perhaps we should model it with a monad?
When we are reading to bind some trait bounds at a call site, then we write some code which will add these implementations to the dictionary at runtime.
This is the same as asking if the implementations exist from the call-site. In order to add them, they must first exist in the source code, so the compiler can statically check they exist.
We can go further, we can ask, from the call site, get a list of all types for which there is an implementation of this function. Now we could put this in the type signature so that the linker knows statically what types it is safe to send to that function.
Wow you really aren't getting it.
When we are reading to bind some trait bounds at a call site, then we write some code which will add these implementations to the dictionary at runtime.
This is the same as asking if the implementations exist from the call-site.
Read again:
When we are ready to bind some trait bounds at a call site, then we write some code which will add these implementations to the dictionary at runtime (insuring they will be available as required for compile-time soundness), but will not overwrite any that already existed in the dictionary.
The point of this is that our caller can set preferential implementations (such as which direction of ordering for
lessThanoperation), yet the code that is called doesn't have to prematurely specialize on any trait bound signatures. Premature specialization is the antithesis of combinatorial composition as per @skaller's excellent point.
There is still something odd about the way your description comes across to me, which might be my misunderstanding...
If I have a function that calls methods on something:
f(x) =>
x.call_widget()
We can say with 100% certainty whatever type whether dynamic or static polymorphism that is passed to f must implement call_widget. Do you agree?
@keean wrote:
We can say with 100% certainty whatever type whether dynamic or static polymorphism that is passed to
fmust implement call_widget. Do you agree?
Agreed. And the mistake in your thinking is you are conflating not knowing if an preexisting implementation will not be replaced at runtime, with knowing at compile-time that all required implementations will be placed into the dictionary as required. But I am repeating myself.
I understand the concept is a bit confusing at first for someone not expecting it. I do tend to come of out no where with mind twisting new things.
And the mistake in your thinking is you are conflating not knowing if an preexisting implementation will not be replaced at runtime, with knowing at compile-time that all required implementations will be placed into the dictionary as required. But I am repeating myself.
That is irrelevant, I am talking about at the call-site.
So when call_widget is called on x there must be an implementation for it available. Do you agree?
So then when we have:
f(x) =>
x.call_widget()
We can clearly see no code in f is inserting any implementations into anything. Sorry to have to take it this slowly, but I am feeling particularly stupid today. Are we agreed?
I thought you were inferring the trait bound on x. Yes you need a trait bound there. So what is your point?
Sorry, I really need to take this one step at a time to see where our understanding diverges. I want to get to the bottom of this once and forall :-)
So can you agree we can be sure f is not dynamically changing the implementations available for `x whatever type it is?
So we should agree my original statetment:
We can say with 100% certainty whatever type whether dynamic or static polymorphism that is passed to f must implement call_widget. Do you agree?
So there was no mistake in my thinking, based on the assumptions stated.
Ah, but one of my assumptions could be wrong - you may want to have a method directly implemented on 'x' that does not depend on the type of x, but depends on the value. (so you may have been objecting to the 'type' implementing call_widget, when it might be the value?)
Of course then we are no longer talking about type-classes, but objects with virtual methods.
Of course, if we cannot statically determine that x has an implementation of call_widget then we no longer have type-safety, and we are simply creating a dynamically-typed language like Python and JavaScript already are.
@keean the point you are missing is that some function g can call your f providing an implementation of the necessary typeclass bound for call_widget, but that does not preclude my point. My point is that some other function h which attaches an implementation to the said runtime dictionary for the typeclass for call_widget then calls g, but g does NOT know it at compile-time (only g will know at runtime). So g knows at compile-time that x is dynamically polymorphic and it knows the data type of x, so g writes some runtime code to attach the typeclass bound for call_widget and at runtime it will set this if there isn't already one attached at runtime. In other words, g supplies a default choice for the implementation, but the caller of g can override it. So that the caller could for example change the ordering of lessThan without g needing to specialize and know which typeclasses its caller wants to specialize. This is dynamic dependency injection specialization. It requires that typeclasses have invariant semantics and that only what can change between implementations is what is allowed by the typeclass semantics (which must be the case any way, otherwise typeclasses aren't generic).
Okay, but the we can put the requirement that 'x' must provide an implementation in the signature of 'f', something like:
f(x : A) requires HasCallWidget
x.call_widget().
Now if the constraint 'HasCallWidget' is on the type A then we have a type-class, if it is on the value x then we have subtyping.
One way to do this perhaps is every where we passed a data type into a function, we also pass a dictionary for that data type. We don't bind the dictionaries to the instances of the data type.
You might think this is useless, because you might think a function will know which trait bounds it needs and can allow its caller to specify them at the call site, but that requires the caller to always specify them, which becomes very onerous for composition, although it is more performant given it can be monomophized. And it doesn't allow defaults with overrides.
Afaics the above is not entirely open to extension, because a function for example might save the instances to a collection and later return that data to another caller. So alternative way to do it (and perhaps need both ways) is to bind the dictionaries to the instances of the data type, so then the overrides follow those instances until they are explicitly requested to be erased (overridden).
One way to do this perhaps is every where we passed a data type into a function, we also pass a dictionary for that data type. We don't bind the dictionaries to the instances of the data type.
So we can have first-class dictionaries?
We already have that, a Record is a first class dictionary.
One way to do this perhaps is every where we passed a data type into a function, we also pass a dictionary for that data type
Are you saying you want to pass a dictionary (by value) into a function?
@shelby3 wrote:
You might think this is useless, because you might think a function will know which trait bounds it needs and can allow its caller to specify them at the call site, but that requires the caller to always specify them, which becomes very onerous for composition, although it is more performant given it can be monomophized. And it doesn't allow defaults with overrides.
On further thought most often we want to write functions to be generic on type, so thus the function must require all typeclass bounds it requires and can't offer its own defaults. @skaller was operating on non-polymorphic data types such as Int.
So I am still not quite sure I understand what @skaller's issue is. With generics, we must pass in all the typeclass implementations required by the algorithm.
Edit: the issue might be when we want to be able to accept many different algorithms which have differing requirements for typeclasses, in which case we would need to keep the data types around. So in that case we also wouldn't know ahead of time which typeclass bounds we need. This is a deeper issue I need to think about after I sleep.
@skaller was talking about ML style modules. With an ML style module you can pass the module you wist to use at runtime. So there can be two different implementations for a type.
So if we have Int we might have a module for sorting that does ascending order and one that does descending order. We cannot determine which to use based only on the type of Int.
So ML would pass a dictionary with the comparison operator you want as a parameter to the module.
@shelby3 I think ML style modules are a different issue to the solving of the expression problem, and I think we are over complicating things by trying to discuss both at the same time.
Nobody has claimed ML style modules are a solution to the expression problem. If is more that @skaller does not like being limited to one implementation of an interface per type.
I don't understand why @skaller didn't do the following for his Felix language.
typeclass LessThan<A>
lessThan(A): Bool
f(x: A, y: A) where A: LessThan => x < y // x.lessThan(y)
typeclass ForwardOrder<A> extends LessThan<A>
typeclass ReverseOrder<A> extends LessThan<A>
Int implements ForwardOrder
lessThan(x) => this <= x
Int implements ReverseOrder
lessThan(x) => this >= x
f(0, 1: ForwardOrder)
f(0, 1: ReverseOrder)
P.S. I think your idea of enforcing one implementation per data type is rubbish, because then I can't do the above.
Int implements ForwardOrder
lessThan(x) => this <= x
Int implements ReverseOrder
lessThan(x) => this >= x
Because you can't do that with typeclasses.
lessThan can only be declared in one typeclass.
typeclass ForwardOrder<A> extends LessThan<A>
typeclass ReverseOrder<A> extends LessThan<A>
Int implements ForwardOrder
lessThan(x) => this <= x
Int implements ReverseOrder
lessThan(x) => this >= x
Again not allowed because:
lessThan can only have one definition for Int
This would be allowed:
data LessThan<A> = LessThan {
lessThan(A, A) : Bool
}
let forwardOrder : LessThan<Int> = LessThan {
lessThan(x, y) = x < y
}
let reverseOrder : LessThan<Int> = LessThan {
lessThan(x, y) = x > y
}
f([0, 1], forwardOrder)
f([0, 1], reverseOrder)
Because the ordering is a value you can pass it in.
A type class must only depend on the type of the arguments, so with a type class:
lessThan(x, y)
only the type of x and y can be used to determine which instance to run. If x and y are Int there can only be one implementation for lessThan on Int no matter how you structure things. This is because the only information available is the name of the function and the type of its arguments (and the type of its result), nothing else can be used.
A datatype is first-class, this means it can be passed as an argument to functions like any other first-class object. So we can define:
data LessThan<A> = LessThan {
lessThan(A, A) : Bool
}
f(x : A, y : A, order : LessThan<A>) => order.lessThan(x, y)
Then you can pass in a value of the 'record-type' LessThan, and it will use exactly that function to do the comparison. So a Record of functions is a first class dictionary.
And we can implement type-classes using records, as we are just adding a hidden 'implicit' argument for each type-class and selecting them based on the types at the call site.
P.S. I think your idea of enforcing one implementation per data type is rubbish, because then I can't do the above.
This is not my idea, this is how type-classes work!
@keean wrote:
This is not my idea, this is how type-classes work!
Afaik I know that is a limitation of Haskell.
Feel free to explain why you think the syntax I wrote won't work.
What I see is I can select which implementation I want to supply to the trait bound if I so desire. I have no idea what reason you think otherwise.
Afaik I know that is limitation of Haskell.
No, it is a limitation of "type classes".
Feel free to explain why you think so. Otherwise I say BS.
Feel free to explain why you think the syntax I wrote won't work.
I never said it would not work, but they are not type-classes.
What you have is good old Java style OO interfaces with extension, and objects.
Lol, what does that mean? Show me such a definition in a canonical resource. The reason typeclasses in Haskell ended up with that limitation is because Haskell prefers global principle typings.
Erm, type-classes have a widely known definition. Even Wikipedia seems vaguely accurate:
Erm, type-classes have a widely known definition. Even Wikipedia seems vaguely accurate:
Wikipedia copied Haskell. Again this is a limitation of Haskell's choice of priorities for global principle typings. Open your mind a bit.
Wikipedia copied Haskell. Again this is a limitation of Haskell's choice of priorities for global principle typings. Open your mind a bit.
Not surprising seeing as Type Classes were "invented" to solve operator overloading in Haskell, see: http://homepages.inf.ed.ac.uk/wadler/papers/class/class.ps
I don't see whats so difficult. Type Classes depend on "types", its in the name "Type Classes", not "Value Classes" or "Widget Classes" :-)
You want the selected function to depend on a value (yes you really do), so the datatype solution is the right one.
Just forget type-classes exist and tell me what is wrong with this:
data LessThan<A> = LessThan {
lessThan(A, A) : Bool
}
let forwardOrder : LessThan<Int> = LessThan {
lessThan(x, y) = x < y
}
let reverseOrder : LessThan<Int> = LessThan {
lessThan(x, y) = x > y
}
f(0, 1, forwardOrder)
f(0, 1, reverseOrder)
What you have is good old Java style OO interfaces with extension, and objects.
Incorrect. A Java interface has to be bound to the data type when it is instantiated.
Where is this extension feature in Java? And even if you emulated with static methods, you don't get monomorphization.
Wikipedia copied Haskell. Again this is a limitation of Haskell's choice of priorities for global principle typings. Open your mind a bit.
Not surprising seeing as Type Classes were "invented" to solve operator overloading in Haskell, see: http://homepages.inf.ed.ac.uk/wadler/papers/class/class.ps
Not surprising has nothing to do with the fact that Haskell's limitation is not an inherent limitation of the concept of type classes.
Okay, to avoid arguing definitions, lets call them "Shelby-Classes", then we can avoid the whole problem of you not getting what a type-class is.
Although that's probably not necessary, as what you have written looks exactly like Java interfaces...
Here's some C# that does this: https://msdn.microsoft.com/en-us//library/bb383977.aspx
@keean wrote:
Just forget type-classes exist and tell me what is wrong with this:
data LessThan<A> = LessThan { lessThan(A, A) : Bool }
Playing with irrelevant names won't help you. Name lessThan to the semantics I intended which is relativeOrdering.
@keean wrote:
Okay, to avoid arguing definitions, lets call them "Shelby-Classes", then we can avoid the whole problem of you not getting what a type-class is.
You mean of you not getting the generality of the concept of a type class because you've known Haskell too closely for too long and can only think one way.
Playing with irrelevant names won't help you. Name lessThan to the semantics I intended which is relativeOrdering.
Sorry I don't understand... what do you mean? Here are definitions of two different orderings:
let forwardOrder : LessThan<Int> = LessThan {
lessThan(x, y) = x < y
}
let reverseOrder : LessThan<Int> = LessThan {
lessThan(x, y) = x > y
}
You mean of you not getting the generality of the concept of a type class.
Shall I put a post on LtU to resolve the matter?
@keean wrote:
Sorry I don't understand... what do you mean? Here are definitions of two different orderings:
let forwardOrder : RelativeOrdering = RelativeOrdering {
relativeOrdering(x, y) = x < y
}
let reverseOrder : RelativeOrdering = RelativeOrdering {
relativeOrdering(x, y) = x > y
}
@keean wrote:
Shall I put a post on LtU to resolve the matter?
Taking the discussion to where I am banned is going to insure I can't say anything. Excellent idea.
@keean wrote:
as what you have written looks exactly like Java interfaces...
Nope. I didn't bind the selection of the implementation to the data instances when they were constructed.
regarding 'RelativeOrdering', what difference does changing the name of the datatype make?
Nope. I didn't bind the selection of the implementation to the data instances when they were constructed.
Yes its more like C# extension methods, see the link I posted above.
@keean wrote:
what difference does changing the name of the datatype make?
Exactly. As for you conflating the interface with the data type, I didn't have that in my example. So if that was part of your point, then you don't have one.
My point was the code does what you want, it lets you select the ordering produced by f.
@keean wrote:
Yes its more like C# extension methods
As well as Swift extension methods, which can simulate type classes. So they have type classes as others have figured out.
Exactly. As for you conflating the interface with the data type, I didn't have that in my example. So if that was part of your point, then you don't have one.
The data type is the interface, the value is the implementation. Looks good to me :-)
@keean wrote:
My point was the code does what you want, it lets you select the ordering produced by
f.
No it does not. It doesn't allow me to select the implementation delayed at the call site. We just had the discussion earlier today.
No it does not. It doesn't allow me to select the implementation delayed at the call site. We just had the discussion earlier today.
But we also very slowly went through that if f does not create new implementations then setting the implementation at the call site of f is the same as setting is at the call site of lessThan
So then when we have:
f(x) => x.call_widget()We can clearly see no code in f is inserting any implementations into anything. Sorry to have to take it this slowly, but I am feeling particularly stupid today. Are we agreed?
But we also very slowly went through that if f does not create new implementations then setting the implementation at the call site of f is the same as setting is at the call site of lessThan
That is irrelevant to what we are talking about now. You seem to get concepts all comingled in your mind.
Don't conflate the discussion in this thread with the discussion I linked to in other thread.
No it does not. It doesn't allow me to select the implementation delayed at the call site. We just had the discussion earlier today.
Well I think its an important point. How do you respond? To just dismiss it as irrelevant is missing the point.
And besides your code also determined the overload at the callsite of f:
f(0, 1: ForwardOrder) f(0, 1: ReverseOrder)
@keean wrote:
And besides your code also determined the overload at the callsite of
f
Yes that is the point. At the call site, not at the instantiation of the data types, which could have been far up the function hierarchy. I have 0, 1 as literals, but I am confident you can imagine them as references to instances.
Well thats exactly what my code does? The overload is determined by the dictionary passed into f
@keean wrote:
How do you respond? To just dismiss it as irrelevant is missing the point.
How to respond to nonsense?
How to respond to nonsense?
Well you can respond to the code. How does it not do what you want. Produce a counter example where it goes wrong?
@keean wrote:
Well thats exactly what my code does? The overload is determined by the dictionary passed into f
No because you can't add new methods after the data type instance was created. That is the entire point of the Expression Problem.
See the link below where I had told you that earlier:
Don't conflate the discussion in this thread with the discussion I linked to in other thread.
No it does not. It doesn't allow me to select the implementation delayed at the call site. We just had the discussion earlier today.
You take some time to think it over. You'll get it if you slow down and think. You must be overworked and too much multitasking.
No because you can't add new methods after the data type instance was created. That is the entire point of the Expression Problem.
Of course you can the datatype is just the method dictionary. You are passing the type (this Int in this case) separately.
The thing is we know all the methods that f is going to call, so what does adding new methods mean? Where do you want to add new methods?
You cant add new methods to type-classes either.
You must be overworked and too much multitasking.
I must be because I just realised the reason I kept changing the compiler code but the output didn't change is because I was running the wrong command :-)
Anyway the important point to note is the datatype is modelling the type-class, not the integer. So you can pass as many dictionaries as you need. The lessThan datatype was implemented on the Int type parameter and you can have as many datatypes as you want implemented for Ints.
data LessThan<A> = LessThan {
lessThan(A, A) : Bool
}
let forwardOrder : LessThan<Int> = LessThan {
lessThan(x, y) = x < y
}
let reverseOrder : LessThan<Int> = LessThan {
lessThan(x, y) = x > y
}
data Show<A> = Show {
show(A) : ()
let print = Show {
show(x : Int) => print_int(x)
}
let write = Show {
show(x : Int) => write_to_file(x)
}
f(0, 1, forwardOrder, print)
f(0, 1, reverseOrder, write)
f(x, y, order, where) =>
where.show(if order.lessThan(x, y) then x else y)
So now we have extended Int with both LessThan and Show
I am getting a bit lost here so lets back up. The way to do this is not think about concepts, but think "what is the implementation and what does it achieve"?
If you associate a dictionary to an object x of type Int which contains field show and a method to convert int to string, you have some kind of object orientation. Original Haskell was like that.
However this is weak, because it cannot handle relationships. GHC and Felix do not do this, they allow a typeclass to be associated with multiple types. So for example you can have a class Addable with two (input) types, and instances for pairs of types.
This implies you have to pass the dictionary to the function containing the addition operation, it has nothing to do with the types of the objects being added. The function contains code which adds two values by dispatching to an empty slot which will crash, so it has to fill the slot in with the instance corresponding to the slot. The name "type class" is a misnomer, because originally in Haskell it was a class for a single type. Category is a better name.
Felix does this at compile time, but the machinery is the same. Fortress does it at run time, Fortress is a nominally typed (traditional) Object Oriented system with multi-methods which have multiple argument type classes, with the binding done at run time (amazing, specialisation/instance detection at run time).
In Felix there are two steps. First, when you see add (x,y) inside a function, you do lookup to try to find add for the types of x and y. (Felix has overloading remember). The result of that lookup is a type class virtual (unimplemented) method. That is the slot I mentioned above. Associated with the slot is a specific type class, Addable. So the data are required
(a) the name of the type class
(b) the name of the method within that type class
(c) a list of types corresponding to the type parameters of the type class
In Felix, this list of types is precisely those generated by unification of the types of the function arguments and the types of the type class virtual function arguments. These specify a lower bound on the types of an instance we need to find later. By lower bound, I mean we require an instance whose types are at least as general as specified.
The next thing Felix does is monomorphisation. This means that the list of types in the function specifying the type class are now concrete (not polymorphic).
Next, Felix fills in the slot by searching through all instances of the relevant type class. It first finds all the instances of that type class for which the instance bindings of the type class parameters are more general than the monomorphised types: the instances are still polymorphic. Then given the list of candidate instances, we try to find the unique most specialised one. There is an error if not existing or not unique. This is NOT a type checking error, it an instantiation error.
Now, if we find the unique instance, we have to specialise it to the concrete types we have. Then we find the corresponding method of the now monormorphised instance which is named add and put that in the slot. So finally we have a concrete add method.
Now you must note that when we monomorphised the instance, we got recursion. That is, to monomorphise the instance we have to monomorphise the signature of the methods, but we also have to monomorphise the method definitions! So the whole monomorphisation process recurses.
This recursion is crucial. It is what allows Felix to do second order polymorphism, Haskell style, and implement monads, for example. Felix top level functions use type-schema, that is, it is only head (Horne clause in Prolog) polymorphism, aka first order polymorphism. Felix does not support passing polymorphic functions around. HOWEVER type class instantiation DOES. The instantiation mechanism is recursive, which means you have polymorphic recursion. I can show you an example of this in the Felix library: polymorphic recursion is used to print tuples by calling show on the head of the tuple, and recursing to show the tail. In Felix, polymorphic recursion only works using the indirection type classes provide: you can't have polymorphic closures directly but you can have polymorphic type class methods.
If you think the above algorithm is complex .. well I used a high level language (Ocaml) to implement it, and Felix, being a whole program analyser, can fully instantiate all type classes at compile time (completely eliminating them prior to optimisation). So my "dictionaries" are in the compiler only.
In other words in Felix, the type class instantiation is done "after type checking" but "before code generation". It is not "early binding" but it is not "late binding either". C++ works the same way. There this machinery is called "two phase lookup". In C++ it really is lookup. The second phase of lookup looks in the scope of the call site to resolve generics, and type checking has to happen there because in C++ templates aren't type checked during phase 1 BECAUSE they have no type classes (called "concepts" in C++).
So when you have type classes you always have two stages of type checking. The first is your usual type checking, prior to monomorphisation. The second, during monomorphisation, is called instantiation, and just means checking for existence of instances. If you delay this too long you can get errors are run time. This is what dynamic languages do.
I realise my description of the machinery is not enough to actually implement anything. Its just a vague waffle describing how type classes (with multiple type arguments) actually work. AFAIK Felix algorithm is superior to GHC because GHC does not allow overlapping instances. Felix does. However to be fair Felix doesn't provide a termination guarantee, and GHC does. Wish I knew how to do that.
So now: modules work differently to type classes. With a module you specifically pass a particular module (dictionary) to your function. You can do this without all the complications above, because you have a named module, so you just name it and pass it in. The named module's type has to agree with the function's module type signature, this has to be type checked. Given that signature, you can just makes slots to hold the functions of the module to be passed in, and when you call add in your function it is just an indirect call via the slot. If you know the module when compiling you can optimise the slot away and call the method directly. Ocaml added this optimisation only recently. It also used to only allow the passing in at link time, but now you can do it with some restrictions at run time (first class modules).
The idea of type classes is that your generic notation systems are consistent globally. It is a way of extending the language in the library. For example you can define add in the library and it means addition universally .. even though it is not defined for all types yet. It means the same add for a new type that you design, by forcing you to provide an instance for your type (and any other types you want to add with it).
The point here is that the binding to the type class is done by the phase 1 type checker, without knowing about your new type. This means you can use add in a generic Euclid gcd algorithm and the algorithm is full type checked and will work even with your new type that is designed after the algorithm, provided you also provide suitable instances.
The reason for this machinery is that Euclid's gcd algorithm is not parametrically polymorphic, because parametric polymorphism is extremely weak. It only supports a very small set of universal operations, such as product (tuple) formation. Type classes allow you to extend the set of operations to include, say, addition, in limited contexts (namely, where you pass the class to a function requiring that extension). It uses a nasty trick: the type checking first assumes parametric polymorphism, that is, it assumes add works for all types. This is what the type class signatures promise.;
The promise is a lie. add does not work for all types. But you can cheat, and make it seem like it does by providing an instance for the particular cases you are actually using.
Modules/functors on the other hand do not cheat, you have to explicitly pass the required "extension" so the system remains fully parametric. So the difference is clear: with type classes the extension is passed implicitly which is why you can only sort integers in one direction. With modules you pass the instance in explicitly so you can have two orderings of integers because you have to actually say which one to use.
Shelby3's chosing by selecting instances by providing candidates in a particular context, and different instances in other contexts mixes both models, so the selection is partly implicit, and partly explicit. This is a bad idea because it makes it hard to reason about what is going on: when you look at a call site, you also have to look at the top of the file to see which instances are made available. The ability to reason about code is dependent on local knowledge. This is what referential transparency means and why purity and absence of side-effects is considered important in functional programming: you can look at a single line of code and know what a particular expression calculates without looking anywhere else. If the expression says sin(x) and you don't know what sin does you have a name you can then look for in the library. So the reasoning is not entirely local, but the non-local part of the reasoning is driven by something tangible you can refer to.
Similarly global variables in C are bad, because when you see a variable you have a name but you don't know which piece of code last assigned a value to it, you have to not only troll through the WHOLE program looking for assignments, you also have to figure out what the previous control flow might have been and calculate the possible values that the variable might contain. Its impossible! Not only can't a human do it, you can't really do it with a mechanical tool either.
So its is easier to reason with modules. They're better than type classes. Except for one problem: reasoning is easier because you explicitly name the module to be use but harder because your code is littered with detailed choices. If you have an "abstract concept" you want to make a whole set of choices at once, and call that a "context". And that is what type classes provide. You only get ONE choice for each concept, so in effect you are not programming, you are designing language extensions.
Ok so here is a partial implementation. In a function definition f you have passed in a type class Addable. This contains a method add. You now put add in your lookup context. Now you are binding the function code. You see add. You look for it, and find it in the context with a link to the add method of the type class dictionary for Addable. So you output the code Addable_parameter.add. Now, Addable_parameter is a parameter of the function. So at run time, you have called the add method of the instance argument of the typeclass Addable which has been passed in.
Since this is Javascript, the instance can contain more methods than just add, it can contain more than the type class Addable allows. You never call them so it doesn't matter inside the function.
So implementing type classes inside the function is easy, the problem now is how to pass a suitable (type checked) instance to the function. In other words when you call f (x,y) how do you know what to pass to f? Well you lookup f, and you see it requires a type class Addable with instance types, say int and float.
And there you start to have fun! How do you find Addable<int,float> instance? It's even harder if you require a non-monomorphic specialisation. It can be done as described earlier, but it is easier in Felix because there is no separate compilation to worry about, and so you never need any dictionaries at run time (the dictionaries only exist at compile time).
f(0, 1: ForwardOrder) f(0, 1: ReverseOrder)P.S. I think your idea of enforcing one implementation per data type is rubbish, because then I can't do the above.
We will need the above casts on typeclass bounds any way. I prefer the inference engine to force me to cast the argument always (when there is a function overload on that argument, to avoid inference weirdness) which tells me which argument is causing the boilerplate, than the alternative of writing boilerplate function names which doesn't tell me which argument the choice is being made on.
Anyway the important point to note is the datatype is modelling the type-class, not the integer. So you can pass as many dictionaries as you need. The
lessThandatatype was implemented on theInttype parameter and you can have as many datatypes as you want implemented forInts.
Excuse me, yes that is correct. So in answer to your original question:
Just forget type-classes exist and tell me what is wrong with this:
f(0, 1, forwardOrder) f(0, 1, reverseOrder)
What is wrong is you are forcing the caller to always specify the dictionary instead of optionally allowing the compiler to infer which dictionary to select. If the compiler instead understands the last argument to be optional and will infer it, then you essentially have typeclasses, except for the case where we want to select typeclasses in the where clause with type variables which are not the types of arguments.
Any way, none of that changes my claim that the general form of typeclasses should let me optionally select the implementation.
So @shelby3, you are arguing against type classes and for modules. I personally have no problem with that, they're easier to implement and more powerful: because modules can contain functions, functors with module parameters have both types and functions as parameters.
The only downside is that to pass them you have to name them, and you have to pass them explicitly every time. First class modules are powerful. With a JS implementation you may even be able to construct first class functors.
The main issue would be notation. Once you use modules, you have to refer to their functions with the module name prefixed, which makes infix operators, etc, difficult.
Take your pick ... or, if you want a language even more complex than Felix, do both :)
If you want implicit selection, you obviously get only one choice (type classes). If you want more than one choice you have to explicitly choose which one (modules).
@skaller wrote:
The only downside is that to pass them you have to name them, and you have to pass them explicitly every time
No I wrote "optional", which means when they aren't explicit then the dictionary will be selected by the compiler.
If you want implicit selection, you obviously get only one choice (type classes). If you want more than one choice you have to explicitly choose which one (modules).
There is another choice, which is explicit when you want to be and implicit when you don't want to be explicit. The import scoping and extends scoping helps you (see my example for using extends).