Thanks for the fix Jehan!
Here's a simple test program I wrote to check open recursion. Obviously, in the call to isEven on eo2 I'm expecting that the new isOdd will be called. Is that the expected behavior?
type
EvenOdd = object of TObject
method isEven(this: EvenOdd, n : int): bool
method isOdd(this: EvenOdd, n : int): bool
method isEven(this: EvenOdd, n : int): bool =
echo "isEven (this: EvenOdd, n : int):", $n
if n < 0:
result = isEven(this, -n)
elif n == 0:
result = true
elif n == 0:
result = false
else:
result = isOdd(this, n - 1)
method isOdd(this: EvenOdd, n : int): bool =
echo "isOdd(this: EvenOdd, n : int) :", $n
if n < 0:
result = isOdd(this, -n)
elif n == 0:
result = false
elif n == 1:
result = true
else:
result = isEven(this, n - 1)
var
eo : EvenOdd = EvenOdd()
echo "isOdd(eo, 16)=", $isOdd(eo, 16)
echo "isEven(eo, 24)=", $isEven(eo, 24)
type
EvenOdd2 = object of EvenOdd
method isOdd(this: EvenOdd2, n : int): bool
method isOdd(this: EvenOdd2, n : int): bool =
echo "isOdd(this: EvenOdd2, n : int) :", $n
if n < 0:
result = isOdd(this, -n)
else:
result = (n mod 2) == 1
var
eo2 : EvenOdd2 = EvenOdd2()
echo "isEven(eo2, 17)=", $isEven(eo2, 17)
This looks like a devirtualization bug to me. Looking at the generated code, the reason is that isEven() incorrectly calls the first isOdd() implementation rather than the method dispatcher. To be precise, there are two bugs, one in the compiler, one other in your code or the language spec:
It all starts with you using an object instead of ref object. That's like the difference between a T and T* in C++, and you can't really have polymorphism in the general case outside of reference types. So, when you pass a T to a method, even calling it this, it may have to get coerced to a subtype (emphasis on may, the implementation actually allows an implicit passing by reference – and does so, often enough), which then would lose type information. In practice, it doesn't quite work, which may actually lead to crashing bugs. In any event, that would also lead to type information being dropped in that eo2 could implicitly get coerced into an instance of EvenOdd.
The long and short of this is that you should always use ref object or ptr object for polymorphism, and this is a common enough problem that I think it may actually be a good idea to just remove it from the language (or at least spec the behavior out very precisely). For now, my recommendation is to not use object without ref or ptr for polymorphism; no matter what you think of it as a feature, the implementation is broken, and most people who want to use polymorphism want a ref object, anyway.
The bug in the compiler is that this also happens with ref object when it shouldn't.
Note that your example also showed that my proposed fix still has a bug in that it incorrectly leads to name mangling producing two functions with the same ID, so the patch still needs some work, alas.
Jehan It all starts with you using an object instead of ref object. That's like the difference between a T and T in C++, and you can't really have polymorphism in the general case outside of reference types.*
Good point. I do understand this, working mostly in Java/C++ and sometimes in D, and my first attempts used object refs.
The long and short of this is that you should always use ref object or ptr object for polymorphism, and this is a common enough problem that I think it may actually be a good idea to just remove it from the language (or at least spec the behavior out very precisely). ... most people who want to use polymorphism want a ref object, anyway.
Agreed.
Note that your example also showed that my proposed fix still has a bug in that it incorrectly leads to name mangling producing two functions with the same ID, so the patch still needs some work, alas.
Oh well, too bad. Glad you're on it though, and that I'm not in the weeds with my attempts. Hopefully you're worknig on HKTs too ;-).
Hopefully you're worknig on HKTs too
What's a HKT? (TMT = Too Many TLAs = Too Many Three-Letter Acronyms.)
Incidentally, the underlying problem is that methods simply haven't been used much, so they've also not been tested much outside of synthetic test cases. I think most serious Nim users so far have been working with the CLU/ML-like subsystem of the types (in particular, parametric polymorphism + variant types), and there hasn't been a whole lot of need for using multi-methods. So it's a good thing that somebody's actually using them in anger.
What's a HKT? (TMT = Too Many TLAs = Too Many Three-Letter Acronyms.)
Sorry. Being American, I love acronyms.
Higher Kinded Type, which is the acronym du jour, rather than the stuttering 'Template Template Parameter' which is the C++ equivalent. One spot where I'd like to see some nimprovement.
I'm actually not a great fan of OO. When I worked in anger using OCaml, I almost never used them. I'd likely use them even less now, since OCaml now has first class modules and the record system allows a bit more 'overloading'. It's an interesting bit of data that the Core library from Jane Street Capital (a large industrial user) doesn't use classes either. I'm pretty sure that my example and perhaps even my terminology (open recursion) is from OCaml.
If Nim dropped 'method' entirely, I'd still find it useful and interesting. However, if Nim has an object system I will kick the !@#$ out of the tires. I would guess (actually, it is known!) that there may be some issues around multimethods and encapsulation. As soon as my trivial example works, I'll try multimodule multimethods.
Yeah, I'm a bit on the fence with respect to higher kinded types. On the one hand, they have some useful applications; on the other hand, those useful applications are relatively narrow in scope, and may encourage an abuse of generics as a metaprogramming facility.
More importantly, remember that type parameters are, strictly speaking, type generators, and higher kinded types simply refer to type generators that themselves have parameters. There's a duplication with respect to what type templates could do, and the combination of generic modules and type templates would render higher kinded types largely superfluous.
There's two problems here, of course. One is that Nim doesn't support type templates (you can hack your way around it with macros, of course). The other is that while Nim technically has generic modules, using them is far from convenient. I've hacked an example implementation together here to show what a parameterized import syntax could look like:
import metamodules
implement vec[float3] as vec3f
implement vec[int2] as vec2i
type Mat3 = vec3f.Mat
type Vec3 = vec3f.Vec
const N = vec3f.Dimension
var m: Mat3
var v: Vec3 = [1.0, 2.0, 3.0]
for i in 1..N:
m[i][N-i+1] = 1.0
echo m
echo m*m
echo v
echo m*v
Why do I like generic modules? Because type parameters for functions and types can get very cumbersome very easily; they're useful for when you have really short parameter lists, but annotating every single procedure with a handful of type parameters can become cumbersome in the extreme. Imagine, for example, if you want to have a container parameterized by different comparison functions (case-sensitive vs. case-insensitive strings) and what that would look like.
I'll note finally that personally I like object-orientated programming (implemented properly). Parametric polymorphism and subtyping polymorphism complement each other, they do not replace each other (parametric polymorphism is about static dispatch, subtyping polymorphism about dynamic dispatch; OCaml functors offer the PP equivalent of inheritance for the static dispatch case). While variant types offer a limited form of subtyping polymorphism, they break when you want to expand the types that you apply actions to rather than the set of actions you want to apply to a given set of types (see the expression problem). OCaml's polymorphic variants allow you to work around that, but are arguably more headache-inducing than straight-up OOP, while still not giving you some benefits you get from objects.
Most crucially, object-oriented or object-based languages that take the "class = module" approach allow you to have multiple instances of a module, which can be very important when you want concurrency and mutable state. It is no coincidence that CLU and Eiffel were the first two programming languages to have a memory-safe concurrency model with mutable state and references. (Obviously, you can still screw it up, see, e.g., Java.)
I don't see how HKTs might encourage an abuse of generics as a metaprogramming facility. Could you explain? I'm also unsure with regards to your second paragraph about 'type templates'. Are you here using templates in the Nim sense of the term?
I also don't think Nim has generic modules in the same sense that, say OCaml or even Ada does. Types are paraemeterized not modules. OCaml's functors and Ada's packages provide strong typing guarantees; does your macro version do that?
I agree that OOP provides capabilities that PP doesn't. The EvenOdd example I gave shows one. It is true that in OCaml the most human understandable solution to the expression problem uses the class system, rather than an polymorphic variants and explicit fix operator (!). Nonetheless, the OCaml community doesn't use the 'O' part that much as far as I can see. In Rust, they still haven't settled on a means to do OOP; they eventually will but so far it hasn't hamstrung them so much.
I don't think Nim object types can solve the expression problem. Mutually recursive object types all need to be declared in the same type section. That precludes adding new cases without recompiling. I don't know how much of a problem that is in practice. As the tutorial says, that restriction enables faster compilation.
edit I was wrong in my statement in the last paragraph, and Nim handles the expression problem with great ease. I just wrote a few tests against the latest devel, and it was trivial to write the code.
First, note that pretty much all I'm saying here is conjecture, not even a firm belief. These are things I think may be worth exploring, not things that I even have strong evidence for might be beneficial.
By type templates I mean Nim templates that return types, yes.
With respect to generic modules, yes, my point is that while Nim doesn't have them, I think they may be a more promising solution rather than piggybacking ever more functionality on type parameters. My macro package is an attempt to play with them, not a serious implementation (as the README notes); it does typecheck the code, obviously, but doesn't allow you to declare signatures for modules (that's beyond the ken of a metaprogramming package). I'm not even sure if that's good or bad at the moment.
With respect to higher-kinded types, it's just that most of the actual use cases I see fall into fairly specific categories, most of which seem to be working around some limitation or another in the language (whatever the language in question is). While in theory the benefit would extend to library design, that's actually one of the rarer places where I'm seeing it being used (other than as a workaround for the absence of metaprogramming).
For what it's worth, I'm also not yet sure what to make of Nim's object types. When I'm talking about the benefits of OOP, I mean "in principle", not in this particular instance; I'm drawing on my experience with other object-oriented languages (such as Eiffel) here, not Nim's object model. You can add new cases without adding to an existing type section in Nim, though; the inheritance relation is pretty much required to be antisymmetric by definition, so that's not inherently a constraint, since the "same type section" restriction is only relevant for mutually recursive types.
Incidentally, the devel branch should now have several bugfixes with respect to method dispatch; the even-odd example seems to work for me at last.
Thanks for those bugfixes. I edited my previous message, simple test cases for the expression problem are dispatched handily by Nim. I imagine there'd be problems if the object types are truly mutually recursive, but you're right that the asymmetry of inheritance renders this a nonissue.
Have you seen http://caml.inria.fr/pub/papers/xleroy-modular_modules-jfp.pdf ?
I believe that parameterized modules are certainly useful. One of the OCaml programmers I worked with thought that OCaml's module system was overkill and didn't use it much. At the time I was coding OCaml I was used to Ada and I found the modules pretty light compared to Ada's packages.
I think the place to look for practical experience with HKTs is C++, where they're called template template parameters. I work with a large body of fairly old C++ (not even C++11 yet) so given that conservatism you can imagine that I don't see much of that. However, I might object slightly to your characterization of HKTs as a workaround for the absence of metaprogramming. I'd think rather that simulating HKTs in metaprogramming is making up for a deficiency in the core language genericity. I like having macros, but as a matter of taste I'd rather have core language genericity as powerful as possible, with HKTs, variadic generics, constant parameters. Basically, almost all of the power of C++ and D templates.
Nim's object system is unfamiliar to me too, but so far I like it. As with the rest of Nim, some more docs and 'best practices' would be helpful. But with each bug fix it becomes a lot easier to use.