Re: [julia-dev] Abstract Algebraic Structures

[Stefan Karpinski]

Multiple inheritance is issue #5. It's not what one would describe as simple to implement. It's also not entirely clear (to me at least) that it should necessarily be added to the language. I'm not against it, but it's a major complication and I view all complications by default with a vast amount of suspicion.

On Thu, Nov 21, 2013 at 11:40 PM, Al Rahimi <alra...@gmail.com> wrote:

I am trying to implement a hierarchy of abstract algebraic structures in Julia, mainly:

1-Semigroups

2-Monoids

3-Groups

4-Fields

and later vector spaces,Hilbert spaces etc.

The main feature which is missing from Julia  (and needed for implementation) is multiple inheritance. For example a Field  IS AN additive group plus A multiplicative group and that can not be expressed  in  Julia easily. Please respond if you have a work around or if you think Julia should support multiple inheritance. I know the language Slate supports multiple dispatch plus multiple inheritance. Can that model be used?  

Please view the preliminary implementation on Git:

https://github.com/alrahimi/algebra/

thanks

Al

[Raphael Sofaer]

We definitely wanted it for building Graphs.jl.  It would be very useful to be able to say that a graph is a VertexList and an EdgeList.

[Stefan Karpinski]

Isn't that an OR not and AND? Shouldn't a Graph be one or the other, not both? Or are you talking about it providing both a list of edges and a list of vertices?

[Viral Shah]

This is only tangentially relevant, but do see:

https://github.com/ViralBShah/SemiringAlgebra.jl

-viral

[Raphael Sofaer]

A graph might provide both a list of edges and a list of vertices, it might provide iteration over neighbors of a vertex, or edges leading out of a vertex, or edges leading into a vertex.  It would be nice to be able to represent the fact that any or all of those could be true for any graph in the type system.

[Francesco Bonazzi]

On Friday, November 22, 2013 5:40:52 AM UTC+1, Al Rahimi wrote:

I am trying to implement a hierarchy of abstract algebraic structures in Julia, mainly:

1-Semigroups

2-Monoids

3-Groups

4-Fields

and later vector spaces,Hilbert spaces etc.

The main feature which is missing from Julia  (and needed for implementation) is multiple inheritance. For example a Field  IS AN additive group plus A multiplicative group and that can not be expressed  in  Julia easily. Please respond if you have a work around or if you think Julia should support multiple inheritance. I know the language Slate supports multiple dispatch plus multiple inheritance. Can that model be used?  

I would advise not to use type inheritance to represent abstract mathematical relations. I would rather create a "relation" function and use multiple dispatching to set mathematical relations. Julia, if I'm correct, only allows abstract types to be inherited. But mathematical objects can be constructed by joining concrete types.

Otherwise you could try to use parametric types, but I can't fancy exactly how.

My suggestion is to use type inheritance for the user interaction code, while defining mathematical relations on abstract objects either through multiple dispatch or through hash maps.

Type inheritance corresponds to a group of limited logical operations on sets, representing mathematics requires something more complete.

[Rauli Ruohonen]

On Friday, November 22, 2013 10:41:58 PM UTC+2, Francesco Bonazzi wrote:

On Friday, November 22, 2013 5:40:52 AM UTC+1, Al Rahimi wrote:

I am trying to implement a hierarchy of abstract algebraic structures in Julia, mainly:

1-Semigroups

2-Monoids

3-Groups

4-Fields

and later vector spaces,Hilbert spaces etc.

Julia, if I'm correct, only allows abstract types to be inherited. But mathematical objects can be constructed by joining concrete types.

Mathematics is also very extensible, and one might want to add more abstract concepts, not just more concrete ones. Unless I've missed something, Julia also doesn't allow you to add new parent types. If you have a hierarchy with fields, groups, semigroups and monoids in a library, the user of that library will be in a bind if he wants to add the type magma and make it the parent type of monoid, even if monoid does not have a parent (= technically, has Any as its parent).

[Al Rahimi]

I think you're  right . You can not dynamically change the inheritance hierarchy but that is  less of a problem than lack of support for multiple inheritance.

By the way I am including Mamma as the  root of the hierarchy but I called it Binop (bad name should change it to Magma or Groupoid)

[Al Rahimi]

Thank you Viral.  In my design I have skipped Semirings and Rings and all variations and your module and the related paper shows that those also must be supported.My ultimate goal is to support a group of algorithms which are applicable to the widest set of algebraic structures . For example for graph shotest path and transitive closure algorithms can be implemented for semirings  in general (as in SemiringAlgebra module) or algorithm for fields which then applies to all fields instances (REal,Complex,Rational,quaternions,and other algebras)

[Al Rahimi]

I agree . In my case I want to be able to say a Field IS AN abelian additive group as well as a multiplicative  group with laws of distributional (addition over multiplication).

The language "Slate" which is drives from "Self" ,support both multiple inheritance and multiple dispatch

[Al Rahimi]

From issue #5 (2 years ago) Jeff stated that:

"The first one. Everything in the type system is pretty fragile, hard to modify without unintended consequences."

I think Julia has the potential to be the best dynamic language specially for applied as well as pure mathematical and scientific computing but for that to happen the foundation which is the type system has to be solid and flexible. Again may be the Slate language model can help:

http://slatelanguage.org/.

The following paper should help too:

Prototypes with Multiple Dispatch:An Expressive and Dynamic Object Model

Lee Salzman and Jonathan Aldrich

Carnegie Mellon University, Pittsburgh, PA 15217, USA,

lsal...@alumni.cmu.edu, jonathan...@cs.cmu.edu

I know this is complicated and it makes a great subject for a Phd or Master thesis  to design the type system as formally as possible

[Al Rahimi]

Good points, I have already started down that path . Please see the  preliminary implementation here:

https://github.com/alrahimi/algebra/

[Al Rahimi]

Yes that is right. I am also using abstract types and inheritance. Please  see the preliminary implementation at:

https://github.com/alrahimi/algebra/

[Stefan Karpinski]

"Models" are not really the problem here. How multiple inheritance should work is actually fairly straightforward. Implementing it efficiently and making it work with Julia's very sophisticated dispatch system is what's difficult. Given your enthusiasm for Slate, I'm curious why you're not using it for this sort of thing? Serious question – I'm not trolling, just wondering.

[Al Rahimi]

Ok I didn't know that efficient implementation was the major difficulty and I rather not have multiple inheritance than having it but loosing efficiency. I think Slate  can never compete with Julia in terms of efficiency so I have more enthusiasm for Julia than Slate.  I just thought Slate (reading the design papers) had a good model for multiple inheritance but the designer of slate didn't have efficiency as their first priority.

[Jason Morton]

Al,

Very late reply but here's what I did when I needed some kind of multiple inheritance for the exact same reason (implementing algebraic structures efficiently):

https://github.com/jasonmorton/Typeclass.jl/blob/master/test/test.jl