Opened 6 years ago

Closed 6 years ago

Last modified 6 years ago

#18099 closed enhancement (fixed)

Prepare linear_code for inheritance

Reported by: dlucas Owned by:
Priority: major Milestone: sage-6.6
Component: coding theory Keywords: sd66
Cc: jsrn, ncohen Merged in:
Authors: David Lucas, Johan Sebastian Rosenkilde Nielsen Reviewers: Nathann Cohen, Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 196e395 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by dlucas)

For now, every family of linear code (eg: Hamming code) is a method which returns a LinearCode object. It would be nice to change this: every family of code should be an object. Besides, every linear codes needs to know its generator matrix to be constructed. This is fine for linear codes without a specific algebraic structure, but not for sub-families of linear codes. For instance, it is possible to encode & decode words in Reed-Solomon codes without the help of a generator matrix. With regards to this, the user should be free to build the generator matrix for sub-families of code (which can be both a time- and memory-consuming operation). This is also true for the dimension of a code (which can be long to compute for some sub-families).

However, some parameters (like the length of the code, or its base field) are mandatory to every linear code, and subfamilies. They need to work fine with the category framework as well.

We then propose the following design:

implement an abstract class , AbstractLinearCode, which will initialize parameters used in every linear code, and make linear codes properly interact as modules in the category framework in its constructor. Besides, as all methods that were previously in linear codes need to work for all subfamilies of codes, we propose to relocate them as methods of AbtractLinearCode. With this design, every linear code and subfamily will only need to inherit from this abstract class to get all the generic methods and parameters initialized.

Besides, linear codes get their base_ring method from their category. For better consistency, we propose to implement a base_field() method which will be specific to linear codes.

Change History (48)

comment:1 Changed 6 years ago by dlucas

  • Branch set to u/dlucas/prepare_linear_code_for_inheritance

comment:2 Changed 6 years ago by dlucas

  • Authors set to David Lucas
  • Commit set to bf70359e1dd818e8dfc066ad2efa4ea03e06144d
  • Status changed from new to needs_review

New commits:

4d7f14dNew method: _init_linear_code
bf70359New method: base_field

comment:3 Changed 6 years ago by jsrn

  • Description modified (diff)

comment:4 Changed 6 years ago by ncohen

  • Cc ncohen added

comment:5 Changed 6 years ago by ncohen

Helloooooooooooooooooooo !

Several comments:

  • I do not understand why you created a specific function _init_linear_code instead of writing what you need in the __init__ function. In particular the names __init__ and _init_linear_code do not indicate how their aims are different.
    • If you want to change the name of the function, could it mention categories explicitly? (Or is there a reason not to?)
    • If you decide to remove this function, please move the doctests that it contains to the __init__ method.
  • You say in the ticket's description that you add a base_ring method while you implement base_field. What is the correct version?
  • I do not understand why you implement this function while saying that it is 'inherited'.
    • If it is inherited, why do you need to implement it?
    • If it is *not* inherited, then shouldn't we fix that instead of implementing the function?
  • We usually type '::' at the end of the line. Is there any reason why you write your code this way?
    We now create a member of our newly made class
    ::
    

Note that writing our newly made class:: will appear in the HTML as our newly made class: (only one ':'). If you do not want to see this terminal ':' then a space is sufficient, e.g.: This sentence ends here. ::

Nathann

Last edited 6 years ago by ncohen (previous) (diff)

comment:6 Changed 6 years ago by ncohen

  • Status changed from needs_review to needs_info

comment:7 Changed 6 years ago by git

  • Commit changed from bf70359e1dd818e8dfc066ad2efa4ea03e06144d to a425a89873d194bfdff1add267502a8f84ca6e08

Branch pushed to git repo; I updated commit sha1. New commits:

a425a89Changed structure of file: now contains an abstract class AbstractLinearCode for linear codes

comment:8 Changed 6 years ago by dlucas

Okay then!

I changed the structure of the file: we now have an AbstractLinearCode class which has all methods that was previously in LinearCode. LinearCode now inherits from this new abstract class (and gets all its former methods that way). I fixed the :: stuff too.

David

comment:9 Changed 6 years ago by dlucas

  • Status changed from needs_info to needs_review

comment:10 follow-up: Changed 6 years ago by ncohen

  • Status changed from needs_review to needs_work

Helloooooooooooooooooooooo,

Several comments:

  • (superficial) The way you moved code around makes the commit much more difficult to read than it should. It is a good thing to quickly read the commits before you push them, as usually the reviewer has to "reverse-engineer" what you want to do from the diff file. If you are forced to move code around, it is better to do so in a specific commit which *only* moves the code without changing anything in it.

As a reviewer, we have to make sure that all changes are correct, and as moving code around appears to us as 1) remove the code 2) add the code we have to re-read and check all of it, even if it was a no-brainer change on your side.

  • I changed your toy example a bit so that the matrix is given as argument. I hope that you will not mind.
  • While modifying minimum_distance() and gens() you interfered with its caching mechanism: answers which used to be cached are now forgotten. Could you fix that?
  • The doctest you wrote for the abstract class takes a lot of time, and we try to not go over a couple of seconds if we can avoid it (even for long ones). As this one does not test a very fundamental feature, could you make it a bit faster by changing the figures?

Thanks,

I added a small commit at public/18099. The usual procedure is that, as I reviewed your changes, you can be the reviewer of mine. In particular, feel free to discuss/oppose any of the changes.

Nathann

comment:11 Changed 6 years ago by jsrn

Also, remember to change the description of the ticket to reflect what it actually does now.

comment:12 Changed 6 years ago by git

  • Commit changed from a425a89873d194bfdff1add267502a8f84ca6e08 to 8905552948a0896a46e587815cce539b6e60aae9

Branch pushed to git repo; I updated commit sha1. New commits:

3ac3d64Merge branch 'u/dlucas/prepare_linear_code_for_inheritance' of git://trac.sagemath.org/sage into prepare_linear_code_for_inheritance
3fb0f56trac #18099: Merged with rc2
f7a8d03trac #18099: unimportant change in a doctest
6587ad8Merge with public branch
357c4f6Fixed too long doctest, put cached_method decorator over minimum_distance() and gens() methods
8905552Minor changes to documentation

comment:13 Changed 6 years ago by dlucas

  • Description modified (diff)

comment:14 in reply to: ↑ 10 Changed 6 years ago by dlucas

Replying to ncohen:

Helloooooooooooooooooooooo,

Hello!

Several comments:

  • (superficial) The way you moved code around makes the commit much more difficult to read than it should. It is a good thing to quickly read the commits before you push them, as usually the reviewer has to "reverse-engineer" what you want to do from the diff file. If you are forced to move code around, it is better to do so in a specific commit which *only* moves the code without changing anything in it.

As a reviewer, we have to make sure that all changes are correct, and as moving code around appears to us as 1) remove the code 2) add the code we have to re-read and check all of it, even if it was a no-brainer change on your side.

Got it! Thanks for the advice :)

  • I changed your toy example a bit so that the matrix is given as argument. I hope that you will not mind.

Not at all. I kept it in the new version of the code.

  • While modifying minimum_distance() and gens() you interfered with its caching mechanism: answers which used to be cached are now forgotten. Could you fix that?

Done. These methods are now cached.

  • The doctest you wrote for the abstract class takes a lot of time, and we try to not go over a couple of seconds if we can avoid it (even for long ones). As this one does not test a very fundamental feature, could you make it a bit faster by changing the figures?

Sure. Considering I picked some random methods to illustrate the inheritance mechanism with a dummy class, I just replaced it by something faster.

David

comment:15 Changed 6 years ago by dlucas

  • Status changed from needs_work to needs_review

comment:16 follow-up: Changed 6 years ago by vdelecroix

Hello,

I just had a quick look.

  1. What is the point of having two classes AbstractLinearCode and LinearCode. I would naturally name LinearCode the one from which I need to inherit from. Why not LinearCode and LinearCode_generic instead?
  1. Why the ambient vector space is not part of the input of AbstractLinearCode?
  1. What is the difference between base_ring provided by the Module and base_field?
  1. Coud you include in the docstring of the former AbstractLinearCode:
    • the set of attributes that are provided by the class
    • what should be done to implement a linar code when inheriting from it

In particular, some methods of AbstractLinearCode assume the presence of the attribute ._generator_matrix (like __cmp__).

  1. Could you remove
    + # sage: C.minimum_distance_upper_bound() # optional (net connection)
    + # 3
    + # sage: C.minimum_distance_why() # optional (net connection)
    + # Ub(7,4) = 3 follows by the Griesmer bound.
    
  1. In the docstring of AbstractLinearCode replace from this abstract method. with from this abstract class..

Vincent

comment:17 Changed 6 years ago by vdelecroix

  • Status changed from needs_review to needs_work

comment:18 in reply to: ↑ 16 Changed 6 years ago by ncohen

Hello,

  1. What is the point of having two classes AbstractLinearCode and LinearCode. I would naturally name LinearCode the one from which I need to inherit from. Why not LinearCode and LinearCode_generic instead?

I am not sure that I totally understand your question, but I may be able to help a bit.

The class which is currently named "LinearCode?" should (to me) be named "LinearCodeFromMatrix?" in the code [1]. It is meant to represent a linear code *defined* from a matrix. On the other hand, they will have some code which will *not* be defined from a matrix [2]. Thus, I thought that it made sense to have a class defining methods which apply to all kinds of codes in some astract class (I don't care much what the name of that class is).

Nathann

P.S.: As usual, when we discuss things "live", important information is left out from the ticket's comments.

[1] At user level, I don't see anything wrong with having it aliased as "LinearCode?", as it is the easiest way for users to define a code.

[2] Like Reed-Solomon codes. They apparently have better ways to compute things than to work on a matrix.

comment:19 Changed 6 years ago by dlucas

  • Description modified (diff)

comment:20 Changed 6 years ago by dlucas

  • Description modified (diff)

comment:21 Changed 6 years ago by dlucas

Hello,

I updated the description of the ticket.

Regarding the naming problem : from the programmer's point of view, having a class named AbstractSomething makes sense (in my humble opinion) with regards to inheritance. Usually, if you see an abstract class of something you know that you need to inherit from this class when it comes to the implementation of something (or its subfamilies).

Regarding the name of what we call LinearCode, we think it's the right name for coding theorists. LinearCode_generic is not really clear. I'd prefer to avoid this idea of using aliases, but if you tell me it's a more Sage-consistent naming scheme, I'll take it.

Why the ambient vector space is not part of the input of AbstractLinearCode??

It is actually implied by the parameters: the ambient space is a vectorial space over the base field of the code and of dimension the length of the code. base_field and length are the two parameters in our abstract class constructor, so every code knows its ambient space. Having both bsae_field, length and ambient_space as class parameters is redundant. We chose to pick length and base_field (and thus build the ambient space from these parameters) but the inverse could make sense too. It's really a matter of taste here :)

What is the difference between base_ring provided by the Module and base_field?

We noticed that some classes in Sage (like for instance VectorSpace) have both base_ring and base_field methods implemented, the former coming from the category framework and the latter specifically made for the class, both returning the same result. We chose to follow that because we thought it was consistent with Sage to do so. If it's not, I can remove the base_field method!

Coud you include in the docstring of the former AbstractLinearCode?: the set of attributes that are provided by the class what should be done to implement a linar code when inheriting from it

In particular, some methods of AbstractLinearCode? assume the presence of the attribute ._generator_matrix (like __cmp__).

Sure, I'll do that. Thanks for noticing that in __cmp__, because it should not directly call the class parameter anymore but use the method generator_matrix() instead. My mistake.

Could you remove

    + # sage: C.minimum_distance_upper_bound() # optional (net connection)
    + # 3
    + # sage: C.minimum_distance_why() # optional (net connection)
    + # Ub(7,4) = 3 follows by the Griesmer bound.

There is some commented lines in the files of the coding part of Sage, along with some algorithms that could be more efficient. We definitely want to clean up the whole coding library, which means:

  • remove all these commented lines
  • remove some deprecation warnings which are more than one year old
  • enhance some algorithms and methods

If you agree, we would prefer to focus on integrated our new functionnalities into Sage for now, and once it is done clean up all the coding library based on what we noticed while working on the existing code, and on the new input we might get.

David

comment:22 Changed 6 years ago by git

  • Commit changed from 8905552948a0896a46e587815cce539b6e60aae9 to 7f667634d5f463ebc2cfb11ade42bb034d631402

Branch pushed to git repo; I updated commit sha1. New commits:

7f66763Fixed mistake in __cmp__ and changed docstring of AbstractLinearCode

comment:23 Changed 6 years ago by git

  • Commit changed from 7f667634d5f463ebc2cfb11ade42bb034d631402 to 1652d7c6f5dfc558d3f0b56882e2f51b7d82decb

Branch pushed to git repo; I updated commit sha1. New commits:

1652d7cSmall fixes in AbstractLinearCode docstring

comment:24 follow-up: Changed 6 years ago by vdelecroix

Replying to dlucas:

Hello,

Regarding the naming problem [...]

If you look around, there are very few AbstractXYZ. On the other hand, I do not have very strong feeling about that, so I let you decide.

Why the ambient vector space is not part of the input of AbstractLinearCode??

It is actually implied by the parameters: [...]

All right. That is at least clearer to me. Thanks for your explanation.

What is the difference between base_ring provided by the Module and base_field?

We noticed that some classes in Sage (like for instance VectorSpace) have both base_ring and base_field methods implemented, the former coming from the category framework and the latter specifically made for the class, both returning the same result. We chose to follow that because we thought it was consistent with Sage to do so. If it's not, I can remove the base_field method!

For vector space, you have

def base_field(self):
    ...
    return self.base_ring()

(see line 5144 of sage/modules/free_module.py). Why would you dupliacte the attribute in your class LinearCode? Note that I have nothing against a method base_field but you should get rid of the attribute _base_field.

Actually, one thing that I would find more natural is to inherit from FreeModule_submodule_field (from sage.modules.free_module) instead of simply Module. You will get for free many very useful methods (like ambient_space, a much better implementation of __contains__, etc). The drawback is that you need the generator matrix in the constructor. But I do not see why this would be so bad.

Could you remove

[...] If you agree, we would prefer to focus on integrated our new functionnalities into Sage for now, and once it is done clean up all the coding library based on what we noticed while working on the existing code, and on the new input we might get.

All right

Next:

  • It is very wrong to set
    Element = type(facade_for).an_element()
    
    The thing is that in the category mechanism, Element is just here to produce the attribute _element_class which is then used as the class for elements. Except in the case where the class is an extension class (i.e. a Cython class) those two classes are different. Moreover, if at some point you implement a LinearCode which is not a facade, you will need to set an attribute Element to it. In the current state, this attribute would be overriden in the __init__ by mentioned line.
  • This badly fails
    sage: sage.coding.linear_code.AbstractLinearCode(GF(3),2)
    <repr(<sage.coding.linear_code.AbstractLinearCode_with_category at 0x7f6867c61890>) failed: AttributeError: 'AbstractLinearCode_with_category' object has no attribute '_generator_matrix'>
    
    One way is to provide a generic is just to move the _repr_ in LinearCode to AbstractLinearCode.
  • the method AbstractLinearCode.generator_matrix is implemented as return self._generator_matrix. Why not
    def generator_matrix(self):
        raise NotImplementedError("This method must be set in subclasses")
    
    That way, the programmer knows where there is something wrong when he implements a new code. Another way to do is to use the decorator @abstract_method from sage.misc.abstract_method.
  • In the docstring of the class, you forgot to mention that the method generator_matrix must be implemented in subclasses.
  • the NOTE:: section in the docstring should be a .. NOTE:: section. Moreover, the lines are too large here (>110 characters and should be around 80).
  • the method zero is badly implemented. Instead, just do (without caching)
    def zero(self):
        return self.ambient_space().zero()
    
    Or if you really care about the non-facade cases
    def zero(self):
        if self.facade_for():
            return self(0)
        else:
            return self.ambient_space().zero()
    
  • Why did you set gens as a cached_method? Why do you check for a _gen attribute there? If you have an attribute _gen at some point the cached_method feature will just duplicate the fact that you already have an attribute that takes care of caching!!
  • In the constructor, don't you want to check that the argument base_field provided is actually a finite field? An easy way is
        if not base_field in Fields().Finite():
            raise ValueError("base_field (={}) must be a finite field".format(base_field))
    
    the argument length should also be checked and converted to the type you want to use (I guess either a Python int or a Sage Integer).

Enough for now...

Vincent

comment:25 in reply to: ↑ 24 ; follow-up: Changed 6 years ago by jsrn

Hi Vincent

It's awesome that you're being so thorough and giving feedback, but I think you're asking for too many things in this ticket. There's many things wrong with the current code, but for this ticket, we're not trying to fix it all. I'll reply to your comments below.

If you look around, there are very few AbstractXYZ. On the other hand, I do not have very strong feeling about that, so I let you decide.

Ok, we'll go with the abstract class then.

For vector space, you have ...

This implementation of base_field is indeed better, and we can kill _base_field.

Actually, one thing that I would find more natural is to inherit from FreeModule_submodule_field (from sage.modules.free_module) instead of simply Module...

  • It is very wrong to set
    Element = type(facade_for).an_element()
    

...

We didn't write this facade code; it's from #16644. We're not sufficiently familiar with the category framework to judge whether it's sensible or not. If it is not good as you say, it should of course be fixed, but I suggest doing that in another ticket since it implies various other cleanup (e.g. __contains__ and ambient_space as you mention). I therefore suggest adding base_field with the simple implementation above -- to fix the interface in this ticket - and then create a new ticket to fix the category stuff (which I hope you can further help us with).

  • This badly fails
    sage: sage.coding.linear_code.AbstractLinearCode(GF(3),2)
    <repr(<sage.coding.linear_code.AbstractLinearCode_with_category at 0x7f6867c61890>) failed: AttributeError: 'AbstractLinearCode_with_category' object has no attribute '_generator_matrix'>
    

It's supposed to fail: it's an abstract class, so you shouldn't instantiate it.

One way is to provide a generic is just to move the _repr_ in LinearCode to AbstractLinearCode.

The usual _repr_ should be in LinearCode, and I don't see a reason for defining AbstractLinearCode._repr_. I guess it could possibly be flagged with @abstract_method but that's largely a matter of taste. In this instance, I don't find it integral to the functionality of sub-classes that they have a _repr_, and @abstract_method is intended for flagging only essential-to-override methods.

  • the method AbstractLinearCode.generator_matrix is implemented as return self._generator_matrix. Why not
    def generator_matrix(self):
        raise NotImplementedError("This method must be set in subclasses")
    

The current implementation should indeed be in LinearCode. In AbstractLinearCode it should raise a NotImplementedError, though not with the message you suggest: mathematically, every linear code has a generator matrix (it has many), but from a programming point of view, one should not be forced to implement it for every code class.

We made this mistake in the current code because we're introducing a generic way to handle encoders in a ticket coming up. Encoders are linked to generator matrices, and this framework will override AbstractLinearCode.generator_matrix with a method which asks the "default" encoder for the generator matrix. In this sense, AbstractLinearCode.generator_matrix becomes a convenience function, and more or less no sub-class will ever need to override it.

  • In the docstring of the class, you forgot to mention that the method generator_matrix must be implemented in subclasses.

Subclasses don't need to. (sure, lot's of functions in AbstractLinearCode will throw a NotImplementedError with the above default implementation of generator_matrix, but that's ok.)

  • the NOTE:: section in the docstring should be a .. NOTE:: section. Moreover, the lines are too large here (>110 characters and should be around 80).

Ok. On a side-note, is the 80-character wrap really enforced everywhere? IMHO, it is archaic and very impractical to enforce, especially for doc-tests.

  • the method zero is badly implemented...

Lot's of stuff is badly implemented (and we know). But it's not the job of this ticket to fix everything in linear_code.py.

  • Why did you set gens as a cached_method? Why do you check for a _gen attribute there? If you have an attribute _gen at some point the cached_method feature will just duplicate the fact that you already have an attribute that takes care of caching!!

You're right, @cached_method should be removed.

  • In the constructor, don't you want to check that the argument base_field provided is actually a finite field? An easy way is
        if not base_field in Fields().Finite():
            raise ValueError("base_field (={}) must be a finite field".format(base_field))
    
    the argument length should also be checked and converted to the type you want to use (I guess either a Python int or a Sage Integer).

Note that such a check wasn't there before either (matrices can be over rings too). But the check makes sense so we can add it. Probably length should be cast to Python int, and then cast to Integer in the def length() method.

Last edited 6 years ago by jsrn (previous) (diff)

comment:26 in reply to: ↑ 25 Changed 6 years ago by vdelecroix

Hello Johan, hello David,

Replying to jsrn:

It's awesome that you're being so thorough and giving feedback, but I think you're asking for too many things in this ticket. There's many things wrong with the current code, but for this ticket, we're not trying to fix it all. I'll reply to your comments below.

No problem. I am just saying what I found wrong while reading the code. You are free to say "this is not for this ticket". But keep my remarks under your pillow for the next tickets.

You somehow ignore my most important request: inheritance from FreeModule_submodule_field. That would avoid implementing plenty of useless stuff like __contains__, cardinality, __iter__ and so on.

  • It is very wrong to set
    Element = type(facade_for).an_element()
    

...

[...]

What happens if you just get rid of that line? Category is a driven by error experimentation ;-)

  • This badly fails
    sage: sage.coding.linear_code.AbstractLinearCode(GF(3),2)
    <repr(<sage.coding.linear_code.AbstractLinearCode_with_category at 0x7f6867c61890>) failed: AttributeError: 'AbstractLinearCode_with_category' object has no attribute '_generator_matrix'>
    

It's supposed to fail: it's an abstract class, so you shouldn't instantiate it.

On the other hand the implementation uses the attribute _generator_matrix. Perhaps, you could just remove this _repr_ in AbstractLinearCode.

  • the method AbstractLinearCode.generator_matrix is implemented as return self._generator_matrix. Why not
    def generator_matrix(self):
        raise NotImplementedError("This method must be set in subclasses")
    

The current implementation should indeed be in LinearCode. In AbstractLinearCode it should raise a NotImplementedError, though not with the message you suggest: mathematically, every linear code has a generator matrix (it has many), but from a programming point of view, one should not be forced to implement it for every code class.

  • In the docstring of the class, you forgot to mention that the method generator_matrix must be implemented in subclasses.

Subclasses don't need to. (sure, lot's of functions in AbstractLinearCode will throw a NotImplementedError with the above default implementation of generator_matrix, but that's ok.)

The thing is that many methods in AbstractLinearCode will just fail if you do not implement the method generator_matrix (like gens, __iter__, information_set, is_permutation_automorphism, is_permutation_equivalent, ...). I agree that there are many generating matrices, but in order to define properly your subspace you need to tell Sage at least one. Perhaps not through the method generating_matrix though. This is of course related to the inheritance from FreeModule_submodule_field.

We made this mistake in the current code because we're introducing a generic way to handle encoders in a ticket coming up. [...]

I am not familiar with encoders (nor code theory by the way ;-).

  • the NOTE:: section in the docstring should be a .. NOTE:: section. Moreover, the lines are too large here (>110 characters and should be around 80).

Ok. On a side-note, is the 80-character wrap really enforced everywhere? IMHO, it is archaic and very impractical to enforce, especially for doc-tests.

It is not strictly requested. But the two dots before NOTE are.

That is great work to clean all of this... a bit tedious but definitely needed!

Best Vincent

comment:27 Changed 6 years ago by git

  • Commit changed from 1652d7c6f5dfc558d3f0b56882e2f51b7d82decb to 6fc5eb18f749e4ee36af0203e22d13a67e2a5fe4

Branch pushed to git repo; I updated commit sha1. New commits:

b287c3bGenerator matrix is now an abstract method
9b6d9b3Removed _gens attribute from linear code and changed gens() method accordingly
7f8558dRemoved _base_field parameter and changed base_field method
6fc5eb1Small fix to the documentation of AbstractLinearCode

comment:28 Changed 6 years ago by dlucas

Hello,

Here is what I did:

  • as Vincent suggested, generator_matrix() is now an abstract method (returns NotYetImplemented) in AbstractLinearCode. I set an implementation of it in LinearCode, and I changed the docstring of the abstract class accordingly.
  • as
    self.Element = type(facade_for.an_element())
    
    seemed harmless to removed (tested with the TestSuite().run method presented in the category tutorial) I killed it.
  • I actually removed _gens parameter from LinearCode and removed the related part in gens() method, so duplicated cache anymore.
  • However, I did not inherit from FreeModule_submodule_field because as far as I understand, it forces us to set the generator matrix as a class attribute, which is something we really do not want to do.

comment:29 Changed 6 years ago by jsrn

  • Branch changed from u/dlucas/prepare_linear_code_for_inheritance to u/jsrn/prepare_linear_code_for_inheritance

comment:30 Changed 6 years ago by git

  • Commit changed from 6fc5eb18f749e4ee36af0203e22d13a67e2a5fe4 to 4048b01c81b228326c7bbb1d977b67b8627f32da

Branch pushed to git repo; I updated commit sha1. New commits:

4048b01changed AbstractLinearCode.generator_matrix error message

comment:31 follow-up: Changed 6 years ago by jsrn

Hi Vincent and David,

I was not clear enough earlier, it seems. What I meant about the category stuff was that I don't think we should touch it in this ticket at all (not even removing the self.Element = ... thing. I for one have no idea what it might or might not break). It is a different kettle of fish and would require cleanup of several functions, etc. Also, as David mentions, it is really important for us that the generator matrix is not explicitly calculated except when asked for (possibly indirectly) by the user. If inheriting FreeModule_submodule_field would require us to explicitly calculate the generator matrix, I down-vote that solution. This whole discussion needs to be thought through properly in another ticket.

Relatedly, I find it perfectly acceptable that lots of functionality breaks in subclasses of AbstractLinearCode if those subclasses don't override generator_matrix; after all, those methods are default implementations which can and should be overridden in many cases. That being said, most code families *will* usually have a generator matrix implementation (based on encoders, after our future ticket on the matter).

David, you forgot to mention that you also fixed the NOTE thing, removed the _repr_, and reimplemented base_field() as suggested. I updated the doc-string for AbstractLinearCode with some small stuff, and I changed the error message in AbstractLinearCode.generator_matrix.

While doing so, I noticed the following: __cmp__ and __eq__ now breaks for AbstractLinearCode since they use generator_matrix which is not defined. That's of course unavoidable if the definition of code equality is that they describe the same sub-space. We have had a discussion on what comparison semantics makes most sense for linear codes, and we should bring this to Trac soon. Our consesus was that it should mean equality of sub-spaces. In this case, the NOTE in AbstractLinearCode should be removed. However, that's for later, I guess.

David, will you create a ticket for fixing up the category stuff, so we don't forget?

Best, Johan

comment:32 Changed 6 years ago by dlucas

Hello,

David, will you create a ticket for fixing up the category stuff, so we don't forget?

Done, see #18150 (very minimal description, but link to this ticket is provided)

comment:33 Changed 6 years ago by dlucas

  • Branch changed from u/jsrn/prepare_linear_code_for_inheritance to u/dlucas/prepare_linear_code_for_inheritance

comment:34 Changed 6 years ago by dlucas

  • Commit changed from 4048b01c81b228326c7bbb1d977b67b8627f32da to afc9fce253e82eb3f57041bb1ed3c0691e35881f

And I reinstated the Element ... line as we will discuss category-related stuff in #18150


New commits:

afc9fceReinstated self.Element = ... line in abstract class constructor

comment:35 Changed 6 years ago by vdelecroix

Hello,

when you are done with your corrections, you should switch the state to needs_review. That way, you have a chance that a reviewer comes back and the patch bot to test your ticket.

Vincent

comment:36 in reply to: ↑ 31 Changed 6 years ago by vdelecroix

  • Status changed from needs_work to needs_info

Replying to jsrn:

Also, as David mentions, it is really important for us that the generator matrix is not explicitly calculated except when asked for (possibly indirectly) by the user. If inheriting FreeModule_submodule_field would require us to explicitly calculate the generator matrix, I down-vote that solution. This whole discussion needs to be thought through properly in another ticket.

All right. Then, I do not understand why there are so much methods in AbstractLinearCode. If most of them need the generator_matrix why not put them in your current LinearCode class? I really do not like the fact that most methods of AbstractLinearCode just reimplement the logic of FreeModule_submodule_field using generator_matrix.

I would be happy if you briefly explain your reasons to avoid the construction of one generator matrix in the constructor.

sided note: there are some trailing whitespaces that needs to be removed.

Vincent

comment:37 Changed 6 years ago by dlucas

when you are done with your corrections, you should switch the state to needs_review. That way, you have a chance that a reviewer comes back and the patch bot to test your ticket.

I thought I did it. My bad.

I would be happy if you briefly explain your reasons to avoid the construction of one generator matrix in the constructor.

Sure. A generator matrix is not mandatory to perform operations of subfamilies of liner codes. For instance, with Reed-Solomon codes, you can encode and decode without using a generator matrix at all (in that case, you work with polynomials only). Compute a generator matrix can take some time for specific codes, and takes space in memory. If any code needs to compute a generator matrix in its constructor, that means you force the user to run a time- and memory-consuming every time he builds a code, even if he does not want to use it to encde and decode. According to us, building such a matrix should be a choice for the user as it is not a "free" computation. Of course, you need a generator for "generic" linear codes, that's why it is in LinearCode class constructor. But as it is not needed for subfamilies, we prefer not put it a a parameter of the abstract class constructor.

sided note: there are some trailing whitespaces that needs to be removed.

Ok, I'll do that

comment:38 Changed 6 years ago by git

  • Commit changed from afc9fce253e82eb3f57041bb1ed3c0691e35881f to 57a4944f9f18915fbc8904631d622aeb4619b306

Branch pushed to git repo; I updated commit sha1. New commits:

34d755fRemoved trailing whitespaces
834f6b0Merged with rc3
26e23ffAdded check on length parameter and cast to Sage Integer in Abstract class constructor
57a4944Merge with 6.7beta1

comment:39 Changed 6 years ago by dlucas

  • Status changed from needs_info to needs_review

comment:40 follow-up: Changed 6 years ago by vdelecroix

  • Status changed from needs_review to needs_info

Hello,

There still are trailing whitespaces!

What do you want to do with LinearCode in the future? Will it dispatch into subclasses. If not, you should add a comment about the implementation (telling that everything is computed from the generator_matrix).

In your children classes of AbstractLinearCode, will your elements always be vectors in a vector space? You talked about polynomials. Will polynomials be valid elements for some code or you will handle a conversion between them?

Vincent

comment:41 in reply to: ↑ 40 ; follow-up: Changed 6 years ago by jsrn

Hi Vincent

What do you want to do with LinearCode in the future? Will it dispatch into subclasses.

It is quite likely that LinearCode is a "final" class. I see little reason why one would sub-class it.

If not, you should add a comment about the implementation (telling that everything is computed from the generator_matrix).

Clearly that is implied by the fact that the generator matrix given as input to the constructor is all the information that the object has. The LinearCode could compute stuff from nothing else.

In your children classes of AbstractLinearCode, will your elements always be vectors in a vector space? You talked about polynomials. Will polynomials be valid elements for some code or you will handle a conversion between them?

All AbstractLinearCodes will be subspaces of GF(q)^n, so yes, its elements will always be vectors over some field. Usually, one talks of an "encoding" which is a bijection between the code and some other space called "the message space". The latter space is usually GF(q)^k where k is the dimension of the code, and the "encoding" bijection can be described by a linear mapping using a matrix. But it could also (for e.g. Reed-Solomon codes) be a k-dimensional space of polynomials.

We will handle this - in a later ticket - using a light-weight system of Encoder objects.

Best, Johan

comment:42 in reply to: ↑ 41 Changed 6 years ago by vdelecroix

Hi Johan, hi David,

Then just remove the trailing whitespaces and it will be good to go.

Vincent

comment:43 Changed 6 years ago by jsrn

Hi Vincent and David,

Actually, having reflected about it I think I now get Vincent's point on generator matrices. Perhaps the doc for the class LinearCode could be improved to something like

Linear codes over a finite field or finite ring, represented using a generator matrix.

This class should be used for arbitrary and unstructured linear codes. This means that basic operations on the code, such as the computation of the minimum distance, will use generic, slow algorithms.

If you are looking for constructing a code from a more specific family, see if the family has been implemented by investigating codes.<tab>. These more specific classes use properties particular for that family to allow faster algorithms, and could also have family-specific methods.

comment:44 Changed 6 years ago by git

  • Commit changed from 57a4944f9f18915fbc8904631d622aeb4619b306 to 196e3959586577954c138b966986535793e46953

Branch pushed to git repo; I updated commit sha1. New commits:

196e395Removed trailing whitespaces and changed LinearCode docstring

comment:45 Changed 6 years ago by dlucas

  • Status changed from needs_info to needs_review

I removed remaining trailing whitespaces (I hope I caught them all this time...) and I changed LinearCode docstring accordingly to comment 43.

comment:46 Changed 6 years ago by vdelecroix

  • Authors changed from David Lucas to David Lucas, Johan Nielsen
  • Reviewers set to Nathann Cohen, Vincent Delecroix
  • Status changed from needs_review to positive_review

It is fine with trailing whitespaces now. And all test pass.

Vincent

comment:47 Changed 6 years ago by vbraun

  • Branch changed from u/dlucas/prepare_linear_code_for_inheritance to 196e3959586577954c138b966986535793e46953
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:48 Changed 6 years ago by kcrisman

  • Authors changed from David Lucas, Johan Nielsen to David Lucas, Johan Sebastian Rosenkilde Nielsen
  • Commit 196e3959586577954c138b966986535793e46953 deleted
Note: See TracTickets for help on using tickets.