Prepare linear_code for inheritance

[sagetrac-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.

CC: @johanrosenkilde @nathanncohen

Component: coding theory

Keywords: sd66

Author: David Lucas, Johan Sebastian Rosenkilde Nielsen

Branch: 196e395

Reviewer: Nathann Cohen, Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/18099

[sagetrac-dlucas]

Branch: u/dlucas/prepare_linear_code_for_inheritance

[sagetrac-dlucas]

Author: David Lucas

[sagetrac-dlucas]

New commits:

4d7f14d	New method: _init_linear_code
bf70359	New method: base_field

[sagetrac-dlucas]

Commit: bf70359

[nathanncohen]

comment:5

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

[sagetrac-git]

Changed commit from bf70359 to a425a89

[sagetrac-git]

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

a425a89

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

[sagetrac-dlucas]

comment:8

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

[nathanncohen]

comment:10

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

[johanrosenkilde]

comment:11

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

[sagetrac-git]

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

3ac3d64	Merge branch 'u/dlucas/prepare_linear_code_for_inheritance' of git://trac.sagemath.org/sage into prepare_linear_code_for_inheritance
3fb0f56	trac #18099: Merged with rc2
f7a8d03	trac #18099: unimportant change in a doctest
6587ad8	Merge with public branch
357c4f6	Fixed too long doctest, put cached_method decorator over minimum_distance() and gens() methods
8905552	Minor changes to documentation

[sagetrac-git]

Changed commit from a425a89 to 8905552

[sagetrac-dlucas]

comment:14

Replying to @nathanncohen:

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

[videlec]

comment:16

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?

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

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

4. 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__).

5. 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.

6. In the docstring of AbstractLinearCode replace from this abstract method. with from this abstract class..

Vincent

[sagetrac-dlucas]

comment:37

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

[sagetrac-git]

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

34d755f	Removed trailing whitespaces
834f6b0	Merged with rc3
26e23ff	Added check on length parameter and cast to Sage Integer in Abstract class constructor
57a4944	Merge with 6.7beta1

[sagetrac-git]

Changed commit from afc9fce to 57a4944

[videlec]

comment:40

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

[johanrosenkilde]

comment:41

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

[videlec]

comment:42

Hi Johan, hi David,

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

Vincent

[johanrosenkilde]

comment:43

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.

[sagetrac-git]

Changed commit from 57a4944 to 196e395

[sagetrac-git]

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

196e395

Removed trailing whitespaces and changed LinearCode docstring

[sagetrac-dlucas]

comment:45

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

[videlec]

comment:46

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

Vincent

[videlec]

Reviewer: Nathann Cohen, Vincent Delecroix

[videlec]

Changed author from David Lucas to David Lucas, Johan Nielsen

[vbraun]

Changed branch from u/dlucas/prepare_linear_code_for_inheritance to 196e395

[kcrisman]

Changed commit from 196e395 to none

[kcrisman]

Changed author from David Lucas, Johan Nielsen to David Lucas, Johan Sebastian Rosenkilde Nielsen