Opened 6 years ago

Closed 5 years ago

#20087 closed enhancement (fixed)

`__call__(message)` on a linear code or encoder should return a codeword.

Reported by: jsrn Owned by:
Priority: major Milestone: sage-7.6
Component: coding theory Keywords: beginner, rd3
Cc: dlucas, cpernet, jlavauzelle, danielaugot Merged in:
Authors: David Lucas Reviewers: Clément Pernet
Report Upstream: N/A Work issues:
Branch: 8ba64ee (Commits, GitHub, GitLab) Commit: 8ba64ee314241b1c905343eefa87dd694f13c8e0
Dependencies: Stopgaps:

Status badges

Description (last modified by jsrn)

If E is an Encoder for a LinearCode C, one can use E.encode(message), where message is in the appropriate space. E(message) should default to the same behaviour. So should C(message).

Be aware that the category framework specifies that C(c) = c if c in C. This needs to be handled.

Change History (37)

comment:1 Changed 6 years ago by dlucas

  • Branch set to u/dlucas/shortcut_to_encode

comment:2 Changed 6 years ago by git

  • Commit set to 49c448862fa2c32dc283b05fa7a749f064c6ec39

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

49c4488Also defined this shortcut in GRSEvaluationPolynomialEncoder

comment:3 Changed 6 years ago by dlucas

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

E(message) now defaults to E.encode(message). I added a few lines to the documentation of encode in encoder.py and in GRSEvaluationPolynomialEncoder to highlight this shortcut.

Setting this as needs_review.


New commits:

02c1f6dShortcut for method encode
49c4488Also defined this shortcut in GRSEvaluationPolynomialEncoder

comment:4 Changed 6 years ago by dlucas

  • Keywords beginner added

comment:5 Changed 6 years ago by git

  • Commit changed from 49c448862fa2c32dc283b05fa7a749f064c6ec39 to de7193894303ef9945d1f152b80cb46b9987affc

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

de71938Same shortcut for C(m)

comment:6 Changed 6 years ago by dlucas

I added the same mechanism with codes: let C be a code, and m an element from the message space of the encoder 'encoder'.

C(m, encoder_name='encoder') is now a shortcut to C.encode(m, encoder_name='encoder')

comment:7 Changed 6 years ago by dlucas

There's a doctest failing which indicates the test suite is broken for codes. That's because in the test suite, there's an idempotency test for element construction.

It picks c = C.an_element() and then tries C(c)... Which of course fails in our case as __call__ has been redefined as encode - and the input of encode cannot be an element of C.

comment:8 Changed 6 years ago by dlucas

  • Milestone changed from sage-7.1 to sage-duplicate/invalid/wontfix

Because of the above, which is related to the way linear codes are set in the category framework, it seems impossible to do the proposed improvement.

Setting this to invalid/won't fix.

comment:9 Changed 6 years ago by jsrn

  • Description modified (diff)
  • Milestone changed from sage-duplicate/invalid/wontfix to sage-7.2
  • Status changed from needs_review to needs_work
  • Summary changed from `E(message)` for a linear code encoder `E` should encode `message` to `__call__(message)` on a linear code or encoder should return a codeword.

This issue is not a show-stopper: instead of __call__ simply aliasing self.encode, it is a proper method which checks its input. If the input is a codeword, it returns that unchanged. If the input has the correct length of a message, return the encoded codeword, via self.encode. Otherwise, throw a ValueError.

Re-opening.

comment:10 Changed 6 years ago by git

  • Commit changed from de7193894303ef9945d1f152b80cb46b9987affc to 872f5d79d4dc260c64ff1512aefaf796d6bc15a8

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

4cd4b26Merge branch 'develop' into shortcut_to_encode
e8d7b58Merge branch 'develop' into shortcut_to_encode
872f5d7Updated __call__ method with a proper behaviour

comment:11 Changed 6 years ago by dlucas

  • Cc danielaugot added
  • Status changed from needs_work to needs_review

Done. Except for the ValueError. If the input is not a codeword, it passes it to encode which does the check. As encode knows the message space of the encoder to use, it returns a nice error message which specifies the expected input (e.g. "The value to encode must be in Vector space of dimension 4 over Finite Field of size 2").

Maybe leave this review for Daniel as he wanted to do it? I just Cc'd him on this ticket.

comment:12 follow-up: Changed 6 years ago by panda314

Hi, Maybe the check of whether the vector passed is a codeword or not can be done before passing it to the encode function. That way if a user means to pass a codeword rather than the message, and passed th wrong vector, he/she will be notified.

comment:13 in reply to: ↑ 12 Changed 6 years ago by jsrn

David, didn't you accidentally put the Encoder-related code on the GRS encoder? It should be on the abstract class Encoder. Also, the check if m in self should be if m in self.code() on the Encoder. And your doc-test there doesn't test that method.

Replying to panda314:

Hi, Maybe the check of whether the vector passed is a codeword or not can be done before passing it to the encode function. That way if a user means to pass a codeword rather than the message, and passed th wrong vector, he/she will be notified.

As far as I can see, the check in LinearCode *does* check for code membership before passing it to the encoder.

comment:14 Changed 6 years ago by git

  • Commit changed from 872f5d79d4dc260c64ff1512aefaf796d6bc15a8 to 92478fd38aa81b95324b2a3b4104416fcc068620

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

bb81375Removed duplicated __call__ method
92478fdBetter documentation and a new check for __call__

comment:15 follow-up: Changed 6 years ago by dlucas

Hello,

David, didn't you accidentally put the Encoder-related code on the GRS encoder?

Indeed, I removed it.

It should be on the abstract class Encoder.

Should it? IMHO, there's nothing elaborate to do for the encoder. If one creates a code C and an encoder E for C, and types E(c) for some c, if c does not belong to the message space of E it should fail. To me, the only purpose of an encoder is to transform elements of the message space into codeword. So if one passes an element which does not belong to the message space, failing makes sense.

As far as I can see, the check in LinearCode? *does* check for code membership before passing it to the encoder.

I think he meant if one tries to pass an element of the ambient space of the code which does not belong to the code. I added a check for that: as I cannot picture an encoder whose message space is the ambient space of the code, it makes sense to immediately reject vectors which are in the ambient space but not in the code, as it avoids calling encode and thus constructing an encoder for nothing.

comment:16 in reply to: ↑ 15 Changed 6 years ago by jsrn

Should it? IMHO, there's nothing elaborate to do for the encoder. If one creates a code C and an encoder E for C, and types E(c) for some c, if c does not belong to the message space of E it should fail. To me, the only purpose of an encoder is to transform elements of the message space into codeword. So if one passes an element which does not belong to the message space, failing makes sense.

Oh yeah, you're right. But this patch then still adds the alias Encoder.__call__ as Encoder.encode, I presume?

I think he meant if one tries to pass an element of the ambient space of the code which does not belong to the code. I added a check for that: as I cannot picture an encoder whose message space is the ambient space of the code, it makes sense to immediately reject vectors which are in the ambient space but not in the code, as it avoids calling encode and thus constructing an encoder for nothing.

Hm, makes sense. You have a typo in the error message though (is -> it)

comment:17 Changed 6 years ago by git

  • Commit changed from 92478fd38aa81b95324b2a3b4104416fcc068620 to 6b32cf00bc4edcbaf17654e5c3f9546914160140

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

f7f075eFixed typo in error message
6b32cf0__call__ has been added for an encoder in grs.py

comment:18 follow-up: Changed 6 years ago by dlucas

Oh yeah, you're right. But this patch then still adds the alias Encoder.call as Encoder.encode, I presume?

Indeed. I fixed that.

Hm, makes sense. You have a typo in the error message though (is -> it)

Oops. Fixed too.

comment:19 in reply to: ↑ 18 Changed 6 years ago by jsrn

Replying to dlucas:

Oh yeah, you're right. But this patch then still adds the alias Encoder.call as Encoder.encode, I presume?

Indeed. I fixed that.

You added it to GRS, not to Encoder...

comment:20 follow-up: Changed 6 years ago by dlucas

You added it to GRS, not to Encoder...

Err yes, because encode is overridden in the polynomial encoder for GRS codes. The alias is already added to encoder.py, and E(m) encodes m if possible.

comment:21 in reply to: ↑ 20 Changed 6 years ago by jsrn

Err yes, because encode is overridden in the polynomial encoder for GRS codes. The alias is already added to encoder.py, and E(m) encodes m if possible.

Ouch, that's a super-nasty trap! All encoders written in the future will fall into this!

I vote for *not* defining Encoder.__call__ as an alias, then, but instead rely on dynamic dispatch to avoid the trap:

    def __call__(self, m):
        return self.encode(m)

comment:22 Changed 6 years ago by git

  • Commit changed from 6b32cf00bc4edcbaf17654e5c3f9546914160140 to ce8d798c14b0e4e419a150cf4c14c5028354694f

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

ce8d798Rewrote __call__ in encoder.py, which is now more generic

comment:23 Changed 6 years ago by dlucas

I vote for *not* defining Encoder.__call__ as an alias, then, but instead rely on dynamic dispatch to avoid the trap

Yes, it's a good idea. Done in the last commit.

comment:24 Changed 6 years ago by panda314

are the changes compiling? The copy of this branch is not compiling on my local pc (new to sage, am i missing something?). Here's the error: InternalError?: Internal compiler error: 'cysignals/signals.pxi' not found

Detailed message is,

Traceback (most recent call last):

File "setup.py", line 590, in <module>

run_cythonize()

File "setup.py", line 582, in run_cythonize

'profile': profile,

File "/home/panda/sage/local/lib/python2.7/site-packages/Cython-0.23.3-py2.7-linux-x86_64.egg/Cython/Build/Dependencies.py", line 758, in cythonize

aliases=aliases)

File "/home/panda/sage/local/lib/python2.7/site-packages/Cython-0.23.3-py2.7-linux-x86_64.egg/Cython/Build/Dependencies.py", line 664, in create_extension_list

kwds = deps.distutils_info(file, aliases, base).values

File "/home/panda/sage/local/lib/python2.7/site-packages/Cython-0.23.3-py2.7-linux-x86_64.egg/Cython/Build/Dependencies.py", line 564, in distutils_info

return (self.transitive_merge(filename, self.distutils_info0, DistutilsInfo.merge)

File "/home/panda/sage/local/lib/python2.7/site-packages/Cython-0.23.3-py2.7-linux-x86_64.egg/Cython/Build/Dependencies.py", line 574, in transitive_merge

node, extract, merge, seen, {}, self.cimported_files)![0]

File "/home/panda/sage/local/lib/python2.7/site-packages/Cython-0.23.3-py2.7-linux-x86_64.egg/Cython/Build/Dependencies.py", line 579, in transitive_merge_helper

deps = extract(node)

File "/home/panda/sage/local/lib/python2.7/site-packages/Cython-0.23.3-py2.7-linux-x86_64.egg/Cython/Build/Dependencies.py", line 555, in distutils_info0

externs = self.cimports_and_externs(filename)![1]

File "/home/panda/sage/local/lib/python2.7/site-packages/Cython-0.23.3-py2.7-linux-x86_64.egg/Cython/Utils.py", line 43, in wrapper

res = cache[args] = f(self, *args)

File "/home/panda/sage/local/lib/python2.7/site-packages/Cython-0.23.3-py2.7-linux-x86_64.egg/Cython/Build/Dependencies.py", line 465, in cimports_and_externs

for include in self.included_files(filename):

File "/home/panda/sage/local/lib/python2.7/site-packages/Cython-0.23.3-py2.7-linux-x86_64.egg/Cython/Utils.py", line 43, in wrapper

res = cache[args] = f(self, *args)

File "/home/panda/sage/local/lib/python2.7/site-packages/Cython-0.23.3-py2.7-linux-x86_64.egg/Cython/Build/Dependencies.py", line 448, in included_files

include_path = self.context.find_include_file(include, None)

File "/home/panda/sage/local/lib/python2.7/site-packages/Cython-0.23.3-py2.7-linux-x86_64.egg/Cython/Compiler/Main.py", line 274, in find_include_file

error(pos, "'%s' not found" % filename)

File "/home/panda/sage/local/lib/python2.7/site-packages/Cython-0.23.3-py2.7-linux-x86_64.egg/Cython/Compiler/Errors.py", line 177, in error

raise InternalError(message)

InternalError: Internal compiler error: 'cysignals/signals.pxi' not found Error building the Sage library make: * [sage] Error 1

comment:25 Changed 6 years ago by dlucas

It's compiling on my side. According to the error report you sent, a file is missing on your side. I guess you'll have to download Sage again and recompile it...

comment:26 Changed 5 years ago by danielaugot

  • Branch changed from u/dlucas/shortcut_to_encode to u/danielaugot/shortcut_to_encode

comment:27 Changed 5 years ago by danielaugot

  • Commit changed from ce8d798c14b0e4e419a150cf4c14c5028354694f to 2fa1f175383fcf4ffd33166ce07d36b0db5c4a97

I used the terminology "ambient space" in the doc string, to avoid being specific in details. Daniel


New commits:

2fa1f17Better doc string for __call__

comment:28 Changed 5 years ago by git

  • Commit changed from 2fa1f175383fcf4ffd33166ce07d36b0db5c4a97 to f25413e058c81e9dbaafa60dfbccc9876301d42d

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

f25413eMerge branch 'u/danielaugot/shortcut_to_encode' of git://trac.sagemath.org/sage into 20087/shortcut_to_encode

comment:29 Changed 5 years ago by git

  • Commit changed from f25413e058c81e9dbaafa60dfbccc9876301d42d to 3ec380cecd6657237c739a1baddeef0ee1126bb4

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

3ec380cfixed the docstring to match the ErrorValue

comment:30 Changed 5 years ago by git

  • Commit changed from 3ec380cecd6657237c739a1baddeef0ee1126bb4 to 1fe5d5bcdb083e80d7b09122a5d021a83dbfa639

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

1fe5d5beasier to understand control structure using if-then-else

comment:31 Changed 5 years ago by jsrn

  • Branch changed from u/danielaugot/shortcut_to_encode to u/jsrn/shortcut_to_encode

comment:32 Changed 5 years ago by jsrn

I mistakenly pushed another branch on top of this one. I've reverted it now -- sorry for the noise.

comment:33 Changed 5 years ago by cpernet

  • Keywords rd3 added
  • Reviewers set to Clément Pernet

Doc string of the __call__ method of encoder (encoder.py:187) should test whether E(p) works not E.encode(p).

comment:34 Changed 5 years ago by cpernet

  • Branch changed from u/jsrn/shortcut_to_encode to u/cpernet/shortcut_to_encode

comment:35 Changed 5 years ago by git

  • Commit changed from 1fe5d5bcdb083e80d7b09122a5d021a83dbfa639 to 8ba64ee314241b1c905343eefa87dd694f13c8e0

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

8ba64eeadd missing doctest for C(word)

comment:36 Changed 5 years ago by cpernet

  • Milestone changed from sage-7.2 to sage-7.6
  • Status changed from needs_review to positive_review

It's all good, after the two minor docstring edits that I've pushed to the ticket. Positive review.

comment:37 Changed 5 years ago by vbraun

  • Branch changed from u/cpernet/shortcut_to_encode to 8ba64ee314241b1c905343eefa87dd694f13c8e0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.