Opened 11 years ago
Last modified 5 months ago
#12224 needs_work enhancement
Language as parent / Word as element
Reported by: | Vincent Delecroix | Owned by: | Vincent Delecroix |
---|---|---|---|
Priority: | major | Milestone: | sage-wishlist |
Component: | combinatorics | Keywords: | word, language, symbolic dynamics |
Cc: | Štěpán Starosta, Sébastien Labbé, Thierry Monteil, Nathann Cohen, Timo Jolivet, Jeremias Epperlein | Merged in: | |
Authors: | Vincent Delecroix | Reviewers: | Sébastien Labbé |
Report Upstream: | N/A | Work issues: | pickling, doctests errors, revert changes on repr, ... |
Branch: | Commit: | ||
Dependencies: | #8920, #12230, #12518, #13778, #13956, #13957, #13801 | Stopgaps: |
Description (last modified by )
This ticket is a prerequisite to further development in the combinatorics of words and symbolic dynamical systems (adic language, SFT, ...). It concerns the implementation of a class "Language" (= graded set of words) as a Parent and a class "Word" as Element.
Three categories are created: Languages, FactorialLanguages and Shifts that gather several methods of finite and infinite words. For speed reason there are base Cython classes for
- finite word (in sage.combinat.words.finite_word)
- infinite word (in sage.combinat.words.infinite_word)
- language (in sage.combinat.languages.language)
Every implementation must inherit from the class above (it is check in the TestSuite? of the related categories).
The previous code of Word is dispatched between the ElementMethods of the category and the Cython class FiniteWord. The choice has been made for sake of optimization.
Old pre-git instructions to import the code. To import and apply all patches do
cd SAGE_ROOT/devel/YOUR_BRANCH hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/8920/trac_8920-alphabet.patch hg qpush hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/12466/trac_12466-ss.patch hg qpush hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/12230/trac_12230-growing_letters-ss.patch hg qpush hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/12230/trac_12230-growing_letters-review-vd.patch hg qpush hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/13801/trac_13801-fix_facade_initialisation-vd.patch hg qpush hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/13956/trac_13956-shift_argument.patch hg qpush hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/13957/trac_13957-catch_value_error.patch hg qpush hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/12224/trac_12224-language.patch hg qpush
Attachments (1)
Change History (36)
comment:1 Changed 11 years ago by
Description: | modified (diff) |
---|
comment:2 Changed 11 years ago by
Dependencies: | → #10193 |
---|---|
Description: | modified (diff) |
comment:3 Changed 11 years ago by
Cc: | Nathann Cohen added |
---|
comment:4 Changed 10 years ago by
Dependencies: | #10193 → #8920, #10193 |
---|
comment:5 Changed 10 years ago by
Dependencies: | #8920, #10193 → #8920, #10193, #13803, #13778 |
---|
comment:6 Changed 10 years ago by
Dependencies: | #8920, #10193, #13803, #13778 → #8920, #13778, #13956 |
---|
comment:7 Changed 10 years ago by
Dependencies: | #8920, #13778, #13956 → #8920, #13778, #13956, #13957 |
---|---|
Description: | modified (diff) |
comment:8 Changed 10 years ago by
Dependencies: | #8920, #13778, #13956, #13957 → #8920, #12230, #12518, #13778, #13956, #13957 |
---|
Changed 10 years ago by
Attachment: | trac_12224-language.patch added |
---|
comment:9 Changed 10 years ago by
comment:10 follow-up: 23 Changed 10 years ago by
I started the review. Here is a first bunch of comments.
- Goal of the ticket: Categories in
sage/combinat/words
library. The goal of this patch reimplements the code structure ofsage/combinat/words
using categories. It also adds classes for languages which is a good thing that I would need for my own research. It touches other files outside of this folder. It also depends on some particular tickets fixing bugs in Cython (#13957) and other patches that apply on similar files which do not commute with this huge patch. Moreover since it is a huge patch touching many files, it prevents any user/developper to change any code insage/combinat/words
without creating conflicts. So I hope this will not take forever to get reviewed because meanwhile it prevents the evolution of the actual code.
- Content of the patch. It is a huge patch (1.3MG). It modifies 40 files, add 27 files and removes 6 files (see detailed list below). It is hard for any reviewer to make sure he doesn't miss a problem possibly added by the patch. Is there a way to cut the patch in different chunks (tickets) which could make it more easy to get it into Sage because easier for reviewers?
~/Applications/sage-5.6.rc0/devel/sage-language/sage/combinat/words $ hg qtop trac_12224-language-vd.patch ~/Applications/sage-5.6.rc0/devel/sage-language/sage/combinat/words $ hg qst M doc/en/reference/categories.rst M doc/en/reference/combinat/words.rst M module_list.py M sage/all.py M sage/categories/algebras.py M sage/categories/algebras_with_basis.py M sage/categories/all.py M sage/categories/examples/algebras_with_basis.py M sage/categories/modules_with_basis.py M sage/categories/primer.py M sage/categories/rings.py M sage/categories/sets_cat.py M sage/combinat/all.py M sage/combinat/debruijn_sequence.pyx M sage/combinat/e_one_star.py M sage/combinat/free_module.py M sage/combinat/iet/constructors.py M sage/combinat/iet/labelled.py M sage/combinat/iet/reduced.py M sage/combinat/lyndon_word.py M sage/combinat/ribbon.py M sage/combinat/ribbon_tableau.py M sage/combinat/sf/ns_macdonald.py M sage/combinat/skew_tableau.py M sage/combinat/tableau.py M sage/combinat/words/__init__.py M sage/combinat/words/all.py M sage/combinat/words/alphabet.py M sage/combinat/words/morphism.py M sage/combinat/words/notes/history.txt M sage/combinat/words/paths.py M sage/combinat/words/shuffle_product.py M sage/combinat/words/suffix_trees.py M sage/combinat/words/word.py M sage/combinat/words/word_datatypes.pyx M sage/combinat/words/word_generators.py M sage/combinat/words/words.py M sage/graphs/digraph_generators.py M sage/sets/disjoint_set.pyx M setup.py A sage/categories/examples/languages.py A sage/categories/factorial_languages.py A sage/categories/languages.py A sage/categories/shifts.py A sage/combinat/languages/__init__.py A sage/combinat/languages/all.py A sage/combinat/languages/balanced_languages.py A sage/combinat/languages/base_class.py A sage/combinat/languages/finite_word_language.py A sage/combinat/languages/generators.py A sage/combinat/languages/language.pxd A sage/combinat/languages/language.pyx A sage/combinat/words/finite_word.pxd A sage/combinat/words/finite_word.pyx A sage/combinat/words/infinite_word.pxd A sage/combinat/words/infinite_word.pyx A sage/combinat/words/lazy_word.py A sage/combinat/words/maps.py A sage/combinat/words/notes/categorification.txt A sage/combinat/words/word_datatypes.pxd A sage/combinat/words/word_deprecation.py A sage/combinat/words/word_integer.py A sage/dynamics/__init__.py A sage/dynamics/all.py A sage/dynamics/symbolic/__init__.py A sage/dynamics/symbolic/all.py A sage/dynamics/symbolic/full_shift.py R sage/combinat/words/abstract_word.py R sage/combinat/words/finite_word.py R sage/combinat/words/infinite_word.py R sage/combinat/words/notes/word_inheritance_howto.txt R sage/combinat/words/word_infinite_datatypes.py R sage/combinat/words/word_options.py
- Reject on tableau file. The actual path creates a reject on the tableau file (I am still using the svn directory for the patches. I will test the patch from the ticket instead soon. Maybe that's the reason for the reject.) :
10 slabbe@pol ~/Applications/sage-5.6.rc0/devel/sage-language $ hg qpush -a applying trac_12466-ss.patch applying trac_12230-growing_letters-ss.patch applying trac_12230-growing_letters-review-vd.patch applying trac_13801-fix_facade_initialisation-vd.patch applying trac_8920-alphabet-vd.patch applying trac_13803-limits.patch applying trac_10962-pickle_set_pythontype.patch applying trac_13956-shift_argument.patch applying trac_13957-catch_value_error.patch applying trac_12224-language-vd.patch patching file sage/combinat/tableau.py Hunk #2 FAILED at 434 Hunk #4 FAILED at 584 Hunk #5 FAILED at 2070 3 out of 5 hunks FAILED -- saving rejects to file sage/combinat/tableau.py.rej patch failed, unable to continue (try -v) patch failed, rejects left in working dir errors during apply, please fix and refresh trac_12224-language-vd.patch
- Few broken doctests. Here are some testing errors I get on the my machine as well as on sage.math. Note that I tested only
sage/combinat
folder on my machine. This shows that some doctest are machine dependant (32bit vs 64 bits, ordering of string and int which depends on the machine : 'a'<9 vs 'a'>9 for cmp). Also for one of the doctest,352
can be replaced by...
to avoid future problem with lines added before. More precisely,
The output of
sage -t sage-5.6.rc0/devel/sage-language/sage/combinat/*
run on my machine (32bit) which was first pasted here is now available here : http://sage.math.washington.edu/home/slabbe/trac_12224/bullet_4.txt.
The output of
sage -t sage-5.6.rc1/devel/sage-12224/sage/*
run on sage.math is here : http://sage.math.washington.edu/home/slabbe/sage-5.6.rc1/testing_12224.txt.
- Testing the sage-main files. I am interested in knowing whether my own code will continue to work after this ticket get merged. Eventually, I will test my own code during this review. But for now I did only one test : I check whether the doctests defined in the
sage-main
branchsage-5.6.rc0
still pass or not. I get 618 failures only forfinite_word.py
file. Some of them are__repr__
modifications that I can accept. But there are a lots of methods that do not exist anymore (maybe it is easy to fix?).
The output of
sage -t sage-5.6.rc0/devel/sage-main/sage/combinat/*
run on my machine which was first pasted here is now available here: http://sage.math.washington.edu/home/slabbe/trac_12224/bullet_5.txt.
The output of
sage -t sage-5.6.rc1/devel/sage-main/sage/*
run on sage.math is here : http://sage.math.washington.edu/home/slabbe/sage-5.6.rc1/testing_12224_on_sage-main.txt.
comment:13 Changed 10 years ago by
- Question. If I understand correctly, the actual ticket does not depend on the following patches :
trac_13801-fix_facade_initialisation-vd.patch trac_13803-limits.patch trac_10962-pickle_set_pythontype.patch
Am I right?
comment:14 Changed 10 years ago by
3 (bis). I tested on sage-5.6.rc1 with the following tickets, and I still get the reject with the tableau file :
~/sage-5.6.rc1/devel/sage-12224$ hg qapplied trac_8920-alphabet.patch trac_12466-ss.patch trac_12230-growing_letters-ss.patch trac_12230-growing_letters-review-vd.patch trac_13956-shift_argument.patch trac_13957-catch_value_error.patch ~/sage-5.6.rc1/devel/sage-12224$ hg qpush applying trac_12224-language.patch patching file sage/combinat/tableau.py Hunk #2 FAILED at 434 Hunk #4 FAILED at 584 Hunk #5 FAILED at 2070 3 out of 5 hunks FAILED -- saving rejects to file sage/combinat/tableau.py.rej patch failed, unable to continue (try -v) patch failed, rejects left in working dir errors during apply, please fix and refresh trac_12224-language.patch
Moreover, with these tickets applied, sage does not start :
slabbe@sage:~/sage-5.6.rc1/devel/sage-12224$ ../../sage ---------------------------------------------------------------------- | Sage Version 5.6.rc1, Release Date: 2013-01-18 | | Type "notebook()" for the browser-based notebook interface. | | Type "help()" for help. | ---------------------------------------------------------------------- ********************************************************************** * * * Warning: this is a prerelease version, and it may be unstable. * * * ********************************************************************** --------------------------------------------------------------------------- AttributeError Traceback (most recent call last) [...] /home/slabbe/sage-5.6.rc1/local/lib/python2.7/site-packages/sage/categories/category.pyc in <genexpr>((cat,)) 144 result = () 145 for category in categories: --> 146 if any(cat.is_subcategory(category) for cat in result): 147 continue 148 result = tuple( cat for cat in result if not category.is_subcategory(cat) ) + (category,) AttributeError: 'tuple' object has no attribute 'is_subcategory' Error importing ipy_profile_sage - perhaps you should run %upgrade? WARNING: Loading of ipy_profile_sage failed. sage: 1+1 --------------------------------------------------------------------------- NameError Traceback (most recent call last) /home/slabbe/sage-5.6.rc1/devel/sage-12224/<ipython console> in <module>() NameError: name 'Integer' is not defined
One need to add ticket #13801 as dependency.
comment:15 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:16 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:17 Changed 10 years ago by
4 (second bis). I tested the doctests of the whole sage library when applying the following 8 patches on sage-5.6.rc1.
trac_8920-alphabet.patch trac_12466-ss.patch trac_12230-growing_letters-ss.patch trac_12230-growing_letters-review-vd.patch trac_13801-fix_facade_initialisation-vd.patch trac_13956-shift_argument.patch trac_13957-catch_value_error.patch trac_12224-language.patch
I get errors on the following files. The complete log is here.
The following tests failed: sage -t devel/sage-12224/sage/structure/sage_object.pyx # 1 doctests failed sage -t devel/sage-12224/sage/combinat/tableau_tuple.py # 2 doctests failed sage -t devel/sage-12224/sage/categories/languages.py # 3 doctests failed sage -t devel/sage-12224/sage/combinat/tableau.py # 3 doctests failed sage -t devel/sage-12224/sage/combinat/languages/finite_word_language.py # 3 doctests failed sage -t devel/sage-12224/sage/combinat/words/word_deprecation.py # 1 doctests failed sage -t devel/sage-12224/sage/combinat/words/word.py # 1 doctests failed sage -t devel/sage-12224/sage/combinat/words/maps.py # 22 doctests failed ---------------------------------------------------------------------- Timings have been updated. Total time for all tests: 4281.6 seconds
Of course, all of these should be fixed. The first file indicates there are issues with pickling.
comment:18 Changed 10 years ago by
Dependencies: | #8920, #12230, #12518, #13778, #13956, #13957 → #8920, #12230, #12518, #13778, #13956, #13957, #13801 |
---|
comment:19 Changed 10 years ago by
Description: | modified (diff) |
---|
comment:20 Changed 10 years ago by
5 (second bis). Still to understand if my code will still work after this ticket, I tested the doctests of the sage-main of sage-5.6-rc1 when applying the following 8 patches on sage-5.6.rc1.
trac_8920-alphabet.patch trac_12466-ss.patch trac_12230-growing_letters-ss.patch trac_12230-growing_letters-review-vd.patch trac_13801-fix_facade_initialisation-vd.patch trac_13956-shift_argument.patch trac_13957-catch_value_error.patch trac_12224-language.patch
It appears that a lot of doctests are failing. The complete log is here.
One observation is that the __repr__
and __str__
should not be changed in this ticket to help the reviewer. There is enough doctests failing already...
The following tests failed: sage -t devel/sage-main/sage/structure/sage_object.pyx # 1 doctests failed sage -t devel/sage-main/sage/plot/plot.py # Time out sage -t devel/sage-main/sage/combinat/words/finite_word.py # 618 doctests failed sage -t devel/sage-main/sage/combinat/tableau_tuple.py # 2 doctests failed sage -t devel/sage-main/sage/tests/cmdline.py # Time out sage -t devel/sage-main/sage/combinat/words/paths.py # 114 doctests failed sage -t devel/sage-main/sage/combinat/e_one_star.py # 6 doctests failed sage -t devel/sage-main/sage/combinat/skew_tableau.py # 6 doctests failed sage -t devel/sage-main/sage/combinat/tableau.py # 7 doctests failed sage -t devel/sage-main/sage/categories/rings.py # 1 doctests failed sage -t devel/sage-main/sage/categories/primer.py # 2 doctests failed sage -t devel/sage-main/sage/combinat/words/suffix_trees.py # 45 doctests failed sage -t devel/sage-main/sage/graphs/digraph_generators.py # 1 doctests failed sage -t devel/sage-main/sage/combinat/ribbon.py # 6 doctests failed sage -t devel/sage-main/sage/combinat/iet/reduced.py # 2 doctests failed sage -t devel/sage-main/sage/combinat/free_module.py # 2 doctests failed sage -t devel/sage-main/sage/combinat/words/word_generators.py # Time out sage -t devel/sage-main/sage/combinat/sf/ns_macdonald.py # 1 doctests failed sage -t devel/sage-main/sage/combinat/words/morphism.py # Time out sage -t devel/sage-main/sage/categories/algebras.py # 6 doctests failed sage -t devel/sage-main/sage/categories/sets_cat.py # 1 doctests failed sage -t devel/sage-main/sage/sets/integer_range.py # 1 doctests failed sage -t devel/sage-main/sage/sets/finite_set_maps.py # 7 doctests failed sage -t devel/sage-main/sage/combinat/iet/template.py # 3 doctests failed sage -t devel/sage-main/sage/categories/algebras_with_basis.py # 38 doctests failed sage -t devel/sage-main/sage/categories/examples/algebras_with_basis.py # 5 doctests failed sage -t devel/sage-main/sage/combinat/words/word_infinite_datatypes.py # 194 doctests failed sage -t devel/sage-main/sage/combinat/words/word_options.py # 6 doctests failed sage -t devel/sage-main/sage/sets/finite_set_map_cy.pyx # 2 doctests failed sage -t devel/sage-main/sage/combinat/iet/constructors.py # 3 doctests failed sage -t devel/sage-main/sage/combinat/debruijn_sequence.pyx # 2 doctests failed sage -t devel/sage-main/sage/combinat/words/word_datatypes.pyx # 29 doctests failed sage -t devel/sage-main/sage/sets/disjoint_set.pyx # 2 doctests failed sage -t devel/sage-main/sage/combinat/lyndon_word.py # 23 doctests failed sage -t devel/sage-main/sage/combinat/words/infinite_word.py # 14 doctests failed sage -t devel/sage-main/sage/combinat/iet/labelled.py # 20 doctests failed sage -t devel/sage-main/sage/combinat/words/abstract_word.py # 220 doctests failed sage -t devel/sage-main/sage/combinat/words/shuffle_product.py # 16 doctests failed sage -t devel/sage-main/sage/combinat/ribbon_tableau.py # 1 doctests failed sage -t devel/sage-main/sage/combinat/words/word.py # 97 doctests failed sage -t devel/sage-main/sage/combinat/words/words.py # 207 doctests failed sage -t devel/sage-main/sage/categories/modules_with_basis.py # 3 doctests failed sage -t devel/sage-main/sage/combinat/words/alphabet.py # Time out ---------------------------------------------------------------------- Timings have been updated. Total time for all tests: 2331.8 seconds
For what reason each of these tests are failing? If it is because of a string repr that changed, this should be reverted and postpone in another ticket. If it is some hidden method starting with an underscore that was change : ok. If some result of type(something)
changed because the class name has changed : ok. But if it is a normal method, it should still work after the ticket.
comment:21 Changed 10 years ago by
Status: | new → needs_review |
---|
comment:22 Changed 10 years ago by
Reviewers: | → Sébastien Labbé |
---|---|
Status: | needs_review → needs_work |
Work issues: | → pickling, doctests errors, revert changes on repr, ... |
comment:23 Changed 10 years ago by
I just reorganized my comments which were all mixed up. See Comment 10 for an up to date summary.
comment:24 Changed 9 years ago by
Cc: | Timo Jolivet added |
---|
comment:25 Changed 9 years ago by
Milestone: | sage-5.11 → sage-5.12 |
---|
comment:26 Changed 9 years ago by
Milestone: | sage-6.1 → sage-6.2 |
---|
comment:27 Changed 8 years ago by
Milestone: | sage-6.2 → sage-6.3 |
---|
comment:28 Changed 8 years ago by
Milestone: | sage-6.3 → sage-6.4 |
---|
comment:29 Changed 6 years ago by
Cc: | Jeremias Epperlein added |
---|
comment:30 Changed 4 years ago by
Vincent, should we close this ticket as "won't fix" since some of the issue was dealt partly in several disjoint other tickets (done or still to be done)?
comment:31 Changed 4 years ago by
Word
/FiniteWord
does not inherits from Element
/Parent
. Why would you want to close this ticket? Where has this problem been dealt with?
comment:32 Changed 4 years ago by
I would suggest to start over in a new ticket, or alternatively, can you please update the description of this ticket to the goal you see it has?
comment:33 Changed 11 months ago by
Description: | modified (diff) |
---|---|
Milestone: | sage-6.4 → sage-9.1.1 |
comment:34 Changed 11 months ago by
Description: | modified (diff) |
---|
comment:35 Changed 5 months ago by
Milestone: | sage-9.1.1 → sage-wishlist |
---|
The patch is still in experimental version but a relatively stable one (all tests pass but the coverage is not 100%)... you may use, test, comment, break and enjoy !
Best, Vincent