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:

Status badges

Description (last modified by Vincent Delecroix)

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)

trac_12224-language.patch (1.3 MB) - added by Vincent Delecroix 10 years ago.

Download all attachments as: .zip

Change History (36)

comment:1 Changed 11 years ago by Vincent Delecroix

Description: modified (diff)

comment:2 Changed 11 years ago by Vincent Delecroix

Dependencies: #10193
Description: modified (diff)

comment:3 Changed 11 years ago by Nathann Cohen

Cc: Nathann Cohen added

comment:4 Changed 10 years ago by Vincent Delecroix

Dependencies: #10193#8920, #10193

comment:5 Changed 10 years ago by Vincent Delecroix

Dependencies: #8920, #10193#8920, #10193, #13803, #13778

comment:6 Changed 10 years ago by Vincent Delecroix

Dependencies: #8920, #10193, #13803, #13778#8920, #13778, #13956

comment:7 Changed 10 years ago by Vincent Delecroix

Dependencies: #8920, #13778, #13956#8920, #13778, #13956, #13957
Description: modified (diff)

comment:8 Changed 10 years ago by Vincent Delecroix

Dependencies: #8920, #13778, #13956, #13957#8920, #12230, #12518, #13778, #13956, #13957

Changed 10 years ago by Vincent Delecroix

Attachment: trac_12224-language.patch added

comment:9 Changed 10 years ago by Vincent Delecroix

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

comment:10 Changed 10 years ago by Sébastien Labbé

I started the review. Here is a first bunch of comments.

  1. Goal of the ticket: Categories in sage/combinat/words library. The goal of this patch reimplements the code structure of sage/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 in sage/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.
  1. 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
  1. 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
  1. 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.

  1. 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 branch sage-5.6.rc0 still pass or not. I get 618 failures only for finite_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.

Last edited 10 years ago by Sébastien Labbé (previous) (diff)

comment:11 Changed 10 years ago by Sébastien Labbé

I removed this comment after reorganisation.

Last edited 10 years ago by Sébastien Labbé (previous) (diff)

comment:12 Changed 10 years ago by Sébastien Labbé

I removed this comment after reorganisation.

Last edited 10 years ago by Sébastien Labbé (previous) (diff)

comment:13 Changed 10 years ago by Sébastien Labbé

  1. 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?

Last edited 10 years ago by Sébastien Labbé (previous) (diff)

comment:14 Changed 10 years ago by Sébastien Labbé

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.

Last edited 10 years ago by Sébastien Labbé (previous) (diff)

comment:15 Changed 10 years ago by Sébastien Labbé

Description: modified (diff)

comment:16 Changed 10 years ago by Sébastien Labbé

Description: modified (diff)

comment:17 Changed 10 years ago by Sébastien Labbé

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.

Last edited 10 years ago by Sébastien Labbé (previous) (diff)

comment:18 Changed 10 years ago by Sébastien Labbé

Dependencies: #8920, #12230, #12518, #13778, #13956, #13957#8920, #12230, #12518, #13778, #13956, #13957, #13801

comment:19 Changed 10 years ago by Sébastien Labbé

Description: modified (diff)

comment:20 Changed 10 years ago by Sébastien Labbé

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.

Last edited 10 years ago by Sébastien Labbé (previous) (diff)

comment:21 Changed 10 years ago by Sébastien Labbé

Status: newneeds_review

comment:22 Changed 10 years ago by Sébastien Labbé

Reviewers: Sébastien Labbé
Status: needs_reviewneeds_work
Work issues: pickling, doctests errors, revert changes on repr, ...

comment:23 in reply to:  10 Changed 10 years ago by Sébastien Labbé

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 Timo Jolivet

Cc: Timo Jolivet added

comment:25 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12

comment:26 Changed 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:27 Changed 8 years ago by For batch modifications

Milestone: sage-6.2sage-6.3

comment:28 Changed 8 years ago by For batch modifications

Milestone: sage-6.3sage-6.4

comment:29 Changed 6 years ago by Jeremias Epperlein

Cc: Jeremias Epperlein added

comment:30 Changed 4 years ago by Sébastien Labbé

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 Vincent Delecroix

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 Sébastien Labbé

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 Vincent Delecroix

Description: modified (diff)
Milestone: sage-6.4sage-9.1.1

comment:34 Changed 11 months ago by Vincent Delecroix

Description: modified (diff)

comment:35 Changed 5 months ago by Frédéric Chapoton

Milestone: sage-9.1.1sage-wishlist
Note: See TracTickets for help on using tickets.