Language as parent / Word as element

[vdelecroix]

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.

• #12225 : finite and lazy languages
• #12227 : adic languages

---

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

[vdelecroix]

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

[slabbe]

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.

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

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

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

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

[slabbe]

4 (bis). Just to continue on point above, testing sage/combinat files gives me three more files having similar doctest errors as the above three:

sage-5.6.rc0/devel/sage-language/sage/combinat $ sage -t *

[...]

sage -t  "devel/sage-language/sage/combinat/languages/finite_word_language.py"
**********************************************************************
File "/Users/slabbe/Applications/sage-5.6.rc0/devel/sage-language/sage/combinat/languages/finite_word_language.py", line 47:
    sage: L.list()
Expected:
    [, a, b, ab, bb, ba, abb, bba, bab, abba, bbab, abbab]
Got:
    [, a, b, ab, ba, bb, abb, bba, bab, abba, bbab, abbab]
**********************************************************************
File "/Users/slabbe/Applications/sage-5.6.rc0/devel/sage-language/sage/combinat/languages/finite_word_language.py", line 53:
    sage: G.list()
Expected:
    [, a, b, ab, bb, ba, abb, bba, bab, abba, bbab, abbab]
Got:
    [, a, b, ab, ba, bb, abb, bba, bab, abba, bbab, abbab]
**********************************************************************
File "/Users/slabbe/Applications/sage-5.6.rc0/devel/sage-language/sage/combinat/languages/finite_word_language.py", line 348:
    sage: for v in w.language(): print v,
Expected:
     a b ab bb ba abb bba bab abba bbab abbab
Got:
     a b ab ba bb abb bba bab abba bbab abbab
**********************************************************************
2 items had failures:
   2 of  22 in __main__.example_1
   1 of   6 in __main__.example_14
***Test Failed*** 3 failures.
For whitespace errors, see the file /Users/slabbe/.sage//tmp/finite_word_language_11178.py
	 [4.7 s]

[...]

sage -t  "devel/sage-language/sage/combinat/tableau.py"     
**********************************************************************
File "/Users/slabbe/Applications/sage-5.6.rc0/devel/sage-language/sage/combinat/tableau.py", line 462:
    sage: Tableau([[1,2],[3,4]]).to_word_by_column()
Expected:
    word: 3142
Got:
    3142
**********************************************************************
File "/Users/slabbe/Applications/sage-5.6.rc0/devel/sage-language/sage/combinat/tableau.py", line 464:
    sage: Tableau([[1, 4, 6], [2, 5], [3]]).to_word_by_column()
Expected:
    word: 321546
Got:
    321546
**********************************************************************
File "/Users/slabbe/Applications/sage-5.6.rc0/devel/sage-language/sage/combinat/tableau.py", line 2309:
    sage: word = t.to_word(); word
Expected:
    word: 4213
Got:
    4.2.1.3
**********************************************************************
2 items had failures:
   2 of   5 in __main__.example_17
   1 of  10 in __main__.example_84
***Test Failed*** 3 failures.
For whitespace errors, see the file /Users/slabbe/.sage//tmp/tableau_12194.py
	 [11.7 s]

[...]

sage -t  "devel/sage-language/sage/combinat/tableau_tuple.py"
**********************************************************************
File "/Users/slabbe/Applications/sage-5.6.rc0/devel/sage-language/sage/combinat/tableau_tuple.py", line 603:
    sage: TableauTuple([[[1,2],[3,4]],[[5,6,7],[8]],[[9,10],[11],[12]]]).to_word_by_row()
Expected:
    word: 12,11,9,10,8,5,6,7,3,4,1,2
Got:
    12.11.9.10.8.5.6.7.3.4.1.2
**********************************************************************
File "/Users/slabbe/Applications/sage-5.6.rc0/devel/sage-language/sage/combinat/tableau_tuple.py", line 622:
    sage: TableauTuple([[[1,2],[3,4]],[[5,6,7],[8]],[[9,10],[11],[12]]]).to_word_by_column()
Expected:
    word: 12,11,9,10,8,5,6,7,3,1,4,2
Got:
    12.11.9.10.8.5.6.7.3.1.4.2
**********************************************************************
2 items had failures:
   1 of   4 in __main__.example_13
   1 of   4 in __main__.example_14
***Test Failed*** 2 failures.

[...]

----------------------------------------------------------------------
The following tests failed:


	sage -t  "devel/sage-language/sage/combinat/languages/finite_word_language.py"
	sage -t  "devel/sage-language/sage/combinat/tableau.py"
	sage -t  "devel/sage-language/sage/combinat/tableau_tuple.py"
	sage -t  "devel/sage-language/sage/combinat/words/finite_word.pyx"
	sage -t  "devel/sage-language/sage/combinat/words/morphism.py"
	sage -t  "devel/sage-language/sage/combinat/words/word.py"
Total time for all tests: 1509.3 seconds

[slabbe]

I removed this comment after reorganisation.

[slabbe]

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

[slabbe]

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.

[slabbe]

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.

[slabbe]

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.

[slabbe]

I just reorganized my comments which were all mixed up. See Comment 10 for an up to date summary.

[slabbe]

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)?

[vdelecroix]

Word/FiniteWord does not inherits from Element/Parent. Why would you want to close this ticket? Where has this problem been dealt with?

[slabbe]

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?