Opened 8 years ago

Last modified 10 months ago

#12224 needs_work enhancement

Language as parent / Word as element

Reported by: vdelecroix Owned by: vdelecroix
Priority: major Milestone: sage-6.4
Component: combinatorics Keywords: word, language, symbolic dynamics
Cc: sstarosta, slabbe, tmonteil, ncohen, tjolivet, jepperlein 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 slabbe)

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.

see also: #12225, #12227

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 vdelecroix 7 years ago.

Download all attachments as: .zip

Change History (33)

comment:1 Changed 8 years ago by vdelecroix

  • Description modified (diff)

comment:2 Changed 8 years ago by vdelecroix

  • Dependencies set to #10193
  • Description modified (diff)

comment:3 Changed 8 years ago by ncohen

  • Cc ncohen added

comment:4 Changed 7 years ago by vdelecroix

  • Dependencies changed from #10193 to #8920, #10193

comment:5 Changed 7 years ago by vdelecroix

  • Dependencies changed from #8920, #10193 to #8920, #10193, #13803, #13778

comment:6 Changed 7 years ago by vdelecroix

  • Dependencies changed from #8920, #10193, #13803, #13778 to #8920, #13778, #13956

comment:7 Changed 7 years ago by vdelecroix

  • Dependencies changed from #8920, #13778, #13956 to #8920, #13778, #13956, #13957
  • Description modified (diff)

comment:8 Changed 7 years ago by vdelecroix

  • Dependencies changed from #8920, #13778, #13956, #13957 to #8920, #12230, #12518, #13778, #13956, #13957

Changed 7 years ago by vdelecroix

comment:9 Changed 7 years ago by 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

comment:10 follow-up: Changed 7 years ago by 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.
  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 7 years ago by slabbe (previous) (diff)

comment:11 Changed 7 years ago by slabbe

I removed this comment after reorganisation.

Last edited 7 years ago by slabbe (previous) (diff)

comment:12 Changed 7 years ago by slabbe

I removed this comment after reorganisation.

Last edited 7 years ago by slabbe (previous) (diff)

comment:13 Changed 7 years ago by slabbe

  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 7 years ago by slabbe (previous) (diff)

comment:14 Changed 7 years ago by 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.

Last edited 7 years ago by slabbe (previous) (diff)

comment:15 Changed 7 years ago by slabbe

  • Description modified (diff)

comment:16 Changed 7 years ago by slabbe

  • Description modified (diff)

comment:17 Changed 7 years ago by 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.

Last edited 7 years ago by slabbe (previous) (diff)

comment:18 Changed 7 years ago by slabbe

  • Dependencies changed from #8920, #12230, #12518, #13778, #13956, #13957 to #8920, #12230, #12518, #13778, #13956, #13957, #13801

comment:19 Changed 7 years ago by slabbe

  • Description modified (diff)

comment:20 Changed 7 years ago by 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.

Last edited 7 years ago by slabbe (previous) (diff)

comment:21 Changed 7 years ago by slabbe

  • Status changed from new to needs_review

comment:22 Changed 7 years ago by slabbe

  • Reviewers set to Sébastien Labbé
  • Status changed from needs_review to needs_work
  • Work issues set to pickling, doctests errors, revert changes on repr, ...

comment:23 in reply to: ↑ 10 Changed 7 years ago by slabbe

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

comment:24 Changed 6 years ago by tjolivet

  • Cc tjolivet added

comment:25 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:26 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:27 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:28 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:29 Changed 3 years ago by jepperlein

  • Cc jepperlein added

comment:30 Changed 10 months ago by 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)?

comment:31 Changed 10 months ago by vdelecroix

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 10 months ago by 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?

Note: See TracTickets for help on using tickets.