Interleaved products and segmentation faults

[MSebeke]

Good morning! I've been trying to implement an Interleaved product, but the gapc raises a segmentation fault when trying to compile it. When combining the classifying algebra alg_shape5 and the kscoring algebra alg_mfe_subopt in an instance gra_macrostate(alg_shape5/alg_mfe_subopt); it first throws a warning, followed by a segmentation fault:

gapc -i Test FG.gap
Warning:
  kscoring choice [int] h([int] i) {
                        ^
Algebras/MFE/alg_mfe.gap:157.25: Declared role of algebra choice function h (in algebra alg_mfe_subopt) does not match autodetected role none(n).
Warning:
  left_dangle = ambd(edanglel, BASE with unpaired, noleft_dangle) | cadd_Pr(edanglel, {noleft_dangle | nil(LOC)}) | cadd(edanglelr, {left_dangle | left_unpair
                                                                                      ^------------------------^
Grammars/gra_macrostate.gap:2080.87-112: Block has an answer list >= n, consider moving this block into an extra NT andapplying choice function to it.
Warning:
  left_dangle = ambd(edanglel, BASE with unpaired, noleft_dangle) | cadd_Pr(edanglel, {noleft_dangle | nil(LOC)}) | cadd(edanglelr, {left_dangle | left_unpair
                                                                                                                                    ^---------------------------^
Grammars/gra_macrostate.gap:2080.133-161: Block has an answer list >= n, consider moving this block into an extra NT andapplying choice function to it.
Warning:
  multiloop = {mldl   (BASE, BASE with unpaired, ml_comps1,                     BASE) with basepair  |
              ^-^
Grammars/gra_macrostate.gap:2097.15-2105.100: Block has an answer list >= n, consider moving this block into an extra NT andapplying choice function to it.
Warning:
  noleft_dangle = cadd_Pr_Pr(edangler, {left_dangle | left_unpaired}) | cadd_Pr_Pr_Pr(nodangle, {noleft_dangle | nil(LOC)}) | ambd_Pr(nodangle, BASE with unpa
                                       ^---------------------------^
Grammars/gra_macrostate.gap:2082.40-68: Block has an answer list >= n, consider moving this block into an extra NT andapplying choice function to it.
Warning:
  noleft_dangle = cadd_Pr_Pr(edangler, {left_dangle | left_unpaired}) | cadd_Pr_Pr_Pr(nodangle, {noleft_dangle | nil(LOC)}) | ambd_Pr(nodangle, BASE with unpa
                                                                                                ^------------------------^
Grammars/gra_macrostate.gap:2082.97-122: Block has an answer list >= n, consider moving this block into an extra NT andapplying choice function to it.
Segmentation fault

This might be related to the other issue I raised here: https://github.com/jlab/fold-grammars/issues/58, as it seems this is a deeper issue with the compiler. All the program parts I used were taken from fold_grammars with no changes. Additionally I also tried compiling with gapc command line arguments, notably --kbacktrace and --subopt-classify, but the warning and the segmentation fault keep occuring. Any help on this would be appreciated!

[sjanssen2]

Hi @MSebeke thanks for the report and sorry for a late reply. I am trying to reproduce your issue and wonder about the first warning

Warning:
  kscoring choice [int] h([int] i) {
                        ^
Algebras/MFE/alg_mfe.gap:157.25: Declared role of algebra choice function h (in algebra alg_mfe_subopt) does not match autodetected role none(n).

as I would have expected to see the answer_macrostate_mfe datatype instead of int. The grammar gra_macrostate requires a specialized version of the MFE algebra to access first and last stem positions during computation (which violated Bellman's principle :-/, see the comment in https://github.com/jlab/fold-grammars/blob/6c651d2f362b3d1b600986a7c7b1cbabc9679324/Algebras/MFE/alg_mfe_macrostate.gap#L2-L34)

Would you mind mailing me your FG.gap source code to be really able to reproduce?

However, this does not touch the segfault and I can already investigate independently ...

[MSebeke]

Hello @sjanssen2, I looked into the type issue and realized that I was using the wrong alg_mfe. I corrected my code to use the alg_mfe_macrostate now (it is still wrong in the mail I send you). Even with this though, the warning persists and the Segmentation Fault aswell:

gapc -i Test FG_Motifs.gap
Warning:
  kscoring choice [answer_macrostate_mfe] h([answer_macrostate_mfe] i) {
                                          ^
Algebras/MFE/alg_mfe_macrostate.gap:391.43: Declared role of algebra choice function h (in algebra alg_mfe_subopt) does not match autodetected role none(n).
Warning:
  left_dangle = ambd(edanglel, BASE with unpaired, noleft_dangle) | cadd_Pr(edanglel, {noleft_dangle | nil(LOC)}) | cadd(edanglelr, {left_dangle | left_unpair
                                                                                      ^------------------------^
Grammars/gra_macrostate.gap:2689.87-112: Block has an answer list >= n, consider moving this block into an extra NT andapplying choice function to it.
Warning:
  left_dangle = ambd(edanglel, BASE with unpaired, noleft_dangle) | cadd_Pr(edanglel, {noleft_dangle | nil(LOC)}) | cadd(edanglelr, {left_dangle | left_unpair
                                                                                                                                    ^---------------------------^
Grammars/gra_macrostate.gap:2689.133-161: Block has an answer list >= n, consider moving this block into an extra NT andapplying choice function to it.
Warning:
  multiloop = {mldl   (BASE, BASE with unpaired, ml_comps1,                     BASE) with basepair  |
              ^-^
Grammars/gra_macrostate.gap:2706.15-2714.100: Block has an answer list >= n, consider moving this block into an extra NT andapplying choice function to it.
Warning:
  noleft_dangle = cadd_Pr_Pr(edangler, {left_dangle | left_unpaired}) | cadd_Pr_Pr_Pr(nodangle, {noleft_dangle | nil(LOC)}) | ambd_Pr(nodangle, BASE with unpa
                                       ^---------------------------^
Grammars/gra_macrostate.gap:2691.40-68: Block has an answer list >= n, consider moving this block into an extra NT andapplying choice function to it.
Warning:
  noleft_dangle = cadd_Pr_Pr(edangler, {left_dangle | left_unpaired}) | cadd_Pr_Pr_Pr(nodangle, {noleft_dangle | nil(LOC)}) | ambd_Pr(nodangle, BASE with unpa
                                                                                                ^------------------------^
Grammars/gra_macrostate.gap:2691.97-122: Block has an answer list >= n, consider moving this block into an extra NT andapplying choice function to it.
Segmentation fault

[sjanssen2]

The most elaborate definition of the interleaved product that I could find is in this paper. It also comes with two example candidate lists and according results on page 9. I tried to implement the example in a very stupid grammar with mentioned algebras A, B and C:

type Rope = extern

signature sig_test(alphabet, answer) {
    answer c1(void);
    answer c2(void);
    answer c3(void);
    answer c4(void);
    answer c5(void);
    answer c6(void);
    answer c7(void);
    answer c8(void);
    answer c9(void);
    answer c10(void);
    answer f(alphabet, answer);
    choice [answer] h([answer]);
}

algebra alg_enum auto enum;
algebra alg_count auto count;

classify algebra alg_A implements sig_test(alphabet=char, answer=Rope) {
    Rope c1(void) { return Rope("green"); }
    Rope c2(void) { return Rope("red"); }
    Rope c3(void) { return Rope("red"); }
    Rope c4(void) { return Rope("blue"); }
    Rope c5(void) { return Rope("blue"); }

    Rope c6(void) { return Rope("green"); }
    Rope c7(void) { return Rope("red"); }
    Rope c8(void) { return Rope("red"); }
    Rope c9(void) { return Rope("blue"); }
    Rope c10(void) { return Rope("blue"); }

    Rope f(char a, Rope x) { return x; }

    choice [Rope] h([Rope] candidates) {
        return unique(candidates);
    }
}

algebra alg_B implements sig_test(alphabet=char, answer=int) {
    int c1(void) { return 14; }
    int c2(void) { return 12; }
    int c3(void) { return 12; }
    int c4(void) { return 8; }
    int c5(void) { return 9; }

    int c6(void) { return 14; }
    int c7(void) { return 12; }
    int c8(void) { return 12; }
    int c9(void) { return 8; }
    int c10(void) { return 9; }

    int f(char a, int x) { return x; }

    choice [int] h([int] candidates) {
        return list(maximum(candidates));
    }
}

classify algebra alg_C implements sig_test(alphabet=char, answer=Rope) {
    Rope c1(void) { return Rope("s1"); }
    Rope c2(void) { return Rope("s2"); }
    Rope c3(void) { return Rope("s3"); }
    Rope c4(void) { return Rope("s4"); }
    Rope c5(void) { return Rope("s5"); }

    Rope c6(void) { return Rope("2"); }
    Rope c7(void) { return Rope("1"); }
    Rope c8(void) { return Rope("6"); }
    Rope c9(void) { return Rope("3"); }
    Rope c10(void) { return Rope("2"); }

    Rope f(char a, Rope x) { return x; }

    choice [Rope] h([Rope] candidates) {
        return unique(candidates);
    }
}

grammar gra_test uses sig_test(axiom=start) {
    start = f(CHAR('1'), l1) | f(CHAR('2'), l2);
    l1 = c1(EMPTY) | c2(EMPTY) | c3(EMPTY) | c4(EMPTY) | c5(EMPTY) # h;
    l2 = c6(EMPTY) | c7(EMPTY) | c8(EMPTY) | c9(EMPTY) | c10(EMPTY) # h;
}

instance test = gra_test(alg_enum);

However, I was not able to run gapc with an interleaved product alg_A / alg_B in any combination of cmd parameters :-/ I could also not find any suitable tests that apply the interleaved product. Thus, I currently doubt that it was ever functional, but one would have to move through all commits and test this.