1############################################################################# 2## 3## This file is part of GAP, a system for computational discrete algebra. 4## This file's authors include Thomas Breuer, Alexander Hulpke, Max Neunhöffer. 5## 6## Copyright of GAP belongs to its developers, whose names are too numerous 7## to list here. Please refer to the COPYRIGHT file for details. 8## 9## SPDX-License-Identifier: GPL-2.0-or-later 10## 11## This file contains the declarations of the operations 12## for straight line programs. 13## 14## 1. Functions for straight line programs 15## 2. Functions for elements represented by straight line programs 16## 17 18 19############################################################################# 20## 21## 1. Functions for straight line programs 22## 23 24 25############################################################################# 26## 27## <#GAPDoc Label="[1]{straight}"> 28## <E>Straight line programs</E> describe an efficient way for evaluating an 29## abstract word at concrete generators, 30## in a more efficient way than with <Ref Oper="MappedWord"/>. 31## For example, 32## the associative word <M>ababbab</M> of length <M>7</M> can be computed 33## from the generators <M>a</M>, <M>b</M> with only four multiplications, 34## by first computing <M>c = ab</M>, then <M>d = cb</M>, 35## and then <M>cdc</M>; 36## Alternatively, one can compute <M>c = ab</M>, <M>e = bc</M>, 37## and <M>aee</M>. 38## In each step of these computations, one forms words in terms of the 39## words computed in the previous steps. 40## <P/> 41## A straight line program in &GAP; is represented by an object in the 42## category <Ref Filt="IsStraightLineProgram"/>) 43## that stores a list of <Q>lines</Q> 44## each of which has one of the following three forms. 45## <Enum> 46## <Item> 47## a nonempty dense list <M>l</M> of integers, 48## </Item> 49## <Item> 50## a pair <M>[ l, i ]</M> 51## where <M>l</M> is a list of form 1. 52## and <M>i</M> is a positive integer, 53## </Item> 54## <Item> 55## a list <M>[ l_1, l_2, \ldots, l_k ]</M> 56## where each <M>l_i</M> is a list of form 1.; 57## this may occur only for the last line of the program. 58## </Item> 59## </Enum> 60## <P/> 61## The lists of integers that occur are interpreted as external 62## representations of associative words (see Section 63## <Ref Sect="The External Representation for Associative Words"/>); 64## for example, the list <M>[ 1, 3, 2, -1 ]</M> represents the word 65## <M>g_1^3 g_2^{{-1}}</M>, with <M>g_1</M> and <M>g_2</M> the first and 66## second abstract generator, respectively. 67## <P/> 68## For the meaning of the list of lines, see 69## <Ref Oper="ResultOfStraightLineProgram"/>. 70## <P/> 71## Straight line programs can be constructed using 72## <Ref Func="StraightLineProgram" Label="for a list of lines (and the number of generators)"/>. 73## <P/> 74## Defining attributes for straight line programs are 75## <Ref Attr="NrInputsOfStraightLineProgram"/> 76## and <Ref Attr="LinesOfStraightLineProgram"/>. 77## Another operation for straight line programs is 78## <Ref Oper="ResultOfStraightLineProgram"/>. 79## <P/> 80## Special methods applicable to straight line programs are installed for 81## the operations <Ref Oper="Display"/>, 82## <Ref Oper="IsInternallyConsistent"/>, <Ref Oper="PrintObj"/>, 83## and <Ref Oper="ViewObj"/>. 84## <P/> 85## For a straight line program <A>prog</A>, 86## the default <Ref Oper="Display"/> method prints the interpretation 87## of <A>prog</A> as a sequence of assignments of associative words; 88## a record with components <C>gensnames</C> (with value a list of strings) 89## and <C>listname</C> (a string) may be entered as second argument of 90## <Ref Oper="Display"/>, 91## in this case these names are used, the default for <C>gensnames</C> is 92## <C>[ g1, g2, </C><M>\ldots</M><C> ]</C>, 93## the default for <C>listname</C> is <M>r</M>. 94## <#/GAPDoc> 95## 96 97 98############################################################################# 99## 100#C IsStraightLineProgram( <obj> ) 101## 102## <#GAPDoc Label="IsStraightLineProgram"> 103## <ManSection> 104## <Filt Name="IsStraightLineProgram" Arg='obj' Type='Category'/> 105## 106## <Description> 107## Each straight line program in &GAP; lies in the category 108## <Ref Filt="IsStraightLineProgram"/>. 109## </Description> 110## </ManSection> 111## <#/GAPDoc> 112## 113DeclareCategory( "IsStraightLineProgram", IsObject ); 114 115 116############################################################################# 117## 118#F StraightLineProgram( <lines>[, <nrgens>] ) 119#F StraightLineProgram( <string>, <gens> ) 120#F StraightLineProgramNC( <lines>[, <nrgens>] ) 121#F StraightLineProgramNC( <string>, <gens> ) 122## 123## <#GAPDoc Label="StraightLineProgram"> 124## <ManSection> 125## <Func Name="StraightLineProgram" Arg='lines[, nrgens]' 126## Label="for a list of lines (and the number of generators)"/> 127## <Func Name="StraightLineProgram" Arg='string, gens' 128## Label="for a string and a list of generators names"/> 129## <Func Name="StraightLineProgramNC" Arg='lines[, nrgens]' 130## Label="for a list of lines (and the number of generators)"/> 131## <Func Name="StraightLineProgramNC" Arg='string, gens' 132## Label="for a string and a list of generators names"/> 133## 134## <Description> 135## In the first form, <A>lines</A> must be a nonempty list of lists 136## that defines a unique straight line program 137## (see <Ref Filt="IsStraightLineProgram"/>); in this case 138## <Ref Func="StraightLineProgram" Label="for a list of lines (and the number of generators)"/> 139## returns this program, otherwise an error is signalled. 140## The optional argument <A>nrgens</A> specifies the number of input 141## generators of the program; 142## if a line of form 1. (that is, a list of integers) occurs in <A>lines</A> 143## except in the last position, 144## this number is not determined by <A>lines</A> and therefore <E>must</E> 145## be specified by the argument <A>nrgens</A>; 146## if not then 147## <Ref Func="StraightLineProgram" Label="for a list of lines (and the number of generators)"/> 148## returns <K>fail</K>. 149## <P/> 150## In the second form, <A>string</A> must be a nonempty string describing an 151## arithmetic expression in terms of the strings in the list <A>gens</A>, 152## where multiplication is denoted by concatenation, powering is denoted by 153## <C>^</C>, and round brackets <C>(</C>, <C>)</C> may be used. 154## Each entry in <A>gens</A> must consist only of uppercase or lowercase 155## letters (i.e., letters in <Ref Func="IsAlphaChar"/>) 156## such that no entry is an initial part of another one. 157## Called with this input, 158## <Ref Func="StraightLineProgram" Label="for a string and a list of generators names"/> 159## returns a straight line program that evaluates to the word corresponding 160## to <A>string</A> when called with generators corresponding to 161## <A>gens</A>. 162## <P/> 163## The <C>NC</C> variant does the same, 164## except that the internal consistency of the program is not checked. 165## </Description> 166## </ManSection> 167## <#/GAPDoc> 168## 169DeclareGlobalFunction( "StraightLineProgram" ); 170 171DeclareGlobalFunction( "StraightLineProgramNC" ); 172 173 174############################################################################# 175## 176#F StringToStraightLineProgram( <string>, <gens>, <script> ) 177## 178## <ManSection> 179## <Func Name="StringToStraightLineProgram" Arg='string, gens, script'/> 180## 181## <Description> 182## For a string <A>string</A>, a list <A>gens</A> of strings such that 183## <A>string</A> describes a word in terms of <A>gens</A>, 184## and a list <A>script</A>, <Ref Func="StringToStraightLineProgram"/> 185## transforms <A>string</A> into the lines of a straight line program, 186## which are collected in <A>script</A>. 187## <P/> 188## The return value is <K>true</K> if <A>string</A> is valid, 189## and <K>false</K> otherwise. 190## <P/> 191## This function is used by 192## <Ref Func="StraightLineProgram" Label="for a string and a list of generators names"/> 193## and <Ref Func="ScriptFromString"/>; 194## it is only of local interest, we declare it here because it is recursive. 195## </Description> 196## </ManSection> 197## 198DeclareGlobalFunction( "StringToStraightLineProgram" ); 199 200 201############################################################################# 202## 203#A LinesOfStraightLineProgram( <prog> ) 204## 205## <#GAPDoc Label="LinesOfStraightLineProgram"> 206## <ManSection> 207## <Attr Name="LinesOfStraightLineProgram" Arg='prog'/> 208## 209## <Description> 210## For a straight line program <A>prog</A>, 211## <Ref Attr="LinesOfStraightLineProgram"/> returns 212## the list of program lines. 213## There is no default method to compute these lines if they are not stored. 214## </Description> 215## </ManSection> 216## <#/GAPDoc> 217## 218DeclareAttribute( "LinesOfStraightLineProgram", IsStraightLineProgram ); 219 220 221############################################################################# 222## 223#A NrInputsOfStraightLineProgram( <prog> ) 224## 225## <#GAPDoc Label="NrInputsOfStraightLineProgram"> 226## <ManSection> 227## <Attr Name="NrInputsOfStraightLineProgram" Arg='prog'/> 228## 229## <Description> 230## For a straight line program <A>prog</A>, 231## <Ref Attr="NrInputsOfStraightLineProgram"/> 232## returns the number of generators that are needed as input. 233## <P/> 234## If a line of form 1. (that is, a list of integers) occurs in the lines of 235## <A>prog</A> except the last line 236## then the number of generators is not determined by the lines, 237## and must be set in the construction of the straight line program 238## (see <Ref Func="StraightLineProgram" Label="for a list of lines (and the number of generators)"/>). 239## So if <A>prog</A> contains a line of form 1. other than the last line 240## and does <E>not</E> store the number of generators 241## then <Ref Attr="NrInputsOfStraightLineProgram"/> signals an error. 242## </Description> 243## </ManSection> 244## <#/GAPDoc> 245## 246DeclareAttribute( "NrInputsOfStraightLineProgram", IsStraightLineProgram ); 247 248 249############################################################################# 250## 251#O ResultOfStraightLineProgram( <prog>, <gens> ) 252## 253## <#GAPDoc Label="ResultOfStraightLineProgram"> 254## <ManSection> 255## <Oper Name="ResultOfStraightLineProgram" Arg='prog, gens'/> 256## 257## <Description> 258## <Ref Oper="ResultOfStraightLineProgram"/> evaluates the straight line 259## program (see <Ref Filt="IsStraightLineProgram"/>) <A>prog</A> 260## at the group elements in the list <A>gens</A>. 261## <P/> 262## The <E>result</E> of a straight line program with lines 263## <M>p_1, p_2, \ldots, p_k</M> 264## when applied to <A>gens</A> is defined as follows. 265## <List> 266## <Mark>(a)</Mark> 267## <Item> 268## First a list <M>r</M> of intermediate results is initialized 269## with a shallow copy of <A>gens</A>. 270## </Item> 271## <Mark>(b)</Mark> 272## <Item> 273## For <M>i < k</M>, before the <M>i</M>-th step, 274## let <M>r</M> be of length <M>n</M>. 275## If <M>p_i</M> is the external representation of an associative word 276## in the first <M>n</M> generators then the image of this word under 277## the homomorphism that is given by mapping <M>r</M> to these first 278## <M>n</M> generators is added to <M>r</M>; 279## if <M>p_i</M> is a pair <M>[ l, j ]</M>, for a list <M>l</M>, 280## then the same element is computed, but instead of being added to 281## <M>r</M>, it replaces the <M>j</M>-th entry of <M>r</M>. 282## </Item> 283## <Mark>(c)</Mark> 284## <Item> 285## For <M>i = k</M>, if <M>p_k</M> is the external representation of an 286## associative word then the element described in (b) is the result 287## of the program, 288## if <M>p_k</M> is a pair <M>[ l, j ]</M>, for a list <M>l</M>, 289## then the result is the element described by <M>l</M>, 290## and if <M>p_k</M> is a list <M>[ l_1, l_2, \ldots, l_k ]</M> of lists 291## then the result is a list of group elements, where each <M>l_i</M> is 292## treated as in (b). 293## </Item> 294## </List> 295## <P/> 296## <Example><![CDATA[ 297## gap> f:= FreeGroup( "x", "y" );; gens:= GeneratorsOfGroup( f );; 298## gap> x:= gens[1];; y:= gens[2];; 299## gap> prg:= StraightLineProgram( [ [] ] ); 300## <straight line program> 301## gap> ResultOfStraightLineProgram( prg, [] ); 302## [ ] 303## ]]></Example> 304## The above straight line program <C>prg</C> returns 305## –for <E>any</E> list of input generators– an empty list. 306## <Example><![CDATA[ 307## gap> StraightLineProgram( [ [1,2,2,3], [3,-1] ] ); 308## fail 309## gap> prg:= StraightLineProgram( [ [1,2,2,3], [3,-1] ], 2 ); 310## <straight line program> 311## gap> LinesOfStraightLineProgram( prg ); 312## [ [ 1, 2, 2, 3 ], [ 3, -1 ] ] 313## gap> prg:= StraightLineProgram( "(a^2b^3)^-1", [ "a", "b" ] ); 314## <straight line program> 315## gap> LinesOfStraightLineProgram( prg ); 316## [ [ [ 1, 2, 2, 3 ], 3 ], [ [ 3, -1 ], 4 ] ] 317## gap> res:= ResultOfStraightLineProgram( prg, gens ); 318## y^-3*x^-2 319## gap> res = (x^2 * y^3)^-1; 320## true 321## gap> NrInputsOfStraightLineProgram( prg ); 322## 2 323## gap> Print( prg, "\n" ); 324## StraightLineProgram( [ [ [ 1, 2, 2, 3 ], 3 ], [ [ 3, -1 ], 4 ] ], 2 ) 325## gap> Display( prg ); 326## # input: 327## r:= [ g1, g2 ]; 328## # program: 329## r[3]:= r[1]^2*r[2]^3; 330## r[4]:= r[3]^-1; 331## # return value: 332## r[4] 333## gap> IsInternallyConsistent( StraightLineProgramNC( [ [1,2] ] ) ); 334## true 335## gap> IsInternallyConsistent( StraightLineProgramNC( [ [1,2,3] ] ) ); 336## false 337## gap> prg1:= StraightLineProgram( [ [1,1,2,2], [3,3,1,1] ], 2 );; 338## gap> prg2:= StraightLineProgram( [ [ [1,1,2,2], 2 ], [2,3,1,1] ] );; 339## gap> res1:= ResultOfStraightLineProgram( prg1, gens ); 340## (x*y^2)^3*x 341## gap> res1 = (x*y^2)^3*x; 342## true 343## gap> res2:= ResultOfStraightLineProgram( prg2, gens ); 344## (x*y^2)^3*x 345## gap> res2 = (x*y^2)^3*x; 346## true 347## gap> prg:= StraightLineProgram( [ [2,3], [ [3,1,1,4], [1,2,3,1] ] ], 2 );; 348## gap> res:= ResultOfStraightLineProgram( prg, gens ); 349## [ y^3*x^4, x^2*y^3 ] 350## ]]></Example> 351## </Description> 352## </ManSection> 353## <#/GAPDoc> 354## 355DeclareOperation( "ResultOfStraightLineProgram", 356 [ IsStraightLineProgram, IsHomogeneousList ] ); 357 358 359############################################################################# 360## 361#F StringOfResultOfStraightLineProgram( <prog>, <gensnames>[, "LaTeX"] ) 362## 363## <#GAPDoc Label="StringOfResultOfStraightLineProgram"> 364## <Index Subkey="for the result of a straight line program">LaTeX</Index> 365## <ManSection> 366## <Func Name="StringOfResultOfStraightLineProgram" 367## Arg='prog, gensnames[, "LaTeX"]'/> 368## 369## <Description> 370## <Ref Func="StringOfResultOfStraightLineProgram"/> returns a string 371## that describes the result of the straight line program 372## (see <Ref Filt="IsStraightLineProgram"/>) <A>prog</A> 373## as word(s) in terms of the strings in the list <A>gensnames</A>. 374## If the result of <A>prog</A> is a single element then the return value of 375## <Ref Func="StringOfResultOfStraightLineProgram"/> is a string consisting 376## of the entries of <A>gensnames</A>, opening and closing brackets <C>(</C> 377## and <C>)</C>, and powering by integers via <C>^</C>. 378## If the result of <A>prog</A> is a list of elements then the return value 379## of <Ref Func="StringOfResultOfStraightLineProgram"/> is a comma separated 380## concatenation of the strings of the single elements, 381## enclosed in square brackets <C>[</C>, <C>]</C>. 382## <Example><![CDATA[ 383## gap> prg:= StraightLineProgram( [ [ 1, 2, 2, 3 ], [ 3, -1 ] ], 2 );; 384## gap> StringOfResultOfStraightLineProgram( prg, [ "a", "b" ] ); 385## "(a^2b^3)^-1" 386## gap> StringOfResultOfStraightLineProgram( prg, [ "a", "b" ], "LaTeX" ); 387## "(a^{2}b^{3})^{-1}" 388## ]]></Example> 389## </Description> 390## </ManSection> 391## <#/GAPDoc> 392## 393DeclareGlobalFunction( "StringOfResultOfStraightLineProgram" ); 394 395 396############################################################################# 397## 398#F CompositionOfStraightLinePrograms( <prog2>, <prog1> ) 399## 400## <#GAPDoc Label="CompositionOfStraightLinePrograms"> 401## <ManSection> 402## <Func Name="CompositionOfStraightLinePrograms" Arg='prog2, prog1'/> 403## 404## <Description> 405## For two straight line programs <A>prog1</A> and <A>prog2</A>, 406## <Ref Func="CompositionOfStraightLinePrograms"/> returns a straight line 407## program <A>prog</A> with the properties that <A>prog1</A> and <A>prog</A> 408## have the same number of inputs, and the result of <A>prog</A> 409## when applied to given generators <A>gens</A> equals the result of 410## <A>prog2</A> when this is applied to the output of 411## <A>prog1</A> applied to <A>gens</A>. 412## <P/> 413## (Of course the number of outputs of <A>prog1</A> must be the same as the 414## number of inputs of <A>prog2</A>.) 415## <Example><![CDATA[ 416## gap> prg1:= StraightLineProgram( "a^2b", [ "a","b" ] );; 417## gap> prg2:= StraightLineProgram( "c^5", [ "c" ] );; 418## gap> comp:= CompositionOfStraightLinePrograms( prg2, prg1 ); 419## <straight line program> 420## gap> StringOfResultOfStraightLineProgram( comp, [ "a", "b" ] ); 421## "(a^2b)^5" 422## gap> prg:= StraightLineProgram( [ [2,3], [ [3,1,1,4], [1,2,3,1] ] ], 2 );; 423## gap> StringOfResultOfStraightLineProgram( prg, [ "a", "b" ] ); 424## "[ b^3a^4, a^2b^3 ]" 425## gap> comp:= CompositionOfStraightLinePrograms( prg, prg ); 426## <straight line program> 427## gap> StringOfResultOfStraightLineProgram( comp, [ "a", "b" ] ); 428## "[ (a^2b^3)^3(b^3a^4)^4, (b^3a^4)^2(a^2b^3)^3 ]" 429## ]]></Example> 430## </Description> 431## </ManSection> 432## <#/GAPDoc> 433## 434DeclareGlobalFunction( "CompositionOfStraightLinePrograms" ); 435 436 437############################################################################# 438## 439#F IntegratedStraightLineProgram( <listofprogs> ) 440## 441## <#GAPDoc Label="IntegratedStraightLineProgram"> 442## <ManSection> 443## <Func Name="IntegratedStraightLineProgram" Arg='listofprogs'/> 444## 445## <Description> 446## For a nonempty dense list <A>listofprogs</A> of straight line programs 447## <M>p_1, p_2, \ldots, p_m</M>, say, 448## that have the same number <M>n</M>, say, of inputs 449## (see <Ref Attr="NrInputsOfStraightLineProgram"/>), 450## <Ref Func="IntegratedStraightLineProgram"/> returns a straight line 451## program <M>prog</M> with <M>n</M> inputs such that for each 452## <M>n</M>-tuple <M>gens</M> of generators, 453## <C>ResultOfStraightLineProgram( </C><M>prog, gens</M><C> )</C> 454## is the concatenation of the lists <M>r_1, r_2, \ldots, r_m</M>, 455## where <M>r_i</M> is equal to 456## <C>ResultOfStraightLineProgram( </C><M>p_i, gens</M><C> )</C> 457## if this result is a list of elements, 458## and otherwise <M>r_i</M> is equal to the list of length one 459## that contains this result. 460## 461## <Example><![CDATA[ 462## gap> f:= FreeGroup( "x", "y" );; gens:= GeneratorsOfGroup( f );; 463## gap> prg1:= StraightLineProgram([ [ [ 1, 2 ], 1 ], [ 1, 2, 2, -1 ] ], 2);; 464## gap> prg2:= StraightLineProgram([ [ [ 2, 2 ], 3 ], [ 1, 3, 3, 2 ] ], 2);; 465## gap> prg3:= StraightLineProgram([ [ 2, 2 ], [ 1, 3, 3, 2 ] ], 2);; 466## gap> prg:= IntegratedStraightLineProgram( [ prg1, prg2, prg3 ] );; 467## gap> ResultOfStraightLineProgram( prg, gens ); 468## [ x^4*y^-1, x^3*y^4, x^3*y^4 ] 469## gap> prg:= IntegratedStraightLineProgram( [ prg2, prg3, prg1 ] );; 470## gap> ResultOfStraightLineProgram( prg, gens ); 471## [ x^3*y^4, x^3*y^4, x^4*y^-1 ] 472## gap> prg:= IntegratedStraightLineProgram( [ prg3, prg1, prg2 ] );; 473## gap> ResultOfStraightLineProgram( prg, gens ); 474## [ x^3*y^4, x^4*y^-1, x^3*y^4 ] 475## gap> prg:= IntegratedStraightLineProgram( [ prg, prg ] );; 476## gap> ResultOfStraightLineProgram( prg, gens ); 477## [ x^3*y^4, x^4*y^-1, x^3*y^4, x^3*y^4, x^4*y^-1, x^3*y^4 ] 478## ]]></Example> 479## </Description> 480## </ManSection> 481## <#/GAPDoc> 482## 483DeclareGlobalFunction( "IntegratedStraightLineProgram" ); 484 485 486############################################################################# 487## 488## 2. Functions for elements represented by straight line programs 489## 490## <#GAPDoc Label="[2]{straight}"> 491## When computing with very large (in terms of memory) elements, for 492## example permutations of degree a few hundred thousands, it can be 493## helpful (in terms of memory usage) to represent them via straight line 494## programs in terms of an original generator set. (So every element takes 495## only small extra storage for the straight line program.) 496## <P/> 497## A straight line program element has a <E>seed</E> 498## (a list of group elements) and a straight line program 499## on the same number of generators as the length of this seed, 500## its value is the value of the evaluated straight line program. 501## <P/> 502## At the moment, the entries of the straight line program have to be 503## simple lists (i.e. of the first form). 504## <P/> 505## Straight line program elements are in the same categories 506## and families as the elements of the seed, so they should work together 507## with existing algorithms. 508## <P/> 509## Note however, that due to the different way of storage some normally 510## very cheap operations (such as testing for element equality) can become 511## more expensive when dealing with straight line program elements. This is 512## essentially the tradeoff for using less memory. 513## <P/> 514## See also 515## Section <Ref Sect="Working with large degree permutation groups"/>. 516## <#/GAPDoc> 517## 518 519 520############################################################################# 521## 522#R IsStraightLineProgElm(<obj>) 523## 524## <#GAPDoc Label="IsStraightLineProgElm"> 525## <ManSection> 526## <Filt Name="IsStraightLineProgElm" Arg='obj' Type='Representation'/> 527## 528## <Description> 529## A straight line program element is a group element given (for memory 530## reasons) as a straight line program. Straight line program elements are 531## positional objects, the first component is a record with a component 532## <C>seeds</C>, the second component the straight line program. 533## </Description> 534## </ManSection> 535## <#/GAPDoc> 536## 537## we need to rank higher than default methods 538DeclareFilter("StraightLineProgramElmRankFilter",100); 539 540DeclareRepresentation("IsStraightLineProgElm", 541 IsMultiplicativeElementWithInverse and IsPositionalObjectRep 542 and StraightLineProgramElmRankFilter,[]); 543 544 545############################################################################# 546## 547#A StraightLineProgElmType(<fam>) 548## 549## <ManSection> 550## <Attr Name="StraightLineProgElmType" Arg='fam'/> 551## 552## <Description> 553## returns a type for straight line program elements over the family 554## <A>fam</A>. 555## </Description> 556## </ManSection> 557## 558DeclareAttribute("StraightLineProgElmType",IsFamily); 559 560 561############################################################################# 562## 563#F StraightLineProgElm(<seed>,<prog>) 564## 565## <#GAPDoc Label="StraightLineProgElm"> 566## <ManSection> 567## <Func Name="StraightLineProgElm" Arg='seed,prog'/> 568## 569## <Description> 570## Creates a straight line program element for seed <A>seed</A> and program 571## <A>prog</A>. 572## </Description> 573## </ManSection> 574## <#/GAPDoc> 575## 576DeclareGlobalFunction("StraightLineProgElm"); 577 578 579############################################################################# 580## 581#F EvalStraightLineProgElm(<slpel>) 582## 583## <#GAPDoc Label="EvalStraightLineProgElm"> 584## <ManSection> 585## <Func Name="EvalStraightLineProgElm" Arg='slpel'/> 586## 587## <Description> 588## evaluates a straight line program element <A>slpel</A> from its seeds. 589## </Description> 590## </ManSection> 591## <#/GAPDoc> 592## 593DeclareGlobalFunction("EvalStraightLineProgElm"); 594 595 596############################################################################# 597## 598#F StraightLineProgGens(<gens>[,<base>]) 599## 600## <#GAPDoc Label="StraightLineProgGens"> 601## <ManSection> 602## <Func Name="StraightLineProgGens" Arg='gens[,base]'/> 603## 604## <Description> 605## returns a set of straight line program elements corresponding to the 606## generators in <A>gens</A>. 607## If <A>gens</A> is a set of permutations then <A>base</A> can be given 608## which must be a base for the group generated by <A>gens</A>. 609## (Such a base will be used to speed up equality tests.) 610## </Description> 611## </ManSection> 612## <#/GAPDoc> 613## 614DeclareGlobalFunction("StraightLineProgGens"); 615 616 617############################################################################# 618## 619#O StretchImportantSLPElement(<elm>) 620## 621## <#GAPDoc Label="StretchImportantSLPElement"> 622## <ManSection> 623## <Oper Name="StretchImportantSLPElement" Arg='elm'/> 624## 625## <Description> 626## If <A>elm</A> is a straight line program element whose straight line 627## representation is very long, this operation changes the 628## representation of <A>elm</A> to a straight line program element, equal to 629## <A>elm</A>, whose seed contains the evaluation of <A>elm</A> and whose 630## straight line program has length 1. 631## <P/> 632## For other objects nothing happens. 633## <P/> 634## This operation permits to designate <Q>important</Q> elements within an 635## algorithm (elements that will be referred to often), which will be 636## represented by guaranteed short straight line program elements. 637## <Example><![CDATA[ 638## gap> gens:=StraightLineProgGens([(1,2,3,4),(1,2)]); 639## [ <[ [ 2, 1 ] ]|(1,2,3,4)>, <[ [ 1, 1 ] ]|(1,2)> ] 640## gap> g:=Group(gens);; 641## gap> (gens[1]^3)^gens[2]; 642## <[ [ 1, -1, 2, 3, 1, 1 ] ]|(1,2,4,3)> 643## gap> Size(g); 644## 24 645## ]]></Example> 646## </Description> 647## </ManSection> 648## <#/GAPDoc> 649## 650DeclareOperation("StretchImportantSLPElement", 651 [IsMultiplicativeElementWithInverse]); 652 653############################################################################# 654## 655#F TreeRepresentedWord( <roots>,<tree>,<nr> ) 656## 657## <ManSection> 658## <Func Name="TreeRepresentedWord" Arg='roots,tree,nr'/> 659## 660## <Description> 661## returns a straight line element by decoding element <A>nr</A> 662## of <A>tree</A> with respect to <A>roots</A>. 663## <A>tree</A> is a tree as given by the augmented coset table routines. 664## </Description> 665## </ManSection> 666## 667DeclareGlobalFunction("TreeRepresentedWord"); 668 669 670############################################################################# 671## 672## 3. Functions for straight line programs, mostly needed for memory objects: 673## 674 675 676############################################################################# 677## 678#F SLPChangesSlots( <l>, <nrinputs> ) 679## 680## <ManSection> 681## <Func Name="SLPChangesSlots" Arg='l, nrinputs'/> 682## 683## <Description> 684## l must be the lines of an slp, nrinps the number of inputs. 685## This function returns a list with the same length than l, containing 686## at each position the number of the slot that is changed in the 687## corresponding line of the slp. In addition one more number is 688## appended to the list, namely the number of the biggest slot used. 689## For the moment, this function is intentionally left undocumented. 690## </Description> 691## </ManSection> 692## 693DeclareGlobalFunction( "SLPChangesSlots" ); 694 695## 696#F SLPOnlyNeededLinesBackward( <l>,<i>,<nrinps>,<changes>,<needed>, 697## <slotsused>,<ll> ) 698## 699## <ManSection> 700## <Func Name="SLPOnlyNeededLinesBackward" 701## Arg='l,i,nrinps,changes,needed, slotsused,ll'/> 702## 703## <Description> 704## l is a list of lines of an slp, nrinps the number of inputs. 705## i is the number of the last line, that is not a line of type 3 (results). 706## changes is the result of SLPChangesSlots for that slp. 707## needed is a list, where those entries are bound to true that are 708## needed in the end of the slp. slotsused is a list that should be 709## initialized with [1..nrinps] and which contains in the end the set 710## of slots used. 711## ll is any list. 712## This functions goes backwards through the slp and adds exactly those 713## lines of the slp to ll that have to be executed to produce the 714## result (in backward order). All lines are transformed into type 2 715## lines ([assocword,slot]). Note that needed is changed underways. 716## For the moment, this function is intentionally left undocumented. 717## </Description> 718## </ManSection> 719## 720DeclareGlobalFunction( "SLPOnlyNeededLinesBackward" ); 721 722## 723#F SLPReversedRenumbered( <ll>,<slotsused>,<nrinps>,<invtab> ) 724## 725## <ManSection> 726## <Func Name="SLPReversedRenumbered" Arg='ll,slotsused,nrinps,invtab'/> 727## 728## <Description> 729## Internally used function. 730## </Description> 731## </ManSection> 732## 733DeclareGlobalFunction( "SLPReversedRenumbered" ); 734 735## 736#F RestrictOutputsOfSLP( <slp>, <k> ) 737## 738## <#GAPDoc Label="RestrictOutputsOfSLP"> 739## <ManSection> 740## <Func Name="RestrictOutputsOfSLP" Arg='slp, k'/> 741## 742## <Description> 743## <A>slp</A> must be a straight line program returning a tuple 744## of values. This function 745## returns a new slp that calculates only those outputs specified by 746## <A>k</A>. The argument 747## <A>k</A> may be an integer or a list of integers. If <A>k</A> is an integer, 748## the resulting slp calculates only the result with that number 749## in the original output tuple. 750## If <A>k</A> is a list of integers, the resulting slp calculates those 751## results with indices <A>k</A> in the original output tuple. 752## In both cases the resulting slp 753## does only what is necessary. Obviously, the slp must have a line with 754## enough expressions (lists) for the supplied <A>k</A> as its last line. 755## <A>slp</A> is either an slp or a pair where the first entry are the lines 756## of the slp and the second is the number of inputs. 757## </Description> 758## </ManSection> 759## <#/GAPDoc> 760## 761DeclareGlobalFunction( "RestrictOutputsOfSLP" ); 762 763## 764#F IntermediateResultOfSLP( <slp>, <k> ) 765## 766## <#GAPDoc Label="IntermediateResultOfSLP"> 767## <ManSection> 768## <Func Name="IntermediateResultOfSLP" Arg='slp, k'/> 769## 770## <Description> 771## Returns a new slp that calculates only the value of slot <A>k</A> 772## at the end of <A>slp</A> doing only what is necessary. 773## slp is either an slp or a pair where the first entry are the lines 774## of the slp and the second is the number of inputs. 775## Note that this assumes a general SLP with possible overwriting. 776## If you know that your SLP does not overwrite slots, please use 777## <Ref Func="IntermediateResultOfSLPWithoutOverwrite"/>, 778## which is much faster in this case. 779## </Description> 780## </ManSection> 781## <#/GAPDoc> 782## 783DeclareGlobalFunction( "IntermediateResultOfSLP" ); 784 785## 786#F IntermediateResultsOfSLPWithoutOverwriteInner( ... ) 787## 788## <ManSection> 789## <Func Name="IntermediateResultsOfSLPWithoutOverwriteInner" Arg='...'/> 790## 791## <Description> 792## Internal function. 793## </Description> 794## </ManSection> 795## 796DeclareGlobalFunction( "IntermediateResultsOfSLPWithoutOverwriteInner" ); 797 798## 799#F IntermediateResultsOfSLPWithoutOverwrite( <slp>, <k> ) 800## 801## <#GAPDoc Label="IntermediateResultsOfSLPWithoutOverwrite"> 802## <ManSection> 803## <Func Name="IntermediateResultsOfSLPWithoutOverwrite" Arg='slp, k'/> 804## 805## <Description> 806## Returns a new slp that calculates only the value of slots contained 807## in the list k. 808## Note that <A>slp</A> must not overwrite slots but only append!!! 809## Use <Ref Func="IntermediateResultOfSLP"/> in the other case! 810## <A>slp</A> is either a slp or a pair where the first entry is the lines 811## of the slp and the second is the number of inputs. 812## </Description> 813## </ManSection> 814## <#/GAPDoc> 815## 816DeclareGlobalFunction( "IntermediateResultsOfSLPWithoutOverwrite" ); 817 818## 819#F IntermediateResultOfSLPWithoutOverwrite( <slp>, <k> ) 820## 821## <#GAPDoc Label="IntermediateResultOfSLPWithoutOverwrite"> 822## <ManSection> 823## <Func Name="IntermediateResultOfSLPWithoutOverwrite" Arg='slp, k'/> 824## 825## <Description> 826## Returns a new slp that calculates only the value of slot <A>k</A>, which 827## must be an integer. 828## Note that <A>slp</A> must not overwrite slots but only append!!! 829## Use <Ref Func="IntermediateResultOfSLP"/> in the other case! 830## <A>slp</A> is either an slp or a pair where the first entry is the lines 831## of the slp and the second is the number of inputs. 832## </Description> 833## </ManSection> 834## <#/GAPDoc> 835## 836DeclareGlobalFunction( "IntermediateResultOfSLPWithoutOverwrite" ); 837 838## 839#F ProductOfStraightLinePrograms( <s1>, <s2> ) 840## 841## <#GAPDoc Label="ProductOfStraightLinePrograms"> 842## <ManSection> 843## <Func Name="ProductOfStraightLinePrograms" Arg='s1, s2'/> 844## 845## <Description> 846## <A>s1</A> and <A>s2</A> must be two slps that return a single element with the same 847## number of inputs. This function constructs an slp that returns the product 848## of the two results the slps <A>s1</A> and <A>s2</A> would produce with the same 849## input. 850## </Description> 851## </ManSection> 852## <#/GAPDoc> 853## 854DeclareGlobalFunction( "ProductOfStraightLinePrograms" ); 855 856## 857#F RewriteStraightLineProgram(<s>,<l>,<lsu>,<inputs>,<tabuslots>) 858## 859## <ManSection> 860## <Func Name="RewriteStraightLineProgram" Arg='s,l,lsu,inputs,tabuslots'/> 861## 862## <Description> 863## The purpose of this function is the following: Append the slp <A>s</A> to 864## the one currently built in <A>l</A>. 865## The prospective inputs are already standing somewhere and some 866## slots may not be used by the new copy of <A>s</A> within <A>l</A>. 867## <P/> 868## <A>s</A> must be a GAP straight line program. 869## <A>l</A> must be a mutable list making the beginning of a straight line program 870## without result line so far. <A>lsu</A> must be the largest used slot of the 871## slp in <A>l</A> so far. <A>inputs</A> is a list of slot numbers, in which the 872## inputs are, that the copy of <A>s</A> in <A>l</A> should work on, that is, its length 873## must be equal to the number of inputs <A>s</A> takes. <A>tabuslots</A> is a list of 874## slot numbers which will not be overwritten by the new copy of <A>s</A> in <A>l</A>. 875## This function changes <A>l</A> and returns a record with components 876## <C>l</C> being <A>l</A>, <C>results</C> being 877## a list of slot numbers, in which the results of <A>s</A> are stored in the end 878## and <C>lsu</C> being the number of the largest slot used by <A>l</A> up to now. 879## </Description> 880## </ManSection> 881## 882DeclareGlobalFunction( "RewriteStraightLineProgram" ); 883 884## 885#F NewCompositionOfStraightLinePrograms( <s2>, <s1> ) 886## 887## <ManSection> 888## <Func Name="NewCompositionOfStraightLinePrograms" Arg='s2, s1'/> 889## 890## <Description> 891## A new implementation of <Ref Func="CompositionOfStraightLinePrograms"/> using 892## <Ref Func="RewriteStraightLineProgram"/>. 893## </Description> 894## </ManSection> 895## 896DeclareGlobalFunction( "NewCompositionOfStraightLinePrograms" ); 897 898## 899#F NewProductOfStraightLinePrograms( <s2>, <s1> ) 900## 901## <ManSection> 902## <Func Name="NewProductOfStraightLinePrograms" Arg='s2, s1'/> 903## 904## <Description> 905## A new implementation of <Ref Func="ProductOfStraightLinePrograms"/> using 906## <Ref Func="RewriteStraightLineProgram"/>. 907## </Description> 908## </ManSection> 909## 910DeclareGlobalFunction( "NewProductOfStraightLinePrograms" ); 911 912## 913#A SlotUsagePattern( <s> ) 914## 915## <#GAPDoc Label="SlotUsagePattern"> 916## <ManSection> 917## <Attr Name="SlotUsagePattern" Arg="s"/> 918## 919## <Description> 920## Analyses the straight line program <A>s</A> for more efficient 921## evaluation. This means in particular two things, when this attribute 922## is known: First of all, 923## intermediate results which are not actually needed later on are 924## not computed at all, and once an intermediate result is used for 925## the last time in this SLP, it is discarded. The latter leads to 926## the fact that the evaluation of the SLP needs less memory. 927## </Description> 928## </ManSection> 929## <#/GAPDoc> 930## 931DeclareAttribute( "SlotUsagePattern", IsStraightLineProgram ); 932 933## 934#A LargestNrSlots( <s> ) 935## 936## <ManSection> 937## <Attr Name="LargestNrSlots" Arg="s"/> 938## 939## <Description> 940## Returns the maximal number of slots used during the evaluation of 941## the SLP <A>s</A>. 942## </Description> 943## </ManSection> 944DeclareAttribute( "LargestNrSlots", IsStraightLineProgram ); 945 946## 947#I InfoSLP 948## 949DeclareInfoClass( "InfoSLP" ); 950SetInfoLevel(InfoSLP,1); 951