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&nbsp;
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&nbsp;<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&nbsp;<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&nbsp;<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 &lt; 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##  &ndash;for <E>any</E> list of input generators&ndash; 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&nbsp;<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&nbsp;<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&nbsp;<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