SCP 4 you: brief Comments to Demo-Examples

For a lot of other examples , please see a SCP4 User's Guide (in Russian).

Draft

Contents:

Please, pay your attention that the supercompiler can looping forever (by definition) under a combination of keys to run. Default keys are such combination.
There are a number of reasons for that.  In the archive (to be downloaded) version of the documentation we give a number of such examples.

It is not a good idea to see this Web-page in a small window. The MST-schemes can be shown incorrectly in such window. 

Example #1 (Fab):

• This MST-scheme describes a classical task: to transform  a  Fab-function when its argument  is unknown and can be any object expression. 
• The Fab-function replaces 'a' -characters  with  'b'-ones inside a given string.

Example #2 (Fabc):

• The MST-scheme describes a classical task: to supercompile  a composition of  three functions when the argument of the inner Fab-function starts with string  'aebfc' while the rest of the argument is unknown and can be any object expression. 
• The first function (from down to up) replaces 'a' -characters  with  'b'-ones, the second replaces 'b'  with  'c' and ,at last,  the third replaces  'c'  with  'd'.
• If you chouse the lazy driving then you have to expect just one loop in a residual program. 

Example #3 (Sq):

•  Here the Arith-function is an interpreter of a language based on arithmetic expressions. Basic arithmetic operation are defined with external functions.
• The task is to specialize the interpreter w.r.t. a Square function. 

Example #4 (Power):

• Here the Arith-function is an interpreter of a language based on arithmetic expressions. Basic arithmetic operation are defined with external functions.
• The task is to specialize the interpreter w.r.t. a Power function.

Example #5 (Fact):

• Here the Arith-function is an interpreter of a language based on arithmetic expressions. Basic arithmetic operation are defined with external functions.
• The task is to specialize the interpreter w.r.t. a Factorial function.

Example #6 (Cl_AN):

• This example  demonstrates a clearance of input formats and redundant function calls. That is a good idea to compare two residual programs: the first is obtained by  a whole session of supercompilation , - the second is created without the redund stage.   (See  Session Of Supercompilation )

Example #7 (Cl_AK) by  Andrei V. Klimov :

• This example  demonstrates a clearance of input and output formats. That is a good idea to compare two residual programs: the first is obtained by  a whole session of supercompilation , - the second is created without the redund stage.   (See  Session Of Supercompilation )

Example #8 (Permsp) by Alexandr Korljukov:

•  Permutation. Generalization of a classical Fab-example. The permutation is described with cycles. For example, ('123')('45') means that
  '1' --> '2'
'2' --> '3'
'3' --> '1'
'4' --> '5'
'5' --> '4'
other symbols are not to be changed.
• The task: to specialize the permutation when it has just two cycles. The length of the cycles is equal to two. The second cycle has not more restrictions while the first is full known. The string to be replaced is arbitrary.

Example #9 (Permcm) by Alexandr Korljukov:

• Permutation. The permutation is described with cycles. For example, ('123')('45') means that
  '1' --> '2'
'2' --> '3'
'3' --> '1'
'4' --> '5'
'5' --> '4'
other symbols are not to be changed.
• Generalization of a classical Fabc-task.  The start configuration is a composition of three permutations. These permutations are full known. The string to be replaced is unknown.
• If you chouse the lazy driving then you have to expect just one loop in a residual program.

Example #10 (Sum2a) by Alexandr Korljukov:

• To specialize a binary addition w.r.t. the second argument.

Example #11 (Sum2b) by Alexandr Korljukov:

•  To specialize a binary addition w.r.t. the first argument.

Example #12 (Bashe)  by Alexandr Korljukov:

• Specialization of a general form of the Bashe's game when the maximal number of matches to take for one step is equal to one.  

Example #13 (Equal):

• This example demonstrates a use of repeated t-variables in left-hand sides of sentences in a program to be transformed (see  Refal-5: programming guide and reference manual.). 
• Specialization of a concatenation  of results of  two Equal-predicates.

Example #14 (F8_i2a) by Alexandr Korljukov:

• Arithmetic in a finite field. Characteristic  is equal 2. 
• Addition modulo x^3+x+1 (representation:  '1011' == x^3+x+1 ). 
• This example uses a pseudo-comments to declare external executable functions.

Example #15 (F8_i2m) by Alexandr Korljukov:

• Arithmetic in a finite field. Characteristic  is equal 2. 
• Multiplication modulo x^3+x+1 (representation:  '1011' == x^3+x+1 ). 
• This example uses a pseudo-comments to declare external executable functions.

Example #16 (F8_i2i) by Alexandr Korljukov:

• Arithmetic in a finite field. Characteristic  is equal 2. 
• Inversion modulo x^3+x+1 (representation:  '1011' == x^3+x+1 ).
• This example uses a pseudo-comments to declare external executable functions.

Example #17 (Tur_br) by Alexandr Korljukov.  Here the MST-scheme is not full correct. The second level must be just on a single line. Our next version the MST-schemes language allows to write large MST-schemes in some convenient fashion, the available version does not.

•  An inrepreter of  Turing maschine.  Instructions: (s.q  s.b  s.c  s.s  s.r), where
   s.q - a current state,
   s.b - a symbol to observe,
   s.c - a symbol to write on a current position,
   s.s - a direction of shift  ( '<' or '>' ) ,
   s.r - a next state,
   'a'  and  'z' - a start and end state.
• The task: to specialize the interpreter w.r.t. a program which reverses bits ( for example, '1122' ==> '622115' ). The tape is unknown.

Example #18 (Tur_rv)  by Alexandr Korljukov. Here the MST-scheme is not full correct. The second level must be just on  a single line. Our next version the MST-schemes language allows to write large MST-schemes in some convenient fashion, the available version does not.

•  An inrepreter of  Turing maschine.  Instructions: (s.q  s.b  s.c  s.s  s.r), where
   s.q - a current state,
   s.b - a symbol to observe,
   s.c - a symbol to write on a current position,
   s.s - a direction of shift  ( '<' or '>' ) ,
   s.r - a next state,
   'a'  and  'z' - a start and end state.
• The task: to specialize the interpreter w.r.t. a program which checks a bracket's structure
  ( for example, '*()((*' ==> '0(RL*'  (False) , or  '*()()*' ==> '1()()'  (True)). The tape is unknown.

Example #19 (Div3) by Alexandr Korljukov:

• The Divide-function gives a summa of digits of the second argument modulo the first argument. The e.number is a list of decimal digits.
• The task: to specialize the function w.r.t. the modulo. A residual program is exactly the school property of divisiability of numbers by 3:
  3 divides digitN+....+digit0 .
• This example demonstrates  an using  of calls to a image  Const__ -function to protect its argument from generalization.

Example #20 (Div11) by Alexandr Korljukov:

• The Divide-function gives a summa of digits of the second argument modulo the first argument. The e.number is a list of decimal digits.
• The task: to specialize the function w.r.t. the modulo. A residual program is exactly the school property of divisiability of numbers by 11:
  11 divides  digit0+10*digit1+digit2+10*digit3+...
That is equavalent to: 11 divides digit0-digit1+...(-1)^K*digitK+...(-1)^N*digitN .
• This example demonstrates  an using  of calls to a image  Const__ -function to protect its argument from generalization.

Example #21 (Div37) by Alexandr Korljukov:

• The Divide-function gives a summa of digits of the second argument modulo the first argument. The e.number is a list of decimal digits. 
• The task: to specialize the function w.r.t. the modulo. A residual program is exactly the school property of divisiability of numbers by 37:
  37 divides  (a0+10*a1+26*a2)+(a3+10*a4+26*a5)+...
That is equavalent to: 37 divides (digit0+10*digit1-11*digit2)+(digit3+10*digit4-11*digit5)+... .
• This example demonstrates  an using  of calls to a image  Const__ -function to protect its argument from generalization.

Example #22 (Div10) by Alexandr Korljukov:

• The Divide-function gives a summa of digits of the second argument modulo the first argument. The e.number is a list of decimal digits. 
• The task: to specialize the function w.r.t. the modulo. A residual program is exactly the school property of divisiability of numbers by 10:
  10 divides digit0 .
• This example demonstrates  an using  of calls to a image  Const__ -function to protect its argument from generalization.

Example #23 (Div125) by Alexandr Korljukov:

• The Divide-function gives a summa of digits of the second argument modulo the first argument. The e.number is a list of decimal digits. 
• The task: to specialize the function w.r.t. the modulo. A residual program is a property of divisiability of numbers by 125:
  125 divides digit0+10*digit1+100*digit2 .
• This example demonstrates  an using  of calls to a image  Const__ -function to protect its argument from generalization.

Example #24 (Div18) by Alexandr Korljukov:

•  The Divide-function gives a summa of digits of the second argument modulo the first argument. The e.number is a list of decimal digits.
• The task: to specialize the function w.r.t. the modulo. A residual program is a property of divisiability of numbers by 18:
  18 divides digit0+10*(digit1+digit2+...+digitN) .
• This example demonstrates  an using  of calls to a image  Const__ -function to protect its argument from generalization.

Example #25 (Div999) by Alexandr Korljukov:

•  The Divide-function gives a summa of digits of the second argument modulo the first argument. The e.number is a list of decimal digits.
• The task: to specialize the function w.r.t. the modulo. A residual program is a property of divisiability of numbers by 999:
  999 divides (digit0+10*digit1+100*digit2)+(digit3+10*digit4+100*digit5)+... .
• This example demonstrates  an using  of calls to a image  Const__ -function to protect its argument from generalization.

Example #26 (RegeKK) by Arkadij Klimov and  Alexandr Korljukov:

• The Allows-function checks if the second argument belongs to a regular language which is defined with the first argument.
• The task: to specialize the predicate w.r.t. the next language:  'Korlukov' | ('Klimov')^* .
• This example demonstrates a use of external executable ( in supercompile-time ) functions. The functions are declared inside the program to be transformed.

Example #27 (RegeAB) by Arkadij Klimov and  Alexandr Korljukov:

• The Allows-function checks if the second argument belongs to a regular language which is defined with the first argument.
• The task: to specialize the predicate w.r.t. the next language:  (('A')^*  ('B')^*)^* .
• This example demonstrates a use of external executable ( in supercompile-time ) functions. The functions are declared inside the program to be transformed.

Example #28 (Rege12) by Arkadij Klimov and  Alexandr Korljukov:

• The Allows-function checks if the second argument belongs to a regular language which is defined with the first argument.
• The task: to specialize the predicate w.r.t. the next language:  (('A')^* ('1' | '2') ('B')^ *)^* .
• This example demonstrates a use of external executable ( in supercompile-time ) functions. The functions are declared inside the program to be transformed.

Example #29 (RegABi) by Arkadij Klimov and  Alexandr Korljukov:

• The Allows-function checks if the second argument belongs to a regular language which is defined with the first argument.
• The task: to specialize the predicate w.r.t. the next language:  (('A')^* 'B')^* .
• This example demonstrates a use of external executable ( in supercompile-time ) functions. The functions are declared inside the program to be transformed.

Example #30 (RegAB2)  by Arkadij Klimov and  Alexandr Korljukov:

• The Allows-function checks if the second argument belongs to a regular language which is defined with the first argument.
• The task: to specialize the predicate w.r.t. the next language:  (('AB')^* ('AB')^ *)^* .
• This example demonstrates a use of external executable ( in supercompile-time ) functions. The functions are declared inside the program to be transformed.

Example #31 (Formi) by Alexandr Korljukov:

• Arithmetic in an extension of a field.  Let F be a field, P[F] be a ring of polinomials over the field.  The new field can be obtained by extension of the given field  with the roots of some irreducible polinomial. Polinomials are encoded with a sequence of elements from the field.  For example, x^2 - 2 is encoded with (1) (0) ('-' 2). Zero-polinomial is encoded as an empty expression ( nothing ).  The field can be chosen with users.
• Specialization: to create a rule of inversion of rational complex numbers.

Example #32 (Formc) by Alexandr Korljukov:

• Arithmetic in an extension of a field.  Let F be a field, P[F] be a ring of polinomials over the field.  The new field can be obtained by extension of the given field  with the roots of some irreducible polinomial. Polinomials are encoded with a sequence of elements from the field.  For example, x^2 - 2 is encoded with (1) (0) ('-' 2). Zero-polinomial is encoded as an empty expression ( nothing ).  The field can be chosen with users.
• Specialization: to create rules basic arithmetical operations in the field of  rational complex numbers.

Example #33 (Form2) by Alexandr Korljukov:

• Arithmetic in an extension of a field.  Let F be a field, P[F] be a ring of polinomials over the field.  The new field can be obtained by extension of the given field  with the roots of some irreducible polinomial. Polinomials are encoded with a sequence of elements from the field.  For example, x^2 - 2 is encoded with (1) (0) ('-' 2). Zero-polinomial is encoded as an empty expression ( nothing ).  The field can be chosen with users.
• Specialization: to create rules basic arithmetical operations in a field of rational complex numbers of the next form q+p*Sqrt(2),  where q and p are any rational numbers..

Example #34  (Open):

• The example demonstrates a use of open variables  (see  Refal-5: programming guide and reference manual.) as well as a simultaneous  transformation a number of task. 
• The tasks:
  1. Specialization: the first arguments is partly known, the second is unknown.
  2. Specialization: the first arguments is known, the second is unknown. 
  3. Specialization: the first arguments is unknown, the second is partly known.

Example #35 (Search)  by Alexandr Korljukov:

•  A classical task. Specialization of a naive search with respect to a given patter. 
• A residual program is the Knuth-Morris-Pratt algorithm.