SCP 4 you: MST-schemes Language

MetaSystem Transition schemes Language by Prof. Valentin F. Turchin  (The City College of New York) .

For a description on how use the MST-schemes language, please see a SCP4 User's Guide (in Russian).

Draft

Contents:

• Syntax
• Semantics
  • MST-scheme
  • Simultaneous use of a number of mst-schemes
  • Semantics of the $BASIC declaration
  • Semantics of the $PREPARATORY declaration

Syntax

We suppose the reader knows basic ideas of  Refal programming language.   Type of unterminals ( e,t,s ) are just an additional information about.  

-A- Structure of program:

e.program ::= e.declarations e.mst-scheme e.declarations e.program | e.empty 

e.mst-scheme ::= e.mst ';' 
e.declarations ::= e.declaration e.declarations | e.empty
e.declaration ::= e.basics | e.preparatory | e.user-gereralizaion | e.user-reduce 

e.basics ::= $BASIC e.calls t.call; 
e.calls ::= s.call , e.calls | e.empty t.call ::= <s.function-name e.format>

e.preparatory ::= $PREPARATORY e.function-list;
e.function-list ::= e.function-names s.function-name
e.function-names ::= s.function-name , e.function-names | e.empty

e.format ::= (e.expr) e.format | (e.expr)
e.expr ::= (e.expr) e.expr | t.call e.expr | s.symbol e.expr | t.variable e.expr | e.empty

e.mst ::= (e.mst) e.mst | <Const__ e.obj-expr> e.mst | <UnConst__ e.obj-expr> e.mst | <Appl__ e.obj-expr> e.mst
        | <s.function-name e.mst> e.mst 
/* Here s.function-name is not equal to Const__ , UnConst__ , Appl__ */
        | s.symbol e.mst | t.variable e.mst | e.empty
e.obj-expr ::= (e.obj-expr) e.obj-expr | s.symbol e.obj-expr | e.empty

t.variable ::= t.e-variable | t.s-variable | t.t-variable
t.t-variable ::= 't.' s.index 
    /* Another semantics of the t-variables is allowed:
     * if you use '/t' switch to run the MST4, then the t-variables will be treated
     * as t.t-variable ::= ('e.' s.index) */
t.e-variable ::= 'e.' s.index 
t.s-variable ::= 's.' s.index 

-B-  External basic units:

s.index  ::= s.INTEGER | s.IDENTIFIER
s.number ::= s.INTEGER
s.symbol ::= s.SYMBOL
s.function-name ::= s.IDENTIFIER
            /* Under MS-DOS function names must not exceed 8 characters. */
e.empty ::= /* nothing */


Semantics

Contents:

• MST-scheme
• Simultaneous use of a number of mst-schemes
• Semantics of the $BASIC declaration
• Semantics of the $PREPARATORY declaration

Every program in the MST-schemes language is a sequence of MST-schemes and declarations. The MST-schemes define functions to be transformed by a supercompiler while the declarations are an instructions for the supercompiler. The instructions influence behaviour of  the supercompiler. 

MST-scheme

A MST-scheme describes  a parametrized set of inputs to a given program as well as  a start configuration of  a function composition  (a  state of stack). Domains  of the parametrs  and the function composition define  a function  to be  transformed by a supercompiler. 

The MST-schemes language is a two dimensional  programming language.

•  All blanks in a MST-scheme are meaningful and semantics of  every line from the MST-scheme depends on previous and next lines in the given MST-scheme.  
• Semantics of a given line from a MST-scheme:
  • the line is an object to be transformed by function calls from the previous line (whenever it exist);
  • on the other hand, function calls from  the line are subjects to transform the next line (whenever it exist);

If  there exist  a call to a supercompiler on a given line inside a MST-scheme,  then the supercompiler treats a part from the next line ( those part which exactly under its arguments) as a parametrized set of inputs to a given program. 

There are three types of parametrs -- e-parametrs , t-parametrs and s-parametrs. 

• Domain of an e-parametr is the n-th image of  a fixed function ( meta-coding). The meta-coding function is defined on whole set of the Refal object expressions. Under the n-th  image we mean n-th power of the composition  of the function with itself. For example,  the second image is   
  • <Meta-coding  <Meta-coding e.object-expressions>> 
• Domain of a t-parametr is the n-th image of  a restriction  of the meta-coding function  to the set of  the Refal terms.
• Domain of a s-parametr is the n-th image of  a restriction  of the meta-coding function  to the set of the Refal symbols.

The power of the image depends on syntax the MST-scheme so , in the fact,  every type has  the countable set of  subtypes. If  there are two parametrs with the same types and names, then these parametrs can take just equal values. 

Example #1:

This MST-scheme describes a classical task: to specialize  a  Fab-function when its argument starts with string  'aebfc' while the rest of the argument is unknown and can be any object expression. 

Example #2:

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. 

• A lot of demo-examples of MST-schemes can be found here.
• Our current version of the MST-scheme language describes a MST-scheme without the uppermost level. The level is implicit, because of in the version  the uppermost line is always the same as in the simple example above.
• The version of  the MST-compiler, which now is available  to be downloaded and online-demonstrated, supports just one-level MST-schemes (one level without the uppermost). A whole version of the MST-language will  soon available.

Simultaneous use of a number of mst-schemes

You are welcome to create a number of mst-scheme and transform them simultaneity. That is not the same if you transform the mst-schemes step by step:

• the time of the first transformation can be less of the second way; 
• a residual program can be shorter;
• a residual program can be worse w.r.t. efficiency;

If you permuted the mst-scheme inside a mst-program then you can obtain another residual program.  Parametrs are local inside every mst-scheme. One mst-scheme corresponds to one function definition.

Semantics of the $BASIC declaration

Let we have: 
$BASIC <F1 e.format1>, ... , <FN e.formatN>;
If a stack was generalized to  <G1 e.g-format1> <- e.out; .... <GN e.g-formatN> <- e.out; , then every <Gi e.g-formatI> can be recognized as one from the basic list whenever the basic list contains at least one call of the kind  <Gi e.formatI>.

Semantics of the $PREPARATORY declaration

Let we have:
$PREPARATORY F1 , ..., FN;
then the cutting of two stacks should be with the next method:

Previous stack: top	________	CTX1	rest-context
	|      |	\  |	\
	|      |	| \|	\
	|      |	|  |	\ \
	|      |	|  |	\ \
	|      |	|  |	\ \
Current stack: top	========	RST1	++ CTX1 rest-context

Let CTX1, RST1 be elements of the stacks ( see above ). Let CTX1 be <Fi ... > ( where Fi belongs to F1, ..., FN ) and equal to RST1 in a functional aspect ( function name and path ), then Andrei V. Klimov suggested to move CTX1 and RST1 into the correspond prefixes. The promotion can be done recursively over the context. That is useful when some function's calls prefer to be together.