3.2 Function Formats

Formally, all Refal functions are functions of one argument. Very often, however, this single argument consists of parts that are essentially sub-arguments (and are usually called simply arguments). When we define a function which is essentially a function of several arguments, we combine these arguments in some way in order to form the single formal argument. This defines the function's format.

When we program in Refal, we are free to choose any formats. In principle, we can separate sub-arguments by some symbols, e.g., commas:

  <F e1','e2>
  <G e1','e2','e3>
 

One disadvantage of this method is that the arguments must be known not to include separators -- in this case, commas. But there is an even more serious objection to such formats: they include open e-variables, which means that the values of the arguments will be scanned even if this is not necessary by the essence of the algorithm. This is why parentheses should be used in formats.

To separate two sub-expressions we need only one pair of parentheses; for three sub-expressions two pairs, etc. However nothing prevents us from enclosing every sub-argument in parentheses. Thus we have considerable freedom in choosing formats:

  <F (e1)e2>        
  <F e1(e2)>
  <F (e1)(e2)>
  <F (e1)(e2)e3>
  <F (e1)e2(e3)>    
etc. We can vary formats by including mnemonic symbols or strings, e.g.:

  <F Graph (e.Gr) Start (e.St) Weights (eW)>
 

It is strongly recommended that the formats of functions, when they are non-trivial, be kept within the program as comments. It is also desirable to indicate the form and the type of the function's value. Although such comments are not necessary (and are usually omitted for simple functions), they greatly improve the readability of the program and are precious in debugging. The exact form of comments is left to the user. In this book we use this form:

  * < Function-name Argument >
  *     ==   Result-1  *     ==   Result-2
   ... etc.
While the equal sign in Refal symbolizes one step of the Refal machine, the double equal tells us what should happen after some unspecified number of steps, e.g., when the computation process is completed. Often the result may have one of several possible forms. If the form of the result is more or less obvious, this part is omitted.

The comments for the definition of the function Cor from Sec. 3.1 could be:

  * <Cor (e.Scanned-already) e.Not-yet-scanned>
  *     ==  e.Corrected
 

The name of a variable, as always in programming, may give an idea of what it is about. In Refal, the names of variables used in different sentences are completely independent; and, of course, the names of variables in comments are of no significance. But it is a good practice to choose names of variables so that they are identical, or at least similar, in different sentences and so that they resemble the names of variables in the formats, even if this is only one letter. Comparing the sentence with the format helps to read the program.

The following exercise gives an example of a function with a more complex format.

Exercise 3.2 Define function <Cut_e1__e2_> , which cuts the expressions e1 and e2 into pieces such that they end with identical terms having identical sequential numbers in their respective expressions. These pieces must be enclosed in parentheses and printed out by pairs. The remaining parts of expressions that do not match should be discarded. For instance, if the two expressions are:

  'abcc++'()'y'('!')'yxrtr'
  'xyzz+'('==')'yy'('!')'**x'(())'pq'
then the printout should be:

  (abcc+)(xyzz+)
  (+()y)((==)yy)
  ((!))((!))
 

In Refal we have no datatypes other than the three syntax categories: a symbol, a term, an expression. The reason is that this makes the language very simple for programming and formal analysis, yet allows us to easily mimic in our simple syntax much of what is done by introducing datatypes. Suppose, for instance, that we want to work with rational numbers, and we represented them by three symbols: the sign, the numerator, and the denominator. We give the name Rat to this data structure, and use it in the form:

  (Rat s.Sign s.Numerator s.Denominator)
We need not associate a special type of variables with this datatype. For `an arbitrary rational number X', we simply write:

  (Rat eX)
An arbitrary negative rational number can be written as:

  (Rat '-'eX)
 

For every datatype it is easy to define access functions that provide for the structure's components, e.g.:

  Numerator { (Rat sS sN sD) = sN}
However, very often we need not use access functions; a direct use of patterns makes the definition both more concise and more clear. For example, the multiplication of rational numbers may be defined as follows:

  Mul{
     (Rat s.S1 s.N1 s.D1)(Rat s.S2 s.N2 s.D2) =
            (Rat <Mul-signs s.S1 s.S2>
                 <* s.N1 s.N2> <* s.D1 s.D2>);
     }
where the function Mul-signs must be defined appropriately. (Here, as above, we leave open the question of how the rational number 0 is represented).