3.5 Breaking Algorithms into Functions

An algorithm in Refal is a collection of functions. To define a function, we consider different cases of its argument, and write corresponding sentences. This is how a function definition breaks down into sentences. How does an algorithm break down into functions? In the following, we summarize the usual reasons for introducing a new function when we define an algorithm.

1. Consecutive processing

When the operation we want to perform over an object can be defined as a consecutive performance of several operations, we define each of the operations by the corresponding function, e.g.:


  F { eX = <F3 <F2 <F1 eX>>> }
Here the result of one function becomes the argument of another.

2. Parallel processing

When different parts of an object must undergo separate processing, we define functions which are applied to their respective parts, e.g.:


  F { (eX)(eY)eZ = <F1 eX> <F2 eY> <F3 eZ> }
 


 

3. Breaking an expression into parts

As a result of previous steps, we may have a structured object, different parts of which are meant for different uses. For example, the function of integer division </ s.N1 s.N2> produces a combination (s.Quotient)s.Remainder . If we want only the remainder from the division of s.N1 by s.N2 , we call:


  <Rem </ s.N1 s.N2>>
where Rem is defined by:


  Rem { (sQ) eR> = eR }
 

4. Branching on the value of a function

We often wish to evaluate some function F , and then, depending on the result of the evaluation, proceed in one way or another. Then we introduce an auxiliary function F1 , and make the call:


  <F1 <F eX>>
The branching function F1 analyzes the result of Fand makes the required choice. We saw many examples of this.

5. Changing the format

Often we need additional sub-arguments in a function, in order to define a recursive process. Then we define an auxiliary function with the required format. We saw an example above, when we defined the function Cor with the format:


  <Cor (e.Scanned-already) e.Not-yet-scanned>
in order to define the function Correct :


  Correct {
     e1 = <Cor () e1>; }
 

Communication between functions in Refal can be accomplished either through the view field or through direct calls. In the example of consecutive processing above:


  F {eX = <F3 <F2 <F1 eX>>> }
we have used communication through the view field. Each of the three functions, F1 etc., knows nothing about the others. It leaves its value in the view field, and the next function takes it up. The alternative is to define F through a system of direct calls. F itself simply calls F1 :


  F { eX = <F1 eX> }
The definition of F1 must be modified now. In the non-recursive sentences, where the former definition of F1 finished the work with an expression . as the final result, the new definition should finish with <F2_.> . The definition of F2 should be modified in the same manner.

Communication through the view field has the advantage of making the function definitions independent of their use, so that they can be used in other contexts too. Also, with this method we can build up the final result of the function right in the view field, e.g., by the scheme we have already used (see functions Chpm , Blanks , etc.):


  F {... =  E  <F ...> }where E is some expression. This scheme can be varied:


  F {... = <F ...> E }or


  F {... = E1 (<F ...>) E 2 }etc. With direct calls of successors, this is impossible. On the other hand, direct calls are handy when a function has different successors in different sentences.