1.6 More Examples of Functions

Example 1. Change pluses to minuses

Suppose we want a function which works on strings of symbols and converts every '+' into '-' . First define the algorithm verbally:

1. Take the first symbol of the argument. If it is '+' , replace it by '-' . Now apply the transformation to the remaining part of the argument so that the result will be concatenated to the symbol '-' .
2. If the first symbol is not '+' , leave it as it is and apply transformation to the remaining part, as in case 1.
3. If the string is empty, the outcome is empty. End of job.

Now we put it in Refal. Let the function name be Chpm :

  * Chpm, Change Plus to Minus
  Chpm {
  *1.Symbol '+' encountered.Replace by '-':
     '+' e.1 = '-' <Chpm e.1>;
  *2.Any symbol distinct from '+':
     s.2 e.1 = s.2 <Chpm e.1>;
  *3.Empty string:
      =  ; 
        }

This is the computation history if the argument of Chpm is 'ab+c-+d' :

  <Chpm 'ab+c-+d'>
  'a'<Chpm 'b+c-+d'>
  'ab'<Chpm '+c-+d'>
  'ab-'<Chpm 'c-+d'>
  'ab-c'<Chpm '-+d'>
  'ab-c-'<Chpm '+d'>
  'ab-c--'<Chpm 'd'>
  'ab-c--d'<Chpm >
  'ab-c--d';

  Chpm { 
     e.1 '+' e.2 = e.1 '-' <Chpm e.2>;
     e.1 = e.1; }

  <Chpm 'ab+c-+d'>
  'ab-'<Chpm 'c-+d'>
  'ab-c--'<Chpm 'd'>
  'ab-c--d'

Example 2. Factorial

Let us define the factorial function on non-negative whole numbers in Refal. Arithmetic functions in Refal (see Chapter 2 and Reference Section C) have the names Add , Sub , Mul , Div . They can also be represented by the symbols + , - , * , and / , respectively.

  Fact { 0 = 1;
         s.N = <* s.N <Fact <- s.N 1>>>; }

Here is the computation of <Fact 3> :

  <Fact 3>
  <* 3 <Fact <- 3 1>>>
  <* 3 <Fact 2>>
  <* 3 <* 2 <Fact <- 2 1>>>>
  <* 3 <* 2	<Fact 1>>>
  <* 3 <* 2	<* 1 <Fact <- 1 1>>>>>
  <* 3 <* 2	<* 1 <Fact 0>>>>
  <* 3 <* 2	<* 1 1>>>
  <* 3 <* 2	1>>
  <* 3 2>
  6

Example 3. Translate a word

Functions are sometimes defined by a table. Suppose we want to translate Italian words into English. We should, of course, separate the definition of the table from the definition of the function which does translation using the table. Let the former be Table -- a function of no variables which returns the table. Let the latter be Italian , a function of one variable, the Italian word to translate. We immediately figure out that the function which actually uses the table must have it among its arguments. Therefore we introduce the function Trans of two arguments, which we shall call in the format:

<Trans (e.Word) e.Table>

The parentheses separate the first argument, the word to translate, from the second argument, the table to use. We now can define Ital-Engl as calling Trans :

  * Translate an Italian word into English
  Ital-Engl { e.W = <Trans (e.W) <Table>>; }

The format of the table should be such that the necessary word could be found using a simple and efficient pattern. A table for five Italian words may look as follows:

  Table { = (('cane') 'dog')
            (('gatto') 'cat')
            (('cavallo') 'horse')
            (('rana') 'frog')
            (('porco') 'pig') 
        }

With a table of this format, the definition of the function Trans is:

  * Translate a word by table
  Trans { 
     (e.Word) e.1 ((e.Word) e.Trans) e.2 = e.Trans;
     (e.Word) e.1  =  '***';  }

  x + 0 = x 
  x + y' = (x + y)'