4.3 The Bury-Dig Functions

Refal is a strict functional language. But as a concession to the more traditional way of programming, we still have a few built-in functions which allow the user to make assignments. It is not recommended - and, in fact, there is no need - to use them for object manipulation. But sometimes it is desirable to maintain some global parameters or tables without carrying them over as part of the argument from one function call to another. Then we can ``bury'' such parameters under assigned names by activating expressions of the form:

  (*)       <Br N '=' E>
When we need such a parameter, we ``dig'' it up by
  (**)      <Dg N>
Here N stands for a string of characters not including '=' and E for any expression.

When (*) is evaluated, it disappears from the view field, but the expression E stays where it is in the actual linked structure representing the view field. Its location is associated with the string N and kept in a table. Therefore, the evaluation of Br takes a small constant time, no matter how big E. When (**) is evaluated, it is replaced by the buried expression - again, without going through it, but only by relinking its ends. There is also a copying function Cp which has the same format and the value as Dg , but where the buried expression is copied, not extracted. When used repeatedly, Br and Dg create a stack of buried values for each name. Function Br buries each next value for a given name without touching the previous values. Function Dg extracts the last buried value. Thus these functions operate as stacks of values for each used name. However, if the stack for a given name is empty, the result of Dg is empty, not undefined, as it should be for a usual stack. This deviation from the strict semantics of stacks has been found useful in practice.

Suppose that we are writing a program which deals with some objects and from time to time generates new objects of the same kind. We want a unique index to be attached to each object. We assign consecutive numbers to them, startind with 1. The function which generates new objects must have access to the first free index. It can be kept buried under some name, say 'fr-ind' . Then at the start of the program, e.g., as a part of the right side of Go , we execute:

  <Br 'fr-ind=' 1>  
Whenever it is necessary to produce a new index, we use:
  <Next 'fr-ind'> 
as such an index. The function Next yields the number buried under its argument and increments it by 1 :
  Next { 
     e.Name, <Dg e.Name>: e.Value  =
             e.Value  
             <Br e.Name'=' <+ e.Value 1>>; }

In Section 2.1 we wrote a program translating lines of Italian words into English. We used the function Table to store the translation table (dictionary):

  * Italian-English dictionary table
  Table { = (('cane') 'dog')
            (('gatto') 'cat')
            (('cavallo') 'horse')
            (('rana') 'frog')
            (('porco') 'pig')   }
Instead of keeping this table as the right side of a sentence, we could keep it as an expression buried under some name, say 'dict' .

Expressions buried by Br are kept in the form of doubly-linked lists, as are all expressions in the view field. In contrast, the right sides of sentences are stored in the form of a code in the language RASL. The latter is much more compact than the former. However, a buried expression is ready for use, while the right side of a sentence such as that for Table will be read by the Refal machine symbol by symbol in the process of creating the corresponding doubly-linked list in the view field. Therefore, when space is critical, it is preferable to keep a table as the right side of a sentence; but if time is more important, the table should be kept buried.

Let us modify our Italian-English translator so that the table is kept buried. The first thing to do is to modify the function Go to do the burying at the beginning of work:

  * This program translates from Italian into
  * English and keeps the dictionary buried.
  $ENTRY Go { =  <Br 'dict='
            (('cane') 'dog')
            (('gatto') 'cat')
            (('cavallo') 'horse')
            (('rana') 'frog')
            (('porco') 'pig') 
                   >
                   <Job <Card>>    }

Now we must correspondingly modify the use of the table. The simplest way to do it is to redefine only one function, Table , so that it copies the dictionary table:

  Table { = <Cp 'dict'>; }
However, this is no better than keeping the table in a sentence, because before using the table the Refal machine will have to make a second copy of it -- with the inevitable consequences for time and space. To use a buried table efficiently, we must define the process so that the very copy that was buried is used and is then reburied unaltered.

Thus we replace the calls of <Table> , which occur in Trans-line , by <Dg 'dict'> :

  * Translate one line
  Trans-line {
     ' 'eX = <Trans-line eX>; 
     e.Word' 'e.Rest = 
            <Trans (e.Word) <Dg 'dict'>>' '
            <Trans-line e.Rest>;
      =  ;
     e.Word = <Trans (e.Word) <Dg'dict'>>' ';
             }
The whole dictionary table will now be in the argument of Trans . We modify Trans so that it reburies the table after use:
  * Translate Italian word into English by table
  Trans { 
      (e.It) e1 ((e.It)e.Eng) e2 = 
           e.Eng <Br 'dict=' e1 ((e.It)e.Eng) e2>; 
      (e.It) e1 = 
           ***<Br 'dict=' e1>; 
                 /* the word not in table */
        }

One of the advantages of keeping tables buried is that they can be easily updated at run time.

Exercise 4.5 Modify the Italian-English translator so that the dictionary is permanently stored on the disk as the file DICT . At the beginning of work the program asks the user to make (possible) additions to the dictionary table. The user enters the additions, the program updates the file and then works as before.