tech-invite   World Map     

3GPP     Specs     Glossaries     Architecture     IMS     UICC       IETF     RFCs     Groups     SIP     ABNFs       Search

RFC 0610

 
 
 

Further datalanguage design concepts

Part 3 of 3, p. 60 to 88
Prev RFC Part

 


prevText      Top       Page 60 
The primitives discussed so far (assign, listops, and get/struct/member)
provide a basic facility for operating on structures of LISTs, STRUCTs
and elementary items.  Using only them, it is possible to transfer the
contents of one hierarchical structure to another, to append structures,
to delete portions of structures, and so on.  To perform more
interesting operations facilities for control and selection are needed.

A rudimentary control facility is provided through the primitives
if/then, if/then/else, till and while.  All of these evaluate one
primitive function call, which must return a BOOL.  Based on the value
of this BOOL some action is taken.

Let A and B be function calls.  If/then(A,B) will execute B if A returns
TRUE.  If/then/else(A,B,C) will execute B if A returns TRUE; it will
execute C if A returns FALSE.  The while and till operators iterate,
executing first A then B. While terminates the loop when A returns
FALSE; till terminates the loop when A returns TRUE.  If this happens
the first time, B is never executed.

So far, we have mentioned one function which returns a BOOL: the listop,
end/of/list.  Two other classes of functions which have this property
are the booleans and the comparisons.  There are 3 primitive booleans
(and, or, not) and six primitive comparisons (equal, less/than,
greater/than, not/equal, less/than/or/equal, greater/than/or/equal --
only equal is implemented at time of publication).

The booleans input and output BOOLs; the comparisons input pairs of
elementary objects having the same description and output BOOLs.
Expressions composed of booleans and comparisons on item contents are
one of the principal tools used in selectively referencing data in data
management systems.

With the booleans, the comparisons, and the primitives identified
earlier, we can perform selective "retrievals".  That is, we can
transfer to LIST B all items in LIST A having a value of 'ABC'.  In
fact, we now have a (semantically) general ability to perform content-
based retrievals and updates on arbitrary hierarchical structures.  We
can even program something as complex as the processing of a list of
transactions against a master list, which is one of the typical
applications in business data processing.

Of course, we would not expect users of datalanguage to express requests
at the level of listops.  Further, the listops defined here are not a
very efficient way of performing some of the tasks we have mentioned.
To get good solutions, we need both higher-level operators and other
primitives which use other techniques in processing.

In addition to those already discussed, the model contains functions

Top       Page 61 
for: (1) referencing an object by qualified name, (2) generating a
constant, (3) generating data descriptions, (4) writing compound
functions and blocks with local variables, (5) creating objects.

The facilities for generating constants and data descriptions (which are
a special case of constants) are marginal, and have no features of
special interest. Obviously, data description will be an important
concern in the modeling effort later on.

Object referencing functions permit reference to t/objects and p/objects
(these terms are defined in 4.6).  A p/object is referenced by giving
the pathname from STAR to it.  A t/object is referenced by giving the
pathname from the block directory in which it is defined to it.

Compound/function permits a sequence of function calls to be treated
syntactically as a single call.  Thus, for example, in if/then(A,B), B
is frequently a call to compound/function, which in turn calls a
sequence of other functions.

Create takes two inputs: a superior object and a description.  The
superior must be a directory.  The new object is created as the leftmost
child of the directory; its name is determined by the description.


4.8 Details of primitive language functions

This section provides specifications for the primitives discussed in the
previous section.  We are still omitting details when we judge them to
be of no general interest; the objective is to provide enough
information for the reader to examine examples.

Most of the primitives occur at two levels in the model.  The internal
primitives are called i/functions and the external, or language
primitives are called l/functions.  The relationship between the two
types are explained in 4.9. In this section we discuss i/functions.

L/functions input and output _forms_, which are tree structures whose
terminal nodes are atoms.  The atoms are such things as function names,
object names, literal string constants, truth va1ues and delimiters.
Calls to i/functions are also expressed as forms.

Any form can be evaluated, yielding some object.  A form which is an
i/function call yields the value returned by the i/function: another
form.  In general, the form returned by an i/function call will, when
evaluated, yield a datalanguage object (that is, the sort of object we
have been represented by an "object box" in the drawings).

Top       Page 62 
4.8.1 Name recognition functions

These return a form which evaluates to an object.

L/TOBJ

Input must name a temporary object subordinate either to TOP/LEVEL or a
block directory.

L/POBJ

Input must name a permanent object (i.e., an object subordinate to
STAR).

Typical calls are L/POBJ(X.Y.Z) and L/TOBJ(A).


4.8.2 Constant generators

Each of these inputs an atomic symbol yielding a value for a constant to
be created.  Each returns a form which will evaluate to an object having
the specified value and an appropriate description.

LC/STRING - a typical call is LC/STRING('ABC')

LC/BOOL - a typical call is LC/BOOL(TRUE)


4.8.3 Elementary item functions

These input and output forms evaluating to elementary objects (objects
which can have no subordinate object -- in effect, objects whose value
is regarded as atomic).  Eventually all the comparison operators will be
implemented.

L/ASSIGN

Inputs must evaluate either to STRINGs or BOOLs. Outputs a form which
transfers the value of the second to the first.  Typical call:
    L/ASSIGN(L/TOBJ(A),LC/STRING('XYZ'))
The output form, when evaluated, will copy 'XYZ' into A's value.

L/EQUAL

Inputs a pair of forms evaluating to objects, which must have identical
descriptions and be BOOLs or STRINGs.  Returns a form evaluating to an
object of type BOOL.  Value of this object is TRUE if inputs have
identical descriptions and values; otherwise it is false. Typical call:

Top       Page 63 
    L/EQUAL(L/TOBJ(X),LC/STRING('DEF'))

L/AND, L/OR, L/NOT

The standard boolean operators.  Inputs are forms evaluating to BOOLs;
output is a form evaluating to a BOOL.  L/AND and L/OR take two inputs;
L/NOT one.  Typical call:
    L/AND( L/EQUAL(L/TOBJ(X),LC/STRING('DEF')),
                   L/EQUAL(T/TOBJ(Y),LC/STRING('GHI')) )
The form returned will, when evaluated, return TRUE if both X has value
'DEF' and Y has value 'GHI'.


4.8.4 Data description functions

These all return a form evaluating to a description (i.e. that which is
represented in our drawings by a box labeled "description").

LD/STRING

Inputs 3 parameters specifying the name, size option and size for the
string. Typical call:
    LD/STRING(X,FIXED,3)
This call returns a form evaluating to a description for a fixed-length
3-character string named X.

LD/LIST

Inputs two forms.  The first is the name of the LIST and the second
evaluates to a description of the LIST member.  Typical call:
    LD/LIST(L,LD/STRING(M,FIXED,3))
Creates the structure shown in figure 4-11, and returns a form
evaluating to the description represented by the upper box.

Top       Page 64 
               _________________
              |  _____________  |
              | |      L      | |
              | |_____________| |
              |  NAME           |
              |  _____________  |
              | |     LIST    | |
              | |_____________| |
              |  TYPE           |
              |  _____________  |
              | |             | |
              | |________|____| |
              |  CHILD   |      |
              |__________|______|
             DESCRIPTION |
                         |
               __________V______
              |  _____________  |
              | |      M      | |
              | |_____________| |
              |  NAME           |
              |  _____________  |
              | |    STRING   | |
              | |_____________| |
              |  TYPE           |
              |  _____________  |
              | |  _________  | |
              | | |  FIXED  | | |
              | | |_________| | |
              | |  _________  | |
              | | |    3    | | |
              | | |_________| | |
              | |_____________| |
              |  PARAMETERS     |
              |_________________|
               DESCRIPTION

                              Figure 4-11
                      LIST and member descriptions



LD/STRUCT

Inputs a form to use as the name for the STRUCT and one or more forms
evaluating to descriptions; these are taken as the descriptions of the
members.  Typical call:

Top       Page 65 
    LD/STRUCT(R,
            LD/STRING(A,FIXED,3)
            LD/BOOL(B) )
produces the structure shown in 4-12; returns a form evaluating to the
top box.


               _________________
              |  _____________  |
              | |      R      | |
              | |_____________| |
              |  NAME           |
              |  _____________  |
              | |    STRUCT   | |
              | |_____________| |
              |  TYPE           |
              |  _____________  |
              | |             | |
              | |_________|___| |
              |  CHILD    |     |
              |___________|_____|
             DESCRIPTION  |
                          |
               ___________V_____
              |  _____________  |
              | |      A      | |
              | |_____________| |
              |  NAME           |
              |  _____________  |
              | |    STRING   | |
              | |_____________| |
              |  TYPE           |        _________________
              |  _____________  |       |  _____________  |
              | |             | |       | |      B      | |
              | |_____________| |       | |_____________| |
              |  PARAMETER      |       |  NAME           |
              |  _____________  |       |  _____________  |
              | |         ____|_|______\| |    BOOL     | |
              | |_____________| |      /| |_____________| |
              |  SIBLING        |       |  TYPE           |
              |_________________|       |_________________|
               DESCRIPTION               DESCRIPTION

                              Figure 4-12
                     STRUCT and member descriptions

Top       Page 66 
LD/BOOL, LB/DIR, LD/OPD, LD/FUNC, LD/DESC

Each inputs a name and produces a single description; each returns a
form evaluating to the description produced.  Typical call:
    LD/BOOL(X)


4.8.5 Data creation

L/CREATE

Inputs two forms and evaluates them.  First must yield an object of type
DIR; second must yield a description for the object to be created.
Creates the object and returns a form, which, when evaluated, will
generate a value for the new object.  A simple example:
    L/CREATE(L/TOBJ(X),LD/B0OL(Y))

Figure 4-13 shows the directory X before execution of the above call. It
contains only an OPD.  After execution, the directory appears as in 4-
14. Creation of a value for Y occurs when the form returned by L/CREATE
is evaluated (covered in section 4.9).

Top       Page 67 
                _________________
               |                 |
               |  _____________  |
               | |      X      | |
               | |_____________| |
               |  NAME           |        ____________
               |  _____________  |       |  ________  |
               | |         ____|_|______\| |   DIR  | |
               | |_____________| |      /| |________| |
               |  DESCRIPTION    |       |  TYPE      |
               |  _____________  |       |____________|
               | |             | |        DESCRIPTION
               | |_________|___| |
               |  CHILD    |     |
               |___________|_____|
                OBJECT     |
                           |
                           |
                ___________V_____
               |                 |
               |  _____________  |
               | |      Z      | |
               | |_____________| |
               |  NAME           |        ____________
               |  _____________  |       |  ________  |
               | |         ____|_|______\| |  OPD   | |
               | |_____________| |      /| |________| |
               |  DESCRIPTION    |       |  TYPE      |
               |  _____________  |       |____________|
               | |             | |        DESCRIPTION
               | |_________|___| |
               |  VALUE    |     |        ____________
               |___________|_____|       |            |
                OBJECT     |____________\|            |
                                        /|____________|
                                          OPD

                              Figure 4-13
                      X and Z before creation of Y

Top       Page 68 
 _________________
|  _____________  |
| |      X      | |
| |_____________| |        _________________
|  NAME           |       |  _____________  |
|  _____________  |       | |     DIR     | |
| |         ____|_|______\| |_____________| |
| |_____________| |      /|  TYPE           |
|  DESCRIPTION    |       |_________________|
|  _____________  |        DESCRIPTION
| |             | |
| |_________|___| |
|  VALUE    |     |
|___________|_____|
 OBJECT     |
 ___________V_____
|  _____________  |
| |      Y      | |
| |_____________| |        _________________
|  NAME           |       |  _____________  |
|  _____________  |       | |     BOOL    | |
| |         ____|_|______\| |_____________| |
| |_____________| |      /|  TYPE           |
|  DESCRIPTION    |       |_________________|
|  _____________  |        DESCRIPTION
| |             | |
| |_____________| |
|  VALUE          |
|  _____________  |
| |         ____|_|______________
| |_____________| |              |
|  SIBLING        |              |
|_________________|        ______V__________         _________________
       OBJECT             |  _____________  |       |  _____________  |
                          | |      Z      | |       | |     OPD     | |
                          | |_____________| |    __\| |_____________| |
                          |  NAME           |   |  /|  TYPE           |
                          |  _____________  |   |   |_________________|
                          | |         ____|_|___|    DESCRIPTION
                          | |_____________| |
                          |  DESCRIPTION    |
                          |  _____________  |        _________________
                          | |         ____|_|______\|                 |
       Figure 4-14        | |_____________| |      /|_________________|
    X, Y, and Z after     |  VALUE          |        OPD
        L/CREATE          |_________________|
                           OBJECT

Top       Page 69 
4.8.6 Control

L/IF/THEN, L/IF/THEN/ELSE

Used to request conditional evaluation of a form. Typical call:
    L/IF/THEN(L/EQUAL(L/TOBJ(A),LC/STRING('ABC'),
            L/ASSIGN(L/TOBJ(B),LC/STRING('DE')))
The form returned will do the following, when evaluated: if A has value
'ABC', then store 'DE' in the value of B.

L/WHILE, L/TILL

These iterate conditionally, as explained in the previous section.
Examples appear later.

L/CF

Compound function: it inputs one or more forms and returns a form which,
when evaluated, will evaluate each input in sequence.  Typical call:
    L/CF(L/ASSIGN(L/TOBJ(R.A),LC/STRING('XX')),
            L/ASSIGN(L/TOBJ(R.B),LC/STRING('YY')))
When the output of L/CF is evaluated, it will assign new values to R.A
and R.B.


4.8.7 Listops

These primitives are executed in sequences in order to perform
operations on LISTs.  With the exception of L/END/OF/LIST these
functions output forms which are evaluated for effect only; that is, the
output forms do not themselves return values.

L/LISTOP/BEGIN

Inputs forms evaluating to: (1) a LIST, (2) an object to represent the
current LIST member, (3) an OPD.  Also, inputs a list of atomic forms
whose values are taken as suboperations to enable. Typical call:
    L/LISTOP/BEGIN(L/POBJ(F),L/TOBJ(R),
                    L/TOBJ(OPF),ADD,DELETE)
This returns a form that will initialize a sequence of listops to be
performed on F.  Caller has previously created R and OPF. He intends to
ADD and DELETE list members.

All subsequent calls in this sequence of listops need specify only the
OPD and auxiliary parameters.

Top       Page 70 
L/LISTOP/END

Inputs a form evaluating to an OPD.  Outputs a form which, when
evaluated, clears OPD and breaks relationships between OPD, LIST and
member objects.

L/WHICH/MEMBER

Inputs two forms.  First evaluates to an OPD; second is one of FIRST,
LAST, NEXT. The form output, when evaluated, will establish a new
current member for the next suboperation.  Note: this does not make the
value of the member accessible, it simply identifies it by setting the
instance number in the OPD.  A typical call:
    L/WHICH/MEMBER(L/TOBJ(OPF),NEXT)
When a which/member causes advance beyond the end of the list, a flag is
set in the OPD.

L/END/OF/LIST

Inputs a form evaluating to an OPD.  Outputs a form which, when
evaluated, returns a BOOL.  This has value TRUE if the end of list flag
in the OPD is on.

L/OPEN/MEMBER

Inputs a form evaluating to an OPD and a form which must be one of ADD,
DELETE, GET, CHANGE.  Outputs a form which, when evaluated, will
initiate the requested suboperation on the current LIST member.  The
suboperation always establishes the pointer from the member object to
the current member value instance.  In addition, in the case of ADD this
value must be created.  Typical call:
    L/OPEN/MEMBER (L/TOBJ (OPF) ,ADD)

L/CLOSE/MEMBER

Inputs a form evaluating to an OPD.  Outputs a form which, when
evaluated, will complete the suboperation in progress.  A typical call:
    L/CLOSE/MEMBER(L/TOBJ(OPF))
Always clears the pointer from member object to member value.  In
addition, in the case of DELETE, removes the member value from the LIST.
In the case of ADD enters the member value in the LIST.  Makes the
member added the current member, so that a sequence of ADDs executed
without intervening which/members will add the new members in sequence.

An elaborate example, involving listops and several other primitives,
appears in section 4.10.

Top       Page 71 
4.9 Execution cycle

The model datacomputer has a two-part execution cycle: it first compiles
requests, then interprets them.  A "request" is an l/function call;
"compilation" is the aggregate result of executing all the l/function
calls involved in the request (typically this is many calls, as there
are usually several levels of nested calls, with the results of the
inner calls being delivered as arguments to the next level of calls).
Usually, the process of executing an l/function involves a simple macro
expansion, preceded by some binding, checking and (eventually)
optimization.

The compiled form consists wholly of atomic symbols and i/function
calls.  The i/functions are internal primitives which input and output
datalanguage objects (the entities represented by the boxes labeled
"object" in the drawings).

Each of the l/functions discussed compiles into a single i/function;
thus the macro expansion aspect of compilation is presently trivial.
However, this will not be true in general; it is only that these are
_primitive_ l/functions that makes it true now.

The decision to use a compile-and-interpret cycle calls for some
explanation.  The way to understand this, is to think in terms of the
functions that would be performed in a strictly interpretive system.
There would still be a requirement to perform global checks on the
validity of the request in advance of the execution of any part of it.
This is because partial execution of an incorrect request can leave a
database in an inconsistent state; if this is a large or complex
database, the cost of recovery will be considerable.  Thus it pays to do
as much checking as is possible; when the system is fully developed,
this will include a certain element of simple prediction of execution
flow; in any case, much more than syntactic checking is implied.

Since any such global checks will be performed in advance of actual
execution, they are effectively not part of the execution itself, for
any given form.  By performing them as part of a separate compilation
process, we only formalize a modularity which already effectively
exists.

There will still be cases, however, in which checking, binding and
optimization functions must be executed during interpretation, if at
all.  This will occur when the information needed is not available until
some of the data has been accessed. When practical, we will provide for
such occurrences by designing most functions so that they can be
executed as part of either "half" of the cycle.

As the model develops, we expect to get a better feel for this problem;

Top       Page 72 
it is certainly reasonable to end up with a structure in which there are
many cycles of compilation and interpretation, perhaps forming a
structure in which nesting of cycles within cycles occurs.


4.10 Examples of operations on LISTs

Here we develop an example of an operation on a LIST using primitive
l/functions.  We first show the function calls required to create a LIST
named F and give it a few member values.  We then selectively copy
certain members to a second LIST G.

To create F:

L/CREATE("STAR",LD/LIST(F,
                        LD/STRUCT(R,
                                LD/STRING(A,FIXED,2),
                                LD/STRING(B,FIXED,2))))

This creates F as a member of the permanent directory STAR (see section
4.6 for details about STAR).  The symbol STAR has a special status in
the "language", in that it is one of the few atomic symbols to evaluate
directly to an object.  (Recall that most permanent objects are
referenced through a call to L/POBJ; reserving the symbol STAR is
equivalent to reserving STAR as a name and writing L/POBJ(STAR).  The
solution we choose here is easier to write.)  Execution of this call
builds the structure shown in 4-15 (except for STAR, which existed in
advance of the call).  The value initially created for F is an empty
LIST--a LIST of zero members.

Top       Page 73 
 _________________         _________________
|  _____________  |       |  _____________  |
| |     STAR    | |       | |      F      | |
| |_____________| |       | |_____________| |
|  NAME           |       |  NAME           |
|  _____________  |       |  _____________  |
| |             | |       | |     LIST    | |
| |_________|___| |       | |_____________| |
|  CHILD    |     |       |  TYPE           |
|___________|_____|       |  _____________  |
 OBJECT     |             | |             | |
            |             | |___________|_| |
 ___________V_____     __\|  CHILD      |   |
|  _____________  |   |  /|_____________|___|
| |      F      | |   |    DESCRIPTION  |
| |_____________| |   |                 |
|  NAME           |   |    _____________V___
|  _____________  |   |   |  _____________  |
| |         ____|_|   |   | |      R      | |
| |_____________| |___|   | |_____________| |
|  DESCRIPTION    |       |  NAME           |
|  _____________  |       |  _____________  |
| |             | |       | |    STRUCT   | |
| |_________|___| |       | |_____________| |
|  VALUE    |     |       |  TYPE           |
|___________|_____|       |  _____________  |
 OBJECT     |             | |             | |
            |             | |___________|_| |
 ___________V_____        |  CHILD      |   |
|                 |       |_____________|___|
|                 |        DESCRIPTION  |
|_________________|        _____________V___
 VALUE                    |  _____________  |
                          | |      A      | |
                          | |_____________| |
                          |  NAME           |       _________________
                          |  _____________  |      |  _____________  |
                          | |    STRING   | |      | |      B      | |
                          | |_____________| |      | |_____________| |
                          |  TYPE           |      |  NAME           |
                          |  _____________  |      |  _____________  |
                          | |         ____|_|_____\| |  STRING     | |
       Figure 4-15        | |_____________| |     /| |_____________| |
   F immediately after    |  SIBLING        |      |  TYPE           |
        creation          |_________________|      |_________________|
                           DESCRIPTION              DESCRIPTION

Top       Page 74 
To add members to F, we need to use listops, and for this we must create
two more objects: an object to represent the current member and an
operation descriptor (OPD).  These are temporaries rather than permanent
objects; they are also "top level" (i.e., not local to a request).
Temporary, top level objects are created as members of the directory
TOP/LEVEL. The calls to create them are:
    L/CREATE(L/TOBJ(TOP/LEVEL),
                    LD/STRUCT(M,
                            LD/STRING(A,FIXED,2),
                            LD/STRING(B,FIXED,2)))
    L/CREATE(L/TOBJ(TOP/LEVEL),LD/OPD(OPF))
We create M to represent the current member; its description is the same
as the one input for a member of F (see the call which created F). The
proper way to accomplish this is with a mechanism which shares the
actual LIST member description with M; however, this mechanism does not
yet exist in our model.

We now wish to add some data to F; each member will be a STRUCT
containing two two-character STRINGs.

To begin the listop sequence:
    L/LISTOP/BEGIN(L/POBJ(F),L/TOBJ(M),
                            L/TOBJ(OPF),ADD)
This call establishes the structure shown in figure 4-16. It initializes
the OPD, making it point to F and M and recording that only the ADD
suboperation is enabled.

Top       Page 75 
 _________________         _________________
|  _____________  |       |  _____________  |
| |     STAR    | |       | |     OPF     | |
| |_____________| |       | |_____________| |
|  NAME           |       |  NAME           |
|  _____________  |       |  _____________  |
| |             | |       | |             | |
| |_________|___| |       | |_______|_____| |
|  CHILD    |     |       |  VALUE  |       |
|___________|_____|       |_________|_______|
 OBJECT     |              OBJECT   |
 ___________V_____         _________V______
|  _____________  |       |  _____________  |
| |      F      | |/______|_|____         | |
| |_____________| |\      | |_____________| |
|  NAME           |       |  LIST           |
|  _____________  |       |  _____________  |
| |             | |       | |             | |
| |_________|___| |       | |________|____| |
|  VALUE    |     |       |  MEMBER  |      |
|___________|_____|       |__________|______|
 OBJECT     |              VALUE     | OPD
            |              __________V______
 ___________V_____        |  _____________  |
|                 |       | |      M      | |
|       LIS       |       | |_____________| |
|_________________|       |  NAME           |
 VALUE                    |  _____________  |
                          | |             | |
                          | |________|____| |
                          |  CHILD   |      |
                          |__________|______|
                           OBJECT    |
                           __________V______        _________________
                          |  _____________  |      |  _____________  |
                          | |      A      | |      | |      B      | |
                          | |_____________| |      | |_____________| |
                          |  NAME           |      |  NAME           |
                          |  _____________  |      |  _____________  |
                          | |         ____|_|_____\| |             | |
                          | |_____________| |     /| |_____________| |
                          |  SIBLING        |      |                 |
                          |_________________|      |_________________|
                           OBJECT                   OBJECT

                              Figure 4-16
                   F, OPF and M after L/BEGIN/LISTOP

Top       Page 76 
Next we must establish a current member.  We want to add members to the
end (in this case, adding them anywhere would get the same effect, since
the LIST is empty), which is done by making LAST the current member.
    L/WHICH/MEMBER(L/TOBJ(OP1),LAST)

Now, to add a new member to F, we can execute the following:
    L/OPEN/MEMBER(L/TOBJ(OPF),ADD)
    L/ASSIGN(L/TOBJ(M.A),LC/STRING('AB'))
    L/ASSIGN(L/TOBJ(M.B),LC/STRING('CD'))
    L/CLOSE/MEMBER(L/TOBJ(OPF))

L/OPEN/MEMBER creates a STRUCT value for M.  It does not affect the
value of F.  Each member of the STRUCT value is initialized when the
STRUCT is created.  The result is shown in 4-17; notice that the STRUCT
member values are as yet unrelated to the objects M.A and M.B.

Figure 4-18 shows the changes accomplished by the first L/ASSIGN; the
pointer from the object M.A to the value was set up by a
GET/STRUCT/MEMBER compiled by L/TOBJ(M.A).  The value was filled in by
the assign operator.  The second assign has similar effect, filling in
the second value.  The call to L/CLOSE/MEMBER takes the value shown for
M in 4-18 (with the second member value filled in) and adds it to the
value of F.  The result is shown in 4-19; compare with 4-16.

Top       Page 77 
       _________________         _________________
      |  _____________  |       |  _____________  |
      | |      M      | |       | |    STRUC    | |
      | |_____________| |       | |_____________| |
      |  NAME           |       |  TYPE           |
      |  _____________  |       |  _____________  |
      | |         ____|_|______\| |             | |
      | |_____________| |      /| |__________|__| |
      |  DESCRIPTION    |       |  CHILD     |    |
      |  _____________  |       |____________|____|
 _____|_|____         | |        DESCRIPTION |
|     | |_____________| |                    |
|     |  VALUE          |        ____________V____
|     |  _____________  |       |  _____________  |
|     | |             | |       | |    STRING   | |
|     | |_________|___| |       | |_____________| |
|     |  CHILD    |     |   ___\|  TYPE           |        _____________
|     |___________|_____|  |   /|  _____________  |       |  _________  |
|      OBJECT     |        |    | |         ____|_|______\| | STRING  | |
|                 |        |    | |_____________| |      /| |_________| |
|      ___________V_____   |    |  SIBLING        |       |  TYPE       |
|     |  _____________  |  |    |_________________|       |_____________|
|     | |      A      | |  |     DESCRIPTION           DESCRIPTION    A
|     | |_____________| |  |                                          |
|     |  NAME           |  |     _________________                    |
|     |  _____________  |  |    |  _____________  |                   |
|     | |         ____|_|__|    | |      B      | |                   |
|     | |_____________| |       | |_____________| |                   |
|     |  DESCRIPTION    |       |  NAME           |                   |
|     |  _____________  |       |  _____________  |                   |
|     | |             | |       | |         ____|_|___________________|
|     | |_____________| |       | |_____________| |
|     |  VALUE          |       |  DESCRIPTION    |
|     |  _____________  |       |  _____________  |
|     | |         ____|_|______\| |             | |
|     | |_____________| |      /| |_____________| |
|     |  SIBLING        |       |  VALUE          |
|     |_________________|       |_________________|
|      OBJECT                    OBJECT
|___________________________
                            |
       _____________________V____________________
      |  _____________            _____________  |
      | |             |          |             | |
      | |_____________|          |_____________| |
      |__________________________________________|       Figure 4-17
       VALUE                                         After L/OPEN/MEMBER

Top       Page 78 
       _________________         _________________
      |  _____________  |       |  _____________  |
      | |      M      | |       | |    STRUC    | |
      | |_____________| |       | |_____________| |
      |  NAME           |       |  TYPE           |
      |  _____________  |       |  _____________  |
      | |         ____|_|______\| |             | |
      | |_____________| |      /| |__________|__| |
      |  DESCRIPTION    |       |  CHILD     |    |
      |  _____________  |       |____________|____|
 _____|_|____         | |        DESCRIPTION |
|     | |_____________| |                    |
|     |  VALUE          |        ____________V____
|     |  _____________  |       |  _____________  |
|     | |             | |       | |    STRING   | |
|     | |_________|___| |       | |_____________| |
|     |  CHILD    |     |   ___\|  TYPE           |        _____________
|     |___________|_____|  |   /|  _____________  |       |  _________  |
|      OBJECT     |        |    | |         ____|_|______\| | STRING  | |
|                 |        |    | |_____________| |      /| |_________| |
|      ___________V_____   |    |  SIBLING        |       |  TYPE       |
|     |  _____________  |  |    |_________________|       |_____________|
|     | |      A      | |  |     DESCRIPTION           DESCRIPTION    A
|     | |_____________| |  |                                          |
|     |  NAME           |  |     _________________                    |
|     |  _____________  |  |    |  _____________  |                   |
|     | |         ____|_|__|    | |      B      | |                   |
|     | |_____________| |       | |_____________| |                   |
|     |  DESCRIPTION    |       |  NAME           |                   |
|     |  _____________  |       |  _____________  |                   |
|   __|_|____         | |       | |         ____|_|___________________|
|  |  | |_____________| |       | |_____________| |
|  |  |  VALUE          |       |  DESCRIPTION    |
|  |  |  _____________  |       |  _____________  |
|  |  | |         ____|_|______\| |             | |
|  |  | |_____________| |      /| |_____________| |
|  |  |  SIBLING        |       |  VALUE          |
|  |  |_________________|       |_________________|
|  |  OBJECT                    OBJECT
|  |___________
|              |
|      ________|_________________________________
|     |  ______V______            _____________  |
|____\| |   "AB"      |          |             | |
     /| |_____________|          |_____________| |
      |__________________________________________|       Figure 4-18
       VALUE                                        After first L/ASSIGN

Top       Page 79 
    _________________         _________________
   |  _____________  |       |  _____________  |
   | |     STAR    | |       | |     OPF     | |
   | |_____________| |       | |_____________| |
   |  NAME           |       |  NAME           |
   |  _____________  |       |  _____________  |
   | |             | |       | |             | |
   | |_________|___| |       | |___________|_| |
   |  CHILD    |     |       |  VALUE      |   |
   |___________|_____|       |_____________|___|
    OBJECT     |              OBJECT       |
    ___________V_____         _____________V___
   |  _____________  |       |  _____________  |
   | |      F      | |/______|_|____         | |
   | |_____________| |\      | |_____________| |
   |  NAME           |       |  LIST           |
   |  _____________  |       |  _____________  |
   | |             | |       | |             | |
   | |_________|___| |       | |___________|_| |
   |  VALUE    |     |       |  MEMBER     |   |
   |___________|_____|       |_____________|___|
    OBJECT     |              VALUE        | OPD
               |              _____________V___
 ______________V_________    |  _____________  |
| ______________________ |   | |      M      | |
|| _________  _________ ||   | |_____________| |
|||  "AB"   ||  "CD"   |||   |  NAME           |
|||_________||_________|||   |  _____________  |
||______________________||   | |             | |
|                 /      |   | |___________|_| |
|                /       |   |_____________|___|
|_______________/________|    OBJECT       |
 VALUE         /       /      _____________V___        _________________
              /       /      |  _____________  |      |  _____________  |
             /       /       | |             | |      | |      B      | |
            /      LIST      | |_____________| |      | |_____________| |
           /                 |  NAME           |      |  NAME           |
          /                  |  _____________  |      |  _____________  |
 NEW MEMBER VALUE            | |         ____|_|_____\| |             | |
                             | |_____________| |     /| |_____________| |
                             |_________________|      |_________________|
                              OBJECT                   OBJECT

                              Figure 4-19
                          After L/CLOSE/MEMBER

Top       Page 80 
By executing similar groups of four primitives, varying only values of
constants, we can build up the LIST F shown in 4-20.  The calls required
are shown below:

    L/OPEN/MEMBER(L/TOBJ(OPF),ADD)
    L/ASSIGN(L/TOBJ(M.A),LC/STRING('FF'))
    L/ASSIGN(L/TOBJ(M.B),LC/STRING('GH'))
    L/CLOSE/MEMBER(L/TOBJ(OPF))

    L/OPEN/MEMBER(L/TOBJ(OPF),ADD)
    L/ASSIGN(L/TOBJ(M.A),LC/STRING('AB'))
    L/ASSIGN(L/TOBJ(M.B),LC/STRING('IJ'))
    L/CLOSE/MEMBER(L/TOBJ(OPF))

    L/OPEN/MEMBER(L/TOBJ(OPF),ADD)
    L/ASSIGN(L/TOBJ(M.A),LC/STRING('CD'))
    L/ASSIGN(L/TOBJ(M.B),LC/STRING('LM'))
    L/CLOSE/MEMBER(L/TOBJ(OPF))

The add suboperation has the effect of making the member just added, the
current member; thus no L/WHICH/MEMBER calls are needed in this
sequence.

To terminate the sequence of listops:
    L/END/LISTOP(L/TOBJ(OPF))

Top       Page 81 
                      _________________
                     |  _____________  |
                     | |      F      | |
                     | |_____________| |
                     |  NAME           |
                     |  _____________  |
                     | |         ____|_|_________\
                     | |_____________| |         /
                     |  DESCRIPTION    |
                     |  _____________  |
                     | |             | |
                     | |_________|___| |
                     |  VALUE    |     |
                     |___________|_____|
                      OBJECT     |
                                 |
                  _______________V______________
                 |  __________________________  |
                 | |  _________    _________  | |
                 | | |         |  |         | | |
                 | | |  "AB"   |  |  "CD"   | | |
                 | | |_________|  |_________| | |
                 | |__________________________| |
                 |  __________________________  |
                 | |  _________    _________  | |
                 | | |         |  |         | | |
                 | | |  "EF"   |  |  "GH"   | | |
                 | | |_________|  |_________| | |
                 | |__________________________| |
                 |  __________________________  |
                 | |  _________    _________  | |
                 | | |         |  |         | | |
                 | | |  "AB"   |  |  "IJ"   | | |
                 | | |_________|  |_________| | |
                 | |__________________________| |
                 |  __________________________  |
                 | |  _________    _________  | |
                 | | |         |  |         | | |
                 | | |  "CD"   |  |  "LM"   | | |
                 | | |_________|  |_________| | |
                 | |__________________________| |
                 |______________________________|
                  VALUE

                              Figure 4-20
                           After L/END/LISTOP

Top       Page 82 
A slightly more interesting exercise is to construct calls which create
a LIST named G, having the same description as F, and then to copy into
G all members of F having A equal to 'AB'.

We must first create G, an OPD and an object to represent the current
member.
   L/CREATE("STAR",LD/LIST(G,
                           LD/STRUCT(R,
                                   LD/STRING(A,STRING,2),
                                   LD/STRING(B,STRING,2)))
    L/CREATE(L/TOBJ(TOP/LEVEL),LD/OPD(OPG))
    L/CREATE(L/TOBJ(TOP/LEVEL) ,LD/STRUCT(GM,
                                   LD/STRING(A,STRING,2),
                                   LD/STRING(B,STRING,2)))

We now need to initiate two sequences of listops, one on G and one on F.
    L/BEGIN/LISTOP(L/POBJ(F),L/TOBJ(M),
                     L/TOBJ(OPF),GET)
    L/BEGIN/LISTOP(L/POBJ(G),L/TOBJ(GM),
                     L/TOBJ(OPG),ADD)
    L/WHICH/MEMBER(L/TOBJ(OPF),FIRST)
    L/WHICH/MEMBER(L/TOBJ(OPG),LAST)

We will now sequence through the members of F; whenever the current
member has A equal to 'AB', we will add a member to G.  We then copy the
values of the current member of F into the newly added member of G.
When the current member does not meet this criterion, we do nothing with
it.

First, to write a loop that will execute until we get to the end of F:
    L/TILL(L/END/OF/LIST(L/TOBJ(OPF)),x)
Whatever we put in this call to replace "x" will execute repeatedly
until the end/of/list flag has been set in OPF.

We must replace "x" with a single function call to in order to give
L/TILL what it is looking for.  However, we will be executing "x" once
for each member of F, and will need to execute several listops each
time.  The solution is to use L/CF, the compound-function function:
    L/TILL(L/END/OF/LIST(L/TOBJ(OPF)),L/CF(y))
We can now replace "y" with a sequence of function calls.

Each time we iterate, we need to process a new member of F; initially we
are set up to get the first member.  The following sequence, then, is
needed:
    L/CF(   L/OPEN/MEMBER(L/TOBJ(OPF),GET),
            z
            L/CLOSE/MEMBER(L/TOBJ(OPF)),
            L/WHICH/MEMBER(L/TOBJ(OPF),NEXT) )

Top       Page 83 
The above is a compound function which will open the current member of
F, do something to it (represented above by "z"), close it, and ask for
the next member.

We want to replace "z" by a function call which tests the contents of A
in the current member of F, and either does nothing or adds a member to
G, copying the values of the current member of F.  If "w" represents the
action of adding a member to G and copying the values, then we can
express this:
    L/IF(L/EQUAL(L/TOBJ(M.A),LC/STRING('AB')),w)

A suitable way to express "add a member and copy values" is:
    L/CF(L/OPEN/MEMBER(L/TOBJ(OPG),ADD),
            L/ASSIGN(L/TOBJ(GM.A),L/TOBJ(M.A)),
            L/ASSIGN(L/TOBJ(GM.B),L/TOBJ(M.B)),
            L/CLOSE/MEMBER(L/TOBJ(OPG))
This is similar enough to the previous example so that no explanation
should be necessary.

Putting this all together, we get:
    L/TILL(L/END/OF/LIST(L/TOBJ(OPF)),
     L/CF(  L/OPEN/MEMBER(L/TOBJ(OPF),GET),
            L/IF(L/EQUAL(L/TOBJ(A),LC/STRING('AB')),
                    L/CF(   L/OPEN/MEMBER(L/TOBJ(OPG),ADD),
                            L/ASSIGN(L/TOBJ(GM.A),L/TOBJ(M.A)),
                            L/ASSIGN(L/TOBJ(GM.B),L/TOBJ(M.B)),
                            L/CLOSE/MEMBER/L/TOBJ(OPG)) ) )
            L/CLOSE/MEMBER(L/TOBJ(OPF)),
            L/WHICH/MEMBER(L/TOBJ(OPF),NEXT) ) )

To conclude the operation, we execute:
    L/LISTOP/END(L/TOBJ(OPG))
    L/LISTOP/END(L/TOBJ(OPF))

The result is a LIST G whose first member has value ('AB','CD'), and
whose second member has value ('AB','IJ').  With a few variations on the
above example, quite a few LIST operations can be performed.


4.11    Higher level functions

While these primitive i/functions are useful, we would not ordinarily
expect users to operate in datalanguage at this low level.  We want to
make these primitives available to users so that they can handle the
exceptional case, and so that they can construct their own high-level
functions for atypical applications.  Ordinarily, they ought to operate
at least at the level of the following construction (which is legal in
the real datalanguage currently implemented):

Top       Page 84 
    FOR G.R,F.R WITH A EQ 'AB'
            G.R=F.R
            END
This relatively concise expression accomplishes the same result as the
elaborate construction of i/functions given at the close of the
preceding section.  We could define i/functions very similar to the
semantic functions used in the running software, and write the above
request as:
    L/FOR(L/POBJ(G),R
            L/POBJ(F),R,L/WITH(L/EQUAL(L/TOBJ(A),
                                    LC/STRING('AB')))
The differences between the i/function call and the datalanguage request
above it are principally syntactic.

In designing functions such as L/FOR and L/WITH, the central problems
have to do with choosing the right restrictions.  One cannot have all
the generality available at the primitive level.  Some important choices
for these particular functions are: (1) handling multiple inputs and
outputs, (2) when FORs are nested, how outer FORs restrict the options
available to inner FORs, (3) generality of selection functions (may then
in turn generate FORs?), (4) options with regard to where processing
should start (are we updating, replacing or appending to the output
list(s)?).

Finally, this problem is related to the more general problem of dealing
with _sets_, which are a generalization of the idea of a collection of
members in a LIST having common properties.  FOR is only one of many
operators that can input sets.


4.12    Conclusion

The present model, though embryonic, already contains enough primitives
and data types to permit definition and generalized manipulation of
hierarchical data structures.  Common data management operations, such
as retrieval by content and selective update can be expressed.

The use of this model in developing these primitives has resulted in
precise, well-defined and internally consistent specifications for
language elements and processing functions.  Operating in the laboratory
environment provided by the model seems to be a substantial benefit.

Top       Page 85 
5.      Further Work

In this section, we review what has been accomplished so far in the
design and describe what work remains to be done before this design
iteration of datalanguage is complete.


5.1     A Review

Most important, among our accomplishments, we feel that we have
delineated the problems and presented the broad outlines of a solution
to development of a language for the datacomputer system.  Key elements
of our approach are the primacy of data description in capturing all the
aspects of the data, the separation of logical and physical
characteristics of data description, the ability of users to define
different views of the same data, the ability to associate functions
with different uses of data items, an attempt to capture common aspects
of data at every possible level, and the ability of users to communicate
with the datacomputer in as high a level as their application permits.


5.2     Topics for Further Research

Although more work needs to be done in general to turn out a finished
design for datalanguage, we can single out certain issues which in
particular need further investigation.

So far, only hierarchal data structures (i.e. those that can be modeled
by physical containment) have been developed to any extent.  We also
intend to investigate and provide other types of data structures. We are
confident that our language framework does not make assumptions that
would prohibit such additions.

Our current work on access regulation centers on the use of multiple
descriptions for data.  We need to do more work on both the technical
and administrative aspects of access regulation.  Problems of encrypting
data for both transmission and storage will also be investigated.

Another issue requiring further research is the protocol requirement for
process interaction with the datacomputer.

Separation of the description into independent modules needs further
research.  In particular, we need to look into work which has already
been done on separate specifications of logical descriptions, physical
descriptions, and mappings between the two.

Top       Page 86 
5.3     Datalanguage Syntax

We have not yet proposed a syntax for the datalanguage we are
developing.  Certainly the most difficult parts of the problem have been
the semantic and pragmatic issues.  We are confident that various
syntactic forms can be chosen and implemented without excessive
difficulty.  It may be best to develop different syntactic forms for the
language for different types of users or even for the various subparts
of the language itself.  As discussed in section 2, the user syntax for
the datacomputer is supposed to be at a low level.  It should be easy
for _programs_ to generate datalanguage requests in this syntax.


5.4     Further Work on the Datalanguage Model

The model provides an excellent foundation on which to build up a
language with the facilities described in section 3.  Much work is yet
to be done.

For a while, emphasis will be on sets, high-level operators, language
extension and data description.

We expect to model sets as a new datatype, whose value is ordinarily
shared with other objects.  Some further work on binding and sharing of
values is needed to support this.

Sets can be regarded as a special case of generalized relations, which
will come somewhat later.

High-level operators such as FOR will be constructed from the existing
primitives, and will eventually be defined to have one effect but
several possible expansions.  The expansion will depend on the
representation of the data and the presence of auxiliary structures.

Alternate expansions will be possible when the data description has been
broken up into its various modules.  This, also, requires some further
research.

We feel that the language extension problem is much more easily attacked
in the environment provided by the model datacomputer.  In particular,
we expect the laboratory environment to be helpful in evaluating the
complex interactions and pervasive effects of operators in the language
which extend the language.

Data description work in the near term will focus on the isolation of
attributes, the representation of variable structure in description, the
description of descriptions and the development of a sufficient set of
builtin data types.

Top       Page 87 
Later, we expect to model the semantics of pointers as a datatype, when
the representation of the pointer and the semantics of the address space
into which it points are specified in the description of the pointer.

A large number of lower-level issues will be attacked, including some of
the problems discovered in the modeling to date.  Some of these are
pointed out in the discussions in section 4.


5.5     Applications Support

The datalanguage we are designing is intended to provide services to
sub-systems solving a broad class of problems related to data
management.  Examples of such sub-systems are: report generators, online
query systems for non-programmers, document-handling systems,
transaction processing systems, real-time data collection systems, and
library and bibliographic systems.  There are many more.

The idea is that such systems will run on other machines, reference or
store data at the datacomputer, and make heavy use of datalanguage.
Such a system would not be written entirely in datalanguage, but a large
component of its function would be expressed in datalanguage requests;
some controlling module would build the requests and perform the non-
datalanguage functions.

While we have experience with such applications in other environments,
and we talk to potential users, it will require some work to determine
that our language is actually adequate for them.  That is, we are not
attacking directly the problem of building a human-oriented online query
system; we are trying to provide the tools which will make it easy to
build one. There is a definite need to analyze whether the tools are
likely to be good enough. Of course, the ultimate test will be in actual
use, but we want to filter out as many problems as we can before
implementation.

An important component of supporting applications is that the using
programs will frequently be written in high-level languages such as
FORTRAN, COBOL or PL/1.  We will want to investigate the ability of
datalanguage to support such users, while the design is taking shape.


5.6     Future Plans


This paper has laid the foundations for a new design of datalanguage.
Section 3 provides an outline for a datalanguage design, which will be
filled in during the coming months.  Following the issue of a detailed
specification, we anticipate extensive review, revisions, and

Top       Page 88 
incorporation into the implementation plans.  Implementation will occur
in stages, compatible with the established plans for development of
datacomputer service and data management capabilities.











       [ This RFC was put into machine readable form for entry ]
       [ into the online RFC archives by Alex McKenzie with    ]
       [ support from GTE, formerly BBN Corp.           1/2000 ]