RFC 0610
Further datalanguage design concepts
Pages: 88
Unclassified
Unclassified
Part 3 of 3 – Pages 60 to 88
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
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).
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:
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.
_________________
| _____________ |
| | 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:
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
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).
_________________
| |
| _____________ |
| | 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
_________________
| _____________ |
| | 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
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.
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.
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;
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.
_________________ _________________
| _____________ | | _____________ |
| | 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
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.
_________________ _________________
| _____________ | | _____________ |
| | 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
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.
_________________ _________________
| _____________ | | _____________ |
| | 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
_________________ _________________
| _____________ | | _____________ |
| | 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
_________________ _________________
| _____________ | | _____________ |
| | 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
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))
_________________
| _____________ |
| | F | |
| |_____________| |
| NAME |
| _____________ |
| | ____|_|_________\
| |_____________| | /
| DESCRIPTION |
| _____________ |
| | | |
| |_________|___| |
| VALUE | |
|___________|_____|
OBJECT |
|
_______________V______________
| __________________________ |
| | _________ _________ | |
| | | | | | | |
| | | "AB" | | "CD" | | |
| | |_________| |_________| | |
| |__________________________| |
| __________________________ |
| | _________ _________ | |
| | | | | | | |
| | | "EF" | | "GH" | | |
| | |_________| |_________| | |
| |__________________________| |
| __________________________ |
| | _________ _________ | |
| | | | | | | |
| | | "AB" | | "IJ" | | |
| | |_________| |_________| | |
| |__________________________| |
| __________________________ |
| | _________ _________ | |
| | | | | | | |
| | | "CD" | | "LM" | | |
| | |_________| |_________| | |
| |__________________________| |
|______________________________|
VALUE
Figure 4-20
After L/END/LISTOP
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) )
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):
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.
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.
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.
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
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 ]