|___________|_____| | |
OBJECT |____________\| TRUE |
/|____________|
VALUE
Figure 4-1
Two elementary objects
Figure 4-2 illustrates an object of type dir (a _directory_) and related
objects. The directory has name SMITH. There are two objects entered in
this directory, named X and Y.
_________________
| _____________ |
| | SMITH | |
| |_____________| |
| NAME | ____________
| _____________ | | ________ |
| | ____|_|______\| | DIR | |
| |_____________| | /| |________| |
| DESCRIPTION | | TYPE |
| _____________ | |____________|
| | | | DESCRIPTION
| |_________|___| |
| CHILD | |
|___________|_____|
OBJECT |
___________V_____
| _____________ |
| | X | |
| |_____________| |
| NAME | _________________
| _____________ | | _____________ |
_____|_|____ | | | | Y | |
| | |_____________| | | |_____________| |
| | DESCRIPTION | | NAME |
| | _____________ | | _____________ |
| __|_|____ | | | | ____|_|_____
| | | |_____________| | | |_____________| | |
| | | VALUE | | DESCRIPTION | |
| | | _____________ | | _____________ | |
| | | | ____|_|_____\| | ____|_|__ |
| | | |_____________| | /| |_____________| | | |
| | | SIBLING | | VALUE | | |
| | |_________________| |_________________| | |
| | OBJECT OBJECT | |
| | _________________ _________________ | |
| |_\| "ABC" | | FALSE |/_| |
| /|_________________| |_________________|\ |
| VALUE VALUE |
| _________________ _________________ |
| | _____________ | | _____________ | |
| | | STRING | | | | BOOL | | |
|____\| |_____________| | | |_____________| |/____|
/| TYPE | | TYPE |\
|_________________| |_________________|
DESCRIPTION DESCRIPTION
Figure 4-2: A directory with two members
The idea of a dir is similar to the idea of a file directory in most
systems. A directory is a place where one can store named objects,
freely adding and deleting them. The entries in the directory are all
objects whose parent is that directory. Figure 4-3 shows a more rigidly
structured group of objects. Here we have R, a struct, and A and B, a
pair of strings. Note that the boxes labeled 'object' in figure 4-3
bear precisely the same relationships to one another as those labeled
'object' in 4-2. However, there are two conditions which hold for 4-3
but do not hold for 4-2: (1) the value of R contains the values of A and
B, and (2) the descriptions of R, A and B are all related.
Structs have the following properties: (1) name and description of each
component in the struct is established when the struct is created, and
(2) in a value of the struct, the order of occurrence of component
values is fixed.
_________________ _________________
| _____________ | | _____________ |
| | R | | | | STRUCT | |
| |_____________| | | |_____________| |
| NAME | | TYPE |
| _____________ | | _____________ |
| | ____|_|______\| | | |
| |_____________| | /| |__________|__| |
| DESCRIPTION | | CHILD | |
| _____________ | |____________|____|
_____|_|____ | | DESCRIPTION |
| | |_____________| | ____________V____
| | VALUE | | _____________ |
| | _____________ | | | STRING | |
| | | | | | |_____________| |
| | |_________|___| | ___\| TYPE | _____________
| | CHILD | | | /| _____________ | | _________ |
| |___________|_____| | | | ____|_|______\| | STRING | |
| OBJECT | | | |_____________| | /| |_________| |
| | | | SIBLING | | TYPE |
| ___________V_____ | |_________________| |_____________|
| | _____________ | | DESCRIPTION DESCRIPTION A
| | | A | | | |
| | |_____________| | | _________________ |
| | NAME | | | _____________ | |
| | _____________ | | | | B | | |
| | | ____|_|__| | |_____________| | |
| | |_____________| | | NAME | |
| | DESCRIPTION | | _____________ | |
| | _____________ | | | ____|_|___________________|
| __|_|____ | | | |_____________| |
| | | |_____________| | | DESCRIPTION |
| | | VALUE | | _____________ |
| | | _____________ | | | ____|_|____
| | | | ____|_|______\| |_____________| | |
| | | |_____________| | /| VALUE | |
| | | SIBLING | | _____________ | |
| | |_________________| | | | | |
| | OBJECT | |_____________| | |
| | | SIBLING | |
| | |_________________| |
| |__________ OBJECT _____________|
| _______|__________________________|_______
|____\| _____V_______ _______V_____ |
/| | "ABC" | | FALSE | | Figure 4-3
| |_____________| |_____________| | A STRUCT with
|__________________________________________| two members
Figure 4-4 shows a list named L. Here a similar structure of objects is
implied, but because of the regularity of the structure, not all the
boxes labeled 'object' are actually present.
_________________
| _____________ |
| | L | |
| |_____________| |
| NAME | ____________
| _____________ | | ________ |
| | ____|_|______\| | LIST | |
| |_____________| | /| |________| |
| DESCRIPTION | | TYPE |
| _____________ | | ________ |
| | | | | | | |
| |_______|_____| | | |______|_| |
| VALUE | | | CHILD | |
|_________|_______| |________|___|
OBJECT | DESCRIPTION |
| |
_________V_______ ________V___
| | | ________ |
| _____________ | | | STRING | |
| | "ABC" | | | |________| |
| |_____________| | | TYPE |
| _____________ | |____________|
| | "XY" | | DESCRIPTION
| |_____________| |
| _____________ |
| | "ZLM" | |
| |_____________| |
| : |
| : |
| _____________ |
| | "BBBF" | |
| |_____________| |
|_________________|
VALUE
Figure 4-4
A LIST
L has a variable number of components, all satisfying the description
subordinate to L's description.
We could imagine an 'object' box for each string in L. Each of these
boxes would point to its respective string and to the common description
of these strings. Instead, we think in terms of creating such boxes as
we need them.
4.5 Definitions of types
Following are some more precise definitions of types, in terms of the
present model. These serve the purpose of establishing more firmly the
semantics of our structure of objects, descriptions and values; however,
they should not be thought of as providing a definition for the
completed language specification.
An object of type STRING has a value which is a sequence of characters
(figure 4-1).
An object of type BOOL has a value which is a truth value (TRUE or FALSE
-- figure 4-1).
An object of type DIR has subordinate objects, each having its own
description and value. Subordinate objects can be added and deleted at
will (figure 4-2).
An object of type STRUCT has subordinate objects, each of which has a
description which is subordinate to the STRUCT's description, and a
value contained in the STRUCT's value. The number, order and
description of components is fixed when the STRUCT is created (figure
4-3).
An object of type LIST may be thought of as having imaginary subordinate
objects, whose existence is simulated by the use of appropriate
techniques in processing the LIST. Each of these has the same
description, which is subordinate to the description of the LIST. Each
has a distinct value, contained in the value of the LIST. In fact, only
the LIST object, the LIST and component descriptions, and the values
exist (figure 4-4).
An object of type DESC has a description as its value. This value is
the same sort of entity which serves as the description of other
objects.
An object of type FUNC has a function call as its value. We will be
able to say more about this after functions have been discussed.
An object of type OPD has an operation descriptor as its value. (see 4.7
for details).
4.6 Object environment
There are three categories of objects in the model datacomputer. These
are p/objects, t/objects, and i/objects.
P/objects are permanent objects created explicitly with language
functions. They correspond to the idea of stored data in the real
datacomputer. There are three special objects. These are special only
in that they are created as part of initializing the environment, rather
than as the result of executing a language function. These are named
STAR, BLOCK and TOP/LEVEL. All three are of type DIR.
An object is a p/object if it is subordinate to STAR; it is a t/object
if it is subordinate to BLOCK. TOP/LEVEL is subordinate to BLOCK. (see
figures 4-5 and 4-6).
_________________
| |
| _____________ |
| | STAR | |
| |_____________| |
| NAME | ____________
| _____________ | | ________ |
| | ____|_|______\| | DIR | |
| |_____________| | /| |________| |
| DESCRIPTION | | TYPE |
| _____________ | |____________|
| | | | DESCRIPTION
| |_________|___| |
| CHILD | |
|___________|_____|
OBJECT |
|
|
|
V
ALL P/OBJECTS
Figure 4-5
STAR and p/objects
T/objects are temporary objects, also created explicitly with language
functions. However, these correspond to user-defined temporaries, both
local to requests and "top-level" (i.e. not local to any request, but
existing until deletion or logout.)
_________________
| |
| _____________ |
| | BLOCK | |
| |_____________| |
| NAME | ____________
| _____________ | | ________ |
| | ____|_|______\| | DIR | |
| |_____________| | /| |________| |
| DESCRIPTION | | TYPE |
| _____________ | |____________|
| | | | DESCRIPTION
| |_________|___| |
| VALUE | |
|___________|_____|
OBJECT |
|
|
___________V_____
| |
| _____________ |
| | TOP/LEVEL | |
| |_____________| |
| NAME | ____________
| _____________ | | ________ |
| | ____|_|______\| | DIR | |
| |_____________| | /| |________| |
| DESCRIPTION | | TYPE |
| _____________ | |____________|
| | ____|_|___ DESCRIPTION
| |_____________| | |
| SIBLING | |
| _____________ | |___\ ALL BLOCKS AND
| | | | / LOCAL T/OBJECTS
| |_________|___| |
| CHILD | |
|___________|_____|
|
|
V
ALL GLOBAL
T/OBJECTS
Figure 4-6
BLOCK, TOP/LEVEL and t/objects
I/objects are internal, system-defined objects whose creation and
deletion is implicit in the execution of some language function.
I/objects are hung directly off of function calls (objects of type
FUNC), and are always local to the execution of such function calls.
They correspond to the notions of (1) literal, and (2) compiler- or
interpreter-generated temporary.
4.7 Primitive Language Functions
Here we discuss the primitive language functions presently implemented
in the model and likely to be of most interest. In this section, the
emphasis is on relating functions to one another. Section 4.8 contains
more detail and examples.
_Assign_ operates on a pair of objects, called the target and the
source. The value of the source is copied into the value of the target.
Figure 4-7 shows a pair of objects, X and Y, before and after execution
of an assignment having X as target and Y as source. Presently,
assignment is defined only for objects of type BOOL and objects of type
STRING. The objects involved must have identical descriptions.
_________________ _________________
| | | |
| _____________ | | _____________ |
| | | | | | | |
| | X | | | | Y | |
| |_____________| | | |_____________| |
| NAME | | NAME |
| _____________ | | _____________ |
| | | | | | | |
| |_______|_____| | | |_______|_____| |
| VALUE | | | VALUE | |
|_________|_______| |_________|_______|
OBJECT | OBJECT |
| |
_________V_______ _________V_______
| | | |
| "ABC" | | "DEF" |
|_________________| |_________________|
VALUE VALUE
BEFORE ASSIGNMENT
_________________ _________________
| | | |
| _____________ | | _____________ |
| | | | | | | |
| | X | | | | Y | |
| |_____________| | | |_____________| |
| NAME | | NAME |
| _____________ | | _____________ |
| | | | | | | |
| |_______|_____| | | |_______|_____| |
| VALUE | | | VALUE | |
|_________|_______| |_________|_______|
OBJECT | OBJECT |
| |
_________V_______ _________V_____
| | | |
| "DEF" | | "DEF" |
|_________________| |_________________|
VALUE VALUE
AFTER ASSIGNMENT
Figure 4-7
Effect of assignment
A class of primitive functions for manipulating LISTs is defined. These
are called _listops_. All listops input a special object called an
_operation_descriptor_ or OPD.
To accomplish a complete operation on a LIST, a sequence of listops must
be executed. There are semantic restrictions on the composition of such
sequences, and it is best to think of the entire sequence as one large
operation. The state of such an operation is maintained in the OPD.
Refer back to figure 4-4. There is one box labeled "object" in this
picture; this box represents the list as a whole. To operate on any
given member we need an object box to represent that member. Figure 4-8
shows the structure with an additional object box; the new box
represents one member at any given moment. Its value is one of the
components of the LIST value; its description is subordinate to the LIST
description. In 4-8, the name of this object is M.
In 4-8 we have enough structure to provide a description and value for
M, and this is sufficient to permit the execution of operations on M as
an item. However, there is no direct link between object M and object
L. The structure is completed by the addition of an OPD, shown in
figure 4-9.
_________________ _________________
| | | _____________ |
| _____________ | | | | |
| | L | | | |_____________| |
| |_____________| | | TYPE |
| NAME | | _____________ |
| _____________ | | | | |
| | ____|_|______\| |__________|__| |
| |_____________| | /| CHILD | |
| DESCRIPTION | |____________|____|
| _____________ | DESCRIPTION |
| | | | |
| |_________|___| | ____________V____
| VALUE | | | _____________ |
|___________|_____| | | STRING | |/___
OBJECT | | |_____________| |\ |
| | TYPE | |
___________V_____ |_________________| |
| | DESCRIPTION |
| _____________ | |
| | "ABC" | | _________________ |
| |_____________| | | | |
| _____________ | | _____________ | |
| | "XY" | | | | M | | |
| |_____________| | | |_____________| | |
| _____________ | | NAME | |
| | "ZLM" |/|___ | _____________ | |
| |_____________|\| | | | ____|_|____|
| : | | | |_____________| |
| : | | | DESCRIPTION |
| _____________ | | | _____________ |
| | "BBBF" | | |___|_|____ | |
| |_____________| | | |_____________| |
|_________________| | VALUE |
VALUE |_________________|
OBJECT
Figure 4-8
LIST and member objects
_________________ _________________
| _____________ | | _____________ |
| | L | | | | | |
| |_____________| | | |_____________| |
| NAME | | TYPE |
| _____________ | | _____________ |
| | ____|_|______\| | | |
| |_____________| | /| |__________|__| |
| DESCRIPTION | | CHILD | |
| _____________ | |____________|____|
| | | |/__ DESCRIPTION |
| |_________|___| |\ | ____________V____
| VALUE | | | | _____________ |
|___________|_____| | | | STRING | |/___
OBJECT | | | |_____________| |\ |
| | | TYPE | |
___________V_____ | |_________________| |
| _____________ | | DESCRIPTION |
| | "ABC" | | | _________________ |
| |_____________| | | | | |
| _____________ | | | _____________ | |
| | "XY" | | |___|_|____ | | |
| |_____________| | | |_____________| | |
| _____________ | | LIST | |
| | "ZLM" | | | _____________ | |
| |_____________| | | | | | |
| : | | |_________|___| | |
| : | | MEMBER | | |
| _____________ | | : | | |
| | "BBBF" |/|___ | : | | |
| |_____________|\| | |___________|_____| |
|_________________| | OPD | |
VALUE | ___________V_____ |
| | _____________ | |
| | | M | | |
| | |_____________| | |
| | NAME | |
| | _____________ | |
| | | ____|_|____|
| | |_____________| |
| | DESCRIPTION |
| | _____________ |
|___|_|____ | |
| |_____________| |
Figure 4-9 | VALUE |
OPD, LIST and member |_________________|
OBJECT
The OPD establishes the object relationship, and contains information
about the sequence of primitive listops in progress. When sufficient
information is maintained in the OPD, we have in 4-9 a structure which
is adequate for the maintenance of the integrity of the LIST and of the
global list operation. In addition to LIST and member pointers, the OPD
contains information indicating: (1) which suboperations are enabled for
the sequence, (2) the current suboperation, (3) the instance number of
the current LIST member, (4) an end-of-list indicator. The
suboperations are add/member, delete/member, change/member and
get/member. All apply to the current member. Only suboperations which
have been enabled at the beginning of a sequence may be executed during
that sequence; eventually, the advance knowledge of intentions that is
implied by this will provide important information for concurrency
control and optimization.
Presently, an OPD relates a single member object to a single LIST
object. This imposes an important restriction on the class of operation
sequences which can be expressed. Any LIST transformation requiring
simultaneous access to more than one member must be represented as more
than one sequence. (And we do not yet solve the problems implied in
concurrent execution of such sequences, even when both are controlled by
one process.)
Any transformation of a LIST can still be achieved by storing
intermediate results in temporary objects; however, it is certainly more
desirable to incorporate the idea of multiple current members into the
semantics of the language, than it is to use such temporaries. An
important future extension of the listops will deal with this problem.
There are six listops: listop/begin, listop/end, which/member,
end/of/list, open/member and close/member.
Listop/begin and listop/end perform the obvious functions of beginning
and terminating a sequence of listops. Listop/begin inputs LIST and
member objects, an OPD, and a specification of suboperations to enable.
It initializes the OPD, including establishment of the links to LIST and
MEMBER objects. After the OPD-LIST-member relationship has been
established, it is only necessary to supply the OPD and auxiliary
parameters as input to a listop in the sequence. From the OPD everything
else can be derived.
Listop/end clears the OPD and frees any resources acquired by
listop/begin.
Which/member establishes the current member for any suboperations. This
is either the first LIST member, the last LIST member, or the next LIST
member. This listop merely identifies which member is to be operated
on; it does not make the contents of the member accessible.
Open/member and close/member bracket a suboperation. The suboperation
is indicated as an argument to open/member. Open/member always
establishes a pointer from the member object to the member value;
close/member always clears this pointer. In addition, each of these
listops may take some action, depending on the suboperation.
The details of the action would be dependent on the representation of
the LIST in storage, the size of a LIST member, and choices made in
implementation.
Between execution of the open/member and the close/member, the data is
accessible. It can always be read; in the case of the add/member and
change/member suboperations, it can also be written into.
End/of/list tests a flag in the OPD and returns an object of type BOOL.
The value of the object is the same as the value of the flag; it is TRUE
if a get/member, change/member or delete/member would be unsuccessful
due to a which/member having moved "beyond the end". T his listop is
provided so that it is possible to write procedures which terminate
conditionally when all members have been processed.
Get/struct/member provides the ability to handle STRUCTs. Given a
STRUCT object which points to the STRUCT value, it will establish a
pointer from a given member object to the member value. (The pointer it
establishes is represented by a dashed line in figure 4-10).
_________________ _________________
| _____________ | | _____________ |
| | F | | | | STRUCT | |
| |_____________| | | |_____________| |
| NAME | | TYPE |
| _____________ | | _____________ |
| | ____|_|______\| | | |
| |_____________| | /| |__________|__| |
| DESCRIPTION | | CHILD | |
| _____________ | |____________|____|
| | | | DESCRIPTION |
| |___________|_| | ____________V____ _________________
| VALUE | | | _____________ | | _____________ |
| ___________|_ | | | STRING | | | | STRING | |
| | | | | | |_____________| | | |_____________| |
| |_________|_|_| | | TYPE | | TYPE |
| CHILD | | | | _____________ | | _____________ |
|___________|_|___| ____\| | | | | | | |
OBJECT | | | /| |_____________| | | |_____________| |
| | | | SIBLING | | SIBLING |
| | | |_________________| |_________________|
| | | DESCRIPTION DESCRIPTION A
| | | ______________________________________ |
| | | | ____________ ____________ | |
| | | | | "ABC" | | FALSE | | |
| |_____|_____| |____________| |____________| | |
| | |________A_____________________________| |
| | ............: VALUE |
___________V_____ | : _________________ |
| _____________ | | : | _____________ | |
| | A | | | : | | B | | |
| |_____________| | | : | |_____________| | |
| NAME | | : | NAME | |
| _____________ | | : | _____________ | |
| | ____|_|_| : | | ____|_|_______________________|
| |_____________| | : | |_____________| |
| DESCRIPTION | : | DESCRIPTION |
| _____________ | : | _____________ |
| | ....|.|....: | | | |
| |_____________| | | |_____________| |
| VALUE | | VALUE |
| _____________ | | _____________ |
| | ____|_|______\| | | |
| |_____________| | /| |_____________| |
| SIBLING | | SIBLING |
|_________________| |_________________| Figure 4-10
OBJECT OBJECT Effect of GET/STRUCT/MEMBER
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____________________
| _____________ _____________ |
| | | | | |
| |_____________| |_____________| |