|
|||||
|
|||||
Emptiness, representing |
It is sometimes useful to create a positive representation of the concept of nothing or emptiness. There is a difference between something just incidentally being empty and the positive observation that it is empty properly and by design. This concept is represented in some languages by the concept of "null" or "nil" where null or nil are a particular kind of value that certain kinds of variables may have assigned to them, and for which tests either exist or can be defined.
OmniMark does not have a null or nil value or a built in test for nullity. However, if you are creating a data structure that requires a positive representation of emptiness, there are two simple techniques that you can use to express this concept.
The first is to take advantage of the properties of variable shelves. When a shelf is declared variable it initially contains no items. If you need a container that can be tested to determine if it contains something or nothing, you can use a variable shelf. It if has no items (number of foo = 0
) then it is empty. However, a variable shelf can normally contain an unlimited number of items and if you just want to be able to distinguish between the existence of a single value and the absence of a value, you need to restrict the shelf to having at most one item. You can do this by declaring a shelf variable to 1
. This creates a shelf with zero items that can contain at most one item. If the item exists, the shelf has a value. If it does not exist, the shelf is empty.
The second approach is to create a record type whose sole function is to represent nothing. To make this strategy work, you first need a generic container type that can contain either something or nothing. You can do this using extended records:
declare record thing declare record nothing extends thing declare record something extends thing field integer name
In the above example, the record type thing
is the generic container. It has no fields because a thing by itself has no properties. However, because the types nothing
and something
are extensions of thing
, you can place a nothing
or a something
on a shelf of type thing
:
process local thing stuff variable local nothing empty local something full set full:name to "Roger Rabbit" set new thing to empty set new thing to full
The type nothing
is also declared without any fields because its only function is to represent nothingness. In other words, the concept of emptiness is represented by a thing that is empty.
Once you have these types in place, you can test for emptiness by testing for the nothing type:
do select-type stuff[1] as s case nothing output "Nothing here." case something output s:name || "here." done
You can easily create a test for emptiness:
define switch function is-nothing value thing thing as do select-type thing as t case something return false case nothing return true done
One application of the concept of nothing is the building of a binary tree. A binary tree is one in which each node can have only two child nodes. One way to achieve this would be to create a node record with a field of type node that was declared variable to 2
. However, the two nodes of a binary tree often have distinct meanings. For instance, one node may represent a higher value and the other may represent a lower value. If there are no lower values, then the lower node needs to have a value of empty. If there are no higher nodes, then the higher node needs to have the value of empty. Here's how this can be set up:
declare record node declare record empty-node extends node declare record value-node extends node field node higher field node lower field integer value
Here is a program that reads a set of numbers and assembles them onto a binary tree. The program then walks the tree and prints the numbers out in order:
declare record empty-node elsewhere define empty-node function new-empty elsewhere declare record node declare record empty-node extends node declare record value-node extends node field node higher initial {new-empty} field node lower initial {new-empty} field integer value global node btree initial {new-empty} define empty-node function new-empty as local empty-node e return e define switch function is-empty value node node as do select-type node as t case empty-node return true done return false define value-node function new-value value integer i as local value-node v set v:value to i return v define function walk-tree value node tree as do select-type tree as t case value-node do unless is-empty t:lower walk-tree t:lower done output "d" % t:value || " " do unless is-empty t:higher walk-tree t:higher done done define function add-tree value integer n to modifiable node tree as do select-type tree as t case value-node do when t:value > n add-tree n to t:lower else when t:value < n add-tree n to t:higher done case empty-node set tree to new-value n done process submit "23 76 98 21 7 89 34 86 14 25 1" walk-tree btree find digit+ => number white-space* add-tree number to btree
There are a couple of important points to note about this program. The first is that the value-node and empty-node types are both extensions of node and that the tree itself is defined in terms of nodes, built on the global variable btree which is declared to be of type node. Since the node type contains no fields the tree is actually made up of value-node records sitting on shelves of type node. To access the fields of the value-nodes, therefore, you have to use a do select-type
statement to get a type specific alias for the item you are looking at. You cannot ask an item on a node shelf directly for the fields of a value-node record. You must use do select-type
to obtain a reference of type value-node.
Secondly, it is important to note that in the do select-type statement in the add tree function, the shelf item is referred to in two different ways for different purposes:
define function add-tree value integer n to modifiable node tree as do select-type tree as t case value-node do when t:value > n add-tree n to t:lower else when t:value < n add-tree n to t:higher done case empty-node set tree to new-value n done
When querying the values of the value, lower, and higher fields of the record, the alias t must be used, since the shelf tree is of type node while the alias t is of type value-node.
When assigning a new value node to the variable tree, however, the original name tree must be used. The set statement is not type specific, so there is no need to use the alias t. But there is another consideration. Because the value referred to in a do select-type may be a dynamic expression, which naturally cannot be written to, the alias name in a do select-type is always read-only and cannot be written to. Therefore the original variable name must be used in the set statement.
Here is the same program written using the variable to 1
technique:
declare record value-node field value-node higher variable to 1 field value-node lower variable to 1 field integer value global value-node btree variable to 1 define switch function is-empty read-only value-node node as return number of node = 0 define value-node function new-value value integer i as local value-node v set v:value to i return v define function walk-tree value value-node tree as do unless is-empty tree:lower walk-tree tree:lower done output "d" % tree:value || " " do unless is-empty tree:higher walk-tree tree:higher done define function add-tree value integer n to modifiable value-node tree as do when is-empty tree set new tree to new-value n else do when tree:value > n add-tree n to tree:lower else when tree:value < n add-tree n to tree:higher done done process submit "23 76 98 21 7 89 34 86 14 25 1" walk-tree btree find digit+ => number white-space* add-tree number to btree
The notable differences between the two approaches are as follows:
The variable to 1
technique avoids the use of extended types and therefore the need to use do select-type
to access field values. This simplifies the code somewhat. However, it should be noted that the need to use do select-type
in this way largely affects functions that act on the tree rather than the main program, so in a more extensive application, this difference may not be terribly important.
The empty-node technique has the advantage that an empty-node can be passed to a function, leaving it to the function to determine its type. The variable to 1
technique, by contrast, does not have a specific item that represents nothing, and so the calling environment has to take more responsibility for assessing its emptiness.
In summary, the variable to 1
technique is lighter weight and suitable for small or quick programs. The empty-node technique involves more overhead but allows for better encapsulation of the concept of emptiness, making it suitable for larger programs or the development of packaged modules.
Copyright © Stilo International plc, 1988-2010.