 |
|
|
|
||||
|
|||||
|
|
|||||
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.
