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

Building a binary tree

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

Choosing the appropriate technique

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.

[ INDEX ] [ CONCEPTS ] [ TASKS ] [ SYNTAX ] [ LIBRARIES ] [ LEGACY LIBRARIES ] [ ERRORS ]