Representing field types

In the previous post we examined how Mitopia's GUI auto-generation capability handles the representation of structures and sub-structures and the fields within.  In an earlier post we looked at how the keyword 'union' is represented in the GUI.  In this post we will explore examples of how other more specialized field types are typically represented (remember each GUI renderer is a plugin and may adopt a different strategy).

Numeric Fields and Units

The display of numeric fields is a relatively straightforward matter as illustrated by the screen shots to the right.  Numbers can be displayed in single-line text controls and formatted according to standard conventions for integer and real numbers.

The main complicating issue with numbers is the question of units.  Numbers, especially floating point numbers, tend to have associated units with them and only by knowing the units associated with any numeric value is it possible to reliably interpret the number or to compare it with other numbers.  What we require is that every numeric field potentially have an associated unit value and that there exist a Mitopia® unit manager which understands units and unit conversions at a level necessary to allow the selection of compatible alternate display units (e.g., miles/h vs. km/h).  Mitopia® has a fledgling UnitMgr package but the support for unit conversion and the associated GUI connection through the DataModels abstraction to allow renderer interaction with units is incomplete at this time.  For this reason, you may see fields in the current base ontology that hold the units associated with other numeric fields.  This is a stop gap measure designed to preserve unit data until such a time as units and their UI ramifications can be fully supported in an integrated manner with the TypeMgr APIs and specified using the Carmot ODL.

When this is the case, the numeric displays where units are appropriate will have a unit popup menu after the number value and this popup will allow selection of any compatible unit in which to display the value during display or editing.  This means that all numeric fields with associated units are always actually held in the ‘prime’ unit value and the value displayed on the screen is obtained by the renderer through DataModels API calls which convert into the currently selected ‘display’ unit for the field concerned.  Unit compatibility and conversion is a complex matter and is rarely handled in any formalized manner in today’s systems.  Units might include currency values which require near-real-time lookups, and they might include units such as distances on the earth’s surface which require complex calculations involving other fields of the record in order to make the necessary conversions.  The full support of units within the Mitopia® type manager infrastructure will be a subject of future R&D.  The problem is similar in many ways to tracking union ‘state’ since we cannot place the display unit into the actual record structure, but must instead track it in the associated collection structures.
Numeric fields should generally use the maximum precision available (i.e., int64 or double) unless there is good reason to be certain that a smaller representation (e.g., int32) will never overflow.  Beware of falling into the trap of including units in a field name (e.g., ‘heightInInches’) since this will violate the unit manager abstraction when available.  Field names should be meaningful without including units (i.e., ‘height’).

Dates and Time

One special case of numeric formatting and units is the whole area of dates, time and calendars.  In Mitopia® and in the DataModels abstraction layer there is extensive support for date handling and display by renderers.  Mitopia® stores dates and times as double precision floating point numbers where the whole number part represents the ‘Serial Day Number’ (SDN) and the fractional part represents the time of day.  See the earlier section on “Numeric Queries” for details of date encodings.

There are of course a significant number of different calendar systems in effect throughout the world and it is necessary to convert to/from these ‘units’ during date display and entry.  Currently Mitopia® provides support for GUI renderers to convert between the Gregorian, Julian, Islamic (x2), and Hebrew calendar systems.  Additionally, Mitopia® contains code internally to handle and convert between virtually all known common calendar systems such as the Alexandrian Calendar, the Armenian Era Calendar, the Badi & Baha'i Calendars, the Chinese Calendar, the Egyptian Coptic Calendar, the Ethiopian Calendar, and roughly 20 others including the Ancient Mayan calendar.

The screen shots on this page illustrate the rendering of date values in the default renderer and illustrate the various controls available for choosing the date display format.  In this sense, date conversion can be seen as a special case of unit conversion involving complex astronomical calculations in order to make the conversion.  Once the unit conversion mechanism is fully developed, the behavior of date controls will simply be a subset of that of any numeric value with associated units.

Note that times and dates must not only be aware of the calendar system in effect, but also of the time zone.  All times are stored in GMT which means that displaying local time at any particular location also involves a conversion based on the time zone and any daylight savings time that might be in effect.  Once again even this time zone calculation can be quite complex but is essential if dates and times are to be easy to use by the users while remaining useful for analytical, comparison and search purposes to the rest of the underlying code base.  This whole area tends to be glossed over in most systems, but the existence of the flat memory model and the ability to reliably track the current display ‘state’ in the underlying abstraction without having to modify the actual structure fields, mean that dates and times, like all other unit issues can be fully handled by the substrate without renderer knowledge.  This includes the ability to lay out calendar days into months (see screen shot to the right).  As a side benefit the date/time abstraction can function as an astronomical almanac yielding times for moon rise/set, sun rise/set, twilight, phases of the moon etc.  In many cultures these calculations can in turn be used to compute other important information (e.g., Islamic prayer times, Hebrew Havdalah etc.).  The Mitopia® date conversion utilities provide all of these features/calculations although few are exposed in any direct way through current renderers.

Text Fields

The display of text fields is one of the most commonplace and pervasive behaviors of any renderer.  The screen shots in this section illustrate a number of display formats used by the default renderer for showing text.  The standard strategy is to display the text in a text control of a size that is just sufficient to display whatever text is actually in the record.  Thus we see that in the case of the ‘other’ field, the renderer (through interaction with the DataModels layer) determined how much text was available and made the control just large enough to display the it.  In the case of the ‘name’ field, the render has determined that a single line control is sufficient.  The ‘description’ field shown is empty and thus can fit into half a column in this case.  Furthermore the ‘subType’ field that follows is mentioned in the $ShortStrings annotation (see annotations discussion) for Organization and thus empty or not is a candidate for packing two to a column.  The ‘keyWords’ field shown despite being empty is followed by a collection reference field (‘divisions’) which requires a full column width to display and this means that the ‘keyWords’ field is extended to the end of the line to avoid creating odd looking gaps.

Mitopia® (and the plugin renderers) provides full support for highlighting areas of the text under program control and also for the automatic and pervasive creation of hyperlinks within displayed text.  In the ‘borderCountries’ field screen shot, we see the effect of turning on the ‘Country’ hyperlink domain.  Clicking on any of the hyperlinks displayed will result in navigating to and displaying the associated record through Mitopia’s invocation abstraction.  In the final screen shot for the ‘executive’ field we see a situation where the renderer has been unable to fit all the text into the display area due to layout constraints, in which case the text control is size limited and can be selected and scrolled as shown in order to examine the entire text string.

Styled Text

In the screen shot above (taken from the stemmer development window), we see on the far right an HTML display field extracted from a dictionary definition of the word ‘abdicate’.

If you look in the base ontology under the type DictionaryEntry, you will note that the ‘description’ field is intended to hold HTML text.  During AutoUI generation, the content of any valued ‘@char’ field is examined, and if it contains a block bounded by “<html” and “</html>”, an HTML control is used instead of a standard text control.  The effect is that persistent records can contain text styled using HTML which can thus be displayed throughout the standard auto-generated UI.  Of course this capability to embed HTML into the fields of a record should be used sparingly since the embedded HTML tags within the field make the content less useful for search purposes, and it is not clear how such HTML fields can be easily or reliably edited manually by the user.  Note that the default renderer text control is fully capable of displaying and editing simple ‘styled’ text (as indicated by the hyperlink screen shot in the previous section), the problem is that there is not currently any standardized persistent way to represent styled text in the server collections and restore the styles in user displays.

Booleans

The screen shot to the right illustrates the rendering of Boolean fields by the default renderer.  As can be seen, Booleans are rendered as checkbox controls and can be packed two to a column in most layouts.  The screen shot is of a portion of the ‘SystemRelated’ type ‘InterestProfile’ for which the corresponding Carmot field definitions appear as shown in the listing below.

Bit Fields and Enumerated Types

The use of the C bit field capability is generally restricted to cases where existing hardware registers or encoding formats must be matched or where data storage restrictions are so severe that data must be packed as tight as possible.  None of these conditions are likely to apply to ontological types declared in Carmot, although they do apply to the platform C header files which must also be compiled by the Carmot language.  For this reason, Carmot provides full support for C’s bit field syntax.  In the listing above, driven by platform headers, we see a type definition combining both bit field definition and enumerated types within those bit fields.

The two screen shots in this section illustrate the appearance of the type defined in the listing above when rendered in the default renderer.  As can be seen, the fact that a field is a bit field rather than a normal integer type makes no difference to how it is displayed and bit fields are thus indistinguishable from other numeric fields.  The fact that the ‘segment’ field is tied to an enumerated type results in it being displayed both as a numeric value and as a popup with the enumeration options as entries.  This makes the value much easier for users to understand and enter.  If the field type has an associated $MultiSelect annotation, then the popup is a multi-select popup and the field can be used to handle bit mask values such as options flags.  The use of enumerations in this manner is not restricted to bit fields of course and can be used with any integer field.

If the number of enumerated values is small and the $MultiSelect annotation is not present, for example if the enumeration were tied to a Boolean, it might be preferable for the renderer to display the field as a radio button group.  Larger radio button groups might be generated as a result of say a $RadioButton annotation on the field.

Persistent References

The display and handling of persistent references requires a text control to display the referenced item name, a popup selector to choose the referenced type, and an icon button (displaying the jagged arrow) to cause immediate navigation to the referenced item using the Mitopia® invocation abstraction.

The popup selector is rooted in the declared referenced type for the field but allows selection of more specific types (if any) during manual data entry.

During manual data entry, an additional list icon button is displayed such that clicking on the button launches a list selection dialog (as shown to the left).  This allows the user to examine the list of possible items (and their fields) that could be referenced (in this case countries).  If the domain of reference is too large, the user will be prompted to create the reference through some other means (e.g., drag & drop).

Persistent Collection References

The display and handling of collection references is performed by renderers using list controls as illustrated in the screen shots in this section.  The column headers for these list controls are driven by the $ListSpec annotation for the field or referenced type.  If no $ListSpec is specified for the field/type, inheritance will cause the $ListSpec for Datum to be used which results in a list containing just the ‘name’ field.

Lists can be sorted by column in exactly the same way described earlier for node navigation.

Double-clicking on a cell within such a list causes the referenced item to be launched and displayed via the Mitopia® invocation abstraction for “Display”.  If the ‘option’ key is held down while double-clicking on a cell, the launch is invoked for “Info”.  See other Mitopia® documentation for details.  Note that the field values displayed in the list control are the contents of the fields of the referenced item, not the referencer, and one or more of these fields may in fact be a persistent reference.  Double-clicking on such a second-level reference launches the second-level item referenced, not the primary reference.  Thus in the last screen shot above, double-clicking on a ‘name’ column cell would launch the NoteRelating record, double-clicking on a ‘relationType’ column cell would launch the RelationType record for “Picture of”, and double-clicking on a ‘related’ column cell would actually launch and display the related JPEG image.

Relative Collection References

The screen shots above illustrate the appearance of ‘@@’ fields when being edited in the auto-generated user interface.  The type definition is for the GUI Canvas type used by Mitopia’s universal GUI renderer layer.  See the type definitions in K.DEF for details on the Canvas and Control types.

The critical difference is that the layout algorithm has chosen to display the ‘controls @@’ fields in a separate tab within the containing record display, just as it would for a sub-structure.  Within that tab, the ‘@@’ collection is displayed as a full height list on the left hand side of the display while any selected node in the list is displayed in an embedded data model view to the right of the list.  Note also that the lists are both horizontally and vertically scrollable in order to account for the possibility of nested hierarchies within the ‘@@’ collection (see the lower screen shot).  Given sufficient screen real-estate, the nested lists and DMVs can be repeated for many levels, which gives the user the ability to examine in depth the inner structure of the data stored in ‘@@’ collections if necessary.  This ability is not relevant for ‘##’ collections because these are nothing more than references to the outer collection (and persistent storage), so that double-clicking on a ‘##’ list entry causes the entire display to be replaced from the outer level by the content of the referenced record.  There is thus no need to nest displays as shown for the ‘@@’ case.  In contrast, if one double-clicks on a ‘@@’ list entry in display mode, this has no effect, however, a double-click in Edit mode will cause the selected entry to be displayed in the outer DMV just as for the ‘##’ case.

The screen shot to the right illustrates the effect of double clicking on the “ListView10742” entry in the first level ‘@@’ collection.  The content of the ‘ListView10742’ record is displayed in the DMV to the right.  Relative collections fields and the types they reference can have associated “$ListSpec” annotations in a manner identical to the ‘##’ case, and in these cases, the list displayed will contain the relevant titles over and above the default “Name” column.

Since Mitopia® places few restrictions on the data that can be displayed in an ‘@@’ sub collection, they can be used for a wide variety of data processing purposes, and thus the auto-generated UI can be a very convenient way for examining these complex structures.  In particular, the sub-collection may use any of the supported organizational metaphors (tree, list, stack, ring, queue, N-array etc.).  The only restrictions placed on the data in the ‘@@’ sub collections are the following:

1. Records cannot be derived from ‘Datum’, but can use persistent (‘#’) and persistent collection (‘##’) reference fields.  Echo specifications that are mediated through ‘@@’ collection elements must use the ‘><><‘ indirect echo specification syntax (see earlier posts).
2. Record types should either have a ‘name’ field (either char[] or char@) or a $UniqueBy annotation specifying another field that is used to disambiguate different records within the same parent node of the ‘@@’ hierarchy.  If names are not unique within a given node, the associated records will be merged during MitoMine™ or when persisted to the servers.
3. The ‘@@’ nodes themselves, regardless of if they have associated values (which is permitted for any node) can be named and if they are, the merge process during MitoMine™ or when persisted to servers, will take account of the node name also.

Non-’char’ Relative References

As described previously, by default, the MitoQuest™ container registers to handle all field types other than a relative reference to a type other than char. This means that all support for rendering of these MitoQuest™ fields is provided and registered internally to Mitopia®.  When one adds a new multimedia type and a corresponding relative reference to that type as part of the Carmot ontology for a system, it is necessary also to register or add code to handle the display of that type within auto-generated UI.  This allows the renderer to display the associated item to the user.

The screen shot to the left shows the effect of this for the Image type as referenced in the ‘Picture @preview’ field of a Video.  To the right is a screen shot of the ‘Picture @picon’ field of the type Image.  The screen shot below shows that this registration of custom display formats can even be extended to persistent references to the type as in the ‘related’ field in this NoteRelating record.

By clicking on the camera icon, one can immediately launch and display the associated multimedia.  One might imagine sound references being playable in a similar manner, or indeed launch and display of any other custom registered multimedia type.

The API details of how to make the necessary registrations to accomplish these kinds of modifications are beyond the scope of this blog.

Just the fields please Ma'am

In the previous post we looked at how Mitopia® auto-generates the GUI appropriate for examining and navigating a collection of nodes, in this post we will begin to look at how the GUI to display and handle the content of a given node is auto-generated.

The most critical component of the GUI renderer’s control set is the existence of a control type that is capable of performing ontological field discovery and layout through the DataModels abstraction.  We will refer to this control type as the Data Model View Control (DMVC).  A DMVC is created by Mitopia’s AutoUI package when any request to display data occurs.  The DMVC is set to a rectangular size as determined by the available UI display area.  The DMVC is then ‘linked’ to the data record in the collection that it is to display.  From that point on, all GUI creation and handling is automatic by the GUI renderer through discovery of the fields within the record linked using the DataModels abstraction and API.

The screen shot above illustrates the initial appearance of the DMVC when showing a Country record.  The DMVC has represented the various sub-structures it discovered within the Country record as tabbed panels.  As can be seen , not all tabs will fit into the available screen space so the last tab spot is replaced by a popup menu from which the user is in the process of selecting from the full list of sub-structures.  Note also that the DMVC is displaying the inherited fields of Datum along with the initial fields declared in Country in the first tab panel labelled by the type name Country.  The DMVC shows sub-structures inherited or directly declared in Country as tabs on the top line.  The ‘notes’ and ‘location’ sub-structures are part of the Datum type and hence show as tabs on the top line.  If these values had not been sub-structures in Datum, but directly declared, they would have been displayed directly in the first ‘Country’ tab, and this would have been confusing visually for the user.  For this reason (and others), these fields were organized in sub-structures with easily recognizable names so that the user would not have to see them for every record displayed, and yet could quickly locate them in a known place when needed.  Thus we see that the visual layout of the data in the DMVC is a significant driver on the organization of fields into sub-structures in the Carmot ontology.  This same layout philosophy drove the choice of all the other sub-structures of Country as can be seen from the popup menu selections in the screen shot.

The tabs for ‘actor’ and ‘entity’ are particularly interesting in this regard.  During the ontology development, it became obvious that having the fields of Actor and Entity (see screen shot to the left) displayed on the front tab of every Actor-derived type was confusing for most users.  To avoid this, it was desirable to move these fields to a separate tab.  Thus the declarations of the types Actor and Entity had to be modified as shown in the listing below:

As can be seen from the listing, by moving all the fields of Actor into a sub-structure ‘actor’, and those of Entity in a sub-structure ‘entity’, we obtain the desired result in the GUI, which is to move all these inherited fields out of the first tab display content for all descendant types.  Obviously, this is a tradeoff since if we choose to move all inherited fields into other tabs then there will be nothing much displayed in the initial tab most of the time.  However, we are guaranteed that the ‘essential’ fields of Datum will be displayed in all cases so regardless of type we will see all the fields down to ‘symbology’ on the front tab and this is enough to get at least an idea of what the record describes.  The logic with any renderer DMVC should use for layout of fields at any level of structure nesting, is as follows:

1. Display all direct fields of a type on the front tab for the structure
2. Display all sub-structures or ‘@@’ fields (in the order they are encountered) as additional tabs.  If a sub-structure starts with an ‘_’ character, the renderer may optionally choose to not display a separate tab, but instead display the structure contents directly within the parent tab as peers of the structure field itself.  This convention allows additional ontology control over GUI layout.
3. If there are no sub-structures, do not create any tabbed panels
4. If not all direct fields fit into a given tab panel, create numbered sub-panels.

As implied by the rules above, this logic should be repeated for every level of sub-structure nesting discovered within a type by stacking tabbed panels within each other.  The screen shot above illustrates the display after selecting the “People” tab of a Country.   As you can see, choosing the “People” tab results in displaying the fields of that sub-structure within the tab area but since there are additional sub-structures within ‘people’, a second row of tabs is created to handle this.  In this case the second row of tabs uses an alternate rectangular appearance rather than the rounded tabs found at the first level.

By comparing the Carmot declaration for the sub-structure ‘people’ within the type Country given in the listing above, it should be obvious how the repeated application of the simple logic for tabbed panel creation results in the display shown in the screen shot.  Note that all the directly declared fields of the sub-structure may not fit into the display area for the tab so the algorithm may be forced to create another numbered set of sub-tabs to allow all fields to be displayed.  Other renderer plugins adopt different solutions to this problem.  This is illustrated for ‘government’ where the result of selecting the “3” sub-sub-tab would be to display the following:

Within any given tab panel, the fields are laid out according to their field type using visual representations and strategies as described in the subsequent sections.

Obviously, the layout strategy described above is just one of many possible strategies, indeed the small numeric popup at the top right of the DMVC can be used to dynamically modify the number of columns that should be used within any given tab to represent fields.  The fewer columns used, the more sub-sub-tabs may be required to display all the fields, but the more text it is possible to display at any given time.  Conversely making too many columns prevents the correct layout of certain fields and should only be allowed by the renderer if there is sufficient screen real estate to display data correctly in the number of columns selected.

If the fields of a sub-type can be fully displayed within the parental tab then the layout algorithm might choose to display the sub-type within the parent tab as a ‘bordered’ view for example.  Another possible layout strategy would be to view the DMVC rectangle as a scrolling ‘window’ onto the equivalent of a printed listing of the various fields and sub-fields.  This strategy has the advantage of simplicity of layout computation and might be appropriate for printed reports or in less capable GUI environments (e.g., the web), but for large and deeply nested structures, this scrolling approach leads to loss of context and can be very slow to navigate.  As a matter of fact, another registered Mitopia® GUI web renderer uses this exact strategy to represent data.  Many other layout strategies are possible, all based on sub-division or scrolling of the available visual rectangle for the DMVC.  One huge advantage of the dynamic DMVC approach to GUI layout is that new decisions will happen as the enclosing window is resized as a result of additional screen real estate becoming available, the GUI is this much more adaptive to the current visual environment.  For example, one can zoom the GUI window to fill a large (e.g., 30”) screen to see more fields at once as in the screen shot below.

Furthermore, as can be seen from the screen shot, allocated field display size can be changed dynamically depending on how much data/text is actually in the field for the record concerned, that is the layout of any given type will vary dynamically for each different record displayed in order to make best use of available screen real estate.  Regardless of the particular layout strategy utilized by the renderer within the DMVC, the operation is identical since all fields and layout hints are discovered dynamically through the DataModels abstraction layer.

We will explore GUI auto-generation in more detail in future posts.

Auto-generating the GUI

In earlier posts we introduced what I refer to as "The Bermuda triangle problem", which is the inevitability of knowledge of the database content, application specifics, and GUI implementation from insidiously leaking into each supposedly isolated area and thus rendering complex software fragile and difficult to maintain.  One aspect of Mitopia's solution to this dilema is the fact that the overwhelming majority of all user interfaces are auto-generated and auto-handled based entirely on the system's ontology which is discovered at run time.  This approach removes all knowledge of the specifics of the the data from the GUI code, and breaks this critical dependency that commonly causes large scale project failures.  We have earlier delved into the expressive power (in a GUI sense) of the tagged union concept, but have not as yet examined the broader subject of GUI auto-generation itself.  In this post we will begin to explore some of the basic concepts involved in GUI auto-generation.

Since auto-generation is controlled by the ontology, we will ultimately be examining in detail the specifics of how the Carmot ontology for a system is used to generate and handle the system user interface in an automated manner.  Because the user interface appearance and behavior both for display and data entry is driven directly off the ontology definition according to the principles laid out in this this (and later) post(s), it is essential for anyone using a Mitopia®-based system or contemplating changes to the system ontology, to fully understand the UI impact, as well as the persistence and query impact, of those changes (since these areas are also auto-generated/handled).  Any ontology change, no matter how small, must be considered carefully from both perspectives in addition to its ontological ramifications before it is introduced.

Naming Conventions and UI Labels

In order to construct human readable control labels for auto-generated UI, it is essential that the field names within all ontological types follow a strict naming convention.  When generating labels for UI, Mitopia® processes the raw field name (not the entire path) as follows:

• Convert underscores to spaces, capitalizing any letter that immediately follows the underscore
• Capitalize the first letter
• Insert a space in front of every capitalized letter that immediately follows a lower case letter
• Capitalize any letter that immediately follows a '.' character (field path delimiter)
• De-capitalize the first letter of any of the following filler words (unless they start the sentence): "an","and","of","the","or","to","is","as","a"

So for example:

"aFieldName" would become "A Field Name" in the UI, as would "a_field_name"
"timeOfDay" would become "Time of Day" in the UI, as would "time_of_day"

By careful choice of the name given to a field it is therefore possible to ensure that the label for that field as shown in the GUI is easily readable by human beings.  The use of case to indicate implied word boundaries in this manner is often referred to as CamelCase.  One thing to watch out for is making the field name too long as this may cause it not to fit well into the allocated display area.  By convention, field names within all Mitopia® and Carmot types should start with a lower case letter (preferably not k - which implies a constant).  Because the first letter of the field name is capitalized in the process above before it is displayed, the use of a leading lower case letter allows field names to be distinguished immediately from type names within the code by virtue of the fact that type names by convention always start with an upper case letter.  Additionally, although the algorithm above handles underscore characters by converting them to a space, by convention the underscore character should not be used in field names, since spaces can always be created by a transition from lower to upper case.  An additional convention used in field naming is that any field that starts with a leading underscore character should be ‘invisible’ in the UI.  Invisible fields are often introduced into Carmot types in order to ‘pad’ the field alignments to ensure that the structure layout is invariant across all architectures and compilers.

All field and type names in the Carmot ontology must be readable and understandable in English and contain only ASCII characters, it is not acceptable to name fields based on other languages.  This is because the GUI labels created from field names by the algorithm described must be translated into other languages when the GUI language is switched from English.  The Mitopia® translation capability that is responsible for this is predicated on the fact that all initial text strings are in English and so this must also be true of Carmot field and type names. 

When choosing a field (or type) name, you should be careful not to let the specific situation that caused you to add the field influence the field name any more than is appropriate.  If you have designed your ontology change correctly, then you will have abstracted from your specific problem and will probably be adding a field to ancestral or referenced types.  Nothing is more confusing than a field name in some type that does not make sense when viewed entirely from the perspective of that type.  Even if this means that the field name you use to enter your information is not the one you might have chosen if the domain were restricted just to the original problem that prompted the change, it is essential that you follow this approach, otherwise it is unlikely that anyone will use the new field in any other descendent types.  Over time this leads to a fragmented ontology where multiple fields serve similar purposes at different levels of the ontological hierarchy.  This in turn makes data stored in this manner less useful for analytical purposes and even for search.

If a field name will not fit into the available display area in a given layout, the GUI renderer is responsible either for re-layout of the GUI to ensure full label readability (preferred), or failing that for eliminating a portion of the name display and replacing it with the ellipses character(s) (i.e., ‘...’) while maintaining as much of the original label name as possible in order to allow the full label to be easily guessed by the user.  The screen shots to the left illustrate this effect in the case of successively re-sizing a list control displaying country names.  This effect is more likely to occur with actual control labels following translation of the display to another language, since the translated string might occupy much more space than the original.

Browsing Collection Nodes

The screen shot to the right illustrates the two main aspects of displaying and browsing Carmot data organized in a collection.  On the left side is a list control which is being used to browse a hierarchical collection of nodes organized according to the Carmot ontology for the system.  On the right side is the display of the fields/contents of the selected node in the collection.  The display of node values is accomplished by the “Data-Model View Control” (DMVC), which will be described later.

As can be seen, the hierarchy of nodes in the collection can be navigated in the list control using disclosure triangles.  The non-leaf nodes are named by Mitopia® according to the Carmot ontology type and so this is displayed in the GUI.  In the case of leaf (i.e., valued) nodes, the actual collection node is not named but the DataModels abstraction is aware of the requirement that all persistent data have an ‘@name’ field and so when asked by the GUI renderer for a node name, it returns the content of this field.  The result is a list display where every node has a recognizable name.

You will note that the list control shown is only showing collection type nodes from ‘Entity’ downwards despite the fact that like all collections derived from persistent data, the collection being displayed has a root node called ‘Datum’.  This reduction of clutter is accomplished by only starting to display collection nodes from a parent node that has more than one child.  Since the list shown is the result of a query for ‘Entity’ whose name contains the word “John”, there are no other children of higher ancestral types like ‘Datum’ or ‘Actor’ and so the list can omit these nodes when displayed.  The obvious result of this is that if the collection contains only one distinct type then it may be displayed as a straight linear list without any disclosure hierarchy.

The list may contain multiple columns, each of which displays the content of a particular field.  The initial column list is driven by the $ListSpec annotation however the user can control this column set, for example in the Query Builder the user might have chosen additional fields using the “Display Fields...” button in the Query Builder which would yield the collection browser list shown below:

The node name is always the first column displayed and cannot be eliminated since it is necessary to display the hierarchy.  Obviously the purpose of displaying additional columns is to allow the user to more rapidly determine the information they need to know simply by examining the list.  Note that there are three different types of fields involved in the columns selected in the screen shot.  The ‘datumType’ field is a character string, the ‘dateEntered’ field is a double precision floating point number, and the ‘source’ field is a persistent reference (‘#’).  The GUI renderer makes use of Mitopia® API functions to convert any field value, regardless of type, to a string that can be displayed and thus the renderer does not need to implement this logic internally.

Another key capability of the multi-column list is that the user can use such a list to sort displayed data according to whatever criteria he wishes.  Sorting is initiated by clicking on the column header to sort by, while (in the renderer depicted) sort direction is controlled by the direction triangle in the top right of the list control.  All sorting is performed by the renderer calling back into one of Mitopia’s DataModels API functions and then simply re-rendering the collection which is sorted within the Mitopia® flat memory model and thus returns nodes in a different order to that used previously.  Note that in the final sort the user held down the ‘Option’ key while sorting on a text field and this has the effect of sorting as if the field text string were written backwards, i.e., last letter to first.

Clearly, a list control is just one of the possible means of navigating a hierarchy and the renderer may choose to use different methods depending on the situation and layout constraints.  Regardless of the method chosen, the renderer callbacks into the DataModels API are identical.  The screen shot to the right shows the user navigating the main “View” menu of the Mitopia® application.  This is also a collection hierarchy but in this case the renderer is using a menu-bar rendering strategy to display the data it discovers.  In this case the nodes found within this collection under “Language” have icons associated with them (which are discovered by the renderer using the DataModels abstraction which keys off the $Icon annotation).

Obviously popup menus are yet another variant that can be used by renderers to display and navigate a collection hierarchy.

The ‘Column View’ approach to representing and navigating a hierarchy is a useful alternative to the list control in cases where the number of children below a given node in the tree can be so large, or the tree becomes so deep, that it becomes difficult to maintain visual context of where one is in the hierarchy.

Another useful UI metaphor for hierarchy navigation is the ‘Graph View’ which provides a scroll, pan, and zoom workspace within which the node hierarchy can be navigated and explored.  You can see an example of this navigation metaphor in the Visualizer widget when navigating the collection of ‘things’ within the control room as shown below.

Another example (which matches the column view content above) is shown below:

Below the surface, all of the navigation metaphors shown in this post use the identical set of DataModels data discovery API calls to determine the content of any collection of persistent data.  All are effectively equivalent and interchangeable, depending on UI layout considerations.  This is very analogous to the MVC design pattern which allows the specifics of the UI to be kept separate from ‘Model’, however in this case the entire process is performed dynamically from the Carmot ontology, and so the separation is complete.  There is no specialized ‘Model’ code to support the renderer’s GUI strategies.

In future posts we will examine auto-generation strategies for display the content/fields of data as opposed to the hierarchy of the node organization within the collection.

Defining a language grammar

In my previous post, I introduced some basic concepts for Mitopia's parser abstraction.  In this post I'd like to give a sample complete language definition, in this case for a C programming language expression evaluator.  We will use this language definition in later posts to discuss more complex concepts.

Firstly, we will need a lexical analyzer capable of recognizing all the necessary C language operators and operand types that might be involved in an expression or assignment.  In an earlier post, I have already introduced the basic concepts of the Mitopia® lexical analysis package so I will not describe the lexical analyzer in further detail herein.  Also it is assumed that the reader is familiar with, or has access to documentation on, the C language in order to assist them in interpreting the lexical analyzer specification (Calculator.LXS) below:

Mitopia Lexical Analyzer Specification for C expression evaluator

It should be obvious by comparing the recognizer specification above with the C language syntax specification in any C text book that this recognizer can identify all potential tokens appearing in a C expression or assignment.  Given this recognizer, we can now define a parser for C expressions/assignments (Calculator.BNF) that uses these token numbers as follows: 

Mitopia Parser Specification for C expression evaluator

This parser specification utilizes the tokens from our lexical analyzer specification (both the ‘oneCat’ tokens like ‘++’ and the ‘catRange’ tokens like ‘<3:DecInt>’) to define the operator precedence and syntax for our expression and statement evaluator.  Note that in this BNF, expressions can include parameterized function calls (as for C itself), the productions to handle this are the last four listed in the BNF.  Obviously this allows even this simple parser to support a language involving an extensible function set.

For now we will ignore how these specifications are tied together with the code that will actually execute the calculator functionality and focus on the insights that can be gained into the Mitopia parser abstraction by use of this example grammar.

Referring to our example,  this BNF gives a relatively complete description of the C language expression syntax together with enforcement of all operator precedence specified by ANSI.  This BNF is sufficient to create a program to recognize and interpret C expressions and assignments.

You will notice that precedence order is specified simply by choosing the order in which one production leads to another with the lowest precedence grammar constructs/operators being refined through a series of productions into the higher precedence ones.  Note also that many productions lead directly to themselves (e.g. more_statements ::= <null> <or> statement ; more_statements); this is the mechanism used to represent the fact that a list of similar constructs is permitted at this point.  If you look in any C book, you will find a section describing the syntax of the language either as syntax diagrams for a series of grammar productions similar to that above (ignoring Mitopia’s unique EBNF symbols for now).  Most computer languages are specified in this way and to make a parser for an existing language using this package, all you essentially have to do is type in the grammar productions as they appear in the language specification.  The way of specifying a grammar used above is a custom variant of the Backus-Naur Form.  It is the oldest and easiest to understand means of describing a computer language.  The symbols (enclosed in ‘<‘, ‘>’ delimiters) described in the table in my previous post, plus the '::=' symbol are referred to as meta-symbols, that is they are not part of the language, but they are part of the language specification.

A production of the form (non_terminal ::= production_1 <or> production_2) means that there are two alternative constructs that 'non-terminal' can be comprised of; they are 'production_1' or 'production_2'.  The grammar for a realistic programming language may contain hundreds of these productions, for example, the definition of Algol 60 contains 117.  An LL(1) parser must be able to tell at any given time what production out of a series of productions is the right one, simply by looking at the current token in the input stream and the non-terminal that it currently has on the top of it's parsing stack.  This means, effectively, that the sets of all possible first tokens for each production appearing on the right hand side of any grammar production must not overlap; the parser must be able to look at the token in the input stream and tell which production on the right hand side is the 'right one'.

The set of all terminals that might start any given non-terminal symbol in the grammar is known as the FIRST set of that non-terminal.  When designing a language to be processed by the parser abstraction, ensuring that these FIRST sets are not multiply defined is most of the work.  In order to understand how to write productions acceptable to an LL(1) parser, (LL(1) stands for 'Left-to-right, using Leftmost derivations, using at most 1 token lookahead') we must understand recursion in a grammar and the difference between left and right recursion in particular.

If the parser tries to use a production of the form 'A ::= A anything' then it will fall into an infinite loop trying to expand A, this is known as left recursion.  Left recursion may be more subtle, as in the pair of productions 'S ::= X a <or> b' and 'X ::= S c <or> d'. Here the recursion is indirect; that is the parser expands 'S' into 'X a', then it subsequently expands 'X' into 'S c' which gets it back to trying to expand 'S', thereby creating an infinite loop.  This is known as indirect left recursion.  You must eliminate all left recursion from your grammar.  You do this simply by replacing all productions of the form 'A ::= A anything' (or indirect equivalents) by a set of productions of the form "A ::= t1 more_t1 <or> ... <or> tn more_tn" where t1..tn are the language tokens (or non-terminal grammar symbols) that start the various different forms of 'A'.

Recursion is usually used in grammars to express a list of things separated by some separator symbol (e.g. comma).  This can be expressed either as "A ::= A , B" or "A ::= B , A".  The first form is left recursive and thus cannot be used; the second form is known as right recursive and is perfectly acceptable.  The production "more_statements ::= <null> <or> statement ; more_statements" in the Calculator BNF is an example of a right recursive production.

A standard problem with top down parsers, in general, is that the order of the alternative productions is important in determining if the parser will accept the complete language or not.  In the Mitopia® parser abstraction, we avoid this problem by requiring that the FIRST sets of all productions on the right hand side be non-overlapping.  Thus in conventional BNF, it is permissible to write:

expression ::= element <or> element + expression <or> element * expression

To meet the requirements of PS_MakeDB() and of an LL(1) parser, we must reformulate this BNF statement into a pair of statements viz:

expression         ::= element rest_of_expression

rest_of_expression ::= <null> <or> + expression <or>  * expression

As can be seen, the 'element' token has been factored out of the two alternatives (a process known as left-factoring) in order to avoid the possibility of multiply defined FIRST sets.  In addition, we have added a new symbol to the BNF meta-language, the <null> symbol.  A <null> symbol is used to indicate to the parser generator that a particular grammar non-terminal is nullable, that is, it may not in fact be present at all in certain input streams.  There are a large number of examples of the use of this technique in the Calculator BNF grammar above.  

If we wished to limit ourselves to LL(1) grammars then these are the only grammatical issues we would have to face.  However, LL(1) grammars are very restrictive and the parser is capable of accepting a much larger set by the use of deliberate ambiguity.  Consider the grammar:

operand ::= expression <or> ( address_register )

This might commonly occur when specifying assembly language syntax.  The problem is that this is not LL(1) since expression may itself start with a '(' token, or it may not, thus when processing operand, the parser may under certain circumstances need to look not at the first, but at the second token in the input stream to determine which alternative to take.  Such a parser would be an LL(2) parser.  We cannot solve the problem by factoring out the '(' token, as in the expression example above, because expressions do not have to start with a '('.  Thus without extending the language beyond LL(1) we would be unable to handle this situation.  Consider however the modified grammar fragment:

operand ::= .... <or> ( expr_or_indir <or> expression

expr_or_indir ::= Aregister ) <or> expression )

Here we have a production for operand which is deliberately ambiguous because it has a multiply defined first set since '(' is in FIRST of both of the last two alternatives.  However, we have arranged the order of the alternatives such that the parser will take the "( expr_or_indir" production first and, should it fail to find an address register following the initial '(' token, the parser will then take the second production which correctly processes "expression )" since as stated before expression itself need not begin with a '(' token.  If we allow this case, we have created the equivalent of a two token look-ahead in the parser, hence the language it can accept is now LL(2).  An options parameter 'kIgnoreAmbiguities' can be passed to PS_MakeDB() to cause it to accept grammars containing such FIRST set ambiguities, however, it can no longer verify the correctness of the grammar and it is the responsibility of the language definer to ensure that the first production can always be reduced to the second when such a grammatical trick is used.  It is best not to use the 'kInoreAmbiguities' parameter unless one is certain of what they are doing.

We are not quite done yet because grammars can get considerably nastier than LL(2).  To continue a theme, consider the problem of parsing the complete set of 68K assembly language addressing modes, or more particularly the absolute, indirect, pre-decrement and post-increment addressing modes.  The absolute and indirect syntax was presented above, however the pre-decrement addressing mode adds the form "-(Aregister)", while the post-increment adds the form "(Aregister)+".  We would need an LL(3) parser (and some fancy grammar productions) to handle the pre-decrement mode, since the parser cannot positively identify the pre-decrement mode until it has consumed both the leading '-' and '(' tokens in the input stream.  An LL(4) parser is necessary to recognize the post-increment form.

It is true that if all we were trying to do was recognize valid assembly syntax, we could just left-factor out the "( Aregister )" for the post-increment form, but we want to actually perform some useful function with the parser and this is accomplished by inserting reverse polish plug-in operator calls of the form <@n:m[:hint text]> into the grammar (see the Calculator EBNF above) and later posts. Whenever the parser exposes such a meta-symbol on the top of the parsing stack, it calls the registered plugin function in order to accomplish some sort of semantic action or processing.  Given the fact that we might wish to call a different plug-in to handle each of the different 68K addressing modes, we must ensure that we do not call the wrong one before we are absolutely sure that we know what addressing mode we are dealing with.

So, we must extend the parser language set to be LL(n) where 'n' could be quite large.  One mechanism used to do this is to provide explicit control of limited parser back-up capabilities by adding the <bkup> meta-symbol.  Backing up a parser is a lot more complex than it might sound since the parsing stack must be repaired and the lexical analyzer backed-up to an earlier point in the token stream in order to try an alternative production.  Nonetheless, the PS_Parse() parser is capable of limited backup within a single input line by use of the <bkup> flag.  Consider the modified grammar fragment:

operand ::= ... <or> ( Aregister <bkup> areg_indirect <or> abs_or_displ <or> ...

abs_or_displ ::= - ( ARegister <bkup> ) <@1:1> <or> expression <@1:2>

areg_indirect ::= ) opt_postinc

opt_postinc ::= <@1:3> <or> + <@1:4>

Reverse polish operators are discussed in later posts, but let us assume that <@1:1> is the handler for the pre-decrement mode, <@1:2> for the absolute mode, <@1:3> for the indirect mode, and <@1:4> for the post-increment mode.  Now when the parser encounters a '(' token it will push on the "( Aregister <bkup> areg_indirect" production.  As it does so, it notices the presence of the <bkup> symbol in the production being pushed and it saves it's own state as well as that of the input lexical analyzer.  Parsing continues and the '(' is accepted.  Now let us assume that the input was actually an expression so when the parser tries to match the 'ARegister' terminal that is now on the top of it's parsing stack, it fails.  Without the backup flag, this is considered a syntax error and the parser aborts; however because the parser has a saved state, it instead restores the parser and lexical analyzer state to that which existed at the time it first encountered the '(' symbol, it then causes the production that immediately follows the one containing the <bkup> flag to be selected in preference to the original.  Since the lexical analyzer has also been backed up, the first token processed is once again '(' and parsing proceeds normally through "abs_or_displ" to "expression" and finally to invocation of plug-in <@1:2> as appropriate for the absolute mode.  Note that a similar but slightly different sequence is caused by the <bkup> flag in the first production for "abs_or_displ" and that in all cases, the plug-in that is appropriate to the addressing mode encountered will be invoked and no other.

Thus by this use of explicit ambiguity plus controlled parser backup, we have created a parser capable of recognizing languages from a set of grammars that is considerably larger than those normally associated with predictive parsing techniques.  Indeed the set is sufficiently large that it can probably handle any practical computer programming language.  By judicious use of the plug-in and resolver architectures (see later posts), this language set can be extended even further and can also include grammars that are not context-free (e.g. English) that cannot be handled by conventional predictive parsers.  Once again, be warned if your language is LL(1), then the parser generator will automatically check correctness of the grammar.  However once you start using the techniques above, it is up to you to ensure that your grammar works as you expect.

One more concept that must be introduced in order to understand how to build grammars for parsers is the concept of a FOLLOW set.  For any non-terminal grammar symbol X, FOLLOW(X) is the set of terminal symbols that can appear immediately to the right of X in some sentential form.  In other words, it is the set of things that may come immediately after that grammar symbol wherever it can occur in the source text.  For example, by looking at the Calculator grammar above we can see that FOLLOW(expression) contains just three symbols, namely ‘)’,  ‘;’, and ‘,’.

To see why, we look at everywhere expression occurs in the BNF.  In the line “primary ::= ... <or> ( expression )” it is followed by ‘)’, in the lines (“parameter_list := ... <or> expression rstof_param_list” and “rstof_param_list ::= <null> <or> , expression rstof_param_list”) we see that expression may be followed by another rstof_param_list which begins with ‘,’ and finally since expression may end a statement, and statement is followed by ‘;’, we come up with FOLLOW(expression) = ‘)’ ‘;’ ‘,’.

To build a predictive parser table PS_MakeDB() must compute not only the FIRST set of all non-terminals (which determines what to PUSH onto the parsing stack), but also the FOLLOW sets (which determines when to POP the parsing stack and move to a higher level production).  If the FOLLOW sets are not correct the parser will never pop it's stack and eventually it will die. So for this reason, unlike for FIRST sets, ambiguity in the FOLLOW sets is not allowed.  What this means is that for any situation in your grammar, the parser must be able to tell when it is done with a production by looking at the next token in the input stream (i.e., the first token of the next production).  This is usually much easier to arrange than is unique FIRST sets.  PS_MakeDB() will reject any grammar containing ambiguous FOLLOW sets.

This post discusses some very simple parser concepts, we will explore the Mitopia® parser abstraction further in later posts.