gSlip

Gnu Slip (gSlip) is an API written in C++ for the construction and maintenance of a Directed Acyclic Graph (DAG), where each node on the graph consists of two lists, a standard list and an associative list of <key, value> pairs. gSlip is an outgrowth and extension of SLIP, an API developed by Dr. Weizenbaum in 1963 and described in the Communications of the ACM v6n9 publication.

The list cells are symmetric in the sense that each cell points to the previous cell in the list, and the next cell in the list, that is, the cells are doubly linked. The node header points to the first and last cell in the standard list, and points to a list of sublists (nodes) of <key, value> lists for the asscoiative list.

gSlip has 3 types of list cells, a list header (SlipHeader), list data (SlipDatum) and a sublist (DAG child) reference. The SlipDatum cells can hold a character, integer, floating point number and string. Each of these cells can participate in operations suitable to their types in the same manner as in C++. That is, in the computation x = y + z any or all of x, y, and z can be a gSlip cell. This includes all C++ operators.

SlipDatum data is dynamic and can change during application processing. This means that a cell, x, can change from an integer to a floating point with an assignment statement, x = 1; x = 1.0 without changing the application logic. Casting, and other needed operations, are automatically done as required, x += y; will be 2 or 2.0 depending on whether y is 1 or 1.0 and x is 1 or 1.0;

gSlip supports an iterator (SlipReader). The iterator can search for SlipDatum cells (data bearing or sublist references or both) linearly, in a single list, or structurally, descending in depth first order in a DAG.

gSlip maintains a fast and effient mechanism for cell creation and deletion. This space is expandable at runtime if allocated space is insufficient. For embedded application, space allocation can be inhibited from growing. By construction, the gSlip space does not have memory holes and does not need a garbage collector.

Output and input of lists are fully supported and retain list reuse, where the same list is referenced multiple times, and application marking of SlipHeader cells.

Input and output lists are written as a parenthesis enclosed list, an S-Expression. That is: (a 1 'B' 3.0 ("list")) is a list containing data and a sublist, a DAG with a single leaf node.

If we have a list L then L = read(write(L)); and L = write(read(L))

Downloadable objects:
User Manual
Source Code
Test package

TODO

• Expand SlipDatum to support user defined data types.
• Create smart pointers for SlipDatum and SlipHeader cells.