home *** CD-ROM | disk | FTP | other *** search
/ Amiga Developer CD 2.1 / Amiga Developer CD v2.1.iso / Extras / IFF / IFF_Forms / TREE.doc < prev    next >
Encoding:
Text File  |  1993-03-01  |  2.5 KB  |  88 lines
  1. Storage of arbitrary data structures as trees (or nested lists).
  2.  
  3. Date Submitted:    23-JUN-92
  4. Submitted by:    Stefan Reisner
  5.         sr@ph-cip.Uni-Koeln.DE
  6.         Aachener Straße 399
  7.         5000 Köln 41
  8.         Germany
  9.         Phone 0221 / 40 59 16
  10.  
  11. IDEA / MOTIVATION
  12. =================
  13.  
  14. This IFF FORM format was defined as the basic filing and clipping
  15. format for QED and its successors.
  16.  
  17. QED is mainly a symbolic math (formula) editor, but can be thought
  18. of (and be configured) more generally as an editor that can process
  19. ANY formally defined data structure representable as a tree (or
  20. equivalently as nested lists) of symbols (such as letters, words,
  21. numbers etc.).
  22.  
  23. The "representation as nested lists" issue is obvious
  24. (at least to those who are familiar with Lisp).
  25.  
  26. This approach to data abstraction tries to represent any object with
  27. a particular data structure by an instance of one same class, the
  28. class of trees (or nested lists).
  29.  
  30. It should work as long as the object in question can be decomposed
  31. into irreducible (atomic) pieces of information that are small enough
  32. to be represented by textual symbols.
  33.  
  34. Examples:
  35.  
  36. Consider a C-style structure:
  37.  
  38.     struct
  39.     {
  40.         some_type field_1;
  41.         ...
  42.         some_type field_n;
  43.     };
  44.  
  45. or a vector
  46.  
  47.     some_type vector[n];
  48.  
  49. Both are basically just lists of their components. The components
  50. are possibly structures or vectors themselves, and so on. Finally,
  51. "atomic" components (scalar types char, word, long, float, double)
  52. will appear.
  53.  
  54. The tree structure can even represent data structures that are not
  55. as rigid as C-style structures or vectors. This can be achieved by
  56. placing a field identifier symbol in front of each field,
  57. eliminating the need of a fixed order of fields.
  58.  
  59. Further examples: see the Lisp language.
  60.  
  61. CHUNKS
  62. ======
  63.  
  64. The only new chunk to be defined here is FORM TREE.
  65.  
  66. There are two possible shapes a FORM TREE can have: the terminal (leaf)
  67. shape and the non-terminal shape.
  68.  
  69. Terminal (leaf) shape of a FORM TREE:
  70.  
  71. The terminal shape of a FORM TREE consists of exactly one TEXT chunk
  72. (unformatted ASCII text), containing the terminal symbol.
  73.  
  74. Non-terminal shape of a FORM TREE:
  75.  
  76. The non-terminal shape of a FORM TREE consists of exactly one LIST TREE
  77. chunk containing itself any number (including zero) of FORM TREEs.
  78.  
  79. Thus we have the following syntax:
  80.  
  81. tree         ::= "FORM" #{ "TREE" ( terminal | non-terminal ) }
  82. terminal     ::= "TEXT" #{ symbol string }
  83. non-terminal ::= "LIST" #{ "TREE" tree* }
  84.  
  85. The absence of PROP chunks is intentional, because they are unnecessary:
  86. Any such information can and should be stored as part of the actual data
  87. structure.
  88.