idnits 2.17.1 draft-long-external-obj-lang-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-19) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 48 longer pages, the longest (page 2) being 60 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 49 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There is 1 instance of lines with control characters in the document. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 199: '...common OS's. It MAY mean that, but it...' Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 579 has weird spacing: '...schesis the ...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 29, 1997) is 9669 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: 'E' on line 741 == Missing Reference: '10' is mentioned on line 741, but not defined -- Looks like a reference, but probably isn't: 'A' on line 756 == Missing Reference: '4' is mentioned on line 756, but not defined -- Looks like a reference, but probably isn't: 'F' on line 756 == Missing Reference: '6' is mentioned on line 756, but not defined -- Looks like a reference, but probably isn't: 'G' on line 756 == Missing Reference: '19' is mentioned on line 756, but not defined -- Looks like a reference, but probably isn't: 'C' on line 2118 == Missing Reference: '32' is mentioned on line 2118, but not defined -- Possible downref: Non-RFC (?) normative reference: ref. '1' Summary: 9 errors (**), 0 flaws (~~), 9 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet-Draft B. Long 3 draft-long-external-obj-lang-00.txt 4 April 29, 1997 5 Expires October 29, 1997 7 XODL: External Object Description Language 9 Status of this memo 11 This document is an Internet-Draft. Internet-Drafts are 12 working documents of the Internet Engineering Task Force 13 (IETF), its areas, and its working groups. Note that 14 other groups may also distribute working documents as 15 Internet-Drafts. 17 Internet-Drafts are draft documents valid for a maximum 18 of six months and may be updated, replaced, or obsoleted 19 by other documents at any time. It is inappropriate to 20 use Internet-Drafts as reference material or to cite them 21 other than as "work in progress." 23 To learn the current status of any Internet-Draft, please 24 check the "1id-abstracts.txt" listing contained in the 25 Internet-Drafts Shadow Directories on ftp.is.co.za 26 (Africa),nic.nordu.net (Europe), munnari.oz.au (Pacific 27 Rim),ds.internic.net (US East Coast), or ftp.isi.edu (US 28 West Coast). 30 ABSTRACT 32 This document describes a data structure (XODL: Object 33 Description Language) and an associated method which, 34 together, provide a means of representing situations or 35 types of situations. It can thus be used to represent 36 objects, events, or systems of objects and events or 37 types of objects, events or systems. Objects represented 38 can be computer data objects ("stack", "word processor", 39 "user interface", etc.) or "real" objects such as 40 computers, networks, users, and so on. 42 Table of Contents 44 1 INTRODUCTION 45 2 THE XODL SPECIFICATION 46 2.1 Informal Discussion of XODL 47 2.1.1 Introduction to XODL Names 48 2.2 The Formal Specification 49 2.2.1 Notational Conventions 50 2.2.2 StatementLists 51 2.2.3 RelationStmts 52 2.2.4 InfoRefs 53 2.2.5 Names 54 2.2.6 Representing Types 55 3 AVAILABLES: NAMES OF AVAILABLE INFORMATION 56 3.1 Typing ConstantInfos 57 4 EXAMPLES 58 4.1 Enumerations 59 4.2 Records and Type-Definitions 60 4.3 Unions, Multiple-Option Types 61 4.4 Indexing 62 4.5 Numbers, Encapsulation and Inheritance 63 4.6 Functions 64 4.7 Syntax for Particular Numbers 65 4.8 Polymorphism 66 4.9 Arrays and Complex References 67 4.10 Representing Complex Byte Arrays 68 5 Interpreting XODL 69 5.1 How Do XODL Interpreters Solve Problems? 70 5.2 A Simple Example 71 5.3 Internal Problems 72 5.4 Availables Revisited 73 5.5 An Example 74 6 REFERENCES 75 7 SECURITY CONSIDERATIONS 76 8 AUTHOR'S ADDRESS 78 1. INTRODUCTION 80 XODL provides a method of representing situations by 81 representing the different ways information can flow or 82 otherwise be structured. For example, one situation type 83 is where a stack data structure exists. Such a situation 84 is characterized in XODL by the way information is 85 structured; for example, in a stack, the first 86 information "in" is the last information to come "out." 87 Of course that simple description is merely suggestive, 88 but much more complex situations can be well described 89 with XODL. 91 XODL can describe things done by programs, but the 92 descriptions in XODL are not programs. That is, they are 93 not a list of steps which must be done to produce 94 results. Rather, an XODL description provides a way of 95 formally communicating specifications of what resources 96 are available and how to use them, or of communicating 97 what resources are desired. 99 XODL interprets the world as if everything in it were 100 pure information. So it may seem at first that only 101 "computer objects" like stacks or user interfaces could 102 be described. However, since physical objects can be 103 simulated, that is, since they can be modeled in terms of 104 information structures, XODL can also describe physical 105 objects such as computers and modems, or even photons and 106 molecules, bank accounts and governments. 108 2. THE XODL SPECIFICATION 110 This section describes the XODL language. First, a 111 brief, informal discussion is given. Next, a formal 112 specification of the syntax and semantics for XODL will 113 be given. Though XODL is presented here as a language, 114 it is just as importantly a data structure. That is, 115 when it is readable by humans it is in the form of a 116 language with a syntax using the ASCII character set, but 117 when it is being used by a computer it is in the form of 118 a data structure. Thus, instead of a syntax 119 specification, a data description would do just as well. 120 It is important to keep this in mind, as references to 121 XODL as a data structure will be made as easily as 122 references to it as a language. 124 After each syntax specification in the formal section, a 125 discussion of the semantics will be given. Some of the 126 semantics will be presented as comments in examples. 127 Parts of this specification were taken from a thesis by 128 Bruce Long for Colorado State University [1]. 130 2.1. Informal Discussion of XODL 132 XODL code consists of a list of statements called a 133 StatementList. Each statement is called a RelationStmt. 134 A RelationStmt either asserts or denies that two or more 135 pieces of information are identical to each other. A 136 single RelationStmt may imply one or thousands of 137 identities or non-identities. If two pieces of 138 information are identical they can be substituted for 139 each other in any other RelationStmt context. Pieces of 140 information can be constants (7638 or "hello") or names 141 of information (). Sometimes groups of 142 information pieces can act as a single piece. In such a 143 case, the pieces or names of pieces are enclosed in 144 braces: {,
, }. A reference to 145 information in the form of a constant, name or group is 146 called an InfoRef. The important parts of XODL are 147 StatementLists, RelationStmts, InfoRefs, names, and 148 constants. 150 Here is a sample StatementList: 152 StatementList Sample1;; 153 ( == ); 154 ( != ); 155 ( == 8476); 156 ( == ~EmpRec:Ed Hoolan, 132 Oak St., age 28); 157 ([(A==B)] == [(C==D)]); 158 ( == {, , }); 159 # MainNet|; //MainNet is a TCP/IP net. 160 EndList 162 2.1.1. Introduction to XODL Names 164 Names in XODL can be used to refer to a huge variety of 165 information pieces and resources: Bytes, bits, records, 166 files, disk drives, disks, computers, users, even such 167 things as sums and integrals. Further, the need arises 168 in XODL for names which refer to other names. The needs 169 of XODL require a powerful naming scheme which is not 170 satisfied by naming schemes such as those for URLs or 171 OLE2 Monikers. For example, in XODL it is necessary to 172 have names embedded in "parent" names, and to have a sort 173 of "wild card" in segments of a name other than the last 174 segment. So, for example, there might be a name which 175 would mean the same as something like 176 "C:G_PATH).txt", where (PRG_Path) is the name 177 of a path, and the segment with the "*" means "everything 178 here". The example pathname just given is NOT in the 179 syntax of XODL; it is merely an example of the problems 180 the naming scheme in XODL attempts to solve. 182 The complete syntax of XODL names will be given later. 183 However, a brief primer will be given here. Names in 184 XODL are enclosed in angle brackets, and they consist of 185 segments separated by a slash ('/' or '') or a dot. 186 Whether a dot or slash is used is important. Thus, 187 is different from 188 . The dot separators are generally 189 used to refer to items related to the "slash" names. For 190 example we might have which 191 would not be a file, but probably a number. Names can 192 also be embedded in other names. For example: 193 </BankAccount.Balance>. There is also a 194 method of referring to many items at once (like a complex 195 wild card), and a method of referring to name segments 196 themselves. These will be presented in detail in the 197 formal specification. Lastly, adding a new segment to a 198 name does not mean a folder or directory is being 199 referenced as in common OS's. It MAY mean that, but it 200 does not have to. Thus, may not be related in any 201 way to (though it probably is). 203 2.2. The Formal Specification 205 2.2.1. Notational Conventions 207 The following (modified Back-Naur) notation will be used 208 to specify syntax: 210 (1) Terminal symbols are enclosed in double quotes. 211 (2) Non-terminal symbols are alphanumeric or '_'. 212 (3) Alternative items are separated by '|'. 213 (4) Items are grouped by enclosing them in parentheses. 214 (5) Items followed by '!' are optional. 215 (6) Items followed by '*' can occur zero or more times. 216 (7) Some items will be explained in English. 217 (8) Comments are between "//" and the end of the line. 218 (9) Whitespace is only a separator. 219 (10) Case is unimportant. 220 (11) Parameters to an item are in parentheses. 221 (See the definition of NameOf.) 223 2.2.2. StatementLists 225 ************************* 227 GENERAL NOTES: The start symbol is StatementList. When a 228 StatementList is being read, whitespace is ignored. Also 229 comments can be added to any line by using a double 230 slash. Comments extend to the end of the line the 231 comment is on. 233 StatementList: 234 "StatementList" 235 DatabaseID ! ";" 236 UsesClause ! ";" 237 ( RelationStmt ";") * 238 ( "ShortCuts:" (RelationStmt ";")* )! 239 "EndList" 241 DataBaseID: 242 The DatabaseID is used to identify the statements to 243 follow. It is not yet formally defined; however, it 244 will have at least a name, a version identifier, and 245 a date. In this way, new versions and extended 246 versions can be identified. The DatabaseID is used 247 in conjunction with the UsesClause. 249 UsesClause: 250 The UsesClause, also not yet formally defined, 251 identifies other StatementLists which will be 252 referred to in the current one. Thus, a 253 StatementList about a certain protocol might have the 254 UsesClause "Uses TCPIP" where "TCPIP" is the 255 DatabaseID of another StatementList. 257 ************************* 259 SEMANTICS: The tokens "StatementList" and "EndList" 260 identify the start and end of a StatementList. 262 The RelationStmts before the optional token "Shortcuts" 263 are the main statements. Those after it are called 264 "shortcuts." Shortcuts are statements that hold if the 265 statements above them hold; the shortcuts could be 266 inferred from the regular statements. They are analogous 267 to theorems in mathematics. The shortcuts are used to 268 decrease the amount of time it takes to find a solution 269 to an information structure problem. 271 2.2.3. RelationStmts 273 ************************* 275 RelationStmt: 276 "(" InfoRef "==" InfoRef ( "==" InfoRef)* ")" 277 | "(" MajorTermList "!=" MinorTermList ")" 278 | "{" (RelationStmt ";")* "}" 279 | "#" NamePart ("," InfoRef)* "|" RelationStmt 280 | NameOf(RelationStmt) 282 MajorTermList, MinorTermList: 283 InfoRef ("," InfoRef)* 285 ************************* 287 SEMANTICS: RelationStmts can assert either that some 288 InfoRefs are identical, or not identical to each other. 289 More will be said about what that means later. The first 290 form of RelationStmt asserts that two or more InfoRefs 291 are identical to each other. That is, they can be 292 substituted for each other. The second form asserts that 293 two or more InfoRefs are not identical to each other 294 according to the following rule: Each InfoRef in the 295 MajorTermList is asserted to be not identical to 1) every 296 other MajorTerm, and 2) to every MinorTerm. MinorTerms 297 may or may not be identical or not identical to each 298 other. The third form of RelationStmt allows a group of 299 RelationStmts to be asserted as if they were a single 300 RelationStmt. Each RelationStmt in the curly braces ends 301 with a semicolon. While the semicolon is not necessary 302 in the syntax (the end of RelationStmts can be determined 303 without it), I have found that it is a useful visual aid 304 in seeing the end of a RelationStmt. 306 In addition to the RelationStmts explicitly asserted, it 307 is assumed that InfoRefs in different StatementLists are 308 not identical to each other, unless it is explicitly 309 stated that they are. 311 The fourth type of RelationStmt will be explained later, 312 after InfoRefs and Names have been explained. It allows 313 for the easy application of universals. That is, it 314 allows types to be instantiated. 316 Lastly, as with any type of information, a RelationStmt 317 can be given a name, and that name can then be used in 318 any context in which the actual RelationStmt can be. 320 It will be important to explain exactly what is meant by 321 identity and non-identity. But this is better done after 322 more of the formal aspects are taken care of. Following 323 is an example of the RelationStmts just described. It is 324 a valid StatementList. 326 Notice that the following example is in XODL, not in the 327 syntax language. That means the quotes have a different 328 meaning which will be explained shortly. 330 StatementList Example: 332 StatementList Example1; ; // No UsesClause is needed. 333 (1, 2, 3 != 4); // These pieces of information 334 // are not identical to each other. 335 (1 == "one" == "I"); // These are identical. 336 (2 == "two" == "II" == "**"); 337 (4 == "IV"); 338 ("IV" != 3); // "IV" is not the same information 339 // as 3. 340 { 341 ( != ); 342 ( == ); 343 }; // These two RelationStmts act as one complex one. 345 EndList 347 2.2.4. InfoRefs 349 ************************* 351 InfoRef: 352 ConstantInfo 353 | "{" InfoRef ("," InfoRef)* "}" 354 | NameOf(InfoRef) 356 SimpleInfoRef: 357 ConstantInfo 358 | NameOf(SimpleInfoRef) 360 ************************* 362 ConstantInfo is defined formally below. ConstantInfo is 363 what all InfoRefs eventually terminate in. Or at least 364 it is what they ideally terminate in; information may not 365 be available. For example, I can refer to the reader's 366 shoe size, but I may not be able to access that 367 information. ConstantInfo is actual information. For 368 example: "Hello", or 1273. 370 If an InfoRef is not ConstantInfo, it might be the name 371 of such information. E.g., . But notice 372 that an InfoRef can be the name of any InfoRef type. 373 This means that an InfoRef might be the name of a name of 374 a name of some ConstantInfo. 376 Alternatively, there is the notation { a, b, c }. This 377 is a very important feature of the notation. What it 378 means is that all the InfoRefs in the curly braces are to 379 be considered together to count as one single piece of 380 information. Some examples will be given after the 381 definition of ConstantInfo. 383 Note: The following definitions contain some English. 385 ************************* 386 ConstantInfo: 387 "'" (Single Quote Delimited Information) "'" 388 | """ (Double Quote Delimited Information) """ 389 | "~" Number ":" (Length Delimited Information) 390 | "~" TypeID ":" (Type Delimited Information) 391 | (Default Delimited Information) 392 | (Token Delimited Information) 394 Number: 395 A string of numeric digits terminated by a nondigit. 397 TypeID: Token 399 Token: 400 A case insensitive string of alphanumeric or "_" 401 characters terminated by a non-alphanumeric-"_" 402 character. 404 ************************* 406 SEMANTICS: ConstantInfo is actual information. Many of 407 the examples of InfoRefs given so far have been 408 ConstantInfo. 410 Examples of each one in the order they were listed: 411 'Hello There!' 412 "1256" 413 ~5:abcde 414 ~AddressRec:1336 Chambers St., Boulder, CO 80303 415 [34,65, (2+3)] 416 Bruce 418 There are so many different ways of giving ConstantInfo 419 because there are many different needs. Semantically, 420 they are all equivalent. (In fact, once the algorithm I 421 have written loads them from a file, it does not even use 422 the information about which type was given.) But there 423 are pros and cons to each one. Single quoted information 424 is read until another single quote is found. So if a 425 word in the quotes contains an apostrophe, a problem will 426 occur. For example, 'Bob, don't do that' will be read as 427 'Bob, don'. Double quotes have a similar problem, but 428 for information which includes double quotes. An 429 alternative for information which may contain both types 430 of quote is to use tacit length delimited information. A 431 "~" marks that either tacit length delimited information 432 or type delimited information follows. If a number comes 433 next, then that number is interpreted as the number of 434 characters to read as ConstantInfo. Otherwise, a TypeID 435 will tell what type of information follows. The type 436 must have been defined via the language, with a TypeID 437 telling the name of a RelationStmt that defines it. 439 Often, the program will know ahead of time what type of 440 information is being given as ConstantInfo due to a 441 default type that has been defined. As long as whoever 442 defined the type took care to ensure that the end of the 443 information stream can be formally identified by the 444 system, this information can be given without any 445 delimiting symbols at all. If such care has not been 446 taken, the system may think that characters following the 447 ConstantInfo are part of it. 449 Token delimited information is where a single token is 450 held to be the information in question. This is handy 451 for simple items such as names or numbers. Thus, "Hello" 452 and Hello (without the quotes) will be semantically 453 equivalent as an InfoRef. Note that since tokens are 454 terminated by certain characters, "Hello There" and Hello 455 There (no quotes) are not equivalent. The second one 456 would be read as "Hello", and the "There" would be a 457 syntax error. 459 A note about tacit length delimited information: anywhere 460 else in the notation, numbers can be used only after they 461 have been defined, that is, when a StatementList is 462 written which defines numbers and is included in the 463 UsesClause. In the current case, however, the numbers 464 are defined tacitly. This means that expressions and 465 functions cannot be used to specify length. Only a 466 series of digits is allowed, and they will be read as a 467 single base ten number. 469 SPECIAL INFOREF CONSTANT-INFORMATION 471 In actual use of the language, many different types of 472 information will be defined and referred to. There is 473 one special case of information which is recognized 474 without being defined within the language. It is hard 475 wired into the language. The information is named by 476 names of the form: where the 477 %RelationStmt is some RelationStmt. The name refers to 478 "Known" if the RelationStmt is implied by the 479 StatementLists asserted; otherwise, it refers to 480 "NotKnown". Because this will be used so often, and it 481 is hard to read in some cases, the format "[" 482 RelationStmt "]" where the RelationStmt is enclosed in 483 brackets will be recognized as well. 485 EXAMPLES USING INFOREFS 487 // This says: Something, , is divided into two 488 // non-overlapping parts ( and
): 489 { ( == {,
}); 490 ( !=
); }; 492 // Something (A) is divided into two parts (B and C) 493 // which overlap (a union). 494 // The overlapping part is D, while the non overlapping 495 // parts are BO and CO: 496 { ( == {, , }); // A is composed of these 497 // three parts. 498 (, != ); // They are all three 499 // separate parts. 500 ( == {, } ); // B is composed of DO 501 // and D. 502 ( == {, } ); // C is composed of CO // and D. 503 } ; 505 // The amount of cash is $56.23: ( == "$56.23"); 507 // The President is Ed Smith ( == <"Ed Smith"> ); 509 // A three digit number (N) is "123" (said in a hard way) 510 // This does not say that N is a number; that would be more 511 // complex. 512 ( == {, , }); 513 ( == 1); ( == 2); 514 ( == 3); 516 // The information that X is zero is not the information 517 // that X isone: 519 ( [X==zero] != [X==one]); 521 2.2.5. Names 523 In order for this notation to work, the names used in it 524 must meet several requirements. Neither URL's, 525 PathNames, nor ActiveX monikers meet the requirements. 526 Therefore, the naming system used in this notation is 527 somewhat different. However, the notation could be used 528 to define the syntax and semantics of other types of 529 names, and then they could be used in XODL. They could 530 be made to fit the syntax defined here by looking like 531 this: 532 <"http://www.bob.com/index.html">. 534 Following is the syntax for names: 536 ************************* 538 NameOf(TypeID): 539 // The parameter "TypeID" is used to identify what type 540 // will be expected. But it is processed by the 541 // semantic engine, not the syntax checker. So it will 542 // not appear to have any role in defining syntax. 544 "<" NamePart ">" 546 NamePart: 547 NameSegment (( "/" | ".") NameSegment)* 548 | ("^" NameSegment 549 (( "/" | ".") NameSegment)* 550 ( "/" | ".") ":" ) ) 552 NameSegment: 553 ("%"! SimpleInfoRef) | ("@" NameOf(path)) 555 ************************* 557 It is assumed, if a name is used, that it is valid. That 558 is, using a name implies existence. Notice that names 559 are divided into segments similar to DOS or UNIX path 560 names. Notice that the syntax where token delimited 561 ConstantInfo is used as a segment of a name, the colon 562 after "c:" is not allowed. Thus, if we are to use the 563 notation to refer to a drive, we must use a slightly 564 altered form. There are several choices: 565 <"C:/help.txt">, <"C:"/help.txt>, or perhaps 566 . The way drives are described via the 567 notation will determine which of the above will work. 569 Names are the most complex part of the information 570 notation. Names are a single piece of information that 571 is used to refer to another piece of information. 572 However, that single piece might be divided into 573 segments. In fact, a name can be divided into very 574 complex segments. Perhaps the best example of how a name 575 works are the PathNames from the DOS and UNIX operating 576 systems. For example, a filename might be simple: 577 "paper1.doc", or complex: 579 "C:WPmischesis the name. There are several differences between DOS 580 PathNames and the names of the information notation. 581 First of all, where PathNames in DOS refer to a hierarchy 582 of directories and filenames, the names in the 583 information notation refer to a network. For example, in 584 the information notation it is possible that 585 (==). This means more 586 than that the two files contain the same data; it means 587 that they are the same file! Deleting one would delete 588 the other. (Saying that they contain a copy of the same 589 data would be done differently.) Such identities are not 590 possible under the DOS naming system. Another difference 591 has to do with the relationship between segments. In 592 DOS, the relationship between two segments of a name is 593 something like containment. That is to say, for example, 594 that in the name "WPPaper1.doc", "WP" is also a name, 595 and it (WP) contains WPPaper.doc. For example, if we 596 copy WP, we will copy all of the files it contains. In 597 the information notation, the name WPPaper.doc would 598 mean that WPPaper.doc was associated with WP in some 599 way, but not necessarily contained in it. Consider this 600 example: Bruce/L_arm might refer to Bruce's left arm, and 601 Bruce/head to Bruce's head. And when we say "Bruce went 602 to the store" in the language, we will mean that Bruce's 603 head and arms went along also. But consider 604 Bruce/BankAccount. Here, Bruce/BankAccount is associated 605 with Bruce, but when Bruce moves, it does not mean that 606 his bank account goes with him. That is to say that 607 Bruce's head and arms are identical to Bruce in some 608 structured way. But ( != ). 610 Let us look closer at the structure of names. First, 611 they are enclosed in the symbols "< >". This enclosure 612 is to distinguish names which are embedded in other 613 names. For example, consider the difference between 614 and >. The 615 first name refers (presumably) to my right arm. But the 616 second one refers to my right arm only if 617 (==RightArm). 619 NAME-PARTS 621 Inside the "< >" symbols, lies a structure called a 622 NamePart. There are two types of NamePart. The second 623 is syntactically like the first, but with a "^" before 624 it, and where the last NameSegment is a ":". The syntax 625 for the first type of NamePart consists of one or more 626 NameSegments separated by either a slash ("/") or a 627 period ("."). Though the formal syntax diagram suggests 628 a forward slash, the program will respond to either a 629 forward or backward slash. This provides for names which 630 are similar to DOS path names. Some sample names are 631 , and . Notice that either a 632 slash or a dot can be used to separate name segments. 633 Segments separated with a slash may refer to different 634 information than a name with the same segments separated 635 with a dot. For example, is not the same name as 636 . This difference will be useful for keeping names 637 organized. For example, we might define that two "slash" 638 segments after "sum" (e.g., ) are 639 numeric segments. But it is useful to define a function 640 (name) which is associated with sum to represent 641 negation. If we called it we would be 642 contradicting the statement that the segment after "sum" 643 is a number. We can call it and avoid the 644 problem. Semantically, names with dots are processed the 645 same way names with slashes are. However, "dot" names 646 are, in this notation, for special cases. 648 NAME-SEGMENTS 650 Each segment in a name is a NameSegment. A NameSegment 651 can either be a SimpleInfoRef optionally prefaced by the 652 "%" symbol, or the NameOf a Path which is indicated by 653 the symbol "@". Let us look at what these symbols mean, 654 and what a Path is. There are three cases. 656 First, a NameSegment might be a SimpleInfoRef without the 657 percent sign in front of it. A SimpleInfoRef is either 658 ConstantInfo (e.g., "DriveC") or the NameOf a 659 SimpleInfoRef (e.g., ). In either case the 660 information given (directly via ConstantInfo or 661 indirectly via name) becomes a segment of the name. 663 A second kind of NameSegment is a SimpleInfoRef preceded 664 by the "%" symbol. E.g., . This 665 is the syntax to specify that a segment is a variable 666 "<%appendages>" in this case is a variable. The possible 667 values that %appendages can have is determined by other 668 RelationStmts. For example we might have: (Recall the 669 special InfoRef "[...]" from the InfoRef section.) 670 (<%appendages> == 671 { [ <%appendages> == LeftArm ], 672 [ <%appendages> == RightArm ], 673 [ <%appendages> == LeftLeg ], 674 [ <%appendages> == RightLeg ] 676 } ); 678 which says (do not worry excessively about this yet) that 679 the information of whether <%appendages> is equal to 680 "LeftArm" together with the information about whether it 681 equals the other appendage labels is the entirety of 682 <%appendages>. In this case, > might 683 refer to all of my appendages. 685 Variables are not the only item that may need to be given 686 a type. NameSegments themselves may need to be typed. 687 Suppose I want to say that certain RelationStmts hold for 688 a NameSegment whenever it is preceded by 689 " == 695 { [<^Bruce/Sister/:> == "Rebecca"] 696 [<^Bruce/Sister/:> == "Valerie"] } ); 698 I could then assert that ( == 699 >) so that would 700 refer to all of my sisters. I could then refer to all of 701 them, or to each one individually: 702 . 704 The last possibility for a NameSegment is given by the 705 example "@DosPath." This feature can be used to help 706 write StatementLists that work in different situations 707 (e.g., on a different computer) where the name space 708 structure is not known. I will use a computer example 709 for simplicity. Suppose that my DOS directory is in 710 C:/OS/DOS. But most people have their DOS directory in 711 C:/DOS. I can refer to their DOS directory by using the 712 NameOf a Path, as in <@/command.com>. Each name 713 space should have a definition such as: 714 ( == ) 715 defined in it. 717 EMBEDDED NAMES 719 Consider the SimpleInfoRefs in a name. So far, most of 720 the SimpleInfoRefs we have seen in a name have been token 721 delimited ConstantInfo. For example in "Bruce/Head" 722 "Bruce" and "Head" are tokens. That is, they are a 723 series of alphanumeric characters or the character "_". 725 But the SimpleInfoRef in a name segment need not be a 726 token, or even ConstantInfo. Further, as was mentioned 727 above, the segments of a name can have types themselves. 728 (To say they have types, is to say that there are 729 RelationStmts that refer to them). Thus, a particular 730 name segment might be a number or a matrix, or vector. 731 For example, might 732 refer to a particular cell in a spreadsheet. The syntax 733 of the segment "[F,42]" will have to be defined with its 734 own set of RelationStmts. 735 Reviewing, another possibility is that rather than having 736 actual information, the name of information is used. 737 Suppose we wish to refer to a cell in the above 738 spreadsheet, but the cell we wish to refer to is the one 739 named in another cell. We could do this (leaving off the 740 full name): <...WorkSheet1/>. This 741 would refer to the cell pointed to in cell [E,10]. 743 VARIABLES 745 Lastly, let us review what the symbol "%" is for. This 746 symbol is perhaps the most powerful of all. It has a job 747 similar to that of the quantifiers of the predicate 748 calculus. It means that the current name segment is a 749 variable. If there are no restrictions on the variable, 750 then it refers to every possible value that the segment 751 can take, rather like "*.*". Thus, we could talk about 752 all the cells in a spreadsheet this way: 753 >; and we should say nothing about the %X. 754 Now suppose we want to refer to only a range of cells, or 755 perhaps every other row, or every checker-board cell, or 756 even cells [A,4], [F,6] and [G,19]. We can define, using 757 RelationStmts which refer to %X, whatever restrictions or 758 patterns we wish. The details of doing this will be 759 touched upon later. We could also make a set of 760 restrictions which would make the variable %X mean 761 "some." Likewise, once numbers are defined, we could use 762 the notation to say "at least 5 cells", "less than ten 763 cells" or even "less than ten, but not exactly 3 cells." 764 And ranges of any complexity can be defined. 766 Lastly, since %X is a variable, we can use it in more 767 than one place. For example, by using it twice, we could 768 say that the information in each cell in row 5 is 769 identical to the information in the corresponding cell of 770 row 8: 771 ( == ). 773 2.2.6 Representing Types 775 Clearly, if a notation describing objects is to be of any 776 real use, it must be able to work with types as well as 777 actual information structures. For example, we would 778 like to be able to define a system type by stating a list 779 of RelationStmts once, and then applying it to different 780 particulars. Further, we would like to be able to adjust 781 certain aspects of our types that may differ from 782 particular to particular. For example, if we define an 783 array type, we would like to then be able to declare 784 arrays of different sizes and types without changing the 785 definition of arrays. 787 Recall that in the discussion of the semantics for 788 RelationStmts, we skipped the description of the 789 RelationStmts with the form: "#" NamePart ("," InfoRef)* 790 "|" RelationStmt. Let us consider it now, as it provides 791 us with a way to instantiate types. 793 It was mentioned that the type of an information 794 structure is given by the structure of the RelationStmts 795 that refer to it or its parts. Thus, if we wish for two 796 structures to be of the same type, we merely assert an 797 isomorphic set of RelationStmts of each one. That is, 798 the RelationStmts asserted of one should be isomorphic to 799 those asserted of the other. For example, if is 800 asserted to be composed of two nonoverlapping sub-parts, 801 then to make be of the same type, we should assert 802 the same things of it as follows: 804 {( == {, }); ( != )};// describe A. 805 {( == {, }); ( != )};// describe B. 807 Here, and have isomorphic structures, and are, to 808 that extent, of the same type. Notice that there are 809 several problems with this. First of all, we will have 810 to reproduce all the assertions relevant to a certain 811 type for every item we wish to declare. For example, if 812 we wish to assert that is a number, we shall have to 813 assert the relevant RelationStmts of it using entirely 814 unique names (e.g., the subparts of cannot have the 815 same names as the subparts of ). A second problem is 816 that the above solution does not allow for flexible 817 recursive structures. Each level of the structure would 818 have to be defined separately, and thus the number of 819 levels would be fixed and finite. 821 A third problem, which is even more problematic, is that, 822 when there is an isomorphism between items of equivalent 823 structures, the mapping of the isomorphism is not 824 represented. For example, with and above, does 825 the part of correspond to of , or to ? 826 In this case there is no way to tell since the order of 827 the terms in curly braces is not significant. What we 828 need is a method of generating unique names for each new 829 particular's "relateends", while preserving the 830 information about the isomorphism between them. 832 A handy way of generating unique names associated with a 833 certain named particular system is to add a segment to 834 the name of the particular in question. So, rather than 835 using the names and for the parts of , we 836 could use , and respectively. Doing likewise 837 for we have the new assertions: 839 { ( == { , }); ( != ); }; 840 { ( == { , }); ( != ); }; 842 The "NewLevel" RelationStmts, (as I call them), offer a 843 way to shorten this notation. Notice in the syntax 844 specification, that after the "#" comes a Namepart, 845 followed by a list of InfoRefs, and then a RelationStmt. 846 The semantics are as follows. The RelationStmt part of 847 the NewLevel RelationStmt is asserted in the normal way 848 with the following exceptions. First, any name in the 849 RelationStmt which has the token "parent" as its first 850 segment will have the NamePart of the NewLevel 851 RelationStmt appended where the "parent" is. Second, 852 each of the InfoRefs will be asserted to be identical to 853 a name formed by using the parent NamePart as the first 854 part of the name with a dot segment added to it which 855 identifies which InfoRef it is identical to. The new 856 segment will be "param1" for the first InfoRef 857 (parameter), "param2" for the second one, and so on. An 858 example will clarify this. Consider the following 859 NewLevel RelationStmt: 861 #M, 12, | { (==); 862 (==);}; 864 This RelationStmt generates the following two assertions: 866 ( == == 12); 867 ( == == ); 869 Thus, we can shorten our original assertions of and 870 : 872 #A | { (=={, }); 873 ( != ); }; 875 #B | { (=={, }); 876 ( != ); }; 878 The last problem to solve is the redundant entering of 879 the RelationStmts involving and . Recall that the 880 NameOf a RelationStmt can always be used in any 881 RelationStmt context. Thus, suppose is the 882 name of the above RelationStmt. We could save producing 883 the relevant RelationStmt multiple times by using its 884 name. Here is the relevant code: Notice how 885 becomes defined. 886 { 887 ( == 888 " { (=={, }), 889 ( != ) } "); 890 #A / ; // A has two nonoverlapping parts: 891 // and . 892 #B / ; // B has two nonoverlapping parts: 893 // and . 894 } 896 Suppose we wish to define a ball whose size and color are 897 parameters for the type. Skipping much of the detail 898 such as defining numbers-as-sizes, colors and balls, and 899 supposing that the names , and are 900 referenced in the RelationStmt named by , the 901 outcome might look like this: 902 { 903 #MyBall | ; 904 ( == 45); 905 ( == red); 906 } 908 This too can be further reduced by using the list of 909 InfoRefs after the first NamePart. As was explained, 910 these are tacitly assigned names where the first segment 911 is the NamePart, and the second is the dot separated 912 segment , , and so on for each InfoRef 913 included. Thus, we can shorten the above RelationStmt 914 to: 916 #MyBall, red, 45 | ; 917 as long as the necessary changes are made to 918 (i.e., add (==), and so on). 919 In this example, ( == red) and 920 ( == 45). 922 3. Availables: Names of Available Information 924 Many times, it is important for the system utilizing XODL 925 to have access to the information referred to by it. For 926 example, if a piece of information is asserted to be an 927 array with an index ranging from 0 to 10, the "0" and 928 "10" will be needed in the process of marshaling the 929 array. In other words, while the system does not, 930 itself, need to reference the array, it does need to 931 reference the information telling about the array, if it 932 is to successfully marshal the array (or otherwise 933 process it). In this case, the XODL ConstantInfos needed 934 to be referenced. 936 There are also cases where the information being 937 marshaled needs to be referenced. For example, in a 938 graphics file, the width and height of the graphic need 939 to be ascertained if the graphic is to be marshaled to a 940 screen or printer. The width and height are often stored 941 in the graphics file itself, and thus, the file would 942 need to be accessed if its content is to be marshaled (or 943 otherwise utilized) via XODL. 945 This type of referencing is done by the use of special 946 names called "availables" which must be hard-wired into 947 an XODL interpreter. Availables are similar to pointers 948 to arrays of bytes. The following rules describe 949 availables. 951 1) They begin with the segment "avail". E.g. 952 . No other name should be allowed to 953 start with "avail". 955 2) The allowable values for the second segment are 956 determined by the implementation of XODL. They may 957 refer to memory locations, or perhaps to the results 958 of operating system calls, or something equally 959 useful. 961 3) One of the values for the second segment is 962 "const". The names beginning are the 963 names of ConstantInfos in the StatementLists 964 currently being used by the interpreter. The names 965 of ConstantInfos are used to give types to the 966 ConstantInfos. The actual names of particular 967 ConstantInfos can be determined as follows: after the 968 "const" segment, comes the name of the StatementList 969 in which it occurs. The next segment is a number 970 which is determined by the order the ConstantInfos 971 occur in the StatementList - the first ConstantInfo 972 is "1", the second "2", and so on. Thus, the name of 973 the first ConstantInfo in a StatementList named (say) 974 "FTP_protocol" would be: 976 . 978 4) Availables all have two special segments: .data, 979 and .length. the .data segment is a tag for the byte 980 array containing the named information. And the 981 .length segment names an integer which is the length 982 of the data array. Thus, the above ConstantInfo name 983 has the following names associated with it: 985 986 988 Suppose that (<.../1.length> == 2). In other words, 989 the length of the .data array is two bytes. Then the 990 following names are valid: 992 993 995 They refer to the 0th byte and the first byte of the 996 data array. 998 Lastly, each byte is associated with names of each of 999 its bits numbered from 0 to 7. Thus we have names 1000 such as: 1002 1003 1005 which refer to the 2nd bit of byte 0, and the 7th bit 1006 of byte 1 respectively. The bits are either 1 or 0. 1008 Reviewing, the availables are used as an interface to any 1009 real world information including ConstantInfos. They 1010 also may include implementation dependent items such as 1011 memory contents or the results of operating system calls. 1012 Each available has, at least, a byte array and a length 1013 of the byte array. The structure of the byte array must 1014 be specified with other XODL statements. 1016 3.1. Typing ConstantInfos 1018 Consider a RelationStmt with ConstantInfo in it: 1019 (==453). Suppose that it is given elsewhere that 1020 is a number; it can then be concluded (by substitution of 1021 identicals) that the ConstantInfo 453 is a number. But 1022 how do the values of the ConstantInfo represent a number? 1023 How can the type of the ConstantInfos be specified? That 1024 is, how can the structure of the .byte array comprising a 1025 ConstantInfo be asserted? Again, how can ConstantInfos 1026 appear in RelationStmts? There are three different ways 1027 that ConstantInfo can be typed. All three methods have 1028 been alluded to earlier in this document. They are: 1030 1) ConstantInfos can be referred to using the naming 1031 scheme of section 3. Not only can the entire 1032 ConstantInfo be referred to this way, but its byte array 1033 and the length of the byte array can be referred to. 1034 Such ConstantInfos can be referred to individually to 1035 specify the type of a particular ConstantInfo. Referring 1036 to ConstantInfos individually in this way is not usually 1037 desirable because the name of the ConstantInfo depends 1038 upon its location in its StatementList. Any changes made 1039 to the StatementList may change the name of its 1040 ConstantInfos. A better method is to use a variable to 1041 refer to all the ConstantInfos in a StatementList, and 1042 assert that [the information that a ConstantInfo is a 1043 number (for example)], is identical to [the information 1044 that it is related to the byte array in a certain way]. 1045 An example of this procedure will be given in the 1046 examples of section 4. 1048 2) Recall from the syntax description of ConstantInfos 1049 that one of their forms is "~TypeID: Information". Every 1050 ConstantInfo of this form causes a statement of the form 1051 "# | " to be asserted. 1052 Thus, suppose a type <3DigitNumber> was defined (as it is 1053 in the examples) which specified a number in terms of a 1054 byte array. The ConstantInfo "~3DigitNumber:453" would 1055 tacitly assert that this case of "453" was a 1056 3DigitNumber. 1058 3) In Names, each segment can be referred to by the 1059 notation <^.../:> of section 2.2.5. If a segment is a 1060 ConstantInfo, then this segment-name notation can be used 1061 to give a type to the ConstantInfo. 1063 It should be noted that for ConstantInfos where the 1064 length of the byte array can be ascertained by the 1065 interpreter (e.g., where quotes around the information 1066 delimit it), the length will be ascertained 1067 automatically. However, with TypeDelimitedInfo the 1068 length must be asserted (perhaps calculated) in the 1069 associated . The length will then be used to 1070 determine how many bytes should be read in by the syntax 1071 checker. 1073 Each of these techniques will be illustrated in the 1074 examples of the next section. 1076 4. Examples 1078 There are both explicit and implicit reasons for the 1079 examples below. Explicitly, each example illustrates how 1080 to represent a data type using XODL. Implicitly, some 1081 examples will utilize techniques that illustrate such 1082 features of XODL as polymorphism, inheritance, and so on. 1084 These examples are intended only to show how XODL can be 1085 used to represent complex objects and data structures. 1086 They are not intended to describe a standard definition 1087 of such items as numbers or arrays. Nothing in the 1088 following examples should be interpreted as a description 1089 of a standard. 1091 4.1. Enumerations 1093 Suppose we wish to state that a piece of information 1094 represents a day of the week. We could assert it 1095 with XODL like this: 1097 ( == 1098 { [==Sunday], 1099 [==Monday], 1100 [==Tuesday], 1101 [==Wednesday], 1102 [==Thursday], 1103 [==Friday], 1104 [==Saturday] } ); 1106 In English this would read "the information is 1107 identical to the group of information pieces which answer 1108 the following questions: { Is Sunday?, Is 1109 Monday?, Is Tuesday?, ... }" In other words, if you 1110 can answer the questions on the right, you know the 1111 information on the left, and vice versa. 1113 There is one peculiarity here. The above RelationStmt 1114 does not assert that cannot take on values other 1115 than the seven given. But if it does take on other 1116 values, those values will be informationally equivalent 1117 to one of the seven. For example, we might assert 1118 without contradiction that: 1119 ([==Thursday] == [==Thur]); 1120 which says "the information that is 'Thursday' is 1121 identical to the information that is 'Thur' ". 1123 Depending on the circumstances, we may also wish to 1124 assert that: 1125 ([==Sunday],[==Monday], [==Tuesday], 1126 [==Wednesday], [==Thursday], 1127 [==Friday] != [==Saturday] ); 1128 which means that none of the above pieces of information 1129 are identical to each other. E.g., the information that 1130 it is Monday is not the same as the information that it 1131 is Tuesday. 1133 4.2. Records and Type-Definitions 1135 Suppose we need to assert that names an 1136 employee's name, age and salary. A simple (but not 1137 flexible) way would be: 1139 ( == { , , } ); 1141 And suppose we have defined types , and 1142 . We could then declare the type of the fields: 1144 #name | ; 1145 #age | ; 1146 #salary | ; 1148 Notice that the above declaration does not tell how the 1149 is mapped to a character array. If such a map 1150 is desired, it must be asserted separately. Such 1151 examples will be given later in this section. 1153 We have declared a single record, but suppose we need to 1154 declare a "type" which is a record with name, age, and 1155 salary fields. Section 2.2.6 describes how to represent 1156 types. Here is an example: 1158 // Define a type . 1159 ( == " 1160 { 1161 ( == { , , 1162 } ); 1163 #parent/name | ; 1164 #parent/age | ; 1165 #parent/salary | ; 1166 } " ); 1168 // Emp1 and Emp2 are EmpRecords. 1169 #Emp1 | ; 1170 #Emp2 | ; 1172 The above XODL code generates the following names: 1173 , , , 1174 , , and 1175 and and . 1177 And it asserts that: 1178 ( == {, , 1179 } ); 1180 and similarly for . 1182 Notice that a similar type definition method could have 1183 been applied to enumerations. 1185 4.3. Unions, Multiple-Option Types 1187 Often it is necessary for a type to contain one sub-type 1188 in one situation, but another sub-type in another 1189 situation. XODL can handle such situations in several 1190 ways. One method, traditionally called a "union" is to 1191 map two different names to the same bytes in a byte 1192 array. Consider an example: 1194 Suppose that there is a byte array whose 1195 elements start from zero and are referenced by adding a 1196 segment to the name of the array which is the number of 1197 the byte to be referenced. For example, the name of byte 1198 0 would be , and of byte 1: . 1199 (More will be said of this type of indexing in the next 1200 examples.) 1202 And suppose we wish to have some cases where the first 1203 two bytes form a 16 bit word, and other cases where they 1204 are two bytes. Let us use the names and 1205 and . And suppose that the (formal) description 1206 of words is that they have segments /hi and /lo to refer 1207 to their high and low bytes. We can then map the three 1208 names to our byte array like this: 1210 ( == ); 1211 ( == ); 1213 ( == ); 1214 ( == ); 1216 We have thus established a traditional union. However, 1217 it is often useful for XODL to have a representation of 1218 when one interpretation is valid, and when not i.e., a 1219 multiple-option type. 1221 In a multiple-option type, some piece of information (a 1222 "selector") is used to tell which of the options is the 1223 valid one. The selector may be any named piece of 1224 information. For the example, let us call the selector 1225 . Here is how to make the above union into a 1226 multiple-option type: Suppose that can either 1227 be a 1 or 0. 1229 // is either 1 or 0. 1230 ( == 1231 { [(==1)], 1232 [(==0)] } ); 1234 // The information that is 0 is 1235 // identical to the information that ... 1236 ([(==0)] == 1237 { 1238 [( == )]; 1239 [( == )]; 1240 }); 1242 // and similarly for == 1: 1243 ([(==1)] == 1244 { 1245 [( == )]; 1246 [( == )]; 1247 }); 1249 Multiple-option typing can be used to express the type of 1250 ConstantInfos as was described in section 3.1. In other 1251 contexts, it can specify the type of information in a 1252 network stream or file. For example, using a little 1253 English to shorten the example, ([The information that a 1254 file extension is 'gif'] == { Put here: the assertions 1255 describing a .gif file}). It is also useful in many 1256 other cases, as will be apparent in the following 1257 examples. 1259 4.4. Indexing 1261 In the last example, a byte array was discussed. Recall 1262 that if the name of the array was , then the 1263 names of the elements are , , and 1264 so on. (Arrays need not start with zero.) As it stands, 1265 the indexing segment (the 0 or 1) is not known by XODL to 1266 be a number. For example, it does not know that 0+1=1 or 1267 that 0<1. For all XODL knows, there is an element named 1268 . If indexing is to be useful, there must 1269 be a way of asserting the type of the indexing segment or 1270 segments. This can be done by using the names for 1271 segments described in section 2.2.5. The name of the 1272 above indexing segment would be <^RecByte/:>. So if we 1273 had a description of numbers called , we could 1274 assert " #^RecByte/: | ; " to let the XODL 1275 system know that RecByte is an array. Other statements 1276 could be used to specify the range of valid numbers for 1277 the array. 1279 Of course numbers are not the only type that can be 1280 indexed upon. By using some other type we can create a 1281 map or associative array. Suppose we wish to refer to a 1282 color of a geometric figure that varies according to the 1283 shape of the figure. We shall call the "color function" 1284 . We need to assert that the "%shape" is 1285 either triangle, circle, or square: 1287 (<^color/:> == 1288 { [(<^color/:> == triangle)], 1289 [(<^color/:> == square)], 1290 [(<^color/:> == circle)] } ); 1292 Next, we can define some values: 1294 (==red); 1295 (==blue); 1296 (==blue); 1298 The last three assertions could be made without the first 1299 one, but XODL would not know that triangle, circle, and 1300 square exhausted the possible values for . 1302 For really useful indexing, such as in arrays, we must 1303 have a description of numbers. In the next example, we 1304 develop a type definition for numbers, which can then be 1305 used as a parent type for bytes, words, reals, and so on. 1307 4.5. Numbers, Encapsulation and Inheritance 1309 Consider the traditional mathematical definition of 1310 numbers. The definition relies on a concept called a 1311 "group." A group, in mathematics, is defined as 1312 something with the following properties where G is a set 1313 of symbols, and + or * is an operation on those symbols: 1314 (These should seem familiar from algebra.) 1316 1) G is associative, that is, for any x, y, and z 1317 from G, (x+y)+z = x+(y+z). 1319 2) One of the symbols in G is such that x+I=x. It is 1320 called the Identity Element. 1322 3) Every x in G has an inverse (-x or 1/x) such that 1323 x+(-x)=I. 1325 G is called an "Abelian Group" if G is commutative, that 1326 is (x+y) = (y+x). 1328 Next in the definition, the group concept is used to 1329 define "fields." A field is defined as something meeting 1330 the following four requirements where F is a set of 1331 symbols with operations sum (+) and product (*): 1333 1) F under + is an abelian group with the identity 1334 element "0". 1336 2) The set of symbols F, but without "0" under * is 1337 an abelian group with the identity element "1". 1339 3) For all x, y, and z in F, x*(y+z)=x*y + x*z. 1341 4) 0 != 1. 1343 Lastly, a number is defined as an ordered field. 1344 "Ordered" means that for any two numbers, the symbols '<' 1345 and '>' have their usual meanings of greater than and 1346 less than. 1348 Traditionally, a number is something like "THE number 2." 1349 That is, THE number 2 has identity. Of course, while we 1350 can find instances of the number 2 in the world, we can 1351 not find "THE number two." 2 is called an "abstract 1352 entity." XODL cannot represent abstract entities; it can 1353 only represent information structures. Therefore, any 1354 description of numbers in XODL will have to represent 1355 them in terms of information structures. For the 1356 following example, let us say that individual numbers 1357 have identity. That is, we can refer to this 2 or that 1358 2, but not to "the great number two." This switch will 1359 cause the discussion to focus on the operators (sum and 1360 product) rather than on the sets of symbols F and G. 1362 In the following description of numbers, notice that 1363 groups are defined, then abelian groups are defined by 1364 "inheriting" the properties of groups. Next, sum and 1365 product are declared, then fields are described. The 1366 ordering axioms are given, followed by the declaration of 1367 an ordering function (side), then finally, numbers are 1368 described. 1370 Notice how the features of a group such as its inverse 1371 function are encapsulated with it by appending a new name 1372 segment to the group's name. This type of encapsulation 1373 will work in many cases. For example, if a stack object 1374 is named , then it may have the sub-names 1375 and 1377 StatementList Algebra_Draft; ; 1379 ( == " 1380 { 1381 // The operation is associative. 1382 (> == 1383 /%s3>); 1385 // There is an identity element. 1386 ( == ); 1388 // The identity element is the correct type. 1389 (#parent.ID | ); 1391 // a0 == a (if the ID is 0). 1392 (> == <%s4>); 1394 // e.g.: a + -a == 0 1395 (> == ); 1397 // The next group of RS's tell that the operation is 1398 closed. 1400 // e.g., suppose param2== 1401 ( == ); 1403 // sum & product are numbers. 1404 #parent/%s8/%s9 | ; 1406 // the inverse is a number. 1407 #parent.inverse | ; 1409 // The param to Inverse is a number. 1410 #^parent.inverse/: | ; 1412 // the first operand is a number. 1413 #^parent/: | ; 1415 // the second operand is a number. 1416 #^parent/%sx/: | ; 1417 }"); 1419 ( == " 1420 { 1422 #parent | ; // Abelian groups are groups, 1424 // which are commutative. 1425 ( == ); 1426 }"); 1428 ( == " 1429 { 1430 ([ != zero] == 1431 [== 1432 ]); 1433 #parent.NZProduct,,/; 1434 }"); 1436 // Declare sum and product operators. 1437 #sum, zero, | ; 1438 #product, one, | ; 1440 (== " 1441 { 1442 ( == == ); 1444 // a(b+c) = ab+ac 1445 (> == 1446 />); 1447 ([ == zero] != [ == one]); 1448 }"); 1450 ( == " 1451 { 1452 (== { // trichotomy 1453 [ == '<'], 1454 [ == '>'], 1455 [ == '='], 1456 }); 1457 ([=='<'], [=='>'] != 1458 [ == '=']); 1460 // aa 1461 ([ == '<'] == [ == '>']); 1463 // nothing is less than itself. 1464 ( != '<'); 1466 // transitivity 1467 ({[ == '<'], [ == '<']} 1468 =={[ == '<'], 1469 [ == '<'], 1470 [ == '<']}); 1472 }"); 1474 // Declare there to be an ordering operator "Side." 1475 // Side takes two numbers as parameters and refers to "<", 1476 // ">", or"=". 1477 #Side | ; 1479 (== " 1480 { 1481 // The parent is a field. 1482 #parent | ; 1484 // The next two RelationStmts synchronize the field 1485 // ordering operator "Side" with sum and product. 1486 ([ == <'] == [ / 1487 > == <']); 1488 ({[ == <'], [ == <']} 1489 == {[ == <'], 1490 [ == <'], 1491 [/ 1492 == '<'] }); 1494 }"); 1496 Shortcuts: 1498 // In this section a list of theorems can be given. 1499 // XODL interpreters should use the shortcuts to make 1500 // processing more efficient. 1502 // x*0=0 1503 ( == zero); 1505 EndList 1507 Let us work through this StatementList quickly. First, 1508 notice that is declared to refer to a 1509 RelationStmt which describes mathematical groups. You 1510 can find the various aspects of group operators such as 1511 associativity in this definition. Next, a description of 1512 Abelian groups is given which references , then 1513 adds one more RelationStmt to it (commutativity). The 1514 third description is for a multiplicative Abelian group 1515 operator. This operator either returns zero, or acts as 1516 an Abelian group for non-zero values. 1518 The next two RelationStmts after the definition of 1519 refer to the previous descriptions in 1520 order to declare the existence of sum and products. 1521 Notice that each line tells the name of the operator (sum 1522 or product), the identity element for the operator (zero 1523 or one), and the type of the operands and results. These 1524 names can be used to refer to sums and products. For 1525 example, the sum of X and Y could be referred to thusly: 1526 />. Shortly we shall see how to refer to 1527 actual numbers rather than names of numbers. 1529 Next, sum and product are used to describe fields, and 1530 then an "ordering" operator (Side) is defined which takes 1531 two numbers (or other entity) and refers to either "<", 1532 ">", or "=" depending on whether the first number is less 1533 than, greater than, or equal to the second one. For 1534 example, ( == "<"). Notice that while the 1535 group definition creates new names, the field definition 1536 borrows the names already created to be groups. 1538 Lastly, the field description and the ordering operator 1539 are used to describe numbers. This description can be 1540 used to declare numbers: e.g., #EmployeeAge | 1541 declares to be the name of a 1542 number. 1544 How it Works 1546 The statement #Age | declares that the 1547 RelationStmt in is to be asserted in the 1548 normal way with the exception that "Age" is substituted 1549 in for . Looking at the information 1550 , we see that it contains (among other 1551 things) the statement #parent | . Substituting 1552 "Age" for , we get #Age | , and see that 1553 once again we must dereference a name and substitute 1554 "Age" for . In , we find the assertion 1555 (==) which is asserted as 1556 (==). Now, we must look at the 1557 description of . We find it in the line #sum, 1558 zero, | . Thus, we must 1559 dereference . Doing so, we find that sum 1560 is a , and that ( == 1561 ). This means that wherever we find a sum 1562 operation, we can switch the operands without affecting 1563 the reference of the name. By continuing the process we 1564 have been engaged in, we can determine all the valid 1565 substitutions which can be made, and thus, which 1566 inferences are valid in the logic. 1568 4.6. Functions 1570 Obviously, it is important to be able to represent 1571 functions. In XODL, complex names take the place of 1572 functions. The arguments to the function are segments of 1573 the names. 1575 Notice how we refer to sum to define subtraction, and 1576 product for square roots. We will not trace through this 1577 code, merely present it. These RelationStmts should be 1578 placed into Algebra-Draft. Let us use the abbreviation 1579 of "difference" "Diff" to mark subtraction, and Sqr and 1580 Sqrt for square and square root. 1582 { 1583 // A difference is a rearrangement of a sum operation. 1584 (<%op1> == ); 1585 ( == <%op3>); 1587 // A square of a number is the number times itself. 1588 ( == ); 1589 // A square root is a rearrangement of a square oper. 1590 (<%s2> == ) 1591 ( == <%s3>) 1592 } 1594 Given the above RelationStmts, we can now refer to such 1595 information items as or which have 1596 the meanings Square root of 9, and 5-3. There is reason 1597 to believe that XODL can represent the semantics of any 1598 finitely specifiable function. 1600 4.7. Syntax for Particular Numbers 1602 The above descriptions allow us to talk about numbers. 1603 For example, we could ask what any number multiplied by 1604 zero was: . By substituting the 1605 identicals defined in the above definition, we could 1606 conclude that the answer was zero. (We would, after many 1607 substitutions, be able to substitute "zero" for 1608 .) However, notice a major deficiency: 1609 there is no easy way to represent any number other than 1610 zero and one. With the notation, we can define 1611 descendants of numbers which use the ASCII character set 1612 to represent other numbers. First let us describe a 1613 single decimal digit . There are two steps in 1614 defining (other than declaring that it is a 1615 number). First, enumerate the possible values a 1616 may take, and second, establish the meanings 1617 of the values. You can see the two steps in the 1618 following RelationStmt, which we shall add to the 1619 definitions of the Algebra_Draft Statement List above. 1621 ( == " 1622 { 1623 // A is a number 1624 #parent | ; 1626 // Specify Possible values: 1627 ( == { [ == 0 ], 1628 [ == 1 ], 1629 [ == 2 ], 1630 [ == 3 ], 1631 [ == 4 ], 1632 [ == 5 ], 1633 [ == 6 ], 1634 [ == 7 ], 1635 [ == 8 ], 1636 [ == 9 ] 1638 } ); 1639 // Semantics of the values: 1640 ( [ == 0] == [ == zero] ); 1641 ( [ == 1] == [ == one] ); 1642 ( [ == 2] == [ == ] ); 1643 ( [ == 3] == [ == ] ); 1644 ( [ == 4] == [ == ] ); 1645 ( [ == 5] == [ == ] ); 1646 ( [ == 6] == [ == ] ); 1647 ( [ == 7] == [ == ] ); 1648 ( [ == 8] == [ == ] ); 1649 ( [ == 9] == [ == ] ); 1650 }"); 1652 TYPING CONSTANT-INFOS 1654 Now that a single digit number is defined, we would like 1655 to be able to use it in names and other InfoRefs as a 1656 ConstantInfo. For example, we might like to use (as has 1657 been done earlier without explanation) to mean 1658 the square root of 9. But how does XODL know that the 1659 second segment of the name is a ? 1660 Recall from section 3.1 that every ConstantInfo has a 1661 name, and is associated with a byte array (the data 1662 field) and a length field. There are two things that 1663 need to be done. First, criteria must be asserted 1664 whereby XODL can infer that a particular ConstantInfo is 1665 a (or whatever). And second, assert that if a 1666 ConstantInfo is a then it is identical to its 1667 data field's byte 0. 1669 Suppose we are creating a statement list named "Stmts" in 1670 which we use s. We can fulfill the first 1671 requirement (that the type of ConstantInfos be 1672 ascertainable by XODL when necessary) by asserting that 1673 {the information that a ConstantInfo is a 1674 and that its length field = 1} is identical to the 1675 information that it is a : 1677 ([{#avail/const/Stmts/%ConstInfo1|; 1678 (==1>)] == 1679 [#avail/const/Stmts/%ConstInfo1|]); 1681 It may seem circular that we use a "1" in asserting that 1682 a ConstantInfo is a . But in this case, XODL 1683 needs only to check for equality, not do an arithmetic 1684 operation. Thus, it can tell that the length is 1 1685 without having to look up what the 1 means. 1687 Next, we must assert that any ConstantInfos in Stmts that 1688 are are identical to their byte 0: 1690 ([#avail/const/Stmts/%ConstInfo2|] == 1691 {[#avail/const/Stmts/%ConstInfo2|]; 1692 ( == 1693 )} ); 1695 Notice that the condition that a ConstantInfo is a 1696 is on both sides of the (main) identity 1697 symbol. This is because if it were not on the right 1698 side, then the information that the ConstantInfo was 1699 identical to its 0 byte would be identical to the 1700 information that it is a . But there may be 1701 other cases where a ConstantInfo is identical to its 0 1702 byte, but where it is not a . In other words, 1703 we do not want to use a "biconditional" here, and 1704 repeating the "antecedent" on the right side of the 1705 identity statement removes the biconditionality. 1707 3 DIGIT NUMBERS 1709 Now the description of a can be used to 1710 describe a three digit number. Notice how we can use 1711 single digit numbers now as a type of InfoRef. Also, 1712 notice that if we want to refer to 10, we must use 1713 since 10 is a two digit number, which has not 1714 been defined. 1716 (<3DigitNum> == " 1717 { 1718 ( == {, , } ); 1719 # digit1 | ; 1720 # digit2 | ; 1721 # digit3 | ; 1723 // == ((( D3 * 10) + D2) * 10) + D1 1724 ( == 1725 / 1726 / / >> 1727 / >); 1728 } " ); 1730 In order to map a <3DigitNum> to a byte array, we merely 1731 assert that is byte 0, is byte 1, and 1732 is byte 2. Notice that in a <3DigitNum>, we 1733 must fill empty digits with '0'. E.g., a nine would be 1734 "009", not "9". 1736 If we wanted to, we could continue the refinements we 1737 have been making to define more syntaxes such as numbers 1738 with an arbitrary number of digits, decimal numbers, and 1739 so on. We could also use the bit fields in ConstantInfo 1740 names to define integers of different sizes, 1741 floating-point numbers and so on. In fact, we could 1742 create a syntax for complex expressions which result in a 1743 number. These expressions might include functions, and 1744 even such numbers as pi. Let us quickly consider this so 1745 that we may use such a notation without using space here 1746 to define it. 1748 EXTENDED NUMBER SYNTAX 1750 While we could use a very simple syntax for InfoRefs 1751 which are to be interpreted as numbers (such as 1752 <3DigitNum>), complex expressions will be very cluttered 1753 looking and hard to comprehend. Therefore, let us assume 1754 for the rest of this document that a syntax for numeric 1755 InfoRefs called has been defined in some 1756 RelationStmt such that we can use the symbols +, -, *, 1757 and /. Of course if we use the slash, we will sometimes 1758 have to enclose the expression in quotes to avoid its 1759 being mistaken for a name segment separator. Let us also 1760 assume that the extended syntax can handle parentheses 1761 (which will allow us to use "/" for division without 1762 quotes if it is used inside parentheses), and a function 1763 notation including the function sqrt() for square roots. 1764 Thus, from here on, an example of a valid InfoRef in a 1765 numeric context is: (-2.56 + ) * sqrt(81) - 3. When 1766 the "-" sign is used in a unary position, it will signal 1767 that is being applied (i.e., for negative 1768 numbers). 1770 The idea of defining new syntaxes and semantics via 1771 RelationStmts is partly to distance ourselves from the 1772 "<.../<...>>" type of syntax which is powerful, but ugly. 1774 4.8. Polymorphism 1776 Polymorphism is the ability of a language to use the same 1777 name for similar functions on different types of object. 1778 Consider that the name as it was defined 1779 above takes two s as arguments and produces a 1780 in return. 1782 Suppose we wish to have a sum which added two vectors 1783 rather than two numbers. I will only discuss doing so 1784 here, not actually do it. If the programmer were clever 1785 enough, she could actually define once, and 1786 have it apply to any system where a non-multiplicative 1787 group operation was involved. That is, it could 1788 automatically apply to numbers, vectors, matrices, and 1789 any other situation where the concept of a sum applies. 1790 The types of the argument segments and of the named item 1791 (the result) would have to be determined by statements 1792 asserting that if the arguments are of a certain type, 1793 then the result is of a certain type. Unfortunately, 1794 this means a lot more work will have to be done by the 1795 XODL interpreter. It may be better to name each 1796 different kind of sum a different name. For example, 1797 have for numeric sums, but have 1798 for vector sums. The work on 1799 the interpreter would be significantly decreased. 1801 4.9. Arrays and Complex References 1803 With a description of numbers along with a syntax and 1804 semantics for their representation, we can now use the 1805 language to make references that were not available 1806 before. For example, suppose we wish to assert that 1807 there are 100 computers (or vectors, physical objects, 1808 integers, or files etc.). We can use a numeric variable 1809 which is limited to numbers from 1 to 100: 1810 { 1811 // There are some computers. 1812 #Computers/%x | ; 1814 // The "%x" is a 3 digit number (recall the definition). 1815 #^Computers/: | <3DigitNum>; 1817 // %x is not greater than 100 or less than 1. 1818 ( != ">"); 1819 ( != "<"); 1820 } 1822 With this definition, we can refer to such things as the 1823 fifth computer: . Since such arrays are 1824 used often, it is handy to generalize the concept of 1825 arrays as follows: 1827 ( == " { 1828 // There are some items of type param1 1829 #parent/%x | ; 1831 // The "%x" is an integer. 1833 #^parent/: | ; 1835 // %x is not greater than param3 or less than param2. 1836 ( != ">"); 1837 ( != "<"); 1838 }"); 1840 With this definition of , we can declare 1841 arrays easily: 1843 // People is an array of 50 s: 1844 # People, , 1, 50 | ; 1846 Or suppose we assert that there are 100 vectors; we can 1847 say (for example) that the 10th through 30th vectors have 1848 a zero x component: 1850 { 1851 // There are 100 vectors: 1852 #Vectors, <3VectorType>, 1, 100 | ; 1854 // Some vectors' x components are zero. 1855 ( == zero); 1857 // these vectors are those referenced by numbers <= 30, 1858 ( != ">"); 1860 // and >= 10. 1861 ( != "<"); 1862 } 1864 Consider several more examples: 1866 //At least five of the above declared vectors 1867 //(call them XVec) have an x component of (say) 3: 1868 { 1869 #Xvec/%v2 | <3VectorType>;// There are some vectors, 1870 (^Xvec / : | <3DigitNum>; // which are referenced by a 1871 // three digit integer, 1872 ( != "<"); // whose maximum permissible 1873 // value is at least 5. 1874 ( == 3); // And these vectors have an x 1875 // component of 3. 1877 // None of them are the same vector. 1878 ([<%v4> != <%v5>] == [ != ]); 1880 // They are identical to some vectors in . 1882 ( == >); 1883 } 1885 Another Example: 1886 // If a has /x == 3, then its y component == 1887 // twice its z component 1889 { 1890 ([ == 3] == {[ == 1891 ( * 2)], [ == 3] }); 1892 } 1894 In English, the above RelationStmt reads "The information 1895 that a is 3 is identical to the information 1896 that its y component is twice its z component and that it 1897 its x component is 3." The bit about the x component 1898 being 3 needs to be repeated on the right side to avoid a 1899 "biconditional" effect where a y's being 2*z implies 1900 that x==3. 1902 4.10. Representing Complex Byte Arrays 1904 In many if not most cases, the system being represented 1905 is an array of bytes with some complex structure. The 1906 array could be a file, a computer's memory, a disk 1907 surface, or a stream from a network. Consider how a 1908 might be described and mapped to a byte array 1909 (let's call it a . Suppose that we have 1910 defined integer to have /hi and /lo fields as was 1911 illustrated in section 4.3. Also, let us suppose we have 1912 defined to describe an integer (/length) and a 1913 byte array (/data) mapped to a byte array in the usual 1914 way. 1916 ( == " 1917 ( == 32); // max length of user name. 1918 ( == 65535);// max length of a file. 1919 ( == 255); // max length of file name. 1921 // declare types on all names. 1922 #parent/FileOwner | ; 1923 #parent/FileName | ; 1924 #parent/FileData | ; 1925 #parent/FileInt | ; // int rep. of FileType 1927 #parent | ; //the bytes of the file 1929 // Set max length on names. 1931 (/> 1932 != '>'); 1933 (/> 1934 != '>'); 1935 (/> 1936 != '>'); 1938 // Types of files: 1939 ( == 1940 {[ == text ]; 1941 [ == data ]; 1942 [ == exec ]; 1943 [ == gif ]; 1944 } ); 1946 // selects type option for FileData: 1947 // (In an actual implementation, this table would 1948 // probably be centralized, not in .) 1949 ([==text] == 1950 [==0] == 1951 [#parent/FileData|]); 1953 ([==data] == 1954 [==1] == 1955 [#parent/FileData|]); 1957 ([==Exec] == 1958 [==2] == 1959 [#parent/FileData|]); 1961 ([==gif] == 1962 [==3] == 1963 [#parent/FileData|]); 1965 // Now, map each item to the ByteStream passed in. 1966 // (There is an easier way to do this mapping, 1967 // but for the example, I choose the hard way.) 1969 ( == ); 1970 ( == ); 1972 ( == ); 1973 ( == ); 1974 (==); 1976 // record the byte after the filename in NameEnd. 1977 (==+4); 1978 (== 1979 >); 1980 (== 1981 +1)>); 1982 ( == 1983 +2)); 1985 // record the byte after the file owner. 1986 (== 1987 ( + 1988 +2)); 1990 ( == 1991 >); 1992 ( == 1993 +1)>); 1994 ( == 1995 +2)>); 1997 "); 1999 Suppose that a byte stream called "MyFile" is mapped to 2000 an available byte stream. (Recall, available items are 2001 those which are directly accessible to the XODL 2002 interpreter. Then, using the above description of a file 2003 we could assert: 2005 # MyFile | ; 2007 Doing so would provide names of all the parts in MyFile, 2008 along with a way for XODL to access those named pieces of 2009 information via the available MyFile is mapped to. 2011 5. Interpreting XODL 2013 There are many different ways that XODL interpreters may 2014 be implemented, but the basic process must be the same: 2015 substitute identicals and check non-identicals to move 2016 information around. There are two related problems to 2017 solve: The first is, how do we use XODL to represent 2018 problems we wish to have solved. Let us look at this 2019 problem first. 2021 5.1 How do XODL interpreters solve problems? 2023 It may seem that there are many different ways to use 2024 XODL to solve problems. While there are many different 2025 ways to implement XODL interpreters, the different 2026 problems that can be solved with XODL can be generalized 2027 and solved with a single algorithm. Let us consider the 2028 algorithm in term of its inputs (arguments). Let us call 2029 the algorithm task.engage. 2031 The inputs necessary for an XODL interpreter can be 2032 divided into two parts: problem lists, and tacit lists. 2033 Each of these two parts contains three lists, all of 2034 which are XODL StatementLists: Assertions, Capabilities, 2035 and Tasks. Thus, the inputs to task.engage consist of 2036 six lists. Assertions are those statements which 2037 describe the world to the interpreter. They mostly 2038 declare the existence of objects. For example, a 2039 StatementList might use the names of various computers, 2040 network connection, users, programs, and so on. 2042 Capabilities are statements which are not necessarily 2043 true, but which could be made true by the XODL 2044 interpreter if need be. For example, a capability might 2045 be to make certain operating system calls. What those 2046 calls actually do is specified in the assertions. An 2047 example might be of the form ([input to op-sys call] == 2048 432);. Of course that is greatly simplified. 2050 Lastly, besides assertions and capabilities, there are 2051 tasks. A task list is a StatementList which, rather than 2052 describing the way the world IS, or the way the 2053 interpreter COULD make it, describes the way we would 2054 LIKE the world to be. For example, I might like to have 2055 a copy of a certain file or record on my hard drive or in 2056 a certain document. I.e., the information on the drive 2057 == certain other information. Or I might like to have a 2058 system set up whereby I can edit a certain file. 2060 5.2 A Simple Example 2062 Suppose the inputs to task.engage are as follows: 2064 *************** 2065 StatementList // Asserts.smt 2066 (a==b==c); 2067 (B==D); 2068 (X==Y); 2069 EndList 2071 StatementList //Test Capability List 2072 (y==t); 2073 (x==w); 2074 (d==x); 2075 (a==q); 2076 (b==s); 2077 EndList 2079 StatementList // A Task 2080 (A==Y); 2081 EndList 2083 *************** 2085 The interpreter's job is to make sure that the task 2086 (A==Y) becomes the case. First, it (the interpreter) 2087 might look in the assertions to see if (A==Y) is already 2088 the case. It may need to do some substitution of 2089 identicals to do this. For example, it is asserted that 2090 (Y==X); if it is also the case that (X==A) then (A==Y) is 2091 already true and the interpreter need not act at all. 2092 Alas, (A==Y) is not the case according to the above 2093 assertions. The capabilities are items that the 2094 interpreter can MAKE true. In this case, making the 2095 third capability, (d==x), true, will complete the task 2096 since (D==B), and (b==a). In a real case, names might 2097 include URLs, references to the internals of documents, 2098 or to people. And the solution may consist of hundreds 2099 of steps of capabilities to do. 2101 Task.engage has two parts: first, find a suitable 2102 solution, and second, make that solution so. 2104 5.3 Internal problems 2106 Task.engage is not merely the way a user or programmer 2107 interacts with the XODL interpreter. It is a vital part 2108 of how XODL is to BE interpreted. Consider an example. 2109 Suppose a task consists of retrieving a certain piece of 2110 information which is in an array. E.g., . 2111 Now suppose that the index (the 53) was not directly 2112 known, but is stored in a document on the web. The 2113 reference to the information might be something like: 2115 > 2117 The interpreter will have to retrieve the WorkSheet, or 2118 at least the contents of cell [C,32], and this will be a 2119 separate task. Thus, in almost any task, there are 2120 sub-tasks which the interpreter will have to generate for 2121 recursive calls to task.engage. 2123 The problem is that the simple assertions and 2124 capabilities passed in to the top level task.engage may 2125 not cover such things as looking up items on the web, or 2126 parsing spreadsheets. This is the reason for the "tacit" 2127 assertions, capabilities and tasks. Tacit assertions and 2128 capabilities are those items which the interpreter may 2129 use in solving any problem. For example, in the case 2130 where a problem references some information on the 2131 Internet, StatementLists describing TCP/IP, HTTP and so 2132 on may be needed to reference that information. 2134 Tacit tasks are a security measure. The tacit tasks will 2135 often be negative, that is of the form (A!=B). For 2136 example, tacit tasks might be "do not erase the hard 2137 drive", "do not try to guess passwords", "do not try to 2138 thwart system security." Using tacit tasks to increase 2139 security is only a precaution. It should not be the main 2140 method of directing the actions of the interpreter. See 2141 the section on security considerations for more 2142 information. 2144 5.4 Availables revisited 2146 Recall that availables are named items to which the 2147 interpreter has access. The question is, what is the 2148 nature of this access? The answer is, whenever a piece 2149 of information resides in available memory, an implicit 2150 StatementList is being asserted. Suppose that 2151 named an available byte somewhere in system memory. And 2152 suppose that memory cell contained the number 255. Then 2153 the statement(==255) would automatically be 2154 asserted, as well as (==1) and so on for 2155 all eight bits. Thus, if the interpreter needs to access 2156 a piece of information, it can engage a task to move that 2157 information into an available memory location, and then 2158 read it from there. 2160 5.5 An Example 2162 Suppose we wish to have the XODL interpreter design an 2163 AND gate. There are many different ways that AND gates 2164 can be created: out of transistors and resistors, via 2165 software connected to an I/O port, out of NAND or NOR 2166 gates, and so on. We can select which of the possible 2167 solutions XODL will use by limiting the capabilities it 2168 has to work with. Let us look at how XODL might 2169 construct an AND gate out of NOR gates. 2171 The first step is to describe AND and NOR gates. Let us 2172 assume that our gates are ideal in the sense that there 2173 is no time lag between when the signal arrives at the 2174 gate and when the new signal leaves. We can index the 2175 gates over time. That is, we can act as though we have 2176 an array of gates where each one is at a different time. 2177 The reference to the inputs of the gates have the form: 2179 and , and so on for 2180 Input2, and output. 2182 Where %t is the time. Let us consider the three 2183 StatementLists for this problem: Assertions, 2184 Capabilities, and Tasks. 2186 /////////////////////////////// 2188 StatementList And_Nor_Assertions;; 2189 // Type description for a two state system: 2190 ( == 2191 "{( == 2192 { [==0], [==1] }); 2193 ([(==0)] != [(==1)]);}"); 2195 // Describing AND: 2196 ( == "{ 2197 # parent/%t1/Input1|; // input1 is 1 or 0. 2198 # parent/%t2/Input2|; // input2 is 1 or 0. 2199 # parent/%t3/output|; // result is 1 or 0. 2201 // The result is 1 if & only if both inputs are 1. 2202 ([ == 1] == 2203 {[==1], 2204 [==1]}); 2205 }"); 2207 // Describing NOR: 2208 ( == "{ 2209 # parent/%t1/Input1|; // input1 is 1 or 0. 2210 # parent/%t2/Input2|; // input2 is 1 or 0. 2211 # parent/%t3/output|; // result is 1 or 0. 2213 // The result is 1 if & only if both inputs are 0. 2214 ([ == 1] == 2215 {[==0], 2216 [==0]}); 2217 }"); 2218 // There are two inputs In1 and In2 which are either 2219 // 1 or 0 depending on the time. 2220 # In1/%t1 | ; 2221 # In2/%t1 | ; 2222 # Out1/%t1| ; // the output is binary. 2224 // There are three Nor Gates: 2225 // (Recall the Array example.) 2226 #Nor, , 1, 3 | ; 2228 EndList 2230 ///////////////////////////////// 2232 StatementList And_Nor_Capabilities;; 2234 // In1 can attach to any gate input: 2235 (==); 2236 (==); 2238 // In2 can attach to any gate input: 2239 (==); 2240 (==); 2242 // Gate outputs can attach to gate inputs: 2243 (==); 2244 (==); 2246 // Out1 can attach to any gate output: 2247 (==); 2249 EndList 2251 ///////////////////////////////// 2253 StatementList And_Nor_Task;; 2255 // Create a new AND gate, 2256 #NewAnd | ; 2258 // where in1, in2, and out1 are the I/O. 2259 (==); 2260 (==); 2261 (==); 2263 EndList 2265 ///////////////////////////////// 2266 Given the above inputs, an XODL interpreter should 2267 produce a list of statements similar to the following 2268 one: 2270 { 2271 ( == ); 2272 ( == ); 2273 ( == ); 2274 ( == ); 2275 ( == ); 2276 ( == ); 2277 ( == ); 2278 } 2280 It can be shown that the above RelationStmt will produce 2281 an AND gate if it is instantiated. 2283 6. References 2285 [1] Bruce Long, "The Concept of Causality in Ethical 2286 Theories", not published. This paper can be requested 2287 from xbruce@dimensional.com. 2289 7. Security Considerations 2291 XODL interpreters are given a specification of a state of 2292 affairs, and they try to find a sequence of actions which 2293 will bring that state of affairs to be. Different 2294 interpreters, or interpreters with slightly different 2295 StatementList driving them will come up with different 2296 sequences of actions. This means that special care must 2297 be taken to ensure that none of the actions taken are 2298 harmful, illegal, or immoral. For example, if a local 2299 machine did not have enough resources to complete a task, 2300 one solution would be to hack into another computer and 2301 use its resources via a hacked password. 2303 While such scenarios must be watched for, they need not 2304 cause a panic. There are several ways to control the 2305 behavior of XODL interpreters. 2307 1) Do not give it access to certain resources. 2308 2) Do not give it the capability of accessing them. 2309 3) Do not give it the knowledge (StatementLists) of them. 2310 4) Use tacit tasks to forbid certain actions. 2311 5) Program the interpreter to follow a system of values. 2313 The last item may sound hard to do, but I have developed 2314 a theory which will allow a complex value system to be 2315 "digitized." This theory can easily be hardwired into an 2316 XODL interpreter such that any action taken would conform 2317 to the stored value system. Such a system would probably 2318 be quite secure, as the XODL interpreter could be on the 2319 look out for items which would cause problems, and 2320 prevent them; whether they were rogue StatementLists or 2321 other programs. This theory is partly documented in [1]. 2322 More information will be forthcoming, and will be posted 2323 at http://www.dimensional.com/~xbruce/. 2325 8. Author's Address 2327 Bruce Long 2328 1335 Chambers Drive 2329 Boulder, CO 80303 2331 Phone: 303/494-3985 2332 E-mail: xbruce@dimensional.com