------------------------------------------------------------------------------- ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- ------------------- SLIVER_TOP_LEVEL: OBJECTS --------------------------- ------------------------------------------------------------------------------- -- PROBLEMS -- - Terminal: Do I need to specify stuff like change location, set/get name? -- - should all objects and ops be shown on the DFD? ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- define object attribute problem; object Canvas has CanvasElement*; -- Drawing canvas on which objects are drawn. obj CanvasElement has term:Terminal or toporel:TopologicalRelation; object SLIVER components: ExpertUser, LanguageDesigner, VisualProgrammer, SemanticAction, ObjectSet, LanguageSpec, InputSet, RelationalParser, ParseTree; operations: CreateObjectSet, EditObjectSet, CreateLanguageSpec, EditLanguageSpec, CreateInputSet, EditInputSet, ParseInputSet, MonitorParser, ExamineParseTree, ExecuteParseTree; description: -- This describes the SLIVER system in a nut shell. All sliver -- objects and operations should be some refinement of the above. -- -- SUMMARY: In the SLIVER system, an expert user creates an Object Set -- which is used by a Language Designer to create a visual Lanugage Spec -- as well as by the Visual Programmer to create Input Sets to be parsed -- according to the Language Spec. As a Visual Programmer might simply -- execute the resulting parse of the Input Set, the Language Designer -- is able to examine the resulting Parse Trees, while the Expert User -- is able to monitor the functioning of the Parser itself. -- -- NOTE: This may be one more level of abstraction than we need, but -- it helps me think... ; end SLIVER; object ExpertUser components:; description: -- The expert user is interested in research concerning relational -- parsers in general and parsing visual languages in particular. -- Asside from this, the ExpertUser creates the ObjectSet, which -- determines the domain of objects and relationships in which -- the LanguageSpec and associated InputSets are composed of. ; end ExpertUser; object LanguageDesigner components:; description: -- The LanguageDesinger is interested in the design and execution of -- visual languages. In creating a LanguageSpec, the LanguageDesigner -- will provide a formal specification of the visual lanugage in some -- well defined syntax that describes a relational language. -- The LanguageDesigner is then able to examine the ParseTrees that are -- generated as InputSets are parsed according to a LanugageSpec. ; end LanguageDesigner; object VisualProgrammer components:; description: -- The VisualProgrammer is ultimately the "end user" of the system. The -- VisualProgrammer creates an input set in terms of the same ObjectSet -- associated with the visual LanguageSpec in use and then submits that -- set to be parsed. Once parsed, the VisualProgrammer may execute -- a resulting ParseTree, resulting in the execution of the semantic -- actions specified by that tree. ; end VisualProgrammer; ------------------------------------------------------------------------------- --------------- top level object: SemanticAction -------------------------- ------------------------------------------------------------------------------- object SemanticAction components:; description: -- As far as we are concerned, a semantic action is opaque to the -- to SLIVER, but is some kind of general command set that can be -- executed so as to achieve some kind of effect in the outside world: -- e.g. A database action, output to the screen, executable code, etc. -- (even updating the SLIVER Input Set or Parse Tree should not be -- ruled out.) ; end SemanticAction; ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- --------------- top level object: ObjectSet ----------------------------- ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- object ObjectSet components: name:Name, Terminal*, Relation*; operations: CreateObjectSet(n: Name)->(o': ObjectSet), EditObjectSet(o: ObjectSet, d: DefaultObjectSet)->(o': ObjectSet); description: -- The purpose of the ObjectSet is to bind a set of Terminals and -- the valid Relations over those terminals into a single entity: -- -- An Object Set serves as a basis for both 1) the definition of a -- visual language (the Language Spec) which is created by the -- Language Designer as well as for 2) well-formed "sentences" of that -- language which are to be found in the InputSet created by the Visual -- Programmer. -- -- The objects in the Object Set will serve as the "terminal tokens" -- of the visual lanugage. These are the objects that the Visual -- Programmer will manipulate on the screen in order to produce well- -- formed graphic sentances of the visual language. -- -- Also included in the Object Set are a set of predicate-like -- spatial or topological relations which may or may not hold over -- objects in the Object Set. "Inside(x1, x2)", "Above(x1, x2)" or -- "Overlap(x1, x2)" might be examples of implicit spatial relations. -- Topological relations are any other kind of relation that -- explicitly stated by the Visual Programmer and can not be inferred -- by geometric properties. A topological relation will most likely -- have it's own graphic representation. -- -- The Object Set contains relations in the sense that, along with the -- graphical objects, the Object Set provides a means by which the -- relationships in the object set can be evaluated to True or False -- given any to types of objects. -- -- Each Object Set is referred to by name. An Input Set can contain -- well-formed sentences of any Language Spec iff they are both -- based on the same Object Set. -- ; end ObjectSet; obj DefaultObjectSet is ObjectSet description: -- The predefined set of textual and graphical objects. ; end; --------------------------------- Terminal ------------------------------------ object Terminal components: name:Name, ttype:TerminalType, id:Id, pos:Position; operations: DrawTerminal(c: Canvas, t: Terminal) -> (c': Canvas); MatchTerminal(t1: Terminal, t2: Terminal) -> (b: boolean); description: -- A terminal is a graphic object which has a size, location, and -- orientation. It is displayed graphically on a drawing Canvas. -- -- Each terminal has a certain Type which decides how that -- Terminal is draw on the drawing Canvas. Each inherits from a -- Terminal has a unique identifier Id, as well as a Location, -- Bounding Rectangle and Orientation on the Drawing Canvas. -- -- Terminals appear on the RHS of a Rule in a Language Spec. Here -- only the type is important, and any instance values mentioned -- above are ignored. -- -- A Match function determines whether two Terminals are of the -- same type (i.e. both are of type Circle). ; end Terminal; object Name is string; object TerminalType; object Id; -- The Name and TerminalType both uniquely identify different types of -- Terminals, such as "Circle", "Square", "Line", "Cloud" and so on. -- They may be the same, but Name must be a human readable string. -- Id uniquely identifies instances of a terminal within an Input Set. object Position; -- The Position of a terminal determines where it is in space relative to -- other terminals. The degree of dimension of that space should be -- encapsulated in this object and the spatial relation methods which will -- most likely access this attribute. ----------------------------- Relation ---------------------------------------- object Relation components: Name, Signature, Definition; operations: EvaluateRelation(r: Relation, t: Terminal*)->(b: BOOLEAN); description: -- A Relation may be either a Spatial Relation or a Topological -- Relation, both defined below. A Relation is just a predicate -- which is evaluated over one or more Terminals and returns a -- boolean value depicting whether that relation holds over the -- given Terminals. -- -- Each Relation has a Name, as well as a Signature which determines -- the number of input Terminal arguments that it will take. -- Signatures need not specify type: "InsideOf(Line, Dot)" may simply -- return false when the arguments make no sense. -- -- Eeach Relation also has a Definition which may be somehow executed -- over the input arguments so that the relation may be evaluated by -- the Evaluate function. -- ; end Relation; object Signature; -- This specifies the signature of the relation. Since all relations take -- Terminals as arguments and return boolean, this may very well boil down -- to simply the arity of the relation. object Definition; -- The definition of a relation is some kind of executable code which, -- given a set of arguments, can be used to determine whether the -- relation holds over those arguments or not. See comments for the -- Relation object... object SpatialRelation inherits from Relation; -- A spatial relation uses the information in the arguemnt Terminals -- to determine whether the relation holds or not. object TopologicalRelation inherits from Relation components: Terminal*; operations: DrawTopoRelation(c: Canvas, t: TopologicalRelation) -> (c': Canvas); ConnectTopoRelation(tr: TopologicalRelation, t: Terminal) -> (tr': TopologicalRelation); description: -- A Topological Relation is any kind of relation that is not spatial -- and thus can not be determined implicitly by the locations of a -- set of Terminal Objects. Rather Topological Relations are -- explicitly created by the Visual Programmer when an Input Set -- created. -- -- E.g., consider an Arc which is "attached" to two terminal -- objects by the drawing editor and rubber bands as they move. The -- arc is topologically connected to the objects, rather than -- spatially. We need to account for these types of relations as -- well. -- A Topological Relation (such as an arrow) is still a -- relation, but it is actually drawn on the screen. Where -- it is drawn depends on the location of the Terminals which -- the Topological Relation references -- -- An inherits from a Topological Relation actually *references* the -- objects over which it holds. The evaluation just sees if -- the input arguments match these objects. -- ; end TopologicalRelation; ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- --------------- top level object: LanguageSpec ---------------------------- ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- object LanguageSpec components: Name, Rule*; operations: CreateLanguageSpec(n: Name)->(l': LanguageSpec), EditLanguageSpec(l: LanguageSpec)->(l': LanguageSpec); description: -- -- A LanguageSpec is a set of re-write rules, similar in form -- to a BNF grammar. The main difference here is that, the tokens -- of a 1-dimensional textual language are all ordered along that -- single dimension, and thus, matching is a straight forward -- left to right operation; -- -- Here, we are dealing with k-dimensional input. The tokens of the -- right-hand-sides of our re-write rules appear as a one-dimensional -- string, but may be matched in any order. Thus the RHS's of our -- rules are *unordered*. -- -- - See description for the Rule object for more. -- -- - Also see [Golin 89], [Whittenburg 92] for more on this -- avoid -- solutions that restrict the input set relations such as [Tucci 88]. -- -- NOTE: A Language Spec does not necessarily need to be -- unambiguous. There may be several valid rule-match sets for any -- given Input Set. Also, there is no guarentee that the matching -- of the input set will terminate. ; end LanguageSpec; --------------------------- Rule ------------------------------------------ object Rule components: LHS, RHS, SemanticAction, Predicate*; operations:; MatchRule(i: InputSet, r: Rule)->(a: SemanticAction); description: -- A Rule is a rewrite rule of a Lanuguage Spec. Like a rewrite -- rule of any other grammar, a Rule is composed of a Left-Hand- -- Side, a Right-Hand-Side. The LHS is a single Non-Terminal. -- The RHS is a combination of Terminals and Non-Terminals. -- -- Unlike other grammars, the elements of the RHS are not matched -- in any particular order (see description for the LanguageSpec -- object) -- -- So, to give our RHS's meaning, we qualify them by insisting that -- certain Relations hold over various combinations of the items that -- appear in our unordered RHS. We do this by specifying a set of -- predicates, each of which is expressed in terms of a relation and -- then names the RHSItems (see below) that are to be supplied as -- arguments to that relation. The rule will be matched by the -- set of Terminals and Non-Terminals that match the RHS in some -- order and satisfy all of the predicates supplied with the rule. -- -- Note, some types of grammars such as [Whittenburg 89, 92] make -- certain restrictions on which predicates may, and must be -- specified. -- -- What we end up with is a BNF-like grammar where our RHS's are comp- -- osed of Non-Terminals, Terminals and a set of Relations that must -- hold for the RHS to match. Like yacc, we can attribute our rewrite- -- rules with Semantic Actions that are to be executed when the rule -- is matched. -- -- Depending on how this is implemented, Matching Rules to an Input- -- Set may result in a parse-graph rather than a parse-tree. In other- -- words, we may wish to account for a *remote* item matching an RHS -- which is not actually *expanded* underneath it. See [Golin 89] for -- more on this. ; end Rule; --------------------------- LHS / RHS ------------------------------------- object LHS is NonTerminal; object NonTerminal is string; -- A Non-Terminal is just some kind of unique place holding entity in the -- language spec. It has a textual representation (string) that is meaningful -- to the LanguageDesigner. object RHS has RHSItem*; -- This may be a bit confusing. A single RHS of a Rule is composed of one -- or more RHSItems. In a regular grammar, an RHS Item is just a Terminal or -- non-terminal. Here each item is associated with a unique name within the -- RHS so that the RHSItem may be specified as an argument to any of the -- Predicates that are included with the Rule. object RHSItem components: RHSItemName, Terminal or NonTerminal; operations:; description: -- An RHS is composed of a set of these things. -- This is just like any other RHS item of any other grammar -- (Terminals and Non-Terminals) except that each item is "named" -- with a unique name so that it may be specified as an argument to -- any of the predicates that are associated with the rule. ; end RHS; object RHSItemName is Name; --------------------------- Predicate ------------------------------------- object Predicate components: Relation, RHSItemName*; operations:; description: -- A Rule is composed of a set of these, among other things. -- A Predicate just specifies a Relation along with a set of -- RHSItemNames which specify what RHSItems are to be given -- to the Relation as arguments. -- ; end Predicate; ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- --------------- top level object: InputSet ----------------------------- ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- object InputSet components: Terminal*, TopologicalRelation*; operations: CreateInputSet(n: Name)->(i': InputSet), EditInputSet(i: InputSet)->(i': InputSet); ParseInputSet(l: LanguageSpec, i: InputSet)->(p': ParseTree*); description: -- This is the set of Terminals that is created by the Visual Pro- -- grammer and then submitted for parsing. It must be composed of -- Terminals from the same Object Set that the Language Spec was. -- -- The Input Set consists of Terminals, each of which has had a -- Position specified for it. Any Spatial Relations which may -- hold over those Terminals may then be inferred. The Input Set -- also consists of any Topographical Relations that has been -- explicitly specified by the Visual Programmer. -- ; end InputSet; ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- --------------- top level object: RelationalParser ------------------------- ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- object RelationalParser components: ParserMatchTable; operations: MonitorParser()->(p': ParserMatchTable); description: -- I can too specify this in the requirements! Exactly how this -- thing will work is up to design and implementation, but what we -- do know is that: -- The Expert User able to view the progress of the parse by examining a -- ParserMatchTable which shows all rules that are being matched, -- what stage they are in and what has been used from the InputSet -- to match them. ; end RelationalParser; ---------------------------- ParseMatchTable/State ------------------------- object ParserMatchTable has ParseMatchState*; object ParseMatchState components: Rule, (Terminal or NonTerminal)*, Completed : boolean; description: -- A ParseMatchState maintains the current state of each rule that -- has been either partially or completely matched. ; end ParseMatchState; ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- --------------- top level object: ParseTree -------------------------------- ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- object ParseTree components: ParseMatchState*; operations: ExamineParseTree()->(p: ParseTree); description: -- A parse tree is just a set of matched rules whose RHS terminals -- refer to instances in the input set and whose non-terminals refer -- to other rules that eventually cook down to non-terminals -- -- In otherwords, a set of ParseMatchStates where Completed = TRUE ; end ParseTree; ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- ------------------- SLIVER OPERATIONS ------------------------------------ ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- op CreateObjectSet(n: Name)->(o': ObjectSet) pre: ; -- No ObjectSet exists with the name n post: ; -- One object set exists with the name n description: ; -- The Expert User can create Objects and Relations in t*he Object Set -- Specifically, the way Objects appear on the screen are specified, -- as well as how position, location, orientation are maintained. -- Also, the Expert User can specify which Relations hold over the -- objects in the Object set, and how those Relations will be calculated. end CreateObjectSet; op EditObjectSet(o: ObjectSet, d: DefaultObjectSet)->(o': ObjectSet) pre: ; post: ; description: ; -- The Expert User freely alters any of the Objects or Relations in -- the Object Set end EditObjectSet; op DrawTerminal(c: Canvas, t: Terminal) -> (c': Canvas) pre: ; post: ; -- the Terminal is graphically displayed on the Canvas description: ; -- It is assumed that the Terminal object has a size, location and -- orientation which has been specified by the Visual Programmer. -- This operation draws that object on the screen via the drawing Canvas. end ; op MatchTerminal(t1: Terminal, t2: Terminal) -> (b': boolean) pre: ; post: -- if t1.TerminalType == t2.TerminalType then b' == true -- else b' == false b' = (t1.ttype = t2.ttype); description: ; -- This determines if two Terminal are of the same TerminalType and -- thus match. This is used in matching Terminals from the Input Set -- to terminals in the Language Spec. end ; op EvaluateRelation(r: Relation, t: Terminal*)->(b': boolean) pre: ; -- t & r are both members of the same Object Set post: ; -- b' = true if evaluating r.Definition with the arguments in t -- results in true, otherwise b' = false description: ; -- This evaluates a Relation with a set of arguments t according -- to the definition of that relation. The result of this operation -- indicates whether or not that relation holds over the argument -- objects or not. end ; op DrawTopoRelation(c: Canvas, t: TopologicalRelation) -> (c': Canvas) pre: ; post: ; -- the DrawTopoRelation is graphically displayed on the Canvas description: ; -- This is similar to the DrawTerminal operation: -- It is assumed that the DrawTopoRelation object has a size, location and -- orientation which has been specified by the Visual Programmer. -- This operation draws that object on the screen via the drawing Canvas. end ; op ConnectTopoRelation(tr: TopologicalRelation, t: Terminal) -> (tr': TopologicalRelation) pre: ; -- tr & t are elements of the same Object set post: ; -- t is an element of tr.Terminal description: ; -- The Visual Programmer, most likely by means of a graphical editor, -- explicitly creates a topological relation and connects it to one -- or more terminals. end ; op CreateLanguageSpec(n: Name)->(l': LanguageSpec) pre: ; -- No CreateLanguageSpec exists with the name n post: ; -- One CreateLanguageSpec exists with the name n description: ; -- The Language Designer creates a Laguage Spec which describes -- valid visual "sentences" in that visual language, as well as -- semantic actions that are to be executed when production rules -- are matched to input. end ; op EditLanguageSpec(l: LanguageSpec)->(l': LanguageSpec) pre: ; post: ; description: ; -- The Language Designer freely alters any of the Objects or Relations in -- the Object Set end ; op MatchRule( i: InputSet, r: Rule)->(a: SemanticAction) pre: ; -- Both the Objects in the Input set and the Objects in the Rule have -- been derived from the same Object Set post: ; -- All Terminals and non-Terminals of the Rule have been matched by -- some set of items from the input set, and all of the predicates -- of the rule have been satisfied by those matching items. description: ; -- This operation takes an Input Set and a Rule and does what ever it -- takes to match items in the input set to the RHS of the rule, while -- satisfying the predicates of the rule. end ; op CreateInputSet(n: Name)->(i': InputSet) pre: ; -- No CreateLanguageSpec exists with the name n post: ; -- One CreateLanguageSpec exists with the name n description: ; -- The Visual Programmer creates an Input Set by creating a -- visual program. This is done by means of some kind of -- graphic editor end ; op EditInputSet(i: InputSet)->(i': InputSet) pre: ; post: ; description: ; -- The Visual Programmer can freely alter any of the items in an input set -- most likely by means of some kind of graphical editor. end ; op ParseInputSet(l: LanguageSpec, i: InputSet)->(p': ParseTree*) pre: ; -- l and i are both derived from the same Object Set post: ; -- all of the rules in the p' have been matched by items in -- the input set description: ; -- This is the heart of the project. Given a LanguageSpec and an -- input set, this operation produces one or more valid Parse Trees -- where items from the Input Set have been matched against -- the rules of the Language Spec end ; op MonitorParser()->(p': ParserMatchTable) pre: ; post: ; description: ; -- As the parsing operation proceeds, the Expert User is able to -- monitor the progress of the parse by viewing the Parser Match -- Table. This is some sort of structure which shows all of the -- Language Spec Rules that are currently in the process of being -- matched or have been completely matched by items from the Input -- Set. end ; op ExamineParseTree()->(p: ParseTree) pre: ; post: ; description: ; -- Similar to the Monitor Parser operation, but this allows the -- language designer to examine only the results of a parse by -- looking at the resulting parse tree. This will show what -- rules of the Lanugage Spec have been matched by which objects -- from the Input Set and in what order this has happened. end ;