|
Is there machine readable ontology of data structures and programming language constructs: tree is ..., consists of ...? I need it to automatically choose appropriate data structure and generate code to create/modify/convert it. EDIT: More detailed example. In it I introduce data structure in pseudocode and pseudo-english :) named A-tree for simplicity. In addition to its definition I need a definition and properties of ordinary tree and want to take it from standard ontology. "A-tree is tree. It consists of ( (type is top) and list of subtrees ) or EDT. type and subtrees are A-trees. EDT is (string or int). (node and subtree) address is A-tree. address type is TPtr, subtrees are ([TType, Type] or [TNum, Num]), where (Type or Num) is (type or number) correspondingly of current subtree. address of main tree is [TPtr, []]." "tree consists of top and subtrees. top is node. subtree is tree. leaf = tree without subtrees." |
|
Answering the edited question, what you describe is very similar to the way data structures are declared in typed functional languages like Haskell. For example, the Maybe type in Haskell can hold a value (of generic type a) or nothing. This is similar to returning a value or null in Java. It is defined as data Maybe a = Nothing | Just a Furthermore, Maybe is an instance of a bunch of typeclasses (Monad, Functor, and so on; listed in the documents). For more complicated examples see, for example, Data.Map. It is Traversable, Foldable and so on. Or see Data.Set or Data.Sequence or, well, you get the idea. This kind of type is known as an algebraic data type. Remarkably, given an algebraic data type one can automatically derive a general transformation function (called fold) and a general constructor (called unfold). This is the closest thing I know to what you describe. I don't know any formal work that encodes, e.g., complexity of different operations. This is in general impossible to prove, so such an encoding would just be annotations that couldn't be checked so it isn't likely anyone would bother. |
|
The only one I could find (and I used to be quite the Ontology Otaku) is the COPS ontology (Core Ontology of Programming and Software) I suspect you are looking for something more fundamental and less descriptive. I don't know if ontologies are still a hot topic, but if there is no ontology for describing data structures and algorithms, that looks like a fairly straight path to a dissertation topic. |
|
The form that you are looking for is called Backus Naur form (also check out Extended-BNF or Augmented-BNF). It is a machine readable form which is similar to the lambda descriptions provided in previous answers. These forms can be used to describe the grammar of programming languages, and is the method used by grammatical evolution to extend genetic algorithms to evolution of computer programs. |
|
I'm not really sure what you're asking. Every language has a grammar that describes the surface syntax. Any language with a formal definition (e.g. Scheme, ML, parts of Haskell) will have as part of that definition some internal representation into which the surface syntax is transformed. This may take the form of an abstract syntax tree or possibly a lower-level machine representation. The are many formal computational models, of which the Lambda Calculus is a popular one. Skip to the formal definition on the Wikipedia page to see how expressions in the Lambda Calculus are constructed. Finally, books like PLAI give an overview of a broad range of constructs found in programming languages. That's every way I could think of answering your question. If you make it more precise I can make my answer more precise. I made a mistake: at this stage I need data structure ontology more and it needs to be machine readable.
(Sep 27 '10 at 23:49)
DSblizzard
1
Want I think you want is a data structure to encode a program. This is usually called an abstract syntax tree. What abstract syntax tree you use is determined by the programs you want to encode (and partly by what properties of those programs you want to emphasise). For example, for the lambda calculus a simple abstract syntax tree, in a pseudo-ML notation, is: type Variable = String type Program = Listof Expr type Expr = Variable | Function | Application type Function = Fn Variable * Expr type Application = App Expr * Expr
(Sep 28 '10 at 02:43)
Noel Welsh
For PL constructs this is perhaps what I will need, hard to say, but not for data structures. For example array will be only mentioned, but in ontology it will be quite complex object with many links.
(Sep 28 '10 at 05:58)
DSblizzard
|
I think I understand what you mean, it's something I'm looking for also. If there is none, would you be interested in building one?