In software or program ontologies described in the literature, the separation between abstract and implementation views is evident. On the other hand, the ontological entities involved in such views are not very well defined in the context of programs life-cycle, having as parts conception, construction plan, construction process and verification. In many papers the ontological entities described are not very well grounded and they are only assumed as premises without top ontological background. To provide answers to some raised questions, this paper presents a computer program ontology based on the Basic Formal Ontology (BFO) and an interpretation of such an ontology. The ontology and its interpretation show how a computer program ontology is complex and need to advance to attend some theoretical or practical needs.
In software or program ontologies described in the literature, the separation between abstract and implementation views is evident. On the other hand, the ontological entities involved in such views are not very well defined in the context of programs life-cycle, having as parts conception, construction plan, construction process and verification.
In many papers the ontological entities described are not very well grounded and such entities are only assumed as premises without top ontological background, without providing an ontological account of the entity’s types of computer programs nor a clear meaning for program abstraction and implementation. Based on these general issues, the main questions taken into account here are the following:
Though some works in the literature [
To provide answers to such questions, this paper presents a computer program ontology based on the Basic Formal Ontology (BFO) and an interpretation of such an ontology. The ontology and its interpretation show how a computer program ontology is complex and need to advance to attend some theoretical or practical needs.
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
The paper is organized as follows. In Section 2, there is a presentation on Algorithms, Computer Programs and Ontologies described in the literature. In Section 3 we present the most important elements of Basic Formal Ontology (BFO) used here. In Section 4, we present a proposal of a Computer Program Ontology and its interpretation. Finally, in Section 5, we present the concluding remarks.
The literature on algorithms and computer programs is vast, but the same is not true for program ontologies. Thus in this section, we intend to highlight some fundamental points about algorithms, computer programs and computer ontologies.
According to
For Donald
For Knuth, an algorithm is an effective method expressed as a finite list of welldefined instructions for calculating a function. Such a method must possess the following properties:
Finiteness: The algorithm must always terminate after a finite number of steps. Definiteness: Each step must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case.
Input: An algorithm has zero or more inputs, taken from a specified set of objects.
Output: An algorithm has one or more outputs, which have a specified relation to the inputs.
Effectiveness: All operations to be performed must be sufficiently basic so that they can be done exactly and in a finite length of time.
For each problem or class of problems, there may be many different algorithms. For each algorithm, there may be many different implementations (programs).
For Moschoyakis [1988], Turing machines capture the notion of mechanical computability of a number of theoretic functions, by the Church-Turing Thesis, but they do not present a mechanical computation to be realized by physical machines. This means that important aspects of the complexity of computations are not captured by Turing machines. In addition, for Moschoyakis [2001], algorithms are generally identified with abstract machines, mathematical models of computers, sometimes idealized by allowing access to "unbounded memory". But for him such a view does not provide a clear way to define algorithms correctly. Moschoyakis [2001] argues that a plausible solution is to see algorithms as defined by recursive functions while physical machines model implementations, a special kind of algorithms. In practical terms, it is not clear what an implementation is and how algorithms and implementations are ontologically connected.
In defining what a program is,
In other words, a computer program can be in three states. The first one is the
pattern of a source code. The second state is the pattern of a machine code. Both of
them are static stages. The third stage is when a machine code is in a position of
instructing the computer to do something. In any of these stages, the algorithm is the
guiding entity that is incorporated and represented by them. Nevertheless, despite
providing an interpretation of what a computer program is,
Another important aspect in the context of computer programs is the
implementation of computational models.
A computational model is an abstract description of a system that reliably conforms to a finite set of mechanical instructions. The instructions dictate how to transit between states. A physical system implements the computational model when the system reliably conforms to the instructions. Thus, a Physical system P realizes/implements a computational model M just in case the computational model M accurately describes the physical system P. In other words, a physical system implements a computational model only if the system can instantiate states belonging to the state space description induced by the model.
Aiming at characterizing a software as a social artifact,
In terms of ontology,
On the basis of an ontology of software which accounts for the possibility for
software to change while maintaining its identity,
Extending their view on program and its identity criteria needs,
A program is constituted by some code intended to determine a specific behavior inside the computer. Such behavior is specified by a program specification.
A software system is constituted by a program intended to determine a specific external behavior of the machine (at its interface with the environment). Such external behavior is specified by a software system specification.
A software product is constituted by a software system designed to determine specific effects in the environment as a result of the machine behavior, under given domain assumptions. Such effects are specified by the high level requirements.
In discussing problems related to computer program ontologies,
Metaprograms - contain statements describing programs, such as algorithms, abstract automata, and software design specifications, which consist of constraints imposed on the structure or behavior of programs such as software metrics and, in particular, descriptions in the literature on software design, including architectural styles, design patterns, and abstract data types. They also include informal descriptions.
A program is divided into Program Scripts and Program Processes. ◦ Program Script - A-temporal entities which consist of well-formed instructions to a given class of digital computing machines, commonly represented as inscriptions or text files. ◦ Program Process - Temporal entities that are created by a process of executing (running) a particular program-script in a particular physical setting, also known as operating system processes or ‘threads’.
We observe two categories of program-scripts: scripts encoded in a machine language, the category of which is generally referred to as machine code, and scripts encoded in a high-level programming language, the category of which is generally referred to as source code.
In our view, the ontologies described in the literature have the main purpose of clarifying the semantics of the elements of computer programs, as well as the semantic of programs as whole. On the other hand, such ontologies do not provide an account of the semantic of the programs in the context of their life-cycle, once they do not include the entities that represent program conception, construction plan, construction process, and verification. Thus, we argue here that taking into account the life-cycle view as the context for ontologies of program, we open up new possibilities of theoretical and practical studies.
BFO is grounded in the Aristotelian tradition. It is an upper-level ontology, designed to
be very small and aiming at consistently representing those upper level categories
common to domain ontologies of different fields. BFO is grounded in two broad
categories of entities: continuant and occurrent. Figure 1 depicts the entities of BFO
here considered. In what follows, we describe such elements taking
Continuant entities are those entities that continue or persist through time, preserving their identity through changes, and have no temporal parts.
An Independent Continuant is a Continuant entity that is the bearer of qualities. If a continuant entity a is the bearer of quality b, then we also say that b inheres in a. Independent continuants are such that their identity and existence can be maintained through gain and loss of parts, and also through changes in their qualities, through gain and loss of dispositions, and of roles.
Material entities have some portion of matter as part. It is thus an independent continuant that is spatially extended in three dimensions and that continues to exist through some time interval.
Maximally self-connected, which means the different parts of the object are tied together in a certain way and that anything that is tied to these parts in the same way is itself part of the object.
Generically Dependent Continuants are entities that depend on one or other independent continuants that can serve as its bearer. We can think of the generically dependent continuants as complex continuant patterns of the sort created by authors or designers or, in the case of DNA, through the process of evolution. Examples include the Facebook trademark, the pattern that is your own signature, and a square arrangement of sixty-four alternating black and white squares. Each such pattern exists only if it is materialized in some counterpart specifically dependent continuant. Such a relation in BFO is technically called “concretized by”.
Information Content Entities (ICEs) provide information about something in reality.
They have this something as a subject; they represent, mention or describe this
something; they inform us about this something [
Information Structure Entity (ISE). An ISE is a structural part of an ICE; speaking
metaphorically, it is an ICE with removed content: for example, an empty cell in a
spread-sheet; a blank Microsoft Word file. ISEs thus capture part of what is involved
when we talk about the ‘format’ of an information artifact [
A Realizable Entity is defined as a specifically dependent continuant that has at least one independent continuant entity as its bearer, and whose instances can be realized, in the sense of being manifested, actualized, executed, in associated processes in which the bearer participates.
Occurrents are those entities that occur, happen, unfold, or develop in time, usually referred to as events, processes or happenings. Occurrents are either processes that unfold in successive phases, or they are the instantaneous boundaries of processes, such as their beginnings or ends, or even the temporal and spatiotemporal regions that such entities occupy.
A Process is an occurrent entity that exists in time by occurring or happening, has temporal parts and it always depends on some material entity. The dependence here is analogous to that between a specifically dependent continuant and its independent continuant bearers. Examples of processes include the life of a given organism, the course of a disease, the process of cell division, and the fall of water down a waterfall.
In this section we present the proposed ontology used as reference to interpret computer programs and a section to discuss such interpretation, due to the important aspects to be discussed.
In software or program ontologies described in the literature, the separation between abstract and implementation views is evident. On the other hand, some of the ontological entities involved in such views are not very well defined.
For
Thus on the basis of gaps identified in the literature, Duncan work, the author’s experience in computer science, his participation in the Industrial Ontological Foundry, and his use of BFO, we came up with the ontology depicted in Figure 2. Such ontology extends the ontology presented in Figure 1, now extending the lower levels types of entities. In what follows, the several entities are described.
Program Requirement Statement. A Directive Information content entity that prescribes a process or the product needs an agent has.
Specification. A Directive Information Content Entity that prescribes some parts, features, or some outcomes of a planned process.
A Plan Specification is a specification with action specifications and objective specifications as parts. When concretized, it may be realized in a process performed by an agent to achieve the prescribed process endpoints by taking the prescribed actions. Program Specification. A Plan Specification entity that prescribes some parts, features, or some outcomes of a program. The program specification derives from the Program Requirement Statement.
A Verification Report is an Information Content Entity that presents the program variables with the corresponding values obtained during a program execution. A Data Item is an information content entity that presents the program variables with the corresponding values inserted or obtained during a program execution. An Algorithm is a Plan Specification entity that prescribes some parts, features, or some outcomes of a Planned Process. An Algorithm is a Machine-Independent Plan Specification.
A Source Code is a Plan Specification entity that prescribes some parts, features, or some outcomes of a planned process formulated according to a programming language syntax. A Source Code is used by programmers in a language syntax, and internally saved in a computer as a binary code.
A Program Verification Plan is a Plan Specification entity that prescribes how a program should be verified, taking into account the program specifications. Algorithm Elaboration is a Process that has as input a Program Specification and as output an Algorithm.
A Programming Process is a Process that has as input an Algorithm and a programming Language Syntax, and as output a Source Code.
Source Code Compilation is a Process that has as input a Binary Code, a Computer as a participant, and as an output a Machine Code.
Program Execution is a Process that has as input a Data Item, a Computer as a participant which inheres a Machine Code, and it has as an output a Data Item. Program Verification is a Process that has as input a Program Verification Plan, a Program Execution, and a Machine Code, and as output a Verification Report. A Binary Code is an Information Quality Entity (IQE), which is a quality of an information bearing entity, which exists in virtue of such patterned arrangements and which is interpretable as an information content entity. Binary code is the binary representation of the source code before its derivation to machine code by means of the Compilation Process.
A Machine Code is an Information Quality Entity (IQE), which is a quality of an information bearing entity, which exists in virtue of such patterned arrangements and which is interpretable as an information content entity. When a Machine Code inheres in the computer, the computer gains the Capability of executing the Machine Code. Such a Capability is realized during the Machine Code Execution. Another aspect that deserves a comment is the extreme case of specifying a program directly in binary code or machine code. Though this is possible in reality, in practical terms it is not usual. Because of that, to keep the consistency of the proposed ontology, this extreme case is not considered as possible.
Figure 2 – A Computer Program Ontology.
A Computer is an Object, which can inhere a Binary Code or a Machine Code, and it is the bearer of Data Processing and Program Execution Capability. A Computer has physical features and abstract machines. Inheres in and bearer of are inverse relations. Their use depends on the circumstances to offer the best clarity.
A Disposition is a Realizable Entity in virtue of which a process of a certain kind occurs, it can occur or it is likely to occur, given appropriate triggers, in the independent continuant in which the disposition inheres. This process is called the realization of the disposition. The trigger might consist in the objects being placed in a certain environment or being subjected to certain external influence, or it may be some internal event within the object itself. A disposition ceases to exist when its bearer is physically changed. In other words, a disposition exists because of certain features of the physical make-up of its bearer.
Capability is a Disposition that under normal circumstances brings benefits to its
bearer, user, or owner [
A Function is a Capability that exists in virtue of the bearer’s physical make-up, and this physical make-up is something the bearer possesses because of how it came into being either through natural selection or intentional design. That means to say that these entities in question came into being to perform activities of a certain sort, called functioning. A Function is a capability that an object has because it was designed or selected to have it: the function of a heart = to pump blood; the function of a pump = to pump; the function of a screwdriver = to drive screws. Every function is associated with a type of process whose instances are realizations of that function (pumping, heating, etc.).
As already mentioned, Data Processing is a Function whose information processing is nothing but symbol manipulation. Arguably, however, it is interpreted symbol manipulation; moreover, not all symbol manipulations are necessarily information in some sense. So, perhaps, although computers are nothing but symbol manipulators, it is as information processors that they will have an impact. As a subtype of function, Data Processing exists in virtue of computers make-up, and this physical make-up is something computers possess because of how it came into being through intentional design.
The presented ontology provides a very general view of the entities involved in a computer program, including Information Content Entities, Processes, Information Structure Entity, Information Quality Entities, Objects and Realizable Entities. For having being put together, they provide a coherent existence of such entities.
A way to analyze such an ontology coherence is to take a look from left to right, which shows the temporal evolution of a program and its corresponding consequences. The right most entity is the Program Execution Capability, whose realization is graded on a scale that reflects the Program Requirement Statement achievements, or the Program Verification Plan verified by the Program Verification Process.
The Source Code does not provide any kind of action to the computer. On the other hand, the Machine Code can be executed by the Computer, meaning the computer generates the internal machine state transitions. In other words, the Machine Code stored in the Computer provides it with the capabilities which are the Program Requirement Statements that can be realized when the Machine Code is executed.
It is important to mention here that in order to realize a Capability, a Computer has to be the bearer of certain qualities and other additional capabilities that play the role of enablers for the capability of interest of an organism at a certain time. Thus computers with programs installed in them have the capability to run the programs.
Going back to the graded realization on a scale of Program Execution Capability, we noticed it reflects the degree of benefits its exercise brings. The highest value in the scale is achieving all the Program Requirement Statements, while some program failures, not yet identified in program verification processes, can also be seen as impediments for the realization of capabilities during a program execution. The graded realization provides a rich way to interpret program executions, opening up a wide spectrum for analyzing program constructions and executions.
It is also interesting to notice that the entity type "Program" does not appear directly in the ontology, though entity types such as "program verification", "program execution" and "program specification" do. The reason for that is that here a program is seen as a sequence of representations in the context of a life-cycle view: program specification, algorithm, source code, binary code, and machine code. Such representations are made possible by means of a series of associated processes, which realize the inherent function and capability. In other words, a computer program is a sum of these representations, and in BFO context we do not have a type of entity to represent it.
In summary, we can say that the proposed computer program ontology provides a grounded characterization of computer program ontological entities based on the top ontology Basic Formal Ontology (BFO). In addition, the proposed ontology offer a grounded meaning for important entities such as algorithms, source codes, machine codes, and machine code executions, and how they are related. Finally, the ontology brings the meanings for a machine code installed in a computer and the importance of a program implementation in a computer. As all these aspects have not been clearly discussed in the literature, the proposed ontology opens up the possibility of new discussions on several aspects of computer program.
Computer Program Ontology has been a very difficult topic in the literature. The proposed ontologies are very different in terms of content and structure.
The guiding questions used here highlight some aspects to be carefully taken into account when designing a computer ontology, specially when having a very clear purpose and need. When just developing an ontology without considering those the reader can be led to a deadlock. The proposed ontology and its interpretation provide a resourceful way to advance and define more detailed aspects for the use of a Computer Program Ontology.
As already mentioned, computational models are abstract entities, which are not located in space or time, and they do not participate in causal interactions. Under certain circumstances, a physical system aims at realizing or implementing abstract computational model. Which are those circumstances? What is it for a physical system to realize a computational model? When does a concrete physical entity implement a given computation? All these aspects, as well as all those related to a whole computer program ontology, are not ontologically clearly described in the literature.
The presented ontology and its interpretation provide a grounded and organized way for answering the fundamental questions raised in the introduction. Such questions raise important aspects not taken into account in many ontology works.
In other words, the presented ontology and its interpretation provide a grounded way to identify the most important elements involved in a computer program ontology and also a practical guideline to identify the elements to be taken into account and collect representative data in future works. For instance, the ontology provides an encouraging view to developers to think carefully about the information transformations and processes along the program life-cycle to develop methods and tools to improve program development. Another thing is to use this ontology to improve program verification processes, be it testing or formal verification. Formal program verification is an ongoing project in our group.
Acknowledgments. I particularly thank the important support provided by the National Council for Scientific and Technological Development – CNPq.