Is Programming Theory needed?

Recently I came across the webpage Programming Theory: What is it, and do you really need to know it (and when)? . For me the answers by others are not satisfying.  You can read my response in that webpage. I myself has written programming theory in Programming Theory. This is a not so short writing about that. This part of Programming Theory series is based on sec 2.1 of my doctoral dissertation titled “Orthogonal Inheritance-based Polymorphism, and Module-based Encapsulation; with Implementation in NUSA Programming-Language“. Chapter 2 is titled “Theoretical Foundation I: Basic Concepts of Programming, and Orthogonality“.

Solid Theory of Programming is Needed

This chapter establishes a solid theoretical foundation for programming, computing, and software. Without the solid theoretical foundation, properly defining advanced concepts such as encapsulation, inheritance, and polymorphism – subjects of this dissertation – would be futile. The definitions will be shallow.

This chapter provides the answer to the question: what is the universal and solid theoretical foundation for programming, computing, and software? The answer is the six main concepts of programming that consists of four main concepts and two supplementary concepts. The former are value, operation, type, and object; shortened VOTO. The latter are punctuator and qualifier.

VOTO will be proven essential and serving its purpose well in the later chapters up to the appendices. VOTO is the foundation for defining orthogonality (as promised at the end of chap 1), modular programming (chap 3), object-orientation (chap 4), encapsulation (chap 5), inheritance (chap 6), polymorphism (chapter 7), and NUSA programming-language (chapter 8). For the universality of VOTO as a theory, appendix A and B proves its ability to define functional and logic programming.

2.1 In search of solid theoretical foundation

Searching for solid theoretical foundation for programming proves to be very difficult. Software engineering standard [56] defined terms informally. Research paper authors either do not define terms (e.g., object) that are thought to be taken for granted, or define terms differently from other authors [51]. Reference [6] wrote that in 1995 that the job title ‘Software Engineer’ is illegal in many states of US, and not accredited by ABET: Accreditation Board for Engineering and Technology.  Subsection 2.1.1 highlights examples that can explain the rejection of ABET. Subsections 2.1.2 through 2.1.5 present our concern and solution criteria.

2.1.1 Sample problems in the theory

The confusions in programming theory and practice are due to the lack of solid theoretical foundation [16-18]. Few researchers and standard committees admit the presence of confusions in the world of programming, especially on the prevailing OOP [16-18, 83-84]. Despite the rare admission, the problems can be found in several literatures within the bibliography of this dissertation. For example, IEEE Standard Glossary of Software Engineering Terminology [56] defines object as “(1) Pertaining to the outcome of an assembly or compilation processSee also: object code; object module; object program.” The definition is not aligned with explanation such as in [59] “an object of type T is defined“. In ref [59], object is not the outcome of an assembly or compilation process.

Textbooks added the confusions. Grady Booch, Robert A. Maksimchuk, Michael W. Engel, Bobbi J. Young, Jim Conallen, Kelli A. Houston wrote ref [9] that is considered authoritative. The authors define object as

something you can do things to.  An object has state, behavior, and identity; the structure and behavior of similar objects are defined in their common class.  The term instance and object are interchangeable.

            That definition is neither formal nor helpful. Big companies like Microsoft, Intel, and Hewlett Packard have their share in adding the confusion, this time by not defining the term object. The three companies produce C# standard [26] that does not define object. This vacuum gave rise to ad hoc definitions of object presented up to the end of this subsection.

Not defining a term is an extreme. Another extreme is providing too many definitions. This is exemplified by ref [83] that proposed five definitions of object

  1. Conceptual (modeling) viewpoint: object as a conceptual model of some part of a real or imaginary world.
  2. Philosophical viewpoint: object as an existential as opposed to universal abstraction.
  3. Software engineering or data abstraction viewpoint: object as a module (a collection of encapsulated operations and variables and other language constructs).
  4. Implementation viewpoint: object as a contiguous structure in memory, possibly containing or referring to other similar structures.
  5. Formal viewpoint: object as a graph of interrelated state machines.

The fifth item, claimed to formal, is not formal. Let us proceed. A definition can be too narrow (e.g., keyword dependent) as well as too wide. The definition of object from ref [9] is too narrow, it limits the definition of object to programming-languages that use keyword class. On the other extreme, the definition of SQL standard [61] is too wide, as written in the box that follows.

object (as in ‘‘x object’’): Any thing. An x object is a component of, or is otherwise associated with, some x, and cannot exist independently of that x. For example, an SQL object is an object that exists only in the context of SQL; an SQL-schema object is an object that exists in some SQL-schema.

            By saying that object is anything, we need no other terms: operators, values, types, punctuator, qualifier, and any other terms or concepts. No notion of value, of type, of operator, of punctuator. This kind of definition is a big problem. The absence of universally agreed upon precise formal definition have causes programmers to define terms as they wish. Here are some of online definitions:

  • a component of a program that knows how to perform certain actions and to interact with other pieces of the program [1].
  • Wikipedia (en.wikipedia.org/wiki/Object_(computer_science)) : “any entity that can be manipulated by the commands of a programming language, such as a value, variable, function, or data structure“.
  • A software bundle of variables and related methods[2]
  • a “black box” which receives and sends messages.” [3]

[1] http://www.intap.net/~drw/cpp/cpp06_01.htm

[2] journals.ecs.soton.ac.uk/java/tutorial/java/objects/object.html

[3] http://www.softwaredesign.com/objects.html

2.1.2 In search of the criteria

Having seen the problems in the current literature, we need to define the solution and its criteria. The solution is the set of basic and supplementary concepts that underlies ALL the advanced concepts. The ability to underly all advanced concepts is a criterion of solid theoretical foundation. But that criterion is a good step into better defined criteria written in subsec 2.1.3 through 2.1.5.

With the failure of literatures in formulating the basic and supplementary concepts that underly all advanced concepts in computing, the author seeks the world outside software engineering [1]. Figure 1.1 in sec 1.6 indirectly shows that physics – through ref [34, 67] – is a source for the criteria. The next three subsections explain the properties of physics that sets the solution criteria.

[1] Reference [29] says that software engineering is programming in the large. Adopting the idea, concepts for programming (in the large) are concepts for software engineering.

2.1.3 Property 1 of physics: Well-definedness

Physicists use the term base quantity and derived quantity; please see Base quantity in Table 2.1. Base quantities and derived quantities in physics have the property of well-definedness. The same can be said to the base-unit, derived-unit, the units, and measure for the quantities, as tabulated in Table 2.2.  This tabulation exists in virtually all physics and engineering textbooks, e.g., [34], [67], and [71].

Table 2.1 Base quantities and base units in physics [34] [67]

Base quantity Base unit
Mass Kilogram
Length Meter
Time Second
Electric current Ampere
Temperature Kelvin
Amount of substance Mole
Luminous intensity Candela

 

 

Table 2.2 Base quantities, base units, and their measures [34]

Base quantity Base unit Measure
Mass Kilogram Equal to the mass of the international prototype of the kilogram
Length Meter Length of the path travelled by light in vacuum during a time interval of 1/299 792 458 of a second
Time Second Duration of  9 192 631 770 periods of the radiation corresponding to the transition between the two hy-perfine levels of the ground state of cesium 133 atom
Electric current Ampere Constant current which, if maintained in two straight parallel conductors of infinite length, of negligible circular cross section, and placed 1 meter apart in vacuum, would produce between these conductors a force equal to 2 x 10-7 newton per meter of length
Temperature Kelvin The fraction 1/273.16 of the thermodynamic temperature of the triple point of water.
Amount of substance Mole The amount of substance of a system which contains as many elementary entities as there are atoms in 0.012 kilogram of carbon 12.
Luminous intensity Candela Luminous intensity of a source that emits mono-chromatic radiation of frequency 540 x 1012 hertz and that has a radiant intensity in that direction of 1/683 watt per steradian.

 

Figure 2.1 shows how base quantity Length can derive the derived quantities area and volume. Base quantities Length and Time can derive the derived quantity Velocity. The label in fig 2.1 emphasizes units (Newton, Joule, lm) instead of quantities (Force, Energy, Luminous Flux). Still, fig 2.1 demonstrates the well-definedness within physics; all quantities and units are well-defined.

NIST

Figure 2.1 Base quantities and derived quantities [1]

Concepts in physics meet the criteria for solid theoretical foundation.  For software – and thus programming – such solid theoretical foundation is yet to be established. In absence of such theoretical foundation for software, the author offers a tentative one, to ease the elaboration of problems and solution within this dissertation. Without this theoretical foundation, examination of previous works is impossible (e.g.: how to critically examine the concept of class?).

It is customary in physics to use the abbreviation of base quantities. Table 2.3 shows a similar tabulation with Table 2.1, but now with abbreviations. In Table 2.3 (that is similar to the left part of fig 2.1), some base quantities are not named with the abbreviation of the base quantity. Instead, the abbreviations of base units are used. This applies to electric current, thermodynamic temperature, amount of substance, and luminous intensity. The electric current is referred to by A (for Ampere), the thermodynamic temperature is referred to by K (for Kelvin),

[1] http://physics.nist.gov/cuu/Units/SIdiagram.html

the amount of substance is referred to by mol (for mole), and the luminous intensity is referred to by cd (for candela). Table 2.3 lists the conventions.

Table 2.3 Abbreviated base quantities in physics [34] [71]

Base quantity Base unit
M kg
L m
T sec
A A (or Amp)
K K
Mol Mole
Cd Cd

 

2.1.4 Property 2: Unique (Non-redundant)

In physics there is no redundant base quantity. This criteria needs to be explicitly stated here to properly establish the similar theory for software. If base quantity is basic concept, all basic concepts must be unique.

2.1.5 Property 3: Closure of Concepts

The closure of concepts means that all derived (or advanced) concepts must be based on the basic (and supplementary) concepts only.  In physics no derived quantity comes out of the blue (please see fig 2.1). All derived quantities must be derived from base quantities.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s