28 March 2012

Amazing Abstract Algebra: Groups and Rotations


A little while ago I noticed a very interesting group, I am sure it is well known in math circles but I find it intriguing for a number of reasons and I have recently learned more about Abstract Algebra which ties in some more interesting ideas. The group relates to imaginary numbers, it is the set {1,-1,i,-i} which is closed under multiplication. It has an identity which is 1. Each element has an inverse, -1 is its own inverse: -1 · -1 = 1 and -i · i = 1. The following cayley table shows all this:


1 i -1 -i
1 1 i -1 -i
i i -1 -i 1
-1 -1 -i 1 i
-i -i 1 i -1

If you are new to these ideas I recommend looking at my previous post on abstract algebra, especially since we will be looking at some isomorphisms again. In order to talk about the ideas in the post we need to get some group theory concepts out of the way first, don't worry they aren't hard in fact they're fairly intuitive. Also in this post I am restricting the discussion to finite groups, groups with a finite number of elements. In fact the first idea is the concept of group order.

The order of a finite group is simply the number of elements of the set the group is defined on and is denoted as |G|.

The group above has an order of 4.

The next idea is that of exponentiation, which can be thought of as a subset of "classical" exponentiation on the field of real numbers, see identities here. Exponentiation on group elements extends to integer exponents only and refers to repeated application of the binary operation to the element itself. So:


an = a·a·a·a...a ( a "times" itself n times)

a-n = a-1·a-1·a-1·a-1...a-1 (a-1 "times" itself n times or the inverse of an)

a0 = e (where e is the identity element)

The laws of exponents are:

am an = am+n

(am)n = amn

a-n = (a-1)n = (an)-1


Just as a group has an order an element of a group also has an order and it is related to exponentiation and it is defined as:

If there exists a nonzero integer m such that am=e, then the order of the element is defined to be the least positive integer n such that an=e. Also if there does not exist any nonzero integer m such that am=e, we say that a has order infinity.

So the elements in our group (⋅, {1,-1,i,-i}) above have the following orders:

11 = 1 (this is the identity and has order 1) [11 = 1, ...]

-12 = 1 (has order 2) [-11 = -1, -12 = 1, ...]

i4 = 1 (has order 4) [i1 = i, i2 = -1, i3 = -i, i4 = 1, ...]

-i4 = 1 (has order 4) [-i1 = -i, -i2 = -1, -i3 = i, -i4 = 1, ...]

Order is also sometimes referred to as period and you should note that each of the above will cycle through each power listed in the square brackets so for both the order 4 elements {i, -i}: a1n=a1, a2n=a2, a3n=a3, a4n=a4 for all integers n>0 and the values will cycle through the list which would be the case for any element of finite order.

As it turns out elements like i and -i which cycle through all of the elements of a group exactly once in the period have an order that is equal to the order of the group. These define what is known as a cyclic group. So our group is cyclic and any element which cycles through all elements once is the generator so i and -i are generators for the group.

Another interesting result from group theory is that any cyclic group of order n is isomorphic to the group (+,Zn) which is the integers (mod n) under addition so our group above is just a renaming of Z4 see the similarity to the cayley table below:


+ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2

Now I want to take a look at another important group, it's called the dihedral group, this one is known as D4 and has the cayley table:

  R0 R1 R2 R3 V H D1 D2
R0 R0 R1 R2 R3 V H D1 D2
R1 R1 R2 R3 R0 D1 D2 H V
R2 R2 R3 R0 R1 H V D2 D1
R3 R3 R0 R1 R2 D2 D1 V H
V V D2 H D1 R0 R2 R3 R1
H H D1 V D2 R2 R0 R1 R3
D1 D1 V D2 H R1 R3 R0 R2
D2 D2 H D1 V R3 R1 R2 R0

The dihedral group is the group of symmetries of a regular polygon, including both rotations and reflections. In this case we will consider the rotations and reflections of a square denoted as D4 represented visually as four couterclockwise rotations of a square:



And the following four reflections, vertical, horizontal, and two diagonal reflections:




With each image is included the permutation, actually dihedral groups are permutation groups and D4 is a set of 8 permutations, hence the order of the group is 8. It is a subgroup of the group of all permutations of four items which is known as the Symmetric Group which has order 4!=24, it's denoted as S4. The interesting thing here is the rotations form a subgroup that is isomorphic to our group from above and Z4. In a sense this isn't really surprising since it is a cyclic group of order four meaning it cycles through 4 items just as a square cycles through four rotations.


As you can see from the color coding, the elements {R0, R1, R2, R3} form a subgroup, a subgroup is just a subset of the elements that is still a group. These subgroup elements forming the upper left hand corer of the table are color coded to show the isomorphism between this subgroup and Z4 and also our group (⋅, {1,-1,i,-i}). Also R0 is the identity which makes sense since it is a zero rotation, which means that you didn't rotate it, or you did by 360° aka one tau.


Our Z4 isomorphic group (⋅, {1,-1,i,-i}) also has a subgroup. Our original arrangement of the cayley table was ordered to show the Z4 isomorphism. To show our subgroup we need to rearrange the cayley table:


1 -1 i -i
1 1 -1 i -i
-1 -1 1 -i i
i i -i -1 1
-i -i i 1 -1

Now it should be fairly easy to the subgroup (⋅, {1,-1}) again forming the upper left corner in the table above, or shown by itself:


1 -1
1 1 -1
-1 -1 1

Now if you think about it our subgroup which is just another group is a group, 1 is the identity and -1 is its own inverse, actually it turns out that all subgroups of cyclic groups are also cyclic groups and since all cyclic groups are isomorphic to Zn groups, this group is actually one that we have seen before it's just Z2 addition aka exclusive-or, etc.

Also there are some remarkable connections to number theory in regards to the order of subgroups and the order of elements, for example the order of our subgroup is 2 which evenly divides 4 the order of the group, the order of a subgroup will always evenly divide the order of the group. Also the order of each element evenly divides the order of the group. I suspect that these ideas have profound implications.


Going back to our original group there are a couple of interesting things about imaginary numbers, first are the following equations:





If we consider the sequence of raising i to successive powers, multiplying by I each time, if we start with 1, we get the sequence (1, i, -1, -i), these are actually coordinates in the complex plane and can be written as (0i+1, 1i+0, 0i-1, -1i+0). This cycle (increasing powers of i) is the following (counter clockwise) rotation in the complex plane:



Conversely if we divide, or repeatedly multiply by -i, we get the following sequence (1,-i,-1,i) which correspond to the complex numbers (0i+1, -1i+0, 0i-1, 1i+0) and is the opposite (clockwise) rotation:



Another interesting seemingly related concept is the idea of turning number or winding number of a curve, the red circle with clockwise rotation corresponds to curve with a winding number of -1 and the blue curve with positive increasing powers of i has a winding number of 1.


As we saw our group is cyclic and isomorphic to Z4 and isomorphic to the rotation subgroup of the dihedral group D4 and both of the generators of our group correspond to rotation in the complex plane. Counterclockwise rotation corresponds to the period of i and clockwise rotation corresponds to the period of -i.

25 March 2012

More Thoughts on Formal Approaches to Naming in Software

On the Importance of Naming in Software Systems, Part II


In my last post on naming I surveyed and attempted to categorize the conventional wisdom in regards to naming. Here I will expand on some of my ideas and extend my naming domain vocabulary.


A software system is composed of many things and most of them if not all have names.  In order to talk about this I realized that I need a term to describe the things that have names, Steve McConnell makes the comment "a variable and a variable’s name are essentially the same thing".  While this is effectively true, named things in a system have different types, uses, etc.  In trying to come up with a name for these named things, I felt that I could do better than the phrase "named things". For the word "things" I contemplated item, object, entity, artifact, and more. These all had various connotations and possible contexts which confused the meaning. I turned to linguistics for the answer, and found the following on Wikipedia under intension, the bolding is mine:


The meaning of a word can be thought of as the bond between the idea or thing the word refers to and the word itself. Swiss linguist Ferdinand de Saussure contrasts three concepts:



So the word referent seems to be a good choice as it probably has no context with relation to software engineering.  To take this further, I will use the expression Named System Referent or possibly just System Referent to refer to those things in a software system that have a name.  To be clear here a name is what is referred to above as a signifier but I will just use name.  A System Referent is the thing (referent) in the Software System that the name refers to.  If this is confusing hopefully some examples will help.  Some System Referents include but are not limited to the following1:

  • Classes
  • Variables (local, instance, static)
  • Methods
  • Method Parameters
  • Packages
  • Database Tables, Columns, Triggers, Stored Procedures, etc.
  • HTML Files, CSS Files, Javascript Files, Config Files, all files
  • Directories
  • Urls
  • Documents
  • XML Elements and Attributes
  • CSS Classes

And the list goes on.


Another observation we can make is that System Referents can have a context or a grouping, for example System Referents which include classes, packages, variables, methods, etc. may have different conventions from other System Referent groupings such as database System Referents.


Now that we have a way to talk about named items, we can explore the very important idea of naming conventions.  The name of a System Referent often consists of several components, from a linguistic stand point these components are similar to, but not the same as a lexical unit or a morpheme, for this I am choosing the term Name Unit, for example an identifier "personId" consists of two Name Units, "person" and "id". Name units imply a separator mechanism. In this example the use of CamelCase, another example is "person_id" where the name units are separated by the separator "_".  So a name unit is that atomic piece of a name that is separated by a separator and a separator is either explicit e.g. "_" or implied e.g. CamelCase. In my previous post we looked at different prefix and suffix qualifiers, this is a generalization of the qualifier concept which deals with the whole name and not just one part of it.


I wish to compare, from the structural perspective, two common conventions one for the Java System Referent grouping and that of an SQL Database grouping.  For the Java Naming convention we will assume the standard Java naming convention.  For the database we will limit ourselves to Tables and Columns and assume uppercase Names, name units that consist only of upper case characters, the separator will be an underscore "_".


We can define formal a more formal approach to the lexical structure of a naming convention using a BNF, or in this case my own variant extended BNF, for example our BNF for variable names in Java might look like the following:


name-unit-terminal ::= [A-Z]+[a-zA-Z0-9]*

name-unit-prefix-terminal ::= [a-z]+[a-zA-Z0-9]*

<name> ::=  name-unit-prefix-terminal | name-unit-prefix-terminal <name-unit>

<name-unit> ::= name-unit-terminal | name-unit-terminal <name-unit>


The Naming convention for our database column names and table names:


name-unit-terminal ::= [A-Z]+[A-Z0-9]*

<name> ::=  name-unit-terminal | name-unit-terminal "_" <name>


Two Concrete examples illuminating these are as follows:


public class Person {

private Long id;

private String lastName;

private String firstName;

private String middle;

private String phone;

private String email;

public Long getId() {

return id;

}

public void setId(Long value) {

id = value;

}

public String getLastName() {

return lastName;

}

public void setLastName(String value) {

lastName = value;

}

public String getFirstName() {

return firstName;

}

public void setFirstName(String value) {

firstName = value;

}

public String getMiddle() {

return middle;

}

public void setMiddle(String value) {

middle = value;

}

public String getPhone() {

return phone;

}

public void setPhone(String value) {

phone = value;

}

public String getEmail() {

return email;

}

public void setEmail(String email) {

this.email = email;

}

}


 


CREATE TABLE PERSON (

ID INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,

LAST_NAME VARCHAR(40) NULL,

FIRST_NAME VARCHAR(20) NULL,

MIDDLE VARCHAR(20) NULL,

PHONE VARCHAR(20) NULL,

EMAIL VARCHAR(256) NOT NULL

);


Naming Conventions consist of both a Lexical Component and a Semantic Component. In this post we have focused on the lexical aspects of naming, from the intension definition above we focused on the signifier and the referent. To really create a comprehensive approach the Semantic aspect cannot be ignored. In the intension definition above this can be viewed as focusing on the signified and the referent. This is an area that is explored in the idea of the Ubiquitous Language within the realm of  Domain Driven Design.


The Semantic Elements of a system and of a naming convention are more complex and ambiguous. I do think that software systems should have a System Lexicon which would be a more concrete formalization and extension of the System’s Vocabulary or Ubiquitous Language this would also incorporate ideas encapsulated in a Data Dictionary.  A System Lexicon would be an entity of some complexity and would require some commitment to build also applying it could be problematic and might require tooling such as an IDE interactive name suggestion feature or a static analysis component or both. It might even require an ontology or taxonomy oriented graphical tool for constructing and maintaining the System Lexicon depending on the size and complexity of the system.  I will get into some ideas that extend the lexical aspects and move into the Semantic aspects in future posts.  I know that this might seem pretty grandiose but I think this powerful stuff that could lead to better approaches to create higher quality software.


1This list is biased to Java Web development, but these ideas should be general enough to span any software system.

19 March 2012

A Survey of the Conventional Wisdom on Software Naming

On the Importance of Naming in Software Systems, Part I





Naming is a very important aspect of software, however, its importance and relevance to building quality software is often overlooked or ignored all together.  I feel that naming needs to be part of a larger more formal framework for building software.  In previous posts I have advocated a framework approach to capturing reuse and standardizing software design and implementation and I feel that naming is a crucial part of such an approach. Previously I included the following quote about naming in an API design talk by Joshua Bloch:


Names matter a lot, there are some people that think that names don’t matter and when you sit down and say well this isn’t named right, they say don’t waste your time let’s just move on, it’s good enough. No! Names, in an API, that are going to be used by anyone else that includes yourself in a few months mater an awful lot. The idea is that every API is kind of a little language and people who are going to use your API needs to learn that language and then speak in that language and that means that names should be self explanatory, you should avoid cryptic abbreviations so the original Unix names, I think, fail this one miserably.

He is not the only prominent software engineer to advocate an attention to naming, in this post I will summarize and discuss several sources.  I will start with his material which is part of his talk on API design which I summarized in my previous post.  Actually I feel that most if not all of what he says on API design is applicable to software in general including what he has to say on naming. The summary points are as follows:


Names should be self explanatory.

Avoid cryptic abbreviations.

Don’t have multiple words meaning that same thing.

Names should be consistent – same word means same thing.

Be regular–strive for symmetry. This implies a larger context of naming and a relationship between concepts.

Code should read like prose. (As a result of good API design)


Chapter two titled "Meaningful Names" of Robert Martin’s Clean Code, written by Tim Ottinger, is dedicated to naming. A summary of the advice is as follows:


Use Intention Revealing names

Avoid Disinformation – This is a corollary to Use Intention Revealing names. This means that the components of the name actually conceptually match the intent.

Make Meaningful Distinctions – This means Pick One Word per Concept.

Use Pronounceable Names. This means Avoid cryptic abbreviations.

Use Searchable Names. This is mainly about not using single character names and magic constants.

Avoid Encodings. This means do not use suffixes or prefixes to encode type or status as a member "m_".  He also discourages using "I" as a prefix to an interface. This includes avoiding Hungarian Notation.

Avoid Mental Mapping. This is an anti pattern. It is a corollary to Use Intention Revealing Names.

Class Names should consist of nouns of verb Phrases.

Method Names should consist of verbs or verb Phrases.

Pick One Word per Concept. 

Use Solution Domain Names. Solution domain names refer to things like design patterns or more distinct concepts such as Queue or Binary Tree

Use Problem Domain Names – This is pretty straight forward, if your system processes medical records, you might expect a class called MedicalRecord.

Add Meaningful Context – This deals with the idea of adding suffixes or prefixes to denote additional context information in the name.  The example given is use addrState vs. state.

Don’t Add Gratuitous Context – This talks about the idea of adding unnecessary or too specific suffixes or prefixes to denote context.

Choosing good names requires good descriptive Skills and Shared cultural background


Steve McConnell’s Code Complete contains the following advice1:


A name should fully and accurately describe what the variable represents.

A good mnemonic name generally speaks to the problem rather than the solution. A good name tends to express the what more than the how. In general, if a name refers to some aspect of computing rather than to the problem, it's a how rather than a what. Avoid such a name in favor of a name that refers to the problem itself.

Use pronounceable names.

Avoid misleading names or abbreviations and use consistent abbreviations.

Avoid names that are misleading.

Avoid names with similar meanings.

Avoid variables with different meanings but similar names

Name Specific Types of Data using Standardized Prefixes – Use prefixes to denote (encode) type such as Hungarian Notation.

Use computed-value qualifiers if needed at the end of the name. Examples are: Total, Sum, Average, Max, Min, Record, String, or Pointer.

Use a Naming Convention and that naming convention should be compatible standard conventions for the language.   Naming convention should distinguish among local, class, and global data.  Naming convention should distinguish among type names, named constants, enumerated types, and ­variables.

Good variable names are a key element of program readability. Specific kinds of variables such as loop indexes and status variables require specific considerations.

Names should be as specific as possible. Names that are vague enough or general enough to be used for more than one purpose are usually bad names.

Naming conventions distinguish among local, class, and global data. They distinguish among type names, named constants, enumerated types, and variables.

Abbreviations are rarely needed with modern programming languages. If you do use abbreviations, keep track of abbreviations in a project dictionary or use the standardized prefixes approach.



I did reword some of these to make them more stand alone. You may want to pursue the sources to gain a fuller picture of each author’s perspective.  The interesting thing here is while there are several key common themes to these approaches there are some very explicit contradictions. For example Clean Code recommends against Type encoding like Hungarian Notation while Code Complete recommends it.  Conversely Code Complete seems to implicitly recommend against using Solution Domain Names "speaks to the problem rather than the solution" whereas Clean Code advocates their use.

I feel that when talking about naming it is easy to conflate ideas pertaining to structural (lexical) concerns and ideas pertaining to domain (semantic) concerns.  Unfortunately while these ideas are separate they are also intertwined and an intelligent approach to naming needs to recognize this.  

One structural theme is the idea of qualifiers, which Code Complete explicitly names, but the idea appears implicitly in Clean Code as well.  Qualifiers in this context are generally prefixes and suffixes that qualify the name. Qualifiers mentioned above include scope qualifiers which denote the scope of a variable such as the prefixes "m_" for member or "global_" for global. Hungarian Notation in this context2 is an example of a type qualifier. Additionally Code Complete defines computed-value qualifier suffixes to denote values which are computed values these include: Total, Sum, Average, Max, Min, Record, String, or Pointer.  Interestingly qualifiers are a structural element of a name which denotes additional specific types of semantic meaning to the name. The structural and semantic construction of names is a topic I intend to continue exploring in subsequent posts.

The previous ideas address both structural (lexical) and domain (semantic) concerns now I wish to look at a targeted summary of more semantic oriented conceptual advice in Eric Evan’s Domain Driven Design:


Domain model terms are part the UBIQUITOUS LANGUAGE.

In regards to an INTENTION-REVEALING INTERFACE, name classes and operations to describe their effect and purpose without reference to the means by which they do what they promise. This relieves the client developer of the need to understand the internals. These names should conform to the UBIQUITOUS LANGUAGE so that team members can quickly infer their meaning.

In regards to MODULES aka Packages, If your model is telling a story your MODULES are chapters. The name of the MODULE conveys its meaning.  These names enter the UBIQUITOUS LANGUAGE.

Name each BOUNDED CONTEXT and make the names part of the UBIQUITOUS LANGUAGE.


In Domain Driven Design the idea of conceptually developing and implementing the Domain iteratively is explored.  This book reveals many approaches and concepts pertaining to that topic, the ideas that I am interested in which are targeted in the quotes above pertain to naming.  A common theme in naming which would be hard to dispute is to Use Problem Domain Names. The idea of a UBIQUITOUS LANGUAGE is promoted in the book as a way to help define the domain so that all stakeholders have a common way to talk about the domain and its representation in the resulting software.  Domain Driven Design promotes using the UBIQUITOUS LANGUAGE as a theme to defining the system and unifying the system documentation.  To me a UBIQUITOUS LANGUAGE implies the need to track, define and attempt to codify it over time which I think implies a more formal way to document it like a lexicon is needed, an idea I will follow up on more in a future post.

Another issue with talking about software naming is the idea of context.  Names pretty much always exist in a context, in Java a variable can be in the context of a method or a class. Both methods and classes themselves can exist in the context of classes and classes exist in the context of classes and packages and packages are themselves hierarchical. In fact software systems have developed the concept of Namespace to in part deal with this problem.  

Each name exists in a context, and in order to talk about naming we need a language just as you need to define a language for a domain. Actually naming is a domain, a meta-domain perhaps, a domain that describes other domains.  This means we need a "UBIQUITOUS LANGUAGE" for the domain of naming. So in that language I am going to define name scope context to define to context or "hierarchical place" in which a name occurs. I am purposefully not using namespace since that has other explicit meanings.  I know using the words scope and context seem redundant but I felt using "scope" alone didn’t work because it has a specific meaning and context by itself was too vague, using name scope context can refer to a broader set of circumstances such as an attribute’s position in an xml document relative to its parent element or a SQL Column name relative to its parent table, a file’s directory and so on.

An interesting thing I have noticed about name scope context is that it can be redundant.  For example let’s assume that we have an object named a database table named PERSON and a corresponding object named Person.  I have seen the following approach to naming these:


CREATE TABLE PERSON (

    PERSON_ID INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,

    LAST_NAME VARCHAR(40) NULL,

    FIRST_NAME VARCHAR(20) NULL,

    MIDDLE VARCHAR(20) NULL,

    PHONE VARCHAR(20) NULL,

    EMAIL VARCHAR(256) NOT NULL,

    DELETED CHAR(1) NOT NULL DEFAULT 'N',

    CREATE_DATE TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,

    MODIFY_DATE TIMESTAMP NULL

)


 


class Person {

    private int personId;

    private String lastName;

    private String firstName;

    private String middle;

    private String phone;

    private String email;

    private boolean deleted;

    private Date createDate;

    private Date modifyDate;

...


Now in these examples the database table PERSON contains the column named PERSON_ID and the class Person contains the corresponding field named personId.  In both of these cases ID or id respectively would be probably be better as the use of person is repeating the name used within the name scope context of the member variable.  The down side of this type of non-duplication is the loss of the ability to search for the names, which I think implies that software name search probably needs more sophisticated mechanisms over that of simple text searching, another idea I will expand on in the future.

This is my first post on naming, I have three more planned and I will get into more ideas some of which come from linguistics. I feel that Domain Driven Design gets into a number of linguistic and linguistic oriented concepts, maybe what we are going for here is Semantic Driven Design, but that would be just another YADD.


1 Code Complete provides a lot of ideas here are few more:


The name should long enough that you don't have to puzzle it out.

Avoid misspelled words in names.

Avoid words that are commonly misspelled.

Don't differentiate variable names solely by capitalization.

Creating Short Names That Are Readable. These are guidelines for shortening names when you need to, so this is a special case not a general one.  I know I have run into this with Oracle 11g’s 30 Char limit.

Avoid unnecessary abbreviations.

Avoid multiple natural languages.

Avoid names that could be misread or mispronounced.

Avoid names that are different by only one or two characters.

Avoid names that sound similar.

Avoid names that conflict with standard library routine names or with predefined variable names.

Format names for readability.

Avoid excessively long names.

Code is read far more times than it is written. Be sure that the names you choose favor read-time convenience over write-time convenience.


2 This use of Hungarian notation is apparently not how it was intended to be used see "Making Wrong Code Look Wrong".



11 March 2012

Are you sure that you are editing in two dimensions?


Editing the Positive Orthant and The Topology of Text Editing





In my previous post on editing I mentioned column cutting and pasting, a powerful feature that many programmers I have worked with don’t use or even know about.  I started thinking about it in terms of math and seemed to me that this creates a dimensional difference between the standard Eclipse Editor and the editor that I use.  My observation is that the standard Eclipse Editor only lets you edit in one dimension, of course such a statement might seem absurd but I think it’s true and to explain it I am going to take a little tour of the concept of dimension.


From what I understand the idea of Dimension is not completely cut and dry and comes in a variety of forms, most people only know of or think of Spatial Dimension of the Cartesian Coordinate System in Euclidean Space for example the screen on which your editor is displayed.  But dimension both comes in many other flavors and allows the representation of so many things.  For example Dimensions can be in the form of Fractal Dimension, Hausdorff Dimension, Topological aka Lebesgue Covering Dimension, and the list goes on.


Another deceptive property of Dimension comes from the topological concept of surfaces or more generally Manifolds.  An interesting example of this is the older video game Asteroids or any game where you move from the bottom edge to reappear on the top edge of the screen or from top to bottom of the screen, the same applies to the left to right wrapping motion.  You are actually moving as shown above around on the surface of a torus along the two different axes shown in red and blue.  This idea can extend to higher dimensions, imagine, instead of a square video game screen, a cube where each face was connected to the opposite face (3 connections), if you moved in any direction, in three dimensions, far enough you would always end up at the same place, actually the universe could have this shape, I am not saying that it does though, interestingly there is a three dimensional version of asteroids.  This cube torus is known as a 3-torus which is one many 3 manifolds (three dimensional manifolds). Manifolds are a higher dimensional topological generalization of surfaces like spheres and tori.  In the case of the torus and 3-torus, you need to step up to a higher dimension to really see the structure that you are in.



Ok so some of these ideas may seem a little broad and not necessarily directly relevant but they really are and they are interesting and give a larger picture of the complexity of the idea of dimension so bear with me.  The next important and hopefully more obviously relevant idea is the concept of an Orthant or n-hyperoctant, these are just fancy and more general terms for a concept you probably already know.  An Orthant is the division of space around the origin, so in two dimensions there are four orthants also known as Quadrants or 2-hyperoctants.   The simplest case is two rays forming two 1-dimensional orthants, one positive and one negative.  The number of orthants grows by powers of 2, i.e. 2n, so one dimension (line) has 21= 2, two dimensions (plane) has 22= 4, three (space): 23= 8 and so on.  Each orthant has all combinations of positive and negative coordinates a set that will be of size 2n, so one dimension has {(+),(-)}, two dimensions has {(+,+),(-,+),(+,-),(-,-)},  and so on,  each dimension will have exactly one orthant that has only positive coordinates and exactly one orthant that has only negative coordinates.



The orthant concept is very relevant to text editing, when you edit you are working in a two dimensional Euclidean space, and you are working in the Positive Quadrant (Orthant).  When you edit, you start with line one, column one and count up to the right and down, this is actually a reflection around the x-axis of the traditional plane with the positive y to the left or counter clockwise from the x axis which is the way one usually represents a Cartesian plane.  Also we are working strictly with positive non-zero integer positions so our space is (n,n) ∈ (N x N)  n ∈ N > 0 the positive quadrant of the two dimensional integer plane.



At this point, if you are still with me, you might be saying: “Aha, you just demonstrated that editing is two dimensional”, but I’m not done yet and I want to take a small digression into Fractal Geometry first. The Koch or Snowflake curve shown above has a Fractal Dimension of log(4)/log(3) =log34= 1.2619.  But its Topological Dimension is 1 since it is a one dimensional continuous everywhere but differentiable nowhere curve.   In Topology you can stretch and bend things so imagine the curve is made of string and you pick it up and it loses its shape. You can then lay it down as a circle which is a one dimensional curve, a 1-torus.


The Koch Curve can be created using a Fractal L-System. The important thing to realize here is that Fractal L-Systems have a strong similarity to the Chomsky Hierarchy, now there are some substantial differences between the two rewriting systems, but I will focus only on one of the similarities here. The Koch Curve can be defined by the following L-System:


Alphabet : F

Constants : +, −

Axiom : F++F++F

Production rules:

F → F−F++F−F


Here, F means "draw forward", + means "turn right 60°", and − means "turn left 60°" (see turtle graphics).


The first four iterations, which correspond to the images above are:


F++F++F

F-F++F-F++F-F++F-F++F-F++F-F

F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F

F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F-F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F-F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F-F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F-F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F-F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F-F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F

Each iteration results in a new longer more complex one [topological] dimensional strand of characters.  The striking similarity here is that much as an L-System will give you a one dimensional strand of characters a Context Free Grammar which will describe most programming languages will give you a similar one dimensional “strand” of terminal symbols which would be lexemes corresponding to a linear sequence of programming language statements.


In the asteroids example we are looking at two dimensional screen that is really a two dimensional surface on a three dimensional torus, here we are looking at one dimensional strand represented on a two dimensional screen and this is the key observation that ties all of this together and shows the nuances of these ideas.  One dimensional editing is when you are editing on the positive ray, 1-hyperoctant, cursor movement follows the strand in one dimension, in both directions along the strand, and cutting will cut one dimensional strands and only allow them to and pasted into any single position within the strand.  The default behavior of the Eclipse editor offers one dimensional editing. Now let’s compare these specific operations to another editor which allows two dimensional movement and cutting and pasting.


Cursor Movement


The first example shows the how the cursor behaves at the end of the line in Eclipse. In the following image the cursor is at the end of line 21, which is a coordinate of (21,37) as shown at the bottom of the image:


Hitting the right arrow to move cursor right by one, moves you to the beginning of the next line, coordinate (22,1) as shown below:


This movement is along the one dimensional stand of the code itself, not the plane.  The confusing thing here is that we are looking at the text in two dimensions and using two dimensional coordinates to describe it, the next example will make it clearer.  Here is the same image from a different editor that supports two dimensional operations:


 

This example shows two dimensional cursor behavior at the end of line 21, which is a coordinate of (21,37) as shown at the bottom of the image, hitting the right arrow to move cursor right by one, moves you right by one position to coordinate (21,38) as shown above.


Cutting and Pasting



The one dimensional line cut:


Two dimensional cutting and pasting:



In both cases above we are selecting blocks of text with starting coordinate (21,12) to ending coordinate (26,18) however the Eclipse version (top) only allows the selection of a one dimensional strand of text, as you move in either direction you will only be able to grab complete lines between the start and end coordinates and if you paste this text you will be inserting a one dimensional strand into a single position in another one dimensional strand.  The two dimensional operation offers more flexibility beyond the only the one dimensional operation, actually the editor offers both one and two dimensional cutting, which is what you really want in an editor.  The resulting cuts are as follows, now admittedly the two dimensional cut in this case is not really practical.


The two dimensional column cut:



Hopefully this give a sense of the difference from editing on a one dimensional ray vs. a two dimensional plane.


If we revisit the one dimensional strand of characters idea, we notice a problem.  While the strand is one dimensional in that the position of each character can be given by a single integer index into the string, which is a single axis or ray.  Each position can have a different value. In our fractal each position could contain one of three characters {F,+,-} which we could map to {0,1,2} respectively.  Now each iteration of the L-System production generates a number in base three and each position can have one of three “pixels” in the strand. Now we need another dimension, or at least part of one, to represent this additional information.  A more practical example would be a 24 bit RGB image where each pixel has a position, remember this can be stored as a single one dimensional strand of pixels but displayed in two dimensions by cutting up the strand into rows.  Similarly a program can be “pixilated” where each pixel could be an ascii character (byte), a lexical token or lexeme, or a binary zero or one bit along the one dimensional strand.  The length of the strand would vary in accordance to height of the pixels a binary pixel representation/strand would have more positions than an ascii pixel representation/strand than would the lexeme pixel representation/strand.


Ok this is probably my zaniest post about my crazy ideas which I am pretty sure are correct. Hopefully I did a decent job explaining these ideas, I find them to be quite mind blowing, at least that's the way I felt when I first understood the basic ideas about topology and manifolds, and there is still so much I don't know. Also if you feel that you both have a better understanding of some of these ideas and at the same time feel more confused about them, I think that might be normal and I think a big part of learning math is just getting used to feeling that way all of the time, because the more you learn the stronger both of these feelings become, at least that's my experience.


An n-torus can mean either an n-dimensional torus or a two dimensional toriodal surface with n holes. In this post it always means n-dimensional torus.

05 March 2012

The Software Design Debate and the Futility of Opinion


A Tale of Two Classes






A while back when I was at a previous contract this article showed up on various link sites and one of the architects at that company sent it out. As a result, another developer and I, with the help of a googled code snippet, came up with the following code and added it to the common library:


public class ServiceResponse <ERROR extends ErrorReturn,


VALUE extends ValueReturn> {


private ServiceResponse() {


}


public ERROR error() {


return null;


}


public VALUE value() {


return null;


}


public final static class Error<ERROR extends ErrorReturn>


extends ServiceResponse<ERROR, ValueReturn> {


private final ERROR error;


public Error(ERROR error) {


this.error = error;


}


public ERROR error() {


return error;


}


public boolean isError() {


return true;


}


}


public final static class Value<VALUE extends ValueReturn>


extends ServiceResponse<ErrorReturn, VALUE> {


private final VALUE value;


public Value(VALUE value) {


this.value = value;


}


public VALUE value() {


return value;


}


public boolean isError() {


return false;


}


}


}


To be fair the original code was not documented, like this snippet, and there were a few other things that were a little less elegant but not hugely so, also all code here has been changed as not to infringe on intellectual property and to ensure anonymity.  As a result of the architecture and project schedule the other developer who needed the class ended not using it and also due to the aggressive project schedule there was no other follow up such as finishing the documentation or writing tests, this was partially my fault.


A few months later the architect needed this class and discovered our implementation he rewrote it as follows:


public class ServiceResponse<ERROR extends ErrorReturn,


VALUE extends ValueReturn> {


private ERROR error;


private VALUE value;


private boolean isError;


public ServiceResponse(ERROR error, VALUE value,


boolean isError) {


this.value = value;


this.error = error;


this.isError = isError;


}


public ERROR error() {


return this.error;


}


public VALUE value() {


return this.value;


}


public boolean isError() {


return isError;


}


}


Upon committing it he sent out an email to announce that he felt the original code was too complicated and he had simplified it to the above code.  I responded explaining that I felt that there were some issues with the instantiation of his new implementation and the real issue here was the lack of documentation.  I was shocked by his response in which he stuck to his argument that the new class was simpler to implement and didn’t require a lot of thought and we just need a wrapper class.  I confess I was initially perturbed by this as I felt that he was both wrong and taking a cargo cult attitude which was atypical for him, I later found out that he had been suffering through a bad cold.  Since I knew I would soon be leaving the project, I left it there even though I was pretty sure that his new design was significantly worse than the original.   I am intentionally omitting the details of the debate because I want to explore these in more detail momentarily. 


Throughout my career I have all too often found myself in these types of debates, and the thing I find so frustrating about it is the lack of real ways to accurately analyze these types of situations and the lack of any formal structure to the arguments themselves, they frequently become as constructive as a political or religious debate.  So it got me thinking, these are two pretty simple classes, how can we constructively analyze this situation and perhaps establish dispassionately and objectively which solution is better and what opportunities can this exploration present in a larger context?


First let’s look at the problem in the context of the current prominent thinking, let’s start with Joshua Bloch’s API ideas, which I have and will continue to reference.  Now remember the class in question is part of an API so these points are very relevant.  One point he makes is that an API:


  • Easy to use, even without documentation
  • Hard to misuse

So let’s assume that we have the following two classes and references:


ErrorReturn error;


ValueReturn value;


The original design has the two correct ways of creating it, omitting for the moment creating each with null:


new ServiceResponse.Error<ErrorReturn>(error);


new ServiceResponse.Value<ValueReturn>(value);


The new design has the following correct instantiations:


new ServiceResponse<ErrorReturn, ValueReturn>(error, null, false);


new ServiceResponse<ErrorReturn, ValueReturn>(null, value, true);


Also it is pretty obvious that the new design opens up several other ways that this object can be created.  It seems that new design more easily allows value and error to be mixed up.  The new design puts the responsibility of setting the Boolean isError on the user which opens it up to possibly being set incorrectly.  This breaks the hard to misuse rule.  In the old design it is an artificial value that created by a pure function.   So from the API design perspective it seems that the original design is better. 


Now another piece of conventional wisdom is the minimizing the number of parameters, in Clean Code Bob Martin talks about how you really shouldn’t have more than three parameters, well both instantiations fall under that, but by this logic is not the old design with one parameter then preferable to the new design with three? 


Another possible pro argument for the original design is the use of the "Disjoint Union" Either pattern, now this is not a GOF pattern but it is a pattern, perhaps an even more mathematical pattern, but regardless it is a specific pattern with precedence.


So that’s three pro arguments for the original design based on the current conventional software design wisdom promulgated by the leading software engineers of the field. So the original design is probably better.  Unfortunately I have found that even these arguments can be thwarted by the most recalcitrant cargo cult coder who doesn’t read and will always invoke arguments like "it’s too complex, it’s too abstract".


So I started to think, how could one look at this situation more analytically?  Going back to Joshua Blocks API talk, at some point and I don’t have this documented anywhere, he makes reference to an object’s state space, but he doesn’t go into detail about the concept.  This got me thinking, in this case we could pretty easily enumerate, at least at high level, the state space for each object and then compare them.  I am not sure if this is a known technique, I wouldn’t be surprised if someone has thought of or done this before.  In this case I am going to refer to this as "Enumerative Object State Space Analysis" or just "Object State Space Analysis" for lack of a better name.


So for this exercise we will interest ourselves in the possible values of a value or null for each parameter, where the error value is an instance of ErrorReturn and the value parameter is an instance of ValueReturn or true or false for the Boolean parameters, this is the following sets: {<Error>, null}, {<Value>, null}, and {true, false}. 


For the old design the possible instantiations are:


new ServiceResponse.Error<ErrorReturn>(error);


new ServiceResponse.Value<ValueReturn>(value);


new ServiceResponse.Error<ErrorReturn>(null);


new ServiceResponse.Value<ValueReturn>(null);


There are 2 possible Error instantiations and 2 possible Value instantiations leading to an object state space of 2 + 2 = 4 possible states, this is an application of the Sum Rule.  The new class has 2 possible values per constructor parameter, similarly from the Product Rule of combinatorics we can calculate that this leads to 2*2*2 = 8 possible states in the object state space.


We can enumerate (list them out) the states for the original class as follows:


Object State Comment Correctness Status

{Value, false} Return state for successful operation Correct intended state

{Error, true} Return state for operation with an error. Correct intended state
{null, false} Return for a successful operation with no return value State is a side effect of design, allows null, could be correct or could be considered a degenerate state.
{null, true} Return for an operation with an error with no information State is a side effect of design, allows null, could be correct or could be considered a degenerate state.

We can enumerate the states for the new class as follows:


Object State Comment Correctness Status
{null, Value, false} Return state for successful operation Correct intended state
{Error, null, true} Return state for operation with an error. Correct intended state
{null, null, false} Return for a successful operation with no return value State is a side effect of design, allows null, could be correct or could be considered a degenerate state.

{null, null, true} Return for an operation with an error with no information State is a side effect of design, allows null, could be correct or could be considered a degenerate state.
{Error, Value, false} Return state for successful operation State is correct from a usage standpoint but ambiguous from a programmer maintenance standpoint is this what was intended or is it reversed?
{Error, Value, true} Return state for operation with an error. State is correct from a usage standpoint but ambiguous from a programmer maintenance standpoint is this what was intended or is it reversed?

{null, Value, true} Incorrect Usage This is incorrect but the design allows this state to exist.
{Error, null, false} Incorrect Usage This is incorrect but the design allows this state to exist.


Assuming a uniform distribution the probability for each state in the original class is 25% and 12.5% in the new class, this means that the first design has 50% correct states and 50% null states.  The new design has 25% correct states, 25% null states, 25% ambiguous states, and 25% incorrect states. Of course a uniform distribution would probably not be the case as the correct usage would always be more likely and the incorrect usage would be the most unlikely.  Still, based on this analysis I am inclined to further conclude that the original design is better, perhaps even definitively so as the old design has no incorrect states and the expanded state space, which is twice as large, exponentially larger, also increases the complexity. 


Another possibility would be to eliminate the setting of the Boolean flag on the new design and allow it to be determined by a pure function as in the original design, but that opens up problems with respect to the ambiguous states that would exist.  In reflecting I also realized that the one of ambiguous states of the new design allow a state {Error, Value, false} which might be construed as success with information, which leads me to think that both designs are lacking and it might be better to always return an object that contains the value and some type of status object that allows error or success with info.


Now I know this is a lot and I am probably over thinking this, but I am treating this as an experiment:  Is it possible to come up with more analytical approaches using Enumerative and Combinatorial techniques to guide object design or other aspects of software design in a practical way?