Elegant Coding

Programming and Order Theory

Data Science DC: Implicit Sentiment Mining in Twitter Streams

The Math of the First Scala Assignment

The Ubiquitous Patterns of Pascal’s Triangle

Lattice Theory for Programmers and Non Computer Scientists

Why You Can’t Have a Real Software Engineering Discipline

A Framework for Software System Naming

Renaissance 2.0

The Math of Search and Similarity

Software System Morphology

What is Generic Programming?

The Coding Buzz

Amazing Abstract Algebra: Groups and Rotations

More Thoughts on Formal Approaches to Naming in Software

A Survey of the Conventional Wisdom on Software Naming

Are you sure that you are editing in two dimensions?

The Software Design Debate and the Futility of Opinion

Fibonacci: The Math of Agile

Is your Team LCD (Lowest Common Denominator)?

The Software Reuse Complexity Curve

Abstract Algebra: The Logic of Odd and Even

Real Software Engineering: The Good, The Bad, and The Ugly

Metaphorically Thinking about Software Engineering

Responding to "Eleven Equations" Comments, Math Notation, and More

Eleven Equations True Computer Science Geeks Should (at Least Pretend to) Know

Elegant Coding

Programming and Order Theory

Data Science DC: Implicit Sentiment Mining in Twitter Streams

The Math of the First Scala Assignment

The Ubiquitous Patterns of Pascal’s Triangle

Lattice Theory for Programmers and Non Computer Scientists

Why You Can’t Have a Real Software Engineering Discipline

A Framework for Software System Naming

Renaissance 2.0

The Math of Search and Similarity

Software System Morphology

What is Generic Programming?

The Coding Buzz

Amazing Abstract Algebra: Groups and Rotations

More Thoughts on Formal Approaches to Naming in Software

A Survey of the Conventional Wisdom on Software Naming

Summary and more

References

Math and Scala with a Little Bit of Clojure

Part One: Mathematical Foundations

On the Importance of Naming in Software Systems part IV

Part one: Lucene, The Boolean Model, tf*idf, and the Vector Space Model

Tokenizing Text

The Boolean Model

tfidf Weighting (Term FrequencyInverse Document Frequency)

On the Importance of Naming in Software Systems, part III

On the Importance of Naming in Software Systems, Part II

On the Importance of Naming in Software Systems, Part I

A Tale of Two Classes

Deconstructing Glenn VanderBurg’s "Real Software Engineering"

Binomial Coefficient

Demorgan’s Laws

Eigenvector and Eigenvalue

Pumping Lemma for Regular Languages

Information Entropy

Bayes' Theorem

Fermat’s Little Theorem

Natural Join

The Fixed-Point (Y) Combinator

O(n)

Euler’s Identity

Summary and more

References

Math and Scala with a Little Bit of Clojure

Part One: Mathematical Foundations

On the Importance of Naming in Software Systems part IV

Part one: Lucene, The Boolean Model, tf*idf, and the Vector Space Model

Tokenizing Text

The Boolean Model

tf*idf Weighting (Term Frequency*Inverse Document Frequency)

On the Importance of Naming in Software Systems, part III

On the Importance of Naming in Software Systems, Part II

On the Importance of Naming in Software Systems, Part I

tfidf Weighting (Term FrequencyInverse Document Frequency)

Covariance, Contravariance and Order Theory

Defining Covariance and Contravariance

Covariance and Contravariance as Order Duals

Types as Sets of Fields

Types as Sets of Fields in the Real World

Exercise 1: Pascal’s Triangle

Exercise 2: Parentheses Balancing

Exercise 3: Counting Change

School’s out

Binomial Theorem

Additive Structure

Powers of Two

Sets

Powerset Lattice

Principle of Inclusion and Exclusion (P.I.E)

Binomial Distribution

Central Binomial Coefficient and Symmetry

Figurate Numbers

Powers of Eleven

Sierpinski Triangle

And the List Goes On...

Lattices Drawn as Graphs

Binary Relations

Properties of Binary Relations

Comparability: Partial Orders, Total Orders and Antichains

Order Duality

The Powerset Lattice

Binary Relations Drawn as Graphs

Subsets of Posets

Upper and Lower Bounds

The Samuel L Jackson Lattice (Total Order)

Lattices vs Posets

Up and Down Sets

Meet and Join

Semilattices

Lattices are Algebraic

Other Lattice Properties and Operations

The Algebraic Structure of the Powerset Lattice

The D4 Dihedral Subgroup Lattice

Some Notes on Notation

Additional Topics

References and Resources

Low Entry Requirements

The Lack of Differentiation between Science and Engineering

Bad Management

The Disconnect between Academia and Industry

The Lack of an Effective CS Math Curriculum

The Software Architect Debacle

The Continuous Turnover of the Work Force

The Social Networking Drain and Hollywoodification of Silicon Valley

Structural

Semantic

Editing the Positive Orthant and The Topology of Text Editing

Cursor Movement

Cutting and Pasting

Scenario #1 Low Reuse

Skill vs. Complexity

Scenario #2 high reuse

The good

The Bad

The Ugly

In Conclusion

Covariance, Contravariance and Order Theory

Defining Covariance and Contravariance

Covariance and Contravariance as Order Duals

Types as Sets of Fields

Types as Sets of Fields in the Real World

Exercise 1: Pascal’s Triangle

Exercise 2: Parentheses Balancing

Exercise 3: Counting Change

School’s out

Binomial Theorem

Additive Structure

Powers of Two

Sets

Powerset Lattice

Principle of Inclusion and Exclusion (P.I.E)

Binomial Distribution

Central Binomial Coefficient and Symmetry

Figurate Numbers

Powers of Eleven

Sierpinski Triangle

And the List Goes On...

Lattices Drawn as Graphs

Binary Relations

Properties of Binary Relations

Comparability: Partial Orders, Total Orders and Antichains

Order Duality

The Powerset Lattice

Binary Relations Drawn as Graphs

Subsets of Posets

Upper and Lower Bounds

The Samuel L Jackson Lattice (Total Order)

Lattices vs Posets

Up and Down Sets

Meet and Join

Semilattices

Lattices are Algebraic

Other Lattice Properties and Operations

The Algebraic Structure of the Powerset Lattice

The D4 Dihedral Subgroup Lattice

Some Notes on Notation

Additional Topics

References and Resources

Low Entry Requirements

The Lack of Differentiation between Science and Engineering

Bad Management

The Disconnect between Academia and Industry

The Lack of an Effective CS Math Curriculum

The Software Architect Debacle

The Continuous Turnover of the Work Force

The Social Networking Drain and Hollywoodification of Silicon Valley

Structural

Semantic

noreply@blogger.com (Geoff Moes) — Mon, 11 Mar 2013 11:30:00 +0000

In this post I make the observation that covariance and contravariance in programming are what are known as Order Duals. I am not the first person to make this observation, however, these ideas often tend to be buried in academic research papers like "Adding Axioms to Cardelli-Wegner Subtyping" by Anthony J H Simons, don’t get me wrong I love these types of papers, they give me hope and inspiration that software engineering will someday become a first class engineering citizen. Unfortunately, these types of papers tend to be too theoretical and thus not very accessible for the average developer. This is unfortunate as the idea of covariance and contravariance as order duals both puts these concepts into the mathematical context of order theory and possibly gives programmers some native context for order theory. So hopefully this post will make these ideas more programmer friendly.

I previously wrote a post about lattice theory, which is part of the more general order theory, where I talked about some basic order theory ideas such as duality. Order theory occurs quite a lot in software and programming and this is part of a series of posts to talk about those occurrences.

Covariance and contravariance receive a fair amount of attention, as they should, in software blogs and some of these posts include some interesting observations. One, perhaps slightly off topic observation, is "Liskov Substitution Principle is Contravariance" which is an interesting observation and interesting post if you overlook the disdainful tone towards OO. Another more relevant post which is a nice post about "Covariance and Contravaiance in Scala" relates these ideas to category theory which is relevant especially since apparently you can think of "Category Theory as Coherently Constructive Lattice Theory", warning heavy going in that paper.

To me one of the most striking and perhaps apropos examples of order theory in software is that of covariance and contravariance which Eric Lippert defines on his blog as:

The first thing to understand is that for any two types T and U, exactly one of the following statements is true:

T is bigger than U.

T is smaller than U.

T is equal to U.

T is not related to U.

For example, consider a type hierarchy consisting of Animal, Mammal, Reptile, Giraffe, Tiger, Snake and Turtle, with the obvious relationships. (Mammal is a subclass of Animal, etc.) Mammal is a bigger type than Giraffe and smaller than Animal, and obviously equal to Mammal. But Mammal is neither bigger than, smaller than, nor equal to Reptile, it’s just different.

He has an eleven part series on covariance and contravariance, his posts cover some C# implantation details but the ideas are generally applicable and looking at one language’s details can help with comparing and contrasting to other languages.

Wikipedia includes the following definition, the animal example is pretty popular:

Covariant: converting from wider (Animals) to narrower (Cats).

Contravariant: converting from narrower (Triangles) to wider (Shapes).

Invariant: Not able to convert.

Including this is slightly redundant but this definition captures the conversion aspect and defines the relationships explicitly.

The above are definitions that have order theory written all over them. In fact that is pretty much a text book definition of an order Relation in that it is reflexive, transitive, and antisymmetric. It is reflexive since Animal = Animal, transitive since Animal ≤ Mammal ≤ Cat implies Animal ≤ Cat, and antisymmetric since Animal ≤ Mammal implies not Animal ≥ Mammal and in the animal example there are cases of both comparability and incomparability as you would find in a partial order.

As you can see from the above definitions both sets of terms, wider/narrower or bigger/smaller, which are the same, define an order dual for comparison. To write it more formally we will call the set C classes of various types in an OO hierarchy. So covariant would be represented by less than or equals ≤ and contravariant would be represented by greater than or equals ≥ and a set of classes with these order relations can be written with mathematical notation as (C, ≤) = (C, ≥)^d .

It was in researching this post that I came across the paper "Adding Axioms to Cardelli-Wegner Subtyping". These kinds of discoveries are one of the reasons I write these posts. In that paper they quote another paper "On understanding types, data abstraction and polymorphism" by Luca Cardelli and Peter Wegner:

a type A is included in, or is a subtype of another type B when all the values of type A are also values of B, that is, exactly when A, considered as a set of values, is a subset of B

The ideas about types and subtypes covered in these papers extend beyond which fields a class or object has, however, I thought it would be interesting and beneficial to limit the discussion to that case. One reason is that if you take the fields of an object or class then all subtype collections of fields will be found in the powerset and all subtypes will be a subset relation and these can be drawn as my favorite lattice, yes I have favorite lattice, the powerset lattice. Also in this case covariance and contravariance are now defined as the subset and superset operations on the powerset lattice.

Now I always feel that a real example helps quite a bit so I have created a set of example classes, Scala traits actually, which illustrate the above ideas using a quasi-real-world example. Please note that these code examples are designed for the purposes of illustrating these ideas and may contain design issues that one would not implement in the real world, but they should be close enough to bridge the conceptual gap, if you will. Also this first example is should be applicable to dynamically typed languages that might use duck typing or structural typing.

The following Scala traits define a possible domain object hierarchy that could be used to persist data to a database and render it back to a web page among other possible uses:

trait BaseDomain {

override def equals(that: Any) : Boolean

override def hashCode : Int

}

trait PersonInfo extends BaseDomain {

var firstName : String

var lastName : String

}

trait Address extends BaseDomain {

var street : String

var street2 : String

var city : String

var state : String

var country : String

var zipCode : String

}

trait PhoneNumber extends BaseDomain {

var phoneNumber : String

var extension : String

}

trait Person extends BaseDomain {

var personInfo : PersonInfo

var address : Address

var phoneNumber : PhoneNumber

}

These traits yield the following field powerset lattice:

Now suppose we would want to define a type for each of the above lattice points, which we probably would not do but there may be cases to do similar types of things in the real world. Let’s define the following Scala traits that wrap the above domain object hierarchy elements:

trait PersonInfoTrait extends BaseDomain {

var personInfo : PersonInfo

}

trait AddressTrait {

var address : Address

}

trait PhoneNumberTrait extends BaseDomain {

var phoneNumber : PhoneNumber

}

trait PersonInfoAddressTrait extends AddressTrait with PersonInfoTrait {

}

trait AddressPhoneNumberTrait extends AddressTrait with PhoneNumberTrait {

}

trait PersonInfoPhoneNumberTrait extends PhoneNumberTrait with PersonInfoTrait {

}

trait PersonTrait extends PersonInfoAddressTrait with AddressPhoneNumberTrait with PersonInfoPhoneNumberTrait {

}

Since Scala traits support multiple inheritance we can define the above type hierarchy which can be drawn as the powerset lattice that it is:

Again we can see covariant and contravariant types defined on this lattice and each relation is actually the subset superset relation on fields.

I feel the basic observations and the above examples on order duals and covariance and contravariance make the ideas pretty strait forward for field set context. In writing this I delved into a number of papers, adding some of them to my "to read list", on Types in programming and Type Theory and I feel there are probably some deeper insights and implications of all this.

noreply@blogger.com (Geoff Moes) — Tue, 04 Dec 2012 21:53:00 +0000

I have been attending the Data Science DC meetup pretty regularly as it’s an interesting meetup often with quite good talks, the most recent was a very interesting presentation called "Implicit Sentiment Mining in Twitter Streams" by Maksim (Max) Tsvetovat. He discussed number of ideas that relate to semantic discovery which are of interest to me as I am doing research into related areas including applying semantic ideas to software naming. So I thought it would be nice to do a little review augmented with links to references that were made and additional ones that I found in the course of researching what was discussed. I am also including some more introductory links and material as it helps me and hopefully others who are not fully versed in the world of NLP. The meetup was held at Google’s downtown DC office, the irony being that the meetup was about Twitter was pointed out humorously by David Lieber of Google as he introduced Harlan for the usual Data Science DC Harlan-Mark introduction.

Max starts by talking about a system that his team at George Mason built to map sentiment during the 2012 presidential election which was then used to mine sentiment from current news, in this case the media coverage of recent conflict in Gaza. This work has yielded an algorithm to show media bias.

He points out that there are a number of things people are trying to mine and predict using twitter, the example he cites is the wired article "Twitter Can Predict the Stock Market". He sees twitter not as a social network but as a wire, an analogue of physical broadcast ether. It’s not a media carrier but a wire that other things go into with a real-time nature where things can change very quickly.

He moves on to Sentiment analysis, mentioning a paper called "Sentiment Analysis is Hard but Worth it" by Michelle deHaaff. He contrasts this title with what he describes as an easy "old school" sentiment analysis. It's where you want to know what people think, so you take a corpus of words and a stream of data and you look for occurrences of good words vs. bad words. You use an average or apply some formula to create a measure of sentiment, which is a naïve approach that might be used in a CS curriculum, but it does not really work in practice due to the complexity of human emotions and language that can have double and triple entendres. He refers to a computational linguistics paper about "She said" jokes, which I believe is this "That’s What She Said: Double Entendre Identification". Some examples he gives of possibly deceptive and/or ambiguous statements in terms of sentiment are:

This restaurant would deserve highest praise if you were a cockroach (a real Yelp review ;-)

This is only a flesh wound! (Monty Python and the Holy Grail)

This concert was f**ing awesome!

My car just got rear-ended! F**ing awesome!

A rape is a gift from God (he lost! Good ;-)

He summarizes these ideas which are challenges to machines learning these things:

Ambiguity is rampant

Context matters

Homonyms are everywhere

Neutral words become charged as discourse changes, charged words lose their meaning

The field of computational linguistics has developed a number of techniques to handle some the complexity issues above by parsing text using POS (parts-of-speech) identification which helps with homonyms and some ambiguity. He gives the following example:

Create rules with amplifier words and inverter words:

This concert (np) was (v) f**ing (AMP) awesome (+1) = +2

But the opening act (np) was (v) not (INV) great (+1) = -1

My car (np) got (v) rear-ended (v)! F**ing (AMP) awesome (+1) = +2??

Here he introduces two concepts which modify the sentiment, which might fall under the concept of sentiment "polarity classification" or detection. One idea is of an amplifier (AMP) which makes the sentiment stronger and an inverter (INV) which creates an opposite sentiment. I found this idea of "sentiment modification" intriguing and did a little searching and came across a paper called "Multilingual Sentiment Analysis on Social Media" which describes these ideas [page 12] and a few more including an attenuator which is the opposite of an amplifier. It also describes some other modifiers that control sentiment flow in the text, pretty interesting concepts, actually the paper looks quite interesting, I only read the first few pages.

He cites a paper "Cognitive map dimensions of the human value system extracted from the natural language" by Alexei Samsonovich and Giorgio Ascoli. This paper defines the following dimensions:

Valence (good vs. bad)

Relevance (me vs. others)

Immediacy (now/later)

Certainty (definitely/maybe)

And about 9 more less-significant dimensions

One result which is quite interesting is that these dimensions are pretty much language independent. While searching this out I also came across "Computing Semantics of Preference with a Semantic Cognitive Map of Natural Language: Application to Mood Sensing from Text" and "Principal Semantic Components of Language and the Measurement of Meaning" by the same authors.

Max’s work seems to run pretty heavy in social networking theory, which includes an Orielly book: Social Network Analysis for Startups. He also mentions having quite a bit of exposure to social psychology, consisting of "half a degree" as he put it, which also shows in his work. He mentions a couple of human psychological aspects, somewhat NLP related but also somewhat divergent, these are the idea of mirroring and marker words.

Mirroring is the idea that when people interact, if the interaction is positive, the example that was given was a successful flirtation, then one person will mimic the others body language. He extends this concept to the language used by various parties, in this case the tweets they emit.

Marker words are unique words an individual speaker tends to use. The idea can also extend to common expression between speakers. His description of marker words is:

All speakers have some words and expressions in common (e.g. conservative, liberal, party designation, etc)

However, everyone has a set of trademark words and expressions that make him unique.

He extends this idea to the idea of linguistic mannerisms he cites are calling health care "Obama care" would mark you as conservative, calling Hamas "freedom fighters" would mark you as siding with Hamas. Which he uses to observe mirroring:

We detect marker words and expressions in social media speech and compute sentiment by observing and counting mirrored phrases

The next part of the talk gets into the details of how to do the analysis of the raw text. One idea that he talks about is text cleaning pointing out that Twitter data is very noisy. The text is cleaned in part using stop words which are words that are common and have little lexical meaning, some examples are {a, on, the, to}. His full list which he pilfered from WordNet is here.

Another important NLP concept is stemming a linguistic morphology related concept, given by his example:

Stemming identifies root of a word, stripping away: Suffixes, prefixes, verb tense, etc

"stemmer", "stemming", "stemmed" ->> "stem"

"go","going","gone" ->> "go"

He takes his stemming code from the python project: Natural Language Toolkit.

Since the data being mined is coming from the internet which is used by people all over the globe, language detection is important. While the semantic concepts as outlined in the above work by Samsonovich and Ascoli may be language independent, the stemming and stop words are not, these techniques apply to most other languages but the specific tools and data do not, so the goal is to filter out other languages. He sums this up as:

Language identification is pretty easy...

Every language has a characteristic distribution of tri-grams (3-letter sequences);

E.g. English is heavy on "the" trigram

Use open-source library "guess-language"

The Python library he uses is guess-language which is based on some other implementations. There is also a java library: language-detection on Google code which was written by Nakatani Shuyo. All of these use a trigram approach to language detection which uses an n-gram of characters and their probabilities to identify languages this approach is described in "N-Gram-Based Text Categorization".

After the text is filtered to English, cleaned, and stemmed this leaves roots of big words, words that carry more meaning. These are used to create term vectors. Term vectors are a way to map documents into a vector space, this is known as the Vector Space Model (VSM), and is a fairly common approach, it is used in Lucene and its derivatives like Solr and ElasticSearch. Term vectors can be built with different levels of granularity, generally in Lucene this done at the document level but it can also be done at the sentence level.

I was hoping to better describe what he is doing with the term vectors and how they relate to the graphs that he creates but I am unclear as to whether his term vectors are built at the document (tweet) level or sentence level, I believe it is the sentence level as he refers to a common word in two sentences being the intersection of two different term vectors. He then starts talking about bigrams and linking speakers to bigrams, I am not sure how these relate to the term vectors. In this case the bigrams, n-grams order 2, refer to words as opposed to the trigrams mentioned above for language detection which were for letters.

Regardless of how they are created the system he describes uses bigrams of words linked to speakers which form a two-mode network, a concept that I was unfamiliar with which is described in "2-Mode Concepts in Social Network Analysis". This two-mode graph technique drives the final graphs for the sets, in the cases of {Santorum, Gingrich, Romney} and {IDF, Hamas}. He also points out by counting of the occurrence of bigrams the most common bigrams give the nature of discourse structure.

Counting bigrams enables a technique to throw out bigrams that only occur once in a certain time period, purging single occurrences cuts out the noise. The number of co-occurrences are power law distributed which reduces this from a big data problem to something that runs on an Amazon micro instances. Also dates were recorded for each occurrence which allowed noncurrent topics to be purged from the current data over time.

The algorithm to detect media bias, which he warned is naïve, yielded:

NPR	58% favorable to IDF
Aljazeera	53% favorable to IDF
CNN	59% favorable to IDF
BBC	54% favorable to IDF
FOX	51% favorable to Hamas
CNBC	60% favorable to IDF

I hope others find this useful, I sure learned a lot digging into the presentation and researching the ideas presented. This post ran longer than I had originally thought. I attribute this to the broad subject area that this talk covered. Semantics is a complex and deep topic with many facets and approaches, I was hoping to throw some order theory related ideas in as well, as they are quite applicable, but that will have to wait for another time.

The following references are a mix of works referenced in the presentation and that I came across while writing this, many are linked above but not all are:

Data Science DC meetup

Data Science DC:Implicit Sentiment Mining in Twitter Streams

Event Audio

Code and Slides

Maksim Tsvetovat Publications

The Math of Search and Similarity, Part One: Lucene, the Boolean Model, tf*idf, and the Vector Space Model

Sentiment Analysis is Hard but Worth it by Michelle deHaaff.

That’s What She Said: Double Entendre Identification by Chloe Kiddon and Yuriy Brun

WordNet

Stanford NLP

Natural Language Toolkit, github

Multilingual Sentiment Analysis on Social Media by Erik Tromp

Opinion mining and sentiment analysis by Bo Pang and Lillian Lee

Tracking Sentiment Analysis through Twitter by Thomas Carpenter and Thomas Way

Sentiment Analysis: An Overview by Yelena Mejova

N-Gram-Based Text Categorization (1994) by William B. Cavnar , John M. Trenkle

2-Mode Concepts in Social Network Analysis by Stephen P. Borgatti

Basic notions for the analysis of large two-mode networks by Matthieu Latapy, Clemence Magnien, and Nathalie Del Vecchio

noreply@blogger.com (Geoff Moes) — Mon, 22 Oct 2012 18:39:00 +0000

Martin Odersky is teaching Functional Programming Principles in Scala on Coursera and I attempted to complete this course, I completed the first assignment on recursion before the hard deadline which was hard given my work schedule at the time, however, I decided not to submit it, I remembered how much I hate school, or at least being a student in a school even a virtual one, I have my own timeline and my own interests. While doing the problems I realized, and I know this is not a major revelation, that these first three problems are set in the context of math. However, some of that math may not be immediately obvious to everyone so I thought it would make a nice post. I was originally going to publish my solutions in this post, after the hard deadline of course, but there was recently some unpleasantness about publishing solutions and cheating and it seems that it is still possibly a violation of the honor code. I feel having some code for two of the problems increases the quality of this posting so I will provide my examples for those solutions in Clojure, the non solution code will be in Scala so it’s now a hybrid posting. Also the ideas for this post forced me to finally write my previous post on Pascal’s Triangle, which this post will draw on.

The first problem is to recursively compute a binomial coefficient within Pascal’s triangle, this is fairly trivial if you have exposure to recurrence relations and recognize it as such, it is expressed as follows:

Some other common recurrence relations that are popular in CS educational circles include, Fibonacci numbers, triangular numbers and of course the factorial function these are expressed as:

I chose a term based representation of the factorial function over the more traditional:

These can be implemented recursively in Scala as:

def fibonacci(n : Int) : Long = {

if(n <= 1)

else

fibonacci(n - 1) + fibonacci(n - 2)

}

def triangularNumber(n : Int) : Long = {

if(n <= 1)

else

n + triangularNumber(n - 1)

}

def factorial(n : Int) : Long = {

if(n <= 1)

else

n * factorial(n - 1)

}

All of the above examples are inefficient and in many cases considered to be naïve solutions. The Fibonacci example is terrible as it incurs an exponential number of function calls, fortunately there ways to optimize these algorithms. One potential approach would be to use the closed formulas for triangular numbers or Binet’s formula for Fibonacci numbers. I will ignore those as I have covered them previously and they are not what I am going for here. I want to look at two optimizations, one is a way is the use of the tail call optimization and the second is to reduce the number of function calls.

Tail call optimization, put simply, is a mechanism that allows certain recursive functions that are written in a tail recursive form to be converted to iteration when they are executed. It is my understanding that this requires some extra work in the JVM, at least in the older versions, I think 7 and 8 makes changes for this. So this extra work requires some special syntax beyond simply putting your code in tail recursive form, Lisp and Scheme for example do this automatically, in Scala this requires the @tailrec annotation, using this form our functions get converted as follows:

def triangularNumber(n:Int) : Long = {

@tailrec

def triangularNumberAcc(acc: Long, n: Int): Long = {

if (n <= 1) acc

else triangularNumberAcc(n + acc, n - 1)

}

triangularNumberAcc(1, n)

}

def factorial(n:Int) : Long = {

@tailrec

def factorialAcc(acc: Long, n: Int): Long = {

if (n <= 1) acc

else factorialAcc(n * acc, n - 1)

}

factorialAcc(1, n)

}

As you can see the tail recursive forms take on an accumulator parameter. The other optimization I mentioned was to get rid of the extra function call for the Fibonacci, this is done by calculating the series using a second accumulator parameter, so that term Fn and term Fn+1 are passed as accumulator parameters. This following example came out really nice as the base function sequenceGenerator can also generate the Lucas numbers if seeded appropriately:

@tailrec

def sequenceGenerator(n: Int, t0: Long, t1: Long): Long = {

if(n <= 0)

else

sequenceGenerator(n - 1, t1, t0 + t1)

}

def fibonacci(n : Int) : Long = {

sequenceGenerator(n, 0, 1)

}

def lucas(n : Int) : Long = {

sequenceGenerator(n, 2, 1)

}

Going back to Pascal’s Identity if we look at the example from my last post:

We can represent the values that get calculated for this example visually as:

This gives some sense of how the recursive solution moves up through the triangle to sum the values, the example code, in Clojure, the naïve solution is:

(defn bc [r c]

(if (or (<= c 0) (<= r 0) (<= r c))

(+ (bc (dec r) (dec c)) (bc (dec r) c))

)

Additionally the Clojure version of our Binomial Coefficient can be similarly single call/tail call optimized:

(defn bc [rr cc]

(loop [r rr c cc acc 1]

(if (or (= c 0) (= r 0) (= r c))

acc

(recur (dec r) (dec c) (/ (* acc r) c)))

)

As mentioned most of these have closed form formulas like Binet’s formula for Fibonacci numbers. Also if we take the formula for the binomial coefficient and since r ≥ c we can get the following cancelation of c!:

Which can be implemented in Scala, using the factorial function defined above, as:

def partialFactorial(s : Int, e: Int) : Long = {

@tailrec

def partialFactorialAcc(s : Int, e: Int, acc: Long): Long = {

if(e >= s) acc

else partialFactorialAcc(s - 1, e, s * acc)

}

partialFactorialAcc(e, s, e)

}

def binomialCoefficient(r : Int , c : Int) : Long = {

if((c <= 0) || (r <= 0) || (r <= c))

else

partialFactorial(r, c+1)/factorial(r-c)

}

Both of these two “optimized” solutions for the binomial coefficient introduce division which can be problematic due to remainders and floating point rounding errors this would also be the case for the closed form approaches to calculating these numbers. There is a variant for the binomial coefficient that is discussed in a paper which uses a gcd calculation to try to deal with these issues.

Another interesting observation in terms of how values are calculated between the naïve recursive approach and the tail recursive accumulator approach is that there seems to be some order duality on how the calculations are performed. In the naïve approaches the recursion goes to the bottom and accumulates as it comes back up in the call stack. In the accumulator versions the values are accumulated on the way down and returned from the bottom of the call stack.

The next problem is not so much about the solution as it is about the combinatorial properties of the input values. The problem was to take a string and determine if the parenthesis in the string matched, this is also probably pretty common CS educational fodder. So there will be no code for this problem.

The math that we are interested in here relates to the central binomial coefficient, it is a number sequence known as the Catalan numbers after the Belgian mathematician Eugène Charles Catalan. It is given by the following equations:

In the original problem the text containing parentheses was the input, since a parenthesis counting algorithm would need to filter the text or implement some type of get next parenthesis function, we will assume that we have a string that only has only parenthesis. First thing to notice that valid input strings need to be of even length. Each term of the Catalan numbers describes how many possible sets of matching parenthesis you can have for each number n. The table below illustrates the first five possibilities:

n	C_n	Matching parentheses set	Total String Size 2²ⁿ
n=0	1 way	λ	0
n=1	1 way	()	2
n=2	2 ways	()(), (())	16
n=3	5 ways	()()(), ()(()), (())(), (()()), ((()))	64
n=4	14 ways	()()()(), ()()(()), ()(())(), ()(()()), ()((())), (())()(), (())(()), (()())(), ((()))(), (()()()), (()(())), ((())()), ((()())), (((())))	256
n=5	42 ways	()()()()(), ()()()(()), ()()(())(), ()()(()()), ()()((())), ()(())()(), ()(())(()), ()(()())(), ()((()))(), ()(()()()), ()(()(())), ()((())()), ()((()())), ()(((()))), (())()()(), (())()(()), (())(())(), (())(()()), (())((())), (()())()(), (()())(()), ((()))()(), ((()))(()), (()()())(), (()(()))(), ((())())(), ((()()))(), (((())))(), (()()()()), (()()(())), (()(())()), (()(()())), (()((()))), ((())()()), ((())(())), ((()())()), (((()))()), ((()()())), ((()(()))), (((())())), (((()()))), ((((()))))	1024

The table above also includes the number of possible strings with only the two parentheses, which grows at a rate 2²ⁿ. This table is based on one from a paper by Tom Davis on Catalan numbers. It is quite interesting paper as Catalan numbers also describe diagonal avoiding paths, “mountain ranges”, noncrossing partitions, multiplication orderings, the number of different ways a convex polygon with n + 2 sides can be cut into triangles, to mention a few. Another interesting thing about Catalan numbers is they can be described by a recurrence relation:

I confess that this may not be that pragmatic in terms of solving the problem, but I think it is interesting and possibly gives a larger context to the problem.

The last problem, which is probably something of a CS classic problem as it appears in SICP, is the problem of counting change, given some numerical amount and some set of coin denominations we need to count the number of ways that we can represent the amount given the set of denominations. I confess to having cheated a little bit, well ok a lot, I found this post by Bill the Lizard. I also found this post with a more elegant solution and translated these into both Scala and Clojure, well ok I guess it’s not cheating since I didn’t submit it. The clojure version is:

(defn count-change [amount coin-values]

(cond (= amount 0) 1

(or (< amount 0) (empty? coin-values)) 0

:else

(+ (count-change amount (rest coin-values))

(count-change (- amount (first coin-values)) coin-values))

)

The math here is from number theory and combinatorics, actually it might fall under combinatorial number theory. In number theory there are two pretty big areas, one is multiplicative number theory which dates back at least to the Greeks and deals with how numbers divide and remainders and prime numbers which includes things like the well known fundamental theorem of arithmetic. A relatively newer area of number theory is known as arithmetic number theory and is mostly attributed to Euler. In fact it was Euler who initiated the study of number partitions in his book Introduction to the Analysis of the Infinite in 1748. It is the math of number partitions that our change problem falls under. We are basically counting a subset of the partitions of a number’s full partition set. In fact we can create a function that uses a Clojure list comprehension to create a number partition function from our change counting function:

(defn number-partition [n]

(count-change n (for [x (range 1 (inc n))] x ))

)

Functions to count partitions have been studied over the years and Euler invented a generating function that gives rise to, you guessed it, a recurrence equation to count partitions:

So there it is some (hopefully) interesting math context for these problems. I guess it’s kind of a gray area but I am pretty sure I didn’t cross the line on the whole honor code thing but even if I did I believe it’s covered by the People's Freedom of Choices and Voices Act.

Well it was a fun post to write, I got some code in a post, something I haven't done lately, which is only fitting for a blog called Elegant Coding, I think it came out pretty decent but remember I am still learning Scala and Clojure so my code examples here may not be as elegant as they could be. I guess another objective of this post and my blog in general is to explore ways to mix programming and math education, while I think this post makes for a nice start along these lines, it could probably be improved which would be nice.

noreply@blogger.com (Geoff Moes) — Mon, 08 Oct 2012 20:41:00 +0000

Pascal’s Triangle is one of the most fascinating and intriguing objects in math, I was first introduced to it in the sterile context of high school algebra as an aside. Only decades later did I discover its true grandeur when I rediscovered it in the context of combinatorics and number theory. I will attempt to provide some, hopefully, enlightening images but I feel that mathematical notation is both important and beautifully concise and allows one to have a transcendent experience with math so we will start with a formula, one of my “Eleven Equations”. The more I learn the more I feel it is more than justified to be in that list. I also feel that its centrality in combinatorics and probability theory makes it an equation that every math or computer science geek or enthusiast should be able to both recite off of the top their heads and be able to apply, if you don’t agree maybe this post will inspire you to think differently. The equation is that of the binomial coefficient formula and it describes each element of Pascal’s Triangle:

The above formula evaluates under the rules that c ≤ r, r ≤ 0 and 0! = 1. I prefer the use the letters r and c over the traditional n and k as in n chose k, one can as easily say r choose c. The reason I prefer r and c is that r means row and c means column and these values can be viewed as a way to address positions within Pascal’s Triangle, for example using the binomial coefficient notation from the above formula Pascal’s Triangle can be represented as:

As you can see in the above representation each position is the address (r,c) given by the coefficient notation. Evaluating the expressions above with the Binomial Coefficient formula yields the more common representation of Pascal’s Triangle:

If I recall correctly and has been a while, the high school algebra introduction to Pascal’s triangle was mostly tied to the Binomial Theorem, which is written with sigma (summation) notation as:

For our purposes we are interested in the one variable version which can be written as:

This can be expanded to:

This can be written in "Pascal’s Triangle Form" as:

These types of introductions often focus on the additive properties as well. Each element is the sum of the two elements above it, which can be illustrated as:

The logic of this representation assumes that there is a zero on each side to add to propagate the ones on both side, we can rewrite this using the binomial coefficient notation as:

I admit this is where it starts to get more interesting to me. Not to denigrate its importance but I never really got that excited by the whole binomial theorem thing, although the series e stuff is pretty cool. If we pick 5 choose 3 in the above representation, it can be written as the following sum:

If you look at the above representation you can see that this can be done for all entries that have two parents, this can be generalized as:

This formula, which is a recurrence relation, is known as Pascal’s Identity, it is one of several formulas known as Combinatorial Identities.

Another interesting and extremely important pattern in Pascal’s Triangle is the fact that the values of each row sum to the power of two of the row number, which the following representation depicts:

This can be written as the following formula, I think this also qualifies as an identity:

As I mentioned at the beginning the binomial coefficient formula is read as r choose c. I was trying to get back to that but I took the long way, so looking at our examples above our 5 choose 3 means if I have five things how many ways can I choose three of them which is 10 ways . This is useful for counting, in combinatorics and probability theory I could take a deck of 52 cards and count how many 5 card hands I could choose and calculate probabilities of getting various hands, these are pretty standard applications of these types of counting problems. However, if we step back and look at this counting, where each row represents a set of items, then each column represents the number of subsets of size c, this another reason I prefer c here it means both column and cardinality of the subset. We can create a representation of Pascal’s Triangle to show this, but it does become unwieldy pretty quickly due to the exponential growth of each row, we would get:

In this representation each number represents a set element, these can map to any sets with these cardinalities. Each column is wrapped by parentheses. The ones on the left are created by the empty set and the ones on the right are created by the set itself. So each row in Pascal’s triangle gives the structure of the powerset of a set with the cardinality of the row number. Also it is not a coincidence that each row sums to a power of two since the cardinality of the powerset is the cardinality of the set raised to the power of 2.

Since I’ve had lattice theory on my mind lately, I couldn’t help but calling on our old friend the powerset lattice, as you can see in the context of the above each powerset lattice is going to have a row from Pascal’s triangle imprinted on it, each antichain consists of sets of the same cardinality and the number sets in the antichain maps back to a column:

The principle of inclusion and exclusion is used to count the size (cardinality) of a union of sets based on the cardinality of the sets and their intersections, the most common form, which appears in many probability texts, is:

|A ∪ B| = |A| + |B| - |A ∩ B|

The reason for this is that if you take the size of the union two sets, if they have any common elements then they counted twice, so subtracting the intersection removes the duplicate count. This type of problem, counting things more than once and then needing to remove the duplicates comes up in other counting problems as well. The venn diagram below shows the intersection of two sets, these are the elements that get counted twice in |A| + |B|:

Now as a disclaimer this Pascal’s triangle correlation is strictly my own observation so it might be wrong, but it seems to hold. If you take the formula from above and add a term for the empty set, which is not needed as it evaluates to zero you get |∅| + |A| + |B| - |A ∩ B|. Now you can see the number of elements for each term with number of sets (0, 1, 2) are 1 2 1, row 2 of Pascal’s triangle, for three you have 1 3 3 1:

\|A ∪ B ∪ C\| =
	\|∅\| +	(1
	\|A\| + \|B\| + \|C\|	(3
	- \|A ∩ B\| - \|A ∩ C\| - \|B ∩ C\|	(3
	+ \|A ∩ B ∩ C\|	(1

And for four we have (1 4 6 4 1)

\|A ∪ B ∪ C ∪ D \| =
	\|∅\| +	(1
	\|A\| + \|B\| + \|C\|+ \|D\|	(4
	- \|A ∩ B\| - \|A ∩ C\| - \|A ∩ D\| - \|B ∩ C\| - \|B ∩ D\| - \|C ∩ D\|	(6
	+ \|A ∩ B ∩ C\| + \|A ∩ B ∩ D\| + \|A ∩ C ∩ D\| + \|B ∩ C ∩ D\|	(4
	- \|A ∩ B ∩ C ∩ D \|	(1

This does not prove it but I would bet the pattern continues. Like I said this is my own observation, so it might be wrong, if you know either way please let me know.

The binomial distribution is given by the following formula:

I converted it to my r,c nomenclature, I may be going too far using it here but I wanted to keep consistent, remember r=n, and c=k. It is a discrete probability distribution for the number of successes of r independent yes/no experiments each of which yields success with probability p. If you set p=1/2, the symmetric case, then the row number r divided by 2^r gives you the binomial distribution. By the central limit theorem this symmetric case approaches the normal distribution as r increases.

The above representation shows the symmetry in Pascal’s Triangle, each row is colored in a way that highlights the numbers that are the same, the first and last columns consisting of ones match each other obviously, but in each row the second column matches the second to last column, and the same for the third column and so one. This gives rise to, you guessed it, another combinatorial identity:

The columns highlighted in the gray box are special case called the central binomial coefficient. If you notice each even numbered row has an odd number of columns with the central one only occurring only once, it still follows the above identity but the identity evaluates to a value equaling itself. The central binomial coefficient is given by the following form, I use n here since we don’t care about row/column in this case:

There is an area of math that deals with figurate numbers, these are numbers formed by arranging dots to form various polygons which form sequences as you expand size of each polygon, I looked at some interesting properties of triangular numbers in a previous post, for example here are the first 5 triangular numbers:

Triangular numbers are created by adding up the natural numbers, but there is a binomial formula which evaluates to a closed formula:

The idea of figurate numbers can be extended into higher dimensions, so not only do you have numbers that create polygons you can create polyhedrons as well. When you add up triangular numbers, you get the tetrahedral number which can be described by an analogous formula:

This can be visually depicted as stacking up the triangular number to form tetrahedrons:

Pascal’s Triangle has a number of relations with figurate numbers, but the most notable are the triangular and tetrahedral numbers, shown in red and blue respectively:

Also if you look at the binomial expression for these you will notice that the column is fixed, for triangular numbers it is c=2 and for tetrahedral numbers it is c=3, this maps our addressable form to the second and third columns as shown.

The above tabular form is based on a table from Concrete Mathematics, 2nd Edition by Ronald L. Graham, Donald E. Knuth and Oren Patashnik. Again you can see column one, where c=1, is the natural numbers, column two is the trianglular numbers, the summation of natural numbers and three is the tetrahedral numbers, the summation of the triangular numbers. This would imply that this pattern continues to progress, and it does. The next column are the pentatope numbers, which describe a series of four dimensional polytopes, a polytope is an extension of a polyhedron into higher dimensions, called pentachorons which are formed by stacking three dimensional tetrahedrons in four dimensions. These numbers are given by the formula:

And these numbers progress into higher dimensions, each summing the numbers immediately below them. These are generalized as the pyramidal numbers and are described by the following table:

Number	Summation Form	Binomial Form	Closed Form

There is another interesting pattern in Pascal’s Triangle each successive row is equivalent to a power eleven of as you can see in the following table:

0	11⁰	1
1	11¹	11
2	11²	121
3	11³	1331
4	11⁴	14641
5	11⁵	161051

Oops, I fibbed a little here, 11⁵ does not equal the row (1 5 10 10 5 1), this breaks down due to the need to carry 1 to make ten. However, the pattern will hold if you push up the number base, for example 11 hexadecimal, which I will write as 11₁₆, to the 5^th power is (11₁₆)⁵ = 15AA51, remember A equals 10 so now the pattern holds, and it will continue to hold as long as you keep upping the number base, but remember (11₁₆)⁵≠ 11⁵.

There is another interesting relation to another mathematically interesting triangle, the Sierpinski Triangle aka Sierpinski gasket is a fractal that can be constructed by taking an equilateral triangle and removing the center which is an equilateral triangle of ¼ area and then repeating this on each of the three remaining triangles, and so on. It can also be created by applying modulo 2 to each element in Pascal’s Triangle as shown below. The zeros are grayed out to highlight the pattern:

As we saw we ventured into several areas of mathematics, combinatorics, number theory, probability theory, fractal geometry and geometry (topology), and lattice theory. There are many other patterns such as relations to polytopes, cellular automata, a pattern with prime numbers and more. The Wikipedia page has many interesting patterns, some of which I used here also two other interesting sites are Christopher Olah’s post and this.

noreply@blogger.com (Geoff Moes) — Tue, 18 Sep 2012 14:38:00 +0000

Matt Might has a blog post "Order Theory for Computer Scientists" in which he concisely outlines some basics of order theory. It is a nice post but it is targeted towards computer scientists and is possibly only of interest to that audience, especially since all of his examples are in Haskell, not that there is anything wrong with that, but I think this is unfortunate as these ideas are potentially interesting to programmers as well.

In this post I am mostly talking about lattice theory as opposed to the more general order theory. While general order theory is both interesting and relevant to programming and CS, lattice theory is too and there are many interesting ideas that relate to lattice theory. Lattices impose more structure on orders and that is probably why there are a lot of books on lattice theory such as George Gratzer’s comprehensive and recently updated Lattice Theory : Foundation. Lattice theory has been described by Gian-Carlo Rota, an accomplished twentieth century mathematician and lecturer, as having "been the object of such vociferous vituperation". The book Combinitorics the Rota Way, which he coauthored, gives deep insights into this subject and its relationship to other areas of math including, of course, combinatorics, but also topology, set theory, Boolean algebras, probability theory, and more. I think Rota will be vindicated with a vengeance as it seems to me that lattices show up almost everywhere in math. Additionally I feel that lattice theory will be become quintessential in computer science and software engineering and should be a mandatory math for those curricula. I will expand on these ideas in follow up posts.

One anecdote tells of a senior mathematician who stopped Rota in the halls of MIT and stared at him demanding: "Admit it! All lattice theory is trivial." I confess I have some difficulty with lattice theory as it does seem to be both trivial and deep, at first the ideas don’t seem to really have that much substance, but deeper you dig the more things you find, and it seems that it is always showing up in other areas of math, and even if it is not obvious it often seems to be right under the surface. I think that’s the duality here, the ideas, per se, are not that impressive, much of the importance comes from the application of the ideas and their relation to other areas of math.

In George Gratzer’s updated Lattice Theory : Foundation he states that a difference between the new addition and the previous edition is the addition of more diagrams, and recommends the reader drawing their own as well, in my opinion he does not go far enough, one of the goals of this post to have some pictures for the basic ideas. I admit I will do my best here to help the motivated learner, but this post should probably be viewed as supplemental to other resources. Also you will need to have some knowledge of set theory and concepts like Cartesian products and some knowledge of abstract algebra such as group theory may also be helpful. Also knowledge of basic graph theory is needed. You will also need some comfort level with basic mathematical notation. If you don’t have this knowledge, hopefully you are willing to get up to speed on it, trust me, it’s worth it. Another point to note is that everything covered here will be finite, all sets, orderings, and lattices are finite, I believe that much of this extends to the countable infinite, etc. I leave that for you to pursue.

Lattices have some connections to graph theory and to really fully understand the nuances of these ideas you need to have an understanding of basic graph theory, specifically the differences between directed graphs and undirected graphs and an understanding of cycles and acyclic graphs.

Lattices can be drawn as graphs the main diagram used to visually represent lattices is the Hasse diagram which depict lattices as a undirected graph, more on this below. Also it should be noted that issues of graph planarity are ignored and two crossing edges, that is with no vertex, have no significance in terms of order, also sometimes for aesthetic reasons intersecting lines are shown as crossing behind other lines, again this has no impact on the order structure.

Lattices are built on the concept of a binary relation on a non empty set. This is usually expressed in terms of the Cartesian product of a set with itself, where R is the relation and S is the set:

R : S x S → S

In this case the binary relation emits a member of the same set, which means it is closed on the set.

For example for the set S = {a,b,c} a possible relation is the ordered pairs: R = {(a, c), (a, a), (b, c), (c, a)}. In general a Binary Relation can be written as a set of ordered pairs. When talking about orders there is a distinction as to whether the relationship between two elements in the set exists, meaning does the ordered pair (x,y) exist in R. In the example above (b,c) exists, (b,c) ∈ R. Also note that opposite relation of (b,c), (c,b) is not in R, (c,b) ∉ R.

This binary relation can be seen in the diagram below, each of the ordered pairs map to a directed edge:

Binary Relations can have certain properties. I feel this is the crux of understanding ordering relationships. The first two properties are:

Reflexive ∀x ∈ S (x,x) ∈ R

Transitive∀ x,y,z ∈ S if (x,y) ∈ R and (y,z) ∈ R then (x,z) ∈ R

If a binary relation has these two properties, that is it is Reflexive and Transitive then it is known as a preorder or quasi-order. This is a more general type of binary relation which we are not really interested in initially except in how it relates to two more specific types of binary relations.

The symmetric property is defined as:

Symetric ∀ x,y ∈ S if (x,y) ∈ R then (y,x) ∈ R

A preorder with the symmetric property is known as an equivalence relation. In terms of Lattice Theory this is another binary relation that we are not immediately interested in. Equivalence relations are well worth learning more about in their own right, as they play an important role in partitioning sets which have interesting applications in abstract algebra in relation to quotients of groups and rings and homomorphisms of groups and rings.

The next property, which we are very interested in, is the antisymmetric property which is defined as:

Antisymmetric ∀ x,y ∈ S if (x,y) ∈ R and (y,x) ∈ R then x = y

A preorder with the antisymmetric property is known as an order relation sometimes referred to as a partial order. A set with a partial order on it is called a partially ordered set, poset, or just an ordered set. So now we have a definition of an order:

If S is a non-empty set then by an order on S we mean a binary relation on S that is reflexive, anti-symmetric, and transitive.

We will now use the less than equals symbol ≤ to denote our order relation which follows as:

(∀x∈ S) x ≤ x;                                     (reflexive)
(∀x, y ∈ S) if x ≤ y and y ≤ x then x = y;      (antisymmetric)
(∀x, y, z ∈ S) if x ≤ y and y ≤ z then x ≤ z.(transitive)

In general an order is defined using the notational convention: (S, ≤) where S is the Set on which the order is defined and ≤ denotes ordering relation. Note: ≤ is not necessarily the same as less than or equals, it might be, but it could also be a number of other order relations.

One thing that I found confusing when learning about ordering relations is the difference between a total order and a partial order. The idea of a partial order is that not all elements in a set have a relation. Some pairs of elements are incomparable, meaning no relation exists between them. This is denoted using the parallel lines symbol: ∥, for example x ∥ y means (x,y) ∉ R and (y,x) ∉ R.

An example of a partial order is the set of partitions below:

This is a partial order of set partitions of a set of three items. For example suppose that the set {a,b,c} is a plate containing an apple, a banana and a cherry. As you move down the lattice you get more partitions, in the second row you can partition two pieces of fruit onto one plate and one on another, in three different ways {a}, {b,c} or {b}, {a,c} or {c}, {a,b} . In the bottom row you can only partition three pieces of fruit one way on three different plates {a},{b},{c}. If you move up the lattice you can reverse the operation and consolidate the set partitions (plates) in the same manner.

You should note that above the elements: a|bc, b|a,c, and c|a,b have no ordering relation to each other, that is there is no way to further partition the current plates, rearranging them isn’t allowed. So these items are incomparable: a|bc ∥ b|a,c, b|a,c ∥ c|a,b , ...

A total order is also known as a linear order or a chain. In a total order all elements are comparable meaning that the relationship has the following total property:

Total ∀ x,y ∈ S (x,y) ∈ R or (y,x) ∈ R

A fairly simple example of a chain is the integers 1-5 with the ordering relation less than or equals, which would be written as ({1,2,3,4,5}, ≤) which would have the following diagram:

An antichain is a set where no two elements are comparable:

Antichain ∀ x,y ∈ S (x,y) ∉ R and (y,x) ∉ R

An example is the suits of a card deck, there are probably some exceptions, but in general a spade, a heart, a club and a diamond have no order relation to each other, this antichain can be depicted as:

Also you should note that above the elements: a|bc, b|a,c, and c|a,b in our set partition lattice above form an antichain within that lattice.

Order duality is actually a fairly intuitive idea, for example if you had a list of words in alphabetical order, you can reverse the order. This holds true for every ordering relation and is called the Duality principle. More formally if you have an order P = (S, ≤), its dual denoted P^d would be defined as P^d =(S, ≥). If you take any of the lattice examples above or below and reverse them, flip them upside-down, you get the dual of the order relation. This is one of the most seminal ideas in order theory. It also shows up in other parts of math.

The powerset of set is a set of all of the subsets of the set. For a set of three items, S = {a,b,c} The power set of S, which is a set of sets, is: { {a,b,c}, {a,b }, {a,c}, {b,c}, {a}, {b}, {c}, ∅ }. A common notation for denoting the powerset is 2^S. This notation draws from the fact that the cardinality of the powerset is the cardinality, the size of the set, of the set raised to the power of 2, this can be expressed more concisely using the notation |S| to describe cardinality, so the above set has the cardinality |S| = 3. The powerset of S 2^S has the cardinality |2^S | = 2³ = 8.

The lattice below shows the ordering relation "is a subset of", this can be denoted by ⊆ and the order would be given in notational form as (2^S, ⊆).

Its order dual which is "is a superset of" given by (2^S, ⊇):

Now that we have some definitions and diagrams in place I wanted to revisit the drawing of lattice diagrams. Our first relation diagram above has a loop for (a,a) and (b,c) (c,a) makes it transitive, but it is not reflexive because it is missing loops for b and c. So that relation is not a preorder which means it is also neither an equivalence relation nor an ordering relation.

For every preorder, there corresponds a directed graph, with elements of the set corresponding to vertices, and the order relation between pairs of elements corresponding to the directed edges between vertices. Graphs of preorders can contain cycles. Also all nodes in a preorder group will have a loop for the reflexive relation that must exists on each node. Graphs representing equivalence relations will be undirected graphs since these relations are symmetric and will of course have loops on each vertex for reflexivity. As mentioned above graphs for partial orders will be a directed acyclic graph graph due to antisymmetry also they should have reflexivity loops.

The total order for 1-6 mentioned above would look as follows for the relation ≤ it is a simple directed graph:

If we were to add all of the transitive and reflexive relations it would look like this:

As we have seen in our diagrams the reflexivity loops are omitted as they are not needed and would be increase the complexity of the diagrams. Also in the diagrams the transitivity can be inferred by following the two paths connecting three nodes.

Hasse diagrams are drawn as undirected graphs which implies the order duality, we can decompose that graph into two directed graphs as in our example above for the two dual realtions (subset ⊆ and superset ⊇) on the powerset lattice, the lattice is conventionally drawn as the following Hasse diagram:

Another interesting point here is the difference between equivalence relations and order relations is that no cycles will occur in an ordering relation.

Since we are dealing with sets, a set with an order relation, a poset (short for partially ordered set), can have subsets. The interesting thing is that the subsets as a whole can be different types of orders than the original poset. For example the power set above has as a sub-poset, {a,b,c}-{a,b}-{a}-∅, which is a total order. Additionally the antichain {{a,b} {a,c} {b,c}} is also a subset of the powerset poset. These elements still have the same relations as they did in the original set, but the subsets themselves are different structures.

A finite set, remember we are only considering finite sets, with an order relation implies that if you move up and down the ordering relation eventually you will hit a maximum or minimum element. The above examples, the total order has an upper bound of 5 and lower bound of 1, the powerset lattice has an upper bound of the set itself and the empty set as a lower bound. The antichain does not have a single upper or lower bound the four elements are each both their upper and their lower bounds. The idea of bounds, specifically the idea of greatest lower bound (GLB) which is also known as an infimum and the dual the least upper bound (LUB) which also known as the supremum are important in order theory but show up in other areas of math such as topology.

A poset may not have one upper or lower bound, this is a distinction from a lattice which is still a poset but it has a single upper and lower bound. A lattice will have both a distinct upper and distinct lower bound, that is one element that is the upper bound and one element that is the lower bound. These are sometimes denoted as ⊤ for upper bound and ⊥ for lower bound. This bounding feature of lattices is very important as we will see.

Since Samuel L. Jackson has a habit of showing up everywhere, he is the new Kevin Bacon, and it is only fitting that he would show up in Lattice Theory. Another example of a total order or chain is what is known as the "Samuel L. Jackson Scale of Black Emotion" which was developed by Larry Willmore of the Daily Show. It forms a Total Order also known as the Samuel L Jackson Lattice, which includes the following elements:

Furious Anger Guy
Shaft
Changing Lanes Guy
Snakes on a Plane Guy
Jurrasic Park Jackson
Frozone
Mace Windu

As you can see the sup(Samuel L. Jackson Lattice) = ⊤ = "Furious Anger Guy" and the inf(Samuel L. Jackson Lattice) = ⊥ = "Mace Windu". Now it’s pretty obvious in an intuitive human sense that the Master of the Order and Jedi Master Mace Windu is the lattice dual of Furious Anger Guy of Pulp Fiction, well up to his epiphany in the diner robbery scene anyway.

As with all lattices, this lattice has an order dual denoted (Samuel L Jackson Lattice)^d known as the Inverse Samuel L Jackson Lattice, which just a reverse of the above list.

Ok, I’m having a little fun here, trying to lighten the mood a little. However, this is a legitimate example of a lattice.

By definition a lattice is a poset, however, a poset is not necessarily a lattice. A lattice is defined as, with sup being supremum and inf being infimum:

An order (S,≤) is a lattice if sup{a,b} and inf{a,b} exist ∀ a, b ∈ S.

Actually there are some distinctions between different classes of lattices:

A lattice is a poset in which all nonempty finite subsets have both a least upper bound and a greatest lower bound.

A complete lattice is a poset in which all subsets have both a least upper bound and a greatest lower bound.

A bounded lattice has a unique top element and a unique bottom element, actually there are algebraic implications that we will discuss below.

Finite sets form complete lattices and since we are limiting ourselves to finite sets we will only be dealing with complete lattices. Also every complete lattice is a bounded lattice so when we talk about lattices here we will mean complete lattices aka bounded lattices.

If you take an element of a poset or a Lattice and take the subset of all elements that are greater than the element you get a new poset or lattice that is a subset, these types of subsets are referred to as up-sets or down-sets. An up-set of an element x denoted as ↑ x includes the element and everything above it is defined as:

↑ x = {y∈ P : y ≥ x}

The up-set of the element {a} in the powerset lattice above would look like (shown in blue):

Similarly, or perhaps "dually" the down set, denoted as ↓ x, is defined as:

↓ x = {y∈ P : y ≤ x}

With the down-set of the element {a,b} in the powerset lattice (in red):

Meet and Join are two binary operators defined on elements of posets and and lattices which yield a unique value and they are dual operations of each other. In the case of a poset meet and join may or may not exist on any two elements, in the case of a bounded lattice they will exist. Join is usually denoted with the or symbol: ∨ and meet is denoted with the and symbol: ∧. Join is equivalent to supremum and meet is equivalent to infumum. They are defined as:

x ∨ y = sup{x,y}

x ∧ y = inf{x, y}

The following describes their relation with ordering:

x ≤ y ⇔ x ∨ y = y

x ≤ y ⇔ x ∧ y = x

As you can see above when two elements are comparable meet and join will reduce to the appropriate minimum or maximum element, when two elements are incomparable as in the picture of the join below between {a} ∨ {c} the lattice lines show how the join moves up to the element {a,c} that is above each element, not coincidently the join on this lattice is the set union operation ∪ actually this join can be expressed as {a,c} = {a} ∪ {c} which is right out of set theory.

And the dual relation is {a} ∩ {c} = ∅:

A semilattice will define either a meet or a join operation over an order resulting in either a meet semilattice or join semilattice, technically a lattice is both of these combined. A good example is a tree which as a single root node, let’s call it a lower bound aka an infimum, a common example is the prefix tree for strings, in this case we are using binary strings 0 or 1 up to length three:

In this example the order relation is: "Is a prefix of". As you can see you can define a meet on any two elements with the empty string λ serving as the semi-lattice bottom ⊥. Also as you can see there are no joins on this order. Pretty much any tree can be viewed as semi lattice with descendency from the root node through all of the other nodes serving as the ordering relation.

One of the interesting and sometimes confusing things about lattices is that, while they are structural they are also algebraic. Meet and join follow a number of algebraic rules. In general lattices can be defined as an algebra L=(S, ∧, ∨) which satisfy the following algebraic rules for all x, y, z ∈ S:

Idempotent

x ∧ x = x

x ∨ x = x,

Commutative

x ∧ y = y ∧ x

x ∨ y = y ∨ x,

Associative

x ∧ (y ∧ z) = (x ∧ y) ∧ z

x ∨ (y ∨ z) = (x ∨ y) ∨ z,

Absorption

x ∧ (x ∨ y) = x

x ∨ (x ∧ y) = x.

The first three pairs of axioms say that L is both a meet and join semilattice. The fourth pair (the absorption laws) say that both operations induce the same order on L.

Since we are dealing with bounded lattices we extend the above laws to include the following for the top and bottom elements, here we will represent the bottom element ⊥ as 0 and the top element ⊤ as 1. For a bounded lattice the algebra is defined as L=(S, ∧, ∨, 0, 1) with the following identity laws:

x ∨ 0 = x

x ∧ 1 = x

x ∧ 0 = 0

x ∨ 1 = 1

For our powerset lattice above the algebra is (S, ∩, ∪, ∅, S) with the empty set as the identity for the union operation and the set itself as the identity for the intersection.

If you take our powerset example above, you might have noticed that there are some more algebraic properties of this lattice that are not listed above. The first is the distributive property. While the powerset lattice does have the distributive property you should note that not all lattices do. The distributive property is defined as:

Distributive Law

x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z)

x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)

Another property which can be found in certain lattices and also applies to our powerset lattice is the property of complementation which means that for every element x the lattice has a complement y under both the meet and join operations:

x ∧ y = 0

x ∨ y = 1

Some Lattice which are Complemented can have additional properties which is known as orthocomplementation and has the following laws:

Complement Law

x ∧ x^c = 0

x ∨ x^c = 1

Involution Law

(x^c)^c = x

Order Reversing

x ≤ y then y^c ≤ x^c

Our power set lattice which is also a Boolean Algrebra also follows Demorgans laws:

Demorgans laws

(x ∨ y)^c = x^c ∧ y^c

(x ∧ y)^c = x^c ∨ y^c

Some lattices can have a property known as Modularity which follows the following law, which is similar to the distributive law:

Modular law

x ≤ z implies x ∨ (y ∧ z) = (x ∨ y) ∧ z

I am including Modularity for completeness as I am not discussing it or including examples. Distributivity, Modularity and Complementation have many intricacies and there is much theory and complexity surrounding how these work and where they show up, this becomes quickly obvious if you dig into more resources on lattices.

With the above algebraic laws of complemented (orthocomplemented) bounded lattices defined, I figured it might be nice to list out these laws as they apply to our powerset lattice, if we take the powerset 2^S of any set S, the empty set ∅ is the lower bound and the set S is the upper bound. The powerset lattice has the following laws:

Idempotent

x ∩ x = x

x ∪ x = x

Commutative

x ∩ y = y ∩ x

x ∪ y = y ∪ x

Associative

x ∩ (y ∩ z) = (x ∩ y) ∩ z

x ∪ (y ∪ z) = (x ∪ y) ∪ z

Absorption

x ∩ (x ∪ y) = x

x ∪ (x ∩ y) = x

Distributive

x ∪ (y ∩ z) = (x ∪ y) ∩ (x ∪ z)

x ∩ (y ∪ z) = (x ∩ y) ∪ (x ∩ z)

Identity

x ∪ ∅ = x

x ∩ S = x

x ∩ ∅ = ∅

x ∪ S = S

Complement Law

x ∩ x^c = ∅

x ∪ x^c = S

Involution Law

(x^c)^c = x

Order Reversing

x ⊆ y then y^c ⊆ x^c

Demorgans laws

(x ∪ y)^c = x^c ∩ y^c

(x ∩ y)^c = x^c ∪ y^c

This topic might be filed under an advanced example, so feel free to skip if you’ve had enough for the moment. In doing my research I came across the following lattice diagram, it is the lattice of the subgroups of the D₄ Dihedral Group, I looked at cyclic groups and subgroups including the cyclic subgroups of D₄ in a previous post on abstract algebra. I have modified it to better show the identity element marked in blue. It also includes the names of well known isomorphic groups that correspond to each subgroup.

This lattice shows some really interesting things about the dihedral group. The top element is the D₄ group itself and the bottom element is the trivial Z₁ group consisting of only the identity. As you can see the center forms a chain consisting of three cyclic groups, Z₁, Z₂, Z₄, and D₄ (not cyclical). The anti-chain of five Z₂ isomorphic groups, all of which are involutions, like negation it is an operation which if applied twice results in the original value, on the left are the horizontal (H) and vertical (V) reflection involutions, the middle one is a 180 degree rotation (R₂) involution and on the right are two diagonal (D₁, D₂) reflection involutions. As you can see on the vertical and horizontal involutions on the left along with the rotation involution form the group (R₀, V, H, R₂) and on similarly on the right the subgroup (R₀, D₁, D₂, R₂) is formed. Also both of these groups are isomorphic to what is known as the V group, aka the four group, aka Klein group, aka the Vierergruppe. I am not sure what all of this means but I find it fascinating. Also please note that there is a minor nomenclature conflict as V refers to both the Klein group and the vertical reflection D₄ group element, but the context of each is mutually exclusive. The same goes for D_n where D₁ and D₂ are elements and D₄ is a group. Additionally this lattice give a nice visual depiction of Lagrange's Theorem which states that the order of each subgroup will evenly divide the order of the group. Therefore, as in the lattice, a group of order 8 only has subgroups of orders 4,2,1.

In math notation can vary and order theory has several variants on notation that it helps to be aware of. Firstly the following sets of symbols can often be used in relations to orders:

Sometimes these choices are made at a particular authors preference other times combinations of these are used, such as in discussing things like Galois Connections which are mappings between two different orders, in such a case multiple sets of the above symbols might be needed to differentiate between specific instances of different orders. Usually the set notation symbols are not used for lattices but they sometimes are, and in our examples above both meanings apply. Also the following symbols get used to describe comparison as well:

Another set of symbols that show up, which are often used to describe covers, or immediately precedes or immediately succeeds, in that there are no elements between the two items compared are:

The topics of lattice theory and order theory are extensive and this post really just scratches the surface. When you feel comfortable or even if you don’t depending on your learning style, there are many things that I did not cover. There are order specific concepts like strict and asymmetric. Complete partial orders show up a lot in CS as well. For lattices there are things that I only mentioned like modularity and Galois connections, there functions on lattices which include ideas like monotone, antitone, and isotone. New lattice can be created by number of techniques like the Cartesian product of two lattices. And of course there are many interesting results relating to fixed points, and the list goes on.

In my next post I will look at some specific examples of some the ideas discussed here in everyday programming and some more theoretical examples as well.

There are a number of books on the subject, including the previously mentioned the recently updated Lattice Theory: Foundation by George Grätzer and Combinatorics: The Rota Way by Joseph P. S. Kung, Gian-Carlo Rota and Catherine H. Yan, there are a number of books on the subject including:

Lattices and Ordered Algebraic Structures by T.S. Blyth
Introduction to Lattices and Order by B. A. Davey and H. A. Priestley
General Lattice Theory (Second Edition) by George Grätzer, B.A. Davey, R. Freese and B. Ganter

If you are just getting into the subject, and even if you are not, I would recommend taking advantage of some good free resources, listed in no particular order:

Lattice Theory with Applications by Vijay K. Garg

Notes on Lattice Theory[complete pdf here] by J. B. Nation of the University of Hawaii

Chapter 1 - Lattice theory in Vaughan Pratt’s CS 353: Algebraic Logic course handouts

Dave Abrams "Order I Say" blog post, some of the above images are from his post, with his permission, thanks.

Lattice Tutorial by Nenad Jovanovic of Secure Systems Lab

Lecture 7 and lecture 8 of Lionel Levine’s course on Algebraic Combinatorics

Chapter 2 - Ordered Sets and Complete Lattices, A Primer for Computer Science by Hilary A. Priestley of the Mathematical Institute, University of Oxford

The Many Lives of Lattice Theory by Gian-Carlo Rota

Wolfram’s Mathworld on lattices

noreply@blogger.com (Geoff Moes) — Tue, 07 Aug 2012 12:35:00 +0000

As we all know the fields of computer science and software engineering are in their infancies. Many a blog post has been written lamenting the fact that software engineering is not a real engineering discipline, and while I have not written that exact post, I have written about the subject and have deconstructed what others have said about it. A number of these points do apply to why software projects routinely fail, yet another topic that has received considerable attention. Now admittedly all engineering disciplines regardless of their maturity and formalization have project failures and creating a real software engineering discipline will not eliminate this problem but one would hope that it would abate it.

I find it odd that at a time when so many people are involved in IT there seems to be little discernible progress in creating a real software engineering disciple. There are probably millions of people working on creating software. Also there are many researchers trying to solve this problem from many different angles. Practitioners have been attempting to solve it with ideas like Agile and Software Craftsmanship, etc. Additionally there is a long list of failures surrounding the formalization software engineering.

My biggest complaint is the fact that there really are no good formal standards in general software engineering principles and methodologies lack a formal foundation and even the more vague principles can be easily thwarted and misused, and often, as I have previously complained, it often ends up being based on pure opinion which is usually won through positional authority, perseverance or by those who are just more politically savvy.

The intent of this post is not to attempt to solve or even offer solutions to the problem of creating a real software engineering discipline but to look at what I think are some barriers to creating this discipline and in some of these cases offer thoughts on overcoming those barriers.

If we are to think software engineering as an engineering discipline, I challenge you to find another engineering discipline that routinely has practitioners with no formal training in the field. I very much doubt that some who did not hold a degree in engineering and who built a shed in his back yard is now working as a structural engineer on a construction project, the mere idea seems ludicrous. Yet I have worked with non technical degree holders who became software developers, one who started by building web pages and now calls himself an "Internet Application Architect", and is probably one of the biggest cargo cult coders I’ve ever had the misfortune to work with. This egalitarian aspect isn’t all bad as it does let good people into the field as well. Another non technical degree holder I once worked with became an accomplished developer and went on to get an advanced degree in CS and is now a CS professor. Although it’s probably the case that for every good non technical degree holder who joins the field it is likely that dozens of mediocre and bad practitioners will also join. It seems that in other engineering disciplines there are much more stringent educational requirements to ensure proper training. To be clear here I am not equating having a degree with being competent because I have met many incompetent people with degrees, but still you need something. I confess I am at a loss for a solution for this one.

Chemistry is a scientific discipline, chemical engineering is an engineering discipline, and you can make this comparison between other engineering disciplines and the sciences that they employ e.g. electrical, mechanical, and structural map to various areas of physics. Engineering and scientific disciplines are different types of disciplines often taught in separate schools. Although each engineering discipline has some scientific overlap and it would probably be possible to move from the appropriate scientific field to the corresponding engineering field in general you probably would not do so without returning to school. In recent years software engineering curricula have been added to the rosters of many colleges and while this is potentially a step forward, discounting for the moment that software engineering is still not really real engineering, a software engineering degree and a computer science degree in many cases gets you the same job!

So in other fields there would be a differentiation between a degree that would put you on a track to do scientific research and one that would put you on a track to do engineering work. As I understand it, if you are fresh out of school with a BS in CS that qualifies you to be a tester at Microsoft¹, developers hired right out of school need at least a Masters degree in CS. This is an extreme case of how this really breaks down in our industry. In most cases engineering practitioners are the software engineering, MIS, CS or even non technical degrees and the few scientific careers generally go to the advanced degree holders. I admit this probably fairly normal a BS in chemistry or biology is also more likely to get you a job in IT than a job as a research scientist. Still compared to more mature engineering fields there seems to be a lack of real differentiation between the degrees that yield a career as a software engineer versus one as a computer scientist.

The entry requirements for managers in software make the low entry requirements for software engineering practitioners look downright rigorous. I have previously criticized the fact that many organizations find the cheapest people, especially for software management and give them an obligatory certification. Now I know that engineering management regardless how formal or established the engineering discipline is an area that has problems and failures, but again I very much doubt that you would find a twenty something business or liberal arts major with a freshly minted PMP suffix managing construction or civil works projects. Yet in my experience this is pretty normal in IT especially in the government sector. Of course bad software management is executed by older managers as well.

A post by Larry White titled "Engineering Management Is Dying" delves into some these issues. It is definitely the case that methodologies like Agile have changed how software projects work and the traditional corporate management approach to software really doesn’t work. One point he makes is that it is not uncommon to see a two hundred person project at Google headed by an engineer. To me this implies that someone is in some way managing that project. I think all of this is indicative of the need for software engineering mangers to also be practitioners in engineering or at least very well versed in how software development works. The situation he talks about at Google is not the case everywhere, in that case the company is its own client, but there are many cases where software is being built for clients and this does create a need for management that deals with the client, perhaps this should be a role that is separated from management and called a client liaison, which is what often happens. Also I am not sure how things work at Google but I have also seen internal development in organizations where the IT department provides services to an internal client, I have also seen this go horribly awry with contentious unproductive relationships between departments. In short I feel that just as we need a real software engineering discipline we also need a real incarnation of software engineering management.

Most practitioners do not keep up with, or read academic research, actually many practitioners don’t read at all, but that’s another issue, and most academicians don’t work in the field so they lack the hands on knowledge. Unfortunately this rift can take on a somewhat disdainful tone as is the case in my exploration of one practitioner’s attempt to define "Real Engineering". Fortunately some people, I’d like to count myself among them, take a more constructive approach to building bridges across this rift. Daniel Lemire has an interesting critique the quality of software produced in academia.

I think the solution here is for both sides to become more engaged in problems faced on each side. I am optimistic about this one as I feel that these walls are breaking down as the field is growing up and many of the emerging technologies are forcing developers to be more cognizant of and engaged in research topics. I also have encountered much more research that has ties to the practical concerns of day to day software development, some I have mentioned with more to come.

If you read my blog you know it to be a mix of math and software practices. I would describe myself as a software practitioner and a math enthusiast. My math journey has taken me on some interesting math excursions into areas of math that seem to get little or no mention in CS curricula and I feel that this is a major problem in really applying math to the field of software engineering. Another problem is in the way that it is taught, my experience was that it was not only taught badly but in a way that made it seem irrelevant to many of the programming courses. Specifically I would shift the CS math curriculum to include less differential and integral calculus and include more logic, combinatorics, abstract algebra, graph theory, order theory, category theory and probably some topology among others.

Over the last few years I have been progressively learning more math which has been in part motivated by necessity for understanding research papers. This approach has changed the way I see things, I now see the patterns of math in software. They are there and I believe that they can be exploited to create a real software engineering discipline.

For the math learning problem I do have some ideas many of which are expressed in my blog. Some of my posts like refactoring if statements with Demorgan’s Laws or the String Monoid, the Object Graph, etc. are about making these mathematical ideas more relevant and accessible to programmers. Other posts like my series on naming and my post on generic programming and entropy and complexity are about my own ideas and ideas in the research literature that I feel may help to create a real software engineering discipline. These are my attempts at solutions to these problems, so expect more of both of these and more thoughts on the CS math curriculum.

This is one that really bothers me. I feel the software architect role in general has a very negative effect on creating quality software and it dissuades the industry from developing a real engineering discipline. The Software Architect role tends to be broadly defined, you have enterprise architects, software architects, etc., some architects tend to be involved with hardware and networking, some work on configuration management, some do software design, some do all of these things and more. I feel this is a problem as each of these is a separate engineering area with different types of problems. By not breaking these down it often leads to a lack of focus on specific problems, also I have seen cases where the architect focuses on their preference and ignores other issues. The architect role is often divorced from the code. I have met many architects that were responsible for software but had never even looked at the code. To me this is a huge failing that architects that are responsible for building software often lack the interest, time, or even aptitude to know the quality or underlying of structure of the software that they are delivering.

To really do justice to these ideas I might need a separate post, my solution would be to break down the architect role into specific engineering roles, which could include:

Software Process Engineering - this would be involved with software team and resources planning, some aspects of configuration management such as defining policies, requirements analysis and general project management aspects of software construction including the definition and refinement of the SDLC. This role is tightly coupled with software engineering management.
Software Structural Engineering - this would include requirements comprehension, code infrastructure planning, prototyping work, hands on code structural work including custom frameworks and reusable components, third party library products, and general code quality including reviews and static analysis.
Software Quality Engineering - This would include the QA roles, software testing and testing tools, requirements validation and refinement, usability and reliability and general software quality issues.
Software Infrastructure Engineering - This would include hardware, networking, database, app server and general service infrastructure, non functional requirements fulfillment and possibly the implementation of configuration management, continuous integration, etc.

This is a rough "sketch" of these possible roles and each of these areas has some overlap implying that all of the people in these roles would work closely together, also some combination of, or all of these roles might be performed by a single individual depending on the organization’s size and structure. What this approach does is clearly defines roles and responsibilities as opposed to some nebulous software architect role.

A young CEO once commented that he thinks young programmers are superior. In general companies prefer younger workers as they often don’t have family commitments so they can work more hours and you can pay them lower salaries, DC area government contractors rely on this to keep their profit margins up.

As an older developer I often find this frustrating. I confess that I have not moved up the ladder and still mostly work as a developer or what might be called a hands on architect, yes I know but that’s the current term, actually my preferred title would be: Software Structural Engineer. Working as a contractor I have on several occasions found myself on projects that were dominated by younger developers and unfortunately on more than one occasion I watched as teams would make many mistakes due to a lack of experience, in some cases I was able to help in others I was ignored by the younger developers. This is not to say that I do not still make mistakes, I’ve just been around long enough to have made a lot of them already.

If you buy into the software craftsmanship thing, I admit to being skeptical of this idea, you might be inclined to draw a parallel to craftsman of the past when older established masters took on apprentices and passed on their wisdom to the next generation. Given the access to information these days such process is somewhat antiquated and perhaps impractical. Nevertheless I feel, and the industry supports me here, that older developers who keep their skills up to date have value. I know several younger developers who have sought me out to learn from me so I think I can safely say I still have some value.

Many older developers have let their skills get rusty and have not kept up on current technologies I have seen this many times. Also many companies seem to lack the vision to allow for real hands on technical career growth. I can’t help but feel that this inclination to recycle developers in each new generation is hurting or at least slowing our ability to develop a real software engineering discipline, this potential loss of continuity seems like it leads to some lost wisdom.

As I write this Hollywood gears up to deliver a reality TV show that takes place in silicon valley and Mark Zuckerberg now gets the paparazzi treatment. Another article that I previously mentioned was about how CS enrollment was up because the movie The Social Network had enticed many aspiring Zuckerberg wannabes. At present there does seem to be a gold rush mentality and it is noticeable and even discussed on sites like Hacker News.

As someone who has never worked in the valley I am very much an outsider and may not have a good perspective on these things, but it seems that there are a lot of startup companies focusing on crap. Now I get it. We live in a shallow consumer society with a rapacious appetite for crap. But are not these supposed to be some of the smartest people and I am not the only one to wonder why so many smart people who should have better taste and higher standards are settling for working on serving up ads and other vapid crap instead of doing more meaningful work like working on real problems that would advance human society or even just work on advancing software engineering. Maybe I’m just jaded, so I will leave you with this and of course my apologies to Allen Ginsberg:

I saw the best minds of my generation wasted by working on serving up ads,

dragging themselves through the startups in the valley looking for an instant cash fix,

angelheaded hipsters burning for the venture capital connection to the better life in the consumer culture,

...

¹I believe this was the case in the late 90’s and may have changed, this information was conveyed to me by a former Microsoft employee.

noreply@blogger.com (Geoff Moes) — Tue, 17 Jul 2012 19:10:00 +0000

In my previous posts on naming I have laid the foundation for a framework for naming in software systems. This post is mostly a rehashing of those previous ideas and is intended to both codify and consolidate the definitions of terms upon which I have chosen and created to build a naming framework. It also serves as a single location to concisely reference these ideas. To gain more insight into the background and development of these ideas see my previous three posts: "A Survey of the Conventional Wisdom on Software Naming", "More Thoughts on Formal Approaches to Naming in Software", and "Software System Morphology". The definitions are as follows:

Name – The Signifier that consists of a string of characters that refers to a System Referent.
Name Unit Separator – is a mechanism to separate name units within a Name, this can be an explicit character such as "-" or "_". It can also be in implicit mechanism such as the use of Camel Case within the name.
Name Unit – Is the smallest lexical unit of a Name usually separated by a Separator (Name Unit Separator) and is used to describe the lexical structure of the Name.
Named Scope Context – this is the location of the Name within the system, e.g. where the name usage occurs.
System Referent – This is the actual instance of a thing that is named and is used in the system. See System Referent Type for specific types of System Referents.
System Referent Type - This is the specific type or class, as in classification, of what a System Referent is in a system some examples include:
- 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

System Morpheme – This is a conceptual unit of meaning in a system that is used in a name, it is distinguished from a Name Unit in that a morpheme can consist of one or more Name Units.
System Natural Language Set – This is the set of Natural Languages used to create the names. It is often English but it need not be and a system could include components or be constructed in a way that might include hybridization between multiple natural languages.
Problem Domain - This is the Semantic Domain that describes problem area for which the system solution is targeted. This would be a set of concepts and System Morphemes that apply to the problem domain. For example a financial system would be built using the relevant financial terms and language concepts.
Solution Domain – This is the Semantic Domain that describes concepts that are used to implement the system including System Morphemes that apply to the solution domain. This might include things like terms that describe Design Patterns, data structures, etc.

As you can see from above these Ideas can be separated into two categories: Structural and Semantic. However the two categories are not completely independent of each other so there is some overlap and interdependence. The structural ideas include: Name Unit, Named Scope Context, System Referent, and a System Referent Type. Each Name has these properties as attributes. A name has a lexical structure made up of Name Units, and refers to a System Referent of some System Referent Type and has one or more locations given by its Named Scope Context(s).

The semantics of the names which has the "unit" described by the System Morpheme idea has semantic properties which will fall into either the Problem Domain or the Solution Domain. The expression of these concepts is dependent on the System Natural Language Set, in other words the natural languages that are used to construct meaningful names for concepts in both the Problem Domains and the Solution Domains.

This is the current state of my thinking on this. These ideas will be refined and might change over time, the objective is to develop something that is useful and that both supports and can be validated by a more analytic approach.

noreply@blogger.com (Geoff Moes) — Sun, 15 Jul 2012 12:45:00 +0000

Are We on the Verge of the Next Renaissance?

On 31 October 1517, Martin Luther sent to his bishop Albert of Mainz a copy of his "Disputation of Martin Luther on the Power and Efficacy of Indulgences", which came to be known as The Ninety-Five Theses. In January of 1518 he also sent copies to his friends who translated it from Latin to German and had copies printed and passed them on. In part because of easy mechanized printing it went viral, within two weeks it had spread throughout Germany and in a month throughout all of Europe. The rapid propagation of his leaked private communication caught Luther by surprise and he soon found himself in a full on “flame-war” directly with the Pope. Luther quickly mastered this new mass media and effectively used it in his fight. This early landmark public dispute in the emergent mass media of the time demonstrated a new power structure built on the rapid spread of ideas.

Guttenberg’s motivation for inventing the printing press, an idea that had also been invented previously in Asia, was strictly entrepreneurial and it was not his first venture. Shortly after the introduction of the printing press to Europe, other entrepreneurs realized that there was a demand for books. In some respects the printing business of the late 15^th and early 16^th centuries was very similar to the internet boom that we are currently experiencing. This new technology not only caused the creation of new businesses but it also transformed the dissemination of information and the power of information itself in the sense that new information could be more easily created and collaboratively built and referenced also language was standardized and local vernacular languages replaced Latin for scholarly works. This new more egalitarian access to books and information fueled the spread of ideas, and caused an exponential surge forward in the ability develop science and technology and culture itself.¹

There was a dark side to this new change in the way information was disseminated. The Catholic Church, which held a monopoly on the dissemination of religious information², reacted by banning some of the books and publishing its own propaganda including lists of banned books, also the Tyndale Bible written in English was banned in England until Henry VIII broke with the Catholic Church. An inquisition was directed towards the book publishing capital of Europe, Venice, due to the publication of scientific books which contradicted the beliefs of the Roman Catholic Church. Books were banned and burned and heresy trials were held.

There were several inquisitions which were heinous affairs that included racial cleansing, torture, and other barbaric acts of terror. These were started before the advent of the printing press but were then directed towards this new threat. Fortunately the inquisitions eventually died out.

It is thought that this transformation in the spreading of ideas, coupled with the previous reintroduction of earlier Greek, Roman and Arabic knowledge fuelled an expansion of scientific understanding which also transformed art in terms of perspective and anatomical representation was a catalyst for the Renaissance. All of this makes me wonder about the future possibilities of our current era and what similar parallels we could see from that previous “information technology” revolution when the dissemination of information made an exponential leap forward from the old technology, much the same way as we are experiencing an exponential leap forward in information technology.

We now live in an era in which I can download hundreds of books or the equivalent amount of information in minutes more than I can comprehend and software is rapidly evolving to allow me to more effectively deal with large quantities of data I can search, jump, skim, and view almost anything about any subject effectively instantly, the time that it takes to send text, audio, images and video has been reduced almost to the speed of light and that’s how quick we can get real time information from all over the world and from space. We also continuously receive an increasing amount of data from various places in the solar system and even at the edge of the heliosphere.

The very tools to better manipulate crunch and comprehend large petabyte and beyond data are rapidly being invented and refined, the things that we will be able to do in even the next decade(s) is probably going to be revolutionary for human society in terms of art, science and how we live our lives, the changes are already quite pronounced. Soon images, audio, and video will be as searchable and easily manipulated as text is now and algorithms enhanced with more and more math will be able to digest all of this and allow us to query it and manipulate it ways we probably can’t even imagine yet.

From the sixteenth century until the end of the twentieth century publishing grew into a vast industry expanding from books to encompass more such as periodicals. Other entire industries were spawned from it such as the newspaper industry. This spawned new media like audio, radio and recording, movies and video that grew into entire industries. Then along came the internet and fast data transmission. All of these industries are now under pressure and many are fighting this change. Now it would be a bit overly dramatic to compare the copyright wars to the inquisition but the parallel is there: large organizations in control of the dissemination of information fighting the change, more egalitarian information access and distribution. Another common thread is the use of law, the Catholic Church tried to impose its law on the local European governments to stamp out heresy. We now find ourselves in a similar position with the established media companies using their deep pockets to attempt to write new laws that benefit them at the potential cost to a free internet and innovation, so far legislation like the Research Works Act and SOPA have failed but the fight continues. Patents especially broad and abstract patents are another threat to innovation this is another system that has been gamed by the big corporations so that it now often does the opposite of the original intent of the founding fathers.

So we now find ourselves at a unique time where there is so much potential for innovation in science and art and hopefully society. These human endeavors are built on collaboration and on the sharing, remixing, and refining of ideas. Many of Shakespeare’s works were derivative of earlier works, can you imagine if the same type of laws and litigation existed then, such works may have never been created.

How this potential innovation will it play out over the next two decades may very well be beyond comprehension, the things I can buy today were the devices of science fiction, specifically Star Trek, when I was growing up, even as a young adult, the idea of having a thousand books on a tablet device or watching real time video from the space station or access to terabytes of data was almost beyond my expectation, yet now I am starting to take it for granted. My childhood almost seems like the life of a 15^th century turnip farmer who could only dream of reading scientific or any knowledge in a book.

¹ Much of this is excerpted from Episode 4 of The Day the Universe Changed by James Burke

²The bible and all sermons were held in Latin restricting non-ecclesiastical people direct access religious doctrine.

noreply@blogger.com (Geoff Moes) — Mon, 28 May 2012 21:37:00 +0000

Lucene is built on classic IR (Information Retrieval) Math concepts that are actually pretty old by current standards in our industry, with most of its roots from the 1970’s and some of them like the Boolean Model being quite a bit older. Still that’s a solid quarter century older than search techniques like Pagerank and yet it can be a central and almost necessary technology used in many systems. The mathematical domain of searching in Lucene relies on ideas like similarity measures which also relates to other disciplines that are used in Data Mining and Machine learning. The basic ideas of Lucene and IR provide a nice introduction to these ideas and I want to focus on the following classic IR topics:

Lucene is built on the idea of Documents, which can be thought of as a collection of terms. Think of a document as a web page or book and think of the terms as the words and in some cases phrases. Lucene uses an Analyzer to tokenize the text, for example you may want not want to include Stop Words like [the, and, to, a, ...] in your index also indexes can be built using the concept of N-Grams take the expression "Information Retrieval" for example, you might want to treat this as a single term as opposed to breaking it up, there are also Analyzers that do Stemming and even phonetic analysis. The tokenizing process is involved but that should give you a basic idea, more can be found here. Tokenization allows the terms to be defined, identified and parsed and it is the properties of terms in relation to the documents which drive the Boolean Model, the Vector Space Model and tf*idf.

The Boolean Model treats documents as vectors of boolean indicators, this is a brief summary of ideas discussed in chapter one of Introduction to Information Retrieval, I am borrowing part of the example from that chapter:

This is an incidence matrix that shows which terms are in which documents. This representation can be viewed as either a set of columns which form binary vectors indicating which term occurs in each document or it can be viewed as a set of binary term-vectors which shows which shows which documents contain a given term. This example is also a bit deceiving in that these vectors will be pretty sparse, The Tempest and Othello document vectors (columns) and the Cleopatra and Calpurnia term vectors (rows) are more indicative of this sparseness at this small scale. Whether we store and search this data as a full matrix or individual vectors it would require a lot of space and the space would be mostly zeros, so a better structure to store and search this is used, the inverted index, the details of which are covered in chapter one of Introduction to Information Retrieval and Apendix B of Lucene in Action.

The queries on this structure take the form of standard Boolean logic including: Logical Conjunction, Logical Disjunction and Logical Negation. An example is (again taken from Introduction to Information Retrieval with some notational modification):

To answer the query we create a vector (q) [Brutus AND Caesar AND NOT Calpurnia], we take the Boolean vectors for Brutus (b), Caesar (c_s) and Calpurnia (c_l), complement the last, and then do a bitwise AND, where all Boolean vector operation are bitwise operations, this can all be denoted as follows:

The resulting term vector for this query yields: [Antony and Cleopatra, Hamlet] vector positions one and four.

In the above example you can see using the column vectors shows how the inverted index structure works. Here we are indexing into the corpus based on the terms not on the documents. So where a document is usually a collection terms (a column) we have inverted this document/term relationship and are now using the term/document relationship to link to the documents (rows). The inverted index structure in Lucene is built on listing terms and then linking to the documents, in Lucene each document is given an integer document id, so each term has a list of document ids that contain the document. The inverted index structure can include other information such as the position in the document or other metadata.

The inverted index is the same concept as something known as a concordance, which is a list of words and their positions in a work used by scholars. A famous example is one that was published for the Dead Sea scrolls by the team who exclusively controlled them, but the published images of the scrolls at a very slow pace which left many unpublished and this created a researcher monopoly on the scripts which upset many researchers who did not have access. In 1988 Ben Zion Wacholder used a computer to reconstruct 17 documents from the concordance, these were published in 1991. Coincidently the same month a complete set of facsimiles were discovered at the Huntington Library and published breaking the monopoly on the scrolls, they are now available free on online, as they should be.

tf*idf stands for Term Frequency – Inverse Document Frequency which is basically the Term Frequency multiplied by the Inverse Document Frequency. In 1972 Karen Sparck Jones published a paper proposing what has become known as Inverse Document Frequency (idf) it is defined as:

Where |D| is the size of the set of all of the documents and |d_t| is the number of documents that contain the term, this formula is effectively the log of the inverse of the estimated (uniform) probability that a term will occur in a document, which would be given by the formula:

This can be rewritten as:

Using the logarithmic identity, this is needed since a log of a probability, which is less than or equal to one, will always be either a negative value or zero:

The interesting thing about using logs is that it makes the idf terms addable for example if we want to compute the Inverse Document Frequency for term one and(∧) term two, assuming they are mutually exclusive which means the probability P(x ∧ y) = P(x)P(y) is multiplicative:

The additive property is due to another logarithmic identity, which also forms a group isomorphism between multiplication of positive real numbers and addition of real numbers:

Now to get tf*idf we need to multiply the Term Frequency which is the number of times the term occurs in the document with the Inverse Document Frequency, the complete formula is:

When I learned about this I immediately thought of the formula for Information Theory:

It turns out that this has been thought of and debated and is not really correct, a topic that is fairly involved and you can read more about it this paper by Stephen Robertson. The ideas above about the logarithmic properties of addition in idf are taken from this paper.

Basically tf*idf is a term weighting mechanism which maps documents and terms to real numbers and we need this for the next piece of the puzzle.

The Vector Space Model

One problem with the Boolean model is that it either gives too many results or too few. In the example above a Shakespearean "micro-corpus" was used to demonstrate how it works but in real corpus a query like that could potentially retrieve thousands of documents which would make it impractical to attempt to wade through the result set. This is where a weighting mechanism like tf*idf comes in, it effectively maps the boolean values to values in the domain of Real Numbers, well technically floating point numbers. The vector space model uses the columns of the incidence matrix above which are the vectors of terms for each document where each term position in the vector is calculated using the tf*idf weighting scheme. These document vectors exist in a Vector Space and a query can be constructed as a vector and each document can be compared to the query vector using the angles between the query vector and the document vectors (α, θ) to determine which documents (d₁,d₂) best answer a query (q), shown visually above. Also you should note that this is a simple two dimensional example, in reality there will be a dimension for each additional term which becomes a hyperdimensional vector space consisting of hundreds or even thousands of dimensions.

It is not the angle between vectors that is calculated but the cosine of the angle, which is known as the Cosine Similarity, this is used as it is easier to calculate than the angle itself, the formula is:

The numerator is the Dot Product of the two vectors, a query vector and a document vector, the denominator is the product of the Euclidean Norm or Magnitude of the two vectors. The above equation can be written as follows with the expanded Dot Product and Euclidean Norm calculations:

tf*idf is designed to increase as the number of occurrences of the term increase in a given document It should also be noted that the Vector Space Model can be built with other term weighting mechanisms other than tf*idf. More information can be found in "Cosine Similarity and Term Weight Tutorial", in chapter six of Introduction to Information Retrieval and Lucene specific information on scoring.

Extending our example from above we can calculate our weights, first the idf values:

	D	d_t	Idf
Antony	6	3	0.69314718
Brutus	6	3	0.69314718
Caesar	6	5	0.18232155
Calpurnia	6	1	1.79175946
Cleopatra	6	1	1.79175946

From a Shakespearean concordance we can get the number of occurrences for each term:

	Antony and Cleopatra	Julius Caesar	The Tempest	Hamlet	Othello	Macbeth
Antony	157	61	0	0	0	1
Brutus	3	112	0	1	0	0
Caesar	159	145	0	2	1	1
Calpurnia	0	10	0	0	0	0
Cleopatra	56	0	0	0	0	0

Using the idf values and term frequencies we can calculate tf*idf for our documents:

	Antony and Cleopatra	Julius Caesar	The Tempest	Hamlet	Othello	Macbeth
Antony	108.82410	42.281978	0	0	0	0.69314718
Brutus	2.0794415	77.632484	0	0.69314718	0	0
Caesar	28.989127	26.436625	0	0.36464311	0.18232155	0.18232155
Calpurnia	0	17.917594	0	0	0	0
Cleopatra	100.33853	0	0	0	0	0

I will leave calculating a query as an exercise for you, if you are feeling so inclined or masochistic.

Lucene uses a combination of the Boolean Model and the Vector Space Model, when the query is run the documents are first "approved", selected, by the Boolean Model and then scored by The Vector Space Model. I believe this approach offers two advantages. First it would reduce the number of calculations to search the Vector Space since you aren’t really searching it and limiting your calculations to a subset. Secondly the Vector Space Model does not handle negation in queries, and I am not sure how negation is handled in Lucene in regards to scoring. Actually there have been a number of IR tweaks and improvements for flexibility and efficiency that have been incorporated into Lucene and I confess I have only scratched the surface in both my coverage here and current knowledge.

noreply@blogger.com (Geoff Moes) — Sun, 13 May 2012 19:24:00 +0000

In my previous posts on naming "A Survey of the Conventional Wisdom on Software Naming" and "More Thoughts on Formal Approaches to Naming in Software" I discussed several ideas about defining a way to talk about software system naming, I feel the name "Software System Morphology" captures this "big picture" concept. My objective is to develop a comprehensive way to define and analyze the semantic nature (morphology) of the construction of a software system. It’s an ambitious undertaking and whether or not I succeed in this endeavor I am hoping that these ideas will contribute to a better solution to this problem.

To review, I am defining three attributes that a name of signifier can have, the name scope context, i.e. where the name is used or occurs, the type or class of the system referent signified by the name, and the lexical structure of the name i.e. the n-gram of name units. I feel that these three qualities can be used to determine and possibly measure aspects of the morphological structure of software and by determining the morphological structure of a software system that structure might be "comprehended" and refined which could yield higher quality software.

In Linguistics a morpheme is the smallest unit of meaning and it is considered, by some, to be a complete sub-discipline of the study of Linguistics. I admit that I am in the process of learning more about it, I am a few chapters into What is Morphology by Mark Aronoff and Kirsten Fudeman it is an excellent book for linguistic neophytes like me. Software System Morphology will both be divergent and dependent on natural language morphological concepts, which are quite complex. However a general understanding of linguistic morphology will make these ideas more accessible, I suggest looking into it on your own, it’s fascinating and worth it solely on its own merits. A quick example of English Morphology can be given with the morphologically complex word autobiography which consists of the morphemes: auto/bio/graph/y, where [auto] means "self", [bio] means "life", [graph] means "drawn" and [y] means "characterized by".

In my first post of this series I explored various ideas proposed by a few prominent software engineers, one idea that I discussed was the use of what were denoted as qualifiers which included the scope qualifier, the type qualifier and the computed-value qualifier. These qualifiers which are prefixed or suffixed to names can be thought of more generally as morphemes. So we can now incorporate those ideas into a more general way of looking at meaning in software naming. Now the natural conclusion, if you have been paying attention, may be to assume that the name unit concept will map to the morpheme concept, it does not, at least in terms of only software morphology and this is in interesting distinction, software morphemes may consist of n-grams of name units which can be natural language morphemes two examples are CommandPattern and MedicalRecord where separating these into individual name units potentially become meaningless in certain software contexts.

Software System Morphology is primarily influenced by three things, the semantic nature of the problem domain(s), the semantic nature of the solution domain(s), which include languages ORMs, paradigms, design patterns, data structures, and finally the natural language(s) in which both the problem domain and solution domains are expressed. The previous example items CommandPattern and MedicalRecord illustrate these ideas as well.

Ok now let’s take our concepts further with a more detailed example. Assume we have a Hospital Medical system which has the following problem domain concepts: [Medical Record, Patient, Visit, Doctor, Hospital, Address, Invoice]. Obviously there are more. For the solution domain we will assume a JEE/Spring style implementation which might include the following concepts: [Entity, Dao, ServiceLayer, Controller, Map, View]. Now some expected names (signifiers) might be: MedicalRecordEntity, PatientEntity, PatientServiceLayer, PatientDao, PatientController, PatientView, VisitEntity, VisitDao, VisitServiceLayer, VisitController, VisitView, PatientVisitMap, PatientHospitalVisitor,... Now as you can see the names are composed of morphemes from both the problem domain and the solution domain. This is to be expected as each name tells what it is/does in the problem domain and what it is/does in the solution domain. In fact any developer with knowledge of JEE Spring Web application developer can look at these names and know what to expect and where they fit in the system. Additionally it is easy to look at the above set of domain concepts and anticipate named system referents that I omitted.

Previously I pointed out that the idea referred to as a qualifier is really a morpheme and while this is true the term qualifier seems to denote a more contextual setting in terms of the domain concepts. In the above examples the solution domain morphemes act as qualifiers telling where and how each named system referent fits into the solution Entity tells that it is a domain object, Dao tells that it relates to persistence, ServiceLayer tells that one would expect to see a separation of concerns that would put the business logic here. Structurally one would expect the domain objects (with the Entity suffix) to be passed back from the Dao’s and ServiceLayer’s and there might be transformative manipulation or aggregation of the domain objects in the ServiceLayer. The idea of qualification is meaning based but in this case it also indicates structural aspects of the solution domain. In this example I intentionally use the Entity suffix, in many systems the domain concepts would be used alone i.e. [Patient, Visit], I have mixed feelings about this in one sense it can be viewed as potentially unnecessary, in another sense it represents a qualifier that can possibly improve comprehension. Qualifiers do make names longer and while I tend to favor longer names it can become problematic if they get too long. These ideas towards naming are powerful for building comprehensible maintainable code as you can see from the above name examples that they follow a consistent pattern, admittedly these are fairly easy naming tasks, but you would be surprised how many developers fail to even do these types of things consistently.

Unlike others who advocate specific practices in regards to naming I feel that naming should be dealt with in a flexible framework that can be adapted to a specific project’s needs. While I personally agree and disagree with ideas previously discussed, my philosophy is that naming should be done consistently and comprehensively reflecting deliberate choices using conceptual understanding and analysis of the Domains. Also it should be tracked in a Lexicon, an idea that I am working on and hope to explore in a later post. Also as I have said before I feel that tooling could be used to allow better conceptual understanding and navigation and the use of analytics and possibly visualization could be used to ease naming decisions in practice by providing improvements to both static analysis and interactive autosuggest/intellisense aids.

I feel that these ideas are an attempt to create a more "formalized" approach to what Eric Evan’s does in Domain Driven Design which also covers a number of other structural ideas, I hope to extend my ideas here to better integrate some of those as well. The next steps for me are to undertake an analytic approach I also hope to explore the application of ideas like formal concept analysis and spectral graph theory techniques which may add some mathematical rigor to these ideas and perhaps allow some empirical validation and probably refinement. Now it gets really hard so it might be a while for those follow-ups.

noreply@blogger.com (Geoff Moes) — Sun, 29 Apr 2012 21:12:00 +0000

Over the course of my career I have strived to write reusable code, always looking for more general patterns and trying to refactor code to more flexible more generic versions sometimes with mixed success. Lately it has become something of an obsession of mine in that I both try to employ it and have been endeavoring to learn more about it, what it really is, and how to do it right, as I have previously pondered I believe there is a complexity cost with increased reuse. Over the last few years, which I have been programming in Java, generics has become a central tool in achieving reuse. So such a concept comes to mind but it is just one idea in a larger framework of ideas on generic programming.

There is a fair amount of research and discussion of the ideas pertaining to generic programming, the title of this post is taken directly from a paper on the topic, which perhaps not so coincidently was presented at the same OOPSLA (2005) as the paper on Software Reuse and Entropy that I previously discussed. It just seems like every idea I explore is super-interrelated to everything else and this post will be no exception, I can conceptually connect these two papers using a Kevin Bacon like approach using just two other research papers, ideas I have for other posts. I will try to keep this one as focused as possible. Also the referenced paper is, like the Software Framework paper, very math heavy but different math, Category Theory,Order Theory, Universal Algebra, etc. This post will focus on more high level concepts and not the details of math that I wish I could claim that I fully understand.

So back to our question, what is generic programming? For me it is about reuse, and while the information entropy approach to understanding reuse was about reuse from perspective of measure and the reuse (measurable) variation on different domains, I feel that the generic programming concept is about the structure of reuse and how it is implemented in various programming paradigms but the concept itself transcends language specific interpretations and implementations.

As you can tell I am not sure how to exactly answer this question so I will defer to the experts.

"What is generic programming?" in part outlines the paradigmatic distinctions between mainstream OO languages (Java Generics, C++ with STL) and Functional languages (Haskel, Scheme):

As for most programming paradigms, there are several definitions of generic programming in use. In the simplest view generic programming is equated to a set of language mechanisms for implementing type-safe polymorphic containers, such as List<T> in Java. The notion of generic programming that motivated the design of the Standard Template Library (STL) advocates a broader definition: a programming paradigm for designing and developing reusable and efficient collections of algorithms. The functional programming community uses the term as a synonym for polytypic and type-indexed programming, which involves designing functions that operate on data-types having certain algebraic structures.

In "Generic Programming" written in 1988 by David A. Musser and Alexander A. Stepanov use Ada and Scheme and describe generic programming as:

By generic programming, the definition of algorithms and data structures at an abstract or generic level, thereby accomplishing many related programming tasks simultaneously. The central notion is that of generic algorithms, which are parameterized procedural schemata that are completely independent of the underlying data representation and are derived from concrete efficient algorithms.
...
A discipline that consists of the gradual lifting of concrete algorithms abstracting over details, while retaining the algorithm semantics and efficiency.

That last sentence has a very Agile/Refactoring feel to it.

Ralf Hinze in "Generic Programs and Proofs" describes it as:

A generic program is one that the programmer writes once, but which works over many different data types.
...
Broadly speaking, generic programming aims at relieving the programmer from repeatedly writing functions of similar functionality for different user-defined data types. A generic function such as a pretty printer or a parser is written once and for all times; its specialization to different instances of data types happens without further effort from the user. This way generic programming greatly simplifies the construction and maintenance of software systems as it automatically adapts functions to changes in the representation of data.
...
So, at first sight, generic programming appears to add an extra level of complication and abstraction to programming. However, I claim that generic programming is in many cases actually simpler than conventional programming. The fundamental reason is that genericity gives you "a lot of things for free" ...

This last statement resonates with me as it parallels my thoughts on the desirability of using software frameworks and I feel that I continuously have this conversation (argument) with junior level programmers and also senior level cargo cult coders who don’t get it.

Design Patterns are a common generic concept in mainstream programming. It turns out that a number of design patterns can be described in the framework laid out by these papers and a number of papers do exactly that including "Design Patterns as Higher-Order Datatype-Generic Programs " part of extensive research on the topic by Jeremy Gibbons:

Design patterns, as the subtitle of the seminal book has it, are ‘elements of reusable object-oriented software’. However, within the confines of existing mainstream programming languages, these supposedly reusable elements can only be expressed extra-linguistically: as prose, pictures, and prototypes. We believe that this is not inherent in the patterns themselves, but evidence of a lack of expressivity in the languages of today. We expect that, in the languages of the future, the code parts of design patterns will be expressible as directly-reusable library components. The benefits will be considerable: patterns may then be reasoned about, typechecked, applied and reused, just as any other abstractions can. Indeed, we claim that the languages of tomorrow will suffice; the future is not far away. All that is needed, in addition to what is provided by essentially every programming language, are higher-order (parametrization by code) and datatype-generic (parametrization by type constructor) features. Higher-order constructs have been available for decades in functional programming languages such as ML and Haskell. Datatype genericity can be simulated in existing programming languages [2], but we already have significant experience with robust prototypes of languages that support it natively [2]. We argue our case by capturing as higher-order datatypegeneric programs a small subset ORIGAMI of the Gang of Four (GOF) patterns. (For the sake of rhetorical style, we equate ‘GOF patterns’ with ‘design patterns’.) These programs are parametrized along three dimensions: by the shape of the computation, which is determined by the shape of the underlying data, and represented by a type constructor (an operation on types); by the element type (a type); and by the body of the computation, which is a higher-order argument (a value, typically a function). Although our presentation is in a functional programming style, we do not intend to argue that functional programming is the paradigm of the future (whatever we might feel personally!). Rather, we believe that functional programming languages are a suitable test-bed for experimental language features - as evidenced by parametric polymorphism and list comprehensions, for example, which are both now finding their way into mainstream programming languages such as Java and C#. We expect that the evolution of programming languages will continue to follow the same trend: experimental language features will be developed and explored in small, nimble laboratory languages, and the successful experiments will eventually make their way into the outside world. Specifically, we expect that the mainstream languages of tomorrow will be broadly similar to the languages of today — strongly and statically typed, object-oriented, with an underlying imperative mindset — but incorporating additional features from the functional world — specifically, higher-order operators and datatype genericity

Lately I have been making more of an effort to learn Scala. Bruno Oliveira and Jeremy Gibbons make the case in "Scala for Generic Programmers" that it might be one of or even the best language for expressing Generic Programming concepts in part due to its hybridization of object oriented and functional paradigms. Here is the abstract in its entirety:

Datatype-generic programming involves parametrization by the shape of data, in the form of type constructors such as ‘list of’. Most approaches to datatype-generic programming are developed in the lazy functional programming language Haskell. We argue that the functional object-oriented language Scala is in many ways a better setting. Not only does Scala provide equivalents of all the necessary functional programming features (such parametric polymorphism, higher-order functions, higher-kinded type operations, and type- and constructor-classes), but it also provides the most useful features of object-oriented languages (such as subtyping, overriding, traditional single inheritance, and multiple inheritance in the form of traits). We show how this combination of features benefits datatype-generic programming, using three different approaches as illustrations.

So far for me Scala has been a joy. Its features and flexibility are beautifully elegant of course I am tainted coming from the clumsy, clinking, clanking, clattering caliginous world of Java, BTW Java we need to talk, it’s not you, it’s me. I’ve met someone else.

Jeremy Gibbons Makes the following point in "Datatype-Generic Programming":

Generic programming is about making programming languages more flexible without compromising safety. Both sides of this equation are important, and becoming more so as we seek to do more and more with computer systems, while becoming ever more dependent on their reliability.

This idea is similar to ideas that Gerald Sussman explores in his talk at Strangeloop 2011 "We Really Don’t Know How To Compute". However, his general and perhaps philosophical approach to the idea of generic programming is very different from the previous ideas:

[8:40]We spend all of our time modifying existing code, the problem is our code is not adequately evolvable it is not adequately modifiable to fit the future in fact what we want is to make systems that have the property that they are good for things that the designer didn’t even think of or intend. ... That’s the real problem. ... The problem is that when we build systems whatever they are we program ourselves into holes. ... It means that we make decisions early in some process that spread all over our system the consequences of those decisions such that the things that we want to change later are very difficult to change because we have to change a very large amount of stuff. ... I want to figure ways that we can organize systems so that the consequence of the decisions we make are not expensive to change, we can’t avoid making decisions but we can try to figure out ways to minimize the cost of changing decisions we have made.
...
[11:40]Dynamically extensible generic operations ... I want to dynamically extend things while my program is running ... I want a program to compute up what it is going to do.

He shows an example[19:00] which is "the definition of the method of computing Lagrange Equations from a Lagrangian given a configuration space path". This is apparently easy stuff, to him at least. Fortunately you don’t really need to understand the details of this math to understand his points here:

[20:45]This is a little tiny feeling of what is it needed to make things more flexible consider the value here, the value is that I am dynamically allowed to change the meaning of all my operators to add new things that they can do. Dynamically. Not at compile time, at runtime.
...
[21:15]It gives me tremendous flexibility. Flexibility because the program I wrote to run on a bunch of numbers with only a little bit of tweaking suddenly runs on matrices so long as I didn’t make mistake of commuting something wrong. ... So this makes proving the theorems very hard In fact maybe impossible the cost and the benefits are very extreme. I can pay correctness or proofs of correctness or belief in correctness, I can pay that for tremendous flexibility. ... Is correctness the essential thing I want, I am not opposed to proofs, I love proofs I am an old mathematician. The problem is that putting us into the situation that Mr. Dijkstra got us into ... where you are supposed to prove everything to be right before you write the program getting into that situation puts us in a world where we have to make the specifications for the parts as tight as possible because it’s hard to prove general things, except occasionally it’s easier but it’s usually harder to prove a general theorem about something so you make a very specialized thing that works for a particular case you build this very big tower of stuff and boy is that brittle change the problem a little and it all falls over.

His ideas tend towards adaptable and self modifying code at one point he talks about self modifying code in both assembly language and the use of eval in Lisp. He also touches on a number of parallels in the biological world including genetics and the adaptability of the human immune system to fight off mutating parasites. Interestingly some of his ideas seem similar to work done by Stephanie Forrest on using evolutionary/genetic algorithms for program repair which she speaks about at the keynote of SPLASH 2010, formerly known as OOPSLA. The genetic repair approach at the conceptual level is striving for the same results as what Gerald Sussman describes. Also did you notice that the Levenshtein Distance between "generic programming" and "genetic programming" is (one substitution), pretty weird!

Seriously though, the objectives of all of these approaches are the same: building better more flexible software that handles more situations. These ideas are reflected in how Glenn Vanderburg describes software engineering:

Software engineering is the science and art of designing and making, with economy and elegance, systems so that they can readily adapt to situations which they may be subjected.

I feel this Software Engineering insight reinforces my opinion that we will eventually see a real math backed discipline of software engineering and I think that the research work discussed here both supports my conjecture on this point and most likely lays part of that foundation. I also think some of these ideas reflect ideas I discussed in "The Software Reuse Complexity Curve" which implies that programmers will need to become more aware and more adept at more advanced theoretically based concepts like for example GADT’s (Generalized algebraic datatypes), etc. and of course math in general such as Abstract Algebra.

Clearly the idea of Generic programming has some very specific ideas and some very general objectives. There seem to be two approaches here which might described Predictive vs. Adaptive, much like the idea of Separation of Design and Construction described by Martin Fowler. The Gibbons et al more calculational approach is predictive whereas the Sussman/Forrest ideas describe an adaptive approach. I suspect that this will just be another dimension of program design that will have to be considered and assessed as a tradeoff in its application, which Sussman also mentions.

noreply@blogger.com (Geoff Moes) — Sun, 01 Apr 2012 20:47:00 +0000

In the episode of Seinfeld titled "The Frogger" Jerry and George discover a long lost Frogger machine that still has the G.L.C. George Louis Costanza high score of 860,000 of which George reminisces: "I remember that night. The perfect combination of Mountain Dew and mozzarella...just the right amount of grease on the joy stick..."

This essentially sums up what I call the coding buzz, for me it's the perfect combination of a good problem, private time to work on it, and just the right combination of caffeine and music. The coding buzz is what I live for, those narcotic moments of creative bliss when all other distractions and even personal problems melt away into the background and your mind and fingers become one with your editor begetting a symphony of code creation. It's a wonderful thing.

To really achieve the coding buzz one needs to have a level proficiency generally denoted with the quantity 10,000 hours, meaning that you need at least 10,000 hours of practice. It turns out that the coding buzz is what is called "flow". This is from an article on New Scientist:

The first is an intense and focused absorption that makes you lose all sense of time. The second is what is known as autotelicity, the sense that the activity you are engaged in is rewarding for its own sake. The third is finding the "sweet spot", a feeling that your skills are perfectly matched to the task at hand, leaving you neither frustrated nor bored. And finally, flow is characterised by automaticity, the sense that "the piano is playing itself", for example.
...
Flow typically accompanies these actions. It involves a Zen-like feeling of intense concentration, with time seeming to stop as you focus completely on the activity in hand. The experience crops up repeatedly when experts describe what it feels like to be at the top of their game, and with years of practice it becomes second nature to enter that state.
...
Exactly what happens in the brain during flow has been of particular interest, but it has been tricky to measure. Csikszentmihalyi took an early stab at it, using electroencephalography (EEG) to measure the brain waves of expert chess players during a game. He found that the most skilled players showed less activity in the prefrontal cortex, which is typically associated with higher cognitive processes such as working memory and verbalisation. That may seem counter-intuitive, but silencing self-critical thoughts might allow more automatic processes to take hold, which would in turn produce that effortless feeling of flow.

This is why after over two decades I still mostly like to work as a developer, admittedly not all of my career has consisted of those moments, but the times I found myself immersed in those types of projects both personal and professional has well been worth it. I frequently feel that I should have grown up at some point and tried to pursue the management track or a more formal architect position and I have contemporary colleagues that are VPs and CTOs, etc. However, every time I think about such a career path I realize how much I would dislike it and I would then have to let go of being hands on, I know there are probably cases of those types of positions where that is not the case, but you would have to find the right environment.

I have recently found myself in a pair programming environment and while there are some aspects of it that are ok, but I often find myself sneaking away to do the creative experimental work on my own. As an introvert I sometimes find it hard to pair. One problem is that there is a substantial skill differential between my teammates and me in that I am considerably more senior so that's a problem, thus I am not sure if my issues with pairing are truly accurate. Still when I need to build some complex functionality or refactor code that requires you to hold dozens of classes in your head, tasks that require intense concentration and that both require you to and reward you for being in the zone aka achieve flow, I just have trouble seeing doing this effectively with the added pressure of someone looking over your shoulder. I have spoken with developers who like pairing and perhaps it's an introvert/extrovert preference.

When I originally came up with the idea for this post I just wanted to talk about the euphoric bliss of the coding buzz but now I find myself in a situation that seems to be harshing that coding buzz, to put it in the parlance of our times. Coincidently I am writing this at time when the "group" approach seems to be coming under fire, most notably in an article in the New York Times entitled "The Rise of the New Groupthink" by Susan Cain which includes the following:

The reasons brainstorming fails are instructive for other forms of group work, too. People in groups tend to sit back and let others do the work; they instinctively mimic others' opinions and lose sight of their own; and, often succumb to peer pressure. The Emory University neuroscientist Gregory Berns found that when we take a stance different from the group's, we activate the amygdala, a small organ in the brain associated with the fear of rejection. Professor Berns calls this "the pain of independence."

She also includes the following excellent quote from Steve Wozniak:

Most inventors and engineers I've met are like me ... they live in their heads. They're almost like artists. In fact, the very best of them are artists. And artists work best alone .... I'm going to give you some advice that might be hard to take. That advice is: Work alone... Not on a committee. Not on a team.

She also has an interesting TED talk. As an introvert I feel that both Woz's and her sentiments resonate with me, and I really know what it's like to live in my head, I can't imagine doing good creative work any other way.

As I said the groupthink backlash and pair programming skepticism seems to be something of a hot topic at the moment, see this compendium post on InfoQ which includes some these and other links. Obviously communication is essential in a multi-person software project but is pair programming over doing it? It just feels like a coding buzz kill to me.

The following two talks are some additional interesting and relevant neuroscience related resources:

Authors@Google: Sandra Aamodt & Sam Wang

Your Brain at Work by David Rock.

noreply@blogger.com (Geoff Moes) — Thu, 29 Mar 2012 01:49:00 +0000

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:

aⁿ = 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 aⁿ)

a⁰ = e (where e is the identity element)

The laws of exponents are:

a^m aⁿ = a^m+n

(a^m)ⁿ = a^mn

a^-n = (a^-1)ⁿ = (aⁿ)^-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 a^m=e, then the order of the element is defined to be the least positive integer n such that aⁿ=e. Also if there does not exist any nonzero integer m such that a^m=e, we say that a has order infinity.

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

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

-1² = 1 (has order 2) [-1¹ = -1, -1² = 1, ...]

i⁴ = 1 (has order 4) [i¹ = i, i² = -1, i³ = -i, i⁴ = 1, ...]

-i⁴ = 1 (has order 4) [-i¹ = -i, -i² = -1, -i³ = i, -i⁴ = 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}: a¹ⁿ=a¹, a²ⁿ=a², a³ⁿ=a³, a⁴ⁿ=a⁴ 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 (+,Z_n) which is the integers (mod n) under addition so our group above is just a renaming of Z₄ 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 D₄ and has the cayley table:

	R₀	R₁	R₂	R₃	V	H	D₁	D₂
R₀	R₀	R₁	R₂	R₃	V	H	D₁	D₂
R₁	R₁	R₂	R₃	R₀	D₁	D₂	H	V
R₂	R₂	R₃	R₀	R₁	H	V	D₂	D₁
R₃	R₃	R₀	R₁	R₂	D₂	D₁	V	H
V	V	D₂	H	D₁	R₀	R₂	R₃	R₁
H	H	D₁	V	D₂	R₂	R₀	R₁	R₃
D₁	D₁	V	D₂	H	R₁	R₃	R₀	R₂
D₂	D₂	H	D₁	V	R₃	R₁	R₂	R₀

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 D₄ 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 D₄ 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 S₄. The interesting thing here is the rotations form a subgroup that is isomorphic to our group from above and Z₄. 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 {R₀, R₁, R₂, R₃} 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 Z₄ and also our group (⋅, {1,-1,i,-i}). Also R₀ 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 Z₄ isomorphic group (⋅, {1,-1,i,-i}) also has a subgroup. Our original arrangement of the cayley table was ordered to show the Z₄ 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 Z_n groups, this group is actually one that we have seen before it's just Z₂ 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 Z₄ and isomorphic to the rotation subgroup of the dihedral group D₄ 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.

noreply@blogger.com (Geoff Moes) — Sun, 25 Mar 2012 17:08:00 +0000

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:

the signifier — the "sound image" or string of letters on a page that one recognizes as a sign.

the signified — the concept or idea that a sign evokes.

the referent — the actual thing or set of things a sign refers to. See Dyadic signs and Reference (semantics).

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 following¹:

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.

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

noreply@blogger.com (Geoff Moes) — Tue, 20 Mar 2012 00:23:00 +0000

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 advice¹:

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 context² 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.

¹ 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.

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

noreply@blogger.com (Geoff Moes) — Sun, 11 Mar 2012 20:11:00 +0000

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. 2ⁿ, so one dimension (line) has 2¹= 2, two dimensions (plane) has 2²= 4, three (space): 2³= 8 and so on. Each orthant has all combinations of positive and negative coordinates a set that will be of size 2ⁿ, 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) =log₃4= 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.

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.

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.

noreply@blogger.com (Geoff Moes) — Tue, 06 Mar 2012 03:12:00 +0000

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?

noreply@blogger.com (Geoff Moes) — Sat, 25 Feb 2012 17:57:00 +0000

Agile planning poker¹ uses the Fibonacci sequence or in some cases a bastardized version of it. I do not know the exact reason that the series was chosen, I do know the intent is that there is a standard set of numbers and using these deters the player from the temptation of using false precision, like a value of 10.5 for example. Also it captures growth so each next number is a "unit" of growth larger than the last. I suspect that the sequence of powers of two (1,2,4,8,16,32,64...) would also work, and might be more apropos to the computer industry, but these two sequences are similar in that they both increase by a constant factor, each subsequent power of two is two times larger and in the Fibonacci sequence each term is roughly 1.618... larger than the previous term, also each has a closed form exponential formula for each term 2ⁿ or for Fibonacci sequence it's Binet’s Formula, see below. I don’t know if the Fibonacci sequence is the right way to go, but it seems to work and it is fairly prevalent in nature and art so it’s probably not a bad choice. I confess that while this in one of my math of programming series, I am using it primarily as an excuse to write a post about some interesting results relating to the Fibonacci sequence and the Golden Mean, so if you are only interested in Agile you may want to treat this as a short post and stop here, but I encourage you to read on, the math is mostly high school level and it really is interesting.

The Fibonacci sequence is generally attributed to a man, Leonardo Pisano Bigollo who went by Fibonacci and did not actually discover the sequence, it was known about five hundred years earlier in the tenth century by Pingala and it was probably known much earlier. Ironically Fibonacci’s greatest mathematical contribution was the introduction of Hindu-Arabic Numeral System to Europe, just imagine trying to do multiplication and fractions with Roman numerals.

The Fibonacci sequence is what is known as a recurrence relation or recursive sequence each term is defined as the sum of the two previous terms where the first two terms, which are the generator or seed values F₀ = 0 and F₁ = 1, the formula is:

It can alternatively be written as:

This form will be more useful to us in a moment.

The sequence is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393,...

The Fibonacci sequence has a very interesting relation with a very interesting number known as the Golden Mean which is sometimes referred to as phi and has the following value:

An irrational number that is approximately: 1.6180339887498948482045868343656...

The ratio of a Fibonacci number divided by the previous number in the sequence eventually converges to phi, the first few ratios are:

3/2	=	1.5
5/3	=	1.666666...
8/5	=	1.6
13/8	=	1.625
21/13	=	1.615384...
34/21	=	1.619047...
55/34	=	1.617647...
89/55	=	1.6181818...

As you can see it is already heading there. It is interesting that a ratio which is in the set of rational numbers converges to an algebraic irrational number. The following equation describes this relationship, the Limit of consecutive quotients:

Additionally the following is true:

If we take the following formula:

And divide it by F_n we get:

We then take the limit as n goes to infinity, replacing the terms using the two limit equations from above:

And if we multiply by phi:

Solving for zero gives us:

Using the quadratic equation we get the following two roots (conjugates):

This is phi and its conjugate, which we will call tau:

Now that we have defined phi and tau we can describe Binet’s formula, mentioned above, which is an exponential form closed formula:

Binet’s formula is an easy way to compute Fibonacci Sequence values without having to calculate all of the values prior to the value you wish to calculate.

Additionally there is an interesting matrix based calculation:

The above matrix raised to the nth power gives the above matrix of Fibonacci numbers, the first few are:

The determinant of this matrix is (-1)ⁿ which is described by Cassini’s Identity:

The Fibonacci sequence and the Golden mean have many interesting identities and relationships with other mathematical disciplines and natural phenomena, for example there is the famous relation rabbit breeding, it relates to bee ancestry, the packing of seeds in flowers, and other plant growth proportions. The Fibonacci sequence occurs in the shallow diagonals of Pascal’s Triangle, it relates to Pythagorean Triples. It relates to the similar Lucas Sequence , the Fibonacci Spiral form above which is a Logarithmic Spiral and the list goes on, a lot of this can be found on the previously linked Wikipedia Page and this BBC radio program.

¹ http://renaissancesoftware.net/papers/14-papers/44-planing-poker.html

noreply@blogger.com (Geoff Moes) — Mon, 20 Feb 2012 18:39:00 +0000

On some of my previous projects I have felt that the teams became severely dysfunctional and as a result they cater to the lowest common denominator of the team. This was often a result of a lack of both technical and overall leadership. In these cases schisms formed in the team I was usually at the center of one side advocating good design practices, a high degree of control and a framework approach to reuse. I should add here that while I am very passionate about trying to build quality software and I try to be as egoless as possible. Sadly my opponents in these situations were the type of programmers that did not read and in some cases they were woefully ignorant of basic software design concepts like the Solid principles and design patterns. In one case we had several “senior” java developers who didn’t understand generics or even inheritance, that situation really bordered on the absurd.

In these situations I have often felt that these developers were essentially being very selfish, in some cases it was that the developers wanted a wild west chaotic approach to software development so there were no constraints and they were free to tinker with new libraries and frameworks, what I like to call Resume Driven Development. In other cases it was that they didn’t want to have to learn anything new or challenging, and in some cases it seemed to be pure ego driven stubbornness or inferiority complex driven compensatory behavior.

Regardless of the causes of the dysfunctional nature of the team it always resulted in the dominance of the Lowest common denominator, this can applies to technical level as well professional/maturity level, often it’s both. The lack of leadership and a fractured team often had negative effects on morale especially for the better developers. It often created an environment that produced suboptimal architecture and code. Consensus was often impossible to achieve and code duplication was rampant sometimes deliberate. Naturally code reviews were either not conducted or if they were they were done in a perfunctory way so that any feedback was completely disregarded.

The worst part of the LCD team is the lack of ability to have open objective criticism. Criticism is hard to take but anyone engaging in any activity, especially a creative one, in which they wish to improve can greatly benefit from it, this is described in detail in a great essay by Bobby Grossman. To parallel that essay we had one person on the team who if you even hinted at being critical he immediately became super defensive. He was a terrible programmer and will probably never improve. To engineer a good system you need to have a constructive and positive way to deal with mistakes that occur in code, architecture and process. Discordance on the team causes mistakes to be viewed as validation of an opposing viewpoint. It’s an extremely counterproductive and demoralizing environment. It leads to less communication as many people will avoid the conflict, and in one case I felt that I had achieved a level of fatigue and I just stopped caring, I bailed shortly after.

The LCD team illustrates why so many software projects have problems, in the above case the project failed after I left, in part due to the dysfunctional nature of the team. My goal here is not harp on the negative but to use this as negative space for what you really want. The opposite of this is a team that aspires to be great and to be more than the sum of its parts. I know it sounds like a cliché but I really believe a good team is one were the stronger developers help the weaker and less experienced developers become better because everyone wants to. You want a team that can openly discuss and criticize aspects of the system and discover and fix mistakes early. I think this can happen with a team of professionals who can put their ego aside to do good work and a strong leader who trusts their team and leads with fairness and wisdom and who is open to hearing input from the team but willing to make firm decisions. Human nature in most cases probably precludes such a utopian software team, I think the goal here is to optimize and aspire to it.

noreply@blogger.com (Geoff Moes) — Sun, 05 Feb 2012 22:42:00 +0000

I have come to the conclusion that Complexity and Reuse have a nonlinear relationship that has a parabolic shape, shown below, Complexity increases on the Y axis and reuse increases on the X axis. Code complexity is high both with very low reuse and very high reuse forming a minima which might be viewed as an optimization point for reusability, now remember this is a very simple two dimensional graph, a real optimization scenario for this type of problem may include many dimensions and probably would not have a nice clearly defined single minima.

In a low reuse situation everything that could have been implemented using reusability is duplicated and may also be implemented inconsistently, so the code base will be larger which would require a maintainer to learn and know more code, also since there will be variations of varying degree between the similar components the maintainer would have to be constantly aware of these differences, which might be subtle, one might even find them confusing at times.

As we have previously seen reuse relates to entropy, so a low reuse system would have a large random, “uncompressed” codebase, which has high entropy, I have seen this type of system in my career and it is something I hate to work on.

Before I go to the opposite end of the spectrum, which is probably more interesting, and perhaps more speculative on my part, I’d like to talk about the relationship of code complexity to maintainer developer skill.

I believe, and this really shouldn’t be a stretch, that there are some types of complex code that require certain higher level proficiencies and theoretical knowledge, an obvious choice is parsers and compiler construction. A developer who works in this area needs to have a good understanding of a number disciplines, which include but are not limited to: Formal Language Theory and Automata Theory and possibly some Abstract Algebra, which sadly many developers lack. If you had a project that had components that are any type of compiler or parser and needed someone to create and subsequently work on the maintenance of the code, they would need to know these things, they would need to understand this complexity in an organized theoretical way. The alternative would be an ad hoc approach to solving these problems which would probably yield significant complexity issues of its own.

These types of things can be seen at simpler scale, a system that makes use of state machines or heavy use of regular expressions will exhibit more compact and more complex code. The maintainers have to have a skill level to deal with this more complex approach, sadly not all developers do.

Now you can probably find numerous code bases where these types of approaches and others were not used where they should have been, these codebases will be larger and will require a case by case effort to learn something that could have been “compressed” and generalized with better theoretical understanding. It’s a trade off if you cannot hire or retain people who have the advanced skills an advanced codebase can also be a maintenance liability.

Now let’s create a hypothetical example, say we have a system that has many similar components and a brilliant programmer manages to distill this complexity into compact highly reusable code. The problem is that our brilliant programmer is the only one who can really understand it. Ideas similar to this are pondered by John Cook in his post "Holographic Code". Now it might be the case that it code that is really only understandable to our brilliant programmer, or he may be the only one in the organization with that level of proficiency, also in this case we will assume that complexity was not artificially introduced, i.e. not unnecessary complexity, which is also a real problem that arises in software systems. Also we will assume that we know that a less complex solution that is more verbose with less reuse exists, and in fact the solution of the maintainer developer might be to completely rewrite it in a less complex fashion.

As we have previously seen, the complete compressibility of a code base can never be achieved which relates heavily to aspects of both Information Theory and Algorithmic Information theory this results in diminishing returns in terms of shrinking an algorithm or codebase. My speculation here, based on observation, is that as a codebase is "compressed" its complexity increases as shown above. Essentially you need to be increasingly clever to continue to increase reuse. Now some of these reuse complexity issues may be due to our lack of understanding of complexity in relation to software construction. It is feasible that things that we find hard to gain reuse with today may be easier in the future with advances in this understanding.

Another idea from the research covered in my previous post is that different domains exhibit different degrees of Favorability/Resistance to reuse. I would also suspect that the types of reusable components would also vary across different domains this makes me think that perhaps in the future reusability in different domains can be guided both qualitatively and quantitatively by either empirical or theoretical means or both. This means that you might have fore-knowledge of the "compressibility" of a "domain solution" and then you would be able to guide the development effort appropriately.

I feel the ideas here are a step back from a possible absolutist thinking to reuse. Reuse like any important approach in software, for example test coverage, which can also exhibit diminishing returns, needs to be tempered and viewed as an optimization as to the extent of its practice. In many respects that’s what good engineering is, working within constraints and optimizing your outcome within those constraints.

noreply@blogger.com (Geoff Moes) — Sun, 29 Jan 2012 23:47:00 +0000

Steven Strogatz wrote a series of math related articles on the New York Times website one of which is called "Rock Groups" where he looks at adding integers visually and with respect to odd and even and ventures into the territory of triangles and squares and visually portrays the closed formula for computing triangular numbers. My previous post on triangular numbers in some ways parallels his "Rock Groups" article at least in respect to the visual portrayal of triangular numbers. This post also parallels ideas in that article, in contrast his observations are geometric, these are algebraic observations about, among other things, adding and multiplying even and odd numbers, which work as follows:

+	*
Even + Even = Even	Even * Even = Even
Odd + Even = Odd	Odd * Even = Even
Odd + Odd = Even	Odd * Odd = Odd

Now this doesn’t really give one a sense of what is going on here, however, by using a Cayley Table it can also be called an operation table in that it shows the details of an operator. It becomes more interesting we now have a better depiction of the Group for Addition (+) with Even as the Identity Element and the Monoid for Multiplication (*) with Odd as the Identity Element:

+	Even	Odd
Even	Even	Odd
Odd	Odd	Even

*	Even	Odd
Even	Even	Even
Odd	Even	Odd

Now that still may not be very intuitive, however, if you convert Even to Zero (0) and Odd to One (1) you get the following, possibly more familiar Group with 0 as the identity and the Monoid respectively with 1 as the identity:

+	0	1
0	0	1
1	1	0

*	0	1
0	0	0
1	0	1

The Group has 1 as is its own inverse 1 + 1 = 0. In general these "types" of Algebraic structures consist of a binary operator and a set that is closed under the operation so I am using the notation (Operator, {Set}) to denote these and since the sets are small I can just list the elements, but you could also write (+, Z) where Z is the set of integers and in fact this is a well known group: addition on the set of integers, but the set is infinite in this case in contrast to our finite sets. We can describe the above as the Group (+, Z₂) and the Monoid (*, Z₂) where Z₂ is the set {0,1} of the Integers Modulo 2, or simply the Binary digits which are Base 2.

Now let’s do another transformation on our Monoid and Group, we will now map Zero (0) to False (F) and One (1) to True (T) . We will also change our operators, + now becomes Exclusive-Or and * now becomes Logical Conjunction aka Logical And.

Xor	F	T
F	F	T
T	T	F

And	F	T
F	F	F
T	F	T

All of these transformations are actually Isomorphisms and the two structures combine to form a Ring this is also a Field, the smallest Finite Field GF(2). I have a follow up for this post and I will get into these and other ideas in more detail.

Some basic algebraic structures are:

Magma or Groupoid – A closed binary operation on a set.

Semigroup – A closed binary operation on a set, with associatively. (An associative Groupoid)

Monoid – A closed binary operation on a set, with associatively and an identity element. (A Semigroup with an identity element)

Group – A closed binary operation on a set, with associatively and an identity element. Each element has an inverse element. (A Monoid with inverses)

Commutative (Abelian) – used to describe any of the above with the commutative property, these two terms are interchangeable but term abelian¹ in abstract algebra is used mostly just for groups.

	Closed	Associative	Identity	Inverse
Magma	X
Semigroup	X	X
Monoid	X	X	X
Group	X	X	X	X

Now Commutative is more of a property of the above, as we saw the String Monoid is not or Non-Commutative where as the Group (+, Z₂) and the Monoid (*, Z₂) are both Commutative.

Going back to Boolean Logic, if you have had any exposure to Boolean Logic things now may look amiss in regards to operators: such as what about the Or operator? Actually Xor can be defined in terms of Logical Conjunction and Logical Disjunction as follows:

Our Cayley Table for Logical Disjunction (Or) is:

Or	F	T
F	F	T
T	T	T

Now this table is almost the same as Xor with one exception (T or T) = T vs. (T Xor T) = F. We can still call F an identity since it combines with T to give T, but you can see with that one change we lost our inverse for T so this is a now "downgraded" to Monoid status.

Now if we add Logical Conjunction (And) back we get the familiar values in Caley tables:

Or	F	T
F	F	T
T	T	T

And	F	T
F	F	F
T	F	T

Above we noted that the Group (+, Z₂) and the Monoid (*, Z₂) formed a Ring. Since Or is a Monoid these now combine to form a slightly different structure, a SemiRing.

Another interesting observation about these sets of operators comes from a logical standpoint. The combination of these two operators are what’s known as not being functionally complete, which means that there exists truth functional statements that cannot be expressed by these two operators alone, this can be fixed by adding negation which yields a truth functionally complete set of two dyadic and one monadic² operators: {And, Or, Not}, which is a pretty well known and familiar set of logical operators. The Ring operators from above {Xor, And} also form a functionally complete set. It turns out that just {And, Not} and just {Or, Not} are also each functionally complete sets as are the one element operator sets {Nand} and {Nor}, this is why digital logic circuits can be constructed solely with Nand Gates.

The thing that bothered me the most was the fact that And and Xor had this nice mapping from Boolean Logic with {T,F} to Binary Integer Arithmetic {0,1} but Or seemed to be an oddball and then I realized that you can remap both Logical Conjunction and Logical Disjunction to the Numerical functions Min and Max, respectively:

Max(0,0) = 0

Max(0,1) = Max(1,0) =1

Max(1,1) =1

Min(0,0) = 0

Min(0,1) = Min(1,0) =0

Min(1,1) =1

In Caley table form which better shows the isomorphisms (≅ means bidirectionally isomorphic to) from our Caley tables above: (And, {T,F}) ≅ (Min, Z₂) and (Or, {T,F}) ≅ (Max, Z₂):

Max	0	1
0	0	1
1	1	1

Min	0	1
0	0	0
1	0	1

Interestingly this mapping is the effectively definition of Fuzzy Logic mapped to the discrete cases (two value logic). Boolean Logic also maps to Lattices with disjunction being meet and conjunction being join, the min and max ideas give a nice intuition in relation to ordering.

To recap we saw a number of Group and Monoid Isomorphisms (remember Z₂ = {0, 1}), we saw:

(+, Z₂) ≅ (+, {Odd, Even})

(*, Z₂) ≅ (*, {Odd, Even})

(+, Z₂) ≅ (Xor, {F, T})

(*, Z₂) ≅ (And, {F, T})

(Or, {F, T}) ≅ (Max, Z₂)

(And, {F, T}) ≅ (Min, Z₂)

We also saw Ring Isomorphisms and a Semiring Isomorphism:

[(+, Z₂), (*, Z₂))] ≅ [(+, {Odd, Even}), (*, {Odd, Even})]

[(+, Z₂), (*, Z₂))] ≅ [(Xor, {F, T}), (And, {F, T})]

[(Or, {F, T}), (And, {F, T})] ≅ [(Max, Z₂), (Min, Z₂))]

I have always felt that examples are helpful and I think these give some sense of the diversity that can be found in just a small little corner of math. In researching this I came across some interesting facts which also highlight this diversity, for example the Nand operation is not associative but is commutative so it’s a commutative Groupoid. The Octonions, which are hypercomplex numbers,are neither associative nor commutative under multiplication but have an identity of 1 making it a non commutative Groupoid with an identity, so my point here is that the above table of basic algebraic structures that makes everything look so hierarchical is deceiving as the diversity does not seem to be constrained in any way, as far as I can tell.

¹ This term is named after the Norwegian mathematician Niels Henrik Abel who developed Group Theory independently of Galois and like Galois tragically died young(<30).

² Dyadic means takes two operators, e.g. (And, Or) and monadic means takes one operand, in this case the negation (Not) operator, this should not be confused with other uses of the term Monad.

noreply@blogger.com (Geoff Moes) — Wed, 25 Jan 2012 01:26:00 +0000

Many years ago when I started my career, fresh out of school with a Bachelors in Computer Science, I chose to answer that ubiquitous question "What do you do?" with the title of "Software Engineer". Now you must realize that this was back at a time when any technical title including Programmer was as rare and mysterious as any engineering field to the average person who probably had never used a computer, not like today when everyone seems to have one in their hand at all times. When I was younger I always felt weird calling myself a programmer and I had a number of associations with other engineering disciplines, including starting my college studies in Chemical Engineering. Actually I was a chemistry nerd before I was a computer nerd, which you might have guessed as much if you read my previous post on Software Engineering. I also felt weird and perhaps even a bit phony using the title Software Engineer, I still do, so now I mostly go by Software Developer.

My original foray into the contemplation of Software Engineering lead me to do some more research which yielded an enlightening and informative presentation by Glenn Vanderburg called "Real Software Engineering", PDF Slides here, which attempts to explore ideas of what a real discipline of Software Engineering might be. I strongly recommend watching it. It’s about 52 minutes long. I feel that his presentation has some very good points but it also has some flaws and biases.

He starts with a critique about the state of software engineering today, which includes the following points:

Doesn’t reliably control costs.

Doesn’t reliably produce quality software.

Sometimes doesn’t produce software at all.

Software Engineering doesn’t work.

The term engineering is reserved for practices that work, a good capsule definition of engineering independent of any particular discipline.

The set of practices and techniques that have been determined to work reliably through experience.

Software engineering is a caricature of engineering.

In software we have these practices that don’t work and that is called engineering

I find myself agreeing with these, and sadly Software Engineering does seem to be a ridiculous farce that often seems to resemble a real engineering practice only minimally.

He then goes on to talk about the NATO Software Engineering Conference in 1968 which he cites as the origin of the waterfall process as a misinterpretation of a document called:
MANAGING THE DEVELOPMENT OF LARGE SOFTWARE SYSTEMS by Dr. Winston W. Royce who it seems inadvertently started the waterfall process through what might be called "Poor Information Design".

He continues with a quote from Parness about the document oriented path into engineering captured by the following quote:

In Enginering ... people design through documents.

-Parness

This is followed by a list that might be considered failed attempts at such an approach:

CASE Tools

OOSE

VDM

UML

MDA

OMT

Booch

He refers to this as:

Modelling and what I call ‘Math Envy’

While I agree with this last statement in practice, I feel that he goes too far with this opinion, more on that later.

His presentation provides a good historical survey of Software Engineering with respect to the 1968 NATO Software Engineering Conference and is worth watching for that alone. He continues with some great observations about engineering in general:

Engineering is a creative activity it’s about designing and building and creating new things and there are always blind alleys and missteps and mistakes and discoveries and reactions to those reactions and adjustments.

I especially like the trial and error aspect in relation to creativity. I think this is a fundamentally important and potentially overlooked aspect of software development.

The following succinctly sums up what might be the kernel of general engineering:

Different Engineering Disciplines are Different

Different materials, physical effects, forces

Different degrees of complexity in requirements, designs, processes, and artifacts

Varied reliance on formal modeling and analysis vs. experimentation, prototyping, and testing

Varied use of defined and empirical processes

This leads to a comparison between the empirical vs. formal predefined models:

The defined process control model requires that every piece of work be completely understood. A defined process can be started and allowed to run until completion, with the same results every time.

The empirical process control model provides and exercises control through frequent inspection and adaptation for processes that are imperfectly defined and generate unpredictable and unrepeatable outputs.

He then takes the following ideas from Structural Engineering:

Structural engineering is the science and art of designing and making, with economy and elegance, […] structures so that they can safely resist the forces to which they may be subjected.

—Structural Engineer’s Association

Science and art, it employs the findings of science and yet is done with creativity "designing and making" engineers don’t sketch something on paper and validate it with math and throw it over the wall and never look at it again they participate in the building of what they design structural engineers have hard hats in their office because they visit the site and talk to the construction people and work with them during the process. "With economy and elegance" cost is always an object.

From these ideas he derives a brief description of Software Engineering:

Software engineering is the science and art of designing and making, with economy and elegance, Systems so that they can readily adapt to situations which they may be subjected.

With the following caveat:

Software engineering will be different from other kinds of engineering.

We know that software engineering will be different from other kinds of engineering we know that because other kinds of engineering are different from each other. Software systems are usually more complex in terms of number of moving parts and things like that than artifacts in other engineering disciplines we’re not working with physical materials we have different laws we work with and it is rare for a software project to run up against the limitations of physical materials, very rare.

He reiterates this from the Structural Engineering piece:

Cost is always an object.

This is more eloquently stated by Arthur Mellen Wellington:

Engineering is not the art of constructing. It is rather the art of not constructing: or, it is the art of doing well with one dollar what any bungler can do with two.

—Arthur Mellen Wellington

The following are elements that in part drive the agile philosophy:

The source code is the model and the document.

Source code is the detailed design

The design and construction of software is tightly coupled.

He draws the following inferences from the above:

Encourage continued innovations in processes

And do like other engineering disciplines do. Take the processes that work and call those engineering.

Agile software development, far from being anti-engineering, represents the responsible application of engineering ideals to the field of software.

I know that was a lot of quotes with sparse commentary, but it seemed like the best way to capture the really good points that he makes in his talk and again I am trying to create a written artifact that I can reference and build upon in the future.

One thing that I really don’t like about his presentation is the comparison of the two bridge builders: Robert Maillart who designed the Valtschielbach Bridge in Switzerland among others and Leon Moisseiff.

The distinction being that Maillart used testing and all but one of his bridges are still standing while Moisseiff used modeling most notably Deflection Theory and was responsible for designing the ill fated Tacoma Narrows Bridge aka Galloping Gertie possibly one of the most famous engineering disasters in history. Moisseiff was also involved in the design of Manhattan Bridge which is still standing and his Deflection Theory was used in the design of the Golden Gate Bridge and was later determined to be of sound design and is also still standing. The Frommers travel guide considers the Golden Gate Bridge "possibly the most beautiful, certainly the most photographed bridge in the world", what bridge Maillart design?

I will not dispute that the collapse of the Tacoma Narrows Bridge was probably one of the most famous if not the most famous engineering disaster of all time and Moisseiff certainly suffered as a result, his career was shattered and he died shortly thereafter. Wikipedia states: "Though he [Moisseiff] had designed many other famous spans, the Narrows collapse overshadowed them all. It became a symbol of failed engineering and the dangers of arrogance in design." I am in no position nor do I care to debate the soundness of deflection theory or the reasons for the collapse, actually it seems that reasons for the collapse are pretty complicated.

From my limited understanding of Civil Engineering it seems that problems with wind are a continuous problem for Civil and Structural Engineers, I know that the John Hancock Tower in Boston was plagued by problems where wind induced twisting which caused large plate glass windows to careen hundreds of feet to the street making it a deadly hazard. These were replaced with plywood earning it nicknames like the "Plywood Palace" and causing it to be condemned as a fire hazard, eventually these problems were resolved and it won awards for enhancing the Boston skyline. More recently, only twelve years ago in 2000 the Millennium Bridge in London exhibited similar resonance problems to those of Galloping Gertie, it was shut down and reinforced. So while all of this makes for interesting history of engineering fodder and good showmanship, I am not sure how directly relevant it is to software engineering. I Again I agree with his assertion that testing, perhaps not necessarily TDD in my opinion, is most likely a very important component in creating a real software engineering discipline but I feel this particular comparison argument is flawed as it is completely irrelevant to software engineering and in no way can be used to conclude that TDD should be used in software engineering. Also he contradicts his own argument with the statement, from above:

Software engineering will be different from other kinds of engineering.

He also contradicts this in his slides:

Software is very unlike bridges and buildings.

He ends his presentation abruptly with:

Today software engineering is called Agile.

I hate to say it but the way he states it, it sounds a bit like "Mission Accomplished" to me and I may be misinterpreting him here but to me it sounds like his whole presentation is designed to conclude that Agile and TDD are the solution to the problem and I agree that they are probably the best solutions to the problem today, but I think they are severely lacking as an effective and precise framework for a real engineering discipline, I think we still need more cowbell.

I feel that his presentation has anti-math and anti-academic undertones and I have to say: "No Sir I don’t like it." The two main themes that I take issue with are:

He mostly dismisses the work of non practitioner academics.
He dismisses Math and views it as only a cost saving tool.

At various points He states the following:

Advances come from practitioners not from academia.

"Advances come from practitioners." And then are brought into academia.

Important advances often from practitioners not necessarily from academia and they are brought into the academic world and are refined and so forth. But they come from practitioners.

They were practitioners … and there were a few academics, but the academics had good things to say as well.

Perhaps I am misinterpreting his tone here, but the in the last statement he seems surprised that the academics had something of value to contribute. Actually I feel that he has this somewhat backwards, for example I think the work that companies like Google are doing and the general trend in analytics fundamentally contradict this sentiment. I think the way that both the fields of Computer Science and Software Engineering will inevitably move forward in both efficiently and efficacy will be through more collaboration between practitioners and academicians with both groups refining each other’s ideas. I anticipate and hope this is a trend that we will see more of. In fact some really interesting things are happening in that regard one interesting example is the work that Mike McCandless has done with Lucene using Finite State Transducers which was based on academic work, not to mention the Entropy-Framework relationship that we have already looked at.

He goes on to say:

Mathematical Models were introduced to engineering as a cost saving tool it would be easy if you hear software engineering people talk about math and modeling, it would easy to get the idea that it’s the only way to do things right and that it is a tool for robustness and you don’t know it really works that it is really works unless have math to prove it, I’ve heard all of those statements. But, that’s not why it was introduced to engineering at all it was introduced to save cost because in other engineering fields they are working with real materials and things that require people and labor to go out and build and building prototypes and testing them especially at scale is extremely costly and if you can build a model, an approximation of reality you can save money.

Ask your friendly neighborhood aerospace engineer how much math he would do if building a model of his design and testing it were was effectively instantaneous and free. The answer would probably not be none, but a lot less than I do now.

I am not sure if I agree with the idea, that seems to be implied, which is that mathematical models are strictly a cost saving measure.

Towards the end he states the following are approaches needed to advance software engineering:

Not Math

Not Models

Not Documents

Not copying other disciplines

Learn From practioners

Bias towards empirical processes

Ironically he mentions the following:

Programming languages are formal languages some of them even have mathematically specified semantics ... and we understand the math behind them at least as well as your average structural engineer understands the math behind the procedures that he was taught to do to validate his designs.

Programs themselves are models of the solution to the problem, our very tools are mathematical in nature.

In the slides he has the following quote, which I think he skips in his presentation due to time constraints, but I believe it is intended to reinforce his anti math-argument:

What is needed is not classical mathematics, but mathematics. Systems should be built at levels and modules, which form a mathematical structure.

—Friedrich Bauer

I was unable to find it elsewhere, so I don’t know the context of the Friedrich Bauer quote, but I find the quote interesting. I feel the key here is: "not classical mathematics, but mathematics". My interpretation of this is that he is saying that math is important, but not the math many people think about, hence "not classical mathematics".

I hope I didn’t come across as too harsh on Glenn Vanderburg but I am just being honest and as he said about Bruce Eckel, "He said it so I get to pick on him".

The real strength of his presentation is that he really does step back from software and give some perspective on general engineering, and while we can all debate the utility of comparing different engineering fields it does hold that they all have a several common threads, including the application of artistry and creativity to design and construction, the objective to design and build things, working within certain constraints including cost, and the organization of people and resources to accomplish the tasks of design and construction.

I admit that my experience with real Agile is limited and while I like what I have seen. I still doubt that it truly fulfills very little beyond an empirical approach and it seems that its focus is primarily on the process of creating software, which is not necessarily a bad thing. The structural aspect of software is not ignored by Agile, but I do feel that it is the structural aspects of software which is where we currently lack a real engineering framework. This is really what needs to become more established. Ideas like Coupling, Cohesion, Refactoring, Patterns, Anti-patterns, etc. are the state of the art in terms of structure but they seem too "squishy" which leads me to ask the question, is it not possible to have more comprehensive math backed concepts like the types of things you find in other engineering disciplines?

The answers to these questions in the past have been dominated by ideas like formal methods and metrics, ideas which have mostly failed to live up to a real promise, however, that does not mean that we should completely discount these and similar ideas in the future. These and other more math oriented approaches may represent a failed lineage that will go extinct or they may represent the nascent ideas from which we are only now developing the theoretical and mathematical ideas to truly conquer these problems. For example the Nato Conference of 1968 is often cited as a milestone in the development of software engineering. It was only about forty years proir that Category Theory was discovered. I wonder how many attendees or general practitioners knew about it, unlike today where it seems that almost every software blogger writes about Monads and many also mention Category Theory. I feel that the new era of software engineering will be forged from math but it won’t be "Classical Math" like Calculus and Algebra over the Field of Real Numbers, it will be from areas like Graph Theory, Lattice Theory, Category Theory, Information Theory and other related disciplines and not only will it be built on those disciplines but also the interrelation of those disciplines. I may be wrong about this but I have seen research that seems to point in these directions, ideas I will explore in future posts. It seems crazy to assume that the failures of the past imply failures of the future. If math can make software cheaper and more reliable to produce it will become an inevitability.

noreply@blogger.com (Geoff Moes) — Sat, 24 Dec 2011 16:27:00 +0000

Please note this is a rewrite previous post that I was unhappy with.

Years ago I heard a comparison of software engineering to chemical engineering. I believe the intent of the analogy between the two fields was due to the fact that Software Engineering is a very young discipline just as Chemical Engineering was in relatively recent history, circa 1900.

Metaphors get used a lot in our industry, in Chapter 2: “Metaphors for a Richer Understanding of Software Development” of Steve McConnell’s Code Complete they are discussed in some detail. In that chapter he cites the following:

A confusing abundance of metaphors has grown up around software development. David Gries says writing software is a science (1981). Donald Knuth says it's an art (1998). Watts Humphrey says it's a process (1989). P. J. Plauger and Kent Beck say it's like driving a car, although they draw nearly opposite conclusions (Plauger 1993, Beck 2000). Alistair Cockburn says it's a game (2002). Eric Raymond says it's like a bazaar (2000). Andy Hunt and Dave Thomas say it's like gardening. Paul Heckel says it's like filming Snow White and the Seven Dwarfs (1994). Fred Brooks says that it's like farming, hunting werewolves, or drowning with dinosaurs in a tar pit (1995). Which are the best metaphors?

I am not sure how apt the chemical engineering metaphor is either, but there are some interesting parallels. The early chemical manufacturing process to produce sulfuric acid is called the Lead chamber process and it was invented in the mid 1700s. The process was not very well understood and was inefficient in that it required the use of expensive nitrates often from Chile which were partially lost as nitric oxide vapor, and it took over a hundred years before a way to recycle the part of nitrates was added to increase the efficiency of the process. The discipline of chemical engineering was codified in the late 1800s when college curricula and associations for chemical engineering were created. Over time the science of chemistry and stoichiometry advanced as did thermodynamics which made major steps forward around the same time. I am over simplifying here but eventually little understood processes that were discovered and tweaked empirically became understood and could be controlled and improved by applying the laws of science and mathematics. Another parallel is the focus on reusable processes, in that if you are building a new plant to manufacture sulfuric acid you don’t want to design it from scratch each time. An interesting and abstract parallel is that both disciplines have their entropies, i.e. thermodynamic vs. information. A social parallel may be the transformative effect that software is having on our lives and our society is as profound as that of industrial scale chemical production, this keyboard and almost thing I can see right now has been influenced in some way by chemical engineering. Also what are the negative sides of these industries, what problems are we creating by the unregulated and somewhat opaque policies in regards to chemicals and what might some of the issues with software and IT be?

Now admittedly there is pretty big difference between a physical chemical process or the construction of something physical like bridge and software construction. There are obvious parallels to building things in that people have to come together to build something that is greater than what one single individual could build. And there are similarities to Chemical processes in that once you build it that you have keep it up and running and you will probably need to do maintenance and make improvements while it is operational and even in some cases take it off line or build a new one in parallel while the old one is still in production. Also might we possibly view Computer Science and Math as related to Software Engineering as Chemistry, stoichiometry and thermodynamics are related to Chemical Engineering?

Like Donald Knuth I too think there is an artistic element to software, this idea is not incongruent with building or bridge architecture which is a process that organizes groups of people to build something beautiful. Perhaps a possible analogy for software engineering would be the construction of a bridge where we still don’t really understand all of the physics behind it or the best way to go about it. As a result when we are done it might stay up and it might not and it will probably take longer than we thought to build it.

I guess the question is it possible to create a discipline of software engineering that is as effective as the other engineering disciplines? If we use the chemical engineering metaphor, where are we in the time line of understanding the underlying science and applying it to our process? Perhaps we are at the equivalent point to the mid to late 1800s in terms of process and our understanding of the underlying science but I very much doubt the years will map linearly, it’s probably more like an exponential mapping. The elusive software engineering is probably its own entity, are our metaphors confining our thinking and hindering our ability to objectively look at this problem?

The software industry is also different from almost any other technical industry in history just in the sheer number of people who now participate in it worldwide and it seems that the barriers to enter the field can be lower than that of other engineering and scientific disciplines in regards to formal degrees.

noreply@blogger.com (Geoff Moes) — Mon, 05 Dec 2011 16:51:00 +0000

Wow that was quite an experience, I have been looking at sites like Hacker News, Reddit and DZone for years but to see my own post go to #1 on Hacker News and rise high on Reddit and DZone was quite a thrill, with over 70K hits at the time of this writing. It has completely changed my life the phone is ringing off the hook with endorsement offers, it looks like I will only be wearing Nike for the next year.

The best part was the over 200 comments on my Blog, Hacker News, and Reddit, it spawned some spirited discussion on all three locations and many people added their own equations some that I was unfamiliar with and I learned a few new things, excellent! The various discussions for the most part were great and very enjoyable and I’d like to thank everyone who contributed. In the post I commented that I wondered how I would feel about the list in a year and I already think I would change the list by one equation. I was tempted to respond to the comments on all of the forums, I know I should at least respond on my own blog, I just figured I’d do it as a post that way I could hit a number of topics.

One thing that people objected to was the title, which induced some inferences in the tone of the title. One redditer summed it up as:

Someone presuming, yet again, to know what "every" Computer Scientist should know? A title like "my favourite computer science equations" might be better. This list contains a lot of ideas which are only relevant in very narrow domains.

Yes, probably on the title comment, but the title was an intentional "spoof" if you will of a title of an article on Wired, and if you read my post you would have gotten that. Actually I confess that you might even accuse me of "Hacker News Post Popularity Hacking" as I saw the Wired post rise up and figured that there was a high probability that a similar CS related post could achieve a similar placement, actually I think it exceeded my expectations and went even higher, it shot to #1 in under two hours of my submitting it and it stayed on the front page for almost a day. I felt the tone I was setting, by using the term "rip off" and the Spinal tap joke (This one goes to eleven) that I don’t think anyone got, was subtly light hearted, perhaps it was too subtle. I recall reading that the title is key to getting people to read posts, and clearly this title was somewhat controversial which probably helped it, actually most of my titles are fairly boring or references that make them less popular, but I generally title things the way want not for popularity, well with this one exception.

Another thing that people took umbrage with was the use of the equations, as I just explained since I had set my title accordingly my format was now set. One commenter, in two different comments on a thread on Hacker News added:

I think this is a pretty silly post, to be honest. CS covers so much, and everytime I see a list of "things you should know", I have to resist the urge to roll my eyes and ignore it. But then I read it, and inevitably roll my eyes anyway.

...

I disagree. Programming is math. Highly advanced math, in fact. It's just a different type of math. And the 11 equations in the OP's article just barely touches on what CS is about. There is far more to it than that.

I mostly agree with this commenter. I admit that the sentiment that this not really about the equations but the general domain knowledge is implied, again perhaps too subtle. At one point someone mentions memorizing these equations which again means you are missing the point. It’s about knowing what these equations mean and how to use them. I feel that the math domain knowledge for our field is growing and becoming more important. Do I use any of this for my day job? Well no, but I hope to one day. As to the broad domain I actually have a post "Math For Programmer TNG" that covers a very broad domain of math that I think is potentially relevant. Also not all areas of math are going to be used in every math related job.

As to the narrowness insinuated by the two comments above, the post touched on the following domains: Combinatorics, Logic, Boolean Algebra, Set Theory, Lattice Theory, Probability Theory, Statistics, Category Theory, Number Theory including Complex Numbers, Relational Algebra, Abstract Algebra, Linear Algebra, Shannon Information Theory, Algorithmic Information Theory, Kolmogorov complexity, Graph Theory, Formal Language Theory, Automata Theory, Combinatory Logic, Lambda Calculus, Machine Learning, Data Mining, Encryption, Limits, Topology, Fourier Analysis and The Simpsons. Not exactly narrow, or am I missing something here? In fact the list was picked in part for diversity.

The Pumping Lemma turned out to be fairly controversial, I do admit that the Pumping Lemma was perhaps a bit "contrived" as an Equation and as one person put it: "that's the most hideous formulation of the pumping lemma I have ever seen". That formulation came from Wikipedia. As I mentioned I really did want something from Formal Language Theory or Automata Theory and it’s not so much about determining which language is regular but knowing the difference between a Regular Language and a Context Free Language so that you are not the cargo cult coder who tries to parse html with regular expressions because you understand these distinctions. I think the following exchange summed up what I was going for:

(except the Pumping Lemma, WTF?)

Reply:"Seriously, you never learnt theoretical computer science? As in, theory of computation? Automata theory? Complexity theory? Nothing like that?"

There were a number of comments about the use of mathematical notation including the following:

"Shannon's Information Theory, Eigenvector, DeMorgan's Laws, etc. None of those names are meaningful or descriptive. And then the greek letters and made up symbols. Math could learn something from Computer Science:

"https://www.google.com/search?q=readable+code

This commenter seemed to have an issue with the actual names of things in math. I found this to be very narrow minded. Math is many things including being a domain of knowledge, that’s like complaining about the names: Ytterbium in Chemistry, Bose–Einstein Condensate in Physics, Borneo in world Geography, or Impressionism in art. Really!?!

Now the complaints about the notation are more understandable but still unreasonable in my opinion, math in some respects is a language, perhaps somewhere between a natural language and programming language, it has a notation and to really be able to understand it you need to learn this notation (language). Someone remarked that symbols were "unfriendly". Well I find Chinese, Arabic¹, etc. to consist of unfriendly symbols, but that’s because I don’t know them. Also like natural languages you have inconsistencies, and multiple meanings for symbols. One person complained about my notation for the Set version of De Morgan's laws, this may be a nonstandard notation, I saw it in some course notes on probability and set theory and I liked it and I just used it without thinking about it. I do think it’s more elegant. This makes a good point about math. If you learn it and read from diverse sources you will encounter notational differences. This has been my experience, in fact if you look on the Wikipedia page for De Morgan's laws you will find the following example from Modal Logic:

I am used to the notation used in Hughes and Cresswell:

That’s just how things work. You can get hung up on it and complain or you can accept it and move on. Don’t get me wrong it would be nice if there was a notational standard that every one followed for all math.

Like natural languages Math has its equivalences of "Homographs", for example the following symbols can have multiple context dependent meanings: |b| can mean absolute value of b if it is a number or cardinality of b if it is a set or length of b if it is string, ∂ can mean Partial Derivative or Topological Boundary, and as we saw ∧ and ∨ can mean meet and join or "logical and" and "logical or".

Just as Math has "Homographs", as in natural languages it also has its equivalences of "Polysemes", meaning that there are multiple ways to express the same ideas. For example set difference can be expressed as (S – T) or (S \ T), the Powerset notation can be either 2^S or P(S), and meet and join can be expressed as the either of the following sets of symbols:

The list of both math "Homographs" and "Polysemes" is much longer.

For De Morgan's laws, someone added the following generalization using the Existential and Universal Quantifiers, which is really interesting and also illustrates the duality:

It's not much of a generalization, but I prefer the predicate version of De Morgan's:
~∀x p(x) ≡∃x ~p(x)
~∃x p(x) ≡∀x ~p(x)

If you read the Wikipedia Article it includes this generalization as well:

The above equations do generalize De Morgan's laws within Logic and Set Theory respectively but my point was to further generalize them in terms of Lattices which is a different concept all together and gets at the deeper intuition about the interrelation of Logic and Set Theory, quoting from Combinatorics the Rota way: by Rota and Kung, an amazing book I am trying to read, emphasis on the word trying:

"As John Von Neumann put it, the theory of Boolean Algebras is "pointless" set theory.

This set version would be written using the complement exponentiation notation as follows:

I really do prefer this notation, I originally encountered it in "Introduction to Probability Theory" by By Ali Ghodsi and Cosmin Arad, lecture 1(pdf). This notation is also used in Combinatorics the Rota way. So this notation is now the official notation of my blog, get used to it or hit the road. ;)

A commenter (who was also the demorgans notation complainer) responded with the following:

...
For the rest, they seem more likely to be used by someone doing something related to machine learning/AI/information theory than you run of the mill I-spend-all-day-parsing-user-input programmer.

Thank you for making me feel like I'm not a 'true' computer scientist. Next would you like to tell me about how I'm not a 'man' because I don't like to work on cars?

Well I hate to break it to you, but if this list makes you feel that way then chances are you are like me: a software developer with a CS Degree and that does not make you or me a Computer Scientist. This is from Wikipedia:

"The general public sometimes confuses computer scientists with other computer professionals having careers in information technology, or think that computer science relates to their own experience with computers, ...

Oh, and yes you are not a man if you do not at least know how to change your oil, including the filter. ;)

Also a number of people remarked that I did not explain the equations in enough detail and I did not provide code examples. It was meant as high level post, if I were to explain all of these equations the post would have been excessively long, maybe even a whole book. As to the code examples again it would be too long, if you want code examples that relate to math, I have posts for that, I recommend the following posts on my blog, some were linked in the original post: "O(log(n))", "Triangles, Triangular Numbers, and the Adjacency Matrix", "The Combinatorial and Other Math of the Java Collections API", "Math You Can Use : Refactoring If Statements with De Morgan's Laws", and "Monoid for the Masses".

Regrettably some people responded with the sentiment of: I’m not good at math or that math is too hard, I don’t think I can get a CS degree. Fortunately there were a number of comments of encouragement to counter these sentiments, my favorite was this one:

Don't let this be intimidating to you - instead of asking yourself "how come I don't know this?" ask yourself "how can I learn more about this?". This might sound cheesy and simplified but it's as simple as "nobody was born knowing this". I'm 31 and I wish I had the money to go back in education and learn all of this with the official way but for now I'm just picking resources on the web and who knows? It just might happen...

I have a post planned to talk about my experiences and thoughts about learning math, I will say if you are a programmer you are doing math in a sense. You just need to formalize your understanding of the underlying concepts. If it is any consolation I find Math to be very hard at times, I pretty much suck at it in the traditional sense, but it is so beautiful and when you grok a concept, at least for me, it is an incredible buzz. Every new concept that you learn changes how you see everything, I see so much math in programming and the world now it’s scary, I just wish I could figure out how to express it. Everything is math. Over the last few years my ability to understand things has greatly increased and continues to do so. Yes it’s hard but it is so worth it.

A number of commenters added their own equations to the discussion, and this was the best part, which included a few new things for me. In general my list was mostly directed at more pure math oriented equations that I felt were fairly central to a specific discipline and encapsulated certain principles. Here are a few recommendations and thoughts:

One person pointed out the absence of P=NP or P ≠ NP, to which I would respond "D’oh!" If I was doing this over I might even replace the Pumping Lemma with P=NP.

One poster recommended triangular numbers:

Here's a real simple and practical equation: 1+2+3+4 . . . N = N(N+1)/2
This equation represents the number ofedges on a complete graph with N+1 vertices or the number of possible pairings given N+1 objects. Useful whenestimating O(N) for certain algorithms that involve comparing an item to everyother item in a set.

I love Triangular Numbers and this is a great equation, I wrote a whole post "Triangles, Triangular Numbers, and the Adjacency Matrix" on exactly what he is mentioning, and considered that equation but rejected it because triangular numbers are sort of a special case of the Binomial Coefficient equation:

Here are some of the other equations and theorems that were suggested, I wouldn’t really consider these because they didn’t fit my theme and criteria but that doesn’t mean they aren’t interesting:

One commenter accused me of shoehorning in Euler’s Identity. This is partially true. He also accused me of "Name Dropping". That’s not true. A defender supplied the following course notes:

Analytic Combinatorics: A Primer

I followed up on that and found that you can download a copy of Analytic Combinatorics:
by Flajolet and Sedgewick. Warning: pretty advanced stuff.

As the popularity of my post was waning on Hacker News a math oriented post called "Fuzzy string search" was making its way up the ranks. It’s an interesting post and I think it helps illustrate a couple of points I have been making here, first of all it uses mathematical notation, which is not uncommon when writing about these types of topics. Additionally the post includes the equation for the Triangle Inequality:

An equation that crossed my mind when writing my equations post. It is not the equation itself, but the concept, if you become familiar with the idea of a Metric or Metric Spaces, you instantly recognize this equation concept without having to read the associated text, not that you shouldn’t read the associated text. Knowing these ideas gives you the ability to better understand more complex ideas that are based on these concepts. I think this is the case in all knowledge domains. Also I noticed that there was not one comment on that post complaining about math notation.

A lot of what went on is part of an ongoing conversation, I blogged about it in "The Math Debate" which links to other famous blogs of the same ilk. Ultimately the equations probably don’t apply to most programming jobs, the title contained as some commenters pointed out "Computer Science Geeks" not "Corporate Software Developers". A few people castigated the commenters who seemed to be advocating positions of ignorance, thanks, BTW. I personally find it tragic, the following comment sums this up:

"Someone with a CS degree who knows nothing of De Morgan's law should have their credit removed and be demoted to making websites or performing tech support tasks.

Reply: "There goes 98% of your CS graduates then. I wish I was joking, but alas.."

Of course it’s a bit I ironic that as I am wrapping this up, "A co-Relational Model of Data for Large Shared Data Banks" by Erik Meijer, Gavin Bierman just popped up on Hacker News, the relevant quote is:

Every programmer is familiar with the two dual forms of De Morgan’s laws

The writing quality of the post was criticized. I don't know what people will think of this post, I feel like I just wrote a clip show. I admit that previous post was not my best effort, while it was fun putting it together it was not easy, I had hoped to learn all of the equations in more detail, I did to some degree, I confess I still don’t fully get the Y-Combinator, but I will. I finally decided to just push it out and move on. This post, while being relevant to my mission of blogging about math was something of a social experiment in popularity, it was interesting but I will be returning to the true mission of my blog which is my journey through math and the pursuit of a real Software Engineering discipline.

Ultimately I am interested in the readers, like a young colleague of mine who was too busy to comment because he was following the links to learn new things he didn't know, not the complainers and naysayers. There were many positive comments and again, thanks. I did feel a needed to refute some of the negative comments. The bottom line is if you want to read about math, you need to get used to the notation, it probably won't help you to build CRUD Web apps but it will hopefully help you take your career to the next level.

¹Actually this is not true I find them to be quite beautiful, especially Arabic.

noreply@blogger.com (Geoff Moes) — Sun, 27 Nov 2011 21:13:00 +0000

This idea is a complete rip off an article that appeared in Wired a little while ago and it got me thinking what would my list for Computer Science look like? Plus I thought it might be a fun post and unlike the Wired list this one goes to eleven. So here they are in no particular order:

The Binomial Coefficient equation generates Pascal’s Triangle and gives you the coefficients for the Binomial Theorem these ideas are often attributed to Pascal but in fact they have been known in part for over a millennia.

As I mentioned that this list is no particular order and I don’t wish to play favorites but if there is one equation here that you should really consider learning and committing to memory this is it. It is central to Combinitorics which has connections to many areas of math, I guess I should qualify that if you are serious about computer science and math related programming topics then you should be able to recite and apply it from memory, even when you are drunk, sleep deprived or being held at gun point. Ok that might be a bit much but you get the idea. If you are programmer and you haven’t learned it, or need a refresher, I have a post that relates it to the Java Collections API.

Logical form:

Set Form:

Ok so that’s like four "equations" for DeMorgan’s Laws, one can’t help but to struck by the similarity between the two sets and this is not a coincidence these two sets of formulas are essentially the same thing, they are special cases of complemented distributive lattices^† which means technically it’s really just two formulas:

In this case the ∨ symbol means lattice join operation and the ∧ symbol is the lattice meet operation and the dash with the right downward mark means lattice complementation, I used this to differentiate from the tilde for Boolean complementation. Also these two formulas are categorical duals of each other, which means that if one were smart and had a good grasp of Category Theory we could probably be really OCD about it and get it down to one formula.

Understanding Set Theory and Boolean Algebra are very important basic concepts in our profession and the Boolean version can make you better programmer, as you can use it to refactor logical if statements.

This equation and these concepts are not only central to Linear Algebra but these Linear Algebraic ideas and others are both used and extend into many other areas of math including Linear Transformations and Graphs in terms of matrices like the Adjacency Matrix and much more.

Linear Algebra is becoming increasingly central to the types of things we are doing in our profession, it is used heavily in Statistics and Machine Learning not to mention the Page Rank Algorithm is based in part on this equation.

No Comp Sci list would be complete with at least one formula from either Formal Language Theory or Automata Theory. The problem is that these two are pretty different from other areas of math in terms of "Equations" I tried to think of some basic Ideas and The Pumping Lemma came to mind, and I found the above formula concisely expressed on Wikipedia. This version of the Pumping Lemma is a more limited version of Another Theory which is used to check whether a Language is Regular. Also this is maybe not the best choice as it is pretty dense, if you want a better explanation I recommend this.

While this "equation" is pretty specialized, it is actually a special case of the more general Iteration Theorem, the real point here is really about more general domain knowledge. It is central to what you do every day you are programming such as compilers and regular expressions not to mention the almost ubiquitous Kleene Star.

I confess after all my machinations to try to reduce Demorgan’s Laws down to less equations I am totally cheating here by pulling a twofer in including two formulas, both Shannon’s Information Theory:

And the formula for Chaitin’s Constant, which is associated with Algorithmic Information Theory and Kolmogorov Complexity:

Interestingly this area has a parallel in the physical word, in terms of Thermodynamic Entropy, which also parallels the Boltzman Equation mentioned in the Wired Article. Seth Loyd draws some interesting connections between computation and the physical world including Entropy and Boltzman’s Equation.

In programming and computer science information is our business and these ideas are central to many things that we deal with especially the storage, transmission, computational transformation (like compression), and computation of information. We’ve already seen the possible relationship between both of these theories and Reusability and Software Frameworks.

Of all of equations on the list, Bayes' Theorem may stand out on its own merits as being one of the most recognizable and it might even qualify as a poster child for the statistical revolution sweeping our industry. It rose from obscurity to being used for spam detection and with such applications as classifiers, Machine Learning, Data Mining and more.

Mathematically it is part of a rift in statistics and probability and I confess I may not yet call myself "an initiate of the bayesian conspiracy" but it hard to deny its utility plus there seems to be a more axiomatic basis that relates to Boolean Logic Set Theory, which makes it all the more alluring.

These two equations of Fermat’s Little Theorem are really the same equation written in two different forms, where (a ⊥ p) means coprime and (p ∈ P) means prime.

This is a beautiful little theorem in Number Theory which can be generalized and written even more succinctly using Eulers Totient Function which is represented by φ (n):

These ideas are crucial for understanding encryption algorithms like RSA and there’s this cool result.

Natural Join, like all of the Relational Algebra Join Operations is a composition of the more basic, operations: Selection (σ), Projection (π), Cartesian Product (×), Set Difference (-) and Union (∪). Natural Join is the Cartesian Product of two tables selecting matching rows and eliminating duplicate columns. (In the formula above the projection (π) is the set (A) of attributes with duplicates removed and then selects (σ) the set (C) of common attributes which match in both sets and are equal in both sets.)

The Relational Algebra is in my opinion a bit of an odd beast when it comes to algebraic structures, but if you use SQL you are already using an implementation of it. As data persistence becomes more heterogeneous I think understanding these concepts, will become more important. Additionally Relational Algebra also has strong ties to Abstract Algebra[ and Category Theory[.

Just as we need a "equation" from Formal Language Theory or Automata Theory we really should have one that is related to Lambda Calculus, in this case this equation is in the untyped lambda calculus. Even though the Fixed-point Combinator stands up on its own, it is fairly well known, well at least in name due to the use of it by Paul Graham for his incubator (Y-Combinator).

The Fixed-Point Combinator allows one to implement anonymous recursion which is a powerful programming technique. It also ties into some deeper theoretical aspects of computer science and logic such as Combinatory Logic.

Many CS majors may cringe at this, and another possible reaction is that’s not much of an equation. There’s actually quite a bit to this for example did you know there are some substantial and quite beautiful equations associated with this seemingly simple formula. They are:

Also the following is a definition of (lim sup) Limit Superior:

Where inf is infimum and sup is supremum two concepts that seem to show up quite a bit especially when you are concerned with bounds like with Lattices and they also seem to show up in relation to Topology.

And we all know why we should care about his one: Algorithms, Algorithms, Algorithms.

Euler’s Identity is also listed in Wired’s article and I have to agree that it is one the most beautiful and intriguing formulas in math.

Now this isn’t really as relevant to CS as the other formulas but if you a true computer geek you are hopefully some kind of math geek, and this is such a great formula, not to mention that it appears in The Simpsons' Homer³. It’s actually a specific case (where θ = π) of Euler’s Formula:

These formulas will give one a better understanding complex numbers which are needed in other areas of advanced math also these formulas relate to Fourier Analysis which does have applications in Computer Science.

I am curious to see how well this list holds up, how will I feel about it in a year? Also in writing this I realized that I still have quite a bit more to learn about at least half of this list, if not all of it, which made it hard to write as it was quite a little (unfinished) research project. I have already written individual articles on several of these equations and have at least two in the works for Linear Algebra, at least two on the Relational Algebra and one planned for Pascal’s Triangle, and those are just the ideas I’ve already had, who knows what the future holds. I hope you enjoyed it as much as I did writing it.

^† The Set version may not apply to all cases in set theory, this assumes Union and Intersection over the Power Set of a Set Universe, this would be closed under these operations and would include complements of all elements. The Set Universe is the upper bound and the empty set is the lower bound.

(∀x∈ S) x ≤ x;	(reflexive)
(∀x, y ∈ S) if x ≤ y and y ≤ x then x = y;	(antisymmetric)
(∀x, y, z ∈ S) if x ≤ y and y ≤ z then x ≤ z.	(transitive)

Antony and Cleopatra

Julius Caesar

The Tempest