Elegant Coding

Reimagining the Suburban Yard to Reverse Pollinator and Insect Decline

The Problem with Today’s Software Thought Leaders

References and Further Reading

Data Science DC: Deep Learning Past, Present, and Near Future

An Incomplete History of Deep Learning

A Brief and Incomplete History of Game Playing Programs and AIs

The Present and Future

Deep Learning 101/Getting Started

Final Thoughts

References and Further Reading

Software Development is a Risky Business

My Ant Symbiosis Stories

What is Software Engineering?

What is Software Correctness?

A Brief and Incomplete History of Computing from Ancient to Modern

A Survey of Graph Theory and Applications in Neo4J

Are Your Developers Treating Your Project as Their Own Personal Science Project?

Haskell DC

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

Aggressive Native Plants Will Own Your Yard

Bees Are Very Diverse

Bees Are Not the Only Pollinators

Many Things Are Pretending to Be What They Are Not

You’ll Have Lots of Predators

Arachnids Are Sneaky and Exhibit Intelligence and Individualistic Social Behavior

Spiders Seem to Have a Better Understating of Topology than Humans

Indian Hemp Is an Amazing Plant

Every Year Brings Something New

You Can Create an Amazing Amount of Biodiversity in Even a Tiny Yard

You Can Witness Mysteries of Nature That Even Scientists Don’t Really Understand

You Can Be a God

Your Local Municipality Is Most Likely the Enemy of the Environment

The Solution to Our Pollinator Crisis Might Literally Be in Our Backyards

All Things Come to an End

Online Learning Resources

Some Additional Resources

Core Concepts

Git Clone, Hack, and Repeat

Building Deep Learning Systems

Some Leading Deep Learning Researcher's Links

Haskell Language

Ecosystem

Practical Uses

Advanced Topics and Uses

Theoretical

Interesting (Haskell Related) Publications

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

A Possible Pollinator Solution and Other Things I Learned from My Nature Yard

Deception Might be a Preferred Approach in Nature

Data Sets

Deep Learning Frameworks

References and Further Reading

Rhino Thorn Bugs: Masters of Camouflage

Protection and Feeding

Castes

Rhino Thorn Bugs, the Next Generation

The Next Year, New Ants and Aphids

References and Further Reading

REQUIREMENTS

STRUCTURAL

BOTH

References and Further Reading

History of Computing from Ancient to Modern

Videos

References and Further Reading

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

Part 1

Part 2

noreply@blogger.com (elegantcoding) — Wed, 07 Mar 2018 17:19:00 +0000

I wanted to share some things that I learned from growing native plants in my yard. This will be about what I learned about nature and some discoveries about how we might rethink the idea of the suburban yard from an alternate land management perspective.

My ideas and approach come from my childhood. I grew up in a bucolic setting in a heavily wooded area. My mother’s side of my family is Pennsylvania Dutch and we carried on some of those traditions in collecting wild berries for jams and pies and growing our own food in gardens. Another thing we would do was transplant plants from the woods to gardens, although I now realize this was probably not really a good thing to do. I was different from other kids, more curious. I thought plants were beautiful and learned to identify them. I still remember the thrill of finding large patches of native orchids. I was a general science geek and over the years I got distracted by chemistry and eventually computers which lead to my career as a software developer.

Years ago I purchased my first and to date only home. Initially I mowed my lawn and maintained it in the spirit of the American suburbs. My love of native plants never really died out and became rekindled by the local flora. Instead of transplanting plants I merely collected a few seeds here and there and started planting them in pots and the garden areas of my yard. Over time I let them take over my whole yard and what I came to see was amazingly beautiful.

Please note that I took all the photographs in this post and with one exception, try to guess which one, they were all taken in my yard and thus they document the biodiversity that I created. You can click each photo to enlarge.

My yard became something of a Darwinian botanical Battle Royale. As I planted various species of native plants and spread their seeds in my yard, I realized that given the soil and varying climatic aspects of the environment of my yard, some plants tended to be dominant. Unfortunately some of the more interesting plants got outcompeted by the more robust plants. These plants are perhaps less glamorous and while they are native plants and in some cases represent the natural cultural heritage of the region, Arlington County Virginia considers them weeds. The upside is if you are lucky enough to live in a municipality that respects science, nature and its regional natural cultural heritage, you can with little watering and some periodic weed pulling of invasives create an environment where native species can dominate your property.

If you follow the news you have no doubt heard about the plight of the bees, for brevity’s sake the beepocalypse. What you may not realize is that the bees whose plight wins the attention of the media are an alien European species. They are even trucked around like cattle to almond groves and other places and are made of use to pollinate the flowering plants that feed us, excluding the wind pollinated plants like wheat and oats. In these stories we contemplate the Matrix like gruel that humanity will be subjected to when the pollinators die off and we only have the wind pollinated species for food. What they never tell you is that there are another set of bees constituting over a thousand species that might be able to step up and take on that role. Maybe they could make the difference in pollination. What would happen if we give them the habitat and opportunity to flourish? Maybe we wouldn’t even need to create Black Mirror style robobees.

In my native plant yard I saw many species over the years and in the summer of 2016 it seemed that hundreds maybe thousands of bees visited my yard in a day. At times it was like a small cloud of dozens of tiny bees floating above each of the plants in addition to all of the other bees. That year in my yard the pollinator crisis seemed to be a myth as I saw the exact opposite of what I have read about. Admittedly this is only one observation.

While this statement might seem somewhat obvious as most people know that Butterflies (Lepidoptera) are also pollinators.

There are also other insects in the Hymenoptera family such as wasps and ants that also pollinate plants.

Additionally some flies (Diptera) are pollinators as well. In fact some plants like the Pawpaw tree, a tree known to my ancestors, with its fleshy colored flowers are dependent on carrion flies and beetle pollinators. People will sometimes hang rotting meat and chicken bones on its branches to attract these pollinators.

In nature insects use mimicry to try to deceive predators and prey. Hemipterta often try to look like parts of a plant, such as thorns or look like insects that are infected with fuzzy white insecticidal fungus.

Lepidoptera will have eye patterns to dissuade predators from sneaking up on them. One even mimics the Monarch Butterfly which is unpalatable due to absorbing milkweed toxins.

Another potential human deception is to try to look like a badass. In the insect world some of biggest badasses are wasps and bees of Hymenoptera who have stingers. So if you want to look like a badass look like a wasp or a bee that can sting you even if you are a wimpy little fly. The bottom left is a moth so even Lepidoptera gets in on this deception. Nature is not without irony the Large headed fly (bottom right) actually lays its eggs in bumble bees and they gestate “alien style”, although apparently do not usually kill their hosts like the aliens.

When you create a habitat that attracts a lot of insects it also attracts a lot insect predators. Birds and spiders obviously fall into that category. There are many insects that predate on other insects. Many larva including those of flower flies are predatory. I suspect that yellow larva (bottom right) is waiting for an unsuspecting pollinator. Top left an assassin bug feeds on a flower fly. The two iridescent flies are long legged flies, predators who do elaborate mating dances on leaves throughout the day.

Some spiders employ deceptive hunting techniques. As you can see above there are two crab spiders hiding and blending into the flowers. I don’t know what the longer legged one in the two adjacent pictures is but it seems to be mimicking either a flower or a flower fly which I suspect was one of things it was trying to capture as there were lots of them around the Enchanters Nightshade plants it was hanging from.

Around the time I got my macro lens and started observing the jumping spiders in my yard, I came across an article about the surprising intelligence of the Portia jumping spider. I have to admit they are fun to watch they move incredibly fast and their eye configuration is remarkable with two large eyes in the front and posterior eyes that potentially give them 360 degree vision, just try to imagine your brain processing that perspective. They seem intelligent, it also seemed like they got used to being photographed and went from fleeing me to just ignoring me.

Opiliones aka Daddy Long Legs aka Harvestmen exhibit individualistic social behavior. The photo above shows what is reffered to as loose aggregation social behavior. They would hang out with each other all day long sometimes in clusters of up to 20-30 individuals.

I can’t help but to go on an astrobiological tangent here. If you look at our deep ocean creatures you’ll often find cephalopods (octopuses, squids, etc.) and arthropods like crabs and lobsters which are related to our terrestrial arachnids, insects, among others. A recent article talked about the possible ocean and life on Saturn’s moon Enceladus. I used to think it would be Jupiter’s moon Europa, but it might have issues of the water being under too high pressure. If complex and even intelligent life were to evolve in these environments it could look similar to life in our oceans.

Cephalopods clearly display intelligence. However, if one were to consider the jumping spider intelligence and individualistic opiliones social behavior this could point to the idea of intelligent social arthropods. Could these species be a possible mirror to what intelligent life might look like deep in these ice moons oceans?

Ok, I’m going to embellish these a bit. In the top left you can see the conical shape created below the egg sac, probably a trap to funnel prey. However, it’s very much a two manifold exhibiting a local maxima, most of the computer industry is trying to find these places with machine learning. The bottom left shows the Cartesian-esque plane making it locally Euclidean and thus a 2 manifold yet again. The bottom right shows a typical spiders web, this, albeit a bit irregular, exhibits a polar coordinate representation of two dimensional plane, or perhaps a vector field on a two dimensional plane. The spider on the top right sits atop an irregularly spaced two dimensional plane.

It is likely the local Necostins relied on Indian Hemp (Apocynum Cannabinum) for fibers for their bowstrings and maybe for other uses. You can lean more from the film Soft as Silk - Strong as Steel: The living heritage of Apocynum Cannabinum. In fact I would make the case that this plant should be allowed to grow everywhere based on the fact that it is the natural cultural heritage of our region and I know it sounds cheesy but out of respect for those who came before us here on this land.

Ok, Native American pretense and drama aside, there are some very practical reasons to grow Apocynum Cannabinum. Last year it seemed to flower for about six weeks in late spring early summer, which means it supplied six weeks of flowers to support pollinators in that time period while not competing with the late summer plants it grew next to in my yard.

Its strong structure that is comprised of those fibers seems to provide a physical support lattice that benefits other plants. Indian Hemp Apocynum Cannabinum grows to a certain height. Amongst it Jerusalem Artichokes, Wingstem, Hairy Leafcup, and Common Milkweed, grew taller and bloomed later. When I was forced to cut down my yard, I manually removed all of the Indian Hemp first as I had intended to investigate how to extract fibers. I noticed that the other plants seemed to have some physical dependence on the structural support it provided as they immediately fell over. Now I know this is all anecdotal but it really did seem to make a difference. Of course I had to cut down all of the other plants too so who knows how that might have played out. Indian Hemp is related to milkweed, it has a milky sap and the leaves are hydrophobic as you can see in the photo above. This creates significant plant mass that is pretty insect resistant. It’s also a very hardy species so it can probably survive a lot of hardship.

If you look at many of my pictures of insects and spiders it plays the role of the stage for many of them. In fact the jumping spiders seemed to use it as a way to move quickly in three dimensions and to catch ants on it. While, the iridescent long legged flies performed their mating dances on its leaves.

Every year in my yard I would see something I had not seen before and in many cases would not see again. One year it was shiny metallic Dog Bane Beetles. Another year it was lots of ants symbiotically tending to a brood of Rhino Thornbugs and aphids the next year. Last year it was lots of jumping spiders, tiny bees, flower files, and lots of milkweed bugs mating. The year before that it was an Opiliones explosion with hundreds of them. I suspect things like predator prey cycles or other factors in climate and the plants and fungus each year affected what I saw. Regardless, it is such a thrill to just experience what a nature yard will throw at you each year. While this year brought me ground dwelling bees and hawks, sadly it also brings me much sorrow and stress.

My little yard, less than a quarter acre, supported around 20 species of native plants. This is fairly diverse for such a small yard. But the real diversity came in the form of the visitors especially the terrestrial arthropods, insects and arachnids but also many birds, chipmunks, and rabbits. I am still astounded by what I saw when I would just look out the window or take a few steps out of my front door. The photos here present it and there are many more species that I did not show.

Above I mentioned the Loose Aggregation Social behavior of Opiliones. What’s really interesting and maybe a little sad is that scientists don’t really understand this behavior and there are way more questions than answers about the social structure and motivations of these creatures. In a sense this is a true mystery of the universe and it happened one summer in my own back yard. Amazing!

I the movie Groundhog Day Bill Murray’s character Phil Connors declares himself a god, not the god, but a god. This is due to the fact that he knows everything about the local environment and all events that he has not altered ahead of time. When you plant a yard of native plants you create the natural environment in your yard. You create the opportunity for the most amazing things in nature to exist in your yard. You conjure these things into existence. Ok, it’s an: “if you build it they will come” scenario. In a sense you become a god creating nature. Admittedly a less dramatic perspective is you allow this to happen and the nature already existed. But it’s a fun way to think of it and chances are all the drones living next you are creating the antithesis of this in their chemically treated monoculture yards.

Unfortunately many municipalities, in spite of their pro-environmental rhetoric and propaganda, consider dense native plants in residential yards a nuisance. In Arlington County the code enforcement officers refer to it as an “infestation”, which vaguely sounds like saying “witch”. They also call it a public health and safety hazard for which I doubt they have any supporting evidence. If you want to grow a native environment on your personal property, which should be your right, expect to be treated like a criminal and to be met with very parochial attitudes from very ignorant, very arrogant, and very officious local government employees whose salaries are paid for by your tax dollars. Unfortunately, local ordinances effectively promote the use of toxic chemicals in suburban yards to maintain monoculture grass yards over native plants.

America really needs to rethink its obsession with the chemical treated manicured lawn. Of course this is big business and I would not be surprised that if in aggregate, chemicals, services, equipment and other incidentals would number into the billions of dollars so there are obvious economic incentives to keep this going. But are we really looking at the true costs here. Local municipalities promote this through their ordinances and here in the Chesapeake estuary local citizens and service companies probably contribute tons of pesticide, herbicide and fertilizer run off that ends up in the Chesapeake. My yard used none of these and replaced almost all of the grass with native plants. In my back yard there was exposed dirt at the base of thick swaths of Virginia Knotweed, this is good habitat for native bees. I would also leave tree branches to rot in my yard which also provided habitat for native bees, flies, arachnids, fungus and other things. This also reduced the amount biomass that got fed into the county collection system which is funded at taxpayer expense. It even felt like my air conditioner ran less with tall Jerusalem Artichokes, Hairy Leafcup and Indian Hemp in the front yard and as I mentioned it was amazingly beautiful.

Now of course there are some potential pitfalls that need to be avoided and can be through the management of a nature yard. Things like rat harboration would be a potential issue. I did have a chipmunk burrow, not sure if that counts as a hazard. Especially since chipmunks are super cute and the baby ones are even cuter. Also I would destroy any colonies of wasps or yellow jackets as they are a danger to people unlike many of the native bees which are stingless.

It seems to me if local municipalities would take an active role in encouraging native plant yards and were to create programs to help manage them and inspect them for potential hazards that many pollinators could be added to our local environments. I don’t have any actual numbers so this is guestimate but it seemed like my tiny yard at its height was supporting hundreds maybe even over a thousand flower fly and native bee pollinators and I mean habitat for them to breed as well.

Arlington County and other municipalities could probably add hundreds of thousands if not millions of pollinators locally by allowing and incentivizing these types of yards, even at relatively low rates of adoption. They would benefit the Chesapeake as well from reduced run off. Think of the effect if this approach were to spread through the Mid-Atlantic megalopolis and the other megalopolises in the United States.

Of course this is all conjecture on my part and I am a fan of science, I regret not applying a more scientific method to my yard, but it started as an innocent hobby. This is an area that is under study at the National Arboretum (pdf) and should probably be studied more in situ. Of course how can you when it’s illegal in most municipalities in the U.S.

I have decided to sell and move out of Arlington. Arlington loves McMansions with monoculture lawns and that’s exactly what they will get: one more. I used to be somewhat proud to call myself an Arlingtonian, now I am just disgusted by Arlington County Government. There are some other very annoying issues pertaining to the neighborhood that I live in that I tolerated due to my yard, they are now unbearable. I will try to transplant some of the plants but many will not make it. I will be sad to see the remains of what I built completely destroyed. But in life sometimes you have to let go to move on. I just hope what I did here will make some difference some day.

noreply@blogger.com (elegantcoding) — Mon, 10 Apr 2017 13:13:00 +0000

Albert Einstein once said: "What is right is not always popular and what is popular is not always right." The current zeitgeist in software development has this exact same feel. Our lives as software developers have been shaped by the ideas of many people. Some of those ideas are right and some are popular. In time the wrong ideas will fade and the right ideas will dominate. The problem is: How do we make that determination in the present? What are the good ideas and what are the bad ideas?

As software developers our working days usually consist of two types of professional activities, one is obviously creating software (software development) or related technical tasks configuration management, troubleshooting, deployments, etc. and the other is being managed or other duties that relate to providing information (status) to managers (software development management). The software industry is very young and constantly changing. At any given moment there are dominant de facto standards that are followed for both software development and its management. Although it varies across industry sectors, many development practices and tooling have become standards, things like IDE’s, continuous integration, the use of tests and testing frameworks, etc. Some of these have been influenced by Agile and XP. On the management side the standard seems to be largely dominated by Agile like scrum and associated practices from XP.

The people who dominate our industry with their ideas could be described as our thought leaders. Wikipedia has the following definition for thought leader:

A thought leader can refer to an individual or firm that is recognized as an authority in a specialized field and whose expertise is sought and often rewarded.

The creation of Agile was done in a ceremonious fashion, depicted in an odd ritualistic looking and now famous photograph, by signatories to a manifesto. Let’s call these people the Agile Thought Leaders or just the Agilistas (since brevity is our thing). The Agilistas have come to have their ideas dominate the industry and in many cases dictate how we now spend our days.

It seems that Agile’s rise in popularity is directly proportional to my increasing skepticism about it. I find myself internalizing that skepticism into frustration and even feelings of anger towards it and the Agilistas. These feelings become exacerbated by the various incarnations of Agile created by legions of certified Agile consultants that roll into my life to tell me how to spend my days.

Now those feelings are not constructive and one really needs to step back and ask: Why is what I see in the industry wrong and how can I form and a constructive criticism of it?

I was lucky to come across Greg Wilsons’s talk: "What We Actually Know About Software Development, and Why We Believe It's True". This is a very enlightening talk which I highly recommend. In it he looks objectively at how we have arrived where we are and how we can possibly better move forward. I got the term Agilistas from his talk, although I don’t know if he coined it.

The talk touches on issues that I feel plague both my career and our industry. The problem manifests itself in how we make our decisions about what we do on projects both from the day to day and to the larger industry practices. Many of these decisions seem to be influenced all too often by people who claim some authority, sometimes it’s positional authority, sometimes it’s due to some form of gravitas and all too often right or wrong it boils down to someone’s opinion. To better illustrate this about our thought leaders let's look at Greg Wilson’s critique of one of Martin Fowler’s publications about DSL’s (Domain Specific Languages). The relevant quotes with time stamps are as follows:

11:26 [Martin Fowler] is a very deep and careful thinker about software and software design and last summer in IEEE Software he had an article on Domain Specific Languages, this notion that build a tiny language in which the solution to you original problem in easy to express. And in that he said using DSLs leads to improved programmer productivity and better communication with domain experts.
11:51 I want to show you what happened here. One of the smartest guys in our industry made two substantive claims of fact in an academic journal and there is not a single citation in the paper. Not a single foot note or reference. There is no data to backup this claim. I am not saying that Martin is wrong in his claims. I am saying is what we have here is a Scottish verdict. Courts in Scotland are allowed to return one of three verdicts, guilty, innocent, or not proven. Arguments in favor of DSLs, arguments in favor of functional programming languages making parallelism easier or Agile development leading to tenfold return on investment or whatever are unproven. It doesn’t mean they are or wrong, it doesn’t mean they are right, it means that we don’t know and we should be humble enough to admit that.
12:38: Carrying on in that same article "Debate still continues about how valuable DSLs are in practice. I believe that debate is hampered because not enough people know how to develop DSLs effectively." Crap I think the debate is hampered by low standards of proof.
12:55: Listening computer scientists argue, listening to software engineers in industry argue, it seems that the accepted standard of proof is I’ve two beers and there’s this anecdote about a tribe in new guinea from one of Scott Berkin’s books that seems to be vaguely applicable therefore I’m right. Well no, sorry that’s not proof and you should have higher standards than that.

I think these are excellent points. I disagree with Greg Wilson here and feel that Martin Fowler is not one of the smartest guys in our industry, although he maybe one of the most influential. I also question whether he can be considered a careful thinker. I think his approach like many of the other Agilistas is self serving and shows very little humility or willingness to be self critical. This is something that Bertrand Meyer commented on when reaching out to the Agilistas in conjunction with his book on Agile! The Good, the Hype and the Ugly that almost all of the Agilistas treated him with "radio silence" after receiving his draft. The problem is that the Agile business is just too lucrative for consulting and on the speaking circuit. A great example of this business model is "Uncle Bob" Martin’s infomercial-esque site promoting his wisdom for sale. I refuse to link to it, so google it, if you want to see that spectacle. All of these guys make a lot of money selling Agile and if they started being critical of it that would be a risk to their revenue streams. Also how many of these guys still do significant software development work? Ironically I think Uncle Bob still codes, but I am talking about opening up an IDE or text editor after checking out a big code base from version control and fixing bugs or doing actual coding or refactoring. Now maybe that’s not fair to ask that, or is it? After all they are driving how we spend our days being managed on software projects.

Another point of contention I have can be found on Martin Fowlers website under the FAQ section:

Why is your job title "Chief Scientist"?
It's a common title in the software world, often given to someone who has a public facing technical role. I enjoy the irony of it - after all I'm chief of nobody and don't do any science.

He openly admits he does no science (the black bolding is mine). Therein lays the problem with all of the Agilistas. There seems to be no scientific method involved in many if not all of their claims. These claims as we have seen are sometimes made in "academic" journals without any citations. Of course I am skeptical about much that is written about software in journals published by ACM or IEEE and of the organizations themselves. I think Greg Wilsons observation validates my skepticism and further draws attention to the lack of scientific method involved in software. We need better science and people who are intellectually honest about the fact that they are just expressing unproven and in some cases unfounded opinions.

It seems to me a more conscientious approach would be for the Agilistas to promote and fund studies. Use the scientific method to back up their claims and help move the industry forward. Whether they like it or not that is what will most likely eventually happen and they will either need to get on board or be left behind.

The irony here is that while we need more of a scientific method in defining software methodologies, much of our infrastructure comes from mathematics, another area that seems to be lacking with the Agilistas. For example: Noam Chomsky’s formalization of grammars were adapted by Jim Backus and further refined algebraically by Donald Knuth to give us modern compiler theory and compilers. There’s a long list of people who have laid down the mathematical foundations, people like Alan Turing, John Von Nueman, Alonzo Church, Stephen Cole Kleene, Haskell Curry and the list goes on. Unfortunately I think too many people in our industry are ignorant of our field’s true mathematical underpinnings. I have also encountered a large degree of anti-intellectualism from programmers when it comes to applying modern math to programming. Again I think this is an area where one should only ignore it at their own peril.

If you want to see the work that should and probably will drive our future I would recommend looking at what the researchers are doing, people like:

These are just a few. There are many people doing research that will eventually find its way into our industry. It has been happening this way all along. The problem with these people’s work is it requires real intellectual effort as opposed to the Agile approach which, while in some cases maybe common sense, all to often seems to come across as a bunch of platitudinous management speak.

I think we need to hold the Agilistas to higher standards of proof!

Disclaimer: I still code personal projects but have not been on a dev team doing real dev work in about 3-4 years after doing it for over 25 years. Actually from what I have seen of Agile management techniques and war room/open office layouts, I am in no hurry to do any of that any time soon.

noreply@blogger.com (elegantcoding) — Wed, 08 Feb 2017 14:55:00 +0000

Here in Washington DC we are lucky to have a robust technical community and as a result we have many great technical meetups which include a number that fall under the local data science community. I recently attended the Data Science DC (DSDC) talk "Deep Learning Past, Present, and Near Future" (video) (pdf slides) presented by Dr. John Kaufhold who is a data scientist and managing partner of Deep Learning Analytics. This will be the second DSDC post I have written, the first is here. Parts of this post will be cross posted as a series on the DSDC blog (TBA), references to my previous blog posts either here or there will be to referring to my blog elegantcoding.com. My previous DSDC post was pretty much just play by play coverage of the talk. I decided to take a slightly different approach. My goal here is to present some of the ideas and source material in John's talk while adding and fleshing out some additional details. This post should be viewed as "augmentation" as he talks about some things that I will not capture here.

I am guessing that some proportion of the audience that night is like me in that they feel the need to learn more about deep learning and machine learning in general. This is a pressure that seems to be currently omnipresent in our industry. I know some people who are aggressively pursuing machine learning and math courses. So I would like to add some additional resources vetted by John for people like myself who want to learn more about deep learning.

I decided to make this a single post in with parts. This will essentially parallel John's presentation, although I will change the order a bit. The first part will summarize the past, present, and future of deep learning. I will be doing some editorializing of my own on the AI future. The second part will be an augmented list of resources including concepts, papers, and books in conjunction with what he provided for getting started and learning more in depth about deep learning.

I will give a brief history of deep learning based in part on John's slide, well actually Lukas Masuch's slide. I am a fan of history, especially James Burke Connections style history. It is hard for me to look at any current recent history without thinking of the greater historical context. I have a broader computer history post that might be of interest to history of technology and history of science fans. Three earlier relevant events might be the development of the least squares method that lead to statistical regression, Thomas Bayes's "An Essay towards solving a Problem in the Doctrine of Chances" and Andrey Markov's discovery of Markov Chains. I will leave those in the broader context and focus on the relative recent history of deep learning.

1951: Marvin Minsky and Dean Edmonds build SNARC (Stochastic Neural Analog Reinforcement Calculator) a neural net machine that is able to learn. It is a randomly connected network of Hebb synapses.

1957: Frank Rosenblatt invents the Perceptron at the Cornell Aeronautical Laboratory with naval research funding. He publishes "The Perceptron: A Probabilistic Model for Information Storage and Organization in The Brain" in 1958 . It is initially implemented in software for the IBM 704 and subsequently implemented in custom-built hardware as the "Mark 1 Perceptron".

1969: Marvin Minsky and Seymour Papert publish Perceptrons which showed that it was impossible for these classes of networks to learn an XOR function.

1970: Seppo Linnainmaa publishes the general method for automatic differentiation of discrete connected networks of nested differentiable functions. This corresponds to the modern version of back propagation which is efficient even when the networks are sparse.

1973: Stuart Dreyfus uses backpropagation to adapt parameters of controllers in proportion to error gradients.

1972: Stephen Grossberg published the first of a series of papers introducing networks capable of modeling differential, contrast-enhancing and XOR functions. "Contour enhancement, short-term memory, and constancies in reverberating neural networks (pdf)".

1974: Paul Werbos mentions the possibility of applying back propagation to artificial neural networks. Back propagation had been initially context of control theory by Henry J. Kelley and Arthur E. Bryson in the early 1960s. Around the same time Stuart Dreyfus published a simpler derivation based only on the chain rule.

1974–80: First AI winter which may have been in part caused by the often mis-cited 1969 Perceptrons by Minsky and Papert.

1980: Neoconitron, a hierarchical, multilayered artificial neural network, is proposed by Kunihiko Fukushima. It has been used for handwritten character recognition and other pattern recognition tasks and served as the inspiration for convolutional neural networks.

1982: John Hopfield popularizes Hopfield networks, a type of recurrent neural network that can serve as content-addressable memory systems.

1982: Stuart Dreyfus applies Linnainmaa's automatic differentiation method to neural networks in the way that is widely used today.

1986: David E. Rumelhart, Geoffrey E. Hinton and Ronald J. Williams publish "Learning representations by back-propagating errors (pdf)". This shows through computer experiments that this method can generate useful internal representations of incoming data in hidden layers of neural networks

1987: Minsky and Papert publish "Perceptrons - Expanded Edition" where some errors in the original text are shown and corrected.

1987–93: Second AI winter occurs. Caused in part by the collapse of the Lisp machine market and the fall of the expert system. Additionally training times for deep neural networks are too long making them impractical for real world applications.

1993: Eric A. Wan wins the an international pattern recognition contest. This is the first time backpropagation is used to win this contest.

1995: Corinna Cortes and Vapnik publish current standard incarnation (soft margin) in "Support-Vector Networks". The original SVM algorithm was invented by Vladimir N. Vapnik and Alexey Ya. Chervonenkis in 1963. SVMs now take a dominant role in AI.

1997: Sepp Hochreiter and Jürgen Schmidhuber invent Long-short term memory (LSTM) recurrent neural networks greatly improving the efficiency and practicality of recurrent neural networks.

1998: A team led by Yann LeCun releases the MNIST database, a dataset comprising a mix of handwritten digits from American Census Bureau employees and American high school students. The MNIST database has since become a benchmark for evaluating handwriting recognition. Lecun, Bottou, Bengio, Haffner publish "Gradient-Based Learning Applied to Document Recognition (pdf)"

1999: NVIDIA Invents the GPU

2006: Geoffrey Hinton and Ruslan Salakhutdinov publish "Reducing the Dimensionality of Data with Neural Networks (pdf)" This is an unsupervised learning breakthrough that now allows for the training of deeper networks.

2007: NVIDIA launches the CUDA programming platform. This opens up the general purpose parallel processing capabilities of the GPU.

2009: NIPS Workshop on Deep Learning for Speech Recognition discovers that with a large enough data set, the neural networks don't need pre-training, and the error rates drop significantly.

2012: Artificial pattern-recognition algorithms achieve human-level performance on certain tasks. This is demonstrated by Alex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton using the ImageNet dataset and published as "ImageNet Classification with Deep Convolutional Neural Networks (pdf)".

2012: Google's deep learning algorithm discovers cats. AI now threatens the cat cabal control of the internet.

2015: Facebook puts deep learning technology - called DeepFace - into operation to automatically tag and identify Facebook users in photographs. Algorithms perform superior face recognition tasks using deep networks that take into account 120 million parameters.

1951: Alan Turing is first to publish a program, capable of playing a full game of chess, developed on paper during a whiteboard coding interview.

1952: Arthur Samuel joins IBM's Poughkeepsie Laboratory and begins working on some of the very first machine learning programs, first creating programs that play checkers.

1992: Gerald Tesauro at IBM's Thomas J. Watson Research Center develops TD-Gammon a computer backgammon program. Its name comes from the fact that it is an artificial neural net trained by a form of temporal-difference learning.

1997: IBM Deep Blue Beats Kasparov, the world champion at chess.

2011: IBM's Watson using a combination of machine learning, natural language processing and information retrieval techniques beats two human champions on the TV game show Jeopardy! Later versions of Watson successfully banter with Alex thus further surpassing human capabilities.

2013: DeepMind learns to play 7 Atari games, surpassing humans on three of them, using Deep Reinforcement Learning and no adjustments to the architecture or algorithm. It eventually learns additional games taking the number to 46.

2016: AlphaGo, Google DeepMind's algorithm, defeats the professional Go player Lee Sedol.

2017: DeepStack becomes the first computer program to beat professional poker players in heads-up no-limit Texas hold'em.

John also included the idea of Geoffrey Hinton, Yann LeCun, and Yoshua Bengio being the triumvirate that weathered the AI winter, a theme that he used in his first DSDC talk as well. Since it was one of Homer's vocabulary words, I couldn't resist creating my own graphic for it:

While the triumvirate researchers are definitely major players in the field, there are many others. There seems to be some drama about giving credit where credit is due. John goes into some of the drama surrounding this. Unfortunately it seems to human nature sometimes we have drama surrounding scientific discoveries and this is no exception in the Deep Learning community today. Geoffrey Hinton also catches some flak on reddit (ok, no surprise there) for not properly crediting Seppo Linnainmaa for backpropagation. It is natural to want credit for one's ideas, however, these ideas are never conceived of in a vacuum and sometimes they are discovered independently, Calculus springs to mind. As they say history is written by the winners. John made a remark about Rosalind Franklin's Nobel Prize for the double helix. I asked him how many people in the audience he thought got that remark and he replied: "One, apparently :) I'll take it!" Lise Meitner is another interesting example of someone who failed to be recognized by the Nobel committee for her work in nuclear fission.

A major name in the field is Jeff Dean. John mentioned Jeff Dean facts. This is apparently based on the Chuck Norris facts. Jeff Dean somewhat of a legend and it is hard to tell what is real and what is made up about him. Do compilers really apologize to him? We may never know. As I understand it he was one of the crucial early engineers to have helped create the success of Google. He was instrumental in the conception and development of both Map Reduce and Big table not only solidifying Google's successful infrastructure but also laying down much of the foundation of major big data tools like Hadoop and Cassandra. There is some serendipitous timing here in that Jeff Dean published "The Google Brain team - Looking Back on 2016" on the Google Research Blog a few days after John's talk. His post lays out a number of areas where deep learning has made significant contributions as well other updates from their team.

The present and near future for Deep Learning is very bright. There are many deep learning companies that have been acquired and many of these are small averaging about 7 people. John describes this as a startup stampede. Most likely a lot of these are acqui-hires since the labor pool for deep learning is very small. Apparently the top talent is receiving NFL equivalent compensation.

It's fairly obvious that deep learning and machine learning are the current hotness in our industry. One metric might be, given any random moment, go on hacker news and you will most likely see a deep learning article if not a machine learning article on the front page. As if this is not enough, now Kristen Stewart famous for the Twilight movies, has coauthored an AI paper: "Bringing Impressionism to Life with Neural Style Transfer in Come Swim". I am now waiting for an AI paper from Jesse Eisenberg.

As for perspectives on the future of Machine Learning John recommends chapters 2, 8, and 9 of the free O'Reilly book The Future of Machine Intelligence. He also points out that the idea that deep learning does not necessarily mean neural Nets and that it means the number of operations between the input and output. This means that machine learning methods other than neural nets can have a deep architecture. It's about the depth itself that learns the complex relationship. For this he cites "Learning Feature Representations with K-means (pdf)" by Adam Coates and Andrew Y. Ng.

Christopher Olah in his post: "Neural Networks, Types, and Functional Programming" talks about how deep learning is a very young field and that like other young fields in the past things are developed in an ad hoc manner with more of the understanding and formalisms being discovered later. As he points out we will probably have a very different view of what we are doing in 30 years. Although that last point is a bit obvious, it still helps to put things in context. So it is probably hard to tell what will be the most fruitful AI algorithms even ten years from now.

At the end of his talk John touches on a bigger issue that is becoming more ubiquitous in conversations about deep learning and AI: What are the larger social implications for society? So I thought I would contemplate some possibilities.

The first and perhaps most imminent and frightening concern is the loss of jobs due to automation. Many people argue that this is the same fear that was raised especially during the first two industrial revolutions which occurred in the late 18^th-early 19^th century and the late 19^th-early 20^th century. Of course how you classify industrial revolutions can vary and can easily be off by one if you include the Roman innovation of water power. These industrial revolutions displaced certain skilled jobs by mechanizing work and created new, perhaps less skilled factory jobs. The third industrial revolution mid-late 20^th century can be thought of be the rise of more factory automation and the development of microprocessor which can be described in simple terms as a general electronic controller, of course it is way more than that. This continued automation lead to many things like specialized robots for manufacturing. This meant still less jobs for people. Now we are on the cusp of what is being called the fourth industrial revolution with generalized AI algorithms and multipurpose robotics.

I have often heard the argument that this has all happened before. John brings up a valid point on this which is when it happened before there was a lot more time for society to recover and new jobs were created. There was an article on NPR identifying truck driver as one of the most common jobs in America. There is some dispute of this in that the most common jobs are retail jobs. Regardless of which is the most common job, still there are by some estimates 3.5 million truck driver jobs in the US. Self driving vehicles are very possibly less than five years away. That means those jobs, not to mention taxi jobs as well will be lost. How long before you click purchase on an ecommerce website like Amazon and no humans are involved in that purchase arriving at your house? This might be about that same timeframe. This is an unprecedented level of automation and it affects many other professions for example some paralegal and radiology jobs are potentially now under threat.

There is of course an upside. If AI's become better at medical jobs than humans that could be a good thing. They won't be prone to fatigue or human error. In theory people could liberated from having to perform many tedious jobs as well. AI's could usher in new scientific discoveries. Perhaps they could even make many aspects of our society more efficient and more equal. In this case I for one would welcome our AI overlords.

It is hard to contemplate the future of society without thinking of the work of Orwell and Huxley, this comic sums up some of those concerns and begs the question how much of this do we currently see in our society. From the Orwellian perspective programs like PRISM and the NSA's Utah Data Center allow for the collection and storage of our data. AI's could comb through this data in ways humans never could. This creates the potential for a powerful surveillance state. Of course it is about how this power is used or abused that will determine if we go down the trajectory of the Orwellian dystopia. The other scary aspect of AI's are idea of automated killer drones, this of course is the Skynet dystopia. I think we should fear the Elysium dystopia with both aerial and Elysium style enforcement drones.

Maybe we go down the other path with a universal income that frees us from having to perform daily labor to earn our right to live. How do we now fill our days? Do we all achieve whatever artistic or intellectual pursuits that we are now free to explore? What happens if those pursuits can also be done better by the AI's? Is there a point in painting a picture or writing and singing a song if you will just be outcompeted by an AI? Some of this is already possible. ML algorithms have written reasonable songs, created artistic images as well as having written newspaper articles that are mostly indistinguishable from human writers. Even math and science may fall under their superior abilities for instance Shinichi Mochizuki's ABC conjecture proof seems to be incomprehensible by humans. What if math and science becomes too big and complex for humans to advance it and it becomes the domain of the AI's? So in this case do we fall into Huxley's dystopia? Actually many people would probably find themselves, as some do now, exclusively pursuing drugs, alcohol, carnal pleasures, porn, video games, tv, movies, celebrity gossip, etc. So do we all fall into this in spite of our aspirations? And the AI's will most likely be able to create all of our entertainment desires including the future synthetic Kim Kardashian style celebs.

Ok so that's enough gloom and doom. I can't really say where it will go. Maybe we'll end up with AI hardware wired directly to our brains and thus be able to take our human potential to new levels. Of course why fight it. If you can't beat them join them and the best way to do that is to learn more about deep learning.

John mentions a few resources for getting started. He mentions Christopher Olah's blog, describing him as the Strunk and the White of Deep Learning through his clear communication using a visual language. I have had his "Neural Networks, Manifolds, and Topology" post on my todo list and I agree that he has a bunch of excellent posts. I admit to being a fan of his visual style from his old blog as my post on Pascal's Triangle was partially inspired by his work. His newer work seems to be posted on http://distill.pub/. John also mentions Andrej Karpathy's blog as well as the Comprehensive Course on Convolutional Neural Nets that he teaches Stanford: CS231n: Convolutional Neural Networks for Visual Recognition, which can additionally be found here.

Additionally John did a write up "Where are the Deep Learning Courses? after his first DSDC talk.

If you are local we also have the DC-Deep-Learning-Working-Group they are currently working through the Richard Socher Stanford NLP course.

I wanted to include some additional resources and came up with a list that I asked John's opinion on. These are some that I found that he endorses with high recommendations for Richard Socher's NLP tutorial.

Neural Networks and Deep Learning By Michael Nielsen http://neuralnetworksanddeeplearning.com/

Deep Learning by Ian Goodfellow and Yoshua Bengio and Aaron Courville http://www.deeplearningbook.org/

UDACITY : Deep Learning by Google

ACL 2012 + NAACL 2013 Tutorial: Deep Learning for NLP (without Magic), Richard Socher, Chris Manning and Yoshua Bengio

CS224d: Deep Learning for Natural Language Processing, Richard Socher

These are the additional resources that looked interesting to me:

Deep Learning in a Nutshell by Nikhil Buduma

Deep Learning Video Lectures by Ruslan Salakhutdinov, Department of Statistical Sciences, University of Toronto:

Lecture 1

Lecture 2

Nuts and Bolts of Applying Deep Learning (Andrew Ng)(video)

I wanted to list out some core concepts that one might consider learning. I reached out to John with a list of concepts. He replied with some that he thought were important and pointed out that such a list can grow rapidly and it is better to take a more empirical approach and learn as you go by doing. I think a brief list might be helpful to people new to machine learning and deep learning.

Some basic ML concepts might include:

These are some that are more specific to Neural Nets:

Some additional areas that might be of interest are:

Additionaly a couple of articles that lay out some core concepts are The Evolution and Core Concepts of Deep Learning & Neural Networks and Deep Learning in a Nutshell: Core Concepts.

John mentions the approach of Git Clone, Hack, and Repeat. I asked him if there were and there any specific github repo's that you would recommend? I am just using his reply here, with some of the links and descriptions filled in:

This is really, choose your own adventure, but when I look in my history for recent git clone references, I see:
Torch is a scientific computing framework for with wide support for machine learning algorithms that puts GPUs first. It is easy to use and efficient, thanks to an easy and fast scripting language, LuaJIT, and an underlying C/CUDA implementation. github
Efficient, reusable RNNs and LSTMs for torch
Torch interface to HDF5 library
Computation using data flow graphs for scalable machine learning
This repository contains IPython Notebook with sample code, complementing Google Research blog post about Neural Network art.
Neural Face uses Deep Convolutional Generative Adversarial Networks (DCGAN)
A tensorflow implementation of "Deep Convolutional Generative Adversarial Networks"
Among others--playing with OpenAI's universe and pix2pix both seem full of possibilities, too.
Image-to-image translation using conditional adversarial nets
Openai Universe
To learn, I'm a big advocate of finding a big enough dataset you like and then trying to find interesting patterns in it--so the best hacks will usually end up combining elements of multiple repos in new ways. A bit of prosaic guidance I seem to find myself repeating a lot: always try to first reproduce what the author did; then start hacking. No sense practicing machine learning art when there's some dependency, sign error, or numerical overflow or underflow that needs fixing first. And bugs are everywhere.

I asked John to recommend some data sets for getting into deep learning, he recommended the following:

MNIST

CIFAR-10

NORB

Andrej Karpathy's blog post "The Unreasonable Effectiveness of Recurrent Neural Networks" provides some examples using a Shakespeare corpus, wikipedia data, and linux kernel code that can illustrate a lot of really interesting properties of RNNs

He also mentions a number of Deep Learning frameworks to look at for getting into deep learning, the top three are tensorflow, caffe and Keras.

As I was writing this I saw this: "Google Tensorflow chooses Keras". This makes Keras the first high-level library added to core TensorFlow at Google, which will effectively make it TensorFlow's default API.

One area of interest to me is how to build better software. In traditional software development tests area used to help verify a system. In these instances you can usually expect known inputs to yield known outputs. This is something that software developers strive for and is increased by things like referential transparency and immutability. However, how do you now handle systems that behave probabilisticly instead of discretely? As I was researching the topic of how do you successfully test and deploy ML systems, I found these two resources: "What's your ML test score? A rubric for ML production systems" and "Rules of Machine Learning:Best Practices for ML Engineering(pdf) ". I asked John his thoughts on this and he recommended: "Machine Learning: The High-Interest Credit Card of Technical Debt" as well as "Infrastructure for Deep Learning", although he said this is more of a metaphor us normal humans that don't have Altman/Musk funded budgets. He also pointed out that building these types of systems also fall under the standard best practices approach to any software and trying to maintain high software development standards is just as helpful as in any project.

My contemplation of the future is pretty pessimistic from the societal perspective. From the AI perspective it is pretty optimistic on what can be done. New articles about AI achievements like "Deep learning algorithm does as well as dermatologists in identifying skin cancer" are constantly appearing. However, then you see things like "Medical Equipment Crashes During Heart Procedure Because of Antivirus Scan". Although this is not related to Deep Learning it does touch on a well known issue, which is our lives are effectively run by software and we still don't really know how to truly engineer it. From what I understand, we really don't know exactly how some of these deep learning algorithms work. This makes the future of our software and AI seem even more uncertain. Hopefully we will overcome that.

Lastly I wanted thank John for being very generous with his time in helping me with additional resources for this post.

Recurrent neural networks
Deep Learning in Neural Networks: An Overview, Juergen Schmidhuber
Beyond the AI Winter, Paco Nathan
DNA - Secret of Photo 51 (NOVA)
A Short History Of Deep Learning – Every Manager Should Read
A 'Brief' History of Neural Nets and Deep Learning, Part 1, Andrey Kurenkov
BINA48
Deep Learning - The Past, Present and Future of Artificial Intelligence, Lukas Masuch
Who Invented the Reverse Mode of Differentiation? (pdf), Andreas Griewank
Timeline of machine learning
Deep Learning in a Nutshell: History and Training
Deep Learning in a Nutshell: Sequence Learning
An Explanation of Xavier Initialization
Understanding the difficulty of training deep feedforward neural networks (pdf) Xavier Glorot, Yoshua Bengio
Inside OpenAI, Elon Musk's Wild Plan to Set Artificial Intelligence Free
Deep Learning Reading List
Neural Networks and the Backpropagation Algorithm by Jeremy Kun
Playing Atari with Deep Reinforcement Learning Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller
10 Breakthrough Technologies : Deep Learning
NIPS 2010 Workshop on Deep Learning and Unsupervised Feature Learning Tutorial on Deep Learning and Applications (pdf)
Adam Coates -- Demystifying Unsupervised Feature Learning
Generative Adversarial Networks(pdf)
Open AI Blog Generative Models
MIT OpenCourseWare: Probabilistic Systems Analysis and Applied Probability
Essence of linear algebra(videos)
Hello, TensorFlow! Building and training your first TensorFlow graph from the ground up. by Aaron Schumacher
TensorFlow: A System for Large-Scale Machine Learning (pdf)

noreply@blogger.com (elegantcoding) — Mon, 26 Sep 2016 14:31:00 +0000

Software projects are inherently risky. Some statistics show that roughly seventy percent to fifty percent of software projects get classified as “challenged”. Where challenged can mean cost overruns and/or delivery delays, or it can mean complete failure and the cancellation of the project. Some statistics indicate as the size of the project increases so does the probability of problems and failure. Many articles and blog posts have been written about the long history of software project failure. At the time of writing this post the most recent and very public software project debacle was the healthcare.gov project. It seems as IT becomes more pervasive and essential the problems with projects may be getting worse not better.

In spite of these numbers and all too often in my experience I have found that individuals and organizations seem to have a very optimistic outlook about their own projects especially at the beginning of the project. Perhaps it’s the classic: “that won’t happen to me” attitude. Even as projects start to run into problems I have seen people especially managers not take issues seriously or ignore them all together. In some of the analysis of healthcare.gov, this was cited as one of the problems.

Risk management and risk assessment/analysis are developed areas in project management and engineering and are often discussed in software projects. Many risks will end up falling into two categories. One category is actual risks to the end product, such as unforeseen security vulnerabilities in software systems or other engineering issues that lead to flaws or critical failures of the system or components. The other is risks in the management and execution of constructing product or system.

Risk management is one of those areas where the engineering aspects and the engineering management aspects can become tightly coupled. An example can be derived from the XKCD comic “Tasks”: https://xkcd.com/1425/. Now the point of this comic is to demonstrate the difference between an easy problem and hard one, and presumably the conversation takes place between a manager and developer. In a risk setting, perhaps solving the hard problem is the goal of the project. So a risk might be that the research team fails to solve that problem at the end of the five years, or that it takes ten. So in a sense the task is high risk but there are team related risks, maybe the budget is too low and the team is subpar due to low salaries so they can never even solve it. Another possible scenario is that the conversation never happened and the project management and team think it is solvable in six months. This second scenario is the risk I have seen though out most of my career, the project management and team are overly optimistic or really don’t have a good understanding of the complexity of the task at hand. In some cases these types of issues seem to be due in part to pluralistic ignorance. Often in cases where developers don’t want to contradict management. There’s a great dramatization of this type of behavior in the show Silicon Valley when the Hooli developers are working on the Nucleus project, where the information is conveyed up the management chain but nobody wants to tell Gavin the truth.

Sadly it seems like the risks that are identified are almost peripheral to the real risks on projects. It is usually things like the hardware delivery will be delayed which will delay setting up our dev/test/prod environments and delay the start of development. While these are legitimate risks, there is always the risk of all of the unknowns that will cause delays and cost over runs, even things like developer turnover never seem to be taken into account, at least in my experience. Also there seems to no cognizance of the long term cost risks like the project was poorly managed or rushed or was done on the cheap which caused the delivered codebase to be an unmaintainable big ball of mud that will incur a much higher long term costs.

In order for software engineering to grow up and become a real engineering discipline it will need formal risk assessment and risk management methodologies both on the project management side and on the work product side. This is also an area where ideas and methodologies can potentially be taken from existing work in other engineering disciplines. These methodologies will also most likely draw from probability and game theory.

noreply@blogger.com (elegantcoding) — Tue, 31 May 2016 20:34:00 +0000

This post is a little off topic from my normal posts. Although, since I consider my blog to be about programming, software engineering, math and computer science, perhaps taking a brief foray into the natural sciences is warranted as it is science and I am a science nerd, and of course it is my blog. The book that I am referencing for this post is: The Ants by E.O. Wilson and Bert Hölldobler. It has many great examples of data visualization. There is also a CS relevant area of study called ant hill algorithms. Additionally, I believe that the study of social biology is basically just game theory which again is a topic that comes up in CS.

The natural world is fascinating and it teams with many interesting life and death stories that play out every minute of every day in the theatre of nature. Some of the most fascinating plots include various types of symbiosis that occur between species. Symbiosis, also called mutualism, is a cooperative relationship between two species that sometimes includes an exchange of “survival favors”. A fairly famous example of this type of species interdependence is the story of why Brazil nuts produce very poorly in plantations. It turns out the Brazil nut tree Bertholletia excelsa is dependent on a pollinator insect, an orchid bee Euglossa, which is attracted by an orchid, Coryanthes Vasquezii which does not grow on the tree but is present in the undisturbed forest habitat. Finally the tough outer shell needs large rodents like the Agouti to gnaw it open, they much like squirrels consume some of the seeds and also bury some for later which allows some of the forgotten seeds to germinate. There are many examples of symbiotic relationships in rainforest and other habitats.

Ants are notorious for having symbiotic relationships with plants and other insects and many such cases are well documented. One case is the Neotropical Cecropia tree which provides hollow stems for Azteca ants to inhabit and even food in the form of gylcogen-rich Müllerian bodies. There was another story about a relatively recent discovery of a plant that grows on the harsh cliffs of Pyrenees that depends on three species of ants for pollination and seed dispersal. These types of stories are not uncommon in the natural world, however, one often reads of them playing out in the above and often exotic and/or tropical locations, so I found myself rather surprised to discover this type of drama transpiring literally inches from my living room window in suburban Arlington Virginia.

The story I am going to tell happened during the summer of 2011 and I had originally labored under the assumption that it was a somewhat unique undocumented story. However, my subsequent research has yielded a number of pictures which depict many of the events that I will describe and show here often with better photographic quality than what I what I captured. Not that my photos are bad but they lack the fidelity of others I have seen. I make up for this in quantity which captures various events over an extended period of time.

One of my hobbies is identifying eastern forest native plants and experimenting with growing them in my yard. This activity, probably to the chagrin of my mcmansioned neighbors, has turned my yard into a small native plant and wildlife habit. A few years ago I collected some seeds of a plant known as Yellow Leaf Cup, Bearpaw, or Bearsfoot, which I believe goes by the Latin name Smallanthus Uvedalia formerly known as Polymnia Uvedalia. It is in the Aster Family (Asteraceae). I planted some in pots and scattered some seeds in my yard, the potted ones germinated but did not make it however some took root right in front of my living room window. To me this plant really stands out, for a temperate zone plant it has very large leaves, 12 to 18 inches long, and as a result it almost completely obscures my living room window shrouding it in giant green veined leaves as you can see in the picture at the top of this post. The location of these leaves put me in a unexpected and unique position to watch an incredible and probably epoch old symbiotic drama of nature play out between Ants(Hymenopterans) and Hemipterans

In June 2011 as the stand of Large Flowered Leaf-Cup reached about eight or ten feet in height and completely blocked my living-room window providing a nice screen of green privacy, an odd looking insect, pictured below, showed up. As you can see it’s shaped like a thorn which has garnered its ilk the general common name of thorn bug it is also referred to as a tree hopper this class of insects that falls under the order Hemiptera, and I believe it is the species Entylia carinata. It does not have a common name. I think it needs a common name and in that picture I see a rhinoceros looking insect, thus I am coining it the rhinoceros thorn bug or just the shorter version of rhino thorn bug. If you look closely at the picture below you can see its eyes and legs which are hard to see in many of the photos, my guess is this is by design as thorns don’t have eyes and legs.

Shortly after its arrival the ants showed up to tend to it:

I contacted a biologist who specializes in ants and he identified them as a species of carpenter ants in the genus Camponotus. He told me the possible species for this area are: Pennsylvanicus, Nearcticus, and Subbarbatus.

Over the following months I watched the interesting drama play out with these two species. Owning a copy The Ants gave some perspective to the traits and behaviors of these species. Over time I captured over one thousand pictures of what played out between these two species. This collection is really a dataset of photos and it revealed some interesting observations, which while not novel, still make for an interesting story.

First let’s start with how Rhino Thorn Bug disguises itself. A number of the photos of it were taken in different lighting conditions. In the above photos the light is more direct and the yellow and green “veins” of both the plant and insect mesh and it looks like a thorn on the stem. In the following lighting the Rhino Thorn Bug appears to have purplish veins that blend with the background of plant veins.

Another outcome of the Rhino Thorn Bug living on smallanthus uvedalia is the damage to the leaves which also makes for a nice abstract photo:

I’m making a leap here, but it seems that this damage extends the camouflage range for the rhino thorn bug such that it can hang out on the leaf and look like damaged parts of the leaf that more closely match its brownish color and pseudo-veins in back lit conditions:

I also noticed that it seemed to stay in one place and was able to feed by making multiple bites into the thick main leaf vein, I suspect that the major vein might be a bundle of veins and it was tapping into individual sub-veins each time. This is visible in a subsequent photo.

Ant Symbiosis with other insects takes a number of forms. A common symbiosis is known as Trophobiosis where ants feed on what is known as honeydew. This substance is a mixture of sugars that the insect excretes from its posterior. It is often the case that the provider of this mixture breaks down more complex polysaccharides into simpler sugars that the ants can digest these include glucose, fructose, etc. The not so great image below shows this an ant feeding from the posterior of the rhino thorn bug:

This relationship is not unfamiliar to humans. It seems to mirror our use of livestock especially dairy cows, although we get the fluid we consume from a different organ. However, the behavior of protecting, caring for and in some cases herding these insects is exactly what we do with our livestock. The ants have been doing this millions of years prior to our existence as the ant Hemiptera symbiosis behavior is thought to have originated in the Eocene period. There is evidence of this, shown below, from about 15 million years ago found in Dominican Amber which shows a queen from the extinct species Acropyga glaesaria on her mating flight with a “seed” mealybug in her mandibles for use when she establishes her new colony.

Another ant behavior that I believe I caught is ants transferring food to each other, which is known as Trophallaxis. In the image below you can see the two ants at the top with their mandibles interlocked, in a previous picture one of them was feeding and now seems to be transferring food to the other.

Ants have different castes of workers. The image below shows two different castes I observed. The one at the top is a Major worker. Ants of this caste are in some cases referred to as soldiers as they in some species take on roles like acting as “doormen” at colony entrances to ensure that only ants of that colony are allowed. It easy to see that the larger body size with the large head and large mandibles makes them more formidable, although I don’t know if the solder distinction truly applies in this case. The other two are minor workers which have smaller bodies and heads.

As the story unfolded it got even more interesting. I recall, although I don’t have photos of it that the ants seems to escort the thorn bugs to meet each other for mating. The evidence of mating was soon obvious as can be seen in the photo below with the ants in attendance of the brood of recently hatched nymphs. The ants tended to the nymphs which included chasing them around as they wandered off. Some of the nymphs seemed to stray and many of them died. Also visible in this photo are the multiple bites left by what was presumably the female rhino thorn bug made over her extended time staying in one location.

Pretty soon the nymphs are providing the same trophobiosis as their parents as shown below:

As the nymphs grow up you can see that they start to take on their adult shape:

I was curious to see if the thorn bugs would return the following year. They did not. However, I was surprised to a whole new ant drama play out with new actors. I reached out to the ant biologist who helped me the previous year and he identified these as Tapinoma sessile. I was not able to identify the aphids. I was told they would be plant specific.

Their activity was concentrated around the flowers and spanned the time that they were in bloom. The “infestation” of the flower heads can be seen in the following photo:

Another difference was the ratio of ants to honeydew producers, as you can see there are many aphids to each ant which in contrast to the rhino thorn bugs which often had multiple ants in attendance of each one. The biologist that I contacted said that the ants looked fat and happy, and their abdomens or gasters in ant biology speak, seem to be bursting and almost glistening, presumably with honeydew. I once saw David Attenborough eat a honeypot ant and it got me thinking I should have tried it with these guys. Well that was until I learned that their common names include odorous house ant and stink ant.

The photo below shows how the flower’s sepal seems to serve as a protected staging area for the aphids to develop to full maturity:

All of this happened in 2012. I have not seen the aphids since. I do see the rhino thorn bugs at least one or two each year over the last few years. I have never seen the level of activity that I saw back in 2011, I am always hopeful that each new year will bring some new drama. Actually last year it was an opiliones explosion, but that’s a whole other story.

The story about the Brazil nut symbiosis is interesting and was a little bit of a setup to show my cute seed disperser below. Although the plant is obscured by another (Wingstem, Verbesina alternifolia) It is collecting Large Flower Leafcup seeds, the flower heads are visible slightly right and below it.

noreply@blogger.com (elegantcoding) — Thu, 30 Apr 2015 12:46:00 +0000

The terms software engineering, software engineer, and sometimes just engineer as in "full stack engineer" appear a lot in the software development field. Some people including myself find the use of the term "Software Engineering" to be somewhat dubious. I also feel that there are too many people calling themselves engineers who really shouldn’t be. As a result of my skepticism I have been trying to devise a way to determine exactly what is Software Engineering?

The happy path is to go to the web and search for it or just find a book. Both will lead to many answers. But that is really just getting someone else’s opinion. A little later we will look at other people’s opinions as there are very established authors who readily answer this question.

To get some perspective, let’s step back and ask a more basic question. What is engineering? For this I will rely on the ultimate oracle of our time. Some top responses from the Google are:

The Google dictionary definition:

en·gi·neer·ing
noun
the branch of science and technology concerned with the design, building, and use of engines, machines, and structures.
• the work done by, or the occupation of, an engineer.
• the action of working artfully to bring something about.
"if not for Keegan's shrewd engineering, the election would have been lost"

The Georgia Tech School of Engineering provides the following:

Engineering is the practical application of science and math to solve problems, and it is everywhere in the world around you. From the start to the end of each day, engineering technologies improve the ways that we communicate, work, travel, stay healthy, and entertain ourselves.

What is Engineering? | Types of Engineering:

Engineering is the application of science and math to solve problems. Engineers figure out how things work and find practical uses for scientific discoveries.

Wikipedia: defines it as

Engineering (from Latin ingenium, meaning "cleverness" and ingeniare, meaning "to contrive, devise") is the application of scientific, economic, social, and practical knowledge in order to invent, design, build, maintain, research, and improve structures, machines, devices, systems, materials and processes.

So to summarize and synthesize the above for a working definition, we get:

Engineering is a branch of science and technology where mathematical, scientific, economic, and social knowledge are applied artfully, creatively, and efficiently to invent, design, build, maintain, research, and improve structures, machines, devices, systems, materials and processes.

Another aspect of engineering that should be considered is its diversity. Just searching around I came up with the following list of types of engineering, which should by no means be considered complete, they include: Aeronautical, Agricultural, Audio, Biomedical, Biomechanical, Building, Ceramics, Chemical, Civil, Computer, Electrical, Electronics, Environmental, Food, Geological, Industrial, Marine, Mechanical, Military, Mineral, Military, Nuclear, Optical, Petroleum, Photonics, Systems, and Textile.

Often discussions of software engineering draw parallels to construction and civil engineering and it is easy to see why, most people often see the results of these disciplines and even live in them. Not to trivialize these disciplines, but bricks and mortar, in addition to wood, glass, and rebar are things that support our lives and are physical thus somewhat easy to conceptualize. But all engineering disciplines now touch and perhaps run our lives in ways that we rarely think about. I previously posited that chemical engineering, prior to the software era, was probably the most pervasive engineering in our lives not to mention that the computer hardware we use wouldn’t exist without it. It serves as an interesting area to look at in regards to software engineering comparisons too, as it is a relatively recent discipline and has some parallels like the control of processes and "flows" in this case of materials. Perhaps the closest "relative" to software engineering might be industrial engineering. Like software it deals with human factors. It also deals with stochastic processes, something that is becoming increasingly more important in software systems.

Now that we have some general engineering perspective, let’s revisit the question "What is software engineering" by looking at what the established organizations and authors have to say.

Wikipedia gives the following definition:

Software engineering is the study and an application of engineering to the design, development, and maintenance of software.

Typical formal definitions of software engineering are:

the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software
an engineering discipline that is concerned with all aspects of software production
the establishment and use of sound engineering principles in order to economically obtain software that is reliable and works efficiently on real machines.

K.K. Aggarwal provides us with a bit of history:

At the first conference on software engineering in 1968, Fritz Bauer defined software engineering as "The establishment and use of sound engineering principles in order to obtain economically developed software that is reliable and works efficiently on real machines".

Stephen Schach defined the same as "A discipline whose aim is the production of quality software, software that is delivered on time, within budget, and that satisfies its requirements".

The ACM weighs in with:

Software engineering (SE) is concerned with developing and maintaining software systems that behave reliably and efficiently, are affordable to develop and maintain, and satisfy all the requirements that customers have defined for them. It is important because of the impact of large, expensive software systems and the role of software in safety-critical applications. It integrates significant mathematics, computer science and practices whose origins are in engineering.

There are a number of books on software engineering which have an obligation to address the question.

The answer in Ian Sommerville’s 8th Edition of Software Engineering is:

Software engineering is an engineering discipline that is concerned with all aspects of software production from the early stages of system specification to maintaining the system after it has gone into use. In this definition, there are two key phrases:
1. Engineering discipline Engineers make things work. They apply theories, methods and tools where these are appropriate,. but they use them selectively and always try to discover solutions to problems even when there are no applicable theories and methods. Engineers also recognise that they must work to organisational and financial constraints, so they look for solutions within these constraints.
2. All aspects of software production Software engineering is not just concerned with the technical processes of software development but also with activities such as software project management and with the development of tools, methods and theories to support software production.

What Every Engineer Should Know about Software Engineering by Philip A. Laplante offers the following:

Software engineering is "a systematic approach to the analysis, design, assessment, implementation, test, maintenance, and reengineering of software, that is, the application of engineering to software. In the software engineering approach, several models for the software life cycle are defined, and many methodologies for the definition and assessment of the different phases of a life-cycle model" [Laplante 2001]
In Software Engineering A Practitioner's Approach 8th Edition Roger S. Pressman and Bruce R. Maxim provide a terse explanation:
Software Engineering encompasses a process, a collection of methods [practice] and an array of tools that allow professionals to build high-quality computer software.

Roger Y. Lee describes it in Software Engineering:A Hands-On Approach as:

Software engineering is the process of designing, developing and delivering software systems that meet a client’s requirements in an efficient and cost effective manner. To achieve this end, software engineers focus not only on the writing of a program, but on every aspect of the process, from clear initial communication with the client, through effective project management, to economical post-delivery maintenance practices. The IEEE Standard glossary of software engineering terminology defines software engineering as the application of a systematic, disciplined, quantifiable approach to the development, operation and maintenance of software (Ghezzi et al. 1991). As made clear by the above definition, software engineering came about in order to reverse early development practices by establishing a standard development method that could unify and normalize development operations, regardless of the people involved or the goals sought.

The laborious effort of wading through all of this erudition gives me the following distillation:

Software Engineering is:

An engineering discipline
Application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software"
Software engineering (SE) is concerned with developing and maintaining software
Software engineering is the process of designing, developing and delivering software systems
A standard development method that can unify and normalize development operations, regardless of the people involved or the goals sought.

Software Engineering Includes:

All aspects of software production from the early stages of system specification to maintaining
The system after it has gone into use
Non technical activities such as software project management and with the development of tools, methods and theories to support software production.
The integration of significant mathematics, computer science and practices whose origins are in engineering.
The application of theories, methods and tools where these are appropriate
Many methodologies for the definition and assessment of the different phases of a life-cycle model
Several models for the software life cycle
A process, a collection of methods [practice] and an array of tools that allow professionals to build high-quality computer software.
The application of sound engineering principles to the analysis, design, implementation (development), assessment, test, maintenance and reengineering of software that is reliable and works efficiently on real machines

Software Engineering Produces:

Quality software
Software that is delivered on time
Cost effective production of software (within budget)
Software that satisfies its requirements.
Software systems that behave reliably and efficiently
Software that is affordable to develop and maintain
Solutions that conform to organizational and financial constraints

I tried to break the multitude of ideas into three categories, but they are admittedly a bit fuzzy and you could probably move some of these around. The point of the categorization exercise is to attempt to separate a definition from the broader idea of what the discipline encompasses and the attributes of the structures and systems that it produces, again things can get fuzzy here. In thinking about these and my own experience with software development I came up with a list of things that I feel should be defined to make software engineering a real discipline and they are:

What is the definition of the engineering discipline we are describing?
What are the produced artifacts, e.g. structures and processes that the discipline creates?
What non-managerial processes and methodologies are used to create the produced artifacts?
What types of documentation (descriptive artifacts) are used to describe the produced artifacts and the processes to create those produced artifacts?
How does the underlying math and science support the engineering discipline and how do these foundational disciplines allow one to reason about the produced artifacts that the engineering discipline is trying to construct? How do these disciplines define and drive the descriptive artifacts?
How does one organize and manage the effort including various roles people will play to actually carry out the work to bring the system or structure to fruition?

So coming back to the original purpose of this post, my answer to the question of what is software engineering, number one above, is:

Software engineering is the branch of science and technology where mathematical, computer science, linguistic, social knowledge and system relevant domain specific knowledge are applied artfully, creatively, and efficiently to invent, design, build, maintain, research, and improve software systems.

That’s the easy part. The hard part is what are the answers to the other five questions? I know that there a number of industry standard answers for these that include things like UML, Agile, Scrum, etc., but are those really valid and are they really working? I don’t think so, so maybe it’s time to look for other answers.

noreply@blogger.com (elegantcoding) — Mon, 23 Mar 2015 11:45:00 +0000

Software correctness which is really software quality is not one thing. It is comprised of a number of different and sometimes conflicting attributes. As always Gerald J. Sussman provides interesting insights and in this case it is in his "We really don’t know how to compute" talk. He makes the point that "correctness" may not be the most important attribute of software, the example he give is if Google’s page craps out on you, you will probably try again and it will probably work. Actually this example might be more about reliability but it got me thinking as I have always thought that "software correctness" meant the combination of both accuracy and reliability and that was this the "correctness" that I always thought was the most important feature of software. But this correctness is really two software quality attributes and the Google search software exemplifies these two aspects of "software correctness", one is availability and the other is search accuracy or the fulfillment of the users expectations. One could argue that availability is not a software attribute but it is affected by the quality of the software and it is an attribute of a software system even if some of that might be driven by hardware. So these two attributes for Google search do not have to be perfect. The search quality needs to be at least better than the competition and the availability has to be high enough so that people won’t be discouraged from using it and for these two attributes they are both very high. These parameters of quality vary in other domains, a machine administering a dose of radiation to a cancer patient would need to have stringent requirements as to the correctness of the dose, and in fact there have been deaths due to exactly this type of problem. Another is software guiding a spacecraft or a Mars rover which needs to be extremely reliable and correct and when it hasn’t been, well there are a few space bricks floating around the solar system due to software errors. In the real world, especially now, software is everywhere and it now lives in a variety of contexts. So which quality attributes are important will vary based on its domain and its context.

So what makes software good? Google first conquered search with Map-Reduce and other processes running on custom commodity hardware that allowed for flexible fault tolerant distributed massive data crunching. Amazon has commoditized its server infrastructure to sell spare capacity that can be easily used by anyone. Apple created easy to use attractive interfaces for the iPhone and iPad that consumers loved with similar usability now being offered on Android. NASA has successfully landed on the frigid world of Titan, touched the edge of the heliosphere, and has run rovers on Mars. While there are obviously hardware components to these systems, it was the various types of software quality that played a pivotal role in these and the many other great software successes.

It is easy to look back at these successes. With the exception of NASA, I doubt there was a deliberate effort on which quality aspects to focus on. Most were probably chosen intuitively based on business needs. Software quality is essential to any organization that creates software. It is an established subdomain or perhaps a related separate sibling field of software development. It has consortiums, professional organizations and many books written on the subject. So I delved into some of these and you find mention of Agile and TDD. You also start to see things like CMMI, ISO 9000, Six Sigma. Some of the resources seem to be written in some alien language, perhaps called ISO900ese, that seems related to software development but leaves me feeling very disconnected from it. I think that the problem might be that these attempts to formalize software quality as a discipline are suffering from the same problem that plagues the attempt to formalize software engineering as a discipline. It conflates the development process with the final product and the software quality formalization might be further exacerbated by the influence of the domain of manufacturing and its jargon. I think these established methodologies have value, for example makes sense, but it seems like in general with these standards there is a lot to weed through and the good parts seem to be hard to pick out. So I thought it might be fruitful to look at the problem from another angle that might provide a better way to reason about the quality of a system not only after and during its development but also before development begins.

A list of "quality parameters" for software is a requirement for software engineering to be a real engineering discipline. These parameters could then be viewed qualitatively and quantitatively and perhaps even be measured. In engineering disciplines various parameters are tradeoffs, you can make something sturdier but you will probably raise the cost and or the weight, for example plastic bumpers on cars, metal would be more durable but would be heavier and more costly. If one were to think of some parameters in software as tradeoffs you can see that improvements on some parameters may cause others to go down. In my post "The Software Reuse Complexity Curve" I posit that reuse and complexity are interrelated and that the level of reuse can affect understandability and maintainability. Another example is performance, increasing performance of certain modules or functions might lead to an increase in complexity which without proper documentation could lead to harder understandability which might cause a higher long term maintenance cost.

So to come back to the question and to rephrase it: What are the attributes that constitute software quality? I am not the only person to ask this question as I have seen other blog posts that address this. There are quite a few people who have asked this question and have compiled good lists. One post by Peteris Krumins lists out some code quality attributes that Charles E. Leiserson, in his first lecture of MIT's Introduction to Algorithms, mentions as being more important than performance. Additionally Bryan Soliman’s post "Software Engineering Quality Aspects" provides a nice list with a number of references. I thought I’d create my own list derived from those sources and my own experience. I am categorizing mine in three groups, Requirements based (including nonfunctional requirements), structural, and items that fall into both categories.

Performance
Correctness (Requirements Conformance)
User Expectations
Functionality
Security
Reliability
Scalability
Availability
Financial Cost
Auditability

Modularity
Component Replaceability
Recoverability
Good Descriptive Consistent Naming
Maintainability/ Changeability
Programmer's time
Extensibility/Modifiability
Reusability
Testability
Industry standard best practices (idiomatic code)
Effective library use, leveraging open source (minimal reinvention)
Proper Abstractions and Clear code flow
Good and easy to follow architecture/ Conceptual Integrity
Has no security vulnerabilities
Short low complexity routines

Robustness/Recoverability
Usability
Adaptability
Efficiency
Interoperability/Integrate-ability
Standards
Durability
Complexity
Installability

This is by no means intended as a definitive list. The idea here is to put forth the idea of enumerating and classifying these attributes as a way to reason about, plan and remediate the quality of software projects, basically create a methodical way to address software quality throughout the software development lifecycle. In the case of planning software quality attributes can be potentially rated with respect to priority. This could also allow conflicting attributes to be more effectively evaluated.

The attribute of availability is one that is fairly easy to quantify and often gets addressed usually in some type of Service Level Aggreement (SLA). Although availability cannot be predicted, the underlying system that "provides" it can be tested. Netflix has developed chaos monkey to in part to verify (test) this quality attribute of their production system. Tests and QA testers are a way to verify the requirements correctness and the correctness of system level components and services contracts of software. Static analysis tools like PMD, Checkstyle, and Sonarqube can help with code complexity, code conventions and even naming.

Complexity is an elusive idea in this context it also crosses many of the above ideas. Code can be overly complex, as can UIs, Usability (think command line), Installability, etc. Another cross concept is understandability which can affect code, UIs, etc. which is in part related to complexity but can manifest itself in the use of bad or unconventional nomenclature as well. There may be other cross concerns and it seems that the spectrum of quality attributes might better reasoned about by separating out these concepts and developing general ways to reason about them.

I should note that I include financial cost as one of the attributes. While it might not be a real quality attribute, higher quality may necessitate higher cost, but not necessarily. If one were to develop two systems that had the same level of quality across all of the chosen attributes, but one system had twice the cost, the cheaper one would be a better value, hence more desirable. So cost is not a quality attribute per se, but it is always an important factor in software development.

In summary my vision is a comprehensive methodology where the quality attributes of a software system are defined and prioritized and hopefully measured. They are planned for and tracked throughout the life cycle and perhaps adjusted as new needs arise or are discovered. The existing tools would be used in a deliberate manner and perhaps as thinking about the quality attributes becomes more formalized new tools will be developed to cover areas that are not currently covered. It will no longer be about code coverage but quality coverage.

Anthony Ferrara, Beyond Clean Code, http://blog.ircmaxell.com/2013/11/beyond-clean-code.html

David Chappell, The Three Aspects of Software Quality: Functional, Structural, and Process, http://www.davidchappell.com/writing/white_papers/The_Three_Aspects_of_Software_Quality_v1.0-Chappell.pdf

Rikard Edgren, Henrik Emilsson and Martin Jansson , Software Quality Characteristics,

http://thetesteye.com/posters/TheTestEye_SoftwareQualityCharacteristics.pdf

Bryan Soliman, Software Engineering QualityAspects, http://bryansoliman.wordpress.com/2011/04/14/40/

Ben Moseley and Peter Marks , Out of the Tar Pit, http://shaffner.us/cs/papers/tarpit.pdf

Brian Foote and Joseph Yoder, Big Ball of Mud, http://laputan.org/mud/

Wikipedia , Software quality, http://en.wikipedia.org/wiki/Software_quality

Franco Martinig, Software Quality Attributes, http://blog.martinig.ch/quotes/software-quality-attributes/

MSDN, Chapter 16: Quality Attributes, http://msdn.microsoft.com/en-us/library/ee658094.aspx

Advoss, Software Quality Attributes, http://www.advoss.com/software-quality-attributes.html

Eric Jacobson, CRUSSPIC STMPL Reborn, http://www.testthisblog.com/2011/08/crusspic-stmpl-reborn.html

noreply@blogger.com (elegantcoding) — Thu, 14 Aug 2014 11:01:00 +0000

I recently attended an event here in DC where Woz was the guest of honor. I was unaware of his book at the time. So leading up to it, I thought it would be fun to re-watch a couple of old documentaries in which he appears. I forewent his foray into reality TV. I chose to watch "The Machine that Changed the World" (youtube) a PBS documentary from 1992 which is farsighted enough to not feel completely dated plus the chronicling of the early history of computing is nicely done. The other was Robert X Cringley’s 1996 "Triumph of the Nerds" (youtube) which is a fun account of the rise of the personal computer.

ENAIC took up 1800 square feet

Watching these rekindled an idea I had to do a history of events from ancient to modern that got us to where we are now. So I set forth to collect and list notable events that propelled both the science and industry of computing to its present state. My goal was to include the people and events that not only shaped the technology but that also shaped the industry and the language we use to describe things. One example is the term bug that many people may take for granted. It is derived from a problem caused by an actual insect, a moth stuck in a relay. The other and perhaps more profound case is that the word "computer", a name we also take for granted, was a historical accident. Prior to 1940 a computer was a person who did computations or calculations. Many of the first machines with the exception of the decryption work done Bletchley Park were developed for doing computations, specifically ENIAC, which was initially designed to calculate artillery firing tables. ENIAC became the first well known computer and captured the public’s imagination when the "Giant Brain" was displayed to the American press in 1946. Not long after that the word computer went from describing a person to a machine. Meanwhile the Colossus machine from Bletchley Park, the project Alan Turing worked on, remained a secret until the 1970’s. Had that work been made public immediately following the war we might be calling these machines decoders or decrypters and the history of the computer might have taken some different turns, who knows maybe even Silicon on Avon, okay that’s probably a stretch.

As I was chronicling these events of which I tried to include when certain ideas and inventions occurred I noticed some interesting trends. For example some ideas like the algorithm and robotics (or mechanical automata) are quite ancient going back over a thousand years. Many of the technologies we use today date back mostly about 30 to 50 years ago and some are even older. Magnetic storage was patented in 1878, making it 19^th century technology, and if you think about it, it is really is fairly primitive, I‘ve heard hard disks described as "spinning rust". Admittedly today’s hard disks contain very sophisticated electronics and electromechanics but are still technologically primitive (effectively sophisticated 19^th century technology) compared to SSD technology, which is 20^th century technology with DRAM from 1966 and NAND Flash being invented in 1980. The real advances, not surprisingly, are the advances in materials science, fabrication and manufacturing that take 1970’s technological developments like the active matrix display technology and make them small, cheap and ubiquitous today.

There are many interesting people who played very important and pivotal roles who seem to be largely forgotten. One of my biggest pet peeves is the cult of personality effect that seems to show up in our industry and the worst case of it is probably Steve Jobs. I remember working with one young fanboy who was telling me how great Steve Jobs was and that Steve Jobs thought of the iPad in the 1970s, to which I replied that it was depicted in a movie called 2001 from the late 1960s, which I would wager that Jobs had seen. I include that movie in my list of events because it does depict advanced computer technology. While Steve Jobs seems to garner more attention than he deserves, and I do credit Apple with certain events that shaped the industry as it is today. I think there are several more interesting people who have made much more substantial contributions. One person is Robert Noyce who cofounded Intel and invented the practical version of the integrated circuit that we use today, he was kind of a Jobs and Wozniak combo in terms of technical brilliance and business acumen. Another interesting story surrounds ARPANET, the proto-internet. While Al Gore may have tried to take credit for its invention, J. C. R. Licklider might have actually been the one who did effectively invent it. He convinced Bob Taylor of the idea that became ARPANET. Taylor is another of those people who deserves recognition as after he created the initial proposal for ARPANET he went on to lead Xerox Parc for about 15 years from its inception. Also Xerox Parc often seems to get the credit for our much of our modern computing interfaces, but again Douglas Engelbart really deserves that credit as he demonstrated most of those ideas in 1968 two years before Xerox established Parc. He of course was a big influence of that work at Parc.

A big driving force for the creation of practical computer technology was the need for machines to do tedious laborious mental work like large quantities of calculations especially to create mathematical tables that gave values of various computations such as logarithms which were used extensively prior to the 1970s before the advent of affordable desktop and pocket scientific calculators. Babbage’s work was aimed at solving this problem. During world war two the need for the creation of artillery tables exceeded the available human labor which drove the military to fund the creation of ENIAC, which was not delivered until after the war. The war also drove the Bletchley park work, again an attempt to automate tedious work of trying to manually decipher the coded messages of the Enigma Machine.

Big data circa 1950s. ~ 4GB of punched cards.

Big data is a common term today, but in many respects it has history going back over a hundred years and could be also considered a driver of the development of practical computer technology. One continual source of big data was and probably still is, is collection of census data. In 1889 Herman Hollerith developed an electromechanical tabulating machine that was used to process data for the 1890 US census. His 1889 patent had the title "Art of Compiling Statistics" and he later established a company to sell the machines which were used worldwide for census and other applications. He is credited with laying the foundations of the modern information processing industry. His company was eventually merged with four others to become IBM. In 1948 the US Census Bureau had a big data problem that was outgrowing the existing electromechanical technology. John Mauchly one of the inventors of ENIAC and cofounder of Eckert–Mauchly Computer Corporation sold the census department on its successor named UNIVAC to handle census data. The company survives today as Unisys.

Grace Murray Hopper at the UNIVAC keyboard

A huge problem with software projects today is that of project failure and the history of computing seems to have its share as well. Software projects sometimes outright fail and all too often are late and over budget. Babbage’s Difference Engine project which was cancelled after 15 years and an expenditure that was ten times the original amount paid. The failure was due to bad management on his part and what might be called scope creep in that he got distracted by designing the more general Analytical Engine. UNIVAC is another notable early project that was delivered late and over budget.

The real challenge of a post like this is what to include. The Machine that Changed the World documentary starts with writing which was our first precise technique to record information. I went back farther to include the recording of numerical information. A big influence on the way I view history comes from a PBS show that aired in the eighties called Connections which was done by James Burke. In it he traces in a very engaging way various technological developments as cause and effect events. In a sense he demonstrated that history was an interesting living topic not the banal languid mimeographs that I experienced in school. I tried to choose events that were either the inception of something or the point at which it caused a significant change. In the spirit of Connections there are definite threads here, the thread of calculation and computation including number representation for those purposes. The thread of encryption also plays an important role as does dealing with information both in terms of storage, replication and processing. Some of the threads are obvious and some are more subtle.

Pre 3000 BCE: Tally Marks, a unary numeral system, are used to keep track of numerical quantities such as animal herd sizes.

c. 3200 BCE: Mesopotamian Cuneiform appears. Writing may have been independently developed in other places as well. Although protowriting systems previously existed, society now had a more concise mechanism to record information.

c. 3000 BCE: The development of the Egyptian Hieroglyphic Number System and the Sumerian and Babylonian Number System base 60 number system is the start of non-unary number systems.

2800 BCE: The appearance of the I Ching which included the Bagua or eight trigrams is possibly the first occurrence of binary numbers.

2700–2300 BCE: The Sumerian Sexagesimal Abacus allows human mechanical calculations.

c. 500 BCE: Pāṇini describes the grammar and morphology of Sanskrit.

c. 300 BCE: Euclid's Elements describes among other things an algorithm to compute the greatest common divisor.

100 BCE: The Greeks develop the Antikythera mechanism, the first known mechanical computation device.

c. 5 BCE: The scytale transposition cipher was used by the Spartan military, although ciphers probably existed earlier.

c. 1 - 300 CE: Hindu numeral system, later to become the Hindu–Arabic numeral system, is invented by Indian mathematicians.

c. 201 - 299 CE: Diophantus authored a series of books called Arithmetica which deal with solving algebraic equations.

c. 801 - 873 CE: Al-Kindi develops cryptanalysis by frequency analysis.

c. 825: CE Muḥammad ibn Mūsā al-Khwārizmī writes On the Calculation with Hindu Numerals which helps spread the Indian system of numeration throughout the Middle East and Europe. It is translated into Latin as Algoritmi de numero Indorum. Al-Khwārizmī, rendered as (Latin) Algoritmi, leads to the term "algorithm".

850 CE: The Banu Musa publish The Book of Ingenious Devices a large illustrated work on mechanical devices, including automata.

1202: Leonardo of Pisa (Fibonacci) introduces the Hindu–Arabic numbers to Europe in his book Liber Abaci.

c. 1283: Verge escapement is developed in Europe and allows the development all-mechanical clocks and other mechanical automata.

1450: Johannes Gutenberg invents the Printing Press, while actually invented earlier in Asia, it allows the mechanization of the duplication of information and creates an industrial boom surrounding the selling and dissemination of information.

c. 1624: The slide rule is developed to calculate logarithms.

1642: Blaise Pascal and Wilhelm Schickard invent a mechanical calculator known as Pascal's calculator. It is later discovered that Schickard had described the device to Johannes Kepler in 1623.

1654: Pierre de Fermat’s and Blaise Pascal’s correspondence leads to mathematical methods of probability.

1679: Gottfried Leibniz invents the modern binary number system.

1694: Gottfried Wilhelm Leibniz completes the Stepped Reckoner a digital mechanical calculator that can perform all four arithmetic operations: addition, subtraction, multiplication and division.

1725: Basile Bouchon first uses punched cards.

1736: Leonhard Euler lays the foundation of graph theory and topology in the Seven Bridges of Königsberg problem.

1763: Two years after Thomas Bayes dies his "An Essay towards solving a Problem in the Doctrine of Chances" is published in the Philosophical Transactions of the Royal Society of London.

1786: J. H. Müller Hessian army engineer publishes a description of a Difference Engine.

1801: Joseph Marie Jacquard demonstrates a working mechanical loom, the Jacquard Loom, that uses punch cards based on previous work by Jacques Vaucanson and Basile Bouchon.

1805/1809: The least squares method is published by Legendre in 1805 and by Gauss in 1809.
They both apply it to the problem of determining, from astronomical observations, the orbits of bodies about the sun. This is the earliest form of the linear regression.

1823: The British government gives Charles Babbage £1700 to start work on the Difference engine proposed the previous year. In 1842 after a total expenditure of £17,000 without a deliverable the project was canceled.

1832: Évariste Galois is killed in a duel leaving behind a legacy in algebraic theory to be discovered decades later.

1837: Charles Babbage describes a successor to the Difference Engine, the Analytical Engine, a proposed mechanical general-purpose computer and the first design for a general-purpose computer that could be described in modern terms as Turing-complete. Babbage receive assistance on this project from Ada Byron, Countess of Lovelace. It also serves to distract Babbage from completing the Difference Engine. Neither project is ever completed.

1844: Samuel Morse demonstrates the telegraph to Congress by transmitting the famous message "What hath God wrought" in Morse code over a wire from Washington to Baltimore.

1854 English mathematician George Boole publishes An Investigation of the Laws of Thought.

1878: Oberlin Smith patents magnetic storage in the form of wire recording.

1889: Herman Hollerith develops an electromechanical tabulating machine using punched cards for the United States 1890 census.

1889: Giuseppe Peano presents his "The principles of arithmetic", based on the work of Dedekind and origination of "primitive recursion" begins formally with the axioms of Peano.

1897: Karl Ferdinand Braun builds the first cathode-ray tube (CRT) and cathode ray tube oscilloscope.

1900: German mathematician David Hilbert publishes a list of 23 unsolved problems.

1906: Andrey Markov publishes his first paper on Markov Chains

1907: The thermionic triode, a vacuum tube, propels the electronics age forward, enabling amplified radio technology and long-distance telephony.

1910: Alfred North Whitehead and Bertrand Russell publish Principia Mathematica which introduces the idea of types.

1914: Spanish engineer Leonardo Torres y Quevedo designs an electro-mechanical version of the Analytical Engine of Charles Babbage which includes floating-point arithmetic.

1918: German engineer Arthur Scherbius applied for a patent for a cipher machine using rotors which gives rise to the enigma machine, a family of related electro-mechanical rotor cipher machines used for enciphering and deciphering secret messages.

1928: David Hilbert formulates the Entscheidungsproblem, German for 'decision problem', from his 2nd and 10th problems.

1925 Andrey Kolmogorov publishes "On the principle of the excluded middle". He supports most of Brouwer's results but disputes a few and proves that under a certain interpretation, all statements of classical formal logic can be formulated as those of intuitionistic logic.

1931: Kurt Gödel publishes "On Formally Undecidable Propositions of "Principia Mathematica" and Related Systems".

1933: Andrey Kolmogorov publishes Foundations of the Theory of Probability, laying the modern axiomatic foundations of probability theory.

1936: Alonzo Church and Alan Turing publish independent papers showing that a general solution to the Entscheidungsproblem is impossible. Church’s paper introduces the Lambda Calculus and Turing’s paper introduces ideas that become known Turing Machines.

1938 Konrad Zuse builds the Z1, a binary electrically driven mechanical calculator. It is the first freely programmable computer which uses Boolean logic and binary floating point numbers.

1943 Warren McCulloch and Walter Pitts publish A Logical Calculus Immanent in Nervous Activity (pdf) making significant contributions to the study of neural network theory, theory of automata, and the theory of computation and cybernetics.

1944: The first Colossus computer, designed by British engineer Tommy Flowers, is operational at Bletchley Park. It was designed to break the complex Lorenz ciphers used by the Nazis during WWII and reduced the time to break Lorenz messages from weeks to hours.

1945: Samuel Eilenberg and Saunders Mac Lane introduce categories, functors, and natural transformations as part of their work in algebraic topology.

1945: John von Neumann publishes the "First Draft of a Report on the EDVAC" the first published description of the logical design of a computer using the stored-program concept which came to be known as the von Neumann architecture.

1945: Grace Hopper records the first actual computer "bug" - a moth stuck between relays.

1946: J. Presper Eckert and John Mauchly found Mauchly Computer Corporation, the first commercial computer company.

1947: John Bardeen, Walter Brattain, and William Shockley invent the first point-contact transistor. John R. Pierce, supervisor of the team, coins the term transistor a portmanteau of the term "transfer resistor".

1947: Freddie Williams and Tom Kilburn develop the Williams–Kilburn tube the first random access memory, a cathode ray tube used as a computer memory to electronically store binary data.

1948: Claude Shannon publishes "A Mathematical Theory of Communication" as a two part series in the Bell System Technical Journal describing information entropy as a measure for the uncertainty in a message which essentially invents the field of information theory.

1948: Bernard M. Oliver, Claude Shannon and John R. Pierce publish "The Philosophy of PCM" after the application for the patents by Oliver and Shannon in 1946 and by John R. Pierce in 1945, both patent applications were of the same name: "Communication System Employing Pulse Code Modulation". All three are credited as the inventors of PCM.

1948: The world's first stored-program computer, Manchester Small-Scale Experimental Machine (SSEM), nicknamed Baby, runs its first program.

1951: David A. Huffman devises Huffman encoding for an assigned term paper for the problem of finding the most efficient binary code by his MIT information theory class professor Robert Fano.

1952: Tom Watson, Jr. becomes president of IBM and shifts the company’s direction away from electromechanical punched card systems towards electronic computers.

1953: Jay Forrester installed magnetic core memory on the Whirlwind computer.

1956: Stephen Cole Kleene describes regular languages using his mathematical notation called regular sets thereby inventing regular expressions.

1956: Wen Tsing Chow invents Programmable Read Only Memory (PROM) at American Bosch Arma Corporation at the request of the United States Air Force to come up with a more flexible and secure way of storing the targeting constants in the Atlas E/F ICBM's airborne digital computer.

1956: IBM introduces the IBM 305 RAMAC the first commercial computer using a moving-head hard disk drive (magnetic disk storage) for secondary storage.

1956: William Shockley moves back to California to be close to his aging mother in Palo Alto and starts Shockley Semiconductor Laboratory in a small commercial lot in nearby Mountain View which sets the agrarian area with cheap land and populated with fruit orchards on a path to later become known as Silicon Valley.

1957: Robert Noyce, Gordon Moore and six others known as the "traitorous eight" leave Shockley Semiconductor Laboratory to start Fairchild Semiconductor.

1957: Noam Chomsky publishes Syntactic Structures which includes ideas of the phrase structure grammar and a finite state grammar, communication theoretic model based on a conception of language as a Markov process.

1957: John Backus creates the first FORTRAN compiler at IBM.

1958: John McCarthy develops Lisp which is based on Alonzo Church’s Lambda calculus. It also includes the new idea of a conditional if statement.

1958: Jack Kilby develops the integrated circuit made from germanium and gold wires at Texas Instruments.

1959: Jean Hoerni develops the planar transistor and the planar manufacturing process at Fairchild Semiconductor.

1959: Robert Noyce develops a more practical silicon version of the integrated circuit which has the "wires" between components built directly into the substrate.

1959: Noam Chomsky publishes "On Certain Formal Properties of Grammars" which describes the Chomsky Hierarchy which includes its relation to automata theory.

1959: John Backus publishes "The Syntax and Semantics of the Proposed International Algebraic Language of Zürich ACM-GAMM Conference". In the UNESCO Proceedings of the International Conference on Information Processing, which introduces a notation to describe the syntax of programming languages specifically context-free grammars, the notation later becomes known as the Backus Naur Form (BNF).

1959: Arthur Samuel defines machine learning as a "Field of study that gives computers the ability to learn without being explicitly programmed".

1962: The Radio Sector of the EIA introduces RS-232.

1963: American Standards Association publishes the first edition of ASCII - American Standard Code for Information Interchange.

1964: The CDC 6600 is released. Designed by Seymour Cray, it is dubbed a supercomputer.

1964: MIT, General Electric and Bell Labs form a consortium to develop of the Multics Operating System.

1964: John G. Kemeny and Thomas E. Kurtz create the BASIC language to enable students in fields other than science and mathematics to use computers.

1965: Gordon Moore describes a trend in the paper "Cramming more components onto integrated circuits" which becomes known as Moore’s Law.

1966: Robert Dennard invents DRAM at the IBM Thomas J. Watson Research Center.

1968: Douglas Engelbart gives "The Mother of All Demos", a demonstration that introduces a complete computer hardware/software system called the oN-Line System (NLS). It demonstrates many fundamental elements of modern personal computing: multiple windows, hypertext, graphics, efficient navigation and command input, video conferencing, the computer mouse, word processing, dynamic file linking, revision control, and a collaborative real-time editor (collaborative work).

1968: Edsger Dijkstra´s publishes "GO TO considered harmful" letter, in Communications of the ACM helping pave the way for structured programming.

1968: The Apollo Guidance Computer makes its debut orbiting the Earth on Apollo 7. The Cold War and the Apollo program drive the demand for lighter more reliable computers using integrated circuits.

1968: ARPA approves Bob Taylor’s plan for a computer network. Bob Taylor along with Ivan Sutherland were originally convinced of the idea by J. C. R. Licklider who initially referred to the concept as an "Intergalactic Computer Network". Ivan Sutherland and Bob Taylor envisioned a computer communications network, that would in part, allow researchers to use computers provided to various corporate and academic sites by ARPA to make new software and other computer science results quickly and widely available. The project became known as Arpanet.

1968: Arthur C. Clarke and Stanley Kubrick release 2001: A Space Odyssey a science fiction movie that features advanced computing technology including an AI computer named the HAL 9000 with a voice interface that manages ship operations. The astronauts use multimedia tablet technology (NewsPad) to catch up on family and worldwide events from Earth.

1968: Gordon E. Moore and Robert Noyce found Intel.

1969: Willard Boyle and George E. Smith invent the charge-coupled device (CCD) at AT&T Bell Labs.

1969: Ken Thompson creates his game Space Travel on the Multics Operating System.

1969: Bell Labs pulls out of Multics consortium.

1970: Ken Thompson and Denis Ritche create a new lighter weight "programmers workbench" operating system with many of the robust features of Multics. The new operating system runs its first application: Space Travel. Denis Ritche coins the name Unics playing on the Multics name, later it becomes known as Unix.

1970: Edgar F. Codd publishes "A Relational Model of Data for Large Shared Data Banks" which establishes a relational model for databases.

1970: Xerox opens Palo Alto Research Center (PARC) which attracts some of the United States’ top computer scientists. Under Bob Taylor’s guidance as associate manager it produces many groundbreaking inventions that later transform computing, including Laser printers, Computer-generated bitmap graphics, The WYSIWYG text editor, Interpress, a resolution-independent graphical page-description language and the precursor to PostScript, Model–view–controller software architecture.

1971: IBM introduces the first commercially available 8 inch floppy diskette.

1971: Intel introduces the first commercially available microprocessor the 4-bit 4004.

1971: Raymond Tomlinson implements the first email system able to send mail between users on different hosts connected to the ARPAnet. To achieve this, he uses the @ sign to separate the user from their machine, which has been used in email addresses ever since.

1972: Peter Brody's team at Westinghouse produces the first active-matrix liquid-crystal display panel.

1972: Hewlett-Packard introduces the HP-35 the world's first scientific pocket calculator.

1973: Eckert and Mauchly Eniac patent is invalidated.

1973: Robert Metcalfe devises the Ethernet method of network connection at the Xerox Parc.

1973: Gary Kildall develops CP/M which stands for "Control Program/Monitor".

1974: Vint Cerf and Bob Kahn publish a paper titled "A Protocol for Packet Network Intercommunication" describing an internetworking protocol for sharing resources using packet-switching among the nodes which was henceforth called the Internet Protocol Suite, and informally known as TCP/IP.

1975: The January edition of Popular Electronics featured the MITS Altair 8800 computer kit, based on Intel´s 8080 microprocessor, on its cover.

1975: Bill Gates and Paul Allen found Microsoft to develop and sell BASIC interpreters for Altair 8800.

1975: Softlab Munich releases Maestro I the world's first integrated development environment (IDE).

1975: Frederick Brooks publishes The Mythical Man-Month: Essays on Software Engineering is a book on software engineering and project management

1976: Kenneth Appel and Wolfgang Haken prove the Four Color Theorem by computer, the first major mathematical proof to be proven by a computer.

1977: Ron Rivest, Adi Shamir, and Leonard Adleman publicly describe the RSA cryptosystem, the first practicable public-key cryptosystem.

1977: Apple introduces the Apple II, designed primarily by Steve Wozniak, it is one of the first highly successful mass-produced microcomputer products.

1977 Atari, Inc releases The Atari 2600, a microprocessor-based hardware video game console with ROM cartridges containing game code.

1978: Brian Kernighan and Dennis Ritchie publish "K&R" establishing a de facto standard for the C programming language, later in 1989 the American National Standards Institute published a standard for C (generally called "ANSI C" or "C89"). Development of C was started by Dennis Ritchie and Ken Thompson in 1969 in conjunction with the development of the UNIX operating system.

1978: University of North Carolina at Chapel Hill and Duke University publicly establish Usenet.

1979: Dan Bricklin and Bob Frankston found Software Arts, Inc., and began selling VisiCalc.

1980: Smalltalk (Smalltalk80) a Xerox Parc project led by Allan Kay since the early 1970’s is released to the public.

c. 1980: Fujio Masuoka while working for Toshiba invents both NOR and NAND types of Flash memory

1981: IBM introduces the IBM PC.

1984: Apple Computer launched the Macintosh, Based on the Motorola 68000 microprocessor, it is the first successful mouse-driven computer with a graphic user interface.

1984: Abraham Lempel, Jacob Ziv, and Terry Welch publish the Lempel–Ziv–Welch (LZW) compression algorithm.

1985: Bjarne Stroustrup publishes The C++ Programming Language.

1989: Tim Berners-Lee proposes the "WorldWideWeb" project and builds the first Web Server and Web Client using HTTP and HTML all of which lays the foundation for what becomes the World Wide Web.

1991: Linus Torvalds releases Linux to several Usenet newsgroups.

1991: Eugenio Moggi publishes "Notions of Computation and Monads" (pdf) which describes the general use of monads to structure programs.

1992: The first JPEG standard and the MPEG-1 standard are released.

1993: Marc Andreessen and Eric Bina release the Mosaic Web Browser.

1994: Jeff Bezos founds Amazon.com.

1994: Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides, known as the "gang of four" publish Design Patterns: Elements of Reusable Object-Oriented Software. Subsequently in 1999 are found guilty by The International Tribunal for the Prosecution of Crimes against Computer Science by a two thirds majority.

1995: NSFNET is decommissioned, removing the last restrictions on the use of the Internet to carry commercial traffic.

1996: Larry Page and Sergey Brin develop the PageRank algorithm and found Google two years later.

1997: Nullsoft releases Winamp.

1998: Diamond Multimedia releases The Rio PMP300, the first commercially successful portable consumer MP3 digital audio player.

1999: Napster is released as an unstructured centralized peer-to-peer system.

1999: Darcy DiNucci coins the term Web 2.0 to describe World Wide Web sites that use technology beyond the static pages of earlier Web sites including social networking sites, blogs, wikis, folksonomies, video sharing sites, hosted services, Web applications, and mashups.. The term is later popularized by Tim O'Reilly at the O'Reilly Media Web 2.0 conference in late 2004.

1999: The Wi-Fi Alliance formed as a trade association to hold the Wi-Fi trademark under which most products are sold.

2001: Jimmy Wales and Larry Sanger launch Wikipedia.

2004: Google acquires Sydney-based company Where 2 Technologies and transforms its technology into the web application Google Maps.

2006: Amazon launches Amazon Web Services.

2007: Apple releases the iPhone setting the design of the modern smart phone.

2010: Apple releases the iPad shaping tablet computer technology that started over 20 years prior to its current character.

2010: Siri is released by Siri Inc on iOS and subsequently acquired by Apple.

2012: The LHC Computing Grid becomes the world's largest computing grid, comprising over 170 computing facilities in a worldwide network across 36 countries.

2012: The Raspberry Pi Foundation ships the first batch of Raspberry Pi’s, a credit-card-sized single-board computer.

2013: The Univalent Foundations Program, Institute for Advanced Study organizes 40 authors to release The HoTT Book on Homotopy Type Theory.

If you made it this far you’ve survived my brief, relatively speaking, trip though five millennia of the human history of computing. It was hard to pick more recent things since we don’t know what the important events for the future are. I chose to end with Homototpy Type Theory since it is supposed to be the next big thing. Also you might have noticed that my title is similar, perhaps an homage, or just a rip off of: "A Brief, Incomplete, and Mostly Wrong History of Programming Languages". I had this idea prior to seeing his and for a long time it deterred me from writing this, but I finally got over the perception that he did it first since my original idea was quite different.

If you are still hungry for more including various references and influences on this post:

History of Computing

Columbia University Computing History

List of IEEE Milestones

History of Lossless Data Compression Algorithms

John von Neumann, EDVAC, and the IAS machine

Computer History Museum Timeline of Computer History

Wikipedia History of Computing

Wikipedia Timeline of Computing

PBS American Experience: Silicon Valley

PBS Nova’s Decoding Nazi Secrets

James Burke’s The Day the Universe Changed

noreply@blogger.com (elegantcoding) — Wed, 23 Jul 2014 23:32:00 +0000

A while ago I had the idea to do a graph theory talk at our local Neo4J Meetup, the Baltimore Washington Graph Database Meetup, especially since Neo4J and graph databases are based on graph theory. So I finally sat down and spent quite a bit of time putting a talk together. I decided to go with the idea of an overview of graph theory with a primary focus on the theoretical aspects and with some applications like network theory and some specific examples of applications to Neo4J. My talk is titled: "A Survey of Graph Theory and Applications in Neo4J" and I presented it on June 24, see below for video, slides, and references. This post is my thoughts on it and things leading up to its creation.

Some of my blog posts are created from a desire to make math more accessible and more relevant especially those areas of math that seem to be neglected by the traditional educational system. One huge gaping hole in my math education both in our American institutional learning facilities and in my college computer science curriculum was that I was never exposed to graph theory. Once you start studying graph theory you realize that many of these concepts could be taught in middle and elementary schools. As I was preparing my presentation, I saw this: "Math for seven-year-olds: graph coloring, chromatic numbers, and Eulerian paths and circuits", reaffirming what I already knew. Sadly many of these concepts were new to me as an adult, and I’d guess the same was probably true of much of my audience.

Graph theory has been a topic that I have included in my blog, I have written two posts about it one is a general math post: "Triangles, Triangular Numbers, and the Adjacency Matrix" and the other post: "The Object Graph" attempts to put it in part in a programming context . One post or series of posts that I have wanted to do is an introduction/overview of graph theory. I was thinking that my talk could be turned into those posts. However, I am not sure if and when I will get a chance to do that, so I figured until then I will make the talk itself that post and that post is this post.

I found myself torn about publishing the video of my presentation, on one hand I feel that it could be much better but on the other, as a friend pointed out, people might find it informative and enjoy watching it. That being said, I reserve the right to replace it with a better version if I ever do one.

Writing a post about the talk provides me with an opportunity make a few corrections, add some more source material and mention a couple of things that I would have liked to include but that got cut in the interest of time.

I’ll start by adding some additional source material. I followed the introductory remarks with a brief historical overview. For that, especially 20^th century contributors I made use these power point slides of John Crowcroft’s "Principles of Communications" course. I also referenced Graph Theory, 1736-1936 by Norman L. Biggs, E. Keith Lloyd, and Robin J. Wilson. I mentioned the Watts and Strogatz Model (pdf of original nature paper). I also included Fan Chung who is married to Ronald Graham and is known for her work in graph theory especially spectral graph theory. I mentioned snarks not to be confused with Lewis Carroll‘s snarks from which he coined the name. When I was talking about the topology part I mentioned Eulers Gem. Since the World Cup was going on during the talk I have to include these topology links "The Topology and Combinatorics of Soccer Balls(pdf)" and some more "soccer ball math".

Due to time constraints I cut a few topics, two of them were the ideas of graph isomorphisms and graph automorphisms, also ideas like: Graph families defined by their automorphisms and the automorphism group. Another area that I didn’t really get into, except the linear algebra parts was the area of algebraic graph theory.

I did want to offer up a couple of corrections: I called a truncated icosahedron a dodecahedron, how embarrassing. I called the Travelling Salesman Problem, the Travelling Salesman Program, doh! When I said a bipartite graph has no connections between edges, it should have been vertices. And finally I misstated Kirchoff’s Theorem, it should be n-1 non-zero Eigenvalues, obviously you only use the non-zero ones! There are probably more and if I decide to replace these videos in the future, I will just replace this paragraph as well.

On a lighter note, when I was creating my "Graphs are Everywhere" images and sharing with my friend Wes, I created this one for fun:

Finally I’d like to thank our meetup sponsor neotechnology refreshments. The part where we thanked them at the meetup didn’t get recorded.

noreply@blogger.com (elegantcoding) — Sat, 15 Mar 2014 15:10:00 +0000

Years ago I worked on a project that had a custom role based security system and for this system we needed a way to load menus according to the users’ assigned roles. Two of the dominant developers on the project decided that this was a perfect use for AJAX mainly because they wanted to learn and use AJAX. So they build a separate deployable menu application to serve up the menu by emitting XML from a Spring Controller URL, it was very comparable to a simple Restful service. It was called directly from JavaScript in the application’s web page. Since there would be a lot of calls for any given user’s menu they built a cache for each user’s menu options, it was a custom cache where objects never expired. This work was completed as I joined the project and as I got acquainted with this project my first thought was why do all this work? Why not just load the menu when the user is authenticated and then cache it into the HTTP Session, I raised the issue but was ignored. It was their pet project and it was sacrosanct.

Later, while testing the apps that used the AJAX menu call the testers ran into a problem, the cache was interfering with testing because it was keeping the database changes from be propagated and testing the applications created a need to continuously restart the AJAX menu app. So a new admin interface was added to the AJAX menu application to allow the testers to clear the cache. This created a whole separate application that the client would have to support just to enable this unnecessary AJAX menu delivery mechanism. So instead of just caching the data in the HTTP Session which is easier and any cache problem would be fixed by just logging out and logging back in, these two developers built a pet project which consists of an extra application and codebase that has to be understood and maintained. Ultimately the biggest problem this creates boils down to simple economics, it more expensive to maintain a solution that requires a whole separate application.

I think there is a tendency for all developers both good and bad to sometimes want to make projects more interesting and there can be a lot of temptations. It is often tempting to create a custom implementation of something that could be found already written because it’s a fun project or the temptation to shoehorn a new hot technology into a project or even the temptation to add a solution to a problem that doesn’t need to be solved or just strait up over engineering. I am guilty of some of these transgressions myself over the years.

My anecdote about the menu app is just one of at least a dozen of egregious examples of these types of software project blunders that I have seen over the years. My anecdote shows a manifestation of this problem and it also shows that these types of software project issues have a real tangible cost. They create more code and often more complex code. In some cases they create the need for specialized technical knowledge that wasn’t even necessary for the project. While these approaches may only result in a small cost increases during the construction of the software the real consequence will be the long term maintenance costs of a software system that was needlessly overcomplicated. In some cases these costs will be staffing costs but they can also be time costs in that changes and maintenance take considerably longer. These problems may also result in costs to business as unwieldy systems cause the loss of customers to competitors and can impede the ability to gain new customers.

These types of decisions can be viewed as software project blunders. In some cases the developers know better but choose to be selfish in that they put their own desires above the project, in these cases these decisions can potentially be viewed as unethical. The two developers from the anecdote were extreme examples and were pushing into unethical territory since they treated every new project as a personal opportunity to use some new technique or library or some custom idea that they were interested in. However, I think most of these blunders are simply that, mistakes in judgment or lack of good oversight. It is always easier in hindsight to see these problems, but when one is in the heat of the moment on the project one can lose perspective. The real challenge is trying to avoid these blunders. Really these are problems that fall into a larger spectrum of software project management problems and sadly I have mostly seen terrible software project management throughout my career.

I wish I could say I have a solution to this problem. I think developers have some responsibility here especially senior developers, well at least the good ones. Software development is really about decisions. Developers make many decisions every day including naming, project structure, tools, libraries, frameworks, languages, etc. Too often these decisions are made in isolation without any review and sometimes they can have serious long term consequences. When making so many decisions in such a complex domain mistakes are inevitable. Good software developers and good teams make an effort to deliberate and review their choices.

noreply@blogger.com (elegantcoding) — Wed, 11 Dec 2013 17:34:00 +0000

I am proud and excited to announce the meetup group Haskell DC. Our first meetup agenda is open so I envision some discussion and maybe some basic hacking perhaps using Real World Haskell or Learn You a Haskell for Greater Good. Both are freely available online. In this post I will put forth some ideas that we might consider for future meetups. I hope to see this grow into a community and am looking forward to contributions from members especially those that are currently working with Haskell. I hope to see a mix of practical and theoretical discussions and topics. I will also try to grow the group in terms of sponsorship. We actually have our first sponsor, the local coworking space company Uberoffices is providing us space for our meetups. I recently added our meetup to haskell.org under East Coast, which makes it seem a little more official. I have setup social media accounts on Twitter @HaskellDC also use #HaskellDC for HaskellDC tweets. I created a Google Plus account with the email haskelldc0 at gmail, haskelldc was taken. I have also created a Community in Google Plus for HaskellDC. I hope to do a Google Hangout for our meetups which was requested by one of our remote members. I even created a Facebook account if for no other reason but to claim it. I admit to not being great at the social media stuff but will do my best or perhaps I will get help there from other members.

Learning Haskell has been on my list of things that I want to do for quite a while. Haskell is attractive to me because it was developed in academia and embodies some mathematical concepts and now it seems to be gaining ground for commercial use. So it is interesting to both the computer scientist and the working programmer. I have a few ideas about future meetup topics both practical and theoretical that I wanted to list out in this post. Of course the future is wide open and I am hoping that as a group we develop future ideas with opportunities for anyone to present or lead a coding session. In researching this post I became overwhelmed by the copious amount of material that there is out there for Haskell. I plan to write at least one if not two more posts about Haskell in terms of resources, research, and the ecosystem.

The following are some lists of Programming Language Features, Software Development Related Topics, Practical applications, Advanced Programming Areas and Theoretical Topics. This list is derived from areas of my own interests along with areas that I feel are useful to practical software development. I put these forth as possible topics for consideration for future meetups:

Functional Programming, Purely Functional Programming
Immutability
Lazy Evaluation
Type System
Type inference
Pattern Matching
Algebraic Data types
List Comprehensions
Folds
Monads
Type Classes
Type Polymorphism
Kind
Memory Footprint and Garbage Collection

IDE Support
Building and Deploying, Production deployment
Continuous Integration
Package Management
Testing
Implementations, GHC, etc.

Web Development
XML, HTML Processing and parsing
Network Client/Server, Web Services, Restful, JSON, SOAP
Desktop GUI
Graphics support
Embedded programming
Relational Database Access
MongoDB
Neo4j
Hadoop/HBase
Lucene, Elastic Search, Solr
Other NoSQL: Casandra, CouchDB, Riak, etc.

Algorithms
Generic Programming
Parsers, Parser combinators, PEGs
Natural Language Processing
Graph Theory Applications, Graph Algorithms, Dijkstra's Algorithm, etc.
Algebraic programming e.g. Scala’s Spire Library
Data Munging, Data Science, Data Visualization
Statistical and Mathematical Programming

What is Generic Programming? - Library-Centric Software Design by Gabriel Dos Reis and Jaakko Jarvi
The Essence of the Iterator Pattern by Jeremy Gibbons
Origami programming by Jeremy Gibbons
Typeclassopedia Issue 13 of The Monad Reader by Brent Yorgey
Purely Functional Data Structures by Chris Okasaki

Ok, that’s quite a list. I tried to categorize these as best as I could. Monads show up under theory and language features, although I am not sure but I think they may be considered more of a language idiom. The list is clearly ambitious. If we have one meetup per month it would probably take several years to cover all of these topics if that were the plan. As some of the theoretical topics are pretty advanced, and I hope to someday understand them. Hopefully as a group maybe we make some progress as the theoretical aspects are important for better application of the practical.

I have heard many positive things said about Haskell in regards to good software development practices and that it facilitates the creation of better quality software which is what I, and most likely all good software developers, are striving for. One topic that is of great interest to me is software reuse, I have written about it in relation to complexity and generic programming. The generic programming post takes its title from a paper of the same name, listed above as a Haskell related paper. Interestingly Edward Kmett mentions in his Haskellcast about his Lens Library that using Haskell facilitates a higher ease of reuse that would require significant discipline, especially for a team, when using an OO language like C++. Another area is that of testing, while I think testing is important, my experience with TDD is limited, but it seems that TDD increases the amount of code that has to be written and understood. I have read that Haskell’s type system, like any statically typed language, allows for less testing because of static type checking. This rings true to me as dynamically typed languages like Python, Javascript, and Ruby need tests to enforce things that a type system would give you. Also, purity and referential transparency eliminate side effects. State still exists but it is managed more cleanly. Haskell’s concise syntax is another potential benefit which allows more complexity to be expressed and read more easily. Powerful features like list comprehensions, pattern matching, and abstract datatypes (ADTs) allow for smaller idiomatic code. Of course this requires programmers that understand all of this.

CS research publications are a primary area of interest for me and I have encountered many that use and mention Haskell. The list above provides some papers covering some fairly pragmatic topics that should be of interest to working programmers like Generic Programming, Design Patterns, and Data Structures. I also include Brent Yorgey’s Typeclassopedia which gets a lot of mentions from people giving advice about learning Haskell and starts with the following advice:

“The standard Haskell libraries feature a number of type classes with algebraic or category-theoretic underpinnings. Becoming a fluent Haskell hacker requires intimate familiarity with them all, yet acquiring this familiarity often involves combing through a mountain of tutorials, blog posts, mailing list archives, and IRC logs. The goal of this article is to serve as a starting point for the student of Haskell wishing to gain a firm grasp of its standard type classes. The essentials of each type class are introduced, with examples, commentary, and extensive references for further reading.

In the course of my own general research and what I did for this post, I can attest to the large amount and overwhelming Haskell related topics both theoretical and practical that are available online.

In my above list of possible theoretical interests to the meetup group, I list Homotopy Type Theory. The relevance here is of course that Type Theory is relevant to Haskell. The theory and the book are new, coming out this year. I wanted to give it special mention because there is a lot of excitement about it, including claims that the theory is potentially revolutionary to both mathematics and computer science. The book is a daunting 600 pages and very heavy going, however, Robert Harper has done a series of lectures. I have watched the first lecture and found it very enlightening so I would recommend it, so far anyway.

So for the meetup, as I mentioned we will probably start off with some easy learning and hacking. I thought it might be fun to try to implement something simple, maybe Fizz Buzz. Ultimately it would be nice to work to get set up with the ecosystem to do productive things in Haskell. Maybe eventually a group project or some higher level hacking, I have thought it might be interesting to something like work though some of the problems in Think Stats possibly using a Haskell statistics package.

Well those are my ideas, feel free to suggest others or correct me if I got anything wrong, this is all new to me.

noreply@blogger.com (elegantcoding) — 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 (elegantcoding) — 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 (elegantcoding) — 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 (elegantcoding) — 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 (elegantcoding) — 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 (elegantcoding) — 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 someone 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.

¹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 (elegantcoding) — 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 (elegantcoding) — 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 (elegantcoding) — 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 (elegantcoding) — 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 (elegantcoding) — 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 (elegantcoding) — 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 (elegantcoding) — 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 (elegantcoding) — Sun, 25 Mar 2012 17:08:00 +0000

Antony and Cleopatra

Julius Caesar

The Tempest

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.

(∀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)