A history of concurrent programming and Actor based frameworks – Part 1

In today’s landscape of high end parallel processing technology, large scale distributed systems, and the various high level hardware and software solutions that address the problems in software concurrency, it may not be an easy task to have a holistic view of the fundamentals of concurrency problems. This is largely by virtue of the many technologies that exist to solve the problems caused by the said topic, as well as their trends and adoption rates which sometimes does not allow much insight into the fundamentals and concepts of the problem itself.

This post is the first of a series of blog posts that take a look at the historical origins and evolution of handling software concurrency, as well as the Actor model – a mathematical model of concurrent computing put forward in the 1970s – which in recent years, has spawned the popularity of Actor based frameworks for implementing concurrent, resilient,  and distributed applications.

Early Origins

The term ‘concurrency’ and many of the problems associated with it, existed long before computers were invented, in the world of railroad lines, telegraph offices, and many other similar-era developments. Despite not being in any way associated yet with the computational problems faced in the last few decades, the early understanding of concurrency predominantly made headway under the then problems of rail line operation parallelization, synchronizing and sending multiple signals via telegraph lines, and similar operations in the many other sectors coming up in the age of the industrial revolution, that required operations and processes to be handled in parallel. Bring to mind, a late 18th century factory (maybe using punched card machines – the 1890 US census used a tabulating machine operating on punched cards) having workers and machinery at different stages and production lines churning out finished goods, and you could intuit as to how concurrency would have been a major consideration even during that period in time.

In any case, what we intuitively understand as concurrency problems became quite a complicated concept with the advent of computers. The first generation of machines were invented, and worked as ordained by the theories of computation laid down by Kurt Gödel, Alan Turing, Alonzo Church, and John von Neumann. The first generation vacuum tube behemoths ran their instructions sequentially and churned out results to humans, who for the most part were relieved that there was a means of automating calculations and processes that they would have otherwise done manually. The second and third generation machines, with their transistors and integrated circuit innards, created large waves of change in the computing world (by and large enabling microcomputers to be inexpensive and accessible by many), but the basic software instructions and processing model remained sequential – feeding a single processor – similar to how a first generation machine would have been programmed (to be fair, attempts at building super computers using parallelization were undertaken during this time. One such early example is the ILLIAC IV).

Turing Machines, Push Down Automata, and Finite State Machines

In order to lay down some sort of foundation, and to better appreciate the observations and content in the next few sections of this post, we divert our attention to a quick overview of abstract models of computations known as Turing machines, Push Down Automata, and Finite State Machines. Abstract machines are the foundations of modern computers. Mathemetical models of computation laid the foundations for computers and programming languages, and continue to explore the possibilities and limitations of what computers are capable of.

A finite state automata (or finite state machine – FSM) is an abstract and mathematical model of computation. Very simply put, it models an abstract machine that receives input in the form of a sequence of symbols, and can be only in one state at any given time. Changing from one state to another is known as a transition, and occurs based on the input symbol read from the sequence. From a global perspective of a FSM, the abstract machine only knows the current state it is in, and there is no concept of memory that can hold a list of previous states. Shown below is a rather contrived example of a FSM with three states – A, B, and C.

FSM1

Finite State Machine with states A, B, and C

State A, where the arrow is pointing into, is known as the starting or initial state. State C is known as the accepting state, denoted by the double circle. The arrows between the states as well as self referencing from the state, are known as transitions. The transitions are labelled with symbols, denoting the input symbol value that will allow the transition. In the above case there are three states and a set of two input symbols {0, 1}, therefore the FSM is called a three state two symbol FSM.

Given this information, it is very easy to see what will happen if an input sequence such as 1011 is fed into the above FSM. The very initial state will be the starting state A, and from here, we read the first symbol of the input sequence 1011, which is 1. This invokes the FSM to transition state to B, and now we are in state B. The next symbol we read in is 0, which means there will be a transition from B back to A. Likewise, the next symbol is 1, which means the FSM will transition to state B, and the final symbol is 1, whereby the state will transition from B to C.

The important point to note here is, there can be arbitratily long and complicated sequences of symbols (not limited to binary digits) being read in by the FSM, and when the final symbol of the sequence is read, the FSM could be in state C (the accepting state) or not. If it is in the accepting state after the sequence is completed, the set of symbols is known as a ‘regular language’, and the FSM is said to accept it. vice versa, a language is said to be regular, if there is some FSM that accepts it. This enables us to define that a sequence of symbols such as 1001001001001101 is a regular language to the above FSM, but 100100100100110 is not.

Definition: A regular language is a sequence of symbols that is accepted by an FSM, i.e. if it can terminate in an accepting state.

FSMs can be deterministic or non-deterministic. The FSM we looked at just now is an example of a deterministic FSM, where each state can have one and only one transition for an input. In a non-deterministic FSM, an input could change the current state of the FSM by having one transition, more than on transition, or no transition at all. This brings in the notion of non-determinism to the model of FSMs. Given below is an example of a non-deterministic FSM (NFSM).

NFSM1

Non-deterministic Finite State Machine

If you consider the above finite state machine, you would notice, that when in state A, if the input symbol is 0, there will be two state transitions, one to A itself, and another to B – i.e. there are two possible next states. Also, the above NFSM accepts regular languages with a sequence that ends with 010. If the state is in C, and the input symbol is 1, no state transition occurs.

There is another type of NFSM which uses what is known as ‘epsilon transitions’. In a very simple manner of looking at it, an epsilon transition means that the state change can take place without any input symbol being consumed. This will be clearer with the example of a NFSM that uses epsilon transitions as shown below.

NFSM2

NFSM with Epsilon transitions

In the above NFSM, the transitions labeled with the greek letter epsilon (ε) are the epsilon transitions. State A is the starting state, as well as an accepting state. C and G are accepting states as well. Lets consider what happens when the input set (symbol sequence) consists only of the symbol 0. First, we will be in the starting state A. But as there are two epsilon transitions from A, we will go to the states pointed by these without reading in any input symbol. So we automatically go to states B and H. Now we read in the input symbol, which is 0. In this case only, state H transitions to G, and no state change takes place from B. But as the input sequence is consumed, and the NSFM terminates in an accepting state (G), we can conclude that 0 is a member of a regular language accepted by this NFSM. So is 1, 01, 10, 010, 101, 1010, etc (which can be checked against the above NFSM).

NFSMs are pretty handy when modelling reactive systems. Also, modelling a system using NFSMs is easier than using deterministic FSMs. It would seem that NFSMs are more powerful than DFSMs given the more extensive rule sets of parallel state transitions and epsilon transitions, but it can be proven that for any regular language recognized by a NFSM, there exists an equivalent DFSM that accepts that language (and vice versa). This means that there will always be an equivalent DFSM for any given NFSM. This concept allows us to design or model systems using NFSMs, and later convert it into an equivalent DFSM.

In abstract machines (such as the FSMs we saw above), the power of the machine is another way of saying it can recognize more (regular) languages. There are limitations of FSMs that are addressed by another type of abstract machine known as the pushdown automata (PDA). This can be thought of as a FSM plus a stack that can be used to store information or state in a LIFO (Last In First Out) fashion. This enables the PDA to store bit values in the stack, and come to an acceptance state only if the stack is empty once the input symbol sequence is processed. If you notice, this is a different acceptance criteria from the FSMs we saw earlier. The below image shows a snapshot of a PDA in operation.

PDA1

Push Down Automata (Source)

If the power of abstract machines are determined by the languages they can recognize, then the mathematical model of computation known as Turing machines are more powerful than both FSMs and PDAs (This is another way of saying that there are sequences of input symbols that cannot be processed by FSMs or PDAs, but which are accepted by Turing machines).

MT1.gif

Mechanical model of a Turing Machine (via giphy.com)

Alan Turing published an article in 1936 titled ‘On Computable Numbers, with an Application to the Entscheidungsproblem‘, in which he first described Turing machines. A Turing machine can be thought of as a FSM with an infinite supply of a tape medium that it can read from and write to. Basically, the Turing machine reads a symbol from the tape which serves as the input symbol, and based on this input symbol, either writes a symbol to the tape, moves the tape left or right by one cell (a cell being one read/write unit of the tape which can contain a symbol), or transition to a new state. This seems a simple and basic way of operation, but Turing machines are powerful because given any algorithm, we can construct a Turing machine that can simulate that algorithm. Also, more interestingly, Turing machines have the innate ability to halt or stop, which gives rise to the halting problem.

TM1

Turing Machine (Source)

You can find an online Turing machine simulator at this link if you would like to experiment with Turing machines (I would suggest going through the tutorials in the simulator, and then trying out with the ‘even number of zeros‘ example which is simple yet explains the fundamentals). Also, this video contains one of the best and shortest explanations of Turing machines I have seen yet.

In modelling computations and abstract machines, Turing machines are the most powerful abstraction we have today, and all out modern computers, program code, and algorithms, are based on it. The reason it is powerful is, anything that a Turing machine can simulate, can be constructed physically in the world today. But something that has no Turing equivalent system, cannot be constructed in reality (i.e. we have never come up with a way of doing computations or any mathematical model, that can do more than what a Turing machine can do – this is why for example, we do not have any system today which can solve the halting problem). In this sense, Turing machines are at the forefront of what is computationly feasible. Maybe the next stage in this evolution is Quantum computing, but that would be a post for another day.

 

Stay tuned for post 2 in this blog series, where we will explore the early mathematical models of concurrency, Dijkstra’s 1965 paper which addressed concurrency control for the very first time and gave rise to the dining philosophers metaphor, and how Carl Hewitt’s claim that logical (mathematical) deduction could not carry out concurrent computation due to indeterminacy, laid the foundations for the Actor model.

Advertisements

Engineer or Programmer? The (non existent) Existential Dilemma…

EVERYTHING

This article describes my opinion of the term and title ‘software engineer’ and the implications behind it, and how it ties (or should tie in) to the viewpoints of the engineering discipline at large. (Blog header illustration created using canva)

I very rarely spend attention on philosophical debates relating to software development, but last week I was reading an article I came across at ‘The Atlantic’, which prompted a train of thought, including this blog post. I suggest you read it before continuing, as it has a very interesting premise on why programmers should not call themselves (software) engineers. I neither agree nor disagree with the author or the article, but it had some very interesting ideas, that motivated me to document my thoughts and opinions in this post…

First, a bit about the term ‘software engineering’ from my own perspective and understanding. Throughout my career, I used to work with people who were (are) referred to as software engineers, themselves being graduates of computer science, information systems, or software engineering, the titles being appropriated to the name of the undergraduate degree that each followed in his or her academic journey. I myself hold a degree in ‘software engineering’ issued by a well known university situated around Regent street, north-west of central London in the United Kingdom. Therefore, the term or title ‘software engineer’ was something I was (and am) quite comfortable with, whether in how I introduce myself, or how I refer to my colleagues.

On the origins of the term ‘software engineering’, the article in question quotes a fact that is commonly taught in the industry and field of software development today, which is that the term ‘software engineering’ was first deliberately used in the 1968 Garmisch-Partenkirchen conference organized by NATO. It is said that the term was coined provocatively, in a bid to challenge software development at the time to align with the rigid processes and methods followed by the established branches of engineering. But it was interesting for me to come across an article by Bertrand Meyer, that provides some evidence and basis that the term was used at least two years prior to the NATO conference, and in positive light, indicating (at the time) that software development should be considered an engineering discipline in its own right.

The established engineering disciplines, are coined as ‘established’ based on the rigid processes, regulatory bodies, certifications, licenses, continuous learning, and ethical codes they follow. I am quite firm in my understanding that this is a good thing. But some of these aspects came about mainly due to the problems and engineering disasters that were prevalent in the 19th and 20th centuries, and saw the need to bring in standards, ethics, regulations, certifications and the rest. There is always a scenario which prompts the need for better processes, regulations, and policies. This was widely characterized in the software development world in the last two decades, where a myriad of development philosophies and approaches were invented. Even Robert C. Martin discusses about the situation, and tries to convey the message that if software developers (engineers?) don’t start getting there act together, we will be imprisoned by regulations and policies dictating how we should develop software.

If the practice and business of developing software is expected to evolve into an (established) engineering discipline, the progress will always be compared to the other mature engineering disciplines. This outlook and comparision was not favoured by some, which resulted in a large number of software development circles stating that software is more art/craft/science than engineering, and that there are better ways to build software than using rigid engineering processes. This viewpoint is widely respected and quite popular in the software development world today. On this side of the wall, software development should be lean, agile, and dynamic, without heavy weight engineering processes and regulations retarding these ideas, which is practical for all sense and purposes. Software is an artifact and material unlike anything that traditional engineers are used to working with, and early lessons taught us that building software  to specifications with rigid processes containing blueprints and schematics was not the best way to go about things. But the problem was (and still is) that the computing infrastructure (used by the public, consumers, clients, business users etc.) which is the end product of software development, still requires the same rigidity, reliability, safety, and conformance that a bridge or building built by a civil engineer should have. This is expected by a society which functions daily on the trust and understanding placed on the infrastructure around them, built by engineers. And therein lies the disdain towards the software development world (mostly by the engineering community, I suppose), where systems go wrong, bugs seem to evolve and reproduce, and software development is an activity that seems random and haphazard. The engineering world has its fair share of problems and disasters, just as there are software project failures and disasters. But a crucial difference is that the engineering disciplines will emphasize and priorotize the regulations, standards, safety to public health, and ethics, even if failing to deliver.

Just as engineering has foundations in the natural sciences, software ‘engineering’ too, has its origins in philosophy, mathematical logic, and various other branches of science, that has no direct correlation to what we do today as developers of software. The early proponents and pioneers who set the stage for software development to be a wide spread phenomenon, were computer scientists, mathematicians, particle physisicts, and information theorists. Not engineers per se. I was searching online and came across the professional engineers ontario website, where the definition of a professional engineering was formally stated. Based on my reading, I specifically chose canada as they are one of the countries who are extremely strict with the title ‘engineer’ and who is licensed to carry it. I would like to directly quote the definition of the practice of engineering, taken from their website:

Professional engineering is:

  1. any act of planning, designing, composing, evaluating, advising, reporting, directing or supervising (or the managing of any such act);

  2. that requires the application of engineering principles; and

  3. concerns the safeguarding of life, health, property, economic interests, the public welfare or the environment, or the managing of any such act.

Rings a bell? At least for me it did. This seems to sum up what I have been doing for the past few years in my tenure as a software engineer. In a sense, what’s missing is the regulatory bodies, the policies, licenses, code of ethics, and the rest of the bells and whistles.

Let me summarize (thank you, if you are still reading) and propose an approach towards building better software, gaining the respect of traditional ‘mature’ branches of engineering, and proving ourselves worthy of the title ‘software engineer’.

  • First, I lied about software development not having a code of ethics: Software engineering does have a code of ethics known as the IEEE CS/ACM Code of Ethics and Professional Practice, but no regulatory body to enforce it. It would be a great start to read this, and attempt to see how applicable it is in our everyday work. We may not have regulatory bodies, policies or practice licences etc. but that is not an excuse for not committing to the best standards and practices, and/or not being ethical. In the popular book Content Inc, one of the main (controversial) ideas conveyed by the author is that you should build an audience before you figure out what it is you want to sell them. Ours is a somewhat similar situation, where we need to build our audience (society expecting traditional engineering recipes) and figure out what to sell them (trust and reliance in software development using tailored/non-traditional engineering processes, backed by ethics and a sense of responsibility).
  • Second, the use of sound engineering principles: The design and architecure of the software intensive systems we build, the practices and guidelines followed when coding, the project management and costing aspects, the control and quality checks, all rely on the application of sound engineering principles in the construction of software. True, there is no universal standard or guideline dictating how we go about doing this (in fact there are a great many variety of approaches and methodologies), but whatever we tradeoff or cut-down on, it would be advisable to always reflect and check whether whatever we are doing can still be comfortably called ‘applying sound engineering principles’, without any hint of doubt in our mind.
  • Third, continuous learning and certifications: The software development world is plagued with people who are too busy learning and have no time to work, or are too busy working and have no time to learn. Jokes aside, continuous learning is something we developers are familiar with, due to the evolving trends and technology waves that tow us in their wake. There is no one person or body to standardize it and tell us the how, why, what, and when to learn, but we have ample certification programs to showcase to employers how good we are. Maybe we should have that same pride and attitude, in showing that we are capable of building great software, and that our certifications and achievements are a testament to our responsibility and obligations towards our stakeholders as well.

That was not a short summary, and I apologize for that. Looking back, this post is not a negative response to the original article at ‘The Atlantic’, but instead I was interested in critically analyzing and identifying the weaknesses in software engineering, which is constantly being targeted by traditional engineering disciplines. That being said, in ending, a big salute to all the software engineers, developers, and programmers, who constantly and daily contribute in advancing and moving the field of software engineering, towards being a mature and well respected discipline and industry.