About a year ago, I took up playing a middle-eastern instrument called the oud.
One of the characteristic forms of music for the oud is called a taqsim , which is a short improvisation. I’ve always loved improvisational musical styles, and this was part of the draw of the oud for me.
Improvisational music can be a very pure form of spontaneous creativity, and when it is going well, it gives a powerful feeling of freedom and self-expression.
Many people who don’t play an instrument or who play an instrument only by reading sheet music often ask me how one can possibly make up music on the fly, and I always tell them it is easier than it sounds.
A common misconception is that to be creative means that you throw all rules and restraints out the window, pulling great stuff out of thin air, as if by magic. Many people think that creativity is somehow inherently chaotic and random. But a simple example can show that this is false.
Have you ever listened to a small child with no musical training hammer away at a piano? Based on the “creativity is chaos” misconception, this should be the height of creative expression, since the child is following no structures or rules aside from the physical limits of the piano. But most people would agree that the result is not music, but rather irritating noise.
The first thing that many piano methods do with our budding creative genius is to teach the scales. This is because these are the basic structures that underpin western music. To be either a competent listener or a competent player of western-style music begins by internalizing the sound landscape that is defined by the diatonic (or pentatonic) scales and the melodic and harmonic palette they imply.
After learning even one of the scales, our enriched child could hammer away the same as before, but restrict the hammering to the notes of that scale. Because there is some musical structure, most people would judge the result as more musical, and in that sense morecreative.
This is the trick with improvisation: you aren’t really making up something from scratch. All common forms of musical improvisation I’ve ever studied (Indian classical raga , the blues , Middle Eastern maqamat and Jazz , for example) actually have a lot of structure to begin with: there are specific scales, rhythms, sequences and patterns that have to be learned and internalized or else the result won’t sound like music, or at least not the kind of music you are trying to play.
Once the player (or the listener) has internalized all the rules and structure, then freedom from rules comes back into play. If you have too many rules followed too rigidly, the results become boring and predictable and the music loses its vitality. Great improvisers know where their freedom lies and know where and how to break the rules to produce something fresh and unexpected, and it is this quality that can make improvised music so vital and exciting for players and listeners. So-so improvisers sometimes fall flat on their face by going too far away from the basic structure and have to scurry back to it. But even this freedom to fail is part of the process.
What is true for music seems to be true for other domains with complex structure that require creative solutions: software development, management, politics and economics, for example.
In any of these domains, too few rules results in inharmonious chaos, and too many stifles inventive and effective approaches.
Any approach to these problem areas that looks only at adding regulation or only at removing regulation is probably missing the boat.
The real question always is: “How do you plan to balance freedom and control to maximize harmonious creativity?” Any philosophy of these domains that can’t answer this question is probably not worth considering.
September 30, 2009
July 7, 2009
Why proving that P ≠ NP is hard
A while ago I spent the time to “audit” online a Cambridge University course given by Tim Gowers on computational complexity.
In this course, Gowers takes the students through a proof by Razborov that there is no “natural proof”, for a particular form of the problem, that P ≠ NP, which I found very interesting.
This got me thinking about why this is a hard problem to solve, and I thought it might be useful to explain the intuitive reasons behind it.
So let’s think about this by looking at the Traveling Salesman Problem, since it is a fairly intuitive example of one of the hardest problems in the NP complexity class, known as NP-complete.
In this problem, you have to find the shortest path through a number of cities, visiting each city once and only once. This is a typical NP problem, where the naïve approach to solving the problem would be to just work through all the combinations possible, check the value of that combination (in this case the length), and pick the shortest one.
The problem with that is that the number of combinations gets very large very fast, so it really isn’t practical to do this.
Let me show you what I mean. Let’s take the case where there are 5 cities: A, B, C, D, E. Any path through these cities can be described by a sequence of these letters. For example, CDEAB would be the sequence starting at city C, then going on to city D, etc. To figure out how many combinations there are, I have to use each of the letters once and only once, so there are 5 possible choices for the first slot, four for the second, and so on. This gives me 5x4x3x2x1=5!=120.
In general, this brute force approach to solving the problem, which represents the worst case scenario among solutions, will take n! steps, where n is the number of cities we are considering. This gets very big, very fast. For example 10! is equal to 3628800, so you can see that as you add cities it becomes vastly harder to solve the problem this way.
Now it is very important to realize that this is the worst-case scenario only, or as it is described in mathematics, an “upper bound” on how hard the problem is. For example, if all the cities are in a straight line, you can solve the problem in many fewer steps: just start on one end and move to the next in line and so on
This works because we know that on a straight line, the shortest path will be on that line, so that if the cities are aligned ABCDE, we know right away that we aren’t going to have to consider any of the combinations that don’t follow the sequence on the line. In other words, there is a pattern to the data that allows us to ignore a number of combinations (in this case, all but the two, which are of equal length: ABCDE, and EDCBA).
But to say that some problem is in the class NP (and not in P) is essentially to say that there will always be some collection of cities you could choose that would require you to go through the worst case scenario to find the shortest one. (Technically, the actual worst case scenario for this problem is only exponential in complexity, but that is still pretty bad and doesn’t affect my argument here.)
That is, unless someone can prove that P=NP. This would mean that there was always a shortcut that allowed you to find the solution without having to work through the majority of the possible combinations. And this shortcut would almost certainly involve being able to consistently find some pattern in the data, just as we did with the straight line example, that simplifies the data down to a smaller number of cases.
So in a sense, it should be much easier to prove P=NP than that P ≠ NP. (That no one has proven the former yet is a pretty good reason to suspect that the latter is true, even though no one has proved it either.)
The reason is that to prove P=NP, you just need to show that there is always a pattern in the data that will simplify it, whereas to prove P ≠ NP, you would have to show that there can’t be such a pattern for some scenarios in the problem set.
Why is it easier to show that there is a pattern than that there can’t be a pattern? Well, if you have a pattern, you have a relatively small number of steps needed to describe that pattern, and it is much easer to work through those steps and convince yourself that you have covered all the bases. You can also try your pattern on all the hairiest known instances of the problem and show that they work.
In a sense, having a pattern simplifies the search space required for the proof in exactly the same way that having the pattern simplifies the search space to find the answer to the problem.
But how do you show that there is no possible pattern for some set of data?
Let’s say that I give you a list of digits and tell you that one of two scenarios generated these digits: either I am generating them randomly for each digit as you ask for them, or I am using some relatively simple-to-genarate pattern to generate them. Here is a sample list:
15926535897932384626433832795…
Can you see a pattern? You could do a statistical test on the digits to see if they show the properties of randomness, and in this case, I think you would find that they do show those properties.
So, can you then conclude that they are random?
No, unfortunately not, since there is a pattern here: these are the digits of pi after the well-known first three 3.14…
So the challenge is that you can never really be sure that there is no pattern to some data set; it could just be a really, really unobvious pattern that you haven’t thought of yet.
So you can see how very hard it would be to prove that there is always some configuration of cities that can’t be simplified by some pattern, which is only part of what you would have to do to prove that P ≠ NP.
This is why it is unlikely that anyone will find such a proof unless they can develop some hard-to-imagine technique that allows us to detect when there aren’t any patterns in a set of data.
In this course, Gowers takes the students through a proof by Razborov that there is no “natural proof”, for a particular form of the problem, that P ≠ NP, which I found very interesting.
This got me thinking about why this is a hard problem to solve, and I thought it might be useful to explain the intuitive reasons behind it.
So let’s think about this by looking at the Traveling Salesman Problem, since it is a fairly intuitive example of one of the hardest problems in the NP complexity class, known as NP-complete.
In this problem, you have to find the shortest path through a number of cities, visiting each city once and only once. This is a typical NP problem, where the naïve approach to solving the problem would be to just work through all the combinations possible, check the value of that combination (in this case the length), and pick the shortest one.
The problem with that is that the number of combinations gets very large very fast, so it really isn’t practical to do this.
Let me show you what I mean. Let’s take the case where there are 5 cities: A, B, C, D, E. Any path through these cities can be described by a sequence of these letters. For example, CDEAB would be the sequence starting at city C, then going on to city D, etc. To figure out how many combinations there are, I have to use each of the letters once and only once, so there are 5 possible choices for the first slot, four for the second, and so on. This gives me 5x4x3x2x1=5!=120.
In general, this brute force approach to solving the problem, which represents the worst case scenario among solutions, will take n! steps, where n is the number of cities we are considering. This gets very big, very fast. For example 10! is equal to 3628800, so you can see that as you add cities it becomes vastly harder to solve the problem this way.
Now it is very important to realize that this is the worst-case scenario only, or as it is described in mathematics, an “upper bound” on how hard the problem is. For example, if all the cities are in a straight line, you can solve the problem in many fewer steps: just start on one end and move to the next in line and so on
This works because we know that on a straight line, the shortest path will be on that line, so that if the cities are aligned ABCDE, we know right away that we aren’t going to have to consider any of the combinations that don’t follow the sequence on the line. In other words, there is a pattern to the data that allows us to ignore a number of combinations (in this case, all but the two, which are of equal length: ABCDE, and EDCBA).
But to say that some problem is in the class NP (and not in P) is essentially to say that there will always be some collection of cities you could choose that would require you to go through the worst case scenario to find the shortest one. (Technically, the actual worst case scenario for this problem is only exponential in complexity, but that is still pretty bad and doesn’t affect my argument here.)
That is, unless someone can prove that P=NP. This would mean that there was always a shortcut that allowed you to find the solution without having to work through the majority of the possible combinations. And this shortcut would almost certainly involve being able to consistently find some pattern in the data, just as we did with the straight line example, that simplifies the data down to a smaller number of cases.
So in a sense, it should be much easier to prove P=NP than that P ≠ NP. (That no one has proven the former yet is a pretty good reason to suspect that the latter is true, even though no one has proved it either.)
The reason is that to prove P=NP, you just need to show that there is always a pattern in the data that will simplify it, whereas to prove P ≠ NP, you would have to show that there can’t be such a pattern for some scenarios in the problem set.
Why is it easier to show that there is a pattern than that there can’t be a pattern? Well, if you have a pattern, you have a relatively small number of steps needed to describe that pattern, and it is much easer to work through those steps and convince yourself that you have covered all the bases. You can also try your pattern on all the hairiest known instances of the problem and show that they work.
In a sense, having a pattern simplifies the search space required for the proof in exactly the same way that having the pattern simplifies the search space to find the answer to the problem.
But how do you show that there is no possible pattern for some set of data?
Let’s say that I give you a list of digits and tell you that one of two scenarios generated these digits: either I am generating them randomly for each digit as you ask for them, or I am using some relatively simple-to-genarate pattern to generate them. Here is a sample list:
15926535897932384626433832795…
Can you see a pattern? You could do a statistical test on the digits to see if they show the properties of randomness, and in this case, I think you would find that they do show those properties.
So, can you then conclude that they are random?
No, unfortunately not, since there is a pattern here: these are the digits of pi after the well-known first three 3.14…
So the challenge is that you can never really be sure that there is no pattern to some data set; it could just be a really, really unobvious pattern that you haven’t thought of yet.
So you can see how very hard it would be to prove that there is always some configuration of cities that can’t be simplified by some pattern, which is only part of what you would have to do to prove that P ≠ NP.
This is why it is unlikely that anyone will find such a proof unless they can develop some hard-to-imagine technique that allows us to detect when there aren’t any patterns in a set of data.
June 14, 2009
What problem are you trying to solve?
Anyone who has worked in IT for any period of time is going to be familiar with the dilemma of choosing one particular solution over another. Should I learn language X or language Y? Should I use framework A or framework B for my next project? Should I use the Foo Architecture or the Bar Architecture? Is the Widget application better than the Grommet application?
Since sometimes it seems that the choice you make can have big costs in terms of your project’s success (and your future employability), these dilemmas can result in a lot of stress. It doesn’t help that for each solution you have some proponent telling you that if you don’t use their approach you are stupid and ugly (see Linus Torvalds talking about his source control tool ).
So what’s the smart way to decide?
I think the first step is to realize that you have the wrong question. Technology people by definition tend to be interested in technology (tools and solutions) and we tend, as a result, to give short shrift to the problems themselves, especially when they fall outside our domain. As a result, solutions pile up faster than you can evaluate them, and problems often get shoehorned in a pet solution. So what is the right question?
Do you remember those word problems we used to have to do in school? Trains leaving the station at certain times and speeds, Mary and Bill trying to divide up a pie, and all those hypothetical problems?
The secret of those problems was often just figuring out what the problem was in the simplest terms. Once you rephrased the question, you often knew exactly which technique from that week’s lesson to apply to solve it. You could just whack the problem with all the techniques you had learned, hoping to hit the right one, but you would probably take too much time or might even get an “answer” that was totally off base.
To make this brute force approach even less likely to succeed, the teachers and textbook sometimes threw in irrelevant details that sounded important but had nothing to do with the real solution, in the same way that mystery writers throw in red herrings to make it harder to guess whodunit.
So the only reliable way to solve these problems correctly was to learn to filter out the extraneous blather and find the pithiest answer to the question “What problem am I really trying to solve?”
So how can we use this to solve our solutions dilemma? Let’s start by recognizing that the real problem is not what solution to choose but rather resolving the problem the solution is for. Trying to choose a tool without explicitly defining the real problem is exactly like trying to solve those word problems by throwing all the techniques you know at them. You may get lucky, but more likely you will make a mess.
If you realize, having thought about it, that the problem you are trying to solve is to avoid having others think you are ugly and stupid, then there is an easy solution to the problem: give up on technology altogether. In technology there is always someone telling you are ugly and stupid because you didn’t choose the same solution as them, so you might as well get used to it. If you want to go one step further, reject all forms of ideological thinking on principle, and craft your own rational set of criteria by which to judge things.
If you discover instead that there is some substantive problem you want to solve, spend some time trying to understand the problem. Ask yourself what the essential characteristics of the problem are. Identify some things that might normally be of interest but don’t really apply in this case or have less importance than normal. The truth is that no solution is perfect, all solutions require trade offs, and the secret of success is focusing on the must-haves while sacrificing the merely nice-to-haves or, more often, even the not-quite-so-must-haves.
Sometimes I find it very useful to start sketching out my own solution from scratch. At some point you realize either that you have a nice simple solution and don’t need to go any further, or that, now that you have a better feel for the problem and its challenges, that you have clear criteria upon which to base the choice of an external solution.
Anyone who wants to get good at software architecture has to be willing to throw out conventional wisdom and make choices that fit the problem at hand, not the problem that advocates of particular solutions tell them they should have. Sometimes just spending some quality time with your specific problem clarifies what you really need and melts the solutions dilemma away.
Since sometimes it seems that the choice you make can have big costs in terms of your project’s success (and your future employability), these dilemmas can result in a lot of stress. It doesn’t help that for each solution you have some proponent telling you that if you don’t use their approach you are stupid and ugly (see Linus Torvalds talking about his source control tool ).
So what’s the smart way to decide?
I think the first step is to realize that you have the wrong question. Technology people by definition tend to be interested in technology (tools and solutions) and we tend, as a result, to give short shrift to the problems themselves, especially when they fall outside our domain. As a result, solutions pile up faster than you can evaluate them, and problems often get shoehorned in a pet solution. So what is the right question?
Do you remember those word problems we used to have to do in school? Trains leaving the station at certain times and speeds, Mary and Bill trying to divide up a pie, and all those hypothetical problems?
The secret of those problems was often just figuring out what the problem was in the simplest terms. Once you rephrased the question, you often knew exactly which technique from that week’s lesson to apply to solve it. You could just whack the problem with all the techniques you had learned, hoping to hit the right one, but you would probably take too much time or might even get an “answer” that was totally off base.
To make this brute force approach even less likely to succeed, the teachers and textbook sometimes threw in irrelevant details that sounded important but had nothing to do with the real solution, in the same way that mystery writers throw in red herrings to make it harder to guess whodunit.
So the only reliable way to solve these problems correctly was to learn to filter out the extraneous blather and find the pithiest answer to the question “What problem am I really trying to solve?”
So how can we use this to solve our solutions dilemma? Let’s start by recognizing that the real problem is not what solution to choose but rather resolving the problem the solution is for. Trying to choose a tool without explicitly defining the real problem is exactly like trying to solve those word problems by throwing all the techniques you know at them. You may get lucky, but more likely you will make a mess.
If you realize, having thought about it, that the problem you are trying to solve is to avoid having others think you are ugly and stupid, then there is an easy solution to the problem: give up on technology altogether. In technology there is always someone telling you are ugly and stupid because you didn’t choose the same solution as them, so you might as well get used to it. If you want to go one step further, reject all forms of ideological thinking on principle, and craft your own rational set of criteria by which to judge things.
If you discover instead that there is some substantive problem you want to solve, spend some time trying to understand the problem. Ask yourself what the essential characteristics of the problem are. Identify some things that might normally be of interest but don’t really apply in this case or have less importance than normal. The truth is that no solution is perfect, all solutions require trade offs, and the secret of success is focusing on the must-haves while sacrificing the merely nice-to-haves or, more often, even the not-quite-so-must-haves.
Sometimes I find it very useful to start sketching out my own solution from scratch. At some point you realize either that you have a nice simple solution and don’t need to go any further, or that, now that you have a better feel for the problem and its challenges, that you have clear criteria upon which to base the choice of an external solution.
Anyone who wants to get good at software architecture has to be willing to throw out conventional wisdom and make choices that fit the problem at hand, not the problem that advocates of particular solutions tell them they should have. Sometimes just spending some quality time with your specific problem clarifies what you really need and melts the solutions dilemma away.
May 28, 2009
Functional Programming is Not All or Nothing
I’ve noticed a flurry of discussion around the blogosphere lately about what is and is not a functional programming language and what is or is not stateful. After being interested in functional programming (FP) for many years, I’m glad that it is finally getting some mainstream attention. I think FP has some valuable lessons for all programmers, and that it provides a better default mindset for programming than traditional imperative programming.
However, a lot of the discussion seems to make the mistake of assuming that functional programming and statefulness are all-or-nothing properties, that either you have a total purity of statelessness or you have opened Pandora’s Box and let all the evils of state into your program or programming language. But the truth is that functional programming is best viewed as a style of programming with different default assumptions about state. And statefulness is best viewed as a continuum that varies along at least two dimensions — locality and monotonicity — both of which I will explain shortly.
Before I do that, I had best describe in simple terms what state is. The easiest way to understand state is to imagine that I have given you a distinctive-looking box. If each time you open the box you find exactly the same contents, then the box can be said to be stateless. (This is also known as referential transparency). If each time you open the box the contents vary — the box could be empty sometimes, but full later, it could have different items in it or the same items with some new ones added — then it is stateful.
As you can see from this description, most boxes that we use in the real world are stateful, since it is very unusual for their contents to remain the same throughout their lifetime. However, if you are doing something complicated, say keeping financial records from past years in banker’s boxes, you might impose a discipline on your boxes, such as designating a particular box to contain only those financial records from April 2002, so that you can reliably find the records for a given month when you are looking for them.
Programming is like this as well. “Normal” imperative programming uses variables that can have changing values throughout the life of the program, which matches our understanding of boxes in the real world. FP takes the banker’s view of boxes. Since programs are very complex, and you want to be assured of finding what you expect, then the default assumption is that the contents of boxes will be the same throughout the life of the program.
So the key difference between a functional and an imperative style of programming is not whether there is any state at all in the program but where you start from. With imperative programming you start by assuming total changeability of all values you work with and have to add disciplines to get that state under control, whereas with FP you start from a place of statelessness and strategically loosen the reins in small amounts when you need to. The great strength of the FP approach is that it is much easier to maintain control by letting the genie out of the bottle slowly than by starting with the genie out of the bottle and trying to jam it back in.
The first dimension of state I want to discuss, locality, should be the easiest for programmers to understand but, for some reason, often causes confusion. Locality for state is just like scope for names in that it ranges from totally private to global, depending on how widely in your program it can be seen. A well-known property that makes state more local is encapsulation, when it is used to limit the visibility of a particular bit of state to a small part of the program. For encapsulation to accomplish this, though, it must actually hide the effects of the state from the parts of the program outside its scope.
To explain this, it is helpful to consider a common objection to functional programming languages by people new to the subject: how can a stateless program be built on a computer, which is an inherently stateful machine? The answer is that so long as the state is completely localized “under the hood”, it isn’t state at the next level up.
If we go back to the box analogy, let’s say that you have a very high-tech box that has the same contents every time you open it, but that, instead of the contents just being there when the box is closed, it actually disassembles the item when you close it and re-assembles it when you open the box again. The box is stateless because its contents never change from your point of view, even though its contents change when you can’t see inside.
So you can reduce the state in your program by ensuring that its various components look to each other as if they are stateless, even if internally they are implemented with large amounts of state, say for efficiency.
Monotonicity of state is a little bit more subtle and probably less consciously familiar to programmers. Monotonic is a fancy way to say that once you add something, you can’t take it away. Using our boxes, the simplest example of monotonic state would be if, when you first open a box, you might find either nothing or something, but, as soon as you open the box and find something there, you must find the same something in the box every time you look in it thereafter. Upon finding the box empty, you could stop what you are doing and wait for something to show up in the box, after which you could be sure that it was not going to change, or you could take the opportunity to fill the box with something you want to fill it with, confident that someone else won’t be able to change it later. This is how dataflow variables work.
A more complex example of monotonic state would be a stream.
Once you have asked for the first value from the stream, it is as if you have filled the first box in the sequence, even if the box for the next item in the stream might still be empty.
With non-monotonic state, items can be added and taken away from the box at will, so that the box might have one thing in it the first time you open it, nothing in it the second time, and something totally new the third time. This is the kind of state that we normally think about when we talk about default imperative statefulness.
You can see that, though monotonic state is still state, it is much more predictable and manageable then full non-monotonic state, since you can always tell how much has changed from the last time you checked and you can be assured that what you found before will still be there. Furthermore, there is an explicit order to the changes in state that allows you to understand the history of operations, and thereby to make better automated decisions about what to do.
This is why the kind of message-passing concurrency, such as is found in Erlang is less stateful and relatively safer and more scalable than full shared-state concurrency, since an asynchronous message queue can be thought of as a monotonically-stateful stream.
While it would be much easier to talk about functional programming if statefulness were a nice black and white property that could be assigned to a particular language or program, I hope it is clear now that things are not quite so simple, and that degrees of state and “functionalness” could be present in any language or program. Obviously some languages and programs are going to make reduced state the default, and thus easier to implement, but the functional perspective can be applied to any language or program.
And making use of this perspective will help tame the complexity of software, especially in the face of concurrency.
However, a lot of the discussion seems to make the mistake of assuming that functional programming and statefulness are all-or-nothing properties, that either you have a total purity of statelessness or you have opened Pandora’s Box and let all the evils of state into your program or programming language. But the truth is that functional programming is best viewed as a style of programming with different default assumptions about state. And statefulness is best viewed as a continuum that varies along at least two dimensions — locality and monotonicity — both of which I will explain shortly.
What is state?
Before I do that, I had best describe in simple terms what state is. The easiest way to understand state is to imagine that I have given you a distinctive-looking box. If each time you open the box you find exactly the same contents, then the box can be said to be stateless. (This is also known as referential transparency). If each time you open the box the contents vary — the box could be empty sometimes, but full later, it could have different items in it or the same items with some new ones added — then it is stateful.
As you can see from this description, most boxes that we use in the real world are stateful, since it is very unusual for their contents to remain the same throughout their lifetime. However, if you are doing something complicated, say keeping financial records from past years in banker’s boxes, you might impose a discipline on your boxes, such as designating a particular box to contain only those financial records from April 2002, so that you can reliably find the records for a given month when you are looking for them.
Two styles of programming
Programming is like this as well. “Normal” imperative programming uses variables that can have changing values throughout the life of the program, which matches our understanding of boxes in the real world. FP takes the banker’s view of boxes. Since programs are very complex, and you want to be assured of finding what you expect, then the default assumption is that the contents of boxes will be the same throughout the life of the program.
So the key difference between a functional and an imperative style of programming is not whether there is any state at all in the program but where you start from. With imperative programming you start by assuming total changeability of all values you work with and have to add disciplines to get that state under control, whereas with FP you start from a place of statelessness and strategically loosen the reins in small amounts when you need to. The great strength of the FP approach is that it is much easier to maintain control by letting the genie out of the bottle slowly than by starting with the genie out of the bottle and trying to jam it back in.
Locality of State
The first dimension of state I want to discuss, locality, should be the easiest for programmers to understand but, for some reason, often causes confusion. Locality for state is just like scope for names in that it ranges from totally private to global, depending on how widely in your program it can be seen. A well-known property that makes state more local is encapsulation, when it is used to limit the visibility of a particular bit of state to a small part of the program. For encapsulation to accomplish this, though, it must actually hide the effects of the state from the parts of the program outside its scope.
To explain this, it is helpful to consider a common objection to functional programming languages by people new to the subject: how can a stateless program be built on a computer, which is an inherently stateful machine? The answer is that so long as the state is completely localized “under the hood”, it isn’t state at the next level up.
If we go back to the box analogy, let’s say that you have a very high-tech box that has the same contents every time you open it, but that, instead of the contents just being there when the box is closed, it actually disassembles the item when you close it and re-assembles it when you open the box again. The box is stateless because its contents never change from your point of view, even though its contents change when you can’t see inside.
So you can reduce the state in your program by ensuring that its various components look to each other as if they are stateless, even if internally they are implemented with large amounts of state, say for efficiency.
Monotonicity of State
Monotonicity of state is a little bit more subtle and probably less consciously familiar to programmers. Monotonic is a fancy way to say that once you add something, you can’t take it away. Using our boxes, the simplest example of monotonic state would be if, when you first open a box, you might find either nothing or something, but, as soon as you open the box and find something there, you must find the same something in the box every time you look in it thereafter. Upon finding the box empty, you could stop what you are doing and wait for something to show up in the box, after which you could be sure that it was not going to change, or you could take the opportunity to fill the box with something you want to fill it with, confident that someone else won’t be able to change it later. This is how dataflow variables work.
A more complex example of monotonic state would be a stream.
Once you have asked for the first value from the stream, it is as if you have filled the first box in the sequence, even if the box for the next item in the stream might still be empty.
With non-monotonic state, items can be added and taken away from the box at will, so that the box might have one thing in it the first time you open it, nothing in it the second time, and something totally new the third time. This is the kind of state that we normally think about when we talk about default imperative statefulness.
You can see that, though monotonic state is still state, it is much more predictable and manageable then full non-monotonic state, since you can always tell how much has changed from the last time you checked and you can be assured that what you found before will still be there. Furthermore, there is an explicit order to the changes in state that allows you to understand the history of operations, and thereby to make better automated decisions about what to do.
This is why the kind of message-passing concurrency, such as is found in Erlang is less stateful and relatively safer and more scalable than full shared-state concurrency, since an asynchronous message queue can be thought of as a monotonically-stateful stream.
Conclusion
While it would be much easier to talk about functional programming if statefulness were a nice black and white property that could be assigned to a particular language or program, I hope it is clear now that things are not quite so simple, and that degrees of state and “functionalness” could be present in any language or program. Obviously some languages and programs are going to make reduced state the default, and thus easier to implement, but the functional perspective can be applied to any language or program.
And making use of this perspective will help tame the complexity of software, especially in the face of concurrency.
Subscribe to:
Posts (Atom)