The downfall of Imperative Programming

[Henri Bergius]

While not about FBP directly, again some argumentation that we may find useful:
http://fpcomplete.com/the-downfall-of-imperative-programming/

[Ron Lewis]

On Monday, April 9, 2012 1:48:34 PM UTC-4, Henri Bergius wrote:

While not about FBP directly, again some argumentation that we may find useful:
http://fpcomplete.com/the-downfall-of-imperative-programming/

Henri Bergius, thank you for the link. I liked the way the article boiled down the problems we face in parallel/concurrent processing. Immutable variables obviates the problem of data races as explained in the article. Immutable variables are a feature of the functional programming paradigm. I think immutable variables start out as unset to any value, then they may be set only once. Thereafter, their value cannot be changed. I do not know so much about functional programming. So, I appreciate if anyone says I am on the right track.

I think flow based programming offers another way to avoid data-races, without immutability. That is, an IP may be modified and passed on to the next processor. Right? 

 

[John Cowan]

Ron Lewis scripsit:

> I think flow based programming offers another way to avoid data-races,
> without immutability. That is, an IP may be modified and passed on to the
> next processor. Right?

Yes, because access to the IP is effectively serialized by the rule that
a process can no longer touch it after it sends it on. JavaFBP does not
actually enforce this.

--
De plichten van een docent zijn divers, John Cowan
die van het gehoor ook. co...@ccil.org
--Edsger Dijkstra http://www.ccil.org/~cowan

[Ged Byrne]

Hi Ron,

There's a good explanation of race conditions here: http://support.microsoft.com/kb/317723

The problem really occurs at the machine level, where the language abstractions break down.  Variables are just placeholders for memory locations and where multiple threads share the same locations at the same time we have problems.

In imperative programming we tell the machine what to do.  As wikipedia puts it "imperative programs define sequences of commands for the computer to perform." 

Personally I always like to imagine the inside of a processor as being like a factory.  

Imagine a factory where different workers are all building the same thing.  It sits there on the work top and everybody clambers around trying to do their bit.  It's chaos and very inefficient.  So many things will go wrong, although it's often surprising how well people manage to cope.

Languages like C and Java are like this.  The memory is like a worktop and the code is like workers busy working on the contents of that worktop.  To make things worse

 other workers are constantly swapping the contents so that each person gets to work on their own bit.  It's a miracle of computer science that it all works most of the time.  The problem is that every so often it fails, and when it does it's really hard to work out why.

The traditional solution is to have locks on the worktop, so that only one person can work at a time.  It says that once a person starts a task they get the worktop all to themselves until they've finished.  Everybody else has to queue up and wait their turn.  It's controlled, but can be inefficient.  So much time is spent waiting in a queue.

The FPB approach it the equivalent of the production line.  Instead of all the workers moving around the worktop, the worktop moves between the workers.  The ports connecting the FPB components are like the conveyor belt moving from worker to worker.  Each worker has one task to do, and the belt ensures that theses tasks are done one at a time and in the correct order.  As Paul puts it:

Visualize an application built up of many such main-line programs running concurrently, passing IPs around between them. This is very like a factory with many machines all running at the same time, connected by conveyor belts. Things being worked on (cars, ingots, radios, bottles) travel over the conveyor belts from one machine to another.isualize an application built up of many such main-line programs running concurrently, passing IPs around between them. This is very like a factory with many machines all running at the same time, connected by conveyor belts. Things being worked on (cars, ingots, radios, bottles) travel over the conveyor belts from one machine to another.

http://www.jpaulmorrison.com/fbp/concepts.shtml

If you look at the Programming Paradigms side bar on Wikipedia you'll see that functional and dataflow programming are both examples of declarative programming.  In declarative programming we tell the computer what we want instead of what to do.  As wikipedia puts it "languages applying this style attempt to minimize or eliminate side effectsby describing what the program should accomplish, rather than describing how to go about accomplishing it. This is in contrast with imperative programming, which requires an explicitly provided algorithm."

I'm now going to have a good rant about the functional programming argument.  You probably want to stop reading about now.  I just need to get this off my chest.

Functional programming only describes functions, computational processes that manipulate data.  The introduction to "Structure and Interpretation of Computer Programs" put's it best.

We are about to study the idea of a computational process. Computational processes are abstract beings that inhabit computers. As they evolve, processes manipulate other abstract things called data. The evolution of a process is directed by a pattern of rules called a program. People create programs to direct processes. In effect, we conjure the spirits of the computer with our spells.

A computational process is indeed much like a sorcerer's idea of a spirit. It cannot be seen or touched. It is not composed of matter at all. However, it is very real. It can perform intellectual work. It can answer questions. It can affect the world by disbursing money at a bank or by controlling a robot arm in a factory. The programs we use to conjure processes are like a sorcerer's spells. They are carefully composed from symbolic expressions in arcane and esoteric programming languages that prescribe the tasks we want our processes to perform.

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-9.html#%_chap_1

In functional programming we use computational processes, functions, that describe exactly what we want.  These functions are the strict, true functions of mathematics and not the crude subroutines of C or Java.  Given the same inputs a true function will always provide the same output.

A very sophisticated compiler or interpreter will then take those functional descriptions and then create some executable code that will produce the results you described.

The problem that I have with functional programming is summed up by the quote above.  It is not real.  Executing those programs is like magic.  This makes them difficult to understand for the majority of people.  Programming is an arcane art for the elite few.  Anybody can work in a factory, but only the seventh son of a seventh son gets to be a wizard.

Making these functional programmes executable requires all kinds of conjuring tricks.  Take, for example, tail recursion.

The HelloWorld of functional programming is always the factorial.  As Wolfram MathWorld explains: 

The factorial  is defined for a positive integer  as

(1)

So, for example, 

http://mathworld.wolfram.com/Factorial.html

The Java for implementing this is simple:

int factorial(int n) {

int result = 1;

for (int i = n; i>1; i--) {

result*=i;

}

return result;

}

After a couple of days learning the syntax, most people could work out what's going on.

This version is not functionally acceptable because "i" is a mutable variable, its value changes.  Instead it has to be a recursive approach.  In Lisp it looks like this:

(define (factorial n)

  (if (= n 1)

      1

      (* n (factorial (- n 1)))))

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1

There is no mutable "i" any more, instead the function just keeps calling itself.  In java it looks like this:

    int factorial(int n)

    {

        if (n == 0) return 1;

        return n * factorial(n-1);

    }

The problem is that this approach isn't practical.  It could use a lot of memory and if "n" gets too big then you'll get a stack overflow.  To solve this problem functional languages implement tail-end recursion, which means that the compiler will turn the functionally correct recursive code into the the actual real life loop we wrote above.  As SICP explains:

One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose ``looping constructs'' such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. 

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1

From the simplest example the code written and executed are different.  The programmer does not have to understand the machine, only the numbers.  The problem is that not everybody can understand those numbers.

That isn't supposed to be a problem because the clever PHDs all understand these things, being so clever, and we can trust them.  Personally, I don't trust them.  There is a history of trusting clever approaches turning out badly in finance: the CDO http://en.wikipedia.org/wiki/Collateralized_debt_obligation#Subprime_mortgage_crisis

Modern functional programming languages, like Haskell and Scala, involve something called a Monad.  I have no idea what a Monad is, and I've really tried to understand.  Many many people have tried to explain what it is.  It has been observed:

[I]t seems like every programmer who gets monads posts a tutorial about them. (And each post begins with: There’s already a lot of monad tutorials on the Internet, but...) The reason is that getting monads it’s like a spiritual experience that you want to share with others. (Bartosz Milewski)

http://www.haskell.org/haskellwiki/Monad_tutorials_timeline

Again with the spiritual and magical.  Did those people really get Monads?  Do they really understand them?  According to the Einstein test they do not: 

“If you can't explain it to a six year old, you don't understand it yourself.” 

http://www.goodreads.com/quotes/show/19421

I always come back to Paul's opening paragraphs, because to me they are so important:

A meeting is called of all the people involved - not just programmers and analysts, but users and operations personnel as well. The essential logic of the program is put up on the wall, and the program designers walk through the program structure with the group. During the ensuing discussion, they realize that two new modules have to be written and some other ones have to change places. Total time to make the changes - a week!

http://www.jpaulmorrison.com/fbp/intro.shtml

I've had the pleasure of this scenario on a couple of projects.  It's a wonderful thing.

When the success of the project is dependant upon complexities that cannot be widely understood the scenario is quite different.  

All the people involved get together and the non-programmers explain their concerns. 

Users: "We have this concern, blah blah blah"

Programmers: "I don't see the problem."

Users: "There is a problem, and we can't sign off until its resolved."

Programmers: "Ok, what do you need us to do."

Users: "You must do this and that."

Programmers (shrugging): "Sure.  If that's what it takes to put your minds at ease, we'll do it."

Users (uncertain): "Ok.  good.  Thanks for listening."

After the system is delivered the users come back and tell the programmers that there is a serious problem.

Users: "We told you this would happen and you promised to fix it."

Programmers: "No you didn't."

Users (showing minutes): "Yes we did, look."

Programmers: "We did what you asked, look here and there."

Users: "That isn't what we asked for."

Programmers: "Yes you did.  You have to understand that this means blah blah blah and that is just a specific example of the general principle of blah blah blah."

Users: "That isn't what we meant."

Programmers: "Well, maybe you should have said what you meant."

I've endured this scenario so many times.

The more esoteric and arcane the programming languages used the bigger the gulf between the programmers and users becomes and the more they fail to understand each other.

If you enjoy rants like this you might also like to read the following rant about implementing factorials: 

The smart Java developer would know when to stop. Life is too short to build castles in the clouds. He’d know that a simple looped solution is more than sufficient, and of course he handles negative numbers. (Note that in our recursive solutions, a negative number results in an endless loop.)

http://chaosinmotion.com/blog/?p=622

Regards, 

Ged

[Brad Cox]

My obligatory grumph against such inflamatory titles, with another view that offers much more hope (I think).

Did the introduction of card-level integration (by DEC if not before) mean the "downfall of chip- and gate-level integration"? Hardly, as the success of Intel abundantly shows. The introduction of higher levels of integration just meant broadening the market from the smaller components needed to build them, and the containerization (is that a word?) meant the complexity of working at the chip and gate level (comparable to C++) became much more manageable.

The only "downfall" in sight is the toxic notion that any one tool (C++) is sufficient, particularly when there's no obstacle at all to using them in combination. Except attitudinal, which I abhor.

On Monday, April 9, 2012 1:48:34 PM UTC-4, Henri Bergius wrote: