Turing machines have mutable state. The lambda calculus does not. Yet any algorithm which can be expressed by one can also be expressed by the other. We have proof that state is merely an implementation detail, which happens to be widespread in today's hardware because we figured out how to implement it at scale.
Programmers need to understand the difference between the abstract algorithm they're trying to express and the representation they've chosen (and the ones they didn't) inside the computers they're using, just as astronomers need to distinguish between the stars they study and the measurements coming out of the various telescopes they can choose.
Your hard-line stance is a little bit too far IMHO. That inanimate matter programming is all about manipulating also has no notion of objects or object orientation... or (for the most part) methods, fields, functions, procedures, arrays, modules, encapsulation, interfaces, garbage collection, databases ... and so on and so on. All that abstraction exists to make programming easier for humans to grok, and for teams to deliver some "useful work".
To borrow from Robin Milner, who worked on ML: "Types are the leaven of computer programming; they make it digestible." All that abstraction makes programming more digestible, or more palatable. Functional programming is just some more abstraction to make it more digestible. To say that it's a redefinition of programming is just a distraction, since programming has already been redefined.
Also, you're right that CS isn't programming, and viewed in a certain light one could argue CS is basically just a branch of math. But on the other hand, programming without CS really wouldn't be that useful. It's just not a helpful distinction to make in this way.
I would argue that objects, methods, fields, modules, encapsulation, interfaces, garbage collection, databases are not the basics of programming either.
Good things to have, but are not basics of programming. So, teach/learn them later in the cycle.
Basics of programming are variables, branches, arrays, loops and simple I/O. You can go a long way with these. And you can explain those to 6 yr old child.
Recursion is fundamental. Reassigning to a bunch of variables in a loop is a poor imitation of recursion that caught on because fifty years ago we could barely afford call stacks and hadn't invented tail call optimization. The better our hardware and our theory gets, the more of these shortcuts we can and should leave behind, so that we no longer need to try to preserve the illusion that programs run sequentially and state is globally consistent.
Everything we do in any high level programming languages is an illusion. In fact, even assembly language is an illusion. The only thing that isn't an illusion is building a computer out of nand gates, and the like.
In my education, we STARTED with functional programming, and eventually we built real microcoded computers that we designed ourselves out of nand gates and adder chips. And, yes, I mean REAL chips with lots and lots of wires on a real physical breadboard.
Is a nand gate, the fundamental building block of all computers, is that functional? You bet your ass it is! State only comes by using this functional component and feedback to make a flip-flop.
Your premises are all wrong: My education started with FUNCTIONAL programming. We then learned how to build OO on top of functional programming, using only closures and single mutation operation: variable rebinding. We then went on to design and build our own physical computers out of chips and wires, starting with the fundamental functional component: a nand gate.
You do not program nand gates. You program your cpu. Last time I've checked, it's not Reduceron II but instead AMD64 or ARM cpu. One which is inherently imperative - it's von neumann machine. It has registers, shared writable memory and stuff.
First of all, as I have mentioned, I have implemented programs using real nand gates, with my very own hands, using copper wires and microcode.
Furthermore, my CPU is made out of nand gates, so yes I do program nand gates every day.
If you deny this reductionism, then I deny your reductionism to the CPU. I don't program the CPU--I program the Scala compiler. My Scala code doesn't run on an AMD64, or an ARM CPU, it runs on ANYTHING, past, present, and future for which the Scala compiler has been implemented. In the future, my program runs on DNA or on neutronium Tinker Toys.
Traveling into the past, rather than the future, I have written Lisp code and then compiled it to microcode.
P.S. I don't trust the opinion of anyone who hasn't built a computer out of nand gates, as clearly they are out of touch with the hardware. Have you built your own CPU from scratch?
What I see in your comments is the constant stream of I's.
I, me, I did, I studied, I think this, I think that.
Guess what? Nobody cares that much except for you.
When talking about basics, we should consider the least common denominator of all programmers' knowledge.
You can reason that the basics should be different, but what if you are wrong? You are a smart guy who loves scala, but there are other smart guys who consider scala a failure, for example. And there are guys smarter than you and me who just do it all in C because they can't be bothered with abstractions, and FP is an abstraction in the end.
People are different, and if you think that you're such an unique yet the most important snowflake - why?
Nobody questions your ability to write successful FP code. So what? What does it prove? Nobody even questions that.
But there are people who write FORTH. And there are people who write Prolog. Both groups claim they get much bigger bang for the buck than anyone else. Why do we listen to you and not them?
You keep expressing your opinion. Please tell me how there is no "I" in your opinion. I see two of them: o-p-I-n-I-o-n.
Also, I never said not to listen to any of these other folks. It was you who told me that I didn't learn to program in my first programming class because it started with functional programming as the most fundamental concept. That statement was offensive and false, and I am now demonstrating to you why you are so wrong.
This is not to say that there are not many possible reasonable approaches. I think the one I learned was great. Are there better approaches? Who knows? Certainly not you.
SICP is overrated to whom? For me, it was the most profound and wonderful educational experience of my life. I found it to be profoundly inspirational and educational. I found it to be beautiful, uplifting, moving, rewarding, and just incredible in all sorts of ways that I cannot even begin to express. And it pumped up my joy of learning in a way that survives to this day, decades later. There are not enough words in the English language for me to express how much this course meant to me and how much intellectual joy it provided me.
Of course, YMMV.
As to what I should and should not do, who are you to tell me that?
Mathematically, immutability is more fundamental than mutability, as the mathematical models for computer programs all model mutability in terms of immutability.
Pedagogically, either approach seems to work. Which one is better? For me, the functional approach was FAR superior. The best pedagogical approach is almost always the one that is the most inspirational, and SICP truly inspired me. I found it to be beautiful, whereas I found the more traditional approach to be merely workmanlike.
Having received both kinds of education, I'm qualified to say which worked better for me. Is my experience representative? Well, lots of people who have learned via this approach seem to agree with me. Zillions of people LOVE SICP. On the other hand, zillions of people swear by imperative approach. The best approach then might vary from individual to individual. There may be no one-size-fits-all education. But I suppose that we cannot rule out that future education researchers might show that on average one approach is better than the other. The Logo people claim to have done such research for children, and they settled on the functional approach. But children are not adults, and I'm sure their research did not reach the level of proven fact.
As to which approach results in engineers who produce the highest quality software, I believe that having a deep understanding of the functional approach results in higher quality software, and the best way to acquire such a deep understanding is to start with it from the very beginning. I am not prepared to prove this assertion, but neither are you prepared to prove its contradiction.
As to which approach is closest to the hardware du jour, who cares? That has nothing to do with anything, unless you are writing in assembly language. I will point out, however, that today's hardware comes with multiple cores, and this tend is only likely to increase. Functional approaches to programming result in very natural extension to multiple cores, while with imperative styles, not so much.
If we were talking about teaching programming to kids, I actually agree with you. It wasn't clear from the top-level comment that started this thread if that's what we were talking about though. I thought that we were talking about intro to CS for freshmen in college. That's where I think it might be valuable to start with functional programming. Note: might -- I really don't know.
"People should be required to learn the basics of programming first. They should start with immutable data objects"
We weren't talking about freshmen in college. And talking about freshmen in college is not so interesting because they agreed to listen to bullshit (information of questionable utility) by joining college.
It's much more interesting to talk about kids or adults because they have the choice.
It's used to do all sorts of interesting things, including real economic modeling. I.e., I've seen it used by real economists.
When I first saw NetLogo being used by an economist to demonstrate an economic model, I thought it strange that the NetLogo people had re-used the name "Logo", a kid's programming language, for something that is a serious tool used by professional researchers. It took me a while to figure out that it is the same Logo! And those kids, I guess, grew up, and decided to do something real with it.
R is also a functional programming language used to do very real work.
The inventors of C++, Java, Perl, Python, Erlang are trying to solve problems basic to many other domains. So it depends on what you define as basic. What you seem to define are pre requisite to start learning basics.
Programmers need to understand the difference between the abstract algorithm they're trying to express and the representation they've chosen (and the ones they didn't) inside the computers they're using, just as astronomers need to distinguish between the stars they study and the measurements coming out of the various telescopes they can choose.