I have little real background with computer programming. Played around with BASIC and Pascal in high school, played around with Python a few years ago. I understand the idea of object oriented programming. I’m saddled with imperative habits.
For funsies (and maybe for job skill purposes someday but mostly for funsies) I’m working on learning a new language. The one I zeroed in on was Scala, which you may have opinions about but what I’m asking about is something specific that keeps coming up when people talk about good Scala style. (This may be just what’s considered good style in general, I don’t know).
And that’s the idea that immutable variables are the very best variables. Mutable ones are bad.
My question is two-fold:
Just, why? I read that it’s easier to think about programs when they minimize mutable variables, but I’m not grasping why that would be and no one ever really gives examples. Can you explain?
I am told that ideally one uses no mutable variables, and that they’re never necessary. I believe this. But I don’t understand it. For example, take a tic tac toe program. Things change as the game proceeds. How could it possibly be possible to model this without mutable variables somewhere? Something, somewhere, it seems to me, needs to be mutable–whatever it is that pulls off the task of assigning positions to X’s and O’s. When that position is assigned, something that was “empty” before now has an X or an O in it. That’s… mutation, so to speak. Change. How could this be done without a mutable variable somewhere?
Please explain it like I’m five. I’ve only been at this for a couple of weeks, and that only for an hour or two a day. If I have to stop you and tell you I don’t know about some element of the language or other that you’re referencing, apologies in advance. But I’m hoping this question can be answered at a more abstract level that doesn’t need reference to particulars of the language.
ETA: Concerning that tic tac toe game, I mean, I can concieve of a ludicrous way to do it that involves writing a ton of code accounting for every possible board state but of course that’s not the right idea.
I’ve never heard of mutable variables before. Do you mean variables that can assign new values to? If that is the case, then there are better names than mutable and immutable variables: variables and constants.
The objection to variables is that the resultant code is likely not to be reentrant, meaning that you cannot reenter a program while running an instance of it. Now reentrant programs can be useful, but there is no way you care whether a tic-tac-toe program is reentrant. I wonder this language (which I have never heard of) is a functional programming language, q.g.
And for the record, one way of avoiding variables is to use a stack. I have a fair bit of experience with Forth and that uses a stack extensively and you could, in principal, avoid variables. But unless you set up several stacks, you could spend a lot of time manipulating the stack. I didn’t use variables, but instead used mutable constants, but that is another story.
Well, first off, note that “mutability is evil” is a bit of the functional programming Kool-Aid in the same way that “free functions are evil” is part of the Object Oriented Kool-Aid. To some degree you can work in either mindset, but it often complicated things that don’t need to be complicated.
First let’s start off: is mutability ever needed? No, this is provable – look up untyped lambda calculus. It’s a stateless equivalent of the Turing Machine. What about practically? Well, for modern computers you need some state to interface with things like I/O and networking. That’s why Haskell has Monads, which exist as a way to introduce state into a functional environment (that’s the super simple explanation).
Let’s go to your Tic-Tac-Toe example. Do you need mutable state? NO!
Consider some empty board. Now draw an “X” in the middle column, top row.
Clearly you have to now change the state of this “board” to contain an “X” in this position, right? No, return a NEW board – a successor state that looks like the old board but with the X in that position. In this way you don’t have variables, instead of having a variable called “x” that was 1 and is now 2, you instead have x, which is always one, and adding 1 to it creates some new variable x’ that holds 2.
Note that minimizing state is a goal even in a lot of OOP. If you read OOP books they’ll talk about “minimizing function ordering” a lot. This means that code like:
x = new TransformingCar()
x.PutIntoAirplaneMode()
x.Fly()
Is bad, because flying is (presumably) tied into the car transforming into a plane. Either the transformation should return a Plane object, or Fly() should implicitly transform the Car, or something like that. Because otherwise it causes confusing “boilerplate” issues; where you have to remember what set of arcana is required to make a function run without crashing your program.
Of course, this sort of thinking can go too far, but treating objects as state machines is a cause of a lot of bugs. One “degenerate” case of this is the likes of OpenGL – a very powerful library, to be sure, but one explicitly designed around a state machine, in such a manner than that you have to remember all sorts of glBegin and glBind<whatever> calls to get anything done.
Note that this even works with functions – functional languages have higher order functions: functions that return functions. The exact rules vary from language to language, but you can make a function return a function that has some value held constant in a different way, this is essentially a way of having “state” without actual state; just successor functions.
Consider a value function:
f: int
Value() = c
Where “c” is some constant. Calling it always return “c”.
Now consider the higher order function “Succ”
f(f: int) -> f: int
Succ(Value) = [NewValue = Value()+1]
That is – it takes in a value function and returns the value function which returns a value one greater than the old value function.
Oddly enough, I do have an opinion on Scala. I like it. In fact, I just finished the first Coursera course on it, and my GitHub is about 1/3 in it.
What Scala attempts to do is blend a Java-like syntax, with the concepts of Functional Programming (i.e. the Lisp/Haskell/Clojure tradition of programming) to obtain something with the advantages of both. The “no mutable state” idea comes from the functional programming side of the language.
One important aspect is called referential transparency, which is the idea that if you call a function twice with the same parameters, you must get the same result every time. This allows you, when reasoning about code, to simply replace a function call with its result every time, which is critical in formal proofs of correctness. A “val” is essentially the same as a referentially-transparent function that returns a constant – code that accesses a val doesn’t know that it is not calling a function (and in fact, in Scala sometimes it is calling a function under the hood) so it has the same logical guarantees. A “var” is not referentially transparent, so the guarantees are not met and you have to think more closely about how it is used to reason about it.
If you are avoiding mutable state, what you end up with a bunch of classes and methods that in other languages one might expect to cause mutations, that instead return modified copies of the original object. For example in Java, one might have:
Set<Integer> s = new HashSet(); // s is now an empty set
s.add(5); // s now is non-empty
Whereas the equivalent in Scala would be:
val s = new Set[Int] // s is now an empty set
val s2 = s + 5 // s is still an empty set, but now s2 is a non-empty set.
For your Tic-Tac-Toe example, it might be reasonable to define your board position in terms of a map:
type TTTBoard = Map[Pair[Int, Int], Char]
val emptyTTTBoard = new Map[Pair[Int, Int], Char]
So the boards are maps from pairs of position coordinates, (i.e. (0, 0), (1, 0), (2, 0), (0, 1) … (2, 2) ) to the character written at that position (i.e. either ‘x’ or ‘o’ or if nothing is in the map for that position, empty).
From there, there are two natural functions to define. The first tells if a board has been won. Determining this does not alter the state of the board in any particular way:
def hasBeenWon(board:TTTBoard):Boolean = {....}
And another function, given a board and an indication who which character is to be placed next, decides to place a character on the board. This is something that one might expect to be a mutating operation, but as good functional programmers, we will make the operation return a new board, rather than mutate the old one.
Given those two functions, we can start making the code that plays the game. In places where other languages would use loops (and have to have a var to contain the loop counter), functional languages use recursion. To apply this, we can write a function that “continues” a game from a given position, knowing whose turn it is. For definiteness, lets say that this function returns the winning board, and the player who won in a Pair.
def continueGame(board:TTTBoard, whoseTurn:Char):Pair[TTTBoard, Char] = {
// Get the next position.
val nextBoard = nextMove(board, whosTurn)
// If that move won the game, return the board and winner.
if (hasBeenWon(nextBoard)) { (nextBoard, whosTurn) }
else {
// Otherwise, continue the game with the updated board and the other
// player
val nextPlayer = if (whoseTurn == 'x') 'o' else 'x'
continueGame(nextBoard, nextPlayer)
}
}
Given that, we can play a full game by just “continuing” from the empty board:
Tic-tac-toe is a great example. It may work in a simple example, but to scale the analogy up, in the real world you have to implement something like a chess game and trying to return it in a new complete state after every move is gonna blow your processor up.
As a 30+ year professional developer, I’m always amused by the “academic” languages. Is it really that strange that languages whose main draw is that they forbid some common and useful feature never gain mainstream acceptance?
Sure, it’s useful to know how to operate under constraints to pass some arbitrary programmer purity test, but ultimately I choose my tools to give me a breadth of abilities, not to keep taking them away until everything looks like a nail. Which is why large, real-world system programs not written in some C-class language are effectively non-existent, still. [Except for the web, which has embraced the scripting languages with a passion: most of which still pretty much look like C.]
Never used Scala but I am familiar with C++ and it has mutable, I’m guessing it’s similar. So at least in C++ you can mark a member function as being const. That means it’s not supposed to change the contents of the class/object. But if you declare a member variable as mutable then it’s an exception to that and a const function can change it.
So that becomes the big question. Why did you declare this function const(can’t change stuff) and then turn around and let it change stuff with mutable? Usually if you’re doing that you actually meant it to not be const in the first place. Plus if any developers use your class and they see a const function they’re going to think “It’s const, it’s not going to change stuff.” So the general rule of thumb is don’t use const because either you really don’t want a const function or you do and you made a mistake and you can do what you want to do with out changing stuff.
Actually reading about this I did see an explanation of why you might use const, debugging variables. The variables themselves don’t change the functionality of the class per-se but need to change for whatever reason to keep track of information that may be necessary later on if there are bugs.
I dunno, ANSI Common Lisp has mutability (setq and setf; builtin lists and tables), but it’s not really conducive to a highly-mutable style of programming (note that this is true of most functional programming languages – they provide mutability hacks for when you need them; Monads and whatnot). Big apps have certainly been written in Lisp.
Edit:
Well “immutable” to the programmer is not “immutable” to the language. Functional language use mad optimization hacks. When you return a “new” Chess board, under the hood it’s probably just mutating the old one. It’s just like saying writing only in recursive functions would blow up your stack. If you’re thinking in C, yeah, but Haskell/Scala and the like don’t really grow the stack when your tail recurse.
Scala (and Haskell, and other functional programming languages) have pioneered the concept of fully-persistent data structures. These are data structures for which modifications preserve previous versions of the structure.
For example, in the Scala code:
val s1 = big_set_of_int
val s2 = s1 + 5
val s3 = s2 + 10
val s4 = s3 + 10
s1, s2, s3, and s4 all still exist. But that doesn’t mean that the original set s1 needs to be copied in its entirety three times just to be modified to make s2, s3, and s4 – the three created sets share most of their structure with s1. In general, all but log(s1.size) nodes are shared between s1 and s2, and s2 and s3, and all nodes are shared between s3 and s4. In terms of complexity, an insert into a persistent set takes the same amount of time as a mutable set (but naturally also takes log(n) additional memory to hold the nodes not in common).
These kinds of data structures were developed for functional programming, but have seen new interest recently because in multithreaded applications, they can be used to efficiently eliminate the need for a lot of locking and defensive copying, which improves performance considerably.
Mutable state isn’t that bad when you’re writing sequential programs. It’s when you start trying to do things in parallel and you have multiple threads trying to read and write the same values that you really start to appreciate the benefit of stateless programming.
The usual reason for using mutable with const is to allow for lazy initialization or caching of results. I.e. if some method “int foo() const;” could take a long time time execute, and might be called several times, but might also be never, you might want to make a field “mutable int foo_result_m”. When foo() is called, it checks to see if foo_result_m is set, and if it is just returns that, otherwise it does the long computation, sets foo_result_m to it, and then returns the result.
The object is still semantically constant (i.e. foo() and will always return the same result), but the the mutable foo_result_m improves performance, and it needs to be mutable because setting the lazy result is technically a physical, but not a logical mutation.
And caches are similar, just a little more complex.
In particular, the ITA flight search system is written in Common Lisp. Basically, every time you use Orbitz or Kayak or CheapTickets or a dozen airlines’ search engines, you’re actually shelling out to ITA which is running your query in Lisp.
As for Scala, it is the backbone of Twitter and LinkedIn. Hardly an obscure academic language.
The other option is Actor and CSP models like Go and Erlang have (Erlang is functional, but I don’t think quite in the anal way Haskell and Scala are; there’s some state and looping and stuff in it). Erlang was originally used to write highly parallel phone routing software.
I have this feeling, and one instinct I have is just to ignore these claims until something comes up that makes it seem necessary to finally start thinking like these guys. But I have this intuition that, though that strategy often works when dealing with mysterious claims made by non-pedagogically-oriented people, in this case by “continuing along in my own way” I’m actually making it harder for myself to “catch on” later on. Just an intuition, though. But it makes me nervous.
Okay but that sounds a lot like the suggestion I made at the end of my post that I considered ludicrous–encoding the board simply as a series of variables each of which corresponds to one possible configuration on the board. I’d need three to the power of nine variables! (Right?) How is that tractable? And THEN, of course, this doesn’t even solve the problem of how I say which of those values represents the actual state of the board without… something mutable…
I mean, I imagine not each variable needs to actually be created, just the ones corresponding to states that actually come about. Okay, but even so, how can I tell the program to treat the new variable as replacing the old variable? I guess to me that sounds just like literally saying the old variable “really is” a mutable variable.
As you can see I’m really stuck in a way of thinking here, I think.
Unfortunately, despite your english-language explanation afterwards, I’m having trouble parsing the second bit of (pseudo?)code here, and so don’t quite understand how it’s supposed to work (as opposed to what it’s supposed to do).
What do you mean by the arrow? Where did NewValue come from? How would one refer to it from outside the function? Arg, sorry. If you do keep trying to help me out here, I appreciate it, and I promise I can think like this I am almost certain, I just haven’t quite figured out what you guys are up to yet.
It’s not a coincidence that garbage collection was invented for Lisp – it really makes all of these things a lot simpler. If you’re interested, the standard book on the topic is Purely Functional Data Structures by Chris Okasaki.
Also, on the same pretext, I’m going to show off my fully-persistent priority queue implementations.
[QUOTE=Jragon]
The other option is Actor and CSP models like Go and Erlang have (Erlang is functional, but I don’t think quite in the anal way Haskell and Scala are; there’s some state and looping and stuff in it). Erlang was originally used to write highly parallel phone routing software.
[/QUOTE]
I’d hardly call Scala “anal” in the functional way. Anything you can do in Java, you can do in Scala, but most people who are interested in Scala are interested in the functional aspects. (Haskell is, of course, crazy anal about the FP)
You might be interested in Akka, which is a Scala package/platform that implements an Erlang-like agent model.
That makes sense. It’s not something I’ve had to deal with at this early stage, but as you’ve described it I can see how this would be important.
This is what I don’t quite get. You have to be able to refer to the modified copy as though it were the “same thing” as the original, which I can see how I could do that for any single instance, but if there’s a potentially infinite number of times this might be done within a single run of the program, I don’t see how I could code for that ahead of time.
Here’s what I mean. Suppose I want to have a function that, every time I call it, it simply adds one to a counter value.
var c = 0
def count() = {
c +=1
}
count()
count()
count()
println(c)
If I did that right, it should give me “3” when I run it.
I cannot see how I could write an equivalent using only vals, which allows for any number of "count()"s at the end, and gives me the equivalent output for the final println. And what keeps me from being able to see this is my inability to know what I would put in the parentheses after “println”–it can’t be c because c, being a val, won’t be the name of the value that needs to be printed. But sitting here prior to any actual running of the program, I have no idea what that name will be, because since my new function will need to return a “modified copy” of c instead of c itself the FIRST time it’s called, then a “modified copy” of that NEW value the NEXT time its run, and so on, and each of these “modified copies” will need a new name, and I don’t know ahead of time how many times this will be done, this means I have no idea what name I’ll end up with!
Do you see how basic and completely uncomprehending my problem is here? I know what is probably happening here is I’m thinking in BASIC.
I will have to study your example, thanks for providing it. Maybe it will kick me in to what I need to be kicked into.
Have you ever dealt with video codecs (or even source control like git)? There’s something cool called delta compression. The idea is you have a set of "key"s – whole pictures. So if you have a 1080p video, that’s 1920*1080 RGB values. This is why video is so big.
So how does lossless video compression work? Or even video streaming? Well, you don’t need every frame to be a key. You can just scan over the pixels that changed from last frame and store a list of the pixels that changed and their deltas – the change in RGB value. Of course, sometimes the frame radically changes, so instead of a delta it will include it as a new key – because at a certain critical mass it’s better to just load an entire frame instead of doing 1920*1080 (minus some small number) additions. (And for streaming, sometimes it’ll throw in a new key at regular intervals in case something screwed up in the transmission).
As far as I can tell from earlier posts in this thread – this is how Haskell and the like encode data state – as a set of deltas. They only encode as much as they have to, and the rest with a pointer to some shared (immutable) state up a tree.
Sorry, the notation was a bit brain damaged and inconsistent. It was ad hoc but by the time I saw the inconsistency it was too late to edit.
