Doesn't mutability force you to actually copy data? Immutability enables sharing, which needs less copying.
(Of course what it really comes down to, is whether you use multiple different copies of your data structures. If you only ever use one, even functional languages can update them in place. See Clean's linear types as an example, or Haskell's ST monad.)
Mutable objects are there so that you don't have to create new instances whenever a field changes. The danger of shared mutable objects is that the ground can change beneath your feet.
Immutable objects enable safe sharing, however, if you have an immutable object and want to change it, you have to copy it and make the change during construction of the new object.
I guess the 'copy penalty' in either case depends on the size of your objects.
If your compiler is smart enough (i.e. you are programming in clean, or use Haskell's GHC) the `copy penalty' can be zero for objects that only have "one future", i.e. you only ever keep one copy of your structure. (And that's still cleaner and safer than mutable structures.)
The `copy penalty' for multiple uses of your objects, say a = update1 (x), b = update2 (x), does not depend so much on the size of your object as one the amount of sharing you can do. Immutable objects allow sharing. For mutable ones you have to work much harder.
The machines that we deal with are mutable as hell (unless we see time as an implicit argument ;)). Most early languages were thin abstractions from machine code, and the world kind of built from there.
Ah those were the days when computers hardly had enough memory to even keep the Haskell standard prelude in memory.
Immutability doesn't necessarily require copying data all the time though if you copied data only when modified and used the right data structures, does it?
The Haskell 98 standard prelude is 39 kb big. Computers with less RAM than that were in use in the early 1980s. Since you're obviously an engineer by training, you may now ask why somebody would try to load an Haskell prelude in the early 1980s on a computer that isn't even capable of running a Haskell programme.
Anyway, I guess what I actually wanted to say got lost in the space between.
Actually, I'm wondering what Haskell has to do with any of this at all.
You're comparing the size of the current incarnation of a fairly modern functional programming runtime with the capacity of computers that existed 10 years before the first incarnation was realised...
The only message I can take from that is that programs today are quite big. That's only really interesting from a nostalgic point of view, I don't see what relevance it has to the discussion of mutability?
Of course, I could have missed something obviously significant here...
The parent poster was talking about immutability, "the early days" and copying data. I think my point was that you don't have to copy data all the time but this requires a clever interpreter/compiler that you could not have run "in the early days".
I'd also like to use the opportunity to say that I find those OOP vs FP posts at HN rather pointless.
Actually, today's hardware, with multiple cores/CPUs clashing over shared memory through non-shared cache, is less friendly to mutability than the old systems.
Immutability does require different data structures; a (singly-linked) list is easy to make immutable in most cases -- many lists with the same tail part can share that tail, without copying when a new list starts sharing that tail. Arrays, not so much.
Unless the list elements can be thunks that can be evaluated when necessary or appropriate. See for instance Control.Parallel.Strategies in Haskell, which provides amongst others 'parMap' (parallel mapping over lists).
I think that's a too blanket statement. What do you want to do with the list, a map or a fold? In the former case, what is the cost of the function application?
Please have a look at Guy Steele's talk (http://www.vimeo.com/6624203). Basically he suggests using tree-like data structures, instead of linear data structures. You can also map, fold and filter over trees, but it parallelizes better.
Quite a superficial post. The Alan Kay quote is well-known, and it only touches upon mutable vs immutable data. Purity alone does not define functional programming, since there are plenty of counter-examples (Erlang, Lisp, OCaml).
The purpose of functional programming isn't to eradicate mutable state as if it were criminal. Mutable state is necessary. It's to control mutable state so that it's easy to determine where state is and how it is expected to behave. The problem with state is that if the architecture is sloppy and it's all over the place, it can lead to impossible-to-reason-about program behavior, especially when the rules that govern the state have been written emergently by several parties over years. Mutable state is a flower in the right part of the garden and a weed in the wrong part of it.
Haskell takes the most extreme approach of the mainstream languages, which is to segregate mutable state entirely into monads (e.g. IO, STM). Ocaml does this in a more practical way: some types (e.g. arrays, hashtables, records with mutable fields, ref cells) are mutable while others (e.g. linked lists, tree-based associative maps) are constitutionally immutable. Common Lisp really isn't "purely functional" at all; it provides the tools necessary to write functional code, but it also has methods like NCONC and RPLACA which allow in-place modification of cons cells, put into the language for historical reasons.
The venerable master Qc Na was walking with his student, Anton. Hoping to prompt the master into a discussion, Anton said "Master, I have heard that objects are a very good thing - is this true?" Qc Na looked pityingly at
his student and replied, "Foolish pupil - objects are merely a poor man's closures."
Chastised, Anton took his leave from his master and returned to his cell, intent on studying closures. He carefully read the entire "Lambda: The Ultimate..." series of papers and its cousins, and implemented a small Scheme interpreter with a closure-based object system. He learned much, and looked forward to informing his master of his progress.
On his next walk with Qc Na, Anton attempted to impress his master by saying "Master, I have diligently studied the matter, and now understand that objects are truly a poor man's closures." Qc Na responded by hitting Anton with his stick, saying "When will you learn? Closures are a poor man's object." At that moment, Anton became enlightened.
Immutability is obviously not the same thing as encapsulation and polymorphism, which are what the Qc Na koan is about, but I don't think it "has nothing to do with" encapsulation and polymorphism either. They are both useful techniques for increasing the expressivity of the runtime state of your program, and I think they complement each other nicely. For example, immutability almost absolutely requires garbage collection or other automatic memory management, since deallocating an object is at least conceptually a mutation of its state, and there's a similar but weaker synergy between encapsulation and GC.
I was talking about the content of the actual article linked, though. It bugs me when the highest rated comment in a discussion is a copy-and-pasted blurb from something that is only tangentially relevant.
As long as we're veering off topic, I think it's interesting to consider Erlang in light of Alan Kay's ideas about OOP: While people coming from a C++/Java-ish background likely wouldn't recognize it as any kind of OOP, it's arguably MORE so than those: It's more directly based on encapsulation (via processes) and message-passing, without all of the "x IS-A y" conceptual baggage that comes from their mix of static types and OOP. It also has pervasive immutability.
The pros and cons of different styles is another discussion entirely. This is about judging how 'OOP' something is, so it's probably most fruitful to compare it to its original definition rather than to the derivatives it inspired. Hence Alan Kay.
Alan Kay invented the term "object-oriented programming" to describe what they were trying to do in Smalltalk. It's irrelevant whether Simula-style programming is better or worse than OOP; we're just discussing whether it's equally OO, which is a question about what definition we are choosing to accept — a semantic question, not a normative or factual one.
Yes, he most certainly did. Simula had objects, but it was not object oriented, objects were not the core abstraction everything was built upon. That didn't come until Smalltalk which is why Smalltalk is the defining language for the term object oriented.
Actually, your personal staste has a lot to do with it, since you've picked Alan Kay's/Smalltalk as the de facto definition of oop.
While you may prefer Alan Kay's definition, it is only a subjective one. It was not the first one and it is not the only one, so dismissin Java as less oop than Erlang is premature.
Yes and no -- closures are a tool to provide a behavioral view of state which is environmental in imperative languages. A closure is a set of state, presented as a function, with behavior provided by that function. In an immutable world, a closure can implement a setter which returns a new function closed over the new value.
Objects, on the other hand are... a tool to provide a behavioral view of state which is environmental in imperative languages. An object is set of state, presented as a data structure, with behavior provided by fields in that data structure (one view) or by the way in which functions taking that data structure as an argument dispatch on its type (another). In an immutable world, such an object would have methods which return a new object with some modification made.
Without some mechanism (these are two) to wrap up related state into a passable/returnable datum, its hard to talk about dealing with such state being made immutable.
In other words, I don't think there's anything particular to OO about the mutable/immutable point the article is making; the important distinction is between operations on data structures vs. operations on the environment. The article is thus too hung up on objects as somehow `different' when it comes to immutability, but I don't think they are.
As a side note, for an example of an OO language more recent than Smalltalk which favors objects with immutable operations, look at Scala or Ruby.
Quite correct -- sorry for the confusion; I misremembered the quote's original attribution, and didn't catch my mistake when looking up the link.
I suspect that in another few decades, GLS will, with Alan Perlis, Don Knuth, and perhaps Edsger Dijkstra, begin to take on the CS equivalent to the pop cultural role now played by Mark Twain, Abraham Lincoln, and Ben Franklin -- a figure to which half-remembered quotes or anecdotes are routinely ascribed.
But that's no excuse for my own half-memory here. Thanks for the correction.
People always half quote Kay on C++. He says "I came up with the term object-oriented, and I can tell you I did not have C++ in mind", but if you listen to the actual talk this comes up in, he immediately follows with (slight paraphrasing here) "Of course I'm not sure I had smalltalk in mind either"
"Object-oriented programming" seems to have a "blind man and the elephant" problem. People differ radically in their opinions of it based on what they think "OOP" is. The problem with OO as commonly practiced is that it encourages the promiscuous, distributed proliferation of mutable state. Sometimes this is the right model, especially when involving processes that might be on separate machines, but not usually.
For example, you can write a Die class with a sides field (integer), a topFace field (integer) and a roll method that sets the value of topFace to a random integer between 1 and sides, inclusive. To use the Die, call roll and getTopFace. Want to roll 5 d10s? Then create Die(10) five times, then call .roll and .getTopFace on each of them. By the way, you now have five pieces of mutable state in your program and, if you ever forget to call .roll and only call .getTopFace on your dice (maybe you've been tempted to keep the Die objects around for "efficiency") you get erroneous results.
Clearly, that's the wrong way to solve the problem. It's better to just call (rand 10) five times: in general, you only care about the results of the rolls, not the "dice". (This approach still isn't "purely functional" as written, because it still uses a randomizer, e.g. state, but it's close enough for most purposes. Passing around a PRNG state is pretty heavyweight.)
Sometimes you need the full power of pi-calculus (communication, message passing) but usually you want to stick with lambda-calculus (referentially transparent computation) as far as you can take it. Mutable state is almost always necessary at some point, but you want to segregate it as much as you can.
Seems to me this post is based on a misunderstanding of the Alan Kay quote. Kay wanted to minimize the role of _assignment_, not mutability. So instead of saying things like a=f(a), you say a.f(), where the method f simply mutates a in place. At least, that's how it sounds to me.
Assignment and mutability aren't quite the same thing, but they're pretty close. If a.f() has the effect of mutating the internal state of a, how does that occur? By assignment!
In Smalltalk, there's a fairly common pattern of immutable objects. Their state is set when the object is created and then never changed. There might be getter methods, but there are no setters, and in fact the only method that makes assignments to instance variables is the initializer. It's not hard to see how that could be extended from "fairly common" to being a fundamental part of the language.
I think you misunderstood the quote. Specifically, "even if presented figuratively", and "Many programs are loaded with “assignment-style” operations now done by more expensive attached procedures".
Setters are assignment-style operations, and a.f() is an attached procedure.
Also, in http://www.c2.com/cgi/wiki?AlanKayOnMessaging you can see "[I realized] that assignments are a metalevel change from functions, and therefore should not be dealt with at the same level - this was one of the motivations to encapsulate these kinds of state changes, and not let them be done willy nilly"
To be quite candid I forgot that there are languages that use the equal sign as both equality and assignment depending upon context. VB I think does that.
The CS department at the Ohio State University built their own language on top of C++ called RESOLVE/C++. A lot of students absolutely hated it, but it introduced a pretty awesome paradigm for working with objects: swapping.
If a function needs to operate on an object, rather than messing with pointers or copying the object, the function instead "swaps" the object with an initialized object. The function's "contract" specifies that it "consumes" the object that is passed in, so in code that calls that function, it is apparent that it better copy the object if it needs to access it again.
I think this provides a nice paradigm for allowing for immutability without excessive copying. The only functions that actually modify objects are the object methods themselves.
The RESOLVE/C++ language has been around for well over a decade, but it hasn't garnered much interest outside of academia. It's a shame, because it's a reasonably high level language that allows for mathematical proofs of correctness while still compiling down to machine code.
I think with languages like Haskell, ML, Coq, ACL2 and their ilk, you're not going to get a lot of traction for theorem proving in an OOP-ed C++ variant. The first two do compile to machine code, and have type systems that better lend themselves to theorem proving. I'm not sure if C++ OOP is formal enough (or generally accepted as such) to be a strong contender in theorem proving.
An ex-girlfriend of mine was in the CS program at OSU and I helped her out occasionally with her homework and as such spent many nights pulling my hair out and cursing the name of whomever created RESOLVE/C++. The algebraic proof side of things was so poorly documented and designed that it was effectively impossible to use for its intended purpose, and the macros for things like simple comparisons were just excruciating. I've dealt with many languages, but RESOLVE/C++ is in the elite group which I found absolutely no upside to. I really don't understand why it's still in use.
FP ~ Math/Formal Logics. OOP is a grab bag of theories, ideas and their applications to programming. Unfortunately I don't think that there's a generally accepted formal notion of what OOP actually is. On the other hand, functional languages, while there's some variance, all borrow from the same core principles. Moreover, feature parity in functional languages is a lot more clear in FP than in OOP. Terms such as "pureness" have a well defined meaning.
This is by no means a dogging of OOP. I personally think OOP seems to be better suited for practical business computing. Also FP, tends to have a higher learning curve (ex. monads) such that people of the street and in many academic programs gravitate towards the OOP paradigm. I think this could say something about how natural it is to use OOP, or maybe it just says something about how everybody is taught that programming "should be" (imperative vs functional).
I've read some of this and it's good stuff. I guess where I was coming from was that OOP is already so scatter shot and widely used as such that even if somebody did formalize something based on OOP, it wouldn't be generally accepted as "the OOP standard". So many people have an idea of what OOP is based on the language they've used, and I doubt that if somebody formalized OOP tomorrow that everybody would rush to make their languages compliant to the model.
That being said, I suppose that a solid new language with formalized OOP models that was very useful could become the next Java/C++. Time (and marketing) will tell. I would be very excited about such a language >_>.
"Object interfaces are essentially higher-order types, in the
same sense that passing functions as values is higher-order.
Any time an object is passed as a value, or returned as a
value, the object-oriented program is passing functions as
values and returning functions as values. The fact that the
functions are collected into records and called methods is
irrelevant. As a result, the typical object-oriented program
makes far more use of higher-order values than many functional programs."
I think Java and C++ et. al. get it wrong by overloading the . operator. On one hand it means "gimme this field of that object", and on the other hand it's "find this function in the method table of the class". These are completely different things. And it all goes downhill from this mistake.
60 comments
[ 2.7 ms ] story [ 110 ms ] thread(Of course what it really comes down to, is whether you use multiple different copies of your data structures. If you only ever use one, even functional languages can update them in place. See Clean's linear types as an example, or Haskell's ST monad.)
Immutable objects enable safe sharing, however, if you have an immutable object and want to change it, you have to copy it and make the change during construction of the new object.
I guess the 'copy penalty' in either case depends on the size of your objects.
The `copy penalty' for multiple uses of your objects, say a = update1 (x), b = update2 (x), does not depend so much on the size of your object as one the amount of sharing you can do. Immutable objects allow sharing. For mutable ones you have to work much harder.
Immutability doesn't necessarily require copying data all the time though if you copied data only when modified and used the right data structures, does it?
I think the issue of mutability in OOP vs FP pre-dates that.
Anyway, I guess what I actually wanted to say got lost in the space between.
You're comparing the size of the current incarnation of a fairly modern functional programming runtime with the capacity of computers that existed 10 years before the first incarnation was realised...
The only message I can take from that is that programs today are quite big. That's only really interesting from a nostalgic point of view, I don't see what relevance it has to the discussion of mutability?
Of course, I could have missed something obviously significant here...
I'd also like to use the opportunity to say that I find those OOP vs FP posts at HN rather pointless.
Immutability does require different data structures; a (singly-linked) list is easy to make immutable in most cases -- many lists with the same tail part can share that tail, without copying when a new list starts sharing that tail. Arrays, not so much.
(This only bites you when your lists get long.)
Haskell takes the most extreme approach of the mainstream languages, which is to segregate mutable state entirely into monads (e.g. IO, STM). Ocaml does this in a more practical way: some types (e.g. arrays, hashtables, records with mutable fields, ref cells) are mutable while others (e.g. linked lists, tree-based associative maps) are constitutionally immutable. Common Lisp really isn't "purely functional" at all; it provides the tools necessary to write functional code, but it also has methods like NCONC and RPLACA which allow in-place modification of cons cells, put into the language for historical reasons.
The venerable master Qc Na was walking with his student, Anton. Hoping to prompt the master into a discussion, Anton said "Master, I have heard that objects are a very good thing - is this true?" Qc Na looked pityingly at his student and replied, "Foolish pupil - objects are merely a poor man's closures."
Chastised, Anton took his leave from his master and returned to his cell, intent on studying closures. He carefully read the entire "Lambda: The Ultimate..." series of papers and its cousins, and implemented a small Scheme interpreter with a closure-based object system. He learned much, and looked forward to informing his master of his progress.
On his next walk with Qc Na, Anton attempted to impress his master by saying "Master, I have diligently studied the matter, and now understand that objects are truly a poor man's closures." Qc Na responded by hitting Anton with his stick, saying "When will you learn? Closures are a poor man's object." At that moment, Anton became enlightened.
From:
http://people.csail.mit.edu/gregs/ll1-discuss-archive-html/m...
The parallels between objects and closures are neither here nor there.
As long as we're veering off topic, I think it's interesting to consider Erlang in light of Alan Kay's ideas about OOP: While people coming from a C++/Java-ish background likely wouldn't recognize it as any kind of OOP, it's arguably MORE so than those: It's more directly based on encapsulation (via processes) and message-passing, without all of the "x IS-A y" conceptual baggage that comes from their mix of static types and OOP. It also has pervasive immutability.
Yes, he most certainly did. Simula had objects, but it was not object oriented, objects were not the core abstraction everything was built upon. That didn't come until Smalltalk which is why Smalltalk is the defining language for the term object oriented.
Personal taste has nothing to do with it, I'm just pointing out that it's a closer fit.
While you may prefer Alan Kay's definition, it is only a subjective one. It was not the first one and it is not the only one, so dismissin Java as less oop than Erlang is premature.
I'm pretty sure Alan Kay invented the term "object-oriented programming", which gives his definition some precedence over any other.
Objects, on the other hand are... a tool to provide a behavioral view of state which is environmental in imperative languages. An object is set of state, presented as a data structure, with behavior provided by fields in that data structure (one view) or by the way in which functions taking that data structure as an argument dispatch on its type (another). In an immutable world, such an object would have methods which return a new object with some modification made.
Without some mechanism (these are two) to wrap up related state into a passable/returnable datum, its hard to talk about dealing with such state being made immutable.
In other words, I don't think there's anything particular to OO about the mutable/immutable point the article is making; the important distinction is between operations on data structures vs. operations on the environment. The article is thus too hung up on objects as somehow `different' when it comes to immutability, but I don't think they are.
As a side note, for an example of an OO language more recent than Smalltalk which favors objects with immutable operations, look at Scala or Ruby.
I suspect that in another few decades, GLS will, with Alan Perlis, Don Knuth, and perhaps Edsger Dijkstra, begin to take on the CS equivalent to the pop cultural role now played by Mark Twain, Abraham Lincoln, and Ben Franklin -- a figure to which half-remembered quotes or anecdotes are routinely ascribed.
But that's no excuse for my own half-memory here. Thanks for the correction.
See also this interview with Alan Kay: http://queue.acm.org/detail.cfm?id=1039523
For example, you can write a Die class with a sides field (integer), a topFace field (integer) and a roll method that sets the value of topFace to a random integer between 1 and sides, inclusive. To use the Die, call roll and getTopFace. Want to roll 5 d10s? Then create Die(10) five times, then call .roll and .getTopFace on each of them. By the way, you now have five pieces of mutable state in your program and, if you ever forget to call .roll and only call .getTopFace on your dice (maybe you've been tempted to keep the Die objects around for "efficiency") you get erroneous results.
Clearly, that's the wrong way to solve the problem. It's better to just call (rand 10) five times: in general, you only care about the results of the rolls, not the "dice". (This approach still isn't "purely functional" as written, because it still uses a randomizer, e.g. state, but it's close enough for most purposes. Passing around a PRNG state is pretty heavyweight.)
Sometimes you need the full power of pi-calculus (communication, message passing) but usually you want to stick with lambda-calculus (referentially transparent computation) as far as you can take it. Mutable state is almost always necessary at some point, but you want to segregate it as much as you can.
The OP is kind of ridiculous actually.
In Smalltalk, there's a fairly common pattern of immutable objects. Their state is set when the object is created and then never changed. There might be getter methods, but there are no setters, and in fact the only method that makes assignments to instance variables is the initializer. It's not hard to see how that could be extended from "fairly common" to being a fundamental part of the language.
Setters are assignment-style operations, and a.f() is an attached procedure.
Also, in http://www.c2.com/cgi/wiki?AlanKayOnMessaging you can see "[I realized] that assignments are a metalevel change from functions, and therefore should not be dealt with at the same level - this was one of the motivations to encapsulate these kinds of state changes, and not let them be done willy nilly"
Alan Kay really is for segregating mutable state.
/pedantic
To be quite candid I forgot that there are languages that use the equal sign as both equality and assignment depending upon context. VB I think does that.
That's because Java and C++ embody Barbara Liskov's vision of object oriented programming, primarily. The abstract data vision.
If a function needs to operate on an object, rather than messing with pointers or copying the object, the function instead "swaps" the object with an initialized object. The function's "contract" specifies that it "consumes" the object that is passed in, so in code that calls that function, it is apparent that it better copy the object if it needs to access it again.
I think this provides a nice paradigm for allowing for immutability without excessive copying. The only functions that actually modify objects are the object methods themselves.
The RESOLVE/C++ language has been around for well over a decade, but it hasn't garnered much interest outside of academia. It's a shame, because it's a reasonably high level language that allows for mathematical proofs of correctness while still compiling down to machine code.
This is by no means a dogging of OOP. I personally think OOP seems to be better suited for practical business computing. Also FP, tends to have a higher learning curve (ex. monads) such that people of the street and in many academic programs gravitate towards the OOP paradigm. I think this could say something about how natural it is to use OOP, or maybe it just says something about how everybody is taught that programming "should be" (imperative vs functional).
That being said, I suppose that a solid new language with formalized OOP models that was very useful could become the next Java/C++. Time (and marketing) will tell. I would be very excited about such a language >_>.
On Understanding Data Abstraction, Revisited by William R. Cook
Discussed at:
http://lambda-the-ultimate.org/node/3668
From the paper:
"Object interfaces are essentially higher-order types, in the same sense that passing functions as values is higher-order. Any time an object is passed as a value, or returned as a value, the object-oriented program is passing functions as values and returning functions as values. The fact that the functions are collected into records and called methods is irrelevant. As a result, the typical object-oriented program makes far more use of higher-order values than many functional programs."
This is an argument against publicly accessible internal state, not stateful programming.