Recently I had a quasi-private discussion about philosophy in programming where somebody asked a question about functional programming. I’d like to relay part of the discussion here since it might be of interest to the community at large.
Jason wrote:
I have come out strongly in support of OO, and I think it has a very clear and strong basis in the facts of how computers work and how programmers think. In brief: Computers function by executing a series of instructions, at the level of machine language, which perform calculations and manipulate memory and I/O. In the earliest days of computing, programmers gave instructions to the computer directly at this level. As programs grew more complex, programmers needed ways to achieve greater unit-economy.
…
Often a set of variables truly do go together, such as a record representing an item for sale in a database, and certain functions operate primarily on this data. [This choice is not arbitrary.] Objects formalize this pattern and allow programmers to express it clearly and directly.
…
In general, imperative programming is rooted in the fact that computers actually run programs by executing a series of instructions.
…
I’d love to understand better the advantages of functional programming are. So to its advocates, I ask: What are the facts of reality that give rise to it? Note that it is not enough to explain, for instance, why it is mathematically *possible* to represent any given thing in any given mathematical way. What I want to know is: How is functional style rooted in the *purpose* of the software and the *nature of the thinking* that programmers do?
On the validity of the FP approach
The fact of reality that give rise to the FP approach is that computation is essentially a process of inferring quantities. Its purpose is to aid in human thinking. The conceptual faculty is a quantitative mechanism. This is laid out eloquently in David Harriman’s book “The Logical Leap”. See also “Concept-formation as a mathematical process” in OPAR. So the computer is in essence a quantifying device. Its invention was motivated by man’s need to quantify.
Calculating with numbers (quantities of something) gives rise to algebra, and importantly the abstraction “function”. And functional programming is simply writing programs using this abstraction. Functional programming was being done well before there were computers.
Imperatives are nonessential to computing. A mechanical computer has levers, wheels, and the like. We can imagine programming Babbage’s inference engine by turning a few wheels to set the premises and then moving a lever to make it infer the consequent. Similarly, in a digital computer we fill some registers with the premises and then pull a virtual lever in the form of a CPU instruction. But it’s important to note that “instruction” here is a metaphor. What’s really going on is the selection of a function which computes a quantity based on the input given.
So in summary, the purpose of the computer is to calculate with quantities as functions of other quantities. It is a mathematical tool. Even (especially?) for things like games. Drawing a complex 3D scene on the screen in real-time involves calculating a particular quantity of light of each color to be used to illuminate each pixel on the screen, given a particular time.
On the utility of the FP approach
Referential transparency buys you modularity (the extent to which components of a program can be separated and recombined) and compositionality (the extent to which the whole program can be understood by understanding the components and the rules used to combine them).
Type systems also get more sophisticated to the extent that programs are pure. It’s easier to infer types for pure programs than it is for impure ones, for example. You also gain things like type constructor polymorphism (a.k.a. higher-kinded types) and higher-rank types. It’s my experience that in a sufficiently sophisticated program (such as a compiler for a programming language), you either use these abstractions or you repeat yourself.
Sophisticated type systems then in turn aid in program inference, which is the extent to which the computer (or the programmer with the aid of the computer) can infer the correct program from type information (think tab completion, only moreso). Program inference is currently an active area of research.
As a side-note a lot of OO folks are discovering the functional approach as a tool to aid in modular design. They call it “dependency injection”, “inversion of control”, “interpreter pattern” and the like.
On the way programmers think
I believe that the way programmers think is deeply influenced by their chosen tools. They learn to think in the concepts that pertain to the tool. I think ultimately the argument that OO mirrors how programmers think is an appeal to intuition. But as we know, there’s no such thing as intuition. When people say “intuitive”, they usually just mean “familiar”.
A word on OO and the arbitrary
In OO, as commonly practiced, the choice of distinguished argument is arbitrary. Consider this function:
K(x, y) = x
If we were to write this in OO style, then on which object, x or y, should the function K be dispatched? Should it be x.K(y), or y.K(x)? It’s arbitrary. And before you say that the function K itself is an arbitrary invention, I say no. It’s actually a constructor of emtpy lists in this implementation of a singly linked list data structure:
Empty(x, y) = x
Cons(a, b, x, y) = y(a, b(x, y))
On “types of languages”
I want to get clear on some concepts. First the question of “types of programming languages”. I don’t think it’s helpful to divide programming languages into “functional”, “object-oriented”, “imperative”, etc. Sure, certain languages are better suited to certain styles of programming, but it’s important to differentiate on essentials and not mere aesthetics.
Functional programming is a restriction that the programmer puts on his programs. Having a language with a compiler that will warn you if you’re breaking referential transparency is helpful, but not essential. I do functional programming in Java, for example, which most people consider an “imperative OO” language.
We can also do “OO” in Haskell, a purely functional language (in the sense that all Haskell programs are referentially transparent expressions). Haskell is also a very good imperative language. Here’s a Haskell program in imperative style:
main = do {
putStrLn "What is your name?";
name <- readLn;
putStrLn ("Hello, " ++ name ++ "!");
}
Is this a sequence of instructions, or a referentially transparent expression? It’s both! Another way of writing the same program is:
main = putStrLn "What is your name?" >> readLn >>= (\name -> putStrLn "Hello, " ++ name ++ "!")
It’s important to note that these are not two different programs in any sense. The Haskell compiler literally translates the former into the latter.
The >> and >>= functions concatenate IO actions in exactly the same sense that the ++ function concatenates Strings. It’s possible for us to do this because e.g. calling readLn doesn’t immediately read from standard input. It is a referentially transparent expression that returns an IO action. The operating environment translates this IO action into instructions for the underlying machine at some convenient time. Or it may in fact not do that. The implementation of the IO data structure is abstracted away in a library, and there’s no reason that somebody couldn’t supply a different implementation with the same interface. This may be useful if you’re programming a missile silo and you need to be able to test the launchTheMissile action without starting a nuclear war.
Another benefit is that main can be composed with other programs. We could, for example, write this program:
mainTwice = main >> main
Or this one:
mainForever = main >> mainForever
I hope that helps.
Apocalisp 
I especially love how you clear up an enormous bunch of mythology in so few paragraphs. Awesome post.
I usually love your posts, wonderful examples of higher-level programming that provoke thinking.
However, this one is a nice read until “A word on OO and the arbitrary”. From there it looks like convincing the believers.
I couldn’t grok what ‘Empty’ and ‘Cons’ do, and I’m sure 99.99% of people don’t think of linked lists as some kind of function invocation (I may be missing it altogether, since I couldn’t grok it).
I think that showing Haskell code when writing a post to non-fp programmers is just like trying to convince people to learn chinese by showing a poem in chinese with no translation. The poem may be beautiful, but they can’t read it.
I think most people would agree that code written in FP style is more modular and composable. But it is also harder to understand and takes more thinking to write. What happens is that for small things it isn’t worth it (e.g., I want to write a log statement somewhere..) and by the time you have larger tasks at your hands the code is so non-fp that it will take a lot of work to make it so.
FP is like math. Probably everyone that reads this blog is very comfortable with math and got straight ‘A’s at high school. But many people don’t get math because of the levels of abstraction it required (‘3 – 2’ can be explained as ‘i have 3 apples and i ate 2’, but how can you explain ‘-4/-2’?). To us math is beautiful, because somehow our mind is wired to “get it”, but to others it is “ugly”, no matter how much we tell them it is not so.
I get FP in the mechanical level: I understand the terms and code and I could probably write pure FP if instructed to, but I don’t get it intuitively: when implementing something I will intuitively model it in terms of objects and procedures and it will take a conscious effort to model it in FP.
If I may suggest: A convincing post will not be about what you find beautiful in FP, but about making it intuitive for those whose minds are wired differently and don’t get it.
I think that FP is the most natural way to program for any programmer. Also, FP and OO are not mutually exclusive but actually complement each other.
I think FP is easy enough to be taught in high school, alongside with Math. Of course, static typing (higher-order types and that whole blabla) should NOT be taught in high school. People who professionally design software should have no trouble with static typing, of course, but kids don’t need to know about it.
There will be synergy effects here: Math will become easier to learn, and FP will become easier to learn, too. And to kids who have been brought up this way, it will be clear what imperative programming is: just another tool in their arsenal that sometimes is useful to make their program run more performant, memory efficient, etc.
Ittay,
A couple of notes on your post:
1) “… I’m sure 99.99% of people don’t think of linked lists as some kind of function invocation…”
First, it seems like you are pulling a statistic out of thin air. It also appears that you are failing to “grok” the concept that functions are connected via invocation. Take the list of numbers from 1 to n, for example. This list is described by the execution of a recursive function that counts up from one until it reaches n generating the nodes of the list on the way down (into the recursion) and linking them on the way up (out of the recursion).
2) “Probably everyone that reads this blog is very comfortable with math and got straight ‘A’s at high school.”
Counter example: myself. I was a C student in high school and am still not “very comfortable” with math. Thankfully my college years taught me its importance in describing complex phenomenon. That’s why I keep bashing my head against it in the hopes that one day it will all make sense ;)
3) “how can you explain ‘-4/-2′?”
Pretty easily: -4/-2 = (-1/-1)(4/2). Since anything divided by itself (with the exception of 0) is 1 we end up with 4/2, which is the number of items in each group when dividing a group of 4 apples into two groups. I’m not trying to be pedantic but just as we must learn to associate the numbers with physical quantities (such as with apples in your example) so must we learn to utilize the lessons of the abstraction itself. The argument you give somewhat like saying that cooling blankets do not make sense since we all first learn than blankets are supposed to keep us warm.
4) “… because somehow our mind is wired to “get it”, but to others it is “ugly”.”
This seems to presuppose that the mind completely unable to adapt. That we are all born with a specific set of skills an nothing could ever change that. Perhaps I am naive but nothing in my limited experience has yet to suggest that the mind can only see things in one particular way and that no amount of stimuli can change that “predetermined” way of thinking.
Rsandor,
Yes, statistics were pulled from thin air.
1) Church numerals are a nice concept yet this example is precisely what I’m talking about: it may seem natural to you, but it is fairly obvious that if we take a common, good, programmer he will not think of this as the way to look at numbers.
3) My point in the analogy to math was that FP is about abstraction (you don’t print to the scree, you return something that will sometime print to the screen if asked). Abstraction is hard to get, which is why I gave the analogy to math in the hopes of explaining how something that looks natural to someone is hard to understand by other people. In ‘explain’ I meant a sentence involving oranges. What you gave is an abstract explanation. Sure that 4 oranges divided to 4 people will give 1 orange each. But -1/-1 makes no sense in such a context. This is what confuses people in math (not being able to translate something to physical examples) and the same is true for FP.
4) I was trying to say that in order to convince people to use FP, one has to see it through their eyes and explain it to them. Explaining -4/-2 as you did, or showing haskell code for Cons and Empty makes sense only to those who already understand it in the first place
Ittay,
I’m pretty sure you can figure out that Haskell snippet, even if you have never seen Haskell before.
The “OO and the arbitrary” bit is somewhat out of context. The original questioner had stated that OO provides him with unambiguous design choices and that FP seemed like an arbitrary invention.
As for getting straight `A`s in school, well, I for one was a B-minus student at best. But I think none of us have any trouble learning something that we find intensely interesting.
I guess you have precedence error here:
putStrLn “Hello, ” ++ name ++ “!”
Even if you say “familiarity” instead of “intuition”, it’s still very strong argument in favor of OO. I think FP approach will be used more and more in currently popular OO languages and languages built for FP remain secondary. “Pure” (in broader sense) and “popular” don’t seem to go together in PL world.
Inertia is a strong argument indeed.
Ittay,
Here is the same code in Scala:
def Empty[X, Y](x: X, y: => Y): X = x def Cons[A, B, X, Y](a: A, b: B, x: (B, ((A, X) => Y)) => X, y: (A, X) => Y): Y = y(a, x(b, y))That’s not quite right.
def Empty[X, Y](x: X, y: => Y): X = x def Cons[A, B](head: A, tail: (B, (A, B) => B) => B)(x: B, y: (A, B) => B): B = y(head, tail(x, y))What Ittay said +1.
Yet another post by a Haskell fan trying to explain why Haskell is so great and simple, in which the examples made no sense to me whatsoever.
Yes, I get it. I think the way I do because I have learned to do so from the tools I use. Help!
Simon Hibbs
No, you think the way you do because you are a cynic.
Now try getting the answer without pulling the lever. It is the pulling of the lever that indicates the instruction.
From wikipedia: “In much the same way that imperative mood in natural languages expresses commands to take action, imperative programs define sequences of commands for the computer to perform.”
The pulling of the lever is the “command to take action”. Modern computers have automated the process of pulling the lever, such that it can be pulled millions of times per second. But a CPU is decidedly an imperative machine. You can make it execute a functional language, but I do not think it is a functional device as you cliam.
All you’re saying is “try getting a result without running the program”, or “try getting an answer without calculating it”. Calling the evaluation machinery imperative doesn’t make it so. A CPU isn’t any more imperative than a billiards table.
“A CPU isn’t any more imperative than a billiards table.”
Precisely. A game of billiards is imperative.
A game of billiards has state.
But no imperatives. And it’s not true that state is avoided by FP. It’s just made explicit.
It’s worth noting here that there are perfectly faithful models of the physics of a billiard table that don’t contain anything like state. Paths though configuration space, for example. The most you can say is that temporal slices of the physics of the billiard table appear to have state, but that’s an illusion. In other physics models (e.g. most quantum mechanics interpretations) you don’t even get that.
Exploration of the obvious analogy to functional reactive programming is left as an exercise for the reader.
Tony,
Thanks, but I still cannot figure it out. Maybe a usage example?
Furthermore, throwing it in a blog post without any explanation make it seem like FP is about brain gymnastics rather than purposeful coding. It’s like optical illusions – they are fun to watch, but don’t seem to have real value beyond that.
Try to follow the explanation of Empty and Cons in python at sigfpe’s blog.
Sometimes you need and apple and an orange, “a set of variables truly do go together, such as a record representing an item for sale in a database”. Sometimes you need either an apple or an orange, but few OO languages allow you to easily express this thought.
One point that classifies programming languages is whether they let you easily express the “reasoning by cases” that programmers do all the time. Some languages let you express this easily with data as tagged unions, often as an algebraic data type. In ML-ish languages there is pattern matching (switch-case) to easily consume these tagged unions.
Making proper tagged unions in Java is cumbersome, as Tony Morris demonstrates. Using something at least as heavy-weight as a Java visitor pattern every time you want to examine a value is a ridiculous way to support “either apples or oranges”.
Referentially-transparent higher-order fist-class polymorphic tail-recursive lexical function closures of doom are a brilliant foundation. But wouldn’t it be nice to see Java Enum’s boosted into tagged unions?
You give a mathematician’s answer to an engineer’s question. It is as if you think CAD programs are an artist’s tool. All drawing is art. All numbers are math. Why can’t you see past the math?
Not every branch of mathematics is equally practical in real-life. For example, quaternions. A beautiful, elegance math but having much more limited usefulness than ordinary scalars and vectors. I’m a mechanical engineer — I know first hand.
Is this because of any abstract shortcoming in quaternions? Absolutely not. It is because of the nature of reality. Nature is how she wants to be. Not how we want it. Some math, say functional programming, is just not as generally useful as some other math, say OO programming. That’s real life.
If you really want to answer the question, you will have to discuss the EXPERIMENTAL data. You know, the scientific method. Not ramble off on some logical analysis. Not everything that is logical actually describes the true nature of reality.
By the way, do you think functional databases would be better than relational databases? What about OO databases? :-)
I have no idea what you mean by “functional databases”. And an “OO” database is just an old fashioned graph database with a cute name.
> Some math, say functional programming, is just not as generally useful as some other math, say OO programming. That’s real life.
I’m going to have to say that’s a bad analogy. Functional programming doesn’t really match up with the use of more obscure fields of mathematics just because they’re related. Functional programming is the useful application of those fields that you seem to be missing.
Some problems (and not just a few obscure ones) are much more easily expressed with functional programming. In Haskell, you can write programs just by gluing together standard functions. These programs are short, concise and understandable- Haskell often scores well in code golfing contests without actually needing to obscure things.
For an example, see XMonad- a full tiling window manager in less than 1/10th the size of awesome, a comparable window manager in C and Lua. Even accounting for C’s low-level nature and relative verbosity, that’s an awfully large difference.
A lot of pieces of Haskell that come from its roots in mathematics are incredibly useful and not hard to understand. A good example is the Maybe type. Much like IO’s explicit typing of side effects, Maybe explicitly types values that can be null. This is possible /because of/ Haskell’s very specific and mathematically rigorous semantics.
Aren’t you agreeing with my point?
You compare two similar software (I take your word for it, I’m unfamiliar with either) and claim the Haskell one is 1/10 the size of the other. Great! That’s a *measurable* number. And, if I devoted the time, I could also confirm or falsify.
My complaint was with people who base their programming language comparisons entirely on broad, abstract arguments. A person like every mathematician I ever met. (There’s a very old joke that expresses this complaint in a obtuse way: The difference between an engineer and a mathematician is that a mathematician will assume anything except responsibility.)
BTW, since Lua supports function closures, multi-returns, and proper tail-recursion, doesn’t it qualify as a functional language? I know, it lives in a C ghetto, but do we have to let that prejudice us?
You get the strangest comments man.
your answer doesn’t help. you’re clearly another FP fanboy sitting in his high theoretical tower.
I prefer it to the tower of prejudice in which you sit.
Perhaps you didn’t notice but “toughen up princess” was directly squarely at you.
How does IO fit into all this? Not all programs are pure mathematical expressions and certain algorithms have explicit non-determinism in terms of noise, user input, synchronization, etc. and it’s hard to reconcile these with pure functions.
David,
The Haskell programs in the post interact with the user and yet they are referentially transparent expressions (i.e. pure functions). It’s not at all hard to reconcile this. At the end of the day, all the computer does is calculate some quantities. We basically interact with users and peripherals by calculating some charge differences, as a function of what has come before.
I am not disagreeing with the fact that all computers calculate quantities what I have trouble with is the definition of referential transparency when used in the context of values and expressions that have type IO a because the expression that stands in for the value and the actual value of the expression once it’s evaluated are two different things when there is some kind of implicit or explicit dependence on time. This is not the same when it comes to pure functions like factorial because 5! and 120 can indeed be substituted for each other and the meaning of the program doesn’t change. This is actually where all proponents of functional programming lose me because readLn now is not the same as readLn in a week but for some reason functional programmers keep insisting that it is.
It absolutely is.
readLnwill always be the same program. Running it on different inputs may, of course, yield different results though. What you have to consider is that an IO program carries with it an explicit dependency on some state of the environment. In Haskell, “IO a” is a data type which may be considered a function of typeRealWorld -> (RealWorld, a). So it takes the state of the world as input and returns the next state of the world as output.An expression of type “IO a” cannot be replaced with an expression of type “a”. That would be a type error. What’s more, you can’t get an “a” out of “IO a” because you cannot construct a value of type RealWorld. The runtime will construct one for you, and you can only have one of them for your entire program.
You’re still avoiding the fact that readLn has some weird semantics and doesn’t quite fit the definition of pure function as it’s used in mathematics. It’s not like the function (+) where the semantics and the action of (+) can be reduced to a recursive definition on the natural numbers. readLn depends on this outside machine, which I think haskell programmers call the IO monad, for its operation and this machine can’t be reduced to something resembling the definition of the natural numbers because sequencing and mutation are part of it’s core components.
The semantics aren’t “weird”. Yes, it requires interpretation by a machine of some sort (an IO subsystem), but then again so do the natural numbers.
Sequencing is definitely integral to IO. The sequencing operators (>>) and (>>=) have much more in common with (+) than you think though. They are pure functions, and they are even associative just like (+). But they’re specifically not commutative, hence the sequencing.
Just like operations on natural numbers presume some mechanism of counting, operations on IO actions presume some mechanism of performing IO.
I like to think of it this way: the top level program (main) is a value in the language and there is an interpreter in the runtime which traverses that value and executes IO actions along the way.
So there are two things happening as the program runs: functional expressions are being expanded and reduced according to the lazy evaluation engine and IO actions are being executed as they turn up in the computed program value according to the rules of the values they are part of.
So if you think of the program as a value, then it is a “pure mathematical expression”; but at runtime, there is an imperative runtime engine interpreting that program value.
there is an imperative runtime engine interpreting that program value.
I wouldn’t necessarily say “imperative”, but it’s definitely causal.
Nice post! I’m going to take issue with with this snippet though:
This reflects a very common misconception about OO. While it’s true that this trick does allow us to write in an operand-first style, delimited by a dot, this is *not* the same as OO. It’s not even an interesting part of OO.
The key thing this is missing is open recursion. Like it or lump it, subtyping is an integral part of OO. It’s the very definition of message respondant polymorphism (which is trivially equivalent to structural subtype polymorphism). (note: message respondant polymorphism is sometimes referred to as “virtual method dispatch”, which is accurate, though unnecessarily mired in implementation specifics) Without polymorphism in message passing, OO is barely more than syntactic sugar on top of a procedural language. Open recursion is necessary if you want to support message respondant polymorphism on self, which is in turn necessary if you want to keep your language consistent.
Open recursion is problematic because it requires the variance on the self parameter to be *covariant*, rather than contravariant. The variance on the dispatch receiver in OO is quite literally backwards, and it’s only sound because the language controls the call-site and doesn’t allow you to get access to a raw message handler (i.e. one which hasn’t been partially-applied on a receiver). The key thing to realize though is that this covariant parameter makes OO-style dispatch polymorphism effectively impossible to encode in terms of a statically typed, purely functional language (without *extreme* conniptions, often involving existential types, higher-rank and higher-kinded types). If you don’t believe me, just read the last several chapters of TAPL. If it were this easy to encode OO in a functional language, it wouldn’t have taken Pierce so long to conclude that it is almost impossible.
Just drop the static typing requirement, then. (http://www.babel-17.com)
Open recursion can be encoded in a purely functional style. Like you say, it isn’t trivial, but it has been done using just Haskell.
http://homepages.cwi.nl/~ralf/OOHaskell/
They needed to extend Haskell 98 with support for safe covariant arguments. It’s easy to get a large chunk of OO encoding working in Haskell, particularly in light of its support for typeclasses and higher-kinds. It’s that last little bit (open recursion) that requires language extensions.
Incidentally, purely-functional OO encoding isn’t difficult, just make your language support a primitive self pointer on records and you’re done. What I’m saying is that encoding all of OO in vanilla *Haskell* is very, very difficult, and certainly not as trivial as “flip ($)”.
Lump it.
Thanks for the well reasoned comment, Daniel. I’ve removed that snippet since it’s really a distraction.
The quote that gave rise to the post seems wrong-premised. OOP isn’t in any way more natural to computers than functional code, whatever the definition of “functional”.
As for the *nature of thinking*, it’s a movable feast – you think however you (or, much more often, someone else) taught you to think. The effects of thinking functionally on one’s coding are very far from trivial. It’s kind of like meditation – you have no place talking about it until you’ve done it a while.
I think a more fruitful approach to spread the adoption of FP thinking is to demonstrate benefit from FP ideas within in a familiar mainstream imperative language. Demonstrating within a language familiar to those you are trying to convince will allow readers to focus on just one new thing at a time and see the key part that is important (i.e. the style). Once you have someone interested, only then introduce a language better suited to the style and discuss the theoretical backing.
In particular I think this works for introducing immutability. I myself was sucked into FP by first experiencing complex immutable data structures within C++. This later prompted me to go learn a language better suited to immutability. I have since created plenty of immutable objects and data structures within C++/Java/C# in order to demonstrate the advantages to colleagues. I have found this to be a more successful way to convince colleagues of the benefit of an FP style or language (it certainly worked on me). I’m sure the same applies to higher order functions, laziness, and other elements of FP style.
Runar is a primary committer to Functional Java http://functionaljava.org/
Things don’t work out as well as you might hope when “demonstrate benefit from FP ideas within in a familiar mainstream imperative language.”
I wasn’t aware of Rúnar’s work there – awesome stuff. I’m glad to see he’s covering all approaches to spreading the FP gospel. :)
My comment was almost entirely anecdotal. What worked for me and a few of my colleagues may not work for everyone.
ok let say it tweetly.
can a program, be it functional or non ever run without a “pointer twidling” somewhere behind the empty abstractions ?
let me know you functional people can write a functional program without “pointer twidling”
heck some bloke even wrote a operating system in haskell. i bet he can’t write a real display driver.
if you ask “why you mad bro ?” lemme tell you. functional languages and most of its ideas are still in a beta stage. don’t pretend it is production ready.
Can a program, be it functional or imperative, ever run without manipulating semiconductor activation states somewhere behind the empty abstractions.
At current levels of technology, no. Fortunately, it turns out that really doesn’t matter for 99.999% of programs.
Your problem is not with FP, but with high level languages in general.
Does the computer you’re planning to run your programs on has infinite memory or must reuse memory locations (and so rewrite values)?
That’s not the point. I can program in any garbage-collected language without having to worry about this detail, and I can program with immutable values in any language with garbage collection.
There’s nothing “beta” at all about FP. There’s sound theory behind it and plenty of languages around that make it natural.
Tell that to Galois, Basho, Facebook, Twitter, RememberTheMilk, and thousands of other companies who use Functional Languages for production applications with a much higher level of success than many competitors who don’t. I think you’ll find there’s a raft of smarter people than you who have already proved you wrong.
If your intent was to come across as a bigoted fool, I congratulate you on achieving it.
What if we ask that you learn the topic? Lemme tell you. Functional languages and most of its ideas have been in a beta stage for several decades. Heck one guy, maybe two or even more, have been using it in production for many years! Don’t pretend dude. Try to learn instead.
Rúnar (and/or anyone concerned), do you think “how to best hoodwink a working programmer into trying functional programming” would be a useful topic to discuss?
Hoodwinking sounds dishonest. Knowledge is only possible to those who seek it.
I keep forgetting that sarcasm doesn’t survive a form submission, damn it :)).
Yes, knowledge comes only invited, but not everyone is in perpetual search. More frequently people chance into knowledge by coming across a tasteful morsel – a blog post, a tweet, what not. Ideas only succeed if well-promoted.
I think Rúnar’s “toughen up princess” remark sums it up nicely.
To me, FP just codifies a set of approaches to programming that I’d intuited – things that just felt right. I have since learnt FP, and it provides some excellent real-world reasons why my intuitions were actually good ideas.
Simple mutation. I always felt that mutation was wrong. I would never reassign a variable if I could help it – it’s just as easy to create a new one. I would never reassign to a parameter variable.
Testing. I discovered that “testing pure functions was much easier than testing impure functions” before I discovered what a pure function was! I had experience being bogged down with highly coupled, effect-laden systems, and testing with mocks and spies and it was a nightmare. Now I know why they were a nightmare, I can avoid them.
Higher-order functions (not strictly functional programming, but is often discussed at the same time). I was always a refactoring junkie, and there was always that chunk of code of this form that I couldn’t refactor:
f = do A; do X; do B
g = do A; do Y; do B
Then I read “Head First Design Patterns”, and it shows that “Strategy Pattern”. “do X” and “do Y” are both strategies, so the algorithm becomes:
q strategy = do A; do strategy; do B
Then I discovered that strategy pattern is just a higher-order function.
The “arbitrary distinguished parameter” thing in OO has always driven me nuts. It leads to unnecessary complications in design and decomposition. Moving the function between the two classes is often non-trivial. If there is no distinguished parameter it is much simpler.
I honestly cannot understand why people are resistant to functional programming. Like me, any half-decent programmer should have realised (or at least had an inkling) that the ideas behind FP are good ideas, and should have experienced first-hand the problems associated with not practising it.
Is the main resistance that FP is perceived as equivalent to “that esoteric academic language, Haskell” or “a bunch of crazies that talk in maths”? I think the maths comes up because once you discover FP, you realise that all that maths you did in high school and uni suddenly becomes mindblowingly useful and applicable… so FP people tend to use more maths.
This is confronting for people who think that programming is all about “simplicity” and “decomposing into simple objects”. When you write a “for” loop and suddenly realise: hey, I’ve written this same line of code 40,000 times before, you start to see patterns, and patterns upon patterns. More and more higher-level abstractions.
These do not “complicate” your code, they simplify it. Programming in abstractions means you write less code! And the really powerful abstractions simply do not work without function programming’s purity, and a bit of maths.
Maths isn’t the scary part, maths is the good part! It helps us!
At the end of the day, we do functional programming because:
– it leads to less bugs
– it’s easier to test
– more refactoring power
– it’s essential for parallelism
– you write less code
– it’s just plain easier!
Yep. It’s easier! Don’t let the maths fools you, this is a way of making your life easier!
Programming came from maths. Somewhere along the line, we thought we were too good for the maths, and threw it away. We came up with a whole slew of tools, tricks, concepts etc that ultimately did not work. I think the FP revival is an acknowledgement of our roots in maths. Maths has a lot of the answers we run around trying to reinvent.
Maths is the fundamental source of programming. How can we possibly be good programmers if we do not know our fundamentals?
Great comment Dylan – I’m currently at the stage you were, where “code smells” are screaming to me that there must be a better, cleaner way to not only code, but test my code. I’ve recently learnt about (but not yet learnt) FP.
I thought your comment was about the most perceptive here for those of us just starting down the FP road. Thanks.
I agree. Great comment Dylan. You’ve pointed out som of the areas I’m struggling with im my daily (programming) life with Java. I’m also one of those who’ve just recently stumbled across FP while reading about Scala and more precisely the scalaz library.
Thank you
I think a lot of the frustration and opposition to fp from an oo’ers perspective may come from jargon and a sense that the fp’er sits in an ivory tower looking down and the oo’er as a lesser programmer. I don’t think that does much service to pollinating ideas or inspiring others to learn. If nothing else, it only creates opposition.
Going back to the original post, I think there is still a great deal that can be explained about the philosophy of fp without going straight to jargon, math or an unfamiliar language.
warning: I still consider myself a novice in fp so I admit to ignorance and accept criticism for my own ideas that may be in fault about fp.
Using how a machine works to justify how programs should be written is not particularly a strong argument for imperative programming. A program should be defined as a way to express the solution to a problem in terms of computation. A computer is tool or means we use to execute these computations but that doesn’t necessarily have to dictate the approach we take to designing the computations. The goal should not result in something non deterministic.
The argument that fp can not represent the real world sufficiently is also a weak argument for imperative programming. Going back to the original post’s mention of the philosophy of fp, I think of the real world as a series of transitions that result in instances of time that will eventually transition into other instances which may have a paper trail back to the previous instances but in fact do not share the same identity at different points in time.
In the real world, I am a person made up of a number of transitions over time based on the “application” of events that occurred through out my life. I am not the same person I was 5 minutes ago and won’t be the same person 5 minutes from now. Who I am and become is deterministic based on the transitions I make. The real world is also not single thread and multiple things can definitely happen to me at the same time. If the real world were imperative, my life runs the risk of being in invalid states or worse at the risk a concurrent modification exception! If I had the choice of deciding which style of program I would use to design a real world problem, I would definitely side with the style thats deterministic (referentially transparent).
Fp to me is just the same as the real world. It’s a transition of one state to another or in other words, the composition of functions, and not a series of instructions mutating state.
Isn’t being human means you are *not* immutable? There is just one instance of Doug in this world and everybody around him has a reference to that Doug only. When I tell you something, I may get different responses each time I tell you the same thing.
This is probably why it is harder for people to relate to FP. It may be a great abstraction for modularity, parallelism etc., but it is not an intuitive model of the world.
This kind of analogy is a mistake in the first place. A program is not inhabited by objects to which your heady metaphysical theories apply. Talk about sitting in an ivory tower.
Rúnar,
I did not say anything about ivory towers, no need to bash me.
I did not mean to say that OOP is a model of the world. I don’t think either paradigm should try to model the physical world. The target should be to create better code.
However, I do think that OOP is more intuitive to model for most people. This is why it is more popular. Maybe working in FP produces a better code once you are comfortable with it, but there is that step of becoming comfortable and evidently it is a larger step than getting comfortable with OOP.
So getting people hooked on FP is more about psychology than fact. What I want is blog posts that try to make the casual OOP programmer comfortable with FP. The reference to ‘ivory towers’ that someone made may reflect on the fact(?) that there are non (or at least not many)
P.S: to those that explain how OOP models the real world I give the example of trying to model a library in OOP. If you try to model it like the physical world you end up with on class ‘Librarian’ that does everything and a lot of anemic structures like Book, Shelf etc.
Like I say, there’s no such thing as intuition. OOP feels intuitive either because you already know it, or because it’s explicitly intended to give that illusion. OOP says “look at me, I’m like the real world. The real world has objects. You know objects!” But it’s bollocks.
I’m aware of the fact that many people want to be made comfortable. At some point in their lives, adults turn into intellectual wimps. They want to have their hand held and be reassured that they won’t have to experience the trauma of unfamiliar territory. But why? There is no good reason. This is why I say “thoughen up, princess.”
Or maybe the “ivory tower” reference was made to such remarks as: “intellectual wimps” or “thoughen up, princess”? Maybe instead of bashing those that don’t share your point of view, try to see theirs?
I’ve seen it. I’m not bashing, I’m just saying there’s nothing to be afraid of.
I’m not afraid, just not convinced. Like I said, maybe when I “see the light” I’ll become a much better programmer. But I need to decide where I want to spend my spare time and FP is one topic out of many.
I’m pretty sure that learning something that is totally different from what’s “intuitive” is going to make you a better-rounded programmer. And precisely because time is precious, I’m not going to waste it on platitudes and wankery. Life is too short to get comfortable.
When I tried to make that analogy I maybe had a little Rich Hickey in my head at the time :) I was trying to imply that time in a program is analogous to time in the real world, if we are still talking about paradigms as they apply to the real world. When something changes in a functional program a new value is produced. It may contain some of the previous value (structural sharing) but it is not the same value (same mutated instance).
Falling back on math…
If I am 1 and you add 2 to me I’ll always give you 3 but 3 is definitely not 1. You can’t mutate 1. It’s a value.
When I thought of an real world analogy I may have also be under the influence of Dr. Who :) I can buy the fact that there are instances of me at different points in time but are not the same instance of me that I am right now, though I’ll probably never meet one :) Other people’s references to me are their interactions with the instance of me at that point in time. Have you ever had someone come up to you and say “I don’t even recognize you anymore?” It’s because that person retained an old reference to another value.
With regards to learning, I admit to my own ignorance and don’t even own a desk at home let alone and ivory tower to sit in, but what I have learned about fp has changed the way I programming in oop environments. The result is a mix which is why I think Scala is a great place to start.
Doug,
I think programming idioms should be used to create better code, not because they simulate the real world.
I also think that FP has its merits. I think every good programmer uses FP unconsciously when it is intuitive. That is, when it maps naturally to a processing the returns a result. The question is whether it is better to use when unintuitive. When monads come into play.
It boils down to “is it worth it?”. For me, I still can’t see a big picture of how using FP will make my programs a lot better. Sure that referential-transparency sounds great, but how many of my bugs are due to impure functions? I think very little. Most of them are about forgetting to handle corner cases of logic / data. Going through the hoops of propagating IO monad values throughout my code will not help me there.
Ittay: I would like to make a suggestion that you stop using the word “intuitive”.
Fair enough. I didn’t try to suggest FP is not intuitive. I don’t want to sound like I’m against FP. If you ask my coworkers, I think they are sure I’m some kind of champion for FP (that is why I’m looking for explanations that will sell it to them). I’m just saying it is not black and white. Some cases are modeled better with FP and some with OOP.
There is no FP/OOP dichotomy. You can safely put that out of your mind. There’s also no such thing as intuition, so you can safely suggest that FP is not intuitive.
I’m going to disagree with you there. Try adding subtyping to System F and tell me how it goes. I don’t think that was your point though; I just wanted to clarify.
Fair enough, disagreed. I actually haven’t a clue what OOP is, but subtyping seems to be a popular thing to put in that grab-bag.
The “ivory tower” idea is interesting psychologically because it simply isn’t so. In fact, it may be the “OO analysis and design” folks who sit in an ivory tower, more concerned with their model (and their machines) than with understanding the real world.
I like your reply. I’d add that it’s not the business of programming to imitate some perceived aspect of the real world for the sake of imitation, but to understand it. Specifically, to understand it in terms of quantities.
Something like “Learn You a FP in Scala For Great Good” would be fantastic.
I’m not sure who gave you the authority to dictate what the business of programming is.
Arrogance is an enemy of knowledge because it deludes a person into thinking they know it all.
And your arrogance is evident in no other statement than your claim that there’s no such thing as intution. If you lack intution it doesn’t prove intution doesn’t exist.
I think this article is a thinly veiled attempt to satisfy your great desire to draw audience to your blog. Lets face it, what better way to generate traffic than to bash OOP imperative programming and take the intellectual high ground by glorifying functional programming?
Aren’t you tired of preaching to the converted and trolling by now?
You remind me of Ayan Rand- mediocre philosopher and even worse writer.
what are the chances of my comment getting published? I might write a function that has no side-effect to calculate that. but oops! in such case it is never going to print the outcome to the console is it? I’m heading off to solve this paradox before attempting to calculate the probability…..
Hostility and cynicism are enemies of knowledge as well, and you exhibit both. There is no bashing of “OOP imperative programming” here. I think you’re making that up. Also, please define intuition in unambiguous terms if you wish to assert that it exists.
Here’s what a dictionary says: “Intuition: direct perception of truth, fact, etc., independent of any reasoning process; immediate apprehension.”
There is no such thing as knowledge apart from reason. I find it extremely arrogant to claim that you can know something without thinking.
I’ll take the comparison with Ayn Rand as a compliment, thanks. I’m curious why you would think that your opinion of her would be of value to anyone here.
Let me second the intuitive notion that hostility and cynicism are enemies of knowledge. Decorum would dictate that Arniko’s comment be struck.
But at the same time though let me sharpen Arniko’s actual argument as follows.
1. Programming methodologies are embodied in the real world and are thus subject to the scientific method. Since the scientific method is explicitly non Platonic, all purely rational arguments in support of any theory must fall short. The sole test of knowledge is experiment. That is, the issue of FP vs. OOP must be settled with data, not analysis. Put another way: one of the fundamental assumptions of the scientific method is that Nature is consistent. However, an assumption is just an assumption. Completely scientific theories are shown false all the time. A rational theory is not enough for it to be true.
2. The uncertainties of scientific theories are Bayesian and another word for a Bayesian prior is “intuition”. That is, for a mathematically unambiguous definition of intuition see the definition of Bayesian prior. Others could define other definitions, but they would not be more intuitive. :-)
There is no issue of FP vs OOP. The entire point of the post is that this issue does not exist.
Further, I have to disagree completely with your “critique of pure reason”. You play the same game as Kant, setting up a rationalistic (Platonic) epistemology as a straw man, call it “reason” and then proceed to attack it with the very same rationalistic method. But this simply isn’t an issue. Rationalism is not reason. There is no analytic-synthetic dichotomy. But this issue has been discussed at length elsewhere over centuries and millennia, so let’s not retrace all of that here.
Hi Runar,
I guess you did not catch my meaning when I used the scientific method and Bayesian priors. You really think that’s Kantian Platonic epistemology? Wow.
My comment was addressing your statement that: “I find it extremely arrogant to claim that you can know something without thinking.” I was trying to point out that no assumption is ever based on reason (thinking). And yet all knowledge is contingent on its assumptions. Math on its premises. You cannot say a conclusion is true without also stating what its (assumed to be true) assumptions are.
And exactly what, Runar, distinguishes your assumptions from your intuition? Intuition forms the very basis of all your beliefs. See, for example: http://wmbriggs.com/blog/?p=4008
“Hostility and cynicism are enemies of knowledge as well”
I take that as an unsubstantiated silly wordplay- its no different than saying laziness is the enemy of happiness.
“please define intuition in unambiguous terms if you wish to assert that it exists”
Since you have been repeating your mantra ” there’s no such thing as intution” – I’d like to challange you to prove it. The burden of proof is
on you and not me.
As for knowledge and the prerequisite of thought process before acquiring it, here’s something I’d like you to ponder.
I’m sure you are aware of the fact that animals possess natural disaster early-warning-system that us the smartest species don’t seem to possess
( I’ll exclude tribal jungle-dwellers like the ones found in Andeman Island for the sake of simplifying this argument).
And as such they flee from the area that are going to be hit by disasters such as tsunami, earthquake, volcano eruption etc.
Do animals acquire the knowledge via rational thought process? Do they have some advanced sensor chips embedded in their body somewhere?
If not please explain.
As for Ayan Rand- I’ll explain that part if you can provice me proof that intution indeed doesn’t exist :-)
Calling for the proof of a negative is a logical fallacy. Proof applies only to things that exist. You have the burden of proof backwards.
Are you appealing to some kind of extrasensory perception? Even if I were to allow that, and if humans possessed such perception, they would still have to integrate the material thus obtained by a process of thought.
And it’s not just wordplay. I truly and honestly think you’re just being hostile and cynical and that you don’t really have anything of value to say. I welcome evidence to the contrary.
I’m not at all convinced that I have the burden of proof backwards, I believe that either your understanding of proof of negative is one-dimensional or your claim of non-existence of intution is an excercise of deliberate intellectual laziness.
“The negative proof fallacy is where one assumes something is true if it cannot be proven false. It can also happen when one assumes that something is false if it cannot be proven true.”
http://logical-critical-thinking.com/logical-fallacy/negative-proof-fallacy-and-burden-of-proof/
And besides not every argument can be dissected using a manual of rigid sets of logical fallacies.
For example I can safely claim that ” I’m not a female”. All I have to do to prove the negative is pull my pants down :-)
You can accuse me of being crude here but I don’t think you can claim my method of proving this particular negative claim is invalid or my proof is insufficient.
“Are you appealing to some kind of extrasensory perception? Even if I were to allow that, and if humans possessed such perception, they would still have to integrate the material thus obtained by a process of thought”
If animals (even humans whose instincts haven’t been blunted by technology and over-excercise of rational thinking ) don’t
seem to need to integrate what they sense by thought process, why on earth do you think humans need to do that to be able to act on what they sense? Are you allowing that humans are somehow inferior to those animals?
You have unwittingly let doubt creep into your own claim of nonexistence of intution by allowing- though grudgingly- the possibility of existence of extrasensory preception . Which is no different from intution in that they both have nothing to do with your rational thought process.
I’ll leave it to you to judge the value of my comment and hope that you won’t let ego or some other irrational impulses hinder your judgement.
You’re absolutely right that “intuition” and “extrasensory perception” have nothing to do with a rational thought process. Neither does this conversation, it seems.
The value of your comments here are very close to zero. But I’ll add one thing since not everyone is aware of it: Not everything is either true or false. Truth is a trichotomy (true, false, arbitrary), not a dichotomy. Now, the law of excluded middle says that a thing either is or is not, and truth and falsehood apply only to things that are.
For example, the statement “there is an unstoppable mouse” is neither true nor false. It’s arbitrary. That is, I’m just making it up. So it doesn’t gain admittance for being considered at all. A statement like that is to be treated as if nothing has been said. Because, in practical terms, nothing has. And indeed, this is how I’m going to treat most of what you just wrote.
“You’re absolutely right that “intuition” and “extrasensory perception” have nothing to do with a rational thought process. Neither does this conversation, it seems.”
That’s a prime example of an arbitrary statement. You failed to argue as to why my conversation has nothing to do with rational thought process.
“The value of your comments here are very close to zero”
Why? what made you think so?
Suddenly you sound very weak and unsure of yourself with your indignant unfounded claims.Your claim is like a horse let to the water, can you make it drink?
Truth is not trichtomy as you claim. Between true and false there’s sometimes infinite possibility. Ever came across fuzzy logic?
What’s your point really? And what’s this nonsense about the law of excluded middle? How on earth is that related to my comment?
Why are your resorting to silly examples? Where does the unstoppable mouse fit in?Why are you trying to put up strawman argument on my behalf and shoot it? Your last paraghraph is a classic case of strawman argument.
Why can’t you simply argue why I got the burden of proof backwards and prove it?
Have you run out of defences based on your logical fallacy manual?
You haven’t answered a single question I raised in my comment.
And as such I conclude you are a weak intellectual bully who suffers from delusion of grandeur, you makes things up as you go to support your weak feeble arguments.
You answered noting with your 3 paragraphs of dishonesty.
I challange you to answer my questions and to present counter arguments to my claims in my previous comment.
Toughen up princess, and don;t let your ego get between you and rational arguments.
And moreover,stop claiming anything is non-existence before you have exhausted all the aveues to prove it otherwise.
I don’t really understand what you’re on about. If you actually have a point, write about it coherently somewhere and maybe paste a link to it.
Your assertion about ‘OO and the arbitrary’ is only relevant to functional expressions which have been converted to an OO style, eg. add(x y) ==> x add: y
In THAT PARTICULAR CASE you can treat the add: message as a function with a ‘distinguished argument’, but it misses the whole point of OO design & programming style.
Objects are often mutable, and we build complex behaviours by composition and inheritance.
eg. img rotate: 45; movex: 10 movey: 20; scale: 200
How could I have arbitrarily chosen anything but the image as my ‘distinguished argument’?
Would one define messages scale:, rotate: and move-x:movey: for the integer class, taking an image as an argument? I don’t think so.
The fact that you CAN represent functions using an OO-style SYNTAX doesn’t seem like a compelling criticism of OO design.
There is no “criticism of OO design” in this post. I don’t know where you came up with that.
O-O is intuitive primarily because of the way most of us have been taught programming (which is an “unnatural” activity, in case you hadn’t noticed). The easy, “intuitive,” and popular / commonplace ways of doing things are not always the best; as a profession, we were led down the computer-as-machine path long ago (due to von Neumann architectural thinking). But that doesn’t make it the only way, or even the best way.
O-O as manifest in Java and C# (which together capture much of the programming market) is imperative / procedural with design choices forced on you up-front: you must choose a distinguished argument. In some cases, that’s easy and natural; in other cases, it’s not. One could make a strong argument that the history of mathematics and logic (especially symbolic logic) point to predicates and relations as basic, and that any grouping of predicates into sets associated with distinguished arguments is premature de-optimization.
Every program is a model; the question is what we’re modeling. For simulation, modeling real-world entities makes some sense, and most domains have some entities like that. There are a great number of other “business rules” that straddle objects and have no natural home, so you end up with “service” and “helper” and “utility” and “mix-in” object classes, none of which are very object-oriented.
I like this discussion – thanks for starting it.
I also find it extremely interesting that modern hardware architectures – particularly increased opportunities for parallelism (and the concurrent methods it requires) – are directing programmers to avoid state-driven designs, typically a hallmark of O-O.
And for O-O fans, I’d also point out that Common Lisp (specifically CLOS) was the first ANSI-standardized O-O language.
Applaud the clear explanations of the benefits of the pure lambda calculus.
However, OOP (subtyping) is not arbitrary, because it enables more deterministic partitioning (divide-and-conquer) of the design space, which can aid in the ability to reason about large design spaces (imagine the entire body of software being granularly reusable), as compared to (Haskell’s or Scalaz’s emulation using implicits) structural subtyping (ad-hoc polymorphism).
I am working on a granular approach to mixing the pure lambda calculus and subtyping.
P.S. I got straight As in high school and university, completing several university level math courses (Linear Algebra, Probability & Statistics Theory, etc), and completed first semester of Calculus at the local college while I was still in high school.
I’m not convinced that subtyping and OOP have anything to do with one another.
Concepts of OOP:
http://en.wikipedia.org/wiki/Object_oriented_design#Object-oriented_concepts
So subtyping is the polymorphism concept.
Do you think that arbitrary subtypes (e.g. a collection data structure) of an interface (e.g. applicative, traversable, etc) should not be interchangeable by accessing their shared interface signature?
Or do you mean that implicitly matching an interface to an arbitrary implementation via structure (i.e. structural subtyping) is superior to explicit inheritance?
As a possible example where implicit subtyping might not work, I haven’t thought about how I would code my solution to eliminating exceptions without explicit subtyping:
http://copute.com/dev/docs/Copute/ref/std/SignedState.copu
http://copute.com/dev/docs/Copute/ref/intro.html#Exceptions
Does Haskell have a private instance constructor?
I think it is important to note that OOP and imperative programming are orthogonal concepts (the quote of Jason in the article appears to have conflated them):
http://en.wikipedia.org/wiki/Referential_transparency_(computer_science)#Contrast_to_imperative_programming
Imperative programming is the antithesis of referential transparency, in that the former must be evaluated in a specific order. Whereas, the OOP concepts encapsulation (i.e. information hiding), inheritance, interface, and polymorphism can be referentially transparent.
There is an equivalence (not a dichotomy) between FP and OOP in terms of the “Expression Problem” (Wadler), in that it can be solved by either adding new functions or case classes respectively.
So imperative programming is the “evil” which FP should be criticizing, not OOP.
“Imperative programming is the antithesis of referential transparency”
No it isn’t. See the referentially transparent imperative program in the post. I recently gave a talk titled “Purely Functional Imperative Programming”. Pure and imperative are orthogonal concepts. This is not to say that FP and OOP are somehow opposites either. As far as I’m concerned, if you program with referentially transparent expressions, you’re doing FP. If you call your dictionaries “objects”, I’m OK with that too.
The disagreement is about definitions. Imperative programming employs side effects and thus is the antithesis of pure functional programming which does not:
http://en.wikipedia.org/wiki/Functional_programming#Comparison_to_imperative_programming
Perhaps you are emphasizing imperative vs. declarative style?
http://en.wikipedia.org/wiki/Imperative_programming
Although I wasn’t able to find and view your talk, I guess you are defining “functional programming” to be the inclusive one I linked to in my reply below, “a programming style which composes functions in interesting ways”. I assume you are not using “pure” to mean referential transparency, but rather I guess a purely declarative style? Perhaps it would help to not muddle definitions, by naming non-pure (non-referentially transparent) functional programming as “functional programming style” and not “pure functional programming”:
http://en.wikipedia.org/wiki/Functional_programming#Coding_styles
I am wondering whether a purely declarative style is always referentially transparent.
No wonder so many people can not understand, when the definitions are muddled. I think it is best to not overload the meaning of “pure”. Pure should only mean referentially transparent.
I say “functional programming” to mean programming with pure functions. There is nothing else that I call “functional programming”.
I say “imperative programming” to mean programming with imperatives. This can mean, for example, composing Kleisli arrows, which would be completely referentially transparent. I don’t take “imperative” to imply side-effects.
There’s no muddling going on here.
What is your definition of “imperatives” then?
Let me refer to the reply I made below:
My current understanding is that the State monad composes pure morphism functions, but the composition is order-dependent (i.e. imperative and not referentially transparent) for the pure morphism functions that input and return modified state (and the composition is order-INdependent, i.e. pure, for the portion of the composition that is for pure morphism functions that do not input state).
Are you not confusing the imperative composition with the pure functions being composed?
I think imperative is always order-dependent. Can you show me otherwise?
“What is your definition of “imperatives” then?”
In a purely functional setting, they are state transition functions, or more generally, Kleisli arrows.
The State monad composes ordinary pure functions. There is no magic going on there. Composition in the State monad is pure, but also order-dependent. The order is imposed by binding. Here’s the type of the binding combinator for State:
(=< (a -> State s b) -> State s bIf we expand the State type constructor, the type of Kleisli composition looks like this:
(s -> (a, s)) -> ((a, s) -> (b, s)) -> s -> (b, s)That generalizes to this:
(a -> b) -> (b -> c) -> a -> cWhich is just ordinary function composition.
“Composition in the State monad is pure, but also order-dependent. The order is imposed by binding.”
The morphism functions are not required to execute in the order given by the nested ‘bind’ (=< b:
f( g( h x ) )
Remember functional programming is all about reuse and not repeating oneself. Thus the State monad allows us to compose functions which do not operate on state with those that do, via the ‘unit’ function.
The morphism function, k, is not order-dependent if it has a type of, a -> b, because Haskell will infer that return value of k must be lifted with ‘unit’. Thus, k a, can be called at any time irrespective of the value of the state s. Also k b can be called at any time too, etc. Which is why I wrote above that in terms of memoization potential, it is the same as if the state wasn’t even being threaded:
f( g( h x ) )
Which you agreed to:
“(a -> b) -> (b -> c) -> a -> c
Which is just ordinary function composition.”
For novice readers (not you Rúnar), see here the example with ‘tick’, note the implementation for ‘bind’ (the * star) calls, k a y, so currying can call k a, then call unit on the result, then apply y to the result:
http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf#page=9 (see section 2.8 on pg.9)
Okay, I realize on first read, my assertion sounds like nonsense, because the nested ‘bind’ (=< b, might be reused else where (very likely they are, since FP encourages reuse and not repeating oneself), so via caching (e.g. memoization) their order-of-execution is not necessarily the same as the order in a particular nested ‘bind’ (=< State s b, they depend on the order of the nested ‘bind’ (=<<) and thus the composition is imperative (relative to the state composition), not pure (even if the morphism function is pure).
One might be tempted to argue that the COMPOSITION of the pure functions which operate on the state are not imperative, because they could potentially also be cached via memoization. But that is relative to two identical computations of the state. That is analogous to the ludicrous claim that an imperative program is pure if we run it twice in the exact same global state (environment or inputs).
So that is why I said when you print to the screen in your example, that is an imperative program. The composition of the pure functions is imperative. So I hope it is now clear that imperative means order-dependence relative to the external state, i.e. the antithesis of referential transparency.
I had already explained most of this in my prior reply below, but I was not verbose enough apparently:
Your problem isn’t brevity.
WordPress butchered my reply, because there was symbols that were interpreted as tags. So of course it did not make any sense with most of the important parts missing.
I have reposted the reply with the unintended tags removed.
Let me repost that reply with unintended html tags removed, because wordpress butchered it and big chunks were missing:
“Composition in the State monad is pure, but also order-dependent. The order is imposed by binding.”
The morphism functions are not required to execute in the order given by the nested ‘bind’, because they are pure and due to caching of function return values (i.e. memoization).
The state monad is imperative relative to the COMPOSITION of the state, which can be completely orthogonal to the memoization of nested bind sequence of functions of type, a -> b:
f( g( h x ) )
Remember functional programming is all about reuse and not repeating oneself. Thus the State monad allows us to compose functions which do not operate on state with those that do, via the ‘unit’ function.
The morphism function, k, is not order-dependent if it has a type of, a -> b, because Haskell will infer that return value of k must be lifted with ‘unit’. Thus, k a, can be called at any time irrespective of the value of the state s. Also k b can be called at any time too, etc. Which is why I wrote above that in terms of memoization potential, it is the same as if the state wasn’t even being threaded:
f( g( h x ) )
Which you agreed to:
“(a -> b) -> (b -> c) -> a -> c
Which is just ordinary function composition.”
For novice readers (not you Rúnar), see here the example with ‘tick’, note the implementation for ‘bind’ (the * star) calls, k a y, so currying can call k a, then call unit on the result, then apply y to the result:
http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf#page=9 (see section 2.8 on pg.9)
Okay, I realize on first read, my assertion sounds like nonsense, because the nested ‘bind’ depends on the output of the bind it is nested within. But here is the epiphany. Realize that those pure morphism functions of type, a -> b, might be reused else where (very likely they are, since FP encourages reuse and not repeating oneself), so via caching (e.g. memoization) their order-of-execution is not necessarily the same as the order in a particular nested ‘bind’ sequence. Thus the composition is pure, not imperative.
Whereas, for those morphism functions which do operate on the state s, a -> State s b, they depend on the order of the nested ‘bind’ and thus the composition is imperative (relative to the state composition), not pure (even if the morphism function is pure).
One might be tempted to argue that the COMPOSITION of the pure functions which operate on the state are not imperative, because they could potentially also be cached via memoization. But that is relative to two identical computations of the state. That is analogous to the ludicrous claim that an imperative program is pure if we run it twice in the exact same global state (environment or inputs).
So that is why I said when you print to the screen in your example, that is an imperative program. The composition of the pure functions is imperative. So I hope it is now clear that imperative means order-dependence relative to the external state, i.e. the antithesis of referential transparency.
I had already explained most of this in my prior reply below, but I was not verbose enough apparently:
Replace “equivalence” with “duality” (the mathematics definition, not the “dichotomy” definition where dichotomy means logical opposite complement or mutually exclusive contradiction). FP and OOP are not dichotomic paradigms (rather they are orthogonal, i.e. mutually independent, and can be mixed), and they are duals in terms of their equivalent ability to solve the “Expression Problem”.
http://en.wikipedia.org/wiki/Duality_(mathematics)
Note, above I am referring the exclusive notion of FP, i.e. referential transparency. There is also an inclusive notion of FP which muddles definitions and understanding (and leads to conflation of terms):
http://www.artima.com/weblogs/viewpost.jsp?thread=166742
Also, replace “or case classes” with the more general “or subtypes”.
http://beust.com/weblog2/archives/000490.html (read from Brian Slesinsky’s comment down)
http://lambda-the-ultimate.org/node/2927#comment-43268
Note that I am also referring to the “exclusive notion” of FP. You can write imperative programs composed entirely of referentially transparent expressions, i.e. it is a sequence of referentially transparent imperatives. If you do this you are doing both imperative programming and functional programming. There is no dichotomy there.
Is there a point you’re trying to make?
The point is the one I already made. Imperative is always the antithesis of side-effects-free. Pure (referentially transparent) is never imperative and vice-versa. They are dichotomies, i.e. mutually exclusive. If I am wrong, I would appreciate an example? (see discussion of your example below)
1) Unless I have misunderstood your description of your point-of-view, it seems you are referring to the inclusive notion, which may be more clear from reading #2 below.
2) Order-of-execution dependence (i.e. imperative) is not side-effects-free, and thus is not pure FP. If your sub-expressions are pure FP, but your composition of them is imperative (sequenced in an execution order), then the dichotomic paradigms composition is not pure (even though the sub-expressions are), i.e. they do not mix without choosing one of the contradictions. If the composition of the pure FP expressions is not execution order dependent, then it is pure and not imperative. Note, I assert that it is possible for a pure function to contain imperative composition which calls only pure functions (the rules I am working on have a few more requirements), thus the contradiction shifts back to pure (this is what I mean by my work on a granular mixing), yet while the function is pure, the internals of the function remain order-dependent and impure.
Referential transparency means the function call can be replaced with its cached return value, any where in the program it was called. It thus follows that order-of-execution does not matter, except in a trivial case. In pure FP, the hierarchy of function calls dictates an order-of-execution only where there is no reuse of a function, because the compiler is free to compute and cache values of a sub-function call before executing its caller, and to execute a pure function with different sets of arguments concurrently.
Rúnar said:
“Pure and imperative are orthogonal concepts”
Disagree, they are dichotomies, i.e. mutually exclusive (dependent because they are contradictory, can not be mixed without one overriding the other). Orthogonal means mutually inclusive (independent, freely intermixed without either paradigm contradicted).
Rúnar said:
“See the referentially transparent imperative program in the post.”
I assume you are referring to where you wrote in the article, “We can also do “OO” in Haskell…”.
a) Your example is using a monad (with ‘do’ syntactical sugar to obscure the nested ‘bind’ calls) to abstract side effects. Although abstraction is an “OO” concept, I assume your point is that purely functional can be written in an imperative style. Let’s not conflate “OO” with imperative here, as OOP is orthogonal (not mutually exclusive) to pure FP, i.e. they can be intermixed without a contradiction. Whereas, imperative programming can not be mixed with FP (i.e. not mutually inclusive) without causing some level of the composition to be impure.
b) That example is imperative and not purely functional, because it has side-effects (e.g. printing to stdout). Yes, you can force Haskell to do impure imperative code.
Whereas, for example the State monad can be used to simulate global state in a purely functional (non-imperative) paradigm, i.e. only the pure functions in the composition that access the state are imperatively composed (order-dependent), and pure functions (that do not access the state) remain order-independent, when composed with the former using ‘bind’. Here is an excerpt from my work on State monad which is not yet uploaded to my site.
// When exclusively not composing impure morphism functions that operate on state (i.e. that do not return a copy of modified state),
// the state monad composition of morphism functions (using ‘bind’ and ‘map’),
// isolates the order-dependency drawback of global state to those pure morphism functions that operate on state,
// and any composed pure morphism functions, that do not input state, remain order-independent.
// Thus the state monad is a granular composition concurrent programming paradigm.
You talk a lot and say little.
“The point is the one I already made. Imperative is always the antithesis of side-effects-free. Pure (referentially transparent) is never imperative and vice-versa. They are dichotomies, i.e. mutually exclusive.”
Nonsense. Imperative programming is just Kleisli composition.
“If I am wrong, I would appreciate an example?”
This is an imperative program with no side-effects.
“Order-of-execution dependence (i.e. imperative) is not side-effects-free”
I think you’re conflating “order-of-execution” with ordinary causal sequencing. In the expression
f (g x), is it important that we executeg xbefore applyingfto it? In order to evaluate the expression,g xhas to be substituted into the body off, and before we can know the value off (g x), we have to know the value ofg x.In the expression
readLn >>= putStrLn, it is not important whether we evaluate readLn or putStrLn first. What is important is that readLn results in a String that the evaluation of putStrLn depends on. The sequencing isn’t imposed by any side-effects. It’s clear when you look at the type of(>>=) :: m a -> (a -> m b) -> m b. The second action requires theafrom the first action (of typem a), and you can’t have the second action (of typem b) at all until the first action has been evaluated.“This is an imperative program with no side-effects.”
No, it is a pure program.
That is why I asked you what your definition of “imperatives” is, because it seems your eyes are fooled by the do syntactical sugar. The types of the pure functions determines whether they are composed purely or imperatively, not the ordering of the syntactical sugar. That composition flexibility is the beauty of the State monad, as I explained already.
“You talk a lot and say little.”
I am thinking you did not yet have the epiphany, so you did not absorb what I wrote. Let me try to clarify below.
“I think you’re conflating “order-of-execution” with ordinary causal sequencing. In the expression f (g x), is it important that we execute g x before applying f to it?”
No, I covered that already in my prior reply. Concurrency in the pure lambda calculus is only possible when we reuse functions more than once. The key is that order is not forced when there is reuse, we can calculate the same function concurrently or in opposite order, e.g.
f( g x )( g y ) // or for those who prefer the notation f( g( x ), g( y ) )
“The sequencing isn’t imposed by any side-effects. It’s clear when you look at the type of (>>=) :: m a -> (a -> m b) -> m b. The second action requires the a from the first action (of type m a)”
You are confusing the purity of the functions being composed with the purity of the composition. Indeed the the types of the functions determines whether they are dependent on the prior ‘bind’ call, but some uses of a monad, a = b. For those cases, the composition is pure and not imperative.
As I said above, do not be fooled by the do syntactical sugar, the types of the composition control whether the composition is pure or imperative. Pure and imperative are opposites. Please try to understand.
Also I forgot to say that printing to the screen (twice) is order dependent. I think you agree there is order-dependence in the example in your article.
I am in rush here and I misstated about a = b. The only relevant point is that the types of the morphism function determine if the composition is pure or imperative. I will try to follow up with a clear example later..
OK, so in your view “imperative” = “not pure”. I got it. There’s no epiphany to be had here.
In my view “imperative” = “monadic”. You can be dishonest about your types, in which case you’re not being pure.
“do not be fooled by the do syntactical sugar”
Do not be condescending and pedantic. The syntax has nothing to do with anything.
“There’s no epiphany to be had here”
Please read the latest reply:
“The syntax has nothing to do with anything”
Agreed. So are you missing the epiphany that the morphism function for the state monad is not imperative relative to the state if it doesn’t operate on the state (see link above)? Seems that you are stuck on the superficial sequential order of the binding, but that has nothing to do with order-of-execution relative to the state of the state monad, for morphism functions of type, a -> b.
Imperative is always relative to some state:
http://en.wikipedia.org/wiki/Imperative_programming
“In my view “imperative” = “monadic””
Agreed but only relative to the state of the monad, and only if the state is being used impurely any where in the computer.
Monadic binding is to abstract away the state of the monad, so we can compose with functions of type, a -> b, which know nothing of the state, with functions of type, a -> m b. For example the Maybe monad. The functions of type, a -> b, compose purely and the state of the Maybe monad gets threaded across their composition. So the Maybe monad binding has the potential to be imperative only when a function returns a Maybe, but unless Maybe is used impurely somewhere, then this is still pure code, not imperative.
Can you cite any canonical source that defines imperative as not relative to a state that is used impurely? I think it is common knowledge that imperative means order-dependence due to use of state in non-referentially transparent contexts. So if your IO Monad is reading the keyboard, but another program can eat keystrokes, then accessing the state in your IO monad is imperative. Imperative is all about not being able to compose things safely. Pure is the opposite.
“You can be dishonest about your types, in which case you’re not being pure.”
Agreed. If the IO monad is lying about the referential transparency of the state relative to other things the code might want to compose with, then you’ve got imperative code. This is why I said the print to screen is imperative, because it depends on the state of other parts of the same program that might try to write to the screen, which destroys the order-independence of the program.
Sorry I been awake too long, so getting lazy to condense my writings. Hope we understand each other now.
Let’s have an end to this. It sounds like you’re just repeating yourself.
The purity of an imperative program is up to a given interpreter. See what I mean here:
where I give two implementations of an IO monad, where the same program is interpreted in two different ways. One pure, the other impure.
You would have it that the program suddenly becomes imperative when an interpreter turns it into side-effects. I contend that the program is imperative regardless, even if its interpretation is pure.
That’s the whole content of this conversation. I don’t think there’s anything else to be said.
Agreed. Thanks for the discussion.
After my terse reply that said “agreed”, you edited your comment and added everything from that that sentence down.
Agreed, because the state of your IO monad exposes itself to the possibility of being composed impurely.
This is just Coase’s Theorem, that it is impossible construct a barrier to external state in a Turing complete calculus.
Note that the monadic composition of functions of type, a -> b, e.g. (a -> b) -> (b -> c), is not imperative unless C is exposed to external impure composition, because their order of execution is not exposed. That is my point.
I hope you see now that is not what I am saying. I am making a distinction between the order of normal pure function composition which is not exposed to the external composition, and the state (e.g. of a monad) which is.
Remember I asserted that the the types determine impurity (a/k/a imperative). Your IO monad which has side-effects is impure. I assume you get away with that in Scala because it does not check for impurity. I didn’t study your example, but in the language I am designing (Copute), you won’t be able to create external composition side-effects in the IO Monad without declaring bind to be impure.
Jesus Rollerskating Christ, man.
Haha. Thanks.
Blame God for Godel’s second incompleteness theorem for the inability to declare a consistent theory of the barrier between pure and imperative.
Pureness is relative (to lack of imperative), like everything else existential. Read Hume.
Impure composition of a pure API can render the order-independence within the pure code imperative relative to the external state. If I accepted your notion of imperative, then everything is imperative, and there is no such thing as pure code. Rather I place the barrier at the border between the pure API and the impure composition, which is deterministic relative to static typing.
You place the barrier for some arbitrary reason on pure monadic composition, which orders the monad state purely, which is not conceptually different than how normal function composition orders the final return value (which could also be considered a state and composed impurely).
I think I had a mistake. As long as the State monad is pure, the imperative code is not the monadic binding of functions that access the state, but rather any impure composition of the resultant state. The IO monad is obviously impure as soon as it calls a system function.
The IO monad is not impure in any way. What is impure is anything of type
forall a. IO a -> a. So according to your thesis, unsafePerformIO is imperative and readLn is not. But that’s silly.Stop saying words now. Thank you.
Definitions:
‘pure’ = referentially transparent
‘impure’ = ‘imperative’ = not referentially transparent = referentially opaque
Rúnar said:
Thus, you are claiming that ‘imperative’ = all pure function composition, h : (a -> b) -> (b -> c) -> a -> c; h f g x = f( g x ). Thus you are claiming that ‘imperative’ is not distinguishable from pure FP.
The proof for the state monad, is the morphism function m : a -> State s b; m t = \x -> g (t,x), may call a function g : (a,s) -> (b,s). The monadic binding is pure function composition on the tuple, e.g. f( g (a,x) ).
That the ordering of pure function composition can produce a final result of type c or (c,s), is irrelevant to the concept of ‘imperative’.
My initial succinct comment was correct, ‘imperative’ is the antithesis of purity– there is no other definition that gives imperative any meaning. My followup reply correctly predicted that your definition of imperative is muddled.
My further verbose replies were an attempt to try to understand how you could distinquish some forms of ordering of pure functional composition from others. I was trying to understand and explain what significance you could apply to the abstraction of a monad. The monad abstracts (wraps) some state or computation, so that it is possible to compose functions which map unwrapped types, a -> b, with those that map wrapped types, a -> m a. I explained that for example for the state monad, the composed functions of type, a -> b, do not operate on the state, thus they certainly can’t be ‘imperative’ relative to the state. And as I proved above, the composition of functions of type, a -> State s b, is also pure function composition returning a tuple. You try to make a distinction that monadic ordering determines the result tuple, but the ordering of any pure function composition determines the result. There is no distinction.
The bottom line is that ‘imperative’ is any function that is not referentially transparent. Period. No corner cases, no muddled definition that has no meaning.
In my next comment, I will explain why the IO monad is impure and thus ‘imperative’, even in Haskell.
The IO monadic composition in Haskell is claimed[1] to be pure because the World (as abstracted by IO a), and not an instance of type a, is an input and output for each action function, i.e. it is assumed that for a given state of the potentially infinite state-machine in the World, the same World state will always be returned[2]. The problem here is that the World state includes time, and thus it never has the same state. This is what I was referring to when I mentioned Coase’s and Godel’s theorems. The lambda calculus requires the function to be beta-reducible[3], but the structure of the World is never considered by the Haskell type checker[4][5]. Thus this is a hack to claim[1] that side-effects don’t matter to purity, by assuming that the World input type of the of IO action function is computable, but never having the compiler check its infinite structure. In short, the World’s structure is uncomputable, which relates to undecidability and the Halting theorem.
So the IO monad is actually impure (i.e. ‘imperative’) and Haskell is lying about it[5]. There is analogy to virtual methods, which at compile-time comply with the variance of Liskov Substitution Principle for the method parameters and return types, but fail at run-time the pre- and post-condition behavioral semantics of LSP (which is unchecked by most languages). Scala makes it easier to lie about purity, because its type system does not even check for purity, so any kernel function that interacts with the world, is impure.
For a language that allows the declaration of a function’s type to include whether it is pure or not (e.g. Copute), as I previously stated, the barrier between ‘imperative’ (i.e. ‘impure’) and ‘pure’ is the determined by the type of the function (the API).
[1] – [5] The links for the footnotes follow in the next reply.
[1] Section 7, Tackling the Awkward Squad, Peyton-Jones, “this is an important caveat…I have not proved it”
[2] Section 2.2, Tackling the Awkward Squad, Peyton-Jones
[3] http://en.wikipedia.org/w/index.php?title=Lambda_calculus&oldid=433678424#Computable_functions_and_lambda_calculus
[4] http://www.reddit.com/r/haskell/comments/8bhir/why_the_io_monad_isnt_a_dirty_hack/c08s5bc
[5] http://kawagner.blogspot.com/2007/02/why-monads-are-evil.html?showComment=1170781260000#c2061819858844484763
This is my final post to this blog page. I hope this helps you see the light.
The noise-to-signal ratio in your comments exceeds my tolerance.
Okay since you censored my last 2 posts, then I will send you this message via your blog, since I can not seem to find your contact email address any where.
Rúnar wrote:
“Imperative programming is just Kleisli composition”
John Hughes apparently says you are wrong. I assume you know he helped create Haskell, and is very prominent in the field of FP:
Click to access afp-arrows.pdf
Section 1.3 Arrows as Computations, Programming with Arrows
Hughes wrote:
“monads…, help to structure purely functional code, with not an imperative operation in sight”
Note I am publishing all of the censored comments to the web, including those censored by Tony Morris over at his blog. And I am aware of your remark at Twitter:
http://twitter.com/#!/runarorama/status/84026046692851712
“Feeding a known troll: http://t.co/2ezUkL8 ”
Enjoy the bliss.
Rúnar, thank you for uncensoring my 2 posts.
Let me try to close our discussion amicably.
You added that. My verbose middle comments contained some errors (perhaps due to exhaustion made after midnight at end of 18 hour work day in an Asian internet cafe with multiple patrons simultaneously loudly singing different songs for hours, also fighting an amoeba taking flagyl, and I have 1 eye). The last 4 comments were written after I got some limited sleep (woken by a noisy parade).
I just realized why we were talking past each other.
Imperative means non-declarative, e.g. no “control flow”. The ambiguity is in the definition of “control flow”. A pure function creates a state change by creating new state, and not changing the input state. Thus, apparently some claim that pure FP is declarative, thus impurity is (a subset of) imperative.
I could accept that definition. Alternatively, I already implied early in our discussion that I could agree that all non-declarative programming is imperative.
Rúnar, are you saying that only Kleisli composition is imperative? Or, are we in agreement that monadic composition generalizes to normal pure function composition, and thus all pure function composition would be imperative, where you said “state transition” (i.e. state creation) is imperative?
Pure function composition is ordered and causes state creation (“transition”) whether it be in a monad, Kleisli, or otherwise. Your apparent (?) distinction on monadic and Kleisli lead me to believe that you were saying only some FP composition is imperative.
For novice readers, the Kleisli arrow is the function, a -> m b. The arrow “->” is the general function. A function is either impure or pure, thus either changes or creates state respectively. Some forms of declarative programming (e.g. HTML, CSS, etc) is stateless, and (if I remember correctly) this is possible because they are not Turing complete.
Let it go, man. Let it go.
If you’re getting “*** Exception: user error (Prelude.readIO: no parse)” when trying to use the sample code, try getLine instead of readLn.
@Runar: You are retarded dude! :D
Only stupid and delusional people can even remotely believe that FP is anything more than a tool for stupid math people who can’t wrap their heads around OOP.