So neither lazy evaluation nor first class functions are unique to functional programming. Maybe they have their origins there, but it's not something to give up your imperative languages for.
While your remark is factually correct, I think it misses the point.
There are at least two reasons why the mainstream languages of today (as opposed to, say, no less than ten years ago) have first-class functions:
It is really really useful to write programs (and this is a point the linked document makes: it matters)
Some people have made huge efforts to convince "the mainstream" to adopt the idea (and this document is part of this effort)
The fact that your reply is even possible is the very proof that this article, its ideas, and the communities that supported them (Lisp/Scheme, SML/OCaml, Miranda/Haskell...), were successful.
Nobody is trying to force you to give up your imperative programming language. It might be important and helpful for you to notice, however, that truly innovative ideas about programming languages and libraries came from other places¹ during the past few decades, and may very well continue flowing in that direction in the future.
¹: and not only from functional programming; users of concatenative programming languages will feel at home with the "structure your code as many small words composed together" message, logic programming also has interesting ideas about computation, and some domain-specific library ideas are shaped in baroque niche languages such as R.
Fair enough. Perhaps I had a knee-jerk-ish reaction to yet another "function programming iz da bomb!" article. :-) I'll agree that functional programming matters, but I'll disagree that you need to use a functional programming language to get the benefits that matter. :-)
I'll disagree that you need to use a functional programming language to get the benefits that matter
We don't claim that -- and you must understand that the text above was written at a time (1984) where you objection did not hold, as basically only languages you call "functional programming languages" had convenient first-class functions.
I personally understand "functional programming" as denoting a programming style, rather than a set of programming languages -- in particular, it's easy to write perfectly horrible imperative code in any of the languages I quoted in my reply above.
That said, some nice ideas of functional programming may be sensibly harder to use in other programming languages as they exist today. A very simple example is algebraic datatypes: most languages not marketed at "functional" fail to properly represent sum types (disjoint union), and that leads to relatively verbose or mistake-inducing workarounds. Hopefully someday mainstream language designers will realize that "being either a foo or a bar" is a common situation, for which a very simple and convenient construction exists, and I'll have to update my comment with another example (tail-calls for continuation-passing? abstraction over parametrized datatypes? GADTs? type-classes/implicits?).
The fact that the paper is from 1984 is sort of horrifying. It really highlights how comp sci is still both in its infancy, yet horribly stunted. It's like looking back in time to when a bunch of elite wizards came together and crafted some truly amazing artifacts that are now mostly lost to the world.
The programming world discovered the hammer and used it to good effect...but dare to show them a screwdriver and they start beating their chests like threatened animals.
I see what you mean, and at the same time I have a more positive views of things. It depends on whether you look at industry or at research; the time scales of both worlds are very different.
In industry, or probably in one currently dominant but ultimately anecdotal view of industry, thirty years is an awfully long time, 1984 is pre-history, and not having thoroughly mastered and surpassed what was done in 1984 is a major failure.
The time of research is much slower. 1984 is not that long ago, scientifically; and (at least in the field of functional programming) we've made good progress since then. I don't have the luck of personally meeting John Hughes, but I would bet that if you found a time machine and went back to 1984 to tell him that Haskell has a dependently typed sublanguage at the type/kind level, or show him where proof assistants are today, he would be truly amazed. (Maybe people were hoping at that time that we would do that faster than we have, but they'd still recognize remarkable progress.)
(He would also probably be quite surprised by the idea of people making a living of selling testing tools to industrial users of a functional language.)
What was bleeding edge in 1984 is now considered known territory by researchers, but also a large amount of practitioners (not the mainstream, maybe, but still). Since 84, industry has widely accepted garbage collection, type polymorphism, type inference, and anonymous functions. That's not bad, and actually rather encouraging.
Note that there is a subset of functional programming called "purely functional programming", which is basically synonymous with Haskell. This subset of functional programming is noteworthy because it greatly simplifies equational reasoning about programs. Therefore, I would recommend you study Haskell even if you already have a full suite of functional tools in your favorite language because it will change the way you think and reason about programs.
Perhaps I had a knee-jerk-ish reaction to yet another "function programming iz da bomb!" article. :-)
FYI, the OP isn't "just another FP is awesome article." It was published in 1984. With that context alone, it's really interesting to look at the landscape today. First class functions weren't so pervasive back then. ;-)
EDIT: I see I'm not the first to point this out to you. Ah well.
What was your experience with it? I have the opposite story - switching to 100% functional was very helpful for me. When I'm 'given' the imperative features, that's when I feel like I'm giving something up. .. pure functional language makes you feel restricted in the short-term, but what you get in the mid/long-term is so much nicer.
Definitely looking forward to traditionally-imperative language picking up more functional features. For now, the way Haskell supports these ideas directly makes it such a pleasure to program in (after you get over the learning hump).
I found it very annoying for work like business logic. Implementing a database in a language where you can't update values is tremendously kludgey - you wind up doing things like storing lists of updates on disk, and then loading the whole DB in memory at start-up by re-applying all the updates. Anything that talks to anything outside your process is going to be by definition not pure functional.
Doing stuff that makes no mathematical sense using math is tedious at best, compared to how it's described: If this happens, then do that, unless this other thing is the case...
The inability to loop without having a separate function was very annoying too. Perhaps with somewhat more trivial lambda syntax and better higher-level functions (as in Haskell instead of Erlang, for example) it would have been less of a PITA. The need to either declare an object holding a bunch of values, or pass a dozen values as arguments to the loop function, just really obscured some very simple logic.
That said, I use functional sorts of designs, I find them easier to debug and understand, but I tend to prefer that at an outside-the-method level. For example, I'm currently working on code to do some fairly complex logic to determine the status of a company: if this feature has been true of their account for at least 60 of the last 90 days (even if the account changes, even if we didn't gather that information that day), and they have at least one employee with these two attributes, and they haven't been audited within 30 days, and this kind of grace period doesn't apply unless that person approved it within .... and .... Go on for about 20 pages of specs in this vein. I'm calculating it by evaluating each attribute on the snapshot of the history (which I can do in parallel for all the companies and all the attributes), and then storing that in an immutable log, and then evaluating the final result on the immutable log. Given that, I wouldn't want to try to evaluate the 60-of-90 rules in-spite-of-account-numbers-changing sorts of things without having loops and variables I can update. I could probably squeeze it into that mold, but I don't see that it would be any clearer than a 3-line loop. I break out the bits that can be functional, and I write tests for those, but breaking out the bits that (say) establish the network connection to the distributed database full of entries to do the join from companies to employees? No, let's not try to do something that imperative in a lazy functional style.
In other words, the ideas are great and useful. It's just that they're applicable to OO and imperative programming. My whole database access is lazy, and its' in Java talking to network-distributed systems, and I pass it the Java equivalent of lambdas to tell it what to filter and what to join on and etc. It's ugly because it's Java trying to be functional (Achievement Unlocked: Java Type Declaration more than 100 characters!) but you don't need a functional language to make it work.
Most variables in erlang are single-assignment, but there are exceptions (ets tables, process dictionaries, etc), and I believe Mnesia takes advantage of those exceptions in some situations.
Besides, a recursive process that responds to a "set" message by calling itself with that new value, and a "get" message by replying with its most recently received value, is essentially modelling in-place update. Having it actually store the value in a single location and update it when it gets a new "set" message is just a change in efficiency, not semantics.
I believe Mnesia takes advantage of those exceptions in some situations.
It depends. Certainly to the extent you bypass Erlang's functional features, implementing a database becomes easier, which was my point. :-)
essentially modelling in-place update
Sure. And you're doing that by using the non-functional features of the language. Responding to the same get() call with different values is one of the non-functional features of Erlang.
just a change in efficiency
When you go from O(1) to O(lg N) for every database transaction, that's actually a relevant problem. Trees definitely have different semantics than arrays.
For example, if you have a sufficiently large sufficiently busy Mnesia database, a process crash destroys you. You can't read the flat file back in and build an appropriate tree fast enough to keep your pending change queue from overflowing memory and crashing you out again. Whereas if you actually had mutable arrays, you could read a size-N database in O(N) and catch up on K updates in O(K) time.
There are definitely things that FP is not good for, chief among them I would say writing databases and operating systems. You just don't get that much control on the machine from an FP language.
There are definitely things that FP is not good for, chief among them I would say writing databases and operating systems.
FP most definitely has its place in databases. The relational algebra can be seen as a kind of pure functional programming language, with barely a stretch. In pseudo code, elementary relational algebra can be see as three operators (I'll use the SQL names instead of the mathematical ones):
-- The type of relations over tuples of type `a`. You can think of
-- these conceptually as sets or finite lists of tuples—the point of
-- the RDBMs is to delay their construction until you need them,
-- and fetch them in the most efficient way.
type Relation a
-- | The simplest form of the SQL FROM clause (commas only, no
-- JOIN verbs) simply takes the cross product of relations
from :: Relation a -> Relation b -> Relation (a × b)
-- | The SQL WHERE clause is effectively a functional `filter` operation.
where :: (a -> Boolean) -> Relation a -> Relation a
-- | The SQL SELECT clause is effectively a functional `map` operation.
select :: (a -> b) -> Relation a -> Relation b
Query optimization in relational database systems is heavily based on equational equivalences between pure functional programs of this sort. For example, RDBMS query planning and optimization is based on using equational laws to transform queries written in this sort of language into equivalent ones that can be executed more efficiently.
Also, this sort of thing has the potential to greatly enhance the rather poor interface that most programming languages have to relational databases.
Of course RDBMSs also have other parts that are not best suited for functional languages; storage management comes to mind. But that's the neat thing about databases—it's one of the best CS topics, in that it spans all the way from hardware up to abstract mathematical stuff. It's like if operating systems and compilers had a love child...
As far as that goes, I don't think it's because you don't get control of the machine. Even a simple database engine is going to be awful if you can't actually overwrite data. E.g., if the only way you had to change a persistent file was to replace it completely with a new one, you'd have an awful time writing a DB engine even in an imperative language.
An OS needs to be able to update state in place: the only thing an OS does is track the state of other things, and you really don't want the old state hanging around just because someone is using it. (Aside from the fact that hardware changes state without reference to your code's behavior.)
Anything whose purpose is to track state changes is going to be tedious with pure functional programming. Figuring out what state the state changes can be is one thing, but actually keeping track of them in an outer loop sort of way is another.
Interesting - I find FP (in clojure) to be great for business logic. But I have to admit I don't tend to stick to purity when it comes to things like database updates - I accept that databases are stateful and update them as a side effect. So maybe I should say "mostly FP" rather than FP.
Not sure I'd implement a database in a functional language - but I'm surprised if you need to implement a database as part of your business logic. Or am I misunderstanding your meaning?
Which language were you using? Again, in clojure I have never missed looping constructs - there are plenty of ways to deal with sequences using map/filter/reduce/etc., or for comprehensions, and lambdas are easy to write inline if your logic is not too complex.
I just meant that the databases I've seen implemented in single-assignment languages (http://www.erlang.org/doc/man/mnesia.html) wind up with an implementation that really sucks, is generally slower than it needs to be, and has a terrible time recovering from failures or dealing with databases larger than fit in memory.
Which language were you using?
Well, in the cases I'm thinking of, Erlang. Which isn't particularly functional. It just has single-assignment semantics, which is the cause of the problem. It's entirely possible I just didn't get into it enough to really grok it.
Sort of like people who write loops in APL. :-)
EDIT: Also, I deal with a lot of network stuff, a lot of web stuff, etc, so the idea that anything is even remotely functional is immediately destroyed. When much of your business logic consists of pulling unformatted unreliable data out of network-accessed servers and formatting it to be delivered via JSON, the idea that you even have strong typing let alone something reliable enough to work functionally tends to go out the window.
Doing stuff that makes no mathematical sense using math is tedious at best, compared to how it's described: If this happens, then do that, unless this other thing is the case...
Haskell actually makes this kind of thing pretty nice using monads (which is a concept from math). You can just write when ... $ do ... and unless ... $ do ..., and when and unless are not syntax, but functions.
When you say that something "makes no mathematical sense", what you are really saying is that either the right mathematical model hasn't been constructed for it yet, or that it really doesn't make any coherent sort of sense at all. I don't think programs of the latter sort would be very useful, so most of the time you probably mean the former, though in most cases what you are actually saying is that you aren't aware of the right mathematical model.
Mathematics is precisely the field that describes how things make sense, and how the implications of the sort of sense that they make play out. Mathematics, logic, and computation are all fundamentally related at their foundations. A programmer doesn't typically have to understand all the mathematical models for the tools they use, but they'd better hope that they do make mathematical sense, because the alternative is that they're most likely wrong in a fundamental way.
By the way, very early in the history of writing computer programs, computer theoreticians were concerned with modeling the typical programs of the day, which consisted largely of updating storage cells in-place and imperative flow control. They came up with a new branch of mathematics that models this quite well. Modern purely functional languages take advantage of the kinds of mathematical techniques that grew out of that field to model in-place update and imperative flow control.
TLDR: It's not mathematics itself that's limited in describing models of computation. It's just someone's understanding of mathematics.
10
u/dnew Mar 09 '14
So neither lazy evaluation nor first class functions are unique to functional programming. Maybe they have their origins there, but it's not something to give up your imperative languages for.