Why functional programming matters (1990) [pdf]

http://www.cs.kent.ac.uk/people/staff/dat/miranda/whyfp90.pdf

by znt • 11 years ago

113 139 11 years ago

cs.kent.ac.uk

Probably one of the most popular reposts on HN, if you search this title.

This paper was written 25 years ago; have any studies yet justified the extravagant claims made by Hughes and other FP advocates of substantial increases in productivity, correctness, and modularity?

tel15• 11 years ago

There is still no construction of a study that I would think would convince me of those figures. The number of confounders is invariably far too high.

But there are definitions of at least the latter two which are substantially justified via an FP take on the world.

Really, though, I think FP does itself a disservice by claiming to be a "style" of computing much like OO. It's really just a back-to-the-basics take on what "is" computing and from it you can get a very well-behaved foundations of formal languages to build your CS (of whatever brand you like) atop. This has proven to be incredibly fruitful as a theory since, honestly, something like 1907.

l_dopa4• 11 years ago

This is a really important point that I'm not sure I've seen before in a discussion about the adoption of FP. You're completely right, but I can't imagine FP language advocates would get very far by leading with the history of type theory.

erik14th4• 11 years ago

IMO when it comes to productivity most of the time the platform, and by platform I mean documentation, build tools, package managers and such, are a big influence if not the biggest.

From my experience with functional languages, they slack in that aspect.

I like Lisp's simplicity and I like the elegance in Haskell but the only Lisp I know that have a workflow that kinda matches my taste is Clojure, which reeks of java. I tried Haskell several times and I liked the language but I can't stand cabal.

That's why I believe in Go, the language isn't eye popping, but every aspect of the workflow makes me smile and think "that's how you do it".

And by that I mean the no-versioning policy, web stuff built in to the language, and I just love the workspace structure[0].

It is transparent, no need to google to find out where external packages are installed if you want to fiddle with it's source, no worries about version hell, no worries about unicode.

I've read good things about racket in that aspect but I'm yet to try it.

[0]https://golang.org/doc/code.html

cousin_it3• 11 years ago

back-to-the-basics take on what "is" computing... to build your CS (of whatever brand you like) atop

I feel that we've given many years of attention to functional programming, and it's been disappointingly unfruitful in most areas of CS, such as computational complexity, cryptography, machine learning, or computer graphics. Most new ideas coming out of the FP camp are applicable only to FP itself, like monads. We've discussed that before: https://news.ycombinator.com/item?id=8563817

Part of the mismatch is that many interesting algorithms are impure and cannot be easily made pure. I'd like the "foundation" of CS to give a faithful mathematical description of what computers can and cannot do. Is that too much to ask?

But the bigger problem is that FP treats functions as black boxes, and that's just not enough to prove interesting results in most areas of CS. A better "foundation" would try to describe computational behavior and reason about it, instead of abstracting it away. I admit that's a very vague idea, but I'm not smart enough to make it concrete :-)

brians• 11 years ago

The US Navy, 20 years ago: http://haskell.cs.yale.edu/wp-content/uploads/2011/03/Haskel...

Past that: all the correct systems I know were built using formal methods and a mix of functional languages and assembler to reduce the semantic gap.

All the highly productive programmers I know use either functional languages (or logical languages, same reasons) or else very assembler over very tight machine models--and the one using MMIX is an exception.

I think SML makes a good case to have won the modularity front, but there I don't feel as certain.

istvan__5• 11 years ago

The URL proves that for the certain problem that set of people could come up with the best solution in Haskell. This might just mean that whoever was programming in ADA wasn't as good. The sample size is so small that makes it hard to accept it as evidence. Also almost everybody got A in the evaluation, if the others were C or B- I would see it a little bit more relevant.

I am with you, I also think that functional languages the way to go and I almost exclusively using those, but I would not make this big of a jump.

istvan__5• 11 years ago

I agree these are just claims, but when I look at the something like the following it is hard not to see the power that comes from simplicity.

  ;lazy-seq of Fibonacci numbers
  (defn fibo 
    []
    (map first (iterate (fn [[a b]] [b (+ a b)]) [1N 1N])))

You can apply this to a larger set of problems and realize that issues can be solved with less code and that yields less errors. Correctness is also easier to achieve with FP because you don't have the typical problems of non-FP languages (index out of range in a loop for example), I think.

I personally think that the following has much more impact on modern CS than the Hughes paper linked above.

http://www.erlang.org/download/armstrong_thesis_2003.pdf

This is focusing on the reality (operating system threading model, no shared memory across processes -in the Erlang world-, communicate only with message passing, etc.) and this yields to a much higher impact. If you look into Scala features you can find many that came from Erlang, or through Erlang (some of them originally from other languages).

SCP also gave a bigger kick to CS (even though it has very little to do with FP) and it seems that FP languages were adopting it faster (I might be wrong on that).

http://www.usingcsp.com/cspbook.pdf

lectrick• 11 years ago

I was impressed by both of those papers which is part of the reason I decided to focus on Elixir for now.

coldtea• 11 years ago

I agree these are just claims, but when I look at the something like the following it is hard not to see the power that comes from simplicity.

What simplicity? That's even more complex to state than the traditional imperative solution, that's also closer to how mathematicians would write the equation.

alayne• 11 years ago

I can't be the only one who thinks that implementing a toy function in one line of terse code doesn't demonstrate anything useful. What about programming in the large? What about efficiency of naive implementations? What about maintainability? These are things that actually matter in software engineering.

zak_mc_kracken• 11 years ago

it is hard not to see the power that comes from simplicity

Actually, it is quite hard for anyone who's not already versed in Lisp and equipped with some reasonable knowledge of basic FP constructs such as folds.

It's also important to look at the whole picture, and the author of the paper (and FP advocates in general) have this interesting tendency to completely ignore the opportunity cost of using FP and to dismiss the advantages of alternative approaches over FP.

Personally, I think laziness and immutability come at a very heavy price that explains why only the superficial aspects of FP (lambdas) have been adopted while the rest of FP remains the realm of research papers and conferences.

joseraul• 11 years ago

I suspect that the average coder will find Python-style iterators much easier to read.

    def fibo():
        a, b = 1, 1
        while True:
            yield a
            a, b = b, a + b

loup-vaillant7• 11 years ago

I understand why you would demand peer-reviewed experiments to justify productivity, or maybe even correctness. But modularity needs nothing more than a qualitative argument.

It is neither disputable nor disputed, that pure functions are more modular than procedures: their result is independent from the order of their evaluation, and their data dependencies are explicit. That makes them easier to connect to one another.

It is neither disputable nor disputed, that first class functions enable more modularity than first-order functions alone. Just see `map`, `filter`, `fold`, which separate loop structure from loop body, in a way that would require special constructs or macros in first order languages.

It is neither disputable nor disputed, that in the absence of side effects, lazy evaluation is more modular than eager evaluation. Lazy evaluation lets you cleanly separate producers from consumers, by avoiding the full evaluation of what would otherwise be infinite data structures.

You may argue that the claims of increased productivity and correctness are extravagant, but you can not reasonably challenge the massive increase in modularity.

Some claims don't need "studies". Sometimes, a compelling argument is enough.

jonnybgood• 11 years ago

Somewhat relevant: http://danluu.com/empirical-pl

jayvanguard• 11 years ago

The answer is no. I still expect 25 more years of claims with no further proof though. People believe what they want to believe.

mafribe25• 11 years ago

Credible empirical investigations of programming language efficiency are too hard to carry out (though they could be done in principle). However, what we can do instead is look the evolution of programming languages: what features do the latest creations have, what features are older languages retro-fitted with? What ideas have seen little uptake?

(i) Higher-order functions: Yes, slam-dunk win. Essentially all new languages have them, Java and C++ retrofit them.

(ii) Lazy evaluation order by default: mostly dead. All new language use eager evaluation, even SPJ is sceptical that lazy evaluation should be the default. Scala has an interesting approach: eager by default, but you can switch to CBN (although not full laziness) if required. This hybrid form enables you to define control-operators easily, while keeping the simplicity and efficiency of eager evaluation. Exceptions are languages with dependent types that are really theorem provers (e.g. Agda).

(iii) Purity: dead. All new languages have side-effects. The widely used FP languages like Haskell, Ocaml and F# have side-effects. Exceptions are languages with dependent types for Curry-Howard-based theorem provers (e.g. Agda), because there is no convincing Curry-Howard correspondence using state.

(iv) Everything is function application: open. This may work reasonably well in purely sequential languages, but there are theoretical reasons to believe that message passing is not function application (while function application is a special case of message passing).

(v) Types. The answer on this one depends on whether one is a proponent of statically typed languages or not, clearly an unresolved question. For dynamically typed languages, the question is moot, so the rest of the discussion is irrelevant to those who think that static typing is a bad idea.

(vi) Types (1), type inference: Slam dunk winner. All new languages have inference or wish they could have it but don't know how to do it (Scala). There are probably some hard trade-offs between expressivity of types and efficient decidability of type inference (B Pierce termed Hindley-Milner a "sweet spot"), so we might have to tolerate some type annotation being required, e.g. in local or bidirectional inference.

(vii) Types (2), algebraic data types, pattern matching: winner. Most new languages have them in some form.

(viii) Types (3), monadic encapsulation of effects: open. Most new languages have not yet embraced this. Some conceptual problems not yet solved, e.g. destructors for state monads. There are also expressivity problems, e.g. not all effects can easily be expressed as monads, and composition of monads doesn't always work as desired. Moreover there are pragmatic questions about whether monadic encapsulation should be required or optional.

(ix) Types (4), higher-kinded types: open. Not all new languages have them, but HKTs are generally considered useful, but not super important, cf Rust's evolution. If monadic encapsulation of effects is used, then HKTs become highly desirable, cf the recent Scala fork.

   --------------------

Any other suggestions?

platz• 11 years ago

Regarding purity and encapsulation of effects - I would say instead say that it's just not decided if monads are the best mechanism for controlling effects, but there is still a lot of interest in some mechanism for control and reasoning about them.

efnx2• 11 years ago

Purity is not dead. Haskell 'has' side effects but they are explicitly managed. Managing side effects and relegating them to well defined areas lives on in newer languages.

cageface• 11 years ago

I wish more discussions of the values of FP were this pragmatic. FP has brought some very valuable ideas into the mainstream, along with a few bad ones and many for which the jury is still out. I get a little tired of the people that see Haskell, for example, as the One True Way when it's clear it's a language design with its own set of tradeoffs, just like all the rest.

pjmlp• 11 years ago

I agree mostly with all your points.

Regarding lazyness by default, although you are right, I would say the lazy modifier found in Scala/ML derivatives/C#/D and the use of sequences/ranges kind of help half way there.

M8• 11 years ago

"The answer on this one depends on whether one is a proponent of statically typed languages or not, clearly an unresolved question" - I have yet to see a static-to-dynamic transpiler ;-).

lmm5• 11 years ago

Is purity dead? Do you consider Idris a theorem prover? It's dependently typed but seems to be designed for writing operational programs rather than proofs.

Ono-Sendai2• 11 years ago

Purity is not dead. My newish functional language is pure.

tel15• 11 years ago

Really, really have to say I disagree with (iii). Purity is growing more and more day by day. From other comments you seem to have taken a fairly non-standard definition of purity and I'd encourage you to stick with the normal one as it'll let you talk about more interesting things—see further comment on (viii).

I don't think (iv) is open at all. The fact that you can encode everything as function passing is an interesting trick, but it's merely one of several (you can, e.g., also encode everything categorically or via supercombinators and graph reduction, which turns out to be more practical for lazy languages). Function application is just one really well understood semantic foundation.

I find (v) far more subtle than you make it out to be. The standard static/dynamic types divide is silly because both sides are talking about different things. The static side wins completely because honestly, taken at face value, they don't claim that much. All languages are typed, some have interesting type theories, some compilers reject programs which are syntactically OK but violate the type theory.

(viii) is interesting. In my mind, you've conflated this with what most people would call purity---however, monads are merely an implementation of effect typing/purity. Others exist and are experimented with. Also, composition of monads always works as desired... there's no strange edge-case to it. It's merely that they don't compose like functions in a simple way. When you examine what they would entail you learn that they ought not to as well.

(ix) HKTs are sort of a gateway drug to type-level computation. It's remarkable how many languages just more or less let their type-level language wither and die. I'm not claiming that HKTs are a slam dunk victory, but I would be willing to bet that the evolution of languages will lead us to (a) having them universally in the next two decades and (b) wondering why everyone was so hung up on HKTs---I mean, I suppose I can understand singletons, but HKTs? Really?

discreteevent2• 11 years ago

(iv) I come from an EE background so as when it comes to fundamentals I find it a help to think in terms of message passing and transmitters and receivers. It clears up some of the debate for me about which is more fundamental, objects or functions. To me they are all things (transceivers) that transmit and/or receive messages. In the case of a function the transceiver is alive for the duration of the call. In the case of an object or actor it may be alive for longer (and, if stateful, respond in ways that are harder to predict and reproduce)

But this is just a way of thinking that makes me feel comfortable because I like to have a physical model. If someone else is happy with function application as being the fundamental building block then I have no problem with that. However you said that "there are theoretical reasons to believe that message passing is not function application (while function application is a special case of message passing)." I would be interested to get more background on this. Would you have any references for this? Thanks.

dllthomas12• 11 years ago

"Some conceptual problems not yet solved, e.g. destructors for state monads"

I'm not sure what you're talking about here - could you elaborate?

My best guess would be that by "state monads" you mean streaming libraries like pipes and conduit, where there have indeed been some interesting questions around finalization. Calling these "state monads" is surprising enough that I seek clarification, however. Regarding those libraries, I don't know the current status of that discussion (which mostly took place a couple years back) but I do know the libraries themselves are quite useful.

codygman5• 11 years ago

Purity: dead. All new languages have side-effects. The widely used FP languages like Haskell, Ocaml and F# have side-effects.

You don't consider Haskell to be pure? A big win of using monads for side effects was to keep purity right?

nandemo• 11 years ago

Can you quote the "extravagant claims" made in this paper? This is from the abstract:

We conclude that since modularity is the key to successful programming, functional programming offers important advantages for software development

The conclusion section is more elaborate, but I don't see anything there that warrants the label "extravagant".

Ono-Sendai2• 11 years ago

I don't find the parts on lazy evaluation very convincing.

epidemian• 11 years ago

Finally read this paper a couple of days ago. Even though i thought i already understood the concepts of higher order functions and laziness, and had used them on my every-day programming, the paper was still quite enlightening.

One of the things i hadn't considered before is how much laziness can help to build modular code. The last section in the paper, about implementing the minimax algorithm, is a great example of this. The `evaluate` function is first naively defined as a simple chain of a couple of functions that iterate the tree of all possible game positions. Then a series of improvements are applied to it (e.g. pruning the tree to allow the algorithm to work on infinite trees, or ignoring branches that cannot yield favourable moves), but what's really nice is that thanks to lazy evaluation these improvements can be implemented as independent functions that are just "plugged in" the chain, without having to modify the original functions. For example, the original function that generates the whole game tree doesn't need to be changed to implement pruning.

I'd really recommend the paper to anyone who might be wondering "why all this fuss about functional programming?". It's not only very accessible, but also full of beautiful code examples solving very practical and concrete problems. I personally felt a bit sad having to "back" to the imperative programming world in my every-day job after reading it.

tuukkah• 11 years ago

FP and the arguments have evolved in the 25 years after this paper. Laziness by default was important because it forced language and library developers to invent new purely functional constructs such as monads and functional reactive programming. Functional programming has won with lambdas in every language and even mainstream GUIs getting programmed with React.js, pure Flux architecture and Immutable-js.

tormeh• 11 years ago

Given that "anonymous function" is the same as "lambda", please use "anonymous function", because it's self-explaining.

kinow• 11 years ago

Read this paper the first time while working on an Apache project. Shortly after created a sub in reddit, and now it has almost 1.700 users subscribed.

Feel free to share, vote, comment there too :) http://www.reddit.com/r/functionalprogramming/ A very healthy community, lots of interesting stuff in different programming languages.

denim_chicken3• 11 years ago

If functional programming actually mattered we would stop having to remind ourselves why it matters.

Why functional programming matters (1990) [pdf]

Related Stories