12

I've been trending toward functional programming for 4 years now, ever since I first started working with LINQ. Recently, I wrote some pure functional C# code and I noticed, first hand, what I've been reading about functional programs - that once they compile they tend to be correct.

I tried to put a finger on why this is the case but I have not succeeded.

One guess is that in applying OO principals, you have an "abstraction layer" that isn't present in functional programs and this abstraction layer makes it possible for the contracts between objects to be correct while the implementation is wrong.

Has anyone thought about this and come up with the underlying abstract reason for the correlation between compilation success and program correctness in functional programming?

  • 9
    Lisp is a functional language, yet it has no compile time checks to speak of. Same for a few other functional languages. A more accurate characterization of the languages you talk about would be: Languages with powerful formal (at least Hindley-Milner) type systems. – user7043 Nov 19 '14 at 7:31
  • 1
    @delnan I wouldn't say that Lisp is a functional programming language, although it can be used to write functional programming code. Clojure which is a Lisp dialect is a functional programming language – sakisk Nov 19 '14 at 12:06
  • 2
    I agree with @delnan. This statement is more related with statically typed functional programming languages, especially Haskell which uses the Hindley-Milner system. I think that the main idea is that if you get the types right the confidence that your program is correct is increased. – sakisk Nov 19 '14 at 12:10
  • 1
    Functional code can have just as many abstractions and indirections as your typical, mainstream OOP code (if not more). The devil is in the details - less side effects and no null means less invisible state to track and less chances to screw up. Note that you can apply those same principles in mainstream imperative languages, it's just more work and often more verbose (e.g. having to slap final on everything). – Doval Nov 19 '14 at 15:50
  • 1
    Not a full answer but typing of program is crude form of formal verification of program. In general Object Oriented programs have either complicated or very simple type systems as the substitution needs to be taken into account - in most cases they are made unsound for sake of convenience. OTOH the ML-like systems can use CH to full extent so you can encode a proof just in types and use compiler as proof checker. – Maciej Piechotka Nov 20 '14 at 6:16
12

I can write this answer as someone who proves things a lot, so to me correctness isn't just what works, but what works and is easy to prove.

In a lot of senses, functional programming is more restrictive then imperative programming. After all, nothing stops you from never mutating a variable in C! Indeed most of the features in FP languages are straight forward to talk about in terms of only a few core features. It all pretty much boils down to lambdas, function application, and pattern matching!

However, since we've paid the piper in advance, we have a lot less to deal with and we have a lot less options for how things can go wrong. If your a 1984 fan, freedom is indeed slavery! By using 101 different neat tricks for a program, we have to reason about things as though any of these 101 things can happen! That's really hard to do as it turns out :)

If you start with safety scissors instead of a sword, running is moderately less dangerous.

Now we look at your question: how does all of this fit into the "it compiles and works!" phenomena. I think a large part of this is the same reason as why it's easy to prove code! After all, when you write software you're constructing some informal proof that it's correct. Because of this what's covered by your natural handwavy proofs and the compilers own notion of correctness (typechecking) is quite a lot.

As you add features and complicated interactions between them, what's not checked by the type system increases. However, your ability to construct informal proofs doesn't appear to improve! This means that there's more that can slip through your initial inspection and must be caught later.

  • 1
    I like your answer but I don't see how it answers the question of the OP – sakisk Nov 19 '14 at 12:11
  • 1
    @faif Expanded my answer. TLDR: everyone is a mathematician. – jozefg Nov 19 '14 at 16:42
  • "By using 101 different neat tricks for a program, we have to reason about things as though any of these 101 things can happen!": I read somewhere that you need to be a genius to program with mutation, because you have to keep so much information in your head. – Giorgio Dec 10 '14 at 6:57
12

the underlying abstract reason for the correlation between compilation success and program correctness in functional programming?

Mutable State.

Compilers check things statically. They make sure your program is well formed, and the type system provides a mechanism for trying to ensure that the right sort of values are allowed in the right sort of places. The type system also tries to ensure that the right sort of semantics are allowed in the right sort of places.

As soon as your program introduces state, that latter constraint becomes less useful. Not only do you need to worry about the right values in the right spots, but you also need to account for that value changing at arbitrary points of your program. You need to account for the semantics of your code changing alongside that state.

If you're doing functional programming well, there is no (or very little) mutable state.

There is some debate though about the causation here - if programs without state work after compilation more frequently because the compiler can catch more bugs or if programs without state work after compilation more frequently because that style of programming produces less bugs.

It's likely a mix of both in my experience.

  • 2
    "It's likely a mix of both in my experience.": I have the same experience. Static typing catches errors at compile time also when using an imperative language (e.g. Pascal). In FP, the avoidance of mutability and, I would add, the use of a more declarative programming style makes it easier to reason about code. If a language offers both, you get both advantages. – Giorgio Nov 20 '14 at 6:43
7

To put it simply, the restrictions mean there are fewer correct ways to put things together, and first-class functions make it easier to factor out things like loop structures. Take the loop from this answer, for example:

for (Iterator<String> iterator = list.iterator(); iterator.hasNext();) {
    String string = iterator.next();
    if (string.isEmpty()) {
        iterator.remove();
    }
}

This happens to be the one safe imperative way in Java to remove an element from a collection while you're iterating through it. There are lots of ways that look very close, but are wrong. People unaware of this method sometimes go through convoluted ways to avoid the problem, like iterating through a copy instead.

It's not terribly difficult to make this generic, so it will work on more than just collections of Strings, but without first-class functions, you can't replace the predicate (the condition inside the if), so this code tends to get copied and pasted and modified slightly.

Combine first-class functions that give you the ability to pass the predicate in as a parameter, with the restriction of immutability that makes it very annoying if you don't, and you come up with simple building blocks like filter, as in this Scala code that does the same thing:

list filter (!_.isEmpty)

Now think about what the type system checks for you, at compile time in the case of Scala, but these checks are also done by dynamic type systems the first time you run it:

  • list must be some sort of type that supports the filter method, namely a collection.
  • The elements of list must have an isEmpty method that returns a boolean.
  • The output will be a (potentially) smaller collection with the same type of elements.

Once those things have been checked, what other ways are left for the programmer to screw up? I accidentally forgot the !, which caused an extremely obvious test case failure. That's pretty much the only mistake available to make, and I only made it because I was directly translating from code that tested for the inverse condition.

This pattern is repeated over and over again. First-class functions let you refactor things out into small reusable utilities with precise semantics, restrictions like immutability give you the impetus to do so, and type checking the parameters of those utilities leaves little room to screw them up.

Of course, this is all dependent on the programmer knowing that the simplifying function like filter already exists, and being able to find it, or recognizing the benefit of creating one yourself. Try to implement this yourself everywhere using only tail recursion, and you're right back in the same complexity boat as the imperative version, only worse. Just because you can write it very simply, doesn't mean the simple version is obvious.

  • "Once those things have been checked, what other ways are left for the programmer to screw up?": This somehow confirms my experience that (1) static typing + (2) functional style leave less ways to screw up things. As a result I tend to get a correct program faster and need to write less unit tests when using FP. – Giorgio Nov 20 '14 at 6:36
2

I don't think there's a significant correlation between functional programming compilation and runtime correctness. There may be some correlation between statically typed compilation and runtime correctness, since at least you may have the right types, if you're not casting.

The programming language aspect that may somehow correlate successful compilation with runtime type correctness, as you describe, is static typing, and even then, only if you're not weakening the type checker with casts that can only be asserted at runtime (in environments with strongly typed values or places, e.g. Java or .Net) or not at all (in environments where the type information is lost or with weak typing, e.g. C and C++).

However, functional programming per se may help in other ways, such as avoiding shared data and mutable state.

Both aspects together may have a significant correlation in correctness, but you must be aware that having no compilation and runtime errors tells nothing, strictly speaking, about correctness in a broader sense, as in the program does what it is supposed to do and fails fast over invalid input or uncontrollable runtime failure. For that, you need business rules, requirements, use cases, assertions, unit tests, integration tests, etc. In the end, at least in my opinion, they provide much more confidence than either functional programming, static typing or both.

  • This. The correctness of a program can't be judged by successful compilation. If a compiler could understand the often conflicting and inaccurate requirements of every person that contributed to the specifications of the program, then maybe successful compilation could be considered to be correctness. But that mythical compiler wouldn't need a programmer! While there may be a slightly higher overall correlation between compilation and correctness for functional versus imperative programs, it is such a small part of the total correctness judgement that I think it's basically irrelevant – Jordan Rieger Oct 26 '16 at 20:39
2

Explanation for managers:

A functional program is like one large machine where everything is connected, tubes, cables. [A car]

A procedural program is like a building with rooms containing a small machine, storing partial products in bins, getting partial products from elsewhere. [A factory]

So when the functional machine already fits together: it is bound to produce something. If a procedural complex runs, you might have overseen specific effects, introduced chaos, not guaranteed the functioning. Even if you have a checklist of everything being correctly integrated, there are so many states, situations possible (partial products lying around, overflowing buckets, missing), that guarantees are hard to give.


But seriously, procedural code does not specify the semantics of the desired result as much as functional code. Procedural programmers may more easily get away by circumstantial code and data, and introduce several ways to do one thing (some of them imperfect). Typically extraneous data is created. Functional programmers might take longer when the problem gets more complex?

A strong typed functional language can still do better data and flow analysis. With a procedural language, the goal of a program often has to be defined outside of the program, as a formal correctness analysis.

  • 1
    Better anology: Functional programming is like a help desk without customers - everything is wonderful (as long as you don't question the purpose or efficiency). – Brendan Nov 20 '14 at 8:33
  • @Brendan car & factory does not form such a bad analogy. It tries to explain why (small scale) programs in a functional language are more likely to work and are less errorprone than a "factory." But to the rescue of say OOP comes that a factory can produce several things and is larger. Your comparison is apt; how often one hears FP can parallelize and optimize hugely but in effect (no pun) delivers slow results. I still hold to FP. – Joop Eggen Nov 20 '14 at 8:55
  • Functional programming at scale works quite well for a en.wikipedia.org/wiki/Spherical_cow Keep it local. – Den Nov 24 '14 at 9:55
  • @Den I myself would fear no feasibility problems working on a large scale FP project. Even love it. Generalisation has its limitation. But as that last statement is a generalisation too... (thanks for the spherical cow) – Joop Eggen Nov 24 '14 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.