News for hackers. Stuff that matters.
Re:Some Functional Programmers Are Arrogant by catnaroek on Wednesday July 08, 2015 @08:58PM (#9855633)
> But there is much to be said against PFP itself (and much to be said in favor) like the lack of clear execution models, the lack of clear thread context (which is, of course, related), the difficulty in analyzing computational complexity, in debugging and profiling, and implementing many simple algorithms. Many of those are related to laziness more than referential transparency itself, but RT necessitates laziness in some cases, whether the language itself is strict or not.

Don't blame purely functional programming and referential transparency, which are unquestionably good ideas, for the downsides of laziness, which is indeed a bad default. Purely functional programming doesn't need laziness, and, in fact, is much better off with a formal distinction between values and computations, as in the call-by-push-value paradigm [0]. Pervasive laziness actually has negative consequences for equational reasoning, because it forces all free variables to stand for potentially nonterminating computations. To restore the practicality of equational reasoning, Haskellers often have to pretend free variables only stand for productive computations (that big-step-reduce to a term in WHNF), but this assumption is completely unwarranted by language itself.

> "wherefore referential transparency". If it is to avoid problems caused by shared mutable state, then there might be better ways, like making shared state transactional to some degree (Clojure, Erlang).

Although it doesn't exactly have transactions, Rust's strict aliasing and mutability controls is a much better argument for "there are better ways to avoid the problems of shared mutable state". Clojure and Erlang take the easy route of making the consequences of your bugs less catastrophic [1], but do very little to actually avoid concurrency bugs.

> If it is to make automatic verification better, then there might be easier ways (like some of the many model-checking methods)

Model-checking doesn't scale to truly large state spaces. Typeful purely functional programming is, to a large extent, about trimming the state space to exclude nonsensical stuff.

> and if it is to make human reasoning better, one should ask whether equational thinking is really the best way for people to think about programs

Yes, equational reasoning is the best way for people to think about programs. Equational reasoning, being barely more complex than high school algebra [2], is so easy that a normal programmer can do it casually. The most complicated operation you ever have to perform is substitution: replacing all free occurences of a variable by an expression.

> (I think the human mind is much more adept at simulating state than at math, and that an essential, "basic" abstraction such as monad transformers is already too high-order for people to wrap their heads around)

The untrained human mind might be more adept at simulating a single sequence of states than at math. However, even the best trained human mind is comically bad at analyzing classes of sequences of states, formally or informally. In particular, in the formal case, this kind of analysis often requires using logical relations, such as weakest preconditions [3], whose bodies can contain arbitrary quantifiers. Now, as anyone who's used formal methods can attest, rigorously manipulating quantifiers is a bitch - you often have to refer to their formal rules of inference, because it's so easy to use quantifiers wrong if you rely on intuition alone.

> I think that because much of PL research in the last decade has been focused on PFP, people are under the impression that it is somehow more "mathematical" or theoretically sound (not in the logical sense) than imperative, completely forgetting that fully-verifiable, and theory-supported imperative languages (like Esterel and its descendants) have been used much more successfully in the industry than Haskell and friends.

You're right that it's perfectly feasible to ground imperative programming in a formal foundation. However, as I explained in my previous points, in practice, the formal techniques for reasoning about functional programs are straightforward enough to learn and use by anyone straight out of high school, whereas the techniques for formally reasoning about imperative programs are both cumbersome and subtle - that's precisely why they aren't used except when incorrect programs are completely unacceptable.

> The argument of PFP vs. imperative is important and interesting, and there are both mathematical as well as psychological arguments to be made in favor of each. However, in recent years, many have come to see imperative as pedestrian and PFP as mathematically-advanced, which is completely false.

Again, I partially agree. Imperative programming is far from pedestrian. It's too complicated, in fact, so complicated that the only way we can cope with it is by handwaving away our proof obligation.

---

[0] http://www.cs.bham.ac.uk/~pbl/cbpv.html

[1] Erlang's marketing is very honest about this: Let it crash.

[2] The extra complexity comes primarily from the fact that high school algebra is single-sorted (all free variables are real, or at most complex), whereas equational reasoning in Haskell is multi-sorted (because Haskell has a rich type system).

[3] https://en.wikipedia.org/wiki/Predicate_transformer_semantic...

Re:Some Functional Programmers Are Arrogant by pron on Thursday July 09, 2015 @02:52AM (#9856506)
> Don't blame purely functional programming and referential transparency, which are unquestionably good ideas

I think many people question that they are good ideas. Not pure functions -- but forcing all functions to be pure. If you do that, you are basically forced to use monads for all effects, and that is very questionable.

> Rust's strict aliasing and mutability controls is a much better argument for "there are better ways to avoid the problems of shared mutable state". Clojure and Erlang take the easy route of making the consequences of your bugs less catastrophic [1], but do very little to actually avoid concurrency bugs.

Yeah, Rust does something nice, too, but every operation allowed by Clojure is also allowed by Rust. I don't see how it's any better. Erlang's "let it crash" has nothing to do with data-race bugs. Once you have a GC everything is a lot easier when it comes to concurrency. Rust works very hard to ensure safety without a GC, which is necessary for domains that can't use GCs (like programs in constrained environments). And in any case, I think most people would consider Rust to be even less functional or more imperative (whatever that means) than Clojure.

> Yes, equational reasoning is the best way for people to think about programs.

It's good that you're so certain about this, but I can just as easily say "running your program in a debugger and a profiler is the best way for people to think about programs". How do you know? And nobody has even shown that apriori reasoning is any better than posthoc reasoning (debugger, profiler etc.) Deciding that we must reason completely about our program before we ever run them completely ignores a whole set of useful tools that we have at our disposal.

I also challenge you to program the world's most used sorting algorithm, TimSort, with equational reasoning. And consider this -- Haskell is grossly insufficient to really reason about programs in this way. Idris is the very minimum to even start, and even that doesn't even begin to scratch temporal logic.

> replacing all free occurrences of a variable by an expression.

That is a mathematical argument. Not a psychological one. You could use the same argument to claim that teaching a person to catch a ball is easier if you teach them Newton's equations than let them practice. I mean, we know simply "replacing all free occurrences of a variable" is Turing complete, right[1]? Who says people are good at that?

> However, even the best trained human mind is comically bad at analyzing classes of sequences of states, formally or informally.

And yet 100% of production software in the world, including avionics, medical devices and the like is written in imperative languages. I am not saying this makes your claim outright wrong, but it certainly challenges it, especially considering little evidence exists PFP actually makes things globally better (i.e. not by fixing one undesirable property and introducing another).

> that's precisely why they aren't used except when incorrect programs are completely unacceptable.

But if you want to be honest, you must admit that PFP isn't used anywhere. Imperative verification is much more pervasive. And nobody said people writing programs are willing to invest any extra effort to make them more correct than they believe those programs need be. Programs need to be as correct as they are now only developed at a lower cost (although, if you could offer more correctness completely free -- without any negative consequence -- I don't think people would object).

> It's too complicated, in fact, so complicated that the only way we can cope with it is by handwaving away our proof obligation.

Again, you're thinking about it from a mathematical viewpoint, but mathematics has absolutely zero relevance to whether a programming language is a "good" one or not. It can only promise certain properties, not their desirability. Yes, imperative programming is too complicated for machines to verify in every circumstance, yet claiming it is too complicated for humans pretty much ignores reality (or, at the very least, requires some serious explaining). And where proofs are required, imperative PLs can be just as rigorously proven -- e.g. Esterel, which has been used successfully by the industry much more than Haskell. In other case, I don't see that we have any obligation for proof, and when we do, Imperative languages can do just fine.

What is the source of that obligation? Are, say, provably correct programs more important than fast programs? Than programs shipped soon but are only correct "enough"? Who says correctness is the most important concern? I can tell you that software users certainly don't think so. We had a correctness crisis in the nineties, but the transition to memory-safe languages and wide adoption of engineering practices have pretty much resolved it. It's gotten good enough that continuous deployment, or "how do we ship our software in ever shorter cycles" is now a much bigger concern for most companies than "how do we ensure our software doesn't have bugs". This isn't handwaving but what people actually want. I don't think math can tell them to want something else. It's great that you can build a perfect table, but it doesn't help me if what I need is a chair.

There is one domain, though, where correctness is important even in 99% of software which doesn't require absolute correctness: security. But even with security, memory safety has done a lot to make things better, and where it hasn't, dependent types would be necessary to prove correctness, anyway. You can also help with richer type systems in imperative languages, like Java 8's pluggable type systems[2].

To summarize, I think we know precious little about the relative merits of PFP vs imperative (and by imperative I also mean functional-imperative). Unfortunately, no one has ever used PFP to write any large software other than compilers, so we don't even have the beginning of empirical evidence to even start an educated argument on the subject.

[1]: Well, sort of -- the equivalence between LC and UTM is something many misunderstand. There are plenty of computations that can be expressed by a UTM and not in LC. LC is equivalent because it is powerful enough to simulate a TM (but most certainly not to directly represent any TM program), but from that point on your computational model is no longer simply substituting free variables.

[2]: E.g.: http://types.cs.washington.edu/checker-framework/current/che...

Re:Some Functional Programmers Are Arrogant by tel on Thursday July 09, 2015 @10:35AM (#9858035)
I'm interested what you mean by [1]. The rigorous part of Church's Thesis says exactly that the set of LC-computable, TM-computable, and general recursive functions (nat -> nat) are all identical. This is somewhat weaker that "express", sure, but I'm very curious what you are pointing at when you invoke that.
Re:Some Functional Programmers Are Arrogant by pron on Thursday July 09, 2015 @02:27PM (#9859766)
Parallel or is a classic example. BTW, I'm not implying it's a severe limitation, it's just part of what I see as PFP valuing abstractions over algorithms which -- to my personal taste -- seems like misplaced priorities. The fact that you LC has no good ways of expressing computational complexity is a much bigger limitation, IMO, and another symptom of the same prioritization.
Re:Some Functional Programmers Are Arrogant by tel on Friday July 10, 2015 @12:41AM (#9862326)
I'm curious to see how parallel or is implemented on a TM. It's not a function from (nat -> nat) of course since we're talking about something other than extensional equality... but even then I tend to find these things not terrifically far out of whack.
Re:Some Functional Programmers Are Arrogant by pron on Friday July 10, 2015 @12:13PM (#9864795)
You're right, it's not a function nat -> nat because it depends on program representation. And it's implemented in a universal TM by dovetailing: running one instruction from one input program and then one instruction from the other program and so on back and forth until one of them terminates.

Parallel or is important because it uncovers something interesting: LC works with high-order functions but it can't do high-order programs, namely representing the computation process itself as a first-class entity. LC is not introspective in that sense, and most of its limitations flow from that (including the difficulty describing complexity, which is a feature of the computation process, not of the functions). Again, I'm not well versed in PL theory (or hardly at all), but I think that Lisp's macros therefore actually make it strictly more powerful than LC[1] (I think I may have seen this mentioned somewhere).

Indeed, macros have allowed Clojure to implement stackless continuations, and bytecode manipulation has allowed us to implement full continuations on the JVM without any JVM hacking. Similarly, this kind of direct computation representation allows all sorts of instrumentations and various interesting transformations that are not representable in LC proper (without macros). This isn't at all catastrophic -- you can live without those transformations -- but they can be very powerful and very useful.

[1]: And by "strictly" I mean with direct representation rather than by simulating a TM.

Re:Some Functional Programmers Are Arrogant by tel on Friday July 10, 2015 @02:03PM (#9865625)
Ah, yes. Generally you're right: on 2nd order functions ((nat -> nat) -> nat) TMs and LC differ where TM's have strictly more functionality. But then it flips again at 3rd order (((nat -> nat) -> nat) -> nat) and so on and so forth.

Additionally, you can always just Gödel encode a program, pass it in, get all of this functionality. That might be considered cheating (simulating a TM, although you could just as well simulate LC in both models). This is not actually any different from what the UTM is doing... it's just possible to ignore the difference between interpretation and normal operation because it's all just tape.

Re:Some Functional Programmers Are Arrogant by catnaroek on Thursday July 09, 2015 @03:01PM (#9860005)
Once you have fixed an evaluation strategy, you can talk about time complexity just fine. And, with a substructural type system, you can also talk about space complexity just fine.

So it's not abstraction vs. algorithms. The lambda calculus gives you both.

Re:Some Functional Programmers Are Arrogant by pron on Thursday July 09, 2015 @04:02PM (#9860315)
You're probably right -- I don't have the tools to argue with you -- but you know, as an algorithms person I view this whole abstraction discussion as revolving around UI. To me, UI should be intuitive and never get in your way. I'm appalled to think that I need to spend time learning what a substructural type system is in order to analyze the complexity of my algorithms. I can verify the correctness of my algorithms just fine (to the extent I need them verified, which usually isn't that much, at least not upfront), and so far I have seen zero evidence to support the claim that PFP makes developing software any cheaper. But I see more and more concepts going into abstractions and CH verification that I just can't see the justification for such mental overload standing between me and my algorithms. I'm perfectly happy with a model checker in the very rare cases I need one, and it doesn't require any substructural type systems, or even changing my choice of programming language (there are model checkers that work at the Java bytecode level and verify any program targeting the JVM regardless of the language).
Re:Some Functional Programmers Are Arrogant by tome on Thursday July 09, 2015 @04:02AM (#9856682)
> And yet 100% of production software in the world, including avionics, medical devices and the like is written in imperative languages

Huh?

> But if you want to be honest, you must admit that PFP isn't used anywhere

Eh?

> Unfortunately, no one has ever used PFP to write any large software other than compilers

Whatnow?

Are you exaggerating for rhetorical effect, or do you really believe that?

Re:Some Functional Programmers Are Arrogant by pron on Thursday July 09, 2015 @09:05AM (#9857578)
Sorry, I meant 99.999% and rounded up.

As to the compiler thing -- that is the sad reality. In its 20 years of existence, the largest Haskell program ever written is the Haskell compiler itself. The largest company codebase is only a few million lines of code, and it is comprised of many programs, including a modified Haskell compiler (which, I am willing to bet, is their biggest program). Just for comparison, a medium-sized company codebase is around 50 MLOC. More production code is being produced in 2015 in Delphi, COBOL and Fortran than in Haskell.

This is my biggest problem with PFP: all discussions about its effectiveness are completely theoretical. Calling pertinent evidence "anecdotal" is an insult to anecdotal evidence. There are between 0 and 2 (much closer to 0) data points of large, complex, long-maintained Haskell programs outside the compiler itself (out of thousands of such projects that are started each year). I honestly don't know how effective PFP is, but we can be certain of one thing -- no one else does either[1]. Maybe it's the next big thing as everyone has been saying for twenty years (I remember around that time the talk at my University about how Haskell was about to take over the world) and maybe it's a total dud. Nobody has a clue (and that you've managed to write your API endpoint in two hours instead of two months or whatever isn't evidence of anything; evidence would be writing an air-traffic control system in one year instead of five, and maintaining it for a few years with a changing team of 3 instead of ten).

[1]: I remember that for a good few years most of the industry thought C++ is the best thing that had ever happened to it -- until projects started requiring maintenance. I do not for one second think Haskell is like C++, but vast, undeniably pertinent evidence was proven completely misleading because it wasn't longitudinal enough, let alone, shallow, scattered evidence, which is borderline relevant.

Re:Some Functional Programmers Are Arrogant by catnaroek on Thursday July 09, 2015 @10:20AM (#9857959)
> I think many people question that they are good ideas. Not pure functions -- but forcing all functions to be pure. If you do that, you are basically forced to use monads for all effects, and that is very questionable.

You aren't forced to use monads specifically. What you're forced to do is distinguish pure from impure computations somehow. In the CBPV papers, it's clearly explained that functions are just one particular kind of computation. In CBPV, there's an adjunction between the categories of value types and computation types, and it's this adjunction that gives rise to a monad [corresponding to the effect(s) that computations might exhibit]. If we consider pure computations only [no effects, not even nontermination], this adjunction is actually an equivalence of categories.

---

> Yeah, Rust does something nice, too, but every operation allowed by Clojure is also allowed by Rust. I don't see how it's any better. Erlang's "let it crash" has nothing to do with data-race bugs.

I'm not talking about data races. Of course the absence of sharing in Erlang frees you from data races. But they don't free you from breaking transactional invariants, such as "this doesn't even begin happening unless that condition is met". In spite of the absence of data races, Erlang is still about coping with failure, not outruling it. In Rust, you can use a nonforgeable witness that the precondition holds, and consume it when the operation begins. It's rare that a non-dependently typed language is better than Haskell at something other than performance, but that's exactly what's happening here.

> Once you have a GC everything is a lot easier when it comes to concurrency. Rust works very hard to ensure safety without a GC, which is necessary for domains that can't use GCs (like programs in constrained environments).

Garbage collection makes sharing easy. However, concurrency control (i.e., controlling access to shared mutable resources) remains just as hard. Otherwise, nobody would have invented such things as "global interpreter locks".

> And in any case, I think most people would consider Rust to be even less functional or more imperative (whatever that means) than Clojure.

Indeed, Rust isn't terribly functional (though it's more functional that meets the eye), which is exactly why I said it's a better argument for "there are other ways besides functional programming".

---

> I also challenge you to program the world's most used sorting algorithm, TimSort, with equational reasoning.

Well, in order to use equational reasoning alone, I need a purely functional algorithm.

> And consider this -- Haskell is grossly insufficient to really reason about programs in this way. Idris is the very minimum to even start, and even that doesn't even begin to scratch temporal logic.

Haskell's type system is insufficient to verify equational reasoning using the type system, but equational reasoning is so simple that programmers can do it manually anyway. [More on this later.] On the other hand, programming languages based on dependent type theory, like Idris, while often more beautiful, and certainly more powerful, don't yet pass my bang for the buck test for everyday programming: (0) They force me to annotate things that Haskell can infer on its own. (1) It is a royal pain in the ass to manually translate data between representations that are convenient for proving [e.g., Peano naturals] and representations that are efficient for calculating things at runtime [e.g., machine integers, big integers]. (2) Most dependently typed languages often don't have terribly efficient implementations. To the best of my knowledge, ATS is the only honorable exception to the last point.

---

> That is a mathematical argument. Not a psychological one. You could use the same argument to claim that teaching a person to catch a ball is easier if you teach them Newton's equations than let them practice.

Your analogy breaks when you think about it non-superficially. Merely understanding the laws of physics won't make your muscles strong enough, or your reflexes fast enough to go out there and actually catch a ball. On the other hand, when you've written a program alongside its proof of correctness, well, you've written a program!

---

> Yes, imperative programming is too complicated for machines to verify in every circumstance, yet claiming it is too complicated for humans pretty much ignores reality (or, at the very least, requires some serious explaining).

It's too complicated for humans to verify too. If it weren't, more people would be doing it casually. This is unarguable, unless you've tried it yourself.

> even with security, memory safety has done a lot to make things better, and where it hasn't, dependent types would be necessary to prove correctness, anyway.

I never said that everything has to be machine verified. If you give me a proof that I can understand (i.e., I'm confident I can correctly verify), that's more than enough for me. But, if the proof is past a certain complexity threshold, I'll ask you to convince someone else that I can trust (a better mathematician or a proof assistant).

Re:Some Functional Programmers Are Arrogant by pron on Thursday July 09, 2015 @10:36AM (#9858041)
> What you're forced to do is distinguish pure from impure computations somehow.

Imperative languages can do that very, very easily. The definition of PFP, though, is that it is referentially transparent, i.e. no effects whatsoever (other than monads that are returned to the runtime at the top level).

> I need a purely functional algorithm.

Good luck finding one with the same performance... But the imperative one is now proven to be correct with no need for PFP. Writing a similar provably correct PFP one would have been harder (so it seems to me at least).

> but equational reasoning is so simple that programmers can do it manually anyway.

That's a nice claim. What we know for a fact is that programmers are able to write programs that are as correct as they're required to be with imperative reasoning.

> IT's too complicated for humans to verify too. If it weren't, more people would be doing it casually.

I don't understand exactly what you're referring to, but most programs as correct as people want them to be. The correctness crisis is over, mostly thanks to automated testing.

> If you give me a proof

Who says we want correction proofs to begin with? Most projects require some evidence of some measure of correctness. Certainly not proof of total correctness or even proof of partial correctness.

Re:Some Functional Programmers Are Arrogant by catnaroek on Thursday July 09, 2015 @10:49AM (#9858133)
> Imperative languages can do that [distinguish pure from impure computations] very, very easily.

In an imperative language, can I write a map or filter whose argument is guaranteed to be pure? [Note that my notion of "pure" is stronger than Haskell's: I consider nontermination an effect.] Can you easily convince the type system that an imperative loop will indeed terminate? [Without supplying anything even vaguely resembling a proof.] With pattern matching and recursion, the compiler can check whether recursive calls are always passed smaller arguments.

> Good luck finding one with the same performance...

I'm pretty sure that, with substructural types, it's possible to update a single array element in O(1) in a referentially transparent manner. Conceptually, you're destroying the old array, and creating a new one with the same contents, except for the updated element. But, because the old array won't be used anymore, this can be done in-place. As far as I can tell, no other imperative facilities are needed to sort an array.

> as correct as they're required to be

What does this even mean?

Re:Some Functional Programmers Are Arrogant by pron on Friday July 10, 2015 @03:12PM (#9866118)
> In an imperative language, can I write a map or filter whose argument is guaranteed to be pure?

Of course. See, e.g. Java's checked exceptions. If you marked every effectful function as throwing a checked exception, the compiler can enforce which effects are allowed.

> Can you easily convince the type system that an imperative loop will indeed terminate? [Without supplying anything even vaguely resembling a proof.] With pattern matching and recursion, the compiler can check whether recursive calls are always passed smaller arguments.

Model checkers can do this just as well.

> What does this even mean?

That programs aren't required to be 100% correct, just as they aren't required to be as fast as possible. It is perfectly acceptable for most programs to fail on rare edge cases. If there is an inverse relationship between the manifestation of the bug in the frequency of the circumstances that causes it, then you're fine (put simply: it's OK to fail with ever higher probability on ever rarer cases).

Re:Some Functional Programmers Are Arrogant by tel on Thursday July 09, 2015 @11:47AM (#9858553)
Equational reasoning extends to mutation as long as you track the monad. It also smoothly devolves into Hoare Logic. It's the same tool, just applied in either different (monadic) contexts.

Mutation is not disallowed in PFP, by the way! You can write a perfectly great Timsort that's pure. You just can't pretend that your mutation effects are not observable when they are. (And you can use monads as type cues when that occurs).

Re:Some Functional Programmers Are Arrogant by catnaroek on Thursday July 09, 2015 @12:04PM (#9858717)
In all fairness, Hoare logic just happens to be something I want to avoid doing as much as I can.

Also, you can have a pure Timsort with linearly or affinely typed arrays. Only action-at-a-distance truly requires some framework (monads, algebraic effects, whatever) for embedding an effectul language.

Re:Some Functional Programmers Are Arrogant by tel on Thursday July 09, 2015 @01:51PM (#9859529)
Yup, that's another way to do it so long as you're interested in paying the explicitness tax to introduce substructural types. My point about Hoare logic is not to promote it but instead to note that it's not categorically different from equational reasoning except in that it operates over more complex languages. And then that exactly is your tradeoff.
Re:Some Functional Programmers Are Arrogant by pron on Thursday July 09, 2015 @02:22PM (#9859742)
> You can write a perfectly great Timsort that's pure.

I would be interested to learn how (with the same space complexity?), but anyway my point is that writing a provably correct Timsort using CH is harder than simply proving the imperative algorithm with a model checker.

Re:Some Functional Programmers Are Arrogant by tel on Friday July 10, 2015 @12:43AM (#9862335)
Have a pure model of memory which is implemented directly. Associate this with a proof that the extensional side of it is pure (copying mechanics of substructural types) and you're done.
Re:Some Functional Programmers Are Arrogant by pron on Friday July 10, 2015 @03:12PM (#9866126)
Right, but proving correctness would still be much harder than with the model checker, I think.