Hacker News Reader

Comment by wyager | Hacker News Reader

Immutability is one of many advantages of functional programming. Other advantages include higher-order functions (which Rust cannot support very well with its memory model), stronger type systems (only possibly because the Lambda calculus is on much better mathematical footing than any production imperative language semantics), and better/safer state management via ADTs (which Rust has decent support for).

That's the risk of reading articles like the OP, where they show you a couple functional tricks in an imperative language that inherently can't give you the whole picture. You get too limited an idea of what it means to use modern functional techniques. You simply cannot do anything approaching cutting-edge functional programming in a language like Java or JavaScript or Rust. They all lack some important aspects of what makes functional programming useful.

View on HN

> That's the risk of reading articles like the OP, where they show you a couple functional tricks in an imperative language that inherently can't give you the whole picture.

The other risk is that people (like me, a few years ago) are sufficiently convinced by these simple loop examples that they decide to apply them. This might (or might not) lead to greater functional aspirations which make "whole picture" much more interesting. You might get to free monads, but not before you've used a fold on a list.

Can you explain why Rust "cannot support higher order functions very well?"

I'd also like to hear about "what makes functional programming useful" if you have a minute.

Sure. It's just because when you're passing around functions of type (a -> b) the only fixed-size representation is every possible input/output pair, which is obviously not a good representation. Instead we use a variable-size representation in the form of code (passed around as a code pointer) and captured variables (the format of which depends on the function being passed around). Together these are called a closure. Using variable-sized closures created at runtime requires dynamic allocation, which rust allows for but does not make convenient (intentionally). Sometimes you can get around this but not always. So the kind of stuff you can do with higher-order functions in rust is more restricted and usually has extra rigamorole required for memory management. It's not that rust is doing something wrong, it's just a necessary consequence of having such excellent guarantees about allocation (or lack thereof).

> I'd also like to hear about "what makes functional programming useful" if you have a minute.

This is sort of a book-length topic and I'm on my phone, but a few points worth looking up are (Generalized) Algebraic Data Types, Typeclasses (in particular Functor, Foldable, Applicative, Traversable, Monad (in particular Maybe, Either, and State)), Higher Kinded Types, corecursion, the Y combinator. The gist of it is that you can do a bunch of cool stuff you wouldn't be able to do (or even think about doing) in an imperative language. For some reason we're not entirely sure of, it seems to be way easier to isolate the essence of what we're trying to accomplish when using functional programming than when using imperative programming, and therefore to automate the boring work normally associated with doing things to data, like writing loop definitions.

It's kind of like how natural functional type systems have the same derivation semantics as various logical systems, even though it's not entirely clear why that ought to be the case. We seem to have just stumbled upon an abstraction that meshes nicely with the platonic universe of useful computer programs, as opposed to an abstraction that only exists because of the particulars of how our computers work.

> The gist of it is that you can do a bunch of cool stuff you wouldn't be able to do (or even think about doing) in an imperative language

That's an odd claim and one I've never heard. Surely you can do everything you can with imperative programming as you can with FP, it's just that you will do it differently and, arguably, in a way that will present some downsides (e.g. lack of safety).

Also, for what it's worth, you are enumerating a list of characteristics of functional programming but you're not answering OP's question, which was: what makes FP useful?

Obviously, functional and imperative languages are equivalent in terms of theoretical expressive power. That being said, functional languages often make it easier to build useful abstractions that are more correct. Okasaki's implementation of Red Black trees are an excellent example of this...

How do you define "more correct"?

Sure, the CH isomorphism can help you prove some properties of your code based on its types, but that doesn't mean you can't create an equally correct program imperatively.

> that doesn't mean you can't create an equally correct program imperatively.

You're getting hung up on the fact that the languages are all Turing complete. That's true, but not really relevant. The important thing is that it's much easier to do things correctly with functional constructs like (G)ADTs and strong type systems.

You're preaching to the choir about the superiority of static type systems, but your argument was about imperative vs/ functional, not dynamic vs/ strong.

GADT's and composition are trivial to achieve with imperative languages.

There's a reason not a single production imperative language supports GADTs. Imperative sequencing and mutability semantics, as done in practice, are inimical to rigorous formalization. When imperative language designers try to make a nice consistent type system, they hit road blocks early on and give up. Rust doesn't even support HKTs. GADTs are just an example of something that you rarely see in imperative languages because they almost never even make it that far.

One of the other nice things you get with languages with good functional/pure/immutable(/lazy) semantics are free theorems, where you can actually make strong useful statements about the nature of your program like "this will not crash", "this is memory safe", "this will terminate", "this follows the functor laws", etc. whereas it's effectively impossible to make such claims in a language with messier abstractions like loops and mutable variables.

Basically, the reason functional languages have better type systems is that their underlying untyped semantics are more sensible and simpler than the untyped semantics of mutable imperative (strict) languages, and this is reflected in the safety records of languages through mechanisms other than type safety.

> There's a reason not a single production imperative language supports GADTs.

Scala?

OCaml would also qualify as a counter example, although you cheated a bit by adding all these adjectives and you could argue that OCaml is not "production".

Haskell can easily do imperative as well.

I agree with you overall but I think you're drawing too strict a line between these concepts. Most of the guarantees you obtain from these languages do not even come close to "this will not crash" (this is very hard to guarantee in languages with no totality guarantee, i.e... most of them), let alone "this will terminate" (since most of these are Turing complete).

> Scala?

Well, I'd say Scala is definitely a functional language, but even then its GADT (and even plain old ADT) support is pretty limited and uncomfortable. "Case classes" are one of those things in Scala where it's obvious they're running into the limits of the JVM.

> OCaml would also qualify as a counter example

Again, I'd say OCaml is absolutely a functional language. It's also definitely a production language; I know of a number of firms that use it.

I should have said "Imperative and not Functional languages", a la C, C++, Java, Javascript, etc.

> Most of the guarantees you obtain from these languages

You're right, most of the guarantees you get from e.g. Haskell rely on people following the typeclass laws for whatever you're doing, which isn't necessarily the case. It's not a guarantee in the sense that e.g. Coq or Agda give you a guarantee; it's just a guarantee in the sense that if you follow some simple rules, you get good behavior.

As for totality and termination, it's true that you can't guarantee either in plain old Haskell, but Haskell (and some others) do support checking for pattern match completeness, and then it's not very hard to (informally) guarantee totality by sticking to certain pre-defined operations that operate on data (as opposed to codata) and have good decreasing/tightening rules. For example, if I saw some code composed entirely of functor/foldable/traversable operations over well-behaved data structures, I could be quite confident in correctness and termination.

You can also do anything in assembly. You just won't, practically speaking. "Can do" in that case is shorthand for "is not inordinately expensive and difficult to do".

What I meant was not "you can write programs with FP that you can't in an imperative language" (which is obviously not true); what I meant was "you can syntactically and semantically do things in functional languages that you can't express in imperative languages within a reasonable amount of effort".

> what makes FP useful?

As I said, this is a book-length topic that I can't hope to spell out. The reason I listed those concepts is that learning about them will help to impart understanding of why FP is useful.

> Using variable-sized closures created at runtime requires dynamic allocation,

While this itself may be strictly true, most closures in Rust do not require any allocation at all, and will even possibly get inlined like any other function.

I found this series convinced me I wish I could use FP

http://fsharpforfunandprofit.com/

Specifically the "Why F#" part and within that this article

http://fsharpforfunandprofit.com/posts/correctness-type-chec...

It actually kind of blew my mind (hypebole maybe). Like wow. Not only do I write less code but by language design way more issues are solved .

Kind of like static typing stops certain kinds of issues. FP solves the next level above that.

The interesting thing to me about the FP vs OO discussion that your link highlights very well is that one of the major benefits of FP languages is the expressive type systems that, at least the oo languages I've seen completely lack.

I'm not sure why no mainstream OO language addresses this.

I wish people would stop making this distinction between OO and FP like you can only use one or the other

In imperative languages you typically have to use objects to create functors and other FP primitives

If you reading this as a "OO Programmer" you can benefit your "OO" style code with some "FP" and vice versa

The question I would really ask is have you stopped learning?

It's because OO does not have firm mathematical foundations, so it's much harder/impossible to give OO languages a consistent and powerful type system. Class heirarchies in particular are inimical to good type systems.

A notable exception is Scala's type system, which is pretty expressive. It has been formalized and proven to be sound[0].

[0]: http://scala-lang.org/blog/2016/02/03/essence-of-scala.html

I'm not the OP, but higher-order functions in Rust are a leaky abstraction. Internally, functions are implemented as closures which might capture ownership and potentially duplicate/destroy variables in their scope. This means that there is no single function type in rust, there are several for "use once closures" (which capture ownership of a variable and potentially deallocate it), "linear closures" (which you can't duplicate), "non-linear closures" (normal functions), toplevel functions without environments, closures which allow borrows from their environment to escape, etc.

Which one of these categories your function falls into is a decision of the compiler and might change if the borrow checker improves/regresses.

---

These things are pretty much non-issues unless you make heavy use of higher-order programming. For simple second-order functions such as map/filter/fold it's still easy to wrap your head around all of this. However, experience in Haskell has shown that higher-order functions are a very useful abstraction and if their usage is lightweight and intuitive they pop up all over the place. For instance, parser combinators frequently involve fourth-order functions. At this point you do not want to think about the implementation details that your compiler has to fill in.

At this point, I'm afraid that we will not see a lot of elegant higher-order prorgamming in Rust, because it is potentially so difficult to keep track of the ownership story. I'd be happy to be proven wrong, though. :)

> Internally, functions are implemented as closures which might capture ownership

This seems backwards. Closures are implemented as a struct for the environment, plus a method on that struct that represents the function call.

This then ends up the exact same way as any other function or method call in Rust: with taking self by value, by reference, or by mutable reference.

The environment contains references/copies/borrows of local variables, depending on a number of conditions on the code. Since the environment struct is generated by the compiler, this is different from a method call where you specify the struct yourself.

It's still fundamentally sugar; on nightly, you could write it all yourself.

What exactly are you arguing for? Closures can be implemented using closure conversion as a derived form in most languages. That's how you compile the code in the first place...

The point is that you reason about closures as ordinary functions with local assumptions. You don't need to know how they are implemented at all. On the other hand, in Rust you need to be aware of the implementation in order to use higher-order functions effectively.

I'm arguing that the statement I quoted in my above comment is incorrect; closures are implemented with functions, not the other way around.

Care to give an example to illustrate what JavaScript is lacking?

Which languages do you recommend then?

Just jump straight to Haskell. The learning curve is substantial, but it will guarantee that you learn functional concepts correctly and not in the hackneyed way most "functional" js or Java code is written. If you end up not liking Haskell, every other popular functional language (e.g. Scala) has some subset of haskell's features, so you'll already be equipped to use them.

Can the same concept be learned from scheme? Or is there something special about Haskell regarding functional programing?

Reply on news.ycombinator.com