10 ms·

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

by tps5 10y ago

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.

wyager 10y ago
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.
- hota_mazi 10y ago
  > 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?
  - madmax96 10y ago
    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...
    - hota_mazi 10y ago
      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.
      - wyager 10y ago
        > 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.
        hota_mazi 10y ago
        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.
greggman 10y ago
I found this series convinced me I wish I could use FP http://fsharpforfunandprofit.com/ http://fsharpforfunandprofit.com/ Specifically the "Why F#" part and within that this article http://fsharpforfunandprofit.com/posts/correctness-type-checking/ 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.
- tybit 10y ago
  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.
  - slifin 10y ago
    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?
  - wyager 10y ago
    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.
    - matt_kantor 10y ago
      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 http://scala-lang.org/blog/2016/02/03/essence-of-scala.html
fmap 10y ago
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. :)
- steveklabnik 10y ago
  > 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.
  - fmap 10y ago
    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.

by tps5 10y ago

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.

wyager 10y ago

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.

hota_mazi 10y ago
> 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?
- madmax96 10y ago
  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...
  - hota_mazi 10y ago
    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.
    - wyager 10y ago
      > 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.
      - hota_mazi 10y ago
        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.

greggman 10y ago

I found this series convinced me I wish I could use FP http://fsharpforfunandprofit.com/ http://fsharpforfunandprofit.com/ Specifically the "Why F#" part and within that this article http://fsharpforfunandprofit.com/posts/correctness-type-checking/ 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.

tybit 10y ago
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.
- slifin 10y ago
  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?
- wyager 10y ago
  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.
  - matt_kantor 10y ago
    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 http://scala-lang.org/blog/2016/02/03/essence-of-scala.html

fmap 10y ago

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. :)

steveklabnik 10y ago
> 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.
- fmap 10y ago
  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.