3 ms·
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 o
by 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 agoObviously, 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 agoHow 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 agoYou'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.
- wyager 10y agoThere'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.
- steveklabnik 10y ago> 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.