5 ms·

Functional programming largely has two schools: Treat "commands" as a separate entity from expressions, and bake "commands" into expressions. The former is larg

by jlouis 10y ago

Functional programming largely has two schools: Treat "commands" as a separate entity from expressions, and bake "commands" into expressions. The former is largely Haskell, Clean, ... and the latter is exemplified by e.g., Standard ML or OCaml. There are trade-offs between the two, but I definitely belong to the second school: we simply add an imperative subset to our functional language. This means we can exploit any efficiency trick an imperative program can do, including low-level stuff. The seasoned FP programmer will then proceed to encapsulate the efficiency trick in a abstract module such that the rest of the program doesn't have to worry about it. Of course, the price to pay for this is that you are losing purity. I think this is a fair trade-off but others disagree. As for performance and memory usage: it is always a property of the architecture or system, not of the programming language. Dropping to a low-level language, such as C, usually doesn't buy you too much these days. What is more important is that most C compilers in use have vastly more time invested into optimizing routines than the typical FP compiler. Apart from that, you can easily mange the same kind of data in e.g., OCaml than you can in C. The reason FP can beat the curve of performance in practice is because you operate at a higher level of abstraction. You have more attempts at writing the correct architecture, and it is easier to change over time. Since most real-world problems are heavily time-constrained, this makes them beat low-level solutions: when the C programmer has written the first working version, the FP programmer has tried 5 different solutions. There is one area FP tends to fare poorly: CPU bound tasks where an inner-loop has to squeeze out performance (video encoding comes to mind). But most low-level programming fares poorly as well: either you use assembly, write GPU-level programs, use an FPGA or create your own ASIC/SoC solution for this. Also note that moving to faster solutions here costs an order of magnitude in time and in dollars: FPGAs are, relatively speaking, expensive beasts.

pka 10y ago
> This means we can exploit any efficiency trick an imperative program can do, including low-level stuff. The seasoned FP programmer will then proceed to encapsulate the efficiency trick in a abstract module such that the rest of the program doesn't have to worry about it. You can do that in a pure language as well (i.e. ST monad.) Purity shouldn't be given up lightly.
- marcosdumay 10y ago
  I think he was talking about something like unsafePerformIO. There are plenty of tricks you can not write on pure monads, and there are many Haskell libs that use the unsafePerformIO trick too.
  - pka 10y ago
    > There are plenty of tricks you can not write on pure monads This made me curious, could you list some?
    - marcosdumay 10y ago
      Anything that needs rewriting a memory address without losing time by allocation and garbage collection. Handling IO exceptions and masking them as different errors. Thread, process, or machine coordination in parallel execution.
      - pka 10y ago
        You don't need unsafePerformIO for any of these. > Anything that needs rewriting a memory address without losing time by allocation and garbage collection. ST gives you mutable references. Or just use IO.
        marcosdumay 10y ago
        You need it for doing what the OP is talking about.
- kazinator 10y ago
  ST monad is not state; it's a convoluted way of threading a value through a chain of functions. State means we put the value into the same memory location (or CPU register, or piece of tape or whatever).
  - pka 10y ago
Athas 10y ago
> As for performance and memory usage: it is always a property of the architecture or system, not of the programming language. Dropping to a low-level language, such as C, usually doesn't buy you too much these days. What is more important is that most C compilers in use have vastly more time invested into optimizing routines than the typical FP compiler. Apart from that, you can easily mange the same kind of data in e.g., OCaml than you can in C. This is true in in principle, but not in practice. It is not just a question of whether a language is particularly amenable to optimisation and clever compilation (C is not, by the way), but also whether the baseline of naive compilation is efficient in itself. A naive C compiler will generate vastly better code than a naive compiler for most functional languages, if only because naive C compilation will primarly allocate statically and on the stack, while a functional language will perform an enormous amount of heap allocation. Futhermore, natural C programming style tends towards cache-friendly arrays and bulk allocations, while natural functional programming style tends towards lots of pointers pointing everywhere. Certainly, there are functional languages with efficient array libraries and the like, but they are less natural, and their use is often considered an "optimisation". And of course, most functional languages give you some way of accessing raw memory and essentially just writing C-in-Haskell or whatever, but then you're not really doing functional programming anymore. Of course, if the problem is at its essence about pointer chasing, or composing IO pipelines, then functional programming is a fine choice, because the performance of the language is less important, and the ability to reason about complicated control flow is important. What I find interesting about Haskell is that due to the clear reification of IO, the compiler can actually perform optimisations on IO pipelines, such as fusion. Think about it - IO is usually the prime example of a fusion inhibitor, but GHC can actually do it for libraries such as conduit! It is a little ironic that Haskell is probably the best language I know of for describing complex IO operations. An interesting twist is of course when you construct a functional language with an eye towards efficient compilation from the start. Then the primary compound data type is no longer the linked list, but the array, and you tend to end up with an array language. Examples include SISAL, Single Assignment C, NESL, Accelerate, Futhark, Lift, etc, which are naturally fairly efficient due to their programming model, and which provide strong functional invariants that the compiler can then exploit. These .anguages are all still pretty experimental and unwieldy in practice, though.
- 10y ago
adwn 10y ago
> when the C programmer has written the first working version, the FP programmer has tried 5 different solutions. ... none of which are necessarily faster than the other 4 solutions. It's not just the architecture of your code that influences performance, it's also – sometimes even more so – the underlying details of your implementation, like arrays vs. pointer-based data structures; Athas' comment describes this pretty well. As a consequence, this statement: > it is always a property of the architecture or system, not of the programming language is wrong, simply because your programming language will heavily influence a lot of your productivity vs. performance tradeoffs.
michaelfeathers 10y ago
The key insight is that immutability is not an end in itself, it's a tool to give us referential transparency. If a language can allow mutability in an area of code without allowing side effects to escape from it we can have all of the reasoning advantage that FP gives us at a level above the mutations. We can also have the performance we want.
- stcredzero 10y ago
  The key insight is that immutability is not an end in itself, it's a tool to give us referential transparency. How about a programming environment tailored for small simulations or games? I could imagine such an environment maintaining referential transparency without strict immutability. Rather, such a system could provide a kind of "poor-man's" immutability by only allowing pure functions that take state from tick N and output state for tick N+1. Perhaps such a system could even achieve high performance by exploiting its constraints? Maybe the language could essentially be built on top of a custom VM and around the mechanism of bump allocation, read/write barriers, and Beltway garbage collection?
  - jpt4 10y ago
    Are you familiar with Urbit [0]? [0] urbit.org
    - dTal 10y ago
      Is anyone?
- efnx 10y ago
  This is what StateT in Haskell is for.
- samuell 10y ago
  > If a language can allow mutability in an area of code without allowing side effects to escape from it we can have all of the reasoning advantage that FP gives us at a level above the mutations. We can also have the performance we want. As far as I see and can tell from experience, this exactly the power of the black-box processes of Flow-based Programming (FBP), communicating only via message passing (on buffered channels) [1]. FBP processes can be compared to "functions", but are free to change state etc. The "only communicate via message passing" means funny side-effects are effectively contained to the process itself. Furthermore, I would argue that FBP, via its specification of keeping the network connectivity separate from the process implementation, makes FBP programs so extremely much more composable than most typical FP programs, which often allow references to other functions be hard-coded inside function code. It is like making the call graph of an FP program declaratively configured by a list of processes and connections: Processes: A (ports out1, out2) B (ports in1, out1) C (ports in1, out1) Connections: A.out1 -> B.in1 A.out2 -> C.in1 etc. I wrote a little text processing app in this style some time ago (The network connectivity scheme can be seen here: https://github.com/rdfio/rdf2smw/blob/master/main.go#L100-L125 https://github.com/rdfio/rdf2smw/blob/master/main.go#L100-L1... ) and was amazed by the clarity and composability that emerged, even though I just used my own little experimental subset of full FBP ( http://flowbase.org http://flowbase.org ). As far as I can tell, this helped me going from first line of code to finished app go extremely fast ... app written in 2 days without ever really getting stuck in any strange bug due to bad code organization, which use to happen all the time otherwise. [1] https://en.wikipedia.org/wiki/Flow-based_programming https://en.wikipedia.org/wiki/Flow-based_programming
johncolanduoni 10y ago
> There are trade-offs between the two, but I definitely belong to the second school: we simply add an imperative subset to our functional language. This means we can exploit any efficiency trick an imperative program can do, including low-level stuff. The seasoned FP programmer will then proceed to encapsulate the efficiency trick in a abstract module such that the rest of the program doesn't have to worry about it. Of course, the price to pay for this is that you are losing purity. I think this is a fair trade-off but others disagree. I think the trade-off is unnecessary. If your language can embed a convenient method for analyzing the imperative state in the way it is typically used (F* is a good example), you can get a similar result by lifting your internally stateful but externally pure code into truly pure functions, even if it wants to do something more complicated than simpler state monads can do conveniently. The compiler can then understand the language's state construction and write the imperative code directly when generating machine code, with little more infrastructure than OCaml needs to allow you to do so anywhere. This way you get to keep purity without requiring you to lose performance or jump through hoops to keep your pure code downstream of your impure code.

by jlouis 10y ago

pka 10y ago

> This means we can exploit any efficiency trick an imperative program can do, including low-level stuff. The seasoned FP programmer will then proceed to encapsulate the efficiency trick in a abstract module such that the rest of the program doesn't have to worry about it. You can do that in a pure language as well (i.e. ST monad.) Purity shouldn't be given up lightly.

marcosdumay 10y ago
I think he was talking about something like unsafePerformIO. There are plenty of tricks you can not write on pure monads, and there are many Haskell libs that use the unsafePerformIO trick too.
- pka 10y ago
  > There are plenty of tricks you can not write on pure monads This made me curious, could you list some?
  - marcosdumay 10y ago
    Anything that needs rewriting a memory address without losing time by allocation and garbage collection. Handling IO exceptions and masking them as different errors. Thread, process, or machine coordination in parallel execution.
    - pka 10y ago
      You don't need unsafePerformIO for any of these. > Anything that needs rewriting a memory address without losing time by allocation and garbage collection. ST gives you mutable references. Or just use IO.
      - marcosdumay 10y ago
        You need it for doing what the OP is talking about.
kazinator 10y ago
ST monad is not state; it's a convoluted way of threading a value through a chain of functions. State means we put the value into the same memory location (or CPU register, or piece of tape or whatever).
- pka 10y ago

Athas 10y ago

> As for performance and memory usage: it is always a property of the architecture or system, not of the programming language. Dropping to a low-level language, such as C, usually doesn't buy you too much these days. What is more important is that most C compilers in use have vastly more time invested into optimizing routines than the typical FP compiler. Apart from that, you can easily mange the same kind of data in e.g., OCaml than you can in C. This is true in in principle, but not in practice. It is not just a question of whether a language is particularly amenable to optimisation and clever compilation (C is not, by the way), but also whether the baseline of naive compilation is efficient in itself. A naive C compiler will generate vastly better code than a naive compiler for most functional languages, if only because naive C compilation will primarly allocate statically and on the stack, while a functional language will perform an enormous amount of heap allocation. Futhermore, natural C programming style tends towards cache-friendly arrays and bulk allocations, while natural functional programming style tends towards lots of pointers pointing everywhere. Certainly, there are functional languages with efficient array libraries and the like, but they are less natural, and their use is often considered an "optimisation". And of course, most functional languages give you some way of accessing raw memory and essentially just writing C-in-Haskell or whatever, but then you're not really doing functional programming anymore. Of course, if the problem is at its essence about pointer chasing, or composing IO pipelines, then functional programming is a fine choice, because the performance of the language is less important, and the ability to reason about complicated control flow is important. What I find interesting about Haskell is that due to the clear reification of IO, the compiler can actually perform optimisations on IO pipelines, such as fusion. Think about it - IO is usually the prime example of a fusion inhibitor, but GHC can actually do it for libraries such as conduit! It is a little ironic that Haskell is probably the best language I know of for describing complex IO operations. An interesting twist is of course when you construct a functional language with an eye towards efficient compilation from the start. Then the primary compound data type is no longer the linked list, but the array, and you tend to end up with an array language. Examples include SISAL, Single Assignment C, NESL, Accelerate, Futhark, Lift, etc, which are naturally fairly efficient due to their programming model, and which provide strong functional invariants that the compiler can then exploit. These .anguages are all still pretty experimental and unwieldy in practice, though.

10y ago

adwn 10y ago

> when the C programmer has written the first working version, the FP programmer has tried 5 different solutions. ... none of which are necessarily faster than the other 4 solutions. It's not just the architecture of your code that influences performance, it's also – sometimes even more so – the underlying details of your implementation, like arrays vs. pointer-based data structures; Athas' comment describes this pretty well. As a consequence, this statement: > it is always a property of the architecture or system, not of the programming language is wrong, simply because your programming language will heavily influence a lot of your productivity vs. performance tradeoffs.

michaelfeathers 10y ago

The key insight is that immutability is not an end in itself, it's a tool to give us referential transparency. If a language can allow mutability in an area of code without allowing side effects to escape from it we can have all of the reasoning advantage that FP gives us at a level above the mutations. We can also have the performance we want.

stcredzero 10y ago
The key insight is that immutability is not an end in itself, it's a tool to give us referential transparency. How about a programming environment tailored for small simulations or games? I could imagine such an environment maintaining referential transparency without strict immutability. Rather, such a system could provide a kind of "poor-man's" immutability by only allowing pure functions that take state from tick N and output state for tick N+1. Perhaps such a system could even achieve high performance by exploiting its constraints? Maybe the language could essentially be built on top of a custom VM and around the mechanism of bump allocation, read/write barriers, and Beltway garbage collection?
- jpt4 10y ago
  Are you familiar with Urbit [0]? [0] urbit.org
  - dTal 10y ago
    Is anyone?
efnx 10y ago
This is what StateT in Haskell is for.
samuell 10y ago
> If a language can allow mutability in an area of code without allowing side effects to escape from it we can have all of the reasoning advantage that FP gives us at a level above the mutations. We can also have the performance we want. As far as I see and can tell from experience, this exactly the power of the black-box processes of Flow-based Programming (FBP), communicating only via message passing (on buffered channels) [1]. FBP processes can be compared to "functions", but are free to change state etc. The "only communicate via message passing" means funny side-effects are effectively contained to the process itself. Furthermore, I would argue that FBP, via its specification of keeping the network connectivity separate from the process implementation, makes FBP programs so extremely much more composable than most typical FP programs, which often allow references to other functions be hard-coded inside function code. It is like making the call graph of an FP program declaratively configured by a list of processes and connections: Processes: A (ports out1, out2) B (ports in1, out1) C (ports in1, out1) Connections: A.out1 -> B.in1 A.out2 -> C.in1 etc. I wrote a little text processing app in this style some time ago (The network connectivity scheme can be seen here: https://github.com/rdfio/rdf2smw/blob/master/main.go#L100-L125 https://github.com/rdfio/rdf2smw/blob/master/main.go#L100-L1... ) and was amazed by the clarity and composability that emerged, even though I just used my own little experimental subset of full FBP ( http://flowbase.org http://flowbase.org ). As far as I can tell, this helped me going from first line of code to finished app go extremely fast ... app written in 2 days without ever really getting stuck in any strange bug due to bad code organization, which use to happen all the time otherwise. [1] https://en.wikipedia.org/wiki/Flow-based_programming https://en.wikipedia.org/wiki/Flow-based_programming

johncolanduoni 10y ago

> There are trade-offs between the two, but I definitely belong to the second school: we simply add an imperative subset to our functional language. This means we can exploit any efficiency trick an imperative program can do, including low-level stuff. The seasoned FP programmer will then proceed to encapsulate the efficiency trick in a abstract module such that the rest of the program doesn't have to worry about it. Of course, the price to pay for this is that you are losing purity. I think this is a fair trade-off but others disagree. I think the trade-off is unnecessary. If your language can embed a convenient method for analyzing the imperative state in the way it is typically used (F* is a good example), you can get a similar result by lifting your internally stateful but externally pure code into truly pure functions, even if it wants to do something more complicated than simpler state monads can do conveniently. The compiler can then understand the language's state construction and write the imperative code directly when generating machine code, with little more infrastructure than OCaml needs to allow you to do so anywhere. This way you get to keep purity without requiring you to lose performance or jump through hoops to keep your pure code downstream of your impure code.