7 ms·

Can functional programming be liberated from the von Neumann paradigm? (2010)

92 points by bkirwi 12y ago

jacquesm 12y ago
This page doesn't load for me, which is a pity. Why limit the question just to functional programming? This applies just as much if not more to imperative programming, at least in functional programming you have the option to execute any pure function in parallel on some independent chunk of hardware. Whether imperative programming can be 'liberated' from the von Neumann bottle-neck is a much harder problem. In the end both will still have to deal with Amdahl's Law, so even if you could get rid of the 'looking at memory through a keyhole' issue you're going to have to come to terms with not being able to solve your problem faster than the sequential execution of all the non-parallizable chunks.
- liscovich 12y ago
  Here is the cached version of the article: http://webcache.googleusercontent.com/search?q=cache:CHoIZZiogskJ:conal.net/blog/posts/can-functional-programming-be-liberated-from-the-von-neumann-paradigm+&cd=1&hl=en&ct=clnk&gl=us http://webcache.googleusercontent.com/search?q=cache:CHoIZZi...
- tome 12y ago
  > This page doesn't load for me, which is a pity. https://web.archive.org/web/20131225040636/http://conal.net/blog/posts/can-functional-programming-be-liberated-from-the-von-neumann-paradigm https://web.archive.org/web/20131225040636/http://conal.net/... > Why limit the question just to functional programming? There was already an article about the general case :) http://web.stanford.edu/class/cs242/readings/backus.pdf http://web.stanford.edu/class/cs242/readings/backus.pdf
  - conal 12y ago
    Sorry about that. My blog seems to be working now. I don't know what happened earlier. I think the server I've been using is underpowered. Hopefully I'll get my site migrated soon.
- chongli 12y ago
  A pure function cannot always be executed in parallel. For that it might need access to shared data. On non-von Neumann machines this may not be possible.
  - pohl 12y ago
    Wouldn't such a function not be pure? Or am I not understanding the notion of purity?
    - deleted 12y ago
      [deleted]
    - chongli 12y ago
      Of course it can be pure, so long as the shared data is not mutated. Functional languages such as Haskell don't copy values all over the place when calling functions, they pass in pointers.
      - jdiez17 12y ago
        But that's an optimisation. Which can be switched off to get the benefits from parallelism. This is a tradeoff that programmers would traditionally have to consider, but with functional programming the compiler can figure it out for us.
        chongli 12y ago
        That's assuming that "figuring it out for us" is decidable. Many of the things we wish the compiler could do for us are not.
        dllthomas 12y ago
        "It's not decidable" is not a guarantee that humans can do better than a compiler. It means any approach will sometimes be wrong, but a compiler might well (in principle) be wrong less often than a human. This is separate from the "a human has a lot of additional context that's hard to express" argument, which is valid but has nothing to do with decidability.
- ExpiredLink 12y ago
  > This page doesn't load for me, which is a pity. It only loads in browsers written in a purely functional language!
- profquail 12y ago
  Coral cached version: http://conal.net.nyud.net:8080/blog/posts/can-functional-programming-be-liberated-from-the-von-neumann-paradigm http://conal.net.nyud.net:8080/blog/posts/can-functional-pro...
deleted 12y ago
[deleted]
tenfingers 12y ago
It's worth nothing that functional programming is hard not because of the functional paradigm, but due to the constraints you have while solving a problem (memory, for one). This requires changing the simple, composable functions that you could reuse forever, to complex ones that have to split the work into multiple stages. Another source of inherent complexity which has nothing to do with the solution of the problem itself, is the handling of the input or runtime issues. Input cannot be guaranteed to be always coherent, and runtime issues may arise while running (user interrupt). At this point, interrupting the computation is easy, but as an user I want maybe: * know why the function stopped, with a meaning answer (not just a stack trace) * know the location of the error in the input data * the possibility to resume the computation If you've ever programmed functionally, you know how hard is to do something as simple as give meaningful error messages buried into a series of fold/map calls. Keeping state is a simple (and I would say equally elegant) solution to this recurrent problem. Please consider that I'm saying this from a functional programming perspective (as in: objects as localized state containers not necessarily breaking the purity assumption). Another issue is that we, as humans, are based on a stateful world. Stateful user interfaces are sometimes more efficient due to the way _we_ work. This can be seen in something as simple as "now select a file", which brings up a dedicated section of stateful code to navigate a tree. As such, you are constantly faced with the problem of keeping state.
- seanmcdirmid 12y ago
  Amen. You might want to check out my project that attempts to rationalize mutation through time management rather than avoid it: http://research.microsoft.com/en-us/people/smcdirm/managedtime.aspx http://research.microsoft.com/en-us/people/smcdirm/managedti... Anyways, there are many other ways of fixing or transcending Von nuemann, pure functional might not be it.
  - hyperpape 12y ago
    This is the second time I've looked at that page (saw it on LtU several months ago), and I find it baffling. In particular, what escapes me is what those videos represent. Why are they showing typing, rather than what some code does? Are you demonstrating a programming language or a live coding environment? The first two paragraphs seem to discuss the former, but the videos look like the latter. And if it is the latter, I can't figure out what the language is doing because I'm so hung up on the typing/deletion/live feedback. The only way I've been able to get anywhere is by looking at the paper. You might want to link to the paper or some other overview rather than this page.
michaelochurch 12y ago
This is a really interesting article (and a blog I want to come back to). Thanks, OP. What Haskell seems to achieve, and I'm not an expert on it yet, is an incentive system that encourages small functions especially when you're "in" a monad, because of the "any side effects makes the whole function 'impure'" dynamic as seen in the type system (also known as "you can't get out of the monad"). Of course, it's sometimes a pain in the ass to thread your RNG state or other parameters (that remain implicit in imperative programming) through the function, and that's where you get into the rabbit hole of specialized monads (State, Reader, Writer, RWS, Cont) and, for more fun yet, monad transformers. I think that the imperative approach to programming has such a hold because, at small scale, it's far more intuitive. At 20 lines, defining functions feels dry and mathematical and we're much more attracted to the notion of doing things (or, making the computer do things). And, contrary to what we think in functional programming, imperative programming is more intuitive and simpler at small scale (even if more verbose). It's in composition and at scale (even moderate scale, like 100 LoC) that imperative programming starts to reach that high-entropy state where it's hard to reason about the code.
- jules 12y ago
  Haskell is lazy, which paradoxically means that its execution is sequential. In order to be truly liberated the execution order needs to be unspecified.
  - jberryman 12y ago
    > Haskell is lazy, which paradoxically means that its execution is sequential. I don't understand what you mean.
    - adwn 12y ago
      Although I don't agree that "lazy => sequential", what he/she probably means is that Haskell's lazy execution model sets constraints on program execution, in analogy to an imperative language, which also sets contraints on execution order. Advantages of an unspecified execution order: more compiler optimizations allowed/possible. Disadvantages: even harder to reason about. In fact, some functions may or may not terminate, depending on the whims of the compiler.
jdiaz5513 12y ago
We do have a functional language that's free from imperative constraints - it's called mathematics; everything runs on it. We just don't have the source code.
hellbanner 12y ago
Can someone please explain: " An FP system cannot compute a program since function expressions are not objects. Nor can one define new functional forms within an FP system. (Both of these limitations are removed in formal functional programming (FFP) systems in which objects "represent" functions.) Thus no FP system can have a function, apply, such that apply: <x,y> = x :y because, on the left, x is an object, and, on the right, x is a function. (Note that we have been careful to keep the set of function symbols and the set of objects distinct: thus 1 is a function symbol, and 1 is an object.)" I understand what it says. I don't understand why apply:<x,y> === x:y doesn't work in the construct of functional programming?

92 points by bkirwi 12y ago

This page doesn't load for me, which is a pity. Why limit the question just to functional programming? This applies just as much if not more to imperative programming, at least in functional programming you have the option to execute any pure function in parallel on some independent chunk of hardware. Whether imperative programming can be 'liberated' from the von Neumann bottle-neck is a much harder problem. In the end both will still have to deal with Amdahl's Law, so even if you could get rid of the 'looking at memory through a keyhole' issue you're going to have to come to terms with not being able to solve your problem faster than the sequential execution of all the non-parallizable chunks.

liscovich 12y ago
Here is the cached version of the article: http://webcache.googleusercontent.com/search?q=cache:CHoIZZiogskJ:conal.net/blog/posts/can-functional-programming-be-liberated-from-the-von-neumann-paradigm+&cd=1&hl=en&ct=clnk&gl=us http://webcache.googleusercontent.com/search?q=cache:CHoIZZi...
tome 12y ago
> This page doesn't load for me, which is a pity. https://web.archive.org/web/20131225040636/http://conal.net/blog/posts/can-functional-programming-be-liberated-from-the-von-neumann-paradigm https://web.archive.org/web/20131225040636/http://conal.net/... > Why limit the question just to functional programming? There was already an article about the general case :) http://web.stanford.edu/class/cs242/readings/backus.pdf http://web.stanford.edu/class/cs242/readings/backus.pdf
- conal 12y ago
  Sorry about that. My blog seems to be working now. I don't know what happened earlier. I think the server I've been using is underpowered. Hopefully I'll get my site migrated soon.
chongli 12y ago
A pure function cannot always be executed in parallel. For that it might need access to shared data. On non-von Neumann machines this may not be possible.
- pohl 12y ago
  Wouldn't such a function not be pure? Or am I not understanding the notion of purity?
  - deleted 12y ago
    [deleted]
  - chongli 12y ago
    Of course it can be pure, so long as the shared data is not mutated. Functional languages such as Haskell don't copy values all over the place when calling functions, they pass in pointers.
    - jdiez17 12y ago
      But that's an optimisation. Which can be switched off to get the benefits from parallelism. This is a tradeoff that programmers would traditionally have to consider, but with functional programming the compiler can figure it out for us.
      - chongli 12y ago
        That's assuming that "figuring it out for us" is decidable. Many of the things we wish the compiler could do for us are not.
        dllthomas 12y ago
        "It's not decidable" is not a guarantee that humans can do better than a compiler. It means any approach will sometimes be wrong, but a compiler might well (in principle) be wrong less often than a human. This is separate from the "a human has a lot of additional context that's hard to express" argument, which is valid but has nothing to do with decidability.
ExpiredLink 12y ago
> This page doesn't load for me, which is a pity. It only loads in browsers written in a purely functional language!
profquail 12y ago
Coral cached version: http://conal.net.nyud.net:8080/blog/posts/can-functional-programming-be-liberated-from-the-von-neumann-paradigm http://conal.net.nyud.net:8080/blog/posts/can-functional-pro...

deleted 12y ago

[deleted]

tenfingers 12y ago

It's worth nothing that functional programming is hard not because of the functional paradigm, but due to the constraints you have while solving a problem (memory, for one). This requires changing the simple, composable functions that you could reuse forever, to complex ones that have to split the work into multiple stages. Another source of inherent complexity which has nothing to do with the solution of the problem itself, is the handling of the input or runtime issues. Input cannot be guaranteed to be always coherent, and runtime issues may arise while running (user interrupt). At this point, interrupting the computation is easy, but as an user I want maybe: * know why the function stopped, with a meaning answer (not just a stack trace) * know the location of the error in the input data * the possibility to resume the computation If you've ever programmed functionally, you know how hard is to do something as simple as give meaningful error messages buried into a series of fold/map calls. Keeping state is a simple (and I would say equally elegant) solution to this recurrent problem. Please consider that I'm saying this from a functional programming perspective (as in: objects as localized state containers not necessarily breaking the purity assumption). Another issue is that we, as humans, are based on a stateful world. Stateful user interfaces are sometimes more efficient due to the way _we_ work. This can be seen in something as simple as "now select a file", which brings up a dedicated section of stateful code to navigate a tree. As such, you are constantly faced with the problem of keeping state.

seanmcdirmid 12y ago
Amen. You might want to check out my project that attempts to rationalize mutation through time management rather than avoid it: http://research.microsoft.com/en-us/people/smcdirm/managedtime.aspx http://research.microsoft.com/en-us/people/smcdirm/managedti... Anyways, there are many other ways of fixing or transcending Von nuemann, pure functional might not be it.
- hyperpape 12y ago
  This is the second time I've looked at that page (saw it on LtU several months ago), and I find it baffling. In particular, what escapes me is what those videos represent. Why are they showing typing, rather than what some code does? Are you demonstrating a programming language or a live coding environment? The first two paragraphs seem to discuss the former, but the videos look like the latter. And if it is the latter, I can't figure out what the language is doing because I'm so hung up on the typing/deletion/live feedback. The only way I've been able to get anywhere is by looking at the paper. You might want to link to the paper or some other overview rather than this page.

michaelochurch 12y ago

This is a really interesting article (and a blog I want to come back to). Thanks, OP. What Haskell seems to achieve, and I'm not an expert on it yet, is an incentive system that encourages small functions especially when you're "in" a monad, because of the "any side effects makes the whole function 'impure'" dynamic as seen in the type system (also known as "you can't get out of the monad"). Of course, it's sometimes a pain in the ass to thread your RNG state or other parameters (that remain implicit in imperative programming) through the function, and that's where you get into the rabbit hole of specialized monads (State, Reader, Writer, RWS, Cont) and, for more fun yet, monad transformers. I think that the imperative approach to programming has such a hold because, at small scale, it's far more intuitive. At 20 lines, defining functions feels dry and mathematical and we're much more attracted to the notion of doing things (or, making the computer do things). And, contrary to what we think in functional programming, imperative programming is more intuitive and simpler at small scale (even if more verbose). It's in composition and at scale (even moderate scale, like 100 LoC) that imperative programming starts to reach that high-entropy state where it's hard to reason about the code.

jules 12y ago
Haskell is lazy, which paradoxically means that its execution is sequential. In order to be truly liberated the execution order needs to be unspecified.
- jberryman 12y ago
  > Haskell is lazy, which paradoxically means that its execution is sequential. I don't understand what you mean.
  - adwn 12y ago
    Although I don't agree that "lazy => sequential", what he/she probably means is that Haskell's lazy execution model sets constraints on program execution, in analogy to an imperative language, which also sets contraints on execution order. Advantages of an unspecified execution order: more compiler optimizations allowed/possible. Disadvantages: even harder to reason about. In fact, some functions may or may not terminate, depending on the whims of the compiler.

jdiaz5513 12y ago

We do have a functional language that's free from imperative constraints - it's called mathematics; everything runs on it. We just don't have the source code.

hellbanner 12y ago

Can someone please explain: " An FP system cannot compute a program since function expressions are not objects. Nor can one define new functional forms within an FP system. (Both of these limitations are removed in formal functional programming (FFP) systems in which objects "represent" functions.) Thus no FP system can have a function, apply, such that apply: <x,y> = x :y because, on the left, x is an object, and, on the right, x is a function. (Note that we have been careful to keep the set of function symbols and the set of objects distinct: thus 1 is a function symbol, and 1 is an object.)" I understand what it says. I don't understand why apply:<x,y> === x:y doesn't work in the construct of functional programming?