I stumbled across Thomas Guest's excellent blog, Word Aligned. It's yet another "here is some neat stuff about programming" blog. But, Guest is a good writer, and his approach is similar to how I (aim to) program -- Python first, C++ for performance, functional-style programming for expressiveness -- so naturally I enjoy reading it.
Check out animated pair streams for a post about taking advantage of the lazy evaluation tools in Python. Or The Lazy Builder's Complexity Lesson, an article that covers a typical algorithm problem, but with effective use of the STL as the objective, rather than implementing one's own searches/sorts/etc.
Showing posts with label comp sci. Show all posts
Showing posts with label comp sci. Show all posts
Tuesday, February 26, 2008
Saturday, February 23, 2008
Why Functional Programming Matters
So, Nick sent me a link to "Why Functional Programming Matters." It's a paper by John Hughes from way back in 1984, but it makes arguments that will be relevant forever, or at least as long as some CS programs only bother to teach their students Java because "it's probably the only language they'll ever program in, anyway." The paper is really advocating the value of two things, higher-order functions and lazy evaluation.
Higher-order functions are, I think, pretty uncontroversial at this point. You can't deny that they're useful, and they bring a glamorous crowd of friends with them, like map and reduce. Objects will let you do the same thing, but I think higher-order functions are easier to deal with in many (most?) situations. The Wikipedia article on them seems to imply there is some difficulty implementing higher-order functions in statically-typed imperative languages. I honestly don't know if that's true.
As an aside, Guido van Rossum got pilloried for suggesting that reduce() be removed in Python3000. Posters claimed that he was too stupid to understand reduce, or that he didn't realize you can do useful things with it. Instead, he was saying that many or most uses of reduce can be represented with a few functions, and those that can't are often convoluted and thus unPythonic. That was worthy of debate, and Guido backed down: reduce() is still around, just moved into a library.
Lazy evaluation is a bit trickier. Certain applications of it are obviously useful, like lazy lists. Hughes argues that lazy lists are not enough, and shows a tree-traversal example that also benefits from lazy evaluations. It seems obvious enough to me, 24 years after the paper was written and with crystal-clear hindsight, that if lazy lists are good, lazy trees can only be better. It seems like almost any function that iterates or recurses to produce answers seems could benefit from this approach, which is why iterators/generators are going to be a Big Thing in Python3000.
But in the conclusion, it seems like Hughes makes a different argument: laziness is key to modularity, and should be the default evaluation scheme (or at least, shouldn't be a "second-class citizen." I'm not sure how he supports that point in the body of the paper. Certainly, if you want to build a lazy function by composing other functions (as he does with evaluate), those other functions need to be lazy. But I don't get why modularity in general depends on laziness.
Where I stand:
Higher-order functions are, I think, pretty uncontroversial at this point. You can't deny that they're useful, and they bring a glamorous crowd of friends with them, like map and reduce. Objects will let you do the same thing, but I think higher-order functions are easier to deal with in many (most?) situations. The Wikipedia article on them seems to imply there is some difficulty implementing higher-order functions in statically-typed imperative languages. I honestly don't know if that's true.
As an aside, Guido van Rossum got pilloried for suggesting that reduce() be removed in Python3000. Posters claimed that he was too stupid to understand reduce, or that he didn't realize you can do useful things with it. Instead, he was saying that many or most uses of reduce can be represented with a few functions, and those that can't are often convoluted and thus unPythonic. That was worthy of debate, and Guido backed down: reduce() is still around, just moved into a library.
Lazy evaluation is a bit trickier. Certain applications of it are obviously useful, like lazy lists. Hughes argues that lazy lists are not enough, and shows a tree-traversal example that also benefits from lazy evaluations. It seems obvious enough to me, 24 years after the paper was written and with crystal-clear hindsight, that if lazy lists are good, lazy trees can only be better. It seems like almost any function that iterates or recurses to produce answers seems could benefit from this approach, which is why iterators/generators are going to be a Big Thing in Python3000.
But in the conclusion, it seems like Hughes makes a different argument: laziness is key to modularity, and should be the default evaluation scheme (or at least, shouldn't be a "second-class citizen." I'm not sure how he supports that point in the body of the paper. Certainly, if you want to build a lazy function by composing other functions (as he does with evaluate), those other functions need to be lazy. But I don't get why modularity in general depends on laziness.
Where I stand:
- Higher-order functions: yes, please
- Laziness for some functions: yes
- Laziness all the time: still not convinced
Subscribe to:
Posts (Atom)