Timeline for How important is knowing how to program for TCS?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 29, 2011 at 0:51 | comment | added | Antonio Valerio Miceli-Barone | It depends on what you mean by "functional programming". If you mean programming in a pure functional language with lazy evaluation then yes, reasoning about complexity becomes difficult, and in order to get decent performance you'll probably have to force eager evaluation and implement state machines on the top of the functional layer, hoping that the complier optimizes them. If you mean using elements of the functional paradigm on a multiparadigm language such as the ML family or the Lisp family, then reasoning about complexity and getting good performance becomes more feasible. | |
| Nov 10, 2011 at 14:48 | comment | added | Radu GRIGore | @NeelKrishnaswami: Well, lazy evaluation means that you need to think about what gets evaluated when you analyze the algorithm rather than when you write the code. So, in a sense, lazy evaluation makes algorithm analysis harder (although you don't really do more work overall). It's a bit like the difference between memoized recursive implementations versus dynamic programming ones: For memoization you don't need to figure out the space usage before you write the code, so, in a sense, analyzing the space usage of a memoized implementation can be more work. | |
| Nov 10, 2011 at 14:09 | comment | added | Jeffε | @SashoNikolov: Whenever I teach a graduate data structures class, I really really wish I could assume that everyone had some functional programming experience. Instead of spending three 90-minute lectures to explain persistence, I could just say "Hey, did you notice that your data structures already do THIS?" | |
| Nov 10, 2011 at 8:44 | comment | added | Neel Krishnaswami | @Sasho: All ordinary techniques still work in functional languages. The only "problem" is that functional programming encourages a style of programming and data structure design which ordinary techniques of algorithmic analysis are under-equipped to handle. (E.g., what's the big-O of function composition? The operation is trivial, but it completely breaks the assumptions of asymptotic complexity -- there's no simple numeric metric of size for a functional input.) | |
| Nov 10, 2011 at 0:49 | history | edited | Sasho Nikolov | CC BY-SA 3.0 |
added 362 characters in body
|
| Nov 10, 2011 at 0:42 | comment | added | Sasho Nikolov | @JɛffE That's a question with a terrific answer. But looking over Okasaki's thesis still leaves me with the impression that reasoning about data structure efficiency in a functional language is possible, but can be a headache, even for data structures we consider simple. | |
| Nov 9, 2011 at 12:31 | comment | added | Jeffε | Ahem. | |
| Nov 9, 2011 at 4:46 | comment | added | Sasho Nikolov | Now when I reread it sounds a little too curt. I agree that FP goes great with logic and semantics and am willing to be disproved | |
| Nov 8, 2011 at 18:55 | comment | added | Radu GRIGore | "Functional programming obscures issues of algorithm design and running time and emphasizes logic and semantics issues." Which is why it is a good choice if you work in the logic or semantics side of TCS. :) | |
| Nov 8, 2011 at 17:40 | comment | added | Suresh Venkat | "Functional programming obscures issues of algorithm design and running time and emphasizes logic and semantics issues". Fighting words :) | |
| Nov 8, 2011 at 17:15 | comment | added | Peter Shor | Very good points in favor of C. | |
| Nov 8, 2011 at 16:09 | history | answered | Sasho Nikolov | CC BY-SA 3.0 |