Given that the majority of web surfing is done on mobile these days, it's pretty naïve to put pictures inside a Flash object. Wont be viewing those slides any time soon. (Also, functional programming FTW!)
I stopped listening when she said 'code and data are the same thing in a functional language'. Well not really, code and data are the same in a homoiconic language, but really any language with sufficient reflection capabilities can mix code and data. It has nothing to do with being functional.
Not sure if you're being facetious, but no, not all functional languages are Lisps. Haskell, ML, Ocaml, and Scala all come to mind as functional languages that are far from Lisp.
The book mostly deals with teaching recursive thinking; basically being the notes of a very didactic two week introduction. Do not read the book in fewer than three sittings. So a little more than an evening if you really want to obey the rules, and most importantly: never, ever feed the gremlin (elephant) after midnight.
Disclaimer: I am currently going through SICP (I'm approximately 200 pages in).
So far, I do not get the impression the I'm learning functional programming. Sure, I learn all about map, fold and filter. Sure I've picked this up these concept and apply them almost exclusively to my "regular job" programming in Python. But I'm not learning about functional programming.
What I mean is that assignments are simply never mentioned (so far). Everything is acting as if FP is the only natural way to program (I'm a professional programmer, but keep in mind that this book is geared towards beginners with little-to-no prior exposure to programming).
Anw, my point is that SICP will have you program a lot in FP style, but won't spend time explaining what FP is, or how is it different from your 'standard' procedural paradigms. I hear that you can write in various paradigms with Scheme, I wouldn't be surprised that they'd be mention in this book.
In short, SICP is a wonderful book that will teach you how to build (well "structure") your programs, focusing on mastering complexity to manage large systems. It's not an absolute reference about FP.
Seriously, if you're only 200 pages in, you haven't read chapter 3 yet, which delves deeply into the implications of introducing mutable state, and spends quite a lot of time exploring those implications, especially for concurrent programs. There is also some exploration into object oriented programming and alternative semantics and paradigms, including logic programming and laziness (chapter 4, iirc)
In short, I definitely don't think of SICP as an absolute reference to functional programming, especially since there are newer languages and approaches to these problems (STM in Clojure and Haskell, actor based concurrency etc) but SICP is an absolutely brilliant introduction, albeit a long one.
One of the things Dr. Parsons mentions here is how functional programming makes it easier to reason about programming because of the lack of side-effects. That makes sense to me, and I heard it frequently whenever someone is giving the FP sales pitch.
I wonder, though, whether there is a tradeoff that is going unmentioned, and I suspect that it is that it makes it more difficult to reason about costs. I feel trapped when I'm writing in a language like Java, but at least the cost model is obvious to me. Am I off base here? Is there some way to develop a similar intuition about costs in an FP language?
I think the best way is to have a good taste when choosing how to solve the problem.
Going purely functional (Haskell) has its own benefits but also a lot of drawbacks.
If you don't go purely functional, it doesn't make sense to avoid imperative or OO features where they make sense.
In that sense, I think languages which fuse and unify functional and OO approaches are a good strategy. There is a bit of negativity towards them, because they manage to piss off both OO evangelists as well as functional preachers, but that doesn't detract from the technical benefits of such an approach.
Most of my functional programming experience is with Clojure, and it's not very deep experience, so take this with a grain of salt. However I think reasoning about performance in Clojure isn't tremendously different than reasoning about performance in Java, and in some cases it might even be easier. Yes, it's true that you might have to learn some new idioms, like passing accumulators to tail recursive calls. But once you start structuring programs primarily as a collection of pure functions that operate on data structures like vectors and maps, I think profiling those functions is easier much in the same way that testing them can be easier. Obviously, depending on the language, you might have to develop new mental models for how to use certain features performantly (like lazy seqs and persistent collections in Clojure), but that's mostly true of any new language or even a new library.
Computer use has shifted from calculating tables for ballistic missiles to manipulating gigantic amounts of state. And (pure) FP is the answer because it doesn't have the ability to manipulate state?
On the contrary, pure FP excels at manipulating state.
The name "pure FP" is a bit of a misnomer, because what people really mean by it is that instead of "side effects" we have "typed effects". The effects always appear in the types of our computations, so they're not really "side" effects anymore, they're a central part of the computation.
The cost model can be very simple. Take the cost model of Java and apply it to programs where all fields are final.
Maybe costs are higher than you'd like, but it's simple to understand.
Lazy evaluation seriously complicates the cost model, but few languages are lazy.
You should read the introduction to Chris Okasaki's "Purely Functional Data Structures". It says there may be higher lower bounds for some problems in functional programming languages, although it's often possible to come up with something that is as fast. I interpret that as it can require a lot of ingenuity to come up with efficient data structures in functional programming languages.
It's not harder to reason about time complexity with strict evaluation. I think it's a bit harder with lazy evaluation, though. Okasaki uses both strict and lazy evaluation to achieve fast data structures.
Thank you for the pointer! I grabbed this pdf, and (by random chance) my eyes fell upon this somewhat-related gem (on page 129):
"Ironically, pattern matching — one of the most popular features in functional programming languages — is also one of the biggest obstacles to the widespread use of efficient functional data structures. The problem is that pattern matching can only be performed on data structures whose representation is known, yet the basic software-engineering principle of abstraction tells us that the representation of non-trivial data structures should be hidden. The seductive allure of pattern matching leads many functional programmers to abandon sophisticated data structures in favor of simple, known representations such as lists, even when doing so causes an otherwise linear algorithm to explode to quadratic or even exponential time."
Sounds like your thinking of /purely/ functional programming. Although none of these terms have precise definitions so there’s not really any point arguing over them.
Functional programming for me has a feeling of a mathematically sound foundation: This means a statically typed language with a powerful type-system and type inference. Immutability/effect system are a big plus. Broad range of data-structures and a decent object system are nice, too.
> Functional programming for me has a feeling of a mathematically sound foundation: This means a statically typed language with a powerful type-system and type inference.
Mathematical soundness does not require type inference. It's unclear whether it requires static typing.
And, it can easily get by with almost no type-system.
33 comments
[ 2.4 ms ] story [ 90.8 ms ] threadBased on what? I can't find a single article that would back that up.
Although I do agree that doing anything with Flash is just shooting yourself in the foot.
So far, I do not get the impression the I'm learning functional programming. Sure, I learn all about map, fold and filter. Sure I've picked this up these concept and apply them almost exclusively to my "regular job" programming in Python. But I'm not learning about functional programming.
What I mean is that assignments are simply never mentioned (so far). Everything is acting as if FP is the only natural way to program (I'm a professional programmer, but keep in mind that this book is geared towards beginners with little-to-no prior exposure to programming).
Anw, my point is that SICP will have you program a lot in FP style, but won't spend time explaining what FP is, or how is it different from your 'standard' procedural paradigms. I hear that you can write in various paradigms with Scheme, I wouldn't be surprised that they'd be mention in this book.
In short, SICP is a wonderful book that will teach you how to build (well "structure") your programs, focusing on mastering complexity to manage large systems. It's not an absolute reference about FP.
Seriously, if you're only 200 pages in, you haven't read chapter 3 yet, which delves deeply into the implications of introducing mutable state, and spends quite a lot of time exploring those implications, especially for concurrent programs. There is also some exploration into object oriented programming and alternative semantics and paradigms, including logic programming and laziness (chapter 4, iirc)
In short, I definitely don't think of SICP as an absolute reference to functional programming, especially since there are newer languages and approaches to these problems (STM in Clojure and Haskell, actor based concurrency etc) but SICP is an absolutely brilliant introduction, albeit a long one.
I wonder, though, whether there is a tradeoff that is going unmentioned, and I suspect that it is that it makes it more difficult to reason about costs. I feel trapped when I'm writing in a language like Java, but at least the cost model is obvious to me. Am I off base here? Is there some way to develop a similar intuition about costs in an FP language?
Going purely functional (Haskell) has its own benefits but also a lot of drawbacks.
If you don't go purely functional, it doesn't make sense to avoid imperative or OO features where they make sense.
In that sense, I think languages which fuse and unify functional and OO approaches are a good strategy. There is a bit of negativity towards them, because they manage to piss off both OO evangelists as well as functional preachers, but that doesn't detract from the technical benefits of such an approach.
The name "pure FP" is a bit of a misnomer, because what people really mean by it is that instead of "side effects" we have "typed effects". The effects always appear in the types of our computations, so they're not really "side" effects anymore, they're a central part of the computation.
Lazy evaluation seriously complicates the cost model, but few languages are lazy.
It's not harder to reason about time complexity with strict evaluation. I think it's a bit harder with lazy evaluation, though. Okasaki uses both strict and lazy evaluation to achieve fast data structures.
"Ironically, pattern matching — one of the most popular features in functional programming languages — is also one of the biggest obstacles to the widespread use of efficient functional data structures. The problem is that pattern matching can only be performed on data structures whose representation is known, yet the basic software-engineering principle of abstraction tells us that the representation of non-trivial data structures should be hidden. The seductive allure of pattern matching leads many functional programmers to abandon sophisticated data structures in favor of simple, known representations such as lists, even when doing so causes an otherwise linear algorithm to explode to quadratic or even exponential time."
http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
In my mind, functional languages and Lisp are two separate things.
Lisps can be functional, but most of them are not.
Functional programming for me has a feeling of a mathematically sound foundation: This means a statically typed language with a powerful type-system and type inference. Immutability/effect system are a big plus. Broad range of data-structures and a decent object system are nice, too.
Mathematical soundness does not require type inference. It's unclear whether it requires static typing.
And, it can easily get by with almost no type-system.