I've recently jumped into Erlang, and have come to some of the same conclusions. I read Armstrong's Erlang book, and thought 'that seems cool' and didn't at all grok what was going on beyond the superficial. Then a few months later, just sat down and started solving Project Euler problems. At first it was strange and foreign and I was mad variables were immutable. A day later and it just clicked, I'd never had that much fun writing code.
The FP paradigm is (to me, even after 15 years of imperative programming) so much more natural for development, since you're able to sanely start attacking the problem directly -- instead of architecting a big-picture solution up front that's probably wrong anyway because you've ignored some detail you haven't yet discovered.
Building things with actions instead of objects just makes much more sense. Reuse comes much more naturally, and doesn't seem as contrived as a lot of OOP reuse seems. I've noticed that working my FP muscles out has made me a much better imperative programmer -- I write a lot more clever and effective code (not clever like 'tee-hee-no-one-will-ever-figure-this-out'!).
One thing that raises my eyebrows is how much functional programmers talk about Project Euler problems. The actual programming for solving these problems is in fact extremely trivial. They require some mathematical insight, especially after the first one hundred or so, and you need to do some external research on Pell's Equation to avoid getting stuck, and you need a fraction library if your language doesn't have it built in. But am I wrong in thinking that these kind of problems are almost no test or strain for your actual programming at all?
They're an absolutely fantastic way to start 'getting' any language. They're small, discrete, and varied tasks that require you to build different types of operations and structures. Sure, they're not at all reflective of 'real programming' nor are they necessarily particularly challenging, programming wise.
I'd rather cut my teeth in a new language on the first 50 or so PE problems, than take on a bigger, less defined, or more domain limited task.
I'm conversant in Python and Erlang because of PE problems entirely. They've enabled me to start actual projects in both languages.
That's where I'd argue. It would be like saying you're an all around gamer when you play only chess but with different openings every time.
Varied simple tasks would be doing some Euler problems, doing some basic algorithms (Dijkstra's with Heap, A* pathfinder on a 2d map, etc... TopCoder problems are great for this), write a Mandelbrot zoomer, Conway's Life app with position setup and step-through and save/load, write a Tetris clone, write a basic HTML form builder, write a blogging engine, write a multi-user chat room server, write a simple side-scrolling shooter game, write a basic Roguelike game, write a simple text adventure. Things like this can all be afternoon projects.
Every time I read someone claiming that Project Euler is for developing general-purpose programming, I roll my eyes more than a little.
When learning, it's easiest to learn one thing at at a time. If you're learning a new programming language or programming paradigm, it's helpful to solve a task you fully understand. That way, the unknown is not the solution, but what the solution looks like in this new language or paradigm.
Most of the examples you gave are applications. They require considering things external to the a core problem, such as user interaction and network communication. Those are like projects in a course. Project Euler problems are like a homework set.
> Most of the examples you gave are applications. They require considering things external to the a core problem, such as user interaction and network communication.
"Core problem" to me means solving a problem a user has. Things like user interaction are indeed part of the core problem.
Unless there's another sense of the term I'm missing?
Did anyone actually make this claim here? You quoted two words out of a comment that said quite a bit beside, including:
"Sure, they're not at all reflective of 'real programming' nor are they necessarily particularly challenging, programming wise."
Nobody claimed Project Euler is the way to become a great programmer. I would roll my eyes at your mistake, but I don't roll my eyes at people's mistakes. I try to help them correct them.
Don't get me wrong, I love Project Euler and had a blast doing a couple of hundred problems in Java a couple years ago. I make these claims:
1. The problem solving there has almost no connection to what it is like for the vast majority of uses of writing a computer problem.
2. It is in no sense a varied set of tasks. It's similar to a math contest problem set, with some basic string manipulation masquerading as numerical problems (pandigital numbers, etc.)
3. The programming and program design required to solve tasks in this narrow space is trivial, and not particularly instructive of how you'd write programs in another space.
4. Functional programming articles tend to mention and place stock in Project Euler problems to a degree which, in my opinion, is unusually much larger compared general programming articles.
Any similar sites you'd suggest, besides Project Euler and TopCoder? I've worked through much of PythonChallenge, but I'm more interested in sites that aren't as closely tied to a specific language.
Programming Praxis (http://programmingpraxis.com) provides a collection of etudes, updated weekly, for the education and enjoyment of the savvy programer. Although there is some math content (the current exercise uses the chinese remainder theorem), Programming Praxis is much less math-oriented than Project Euler.
Do you know about Sphere Online Judge? (http://www.spoj.pl/) It supports a lot of languages. It still contains mostly algorithmic problems though, making it a superset of the kinds of problems at Project Euler but still a tiny subset of general programming.
No mystery. Project Euler is a useful set of problems to tackle when learning a new language. It's not 'Wahoo with functional programming I can finally get past Euler 15'; it's 'Wow after a bunch of these Euler problems I think I am finally starting to get functional programming'.
I wonder whether it's just that programmers who enjoy functional programming are also the sort of people who enjoy Project Euler problems. Since most of the problems are fairly mathematical, they also tend to have clear and concise expressions in functional languages.
New to FP here as well (couple of years playing, more serious work in last few months)
It used to bug me too, but then I realized that common mathematical problems are the only "easy" way to explain how some things work.
Put another way, the problem domain in most applications is laid bare in FP. So your structures are intricately tied to whatever you're doing. You can either put up with a 30-minute "backstory" on why you're writing function foo, or we can just go with some kind of math deal. Usually authors pick the math option.
I found that once I could plow through writing short snippets, then I could start reading example code from the web. That helped a lot.
For me one of the real eye openers was that I'd gotten to the end of a fairly long book on FP without seeing a single assignment of a value to a variable.
I have just finished the first iteration of a web app written in clojure and in the several hundred lines of code, I have a single variable which changes state.
I am using hiccup for generating the html, compojure and ring for routing and request/response handling, jetty as the webserver and postgresql as the database
As of now I am just using my own. The user can create an account with username/password. When they login, it will associate the user with the session object. Session management is handled by ring, although the session data resides in memory only. I have a function which wraps around the routes which require the user to be logged in and checks the session to make sure the user is not nil.
Thank you for the reference to Project Euler. I'm learning Scala right now and it gave me just the right sized challenges for testing my knowledge. They're big enough to take time and thought, but small enough that you can solve them within the CLI interpreter.
I've used Erlang for a while, although sporadically. Honestly, I think I can do more with less code in Ruby, though. Erlang's great for the things it's good at, but brevity and clarity are really things I think are critical.
Here's a small example I bumped into the other day, providing a default value if a hash value isn't present:
foo[:bar] || "beebop"
vs
case (catch dict:fetch(bar, Foo)) of {'EXIT', _} ->
"beebop";
Val -> Val
end
Dunno about Erlang, but in Haskell, you can actually call this function ||:
import Prelude hiding ((||))
import qualified Data.Map as M
import Data.Maybe
(||) = flip fromMaybe
main = print $ result || "OH NOES!"
where result = M.lookup "baz" map
map = M.fromList [("foo", "bar"), ("bar", "baz")]
ghci> main
"OH NOES!"
With some typeclass magic, you can even make this work for arbitrary types. But don't waste your time with this, since it's already built in as `mplus`:
ghci> Nothing `mplus` Just 42
Just 42
ghci> Left "OH NOES" `mplus` Right "it worked"
Right "it worked"
* foo.get(bar) will return None if the element is not there
* foo.get(bar, "beebop") does what your Scala example does
* foo.setdefault works just like foo.get. However, if foo did not have key bar when it was called, it will fill the key in with the default value before returning.
* collections.defaultdict is also worth a look.
If you really start studying FP literature you'll discover that an enormous amount of ideas that are in vogue in today's languages have been invented years ago by functional programmers. For example, this paper from 1965(!) describes DSLs: http://www.cs.cmu.edu/~crary/819-f09/Landin66.pdf
I think learning a language like Haskell can be extremely good for you as a programmer. The problem is that you just can't expect to be productive, if you're new to it, and that might be very frustrating if you're doing to do work. However, just as jacquesm writes, if you're doing it for fun you'll learn a lot (that you can sometimes apply directly to your normal programming).
There are about a thousand FP programmers to every imperative programmer, if not ten thousands. They use a tool you may have heard of, called "Excel", which is quite limited in scope.
It is an FP subset which is at the same time trivial to understand (much more so than imperative programming for most users!), and coupled with a usable I/O capabilities, is surprisingly sufficient for many uses.
(IDE, documentation, maintainability all suck, though; I wouldn't recommend it as your main FP tool if you can avoid it)
Yes! Excel formulas === FP! And as you say, there are orders of magnitude more Excel users than imperative programmers, so FP can't be as hard as is usually claimed, and certainly not as "unnatural".
(Before Excel 5 and VBA that Joel Spolsky claims he invented, macro language in Excel was also FP; it was a crazy but fascinating language in which I developed a whole billing application (in 1992...) I miss this language.)
it's funny, in French engineering schools we have the opposite reaction; in "prep" schools students are taught OCaml which is their first programming language if they're not geeks.
Functions returning functions seem a natural thing as they are used to the exact same kind of abstraction in math (and even sometimes order 3+ functions when you study duality!). Conversely, they are initially puzzled when they are taught Java in their engineering school because of the difference between static variables and attributes, constructors and other unnatural concepts.
It's great that more people are exposed to the functional programming style. Kudos to OP for trying something new.
It bugs me whenever FP people talk about state being bad as if it should be avoided at all cost. State is bad if its scope is not carefully managed. Global state is generally bad because its scope allows the whole program to modify it, making it difficult to follow its validity. Local state maintained as a local variable in a function is perfectly fine. Its scope is small and its changes can be tracked easily. Pure functional code actually also implicitly maintain state in their parameters and return values, and the passing of the return values as parameters to next function.
It's ultimately about making code easier to reason about. Immutability (at least as a default) makes the dataflow between independent portions of your program clearer, since every value is determined by where it came from, not where it came from and everything that could have potentially touched it along the way.
One thing you haven't mentioned but it is related to anonymous functions (or lambdas) and is an important part of the fp style is passing around functions as first class objects. It is quite unusual in imperative programming and it is normally only used there to provide callbacks.
Let's say, you want to write a function that exports your video library to an arbitrary medium. In FP, one way to do this is to create generator functions that create DVDs, Blu-Ray discs, etc. Then your export function would take the input and a generator function, and export the library using that function. In Common Lisp:
I'm going to do a completely separate post on the subject of first class functions because I think it is too complicated a subject (and with too many implications) to be squeezed in there as an aside, besides that I don't think I'm qualified just yet to write the article in a strong enough way yet. More understanding is required first.
It must be funny to all the FP gurus here to see someone struggling to understand the things that are second nature to them, but I find that it is surprisingly hard to teach this old dog a new trick. One part of me wants to say 'enough of this' all the time and reach for a C compiler just to get the job done :)
Javascript's treatment of anonymous function is the easiest to understand for imperative background since it uses the same syntax as a named function.
Defining an anonymous function:
function(a, b) {
return a+b;
}
Giving an anonymous function a name (or assigning to a variable):
var add = function(a, b) {
return a+b;
}
Defining a function with a name (just a shorthand of the above):
function add(a, b) {
return a+b;
}
This makes it clear that the object stored in 'add' is a function object and can be passed around like other objects. That's the essence of the 'function as a first class object' concept.
I haven't had the chance to test it out yet, but my impression has always been that first-class functions should be presented to imperative/OO programmers as a replacement for polymorphic functions.
Frequently, for an abstraction X where I need different but similar behavior in different situations, I'll implement X by passing around functions in Scheme or Clojure, but I'd implement X with inheritance and polymorphism in C#. The frequent advantage (in my opinion) is that passing functions is more flexible, conceptually simpler, and usually shorter to write.
function foo(x) { return function(y) { return x+y; }; }
bar = foo(3)
bar(5)
// Returns 8, wait how did the x in the inner function remember the 3?!
// It's supposed to be gone already because the call to foo is over...
One way to understand this is to notice that it always "just works". It seems like magic. The 'aha' for me was when I learned how closures are implemented.
But you'd probably only get hung up on that being "magic" if your mental model of programming assumed stack-based scope for everything.
Besides, how about this pseudocode?
class Foo {
field x;
constructor(x) { this.x = x; }
fun add(y) { return x + y; }
}
bar = Foo(3);
bar.add(5) // returns 8, wait how did the x in the object remember the 3?
Stack based 'mental' scope is one of the bigger things to 'unlearn'.
When I look at a function I build up a mental image of what is going on on the stack as the function executes. Things that I don't see declared within the function or that are explicitly allocated update the heap. To get away from that image is very hard to do at first.
I compare it to learning real life languages, like English versus German. If you've never seen a language that has declinations in the endings of words then it can completely overwhelm you. Likewise tonal languages are strange when you've only spoken English or German.
Each of those opens up the perspective you had before you learned that language to show you that there is more under the sun than what you thought was 'normal', and that your way is not always the better one.
Indeed. For some reason, closures never tripped me up, but continuations took a while to wrap my head around. (I think because I tried to learn continuation-passing-style first. While also learning OCaml.)
Since you know C, it might help to think of continuations in terms of setjmp/longjmp, but with multiple, persistent stacks. (Same with coroutines, but coroutines and continuations have a lot of overlap.)
Yep, that's how closures are implemented. Changing your mental model of programming from stack based to what you could call "lexical scope based" is what's difficult here yes.
One way to understand closure is to know that a function object actually contains both the instruction code and an environment table holding the variable bindings, bar = [ code = { return x+y; }, env = [x:3] ]. When bar is called, it uses x's value in its environment.
Yes, although it gets trickier with mutation. For example:
x = 0
foo = function(){ x += 1 }
bar = function(){ x -= 1 }
Somehow you need to update bar's x too when you call foo and foo's x when you call bar. One way to do this by wrapping x in an object of its own, for example in a single element array that just contains x. I think the implementation of closures in Mono got this wrong, calling foo would have no effect on bar and vice versa (perhaps it's fixed now).
I was hoping to keep thing nice and simple. :) You brought up a good point in the subtle problem in using closure. Yes, in some implementation of closure, both foo and bar access the same closed variable x.
The best way to treat this is to view closed variables as global variables in different scopes. Global variables imply they are shared.
e.g.
x = 1 // environment in the global scope
function baz()
// environment in baz's scope shared by foo and bar
x = 3
foo = function() { x += 1 }
bar = function(){ x -= 1 }
return [foo, bar]
foo1, bar1 = baz() // create a baz_env1 [x:3]
bar1() // baz_env1 [x:2]
foo1() // baz_env1 [x:3]
foo1() // baz_env1 [x:4]
foo2, bar2 = baz() // create a baz_env2 [x:3]
bar2() // baz_env2 [x:2]
x = 10
// At this point,
// global environment's x is 10
// baz_env1 x is 4
// baz_env2 x is 2
Yes, that's actually close to another way of implementing it. But you can't just blindly assign the scope of baz to foo and bar, because foo and bar might have local variables of their own. Another issue is that baz might have local variables that aren't used in foo and bar, so when baz returns you want the garbage collector to be able to reclaim that storage (otherwise it could lead to arbitrary space leakage if these variables point to large structures). You need a tree structure of environments in the general case.
Yes - everything will act as if that stack frame was heap-allocated and still exists* . You can modify the value(s), define multiple functions sharing the same variable bindings, etc. A lot of common language features (such as conventional objects) can be implemented as syntactic sugar on top of closures. (Same with continuations.)
* Compilers/interpreters are free to do optimizations that won't affect results, like only heap-allocating the closures that escape their scope.
When I'm struggling with what a programming concept means, I find it helpful to try implementing it in a toy interpreter. Efficiency is irrelevant, it just needs to model the concept correctly.
Many concepts really aren't that complicated if you're not worried about optimization, and getting to a working model tends to shake out the aspects you don't completely understand. (This is also why books have exercises.)
> When I'm struggling with what a programming concept means, I find it helpful to try implementing it in a toy interpreter.
That's my 'I have understood' benchmark. If I can re-implement something without any reference to outside sources.
My goal is to write a little lisp or scheme from the ground up from nothing but the lambda calculus and some bits & pieces. It'll be slow as molasses but it will help me to really grok it.
That's why I've been reading up on all this stuff over the past year or so. After that I think I'm ready for something more involved, like clojure. I realize that this is not a very efficient way of learning but in the long run it tends to pay off. Knowing what goes on under the hood is an advantage.
Yeah, it seems like the long way around, but it really adds up over the years!
You'll probably want to get Quinniec's _Lisp in Small Pieces_, if you don't have it already. It covers several aspects of implementing Lisp interpreters and compilers, the lambda calculus, a bit on semantics, etc. (It mostly focuses on Scheme.)
When you actually read this what do you do? You work inside-out to understand it. You figure out what 'data-set' is, then you figure out what '(lambda (x) ...) does to it, and so on.
You (or me at least) also write the code inside-out. You start with the data, and an idea of how to transform it, and you work your way towards that transformation.
This, in my opinion, is one of the greatest strengths that OOP has over FP: data.map(...).reduce(...). It doesn't really have anything to do with OOP, you could just as well have such a syntax for calling functions. In F# you do have the |> operator that does something like this.
This may seem superficial, but it helps readability a lot. The human mind (or mine at least) is just not well suited to unraveling nested structures.
The odd thing is that the semantics of the Unix pipeline model is more similar to lazy sequences in Haskell or Clojure.
It is common to have one function generating a lazy sequence, another taking the output of that function and generating another lazy sequence, and so on until you get your final results out at the other end. The nice thing is that at no point in time is it necessary to have the entire sequence in memory.
A Unix pipeline is similar, in that one process consumes the output of another process as it becomes available, as opposed to having to wait for the first process to complete its task before the next process in the pipeline can start.
I'm writing from a phone and lost a longer reply to expired link. In short:
You and the OP (cf. his assumption that you read functional code inside out) seem biased towards a chronological, bottom up reading of code.
An outside-in reading of prefix code is useful to get a top-down general grasp of the structure.
Both approaches are useful and complementary.
This duality also applies when writing code. Cf. "wishful thinking" in SICP: sometimes you want to assume away auxiliar or extraneous functionality to sketch an outline of your program.
In both reading and writing, alternating approaches helps to find the kernel of the problem quickly and to build a whole understanding at your pace, so you don't get bored or stuck.
To that effect, I find prefix notation more balanced, that is, easier to read both ways.
As a practical note, if you follow the 80 column convention long().call().chains() are space hogs and awful to break up. The equivalent problem in lisp is solved with a two-space indent.
But that's just an instance of the syntactic sugar debate. My point is not about notation but how you approach the code.
Stuart Halloway has a great explanation of anonymous functions in "Programming Clojure." He identifies the specific conditions where you might choose to use an anonymous function given that, for readability reasons, naming functions is usually a good idea.
I tried wrapping my head around Clojure but I just couldn't. I'm currently diving into Scala and finding it much easier to get into coming from an OOP background (I'm a Java developer by day and a Rails/Objective-C developer by night).
From the article: "You have to train yourself to start the understanding of code you're looking at from the innermost expressions, which are the first to be evaluated."
The author is in for some even more mind bending, when he eventually has a look at lazy languages.
Lazy evaluation: evaluate an expression only when you are actually going to do something with the result. For instance, in a generator you can generate 'infinitely long lists' because only those values that are consumed are actually generated.
Is that what you mean ?
Or do you mean when that principle is expanded to the whole language ?
Welcome to the party, Jacques! I think you and I started about the same time.
FP seems much richer than IP, but maybe that's just me. I know that once you get all the basic set operations, then you move on to continuations and Monads and it's like wow! A whole other world opens up. Then you can move on to all sorts of other cool stuff like super-scaling which kind of just "falls out" of FP. So it seems like there is more depth here for geekiness.
As far as bugs, I guess that the vast majority of bugs are related to either "state leakage" -- somebody tickling your variables while you're not looking -- or off-by-one errors. FP eliminates both of those. I know I try to stay as immutable as possible and my code feels a lot more solid than it used to.
The FP paradigm is (to me, even after 15 years of imperative programming) so much more natural for development, since you're able to sanely start attacking the problem directly -- instead of architecting a big-picture solution up front that's probably wrong anyway because you've ignored some detail you haven't yet discovered.
Building things with actions instead of objects just makes much more sense. Reuse comes much more naturally, and doesn't seem as contrived as a lot of OOP reuse seems. I've noticed that working my FP muscles out has made me a much better imperative programmer -- I write a lot more clever and effective code (not clever like 'tee-hee-no-one-will-ever-figure-this-out'!).