Adventures of an imperative programmer in the land of fp
jacquesmattheij.com
jacquesmattheij.com
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'!).
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.
"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.
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.
One speaks about the fact that you can learn the basic keywords and flow (as in how the language is parsed) using simple mathematic problems.
While the other speaks about solving real-world problems require more diversity.
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.
"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?
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.
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"
case (catch dict:fetch(bar, Foo)) of {'EXIT', _} ->
"beebop";
Val -> Val
end
default(Dict, Key, Default) ->
case dict:is_key(Key, Dict) of
true -> dict:fetch(Key, Dict);
_ -> Default
end. 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!"
ghci> Nothing `mplus` Just 42
Just 42
ghci> Left "OH NOES" `mplus` Right "it worked"
Right "it worked"The point was about the language in general, its verbosity, and the ability to string things together.
Stuff like this should be built into the standard language.
* 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.
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).
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)
(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.)
To illustrate, Common Lisp directly supports functional programming but not dataflow programming (though it's possible to implement as a library).
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 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.
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:
(defun make-dvd () ... )
(defun make-blu-ray () ... )
(defun export-library (data make-medium) ... )
(export-library *my-data* #'make-dvd)
(export-library *my-data* #'make-blu-ray)
(export-library *my-data* (lambda () ...))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 :)
Defining an anonymous function:
function(a, b) {
return a+b;
}
var add = function(a, b) {
return a+b;
}
function add(a, b) {
return a+b;
}
If you have the time, I highly recommend watching the SICP video. It very gently introduces most of the FP concepts and many others. It's a classic. http://freevideolectures.com/Course/2378/Structure-and-Inter...
Your example would be translated as:
(lambda (a b) (+ a b)) ;; making an anonymous function
(define add (lambda (a b) (+ a b))); ;; calling the anonymous function "add"
(define (add a b) (+ a b)) ;; syntactic sugar for above.
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.
Do you see it that way?
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...
That's closure. Easy, right?
x = 0
foo = function(){ x += 1 }
bar = function(){ x -= 1 }
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
Is that correct?
* Compilers/interpreters are free to do optimizations that won't affect results, like only heap-allocating the closures that escape their scope.
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.)
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.
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.)
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?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.
In programming languages it is much the same way.
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.)
That's exactly the thing I used to help me visualize it :) Funny you came up with the exact same model.
Setjmp and longjmp are by the way probably two of the most abused calls in the C runtime package. But when you need them, you need them badly.
First class functions may be exciting. Not having to give a name to your functions, is not.
foo = 'foo' baz(foo)
When a language forces the same thing upon you with functions (damn you, Python!), it's rather nice to be free of it.
If you just want to compose functions or so, you do not need to name them.
But I see your point.
Take: (reduce (lambda (x y) ...) (map (lambda (x) ...) data-set))
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.
Compare to:
((data-set (lambda (x)...) map) (lambda (x y) ...) reduce)
Of course, this brings up a lot of edge-cases. Ex.: Where does 'define' fit into this? You really want define and the variable name at the beginning.
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.
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.
http://clojure.github.com/clojure/clojure.core-api.html#cloj...;
So you can take
(foo (bar (baz "Hi!")))
(-> "Hi!" baz bar foo)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.
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.
Is that what you mean ?
Or do you mean when that principle is expanded to the whole language ?
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.