Sunday, February 10, 2008

The Set of All Truths

Boolean algebra is definitively out of fashion, really. Set theory returns wrapped in glory! Don't believe me? Let's see...

Everybody that I know outside of computer science tend to assume a lots of mathematics is involved while programming, when in reality we are doing algorythmics. Obviously we do some algrebra and in the past, there was a lot of boolean algebra but times are changing, for the better. What is the main use of boolean algebra?  Control flow, stop condition, exception etc... All things that procedural and OO use a lot.

Functional programming on the other end tends to have a lot less control flow instruction as there is usually a better separation of concerns between transforming an item and working on collections. This is even truer for lazy language since identity for series or stream can be used without polluting them with "stop condition". This separation of collection processing and single transformation is what brings back set theory to flavor of the day. (Just check C# 3.0 Linq if you are not convinced!)

In FP we tend to write our set of single instance transformers and our set of collection processing facilities. Most of the time I feel like I'm using tools from both palettes to assemble new solutions. Oftentimes I find myself playing with sets of data transforms with other sets, filtering, taking difference between sets etc.

And this is true both in Haskell or Common Lisp in my experience.

On the other hand there is usually so much boilerplate code to be repeatedly done and control flow in procedural programming that the "set" nature is not readily apparent.

I said to a friend lately that Haskell was nice but very hard to work with when one is tired compared to say C++. And it somehow make sense, you are rarely dealing with boilerplate or skeleton code in Haskell. It feels like you are always working in on the problem devoid of distraction. I guess you could say that's a nice aspect of C++ even tired you "feel" productive as there is so much banality to type to get to the essence of a problem :P

Cheers and brush up your set theory skills, the functional storm is coming :)

Friday, December 21, 2007

My Type of Language...

Ok as I stated I'm not a Lisp zealot which language am I advocating?


Am I saying it is perfect? No
Is it going to be the Next Big Language? I wish... but No
Is it a silver bullet? No

Then why?

Some smart dude already said that learning Lisp, even if you never use it would make you a better programmer. I don't disagree with that statement but I'd say that it is an order of magnitude truer with Haskell.

The purity of Haskell forces you to think differently. You can't revert to do thing procedurally at least not easily. In fact, I'd say that by the time you know enough Haskell to code procedurally you will not want to do so anymore!

Ok it's pure... What else? It is lazy... this allows it to be even more declarative than other FP language and it also helps even more to separate what you want to do from HOW you do it.

By the way, bear with me on those characteristics I am pointing out, I'll be revisiting them in future posts.

Finally I'd say it's type system will open your mind forever. Haskell is not the only language using Hindley-Milner type system, static type inference, BUT it has Type Classes which makes this type system much more expressive and feel much less "constraining" than the version of H-M in Ocaml for example. Any languages of the ML family (they all have H-M type system) will grow you a third eye: a new axis to design and encode semantics.

What makes Haskell so special is that its version of H-M, it's purety and its lazyness will make you learn a lots of new tricks and bring you to a deeper understanding of all programming languages not just functionals ones, C++ and Java too.

Once you have learned Haskell I'd say you are in a better position to appreciate PL in generals. In my case I love Haskell but I tend to appreciate Scheme and Common Lisp in a different way now that I know Haskell.

More Haskell ramblings to come in future post but for now I'm finishing this post with my personal recipe to learn Haskell. This is an email I sent to a few friend:

Hello all,
I’ve been asked a few times lately about reference or how to learn Haskell. In case it is useful (or of interest) I’m forwarding here the informations I sent to a friend. This is by no means the only way to learn the language but in my experience this recipe is the “smoothest” ride to learn Haskell.
First a brief explanation why the language is SO different:
- There is NO variable, anytime you assign a value it is immutable. (mostly true of ML family languages like Ocaml)
- Purely Functional i.e. there is NO sequencing of operation (outside of Monads)
- Lazy Evaluation, if you call a function with 3 parameters the parameters WILL NOT be evaluated before you enter the function, only if they are used. Laziness allows a LOT of very clever and useful tricks.
- Referential Transparent, if you see a function called with specific arguments then EVERY TIME it is called with the same arguments it will return the SAME value.
In C++/Java, you design your Data Structure and you’re interaction between object, sometimes people design dataflow too.
In Haskell you have 2 additional and mostly orthogonal design Axis: Typing and combinators. Typing is a rather big one, in term of expressiveness. The more you’ll learn Haskell and the deeper your understanding of programming language becomes, including those of C++ and Java languages, this is especially true of template and the reason of their limitation. The second “new axis” is combinator, due to FP, currying (you’ll learn the word soon enough ;) ) you end up separating the pattern of processing for ONE instance and pattern of processing over Collection. The result is much more reusable code and a “by-layer” approach. The more a program grows the less code you have to write to add new features and or to modify to refactor, since your palette of combinator and of transformation becomes very complete.
To “learn” Haskell you need to learn roughly along 4 new “axis” or paradigms. Right now, no single book or paper covers these aspects. They are:
1. Functional Programming and mastering recursion in particular (FP)
2. Very strong typing with type inference (Hindley-Milner typing system). Which is used in all the language of the ML family (Ocaml, SML, ML and also in Haskell) always coupled with immutable variable i.e. constant.
3. Learn to type, i.e. to design the Type of what you are building. It is related to point number 2, but whereas point number 2 concerns the usage and implication of strong statically inferred types. This point refers to actually using typing as a mean to store information, logic and semantic in a program.
4. Monads. This is related to 1. (FP) but it is more advanced, and required in Haskell whereas it is optional for other functional language. This is a consequence of the purity of Haskell. Monads are GREAT, the more you know them the more you love them BUT… they are alien to our usual way of thinking.
To Learn Haskell efficiently and as easily as possible here’s what I suggest.
Point 1. Learning FP, read the book “The Little Schemer” and do all the exercise as you read. This book will bake basic recursive thinking in your brain and will introduce you to collectors function and how to combine functions together and accumulate functions to build new ones. This part will help to groke Monads (point 4.)
By the way no knowledge at all is assume to read this book. Your mom could!
To do the exercise as you go along I recommend picking PLT-Scheme

Point 2. The easiest way here is to do a simple tutorial in Ocaml or SML. Why? To not be distracted by laziness issues. Jason Hickey's Ocaml tutorial here is the one I began with. It also shows some twist about how recursions and FP work in Ocaml. Note that neither Ocaml nor SML are purely functional and you can actually code procedurally in both and “almost” object in Ocaml. The reason why I like this tutorial is because it is a more traditional format and use both functional and procedural and rather concentrate on typing, type deconstruction etc which all works in Haskell.

Point 3. The best way and by far to learn this is through the book “Haskell School of Expression” the book is VERY good to bring you to use the typing system as a design mean and the way it is written is interesting. You basically build a graphical object manipulation framework! Well written, well pace and easy to understand. It progressively introduces a lot of things. Its Monad introduction is too shallow, when he starts using them toward the end of the book you may have to stop and read a few paper to grasp what is there in order to continue. Once you understand the basics of the Monads, the State Monad exemple he uses is very good to build our understanding (he build a robot using the State Monad).

Point 4. That’s the hard one. Because of the different background we all have people don’t always get stuck at the same spot when understanding them. I consider them relatively easy to learn with “support” i.e. someone to explain the hard part, and VERY HARD to learn by oneself depending on what part you are blocked on. Why? Because most of the information on them is either on research paper or in very simple tutorials (too simple). So if there is something you don’t understand there is NO middle level reading that can help you (if you go by yourself) and the only chose is to resort to read research papers, typically many of them to see them present and attack the subject on differents angles until you find the one that “unlock” you. For exemple, by myself with nobody to answer my questions and just the research papers. It took me over 6 months to “taste” most of the subtilities of some Monads, State Monad in particular. Whereas I can explain the basic of it in less than one hour to anybody starting Haskell… Maybe it’s just me! By the way, a bone here :P Monads are the kings of combination they are themselves combinator!!!

The Point 1 to 3 can very easily be done without any support, through self-learning. Point 4, well… call me ;)


Saturday, November 17, 2007

The First One!

Hello all,

I've created this blog to share some random thoughts and cool tricks about functional programming (FP). Over the last year I progressively became a convert. Now I'd like to share my love for FP but also attempts to help those that start this journey.

I've worked for 14 years and most of these I was a devoted OO Developer, mostly in C++ and also in Obj-C. My increasing dissatisfaction was initially aimed at OO then I realized that the C++ implementation of object was also a big part of the issue. I loved the classic Design Pattern but the more I used patterns the more I realized that I spent most of my time coding support code for pattern instead of solving problem I was working on... Seeing the implementation of patterns in various languages (or the lack of since they were natively supported) increased my insatisfaction toward my "beloved C++".

At that point I started to do Generic Programming in C++, what some would call template hell. And I came to the realisation that it's not because you can do something that itis always a good idea to do it.

That's roughly the state of mind I was in when I stumble upon a copy of "On Lisp" by Paul Graham and within a few chapters I saw a new world open. From there I embarked on a journey to learn a new paradigm.

Being the first of my group of friends and coworkers to jump in FP I had to learn the "hard" way. Since then several of them have joined me in my interest and I try to help fast-track them as much as possible. Which is basically why I created this blog.

Although interested in programming language theory I am a software developer not a researcher. One of the problem I've encountered when I started was that a lot of information was available but more in an "academic" format.

It's cool to see new buzz words but what do they REALLY mean in the real world? That's also a little bit of what I hope to convey.

So at this point you may think: "Great yet another Lisp zealot! Exactly what we needed!!!" (sarcastically) ;)

But no I am not a Lisp zealot, I do not hate it but I came to FP to solves specific issues in the ways I see software beeing developed. I'd rather like to think that I'm an FP missionary lol.

Jean-Fran├žois Tremblay