2009-06-15

Haskell horrors

As a beginner Haskell programmer I still remember its horrors. Time to write them down. It is my first functional language, so I have to learn new concepts and new language in parallel, but it is fun. I hope these notes may be useful to other beginners. I'll give also some examples in Python, to show that Haskell in fact is not so scary for beginners.

1. Lambdas

We call it lembas or waybread, and it is more strengthening than any food by men, by all accounts…

This is why I learned about Haskell. I was just curious what those lambdas are. A paper Conception, evolution, and application of functional programming languages by Paul Hudak was really helpful to get started (It's kind of old, and, probably, there are better introductions, but I read this one first).

Lambda expression is an essence of ‘function’: it's an expression of form

\lambda x \;.\; \text{expression with $x$}

The value of this expression is a function, which takes one argument (x) and calculates something with it (an expression on the right hand side of the dot). There is much mathematical theory about lambdas, but sometimes I just think about \lambda as a keyword to define functions. In fact, I was already used to lambdas in Python, where they look like:

lambda x: expression with x

They were very useful in filter() and reduce(). They may be used almost anywhere where a function name is required, but lambdas don't have names. Hence, they are called Anonymous functions.

Sometimes in Python I give them names to define new functions on-the-fly

add_42 = lambda x: x + 42

Name add_42 now refers to a function. This is almost the same as defining functions in a more usual way:

def add_42(x):
    return x+42

Now, what about Haskell? It's pretty much the same. \ symbol stays for \lambda, -> stays for dot:

\x -> expression with x

We can even give them names to define reusable functions:

add_42 = \x -> x + 42

Very similar, isn't it?

There is a subtle point. As soon as I started reading about Haskell, I saw lambda-expressions which looked a little bit strange at first:

\x -> \y -> an expression with x and y

What are those multiple ‘arrows’ I asked? The answer was really simple and very helpful to understand Haskell code.

All Haskell functions are functions of one argument. This may sound like a restriction initially, but then it turns out to be a very convenient concept. A function of n arguments may be represented as a function of one argument producing another function of n–1 arguments. This is called currying.

Once we know this, we can read any expression with many arrows:

\x -> (\y -> an expression with x and y)

The value of the expression is a function which takes an argument and produces another function which takes yet another argument. This expression as a whole behaves as if it were a function of two arguments. For example, we may apply such a function to two arguments in ghci (Haskell interpreter):

ghci> (\x -> \y -> x + y ) 3 4
7
Of course, there is a shorthand form where we can write it as a function of two arguments (please note also that we don't need parentheses for function arguments):
ghci> (\x y -> x + y) 3 4
7

But it is very useful to know that internally every function of two or more arguments is actually a function of only one argument. This also helps reading function types later. For example, a type of map function reads like

map :: (a -> b) -> [a] -> [b]

I usually read it like this: ‘function map takes two arguments, a function from a to b and a list of a and produces a list of b’. But sometimes it is more natural to read as written:

map :: (a -> b) -> ([a] -> [b])

‘A function which takes a function from a to b and produces a function which converts a list of a to a list of b’.

These simple ideas about lambda functions were enough to get me started with Haskell and to understand most of the examples and tutorials.

2. Equals sign

‘If there's no meaning in it,’ said the King, ‘that saves a world of trouble, you know, as we needn't try to find any. And yet I don't know,’

As for me, equals sign = was probably the most important Haskell symbol to understand the language. I think its semantics is underemphasized in tutorials. For example, it's the only ‘keyword’ which is missing on a Haskell keywords' wikipage.

Unlike in most imperative languages where = means an assignemt (i.e. an action), in Haskell it means that its left hand side equals its right hand side.

‘Equals’ is not ‘becomes’. It means that something is equal to something else. Always. Just like in mathematics. a = b in Haskell means that a equals b by definition, a is equivalent to b.

So, = in Haskell serves to write definitions. It defines all sorts of things, but it defines them statically. It doesn't depend on the order of execution. It is something we may rely upon.

This may sound too evident, but this is a major difference for anyone with an imperative background. Now we may give names to our anonymous functions:

add = \x -> \y -> x + y
To tell the truth, it's not very readable, so most of the time functions are defined like this:
add x y = x + y
But this one is still a definition of add.

3. Type classes

Significant benefits arise from sharing a common type system, a common toolset, and so forth. These technical advantages translate into important practical benefits such as enabling groups with moderately differing needs to share a language rather than having to apply a number of specialized languages. — Bjarne Stroustrup
Type system in Haskell is beatiful. It feels very natural to reason about. And probably type classes is the least alien concept for people coming to Haskell from procedural/OO world. At least they are for me. But type classes are not the same thing as classes in C++ or Java. They are much more like abstract template classes in C++, because they
  • define only an abstract interface (don't provide a default implementation)
  • allow independent implementations (that is any class may become an instance of the type class if it implements class methods)
  • are polymorphic by their nature and support inheritance
  • don't have state variables
Once it's accepted that type classes are not C++ classes, but abstract interfaces, and class instances are not “objects”, but implementations of the abstract interfaces, Haskell becomes friendly and easy. I suggest to read an excellent a wiki article OOP vs type classes which covers this topic in much more detail.

4. Monads

And as every present state of a simple substance is naturally a consequence of its preceding state, so its present is pregnant with its future.

Now matter how gentle your introduction to Haskell is, sooner or later you stumble into the wall of Monads. Yes, there is some serious abstract mathematics behind them.

But I learned that it is not necessary to understand abstract mathematics to use monads, and they are indeed a very nice programming technique. They looked a little bit strange to me initially, but understanding monads is easier than memorizing countless OO design-patterns and using them right.

There are plenty of tutorials on monads, so I wont repeat them and expect that you've already read one or two. So, what's wrong with monads? For my imperatively prepared mind spoiled with years of object oriented thinking, monads looked strange. They may look like an abstract container class with a mystic >>= method:

class Monad m where
  return :: a -> m a
  (>>=) :: m a -> (a -> m b) -> m b
  fail :: String -> m a
Well, if return is a constructor, then why such a strange name? If this is a container class, how can I take values out? And what's the point of applying a function inside monad (>>= method, also known as bind) if we cannot take the result out of it?

Let's answer the last question first. What is the purpose of bind (>>=)? Monads are and are not containers. They are wrappers around computations rather than values (return). But they wrap computations not to store them conveniently in monadic boxes, but to link them together. Think standard bricks rather than boxes, or Adapter pattern. Each monad defines a standard interface to pass the result from one computation to the other (>>=). No matter what happens, the result is still in the same monad (even fail).

The most simple programming analogy I found is pipes in unix shell. Monads provide a unidirectional pipeline for computations. The same unix pipes do. For example:

$ seq 1 5 | awk '{print $1 " " $1*$1*$1 ;}'
1 1
2 8
3 27
4 64
5 125

seq produced a list of integers. awk calculated cubes for all of them. What's cool about this? We have two loosely coupled programs which work together. Text stream flows from left to write, each subsequent program in a pipe is capable to read this stream, do something with it, and output another text stream. Text stream is a common computation result, | binds computations together.

Monads are similar. >>= takes the inner computation from the monad on the left and puts it into the computation on the right, which always produces the same monad. You probably already know that lists and Maybe type in Haskell are monads. For example, if we have a simple computation which returns a pair of a number and its cube into the monad:

\x -> return (x, x^3)

then we can ‘pipe’ the list into this computation:

ghci> [1,2,3,4,5] >>= \x -> return (x,x^3)
[(1,1),(2,8),(3,27),(4,64),(5,125)]

Please note that we received a list of pairs. It's the same monad (the list). But if we ‘pipe’ a Maybe value into the same computation, we get the same monad as input (Maybe):

ghci> Just 5 >>= \x -> return (x,x^3)
Just (5,125)

You see, we can construct a pipeline of two computations, and the behaviour of this pipeline depends on the context (i.e. on the Monad instance), not on the computations themselves. Unlike unix pipes, Monads are type-safe, type system takes care that the output of one monadic computation is compatible with the input of the other. And unlike unix pipes, we can define our own binding rules (>>=). Like ‘don't join more than 42 computations in a row’ or ‘look at the input, and do one thing or the other’. Monads encapsulate rules how to bind computations together.

Now, I hope, you understand monads at least as well as I do (not necessarily perfectly). I'd like to discuss some mnemonics. Why return is named ‘return’?

In most languages, return returns result from a function. In Haskell, it acts as constructor for monads. Weird. Well, let's look at how >>= works, we see that it extracts a value from the monad on the left, and then binds it to the argument of the function on the right. This function should return the result back into monad, so that the next >>= can work. This is the first mnemonics.

The second mnemonics. On the top level any Haskell program is executed in IO monad (main's type is IO ()), which can do input/output (and sequential operations in general). Thus, monadic code is executed on the top level and it calls any pure code when necessary, not otherwise. So any pure value if not discarded is eventually returned into the monad of the caller.

With these two explanations the name return does not sound so weird for me as before. I don't pretend these explanations are technically correct.

The next question, how to take a value of the computation out of the monad? Well, it's not always possible by design. For example, you cannot take a pure value outside of the IO monad. If we have such a one-way monad, the only thing we can do, is pipeline the value to the next computation. Fortunately, Haskell has a nice do-notation, which makes such pipelining look almost identical to imperative programming languages. These two programs describe the same thing, with do-notation:

main :: IO ()
main = do
  name <- getLine
  putStrLn ("Hi, " ++ name)
and with explicit >>=:
main :: IO ()
main = getLine >>= \name -> putStrLn ("Hi, " ++ name)
An equivalent Python program:
from sys import stdin, stdout
if __name__ == "__main__":
    name = stdin.readline()
    stdout.write("Hi, " + name)
However, sometimes it is possible to take the pure value out of the monadic computation. This is not possible with the standard monad interface, so the developer of the monad should provide means to extract values. For example, it is possible to extract values from Maybe monad using fromMaybe function:
ghci> fromMaybe 0 $ Just 3
3
ghci> fromMaybe 0 $ Nothing
0

Résumé on monads

So, bind (>>=) allows to put various monadic computations together and combine them. Anywhere, where we have a chain of computation, monads fit naturally. Particular monad implementation may encapsulate custom rules of combining two computations together. Name return may be confusing for beginners, but we have to remember that it returns a value into the monad, not from the monad. Understanding this helped me a lot.

5. Scary words

I know nothing except the fact of my ignorance.
Finally, I have to acknowledge, after months of studying Haskell and being able to write useful programs in it, there is still a lot of concepts in the Haskell world which I don't know anything about or have only a vague idea. I call these kind of concepts “scary words”. But still I see people creating and using new libraries which implement those concepts. Let's face it: Haskell remains a test bed for research. It's both good and bad. It's good, because it feels like a bleeding edge is really close, and you may benefits from the new approaches if you like. And it's bad, because if you want to use some cool new library, you may find that it heavily relies on a concept you are not very comfortable with. For example, there is a modern XML library, HXT. It uses arrows heavily. Arrows provide more general combinators than monads, but it took me much more than a day to understand them. Strictly speaking, Arrows are not part of the language, but they are an actively used concept in practice. There are many other examples like this. I think that it's important not to be afraid of the “scary words”. Fortunately, all the concepts are well documented. There are papers which explain the ideas. Personally I decided to learn such concepts as need arise. At least it promises to be manageable and entertaining.

Conclusion

I mentioned 5 simple ideas which helped me to get used to Haskell: lambdas are just a way to write functions, a function of two or more arguments is actually a function of only one argument which returns another function, type classes correspond to abstract polymorphic interfaces in the object oriented wold, monads are just a tool to merge computations together, and scary words are just scary words. I hope this helps someone else. This post is also available in Russian.

2009-06-09

Debian Lenny on Samsung X22

The laptop

My new laptop is Samsung X22. I like its serious, almost ascetic look. The screen is matte, not glossy. The weight is just within my requirements: 2.18 kg (unfortunately, an AC adapter is bulky). What's more, the laptop came without Vista. I don't mind having WinXP Pro around just in case I need to do test some software on Windows (or to play games). The keyboard is big and very similar to the one of my previous laptop (only Ctrl and Fn are swapped). Nice things to have: 1.3 MP webcam and SD/MS/xD card reader (I have some xD cards, but many embedded card readers don't support them). On the flip side: the laptop is rather big (14"), it is not water-shock-whatever-proof, the screen is only 1280×800 and its viewing angle is relatively narrow, and the battery life is short. Bonus: Bluetooth, ExpressCard slot, HDMI, optical drive.

This is the first time I bought a laptop with discrete graphics (Ati Radeon HD2400 aka RV610). The open source driver does support 3D only in experimental branches, but since I don't need 3D right now and AMD/Ati was kind enough to release the specs, some code and programming guide, I hope this card will have good open source drivers in the future. Anyway, with Intel I could not use 3D neither :)

Hardware: lspci, lsusb and dmidecode.

Installation

I used netinst image of Debian Lenny (5.0.1) and installed from a USB pen drive. This was the first time I tried Debian graphic installer. Well, I liked it. Probably, partition editor was not very GUI-sh, but it's OK. I installed i386 kernel.

The installer asked me for iwlwifi proprietary firmware (I didn't have one nor didn't put it on the installation pendrive). So, I installed from ethernet. Installation was smooth.

Post-installation

Wireless

I installed firmware-iwlwifi package, and the wireless now works perfectly. For convenience, I replaced network-manager with wicd. I like it more.

Keyboard

Some Fn-combos don't work. Most notably: Fn+(F2|F4|F5|F8|F9|F10|Up|Down). These keys don't produce any xev keycode. Among features which are not available are manual brightness (Fn+Up/Fn+Down) and wireless switch (Fn+F9).

I found a kernel bug (almost resolved) with another Samsung model: #12021, and another similar Debian bug #475851 with Samsung Q45. After reading through it, I managed to enable brightness buttons with

$ sudo setkeycodes e008 225 e009 224

Finally, after a small patch to hal-info, all the keys work (at least, generate xev codes).

Good news: sleep button, mute and volume buttons work out of the box.

Video

radeon driver in Debian Lenny is working OK (2D), but XVideo is not enabled by default, so probably I have to try a newer kernel or rebiuld the driver. Up-to-date version claims to support XVideo.

Proprietary Ati driver (fglrx) works too; (hint: enable non-free repository and install fglrx-driver, run aticonfig).

I tried also newer radeon driver from the unstable (since 6.12 radeon supports video and 2D acceleration on R6xx). In fact, HD video played even better than with a proprietary driver. Though I couldn't get proprietary fglrx working with X.org from unstable.

Webcam

Webcam just works. I tried it in Cheese and in Skype. Both work. Picture quality is good. It seems to be the same Vimicro webcam (USB ID 0ac8:c302) used in Samsung Q45 notebook.

Sound

When I installed Lenny, sound was playing without problems, but I could not get microphone working. As usual with Lenny and Intel-HDA hardware, I had to build newer ALSA (as I did for eeePC 901, link points to a post in Russian). To make mic working on X22 I also had to add in /etc/modprobe.d/alsa-base this line:

options snd-hda-intel model=ultra
This HDA Intel Sound HOWTO was very helpful. I found, that Samsung X22 uses Realtek ALC262 codec. Then, I tried some ALC262 models, and model=utlra worked.

Suspend

Fn+Esc did not restore screen/backlight on wake up. Blind typing upon wake up was useless.

I found, that either

s2ram -f -a 2
or
pm-suspend --quirk-s3-mode
suspend and restore the session normally. In X they restore the screen perfectly, but in console they don't turn on backlight. However, Ctrl+Alt+F7 switches to X and the backlight is restored. Minor glitch: when going to suspend, the screen is filled with blinking ’ñ’. Not a big deal, but I don't think it's normal.

I edited /usr/share/hal/fdi/information/10freedesktop/20-video-quirk-pm-samsung.fdi, and the snippet corresponding to X22 now looks like this:

      <!-- this does not work on my SX22S! -->
      <match key="system.hardware.product" string_outof="R40/R41;CoronaR">
        <merge key="power_management.quirk.vbestate_restore" type="bool">true</merge>
      </match>
      <!-- I use this one: -->
      <match key="system.hardware.product" string="SX22S">
        <merge key="power_management.quirk.s3_mode" type="bool">true</merge>
      </match>

Now Fn+Esc works as intended.

Optical drive

It seems to support most of the CD and DVD media, but I didn't use it much yet. It is reading CDs without problem.

Card reader

Works with my xD and SD cards as intended. I don't have MemoryStick cards to test.

Things not tested

I didn't try HDMI, ExpressCard slot, Bluetooth at all.

Links