On self study plans, again

Referring to my previous post, I have now, in the past few days, advanced deep into SICP's interpreter chapter (ch 4). Today I began reading the DIY Scheme interpreter tutorial previously mentioned. I managed to read the first five chapters, and I'm very satisfied so far. The tutorial does not try to teach elementary functional programming concepts, but maintains its scope by just showing how to write real software in Haskell.

Nowadays I'm rather busy writing my LLVM thesis and thus I have not yet got an opportunity to start reading RWH, a promise made a few posts ago.

Job needed

The job market is not the most active right now. However, I'm soon going to send some applications to certain promising places. Both University of Helsinki and Helsinki University of Technology are providing some research group and software developer summer trainee positions. I'm applying there but the number of available positions isn't plenty and I assume people are applying there en masse due to current economy.

Fortunately I'm still unfinished with my thesis so my current unempoyment is not harmful -- it's actually hastening my graduation. But I miss working as a software developer. Past four years in software business have been fun and I want to be there again, soon.

An apt definition of functional programming

While reading Jukka Paakki's paper on attribute grammars I found out that it contains a pretty apt definition of functional programming that I have been learning over the past year. So here it is for the public's delight (OCR'd, so the possible typos might not be original):

"The functional style of programming can
be summarized with the following characteristics:

• referential transparency
• higher-order functions
• lazy evaluation
• pattern matching

Referential transparency is the term used
traditionally to express that the value of
an expression depends only on the values
of its subexpressions, and that the value
of each occurrence of an object is the
same, irrespective of the context. In other
words, side effects are ruled out. Functions
being higher-order means that they are
first-class values and can, for instance,
be stored in data structures and
returned as result of function calls. Lazy
evaluation is tantamount to "nonstrictness,"
meaning that the value of an object is not
computed until it is actually needed, and
thus the value of an argument may be
undefined when calling and executing the
function. Pattern matching is a general
term used to express the mechanism applied
when trying to make X and Y identical in an
equation X = Y where X and Y are expressions.
Pattern matching is restricted in functional
programming to introduce bindings only to
the left-hand side X when solving such an
equation."
(Paakki, J. 1995. Attribute grammar paradigms—a high-level methodology in language implementation. ACM Comput. Surv. 27, 2 (Jun. 1995), page 236.)

What could be added is the concept of recursion.

Yaht is done

Referring to my previous post, I have now finished with Yet Another Haskell Tutorial. My intention was to do all of the exercises. I think I did over 90% of them which is good enough.

As mentioned earlier, my Haskell journey now continues with the Scheme interpreter tutorial. I'm also going to read through RWH as a side-side-project.

My favourite introduction to monads

It is said that the most difficult concept to grasp in Haskell is that of monads. I'm not trying to tell what monads are because it is already been done so many times and I'm not even expert enough to try that. Instead, I'm going to talk about my personal monad-learning experience.

A highly heterogenous set of monad tutorials have been written. Brent Yorgey recently posted a blog entry titled Abstraction, intuition, and the "monad tutorial fallacy" where he pointed out that the numerous metaphors given to monads, each of them purpoted to be _the_ methaphor that should make monads clear for everybody, are not helping but actually harming the learning process. The metaphors are actually hiding essential properties of the concept and thus making learning harder.

I didn't understand monads when I read that they are just like burritos either. I'm still uncomfortable with monads, but after reading several tutorials on the subject, I think I'm now starting to understand what they are useful for in pure, functional programming.

No single monad tutorial can be given the glory of having positively affected most my learning process. I think that after reading several examples of monad usage, I'm gradually grasping the idea of the abstraction they provide. The text that I feel is describing the subject in a very clear way, and that does not hide essential concepts, is Wadler's 1995 paper Monads for functional programming. The paper first describes several examples of tasks that are implemented unwieldy in a pure functional language without side effects. Then it proceeds to show how the same problems can be solved better using monads. The three monadic laws are given, as they should be, and in the end a parser implemented with monads is described.

My point is that people shouldn't be afraid of the original papers. Sometimes they really are useful in _learning_ the subject although occasionally they get lost in their excessively rigorous handling (for being educational for laymen) of the subject.

Recursion with Y

The following is written in Literate Haskell style.

Let us first write a recursive Haskell function that tells if a natural number is even:

> isEven n = if (==) n 0 then True else (if isEven (pred n) then False else True)

From Lambda calculus, we know the Y combinator, which returns the fixed point function for any function f:

> y f = f (y f)

The definition above satisfies the fixed point definition of f(x) = x.

Now let us define the isEven function again now using Y:

> isEven' = y (\f n -> if (==) n 0 then True else (if f (pred n) then False else True))

Above, Y binds its function argument on f, which results in a recursive call:

y (\f n -> if (==) n 0 then True else (if f (pred n) then False else True)) = (\f n -> if (==) n 0 then True else (if f (pred n) then False else True)) (y (\f n -> if (==) n 0 then True else (if f (pred n) then False else True)))

Partial application results in:

(\n -> if (==) n 0 then True else (if (y (\f n -> if (==) n 0 then True else (if f (pred n) then False else True))) (pred n) then False else True))

Now let's ensure that the halting conditon for the recursion works. Let's pass it a zero:

(\n -> if (==) n 0 then True else (if (y (\f n -> if (==) n 0 then True else (if f (pred n) then False else True))) (pred n) then False else True)) 0 = if (==) 0 0 then True else (if (y (\f n -> if (==) n 0 then True else (if f (pred 0) then False else True))) (pred n) then False else True)

The first condition evaluates to True and thus the whole expression evaluates to True.

If we pass an argument larger than zero, call it $, we get:

if (y (\f n -> if (==) n 0 then True else (if f (pred n) then False else True))) (pred $) then False else True)

The first condition above is the recursive function itself, which returns True for zero. So we pass it the predecessor of n. If the predecessor of n is even, n itself must be odd. Otherwise n is even.

Now we can test that it works for some small values:

map (\n -> (n, isEven' n)) [0..5]
[(0,True),(1,False),(2,True),(3,False),(4,True),(5,False)]

Self study plans

Self studying is always fun. Currently, I'm learning Haskell by reading Yaht and doing all the exercises in it. Almost done. In paraller, I'm reading through SICP which Santa brought kindly to me. The idea is to kill two birds with one stone (that's a terrible, violent idiom!) by writing a Scheme interpreter in Haskell. There is a promising tutorial to do just that in Wikibooks. After Yaht is done and the interpreter chapter been read in SICP, I plan to start the interpreter project.

And the bad news: the taocp project is currently halted :(

Saviour VCS

I have been writing my master's thesis for a few months now. I'm using git. Today it came to my rescue, really. I rm'd the wrong file, namely, the .tex file that contains my thesis as a whole. After a millisecond in shock, I recalled that I really am using a vcs. 1) man git-checkout 2) *magic* 3) back in business.