I was speaking with a friend the other day and we were talking about the interaction of effects and how to explain them.

One informal way to explain some additions to languages are that they are scale down localized structured versions of features that were largely available for the whole program. Let me explain: Did you start programming with an imperative language with global variables? (There is one called C that affected the minds of many people.) When you switch to an object oriented language, someone might have explained to you that there is no longer any need for real global variables. You may make these wannabe globals members of a class. You can turn methods that need the globals into members of that class as well. So they are global as far as the methods in question go, but they are not truly global.

In much the same way, we can explain yield. Programming languages have always had input and output operators - scanf-printf, gets-puts etc. However these operators are global with respect to your program. When you execute a printf, it is the output of the whole program, not of any one part of it. Yield on the other hand can be thought of as a localized input output operator. You can yield values from one part of the program to another part of the program. You get input from one part of the program. A method that yields is a packaged up opaque entity, a little sub-program, that communicates using yield with its consuming-context, the rest of the program.

We can explain exceptions in this way as well. In the absence of exceptions when there was a fault, the whole program would come down. It would core dump, modulo global error handlers. The whole machine does not come down, just the program that faults does. The environment that hosts the program may realize that there is a fault and do something about it. Its much the same with exceptions, but with the difference that only a part of the program "core dumps". Its a localized failure of the program that the environment (the rest of the program) can handle (or not handle, thereby making it a global failure).

So can you play this game or any other global program features, turning them into powerful localized structured operators?

I get irritated because too many people in the "computing" business don't understand the word "lambda". Its just irritating because at the heart of it, its just a simple fundamental idea, like the notion of natural numbers or counting. So just spend a few minutes, understand what it means and stay educated. In a few years (if not already), almost every language is going to expose something like a lambda to its programmers. So just pick up the idea ok?

This is a working description, it wont make you an expert on the Lambda Calculus. It might give you some intuitions about it though. Lets get started.

So assuming you are familiar with a C-like language, how do you write a function that takes an integer and returns it?

int foo(int x) {
    return x;
}

Now lets look at what this is saying, it says there is a function called foo, it takes an int which it names x and it returns an int. the body of the function has a single statement called return x. Great! Now, this function is a very famous one and is called the identity function (usually goes by the nick-name id). Also when we talk about functional programming we dont really care very much for the C-style types. So let's rename the function and drop the types.

id(x) {
      return x;
}

Don't worry too much about the types. Typed functional languages usually have a different notion of types from the C like languages. The types will come back, but in a bigger and better form. We however wont discuss any type theory in this article.

So now, what it is saying? It says here is a function called id, it takes some value that it calls x and it returns x. Ok, now lets take a look at this closely. In the syntax that we have here, the name of the function is part of the syntax. We would like to say - here is a function and then assign it the name id. So that we are able to look at the function and its name as two different things. Lets do that by introducing the keyword called "function". Javascript, for example, has such a keyword.

id = function(x) {
      return x;
}

Ok. Now lets make one more simplification. Lets say that the language is a little like Ruby or so where that last statement in a functions body is its return value. Did you get that? That means that we no longer need the keyword return. We can simply make the last statement x and by that we know that the return value from the function will be x.

id = function(x) {
      x;
}

Great, lets rewrite this a bit:

id = function(x) { x; }

Now for one more simplification (really C like languages are so complex!) - lets assume that we can write only one statement inside each function. Just one. If that's the case it can be much like a if with just one statement - we don't need the curly braces anymore. We also don't really need the semicolon.

id = function(x) x

Great! Congratulations ladies an gentlemen, you are looking at a lambda. Simply rename the keyword function and call it lambda and we are all set.

id = lambda(x) x

If we drop the name assignment and look at it we have:

lambda(x) x

This is a function that has no name. It take one argument and return it. Various functional languages use slightly different syntax for writing out their lambdas. The lambda calculus, the underlying calculus of these systems, usually uses a \ instead of the verbose name lambda. It also uses a dot to separate the arguments from the body of the function. A little like this:

\x.x

The functional language Haskell uses an arrow to separate the body from the arguments.

\x->x

The language(s) ML, OCaml, SML, (maybe F#) etc. use the name fun to stand for lambda.

fun x -> x

The language Scheme uses the name lambda and lots of parenthesis.

(lambda (x) x)

Ruby lets you write something very similar to a lambda like this:

lambda {|x| x}

Most of these languages give you some mechanism by which you can give a name to your lambdas (otherwise most of the time you are a little hard pressed to refer to them).

Haskell

id = \x -> x

ML

let id = fun x -> x

Scheme

(define id (lambda (x) x))

There are some alternate syntaxes for writing named lambdas in most languages:

Haskell

id x = x

ML

let id x = x

Scheme

(define (id x) x)

So what is a lambda? It is usually a name used to define a function. The function is a value that can be assigned to a variable name. Just like any other value in your language.

A lambda is an abstraction form. Normally in a program you can read the value of a variable to which you have not assigned a value. In other words is you write (x + 1), it does not have any meaning if x has not been assigned a value already. One way to look at what lambda says is that it abstracts the value of the x. So \x.(x+1) means - give me a value for x and then I will give you the value for x+1. The value of x is abstracted in the body of the lambda. This description comes very close to our informal notion of a function in a C like language.

The lambda calculus usually allows only for lambdas that take one argument. Hence to write functions that take multiple arguments we nest lambdas. We write \x.(\y.(x+y)) for a function that adds two numbers. Most functional languages support multi-argument lambdas. In Haskell this would be \x y -> (x+y).

So what's the big deal? Nothing much and quiet a lot. Nothing much because the notion of functional abstraction is something we learn from high-school math which we port over to programming languages. This is an old and familiar notion.

That said, in the functional programming community, it has long been realized (it is a large community with varying beliefs, secret cults, traditions and practices) that lambdas are the only abstraction form required for a lot of things.  One can do away with loops and conditionals (if, switch) and assignments and numbers and object oriented programming and pretty much everything you can think of (and some things you cant) - they can all be encoded using lambdas. Hence lambdas form a sort of foundational building block for a large number of programming paradigms. At the heart of all of this is the notion of a function - hence the name functional programming.

"Can you recommend any C++ books?"
"I don't recommend C++."

Afterwards I reluctantly come up with some names. I beginning to notice that I eventually end up mentioning the Scott Meyers "Effective C++" books. The last time I did this I started to wonder why I say this?

When I first read "Effective C++" I was horrified. If I derived any pleasure out of it, it was comparable to the morbid curiosity of going to witness an execution (I probably would not do that though, if I ever got such a chance. I don't have the stomach for it). Back to C++ - Firstly there was no way I was going remember all of that. Secondly I felt deeply uncomfortable. In time I realized that the whole book was written in the style of demonstrating "effective" usages of C++, while what it truly was is a careful documentation of the flaws of the language. Every chapter in that book talks of a language flaw in excruciating detail and how to live with it. That book should have been called "Defective C++".

Then there was "More Effective C++" which essentially did more of the same.  Here is what the language does, here is what you think it would do, here is what you'd like it to do and you put these together and it blows up in your face. In time, my intellectual immune system kicked in and started erasing most of my memories about all this.

So why do I recommend the "Defective" and "More Defective" books? My first recommendation would be to get out of the situation, don't deal with the language if that's possible. If not, and you intend to get it to serve you (instead of the converse) you need to quickly understand that most of the abstractions it provides are leaky. There are hardly any non-leaky abstractions that C++-land provides. (Some people associate this behavior with some notion of "freedom" - I trust evolution will take of those folk.)

So if your abstractions are leaky, in that they are going to have strange interactions with each other under-the-hood, then you should quickly start developing an understanding of what happens under the abstractions you are given. Your effectiveness as a developer becomes proportional to your understanding of what happens under the surface. Hence the "defective" C++ books are a useful read.

Today Aziz mailed me a build of his Ikarus compiler for Windows. Though I don't have much to do with software as such these days, I was excited. Ikarus is Aziz's Scheme Compiler. I use Petite Chez Scheme on my machine. Petite  is Kent Dybvig's Scheme interpreter, part of the Chez Scheme compiler system. I don't have Chez Scheme itself because it sells, I am told, for several thousands of dollars and hence I cant afford it. I expect Ikarus to be comparable to full Chez in many ways and surpass most other Scheme systems out there.

What Aziz sent me was a zip file that extracted to a 128k exe and 4mb "boot" file. He says the boot file says the same between windows, linux and mac. The bootstrap executable changes. This is amusing because the "boot" file is actually the compiler binary. It contains the compiled x86 code.  He able to get away with this because he only relies on the OS to load his little bootstrap exe. After that point he simply allocates memory pages from the OS and relies on the OS for almost nothing that he can do himself. So the exe loads the boot file into memory which then acts as its own loader, sets up its own stack, lays out its own code and data areas, does its own GC and such.

Of course, all of this is written in Scheme itself. There is probably a small C file somewhere that acts as the main() and the initial call into some ASM code that transfers control to Scheme. Fun fun.

I have talked to Aziz about many parts of this system and almost always the design has seemed to be of very high quality. His management of code objects, the runtime stack, continuations and on and on. The system has a large part of R6RS implemented and is already a superset of R5RS as far as I understand. Depending on how the development process stabilizes (after all, this is all one persons implementation), I might move over Ikarus altogether and maybe use it exclusively. 

Today over dinner Will Byrd mentioned the Collatz function to Michael Adams and me. The Collatz function is a simple little function that on receiving any natural number seems to always terminate with the result 1. However the strange thing is that no one has been able to prove this property of the function. As a matter of fact one rather famous mathematician is quoted to have said that mathematics isn’t ready to prove the Collatz conjecture and such problems.

So what is Collatz function?

collatz :: Integer -> Integer

collatz 1 = 1

collatz n | n `mod` 2 == 0 = collatz (n `div` 2)

collatz n                  = collatz (3 * n + 1)

Let me translate that into a C* style syntax:

int collatz(int n)

{

      if(n == 1)

            return n;

      else if (n % 2 == 0)

            return collatz(n/2);

      else

            return collatz(n*3+1);

}

Here is a wikipedia page about it:

http://en.wikipedia.org/wiki/Collatz_conjecture

If you look at it hard enough certain patterns emerge and we took some shots at what a proof might entail. In summary its sufficient to say that we didn’t get very far. The interesting consequence though is that enough information about the nature of the function emerged that we were able to create another one:

Hence is our new function that we call collatz’ (read as collatz-prime)

collatz' :: Integer -> Integer

collatz' 1 = 1

collatz' n | n `mod` 3 == 0 = collatz' (n `div` 3)

collatz' n | n `mod` 3 == 1 = collatz' (4 * n - 1)

collatz' n                  = collatz' (4 * n + 1)

Cute?

Later in the evening I found this one which I call collatz’’ (read collatz-double-prime)

collatz'' :: Integer -> Integer

collatz'' 1 = 1

collatz'' n | n `mod` 5 == 0 = collatz'' (n `div` 5)

collatz'' n | n `mod` 5 == 1 = collatz'' (6 * n + 4)

collatz'' n | n `mod` 5 == 2 = collatz'' (6 * n + 3)

collatz'' n | n `mod` 5 == 3 = collatz'' (6 * n + 2)

collatz'' n                  = collatz'' (6 * n + 1)

Like the original collatz function, both collatz’ and collatz’’ seem to terminate on all inputs with the result 1. Again there is no proof that it will do so. I have (at the time of this writing) verified termination of both of these till for all numbers 1 to100,000.

Here is a little verifier:

verify :: (Integer -> Integer) -> Int -> Bool

verify f n = foldl isOne True (map f (take n [1..]))

    where

    isOne :: Bool -> Integer -> Bool

    isOne b x = (x == 1) && b

verify collatz’ 100000 returns True.

Here is collatz in Scheme:

(define C

   (lambda (n)

     (cond

       ((zero? (sub1 n)) 1)

       ((even? n) (C (quotient n 2)))

       (else (C (+ 1 (* 3 n)))))))

And Collatz’

(define C

   (lambda (n)

     (cond

       ((= n 1) 1)

       ((= 0 (modulo n 3)) (C (quotient n 3)))

       ((= 1 (modulo n 3)) (C (- (* n 4) 1)))

       (else (C (+ (* n 4) 1))))))

Here is a good time to make a potential conjecture: Is it true that there are infinitely many such functions?

Updated

For a long time I thought that Roman numerals were the worst counting system out there, until I got down to thinking about Microsoft Excel’s column naming convention. The last time I thought about Excel I wasn’t satisfied with the solution I had – the last time was at Applibase with Sid.

So what do I mean? You know the way columns are numbered in excel they go A, B, C.. till Z and then become AA, AB, AC … AZ, BA, BB, BC … BZ, CA, CB… etc. You get the idea I guess. So in some sense its fair to imagine that you can think of these as representing numbers.

So can you write a mapping from natural numbers to excel-numbers and vice versa?

Lets look at look at the problem in a reduced sense and see what we get – lets consider only A, B and C. Therefore we could count as follows – A, B, C, AA, AB, AC, BA, BB, BC, CA, CB, CC, AAA, AAB, AAC etc.

Lets write these down with their natural numbers next to them –

1 : A

2 : B

3 : C

4 : AA

5 : AB

6 : AC

7 : BA

8 : BB

9 : BC

10 : CA

11 : CB

12 : CC

13 : AAA

14 : AAB

Can you write a function that takes a number and returns the corresponding excel number? Its not as easy as you think. The reverse, ie, taking an excel number and producing a natural number out of it is easier, conceptually.

If you think about it enough you will realize that unlike many number systems out there this one is different because it does not have a zero character – hence you can’t express things like A00.

I don’t think I have a good enough solution yet. My current solution still checks if a value is 0 and if so does something otherwise does something else. I would like to write a solution in a clearly recursive fashion such that the only condition-check I do is to terminate the recursion. Think about how you convert a number from natural numbers to a base 2 representation for example – you can write this recursively and you only need a check to terminate your recursion. Here I need checks for other things. I guess in some sense what I am complaining about is that my number to excel-number conversion is not “mathematical” enough.

Anyway, here is solution as a piece of Haskell code – it’s a spoiler so don’t look at it until you have tried to solve it yourself. (Set base to 26 to get full A to Z numbering).

base = 3

ch :: Integer -> Char

ch n = intToDigit ((digitToInt 'a') + (fromInteger n) - 1)

num :: Char -> Integer

num c = toInteger $ (digitToInt c) - (digitToInt 'a') + 1

mdiv m n | m `mod`n == 0 = m `div` n - 1

mdiv m n = m `div` n

mmod m n | m `mod` n == 0 = n

mmod m n = m `mod` n

excel2int :: String -> Integer

excel2int s = excel2int' s 0

    where

    excel2int' (c:[]) r = r * base + (num c)

    excel2int' (c:cs) r = excel2int' cs  (r * base + (num c))

int2excel :: Integer -> String

int2excel n | n <= base = [(ch n)]

int2excel n = (int2excel (mdiv n base)) ++ [ch (mmod n base)]

Update

Here is a very clean solution, courtesy of Abhijit Mahabal who pointed it out in a couple of minutes. He even stated a proof and went on to show how you can do this with logarithms…

i2e n | n < 3 = [ch (n+1)]

i2e n = i2e (n `div` 3 - 1) ++ [ch ((n `mod` 3) + 1)]

The following solution (that I disagree with in spirit) is by Kyle Ross. It looks rather cute for some values of cute –

i2e = (gen !!) . pred

xs <+> ys = [x ++ y | x <- xs, y <- ys]

gen = base ++ (gen <+> base)

         where base = ["a", "b", "c"]

Write the following into a text file:

A -> B;

B -> C;

C -> A;

A -> D;

D -> C;

C -> B;

And then run the following ruby script with the text file as a command line parameter:

require "win32ole"

def load(fn)

      s = File.new(fn).readlines().join ""

end

gr = WIN32OLE.new "WinGraphviz.DOT"

s = "digraph G {#{load(ARGV[0])}}"

png = gr.ToPNG(s)

png.Save("#{ARGV[0]}.png")

And then you get the following PNG file:

Interesting?

I recently needed to draw a graph (as in connected graph – in graph theory…) and looked around a bit. I came across the Graphviz library developed by the old AT&T. There is a port of the libaray available for windows and it can be downloaded from:

http://www.graphviz.org/

Graphviz or rather, WinGraphviz is available as a COM component which is registered by the installer. So instead of getting my hands dirty with C++,I decided to take the COM bindings in ruby for a walk.

This is where the ruby code comes – it creates an object of WinGraphviz.DOT component and uses it to create a graph. Notice how I can interact with a COM object as though it were a regular Ruby object – fun fun.

As for the language in the text file – Graphviz graphs can be specified using a language (you can find a spec on their website). The A-> B etc at the beginning of the blog post was simply a subset of this language.

Of course if your data is in some other format, you will have to translate it into the graph language – but then again if its in an excel file or something you can just use Ruby to talk to excel COM component and read the data out and then talk to the Graphviz component.

One of the solutions that did not make it into my yield paper (though I sort of liked it) was one that used “braiding”.

The problem here is to do a breadth first traversal of a binary tree. I was looking for a solution using my pet control operator yield. The braiding solution occurred to some months back as a consequence. The solution that finally made it into the paper was one based on a more traditional queue based breadth first traversal (BFT from now on) which did have better perf than the braiding solution. I am however documenting the braiding solution here because I think its elegant at some level.

So how would one do a BFT of a binary tree? Look at this entry for a slightly more detailed problem description. Simple, we start out by defining braiding.

Say you have two yield based iterators. These are just computations that yield values during their process of evaluation. These iterators yield values of type Maybe. For those unfamiliar with the Haskell type “Maybe”, here is a definition –

data Maybe a = Just a | Nothing

It simply says that a value of type maybe is either some actual value or the special value nothing. If you desperately need an analog, think of it as a pointer or a reference – it either points to some object or its null.

So a stream of maybe-values looks like this

x1 x2 # x3 x4 x5 # # x6 # ..

where the ‘x’ denote actual values and the # denotes occasional ‘Nothing’. If one had two such streams of values, then one can braid them as follows. Consider the stream of xs’ and the stream of ys.

x1 x2 # x3 x4 x5 # # x6 # ..

y1 # y2 y3 # y4 y5 # y6 y7 # ..

On braiding gives a single stream with that switches between the original streams every time it sees a Nothing. This results is a single stream like this –

x1 x2 y1 # x3 x4 x5 y2 y3 # y4 y5 # x6 y6 y7 # ..

This is how braiding works.

So how does one do a BFT? Simple, one recursively traverses the tree as follows –

• If you are at a leaf, yield the leaf value and then yield a Nothing.
• If you are at a branch, yield the branch value, a Nothing and then braid the iterators of the left and right branches.

Simple – that’s a breadth first traversal. If you look at the algorithm closely you will realize that final stream produced will be in the breadth first order but will also contain occasional Nothing values – the Nothing values will be precisely in the those places when values of one level deeper in the tree are being produced. (Of course, you don’t want to expose the Nothings you can add a filter and remove them).

The other important observation, which is also a requirement of the problem, is that the values used to resume the iterator will be available to the branches or leafs that yielded the corresponding value – hence tree reconstruction is trivial.

-- This a breadth first tree walk that reconstructs the tree from the

-- the return values of the yield. It is expands the tree one level at

-- a time and internally uses Nothing to communicate level changes.

bfTreeWalk :: Tree a -> Yield i a (Tree i)

bfTreeWalk tr = suppressMaybe $ bft tr

    where

    bft (L v) = do (Just v') <- yield (Just v);

                   yield Nothing;

                   return (L v')

    bft (B v t1 t2) = do (Just v') <- yield (Just v);

                         yield Nothing;

                         (t1',t2') <- braidMaybe (bft t1)(bft t2);

                         return (B v' t1' t2')

Here is the tree walk in Haskell. Even if you are not able to run or fully grok the Haskell code above, you should be able to use it as a guide to reconstruct the solution in your pet language.

The supporting braid and suppress functions are below –

-- Convert maybe values into real values by ignoring the Nothing.

-- 1 2 10 # 3 30 # 5 6 70 50 # 8 ...

-- Becomes

-- 1 2 10 3 30 5 6 70 50 8 ...

suppressMaybe :: Yield (Maybe i) (Maybe o) r -> Yield i o r

suppressMaybe yb = runMapY yb sM

    where

    sM Nothing = return Nothing

    sM (Just v) = do r <- yield v;

                     return (Just r)

-- Alternates two iterators, every time one yields a Nothing

-- 1 2 # 3 # 5 6 # 8 ....

-- 10 # 30 # 70 50 # 80 ....

-- and makes (where # is a Nothing)

-- 1 2 10 # 3 30 # 5 6 70 50 # 8 .. 80 ... ....

braidMaybe :: Yield (Maybe i) (Maybe o) r  -> Yield (Maybe i) (Maybe o) r -> Yield (Maybe i) (Maybe o) (r, r)

braidMaybe yb1 yb2 = bM (runYield yb1) (runYield yb2) True

    where

    bM (Iterator (Just v) k) it ord = do i <- yield (Just v); bM (k i) it ord

    bM it1 it2 False = do yield Nothing; bM it2 (resume it1) True

    bM (Iterator Nothing k) it True = bM it (k Nothing) False

    bM (Done v1) (Done v2) True = return (v1, v2)

    bM (Done v) it True = bM it (Done v) False

    resume  (Iterator Nothing k) = (k Nothing)

    resume it = it

The code above uses a monadic yield implementation and can as easily be expressed by any language which supports a good yield operator. (As of now I have a yield implementation for Haskell and Scheme and I believe Sid has ones for Python and Ruby (?))

At this point I should note that I was referred to the naïve implementation of BFT using nested lists by Simon Peyton Jones. The cods is below

breadthFirstTW :: Tree Int -> [Int]

breadthFirstTW t = concat (bft t)

  where

     bft :: Tree a -> [[a]]

     bft (L x) = [[x]]

     bft (B t1 t2) = b_zip (bft t1) (bft t2)

     b_zip :: [[a]] -> [[a]] -> [[a]]

     b_zip [] ys = ys

     b_zip xs [] = xs

     b_zip (x:xs) (y:ys) = (x++y) : (b_zip xs ys)

The essential idea behind the braiding traversal is not very different from that of the nested solution with the operational encoding of nested lists using Maybe. However looking at the nested list solution, at this point, it is not apparent to me how it can be extended to reconstruct the tree.

The implementation of the monadic yield that this relies on is documented in my paper which I hope to put up on my academic website soon enough.

Work at MSRC has been moving slowly, though I have been busy.

Parallel GC for Haskell

Not much to say on the Haskell parallel GC front except that I am yet to actually start writing any code. I have been trying to understand the existing code base and it has been a little over whelming. This is certainly not one of the best code bases that I have seen. Actually quiet far from it. There are functions of several hundred lines in length. The main GC function itself is 800+ lines long. I have been told that several people have got their PhDs of that GC.c file. I was expecting a pure functional language to contain a couple of core object types and everything else to be built around them. Far from it, there are 70+ types of objects in the system – they have special cased almost everything they can think of for efficiency sakes. Being a pure lazy language these things matter I guess.

That aside the source is littered with lots of interesting ideas. The problem with something so interconnected is that its hard to build incrementally on this. So I am little stuck. The GC has a copy collector and a mark compact collector in the same code base – they share a large amount of code. For a long time this confused me. The system switches from a copy collector to a mark compact collector depending upon memory usage of every step of every GC. The number of generations is runtime configurable. The number of steps per generation is runtime configurable. It’s a crazy, interesting system.

I have been making some notes over here, which I hope to continue updating over the period of my internship –

http://cvs.haskell.org/trac/ghc/wiki/GarbageCollectorNotes

Papers - Quantum

That aside, I helped complete – or rather didn’t help complete – a paper on Quantum Computing since I landed in Cambridge. I actually didn’t do much for that paper. I had some interesting ideas, but they remained undeveloped enough to not go into the final paper (though we initially thought it would). So well, in some sense my first paper is not really my first paper. :)

Papers - Yield

I finished my second paper since landing at Cambridge this past weekend. The paper is about yield, (yes, finally!). It is coauthored with Simon Peyton Jones and Amr Sabry, though most of the actual writing was done by me. So in many senses this paper will not be of comparable caliber to most Amr Sabry or Simon Peyton Jones papers. Writing this paper was quiet an experience – as it is, it was my first real paper. Usually, I am told, people don’t write their first papers completely themselves, they write a section or so. Secondly I had the names of two very respected computer scientists on this and I was afraid of writing accidental stupidity. They however did give me lots of comments over email. And at the end of it I think I have come out braver, a tab bit less afraid of writing papers.

The paper has been submitted to the Haskell Workshop 2006. Haskell is probably the most difficult language to suggest a new control flow operator. Being the pinnacle of pure functional programming, with monads and lazy evaluation it is a very very hard language to make a value proposition to in terms of adding control flow operators. All the same, I think we may have one or two interesting arguments in favor of yield.

Breadth First Renumbering

As an example of control flow based on lazy evaluation consider this problem: You are given a binary and asked to renumber the nodes in breadth first order, thus creating a new tree of the same structure but with changed node values.

 to

Think about it. See if you can do this by only one traversal of the tree and use constant space etc. Basically the best solution you can think up.

In Haskell, lazy evaluation is used as a control flow operation. But one that is an implicit control flow operation – in the sense that the programmer doesn’t have to specify the order of evaluation the system will figure it out, driven by need.

Here is the lazy Haskell solution -

data T a = B a (T a) (T a) | L a

       deriving Show

bfn :: ([Int], T a) -> ([Int], T Int)

bfn (k : ks, L a) = (k + 1 : ks, L k)

bfn (k : ks, B x a b) = (k+1 : ks'', B k a' b')

    where (ks', a') = bfn (ks, a)

          (ks'', b') = bfn (ks', b)

bfnum :: T a -> T Int

bfnum t = t'

    where (ks, t') = bfn (1 : ks, t)

It is just mind boggling that something like this can work – and work so perfectly. If you know how to read Haskell and you haven’t seen this solution before, get ready for a mild surprise. :) The implementation is adapted from the appendix of Chris Okasaki’s  paper –

http://portal.acm.org/citation.cfm?id=351253&dl=ACM&coll=ACM

Even if you don’t understand Haskell, try to solve this in your pet language and see what you come up with.

Haskell

Since I am in a mood for writing a bit – here is a little bit about Haskell. A tiny tiny intro. Haskell is a pure functional language. If you don’t know what that means, there is good chance that you haven’t seen one before. Also Haskell is one of the few languages that are lazy evaluated. Values are computed only on a need basis – hence one gets to write all sorts of crazy circular dependencies between function parameters and their results – if one is careful. Also it is strongly typed – Haskell is a laboratory for stuffy of type systems, if nothing else.

Lets do some examples. Immediately following the example, I write what it means.

n = 5

n is a function that takes no parameters and returns the value 5.

f n = n+1

f is a function that takes one parameter, namely n and return n+1. Hence if one writes (f 1) it is the equivalent of calling f with the parameter 1 and will return 2.

If you write code like the above, it will work. But usually people write the types of everything they write. If you miss out the types, Haskell has a type inferencer which will automatically figure out the types (and might occasionally complain if there are ambiguities).

So here is the definition of the function f with its type signature.

f :: Int -> Int

f n = n+1

So the type of f is written by putting two colons after f and is “from Int to Int”. In other words the function f takes an Int and returns an Int.

Here is the type of the function even, a function that checks if a number is even.

even :: Int -> Bool

It takes an Int and returns a Bool.

So what is the type of the function n?

n :: Int

n = 5

Simple? The type of n is simply Int.

Here is a function g that takes two parameters, namely x and y and returns their sum.

g :: Int -> Int -> Int

g x y = x+y

The type says that g takes an Int and yet another Int and returns an Int. The value of (g 5 10) is 15.

The interesting this is that in haskell, unlike in many other languages, the expression (g 5)  by itself has a meaning.

g5 :: Int -> Int

g5 = g 5

(g 5)  is a function that takes an Int  and returns an Int. Here I assigned the name g5 to be (g 5) hence is I say (g5 20) the result will be 25. The general idea behind applying only some of the parameters of a function thereby result in a new function that awaits the remaining argument is called “currying” – named after Haskell B Curry.

Does this interest you? If so you should consider reading up about Haskell a bit. Maybe I will drop a few simpler examples of lazy evaluation based niceties sometime.

Why Haskell?

So how long does it take for a completely fledgling Haskell programmer to implement a weird language? 2 nights.

Its pretty amazing if you think about it – and it fun and not stressful as well. If I did as much in C or Cpp it would have been significantly more stressful and would have take a over a weekend for sure. And even after that it wouldn’t be as flexible as this is.

In some sense, in my current limited opinion, Haskell is to Scheme what Ruby is to C++. To add to it, it is purely functional than scheme, is lazy, comes with A REAL library, allows for pattern matching and discriminated unions etc… the goodness goes on – as matter of fact, it can even pretend to be imperative for a bit. Also, GHC generates actual Win32 exes that I can run. If you are a languages person you might think it’s a moot point, but for someone who likes to build tools and wants to sometimes share them with his (less inclined) friends, this is essential.

So I think Haskell is going to takes its place in my bag of tools. The only thing I really miss from Scheme land are macros. I wish Haskell had macros – better, I wish Haskell had multistage evaluation.

Being a almost ‘pure’ imperative programmer when I joined college, Prof Dan Friedman’s Programming languages class hurt my head really badly. And I was coming to terms with functional programming.

Last semester I also took a class with Prof Amr Sabry – Quantum computing – and this was my first real introduction to Haskell. I am working with him this semester and of late I have been trying to understand Monads. Its one thing to have working knowledge of a concept, and its quiet another to formally study it. Monads hurt like few other things hurt before – and the fact is that it makes you look at imperative programming in this totally other way.

So that’s the context for why this is in Haskell. The blog entry is really about this little language I wrote in .. in all fairness a little more than a late night. And I haven’t used the parser generator or other tools before this.

Yield Language 1.0

So whats the language like? Well, you’re not going to want to use it at all. But all the same it is the lambda calculus with the following additions (some of which take away its purity) – yield (with all the right behavior in place), if-then-else, numbers (+, -, ==), strings (+, ==). In other words, it’s a simple higher order language with strings and numbers and fancy control flow operator called yield, which is the only “impure” part of the language.

To support yield I introduce a funny tagging operator I call ‘pi’ to tag a sub-expression that can yield. A pi-expression can be called like a normal application, or can be used as a coroutine using co, next and run.

The actual internal implementation is what is best described as “stackless”.

f = \x ->

  ((("x = " + x) + ", ") +

  if (x == 0)

    "zero"

  else

    "not zero");

(f 10)

This evaluates and returns “x = 10, not zero”

Basic syntax

e =     \x->e

| x

| e1 e2

| if e1 e2 else e3

| (e1 + e2)

| (e1 – e2)

| (e1 == e2)

| <num>

| <string>

| x = e1; e2

The above syntactic categories as basically all pure. The last rule is a let. There is no fixed point operator and you will need to add one of your own to do recursion. Evaluation is strict, applicative order. The following are the extensions for yield support.

      | pi e

      | yield e

      | co e

      | next e1 e2

      | run e1 as x1 x2 -> e2 or x3 -> e3

Some more examples, assume that we have an applicative order Y combinator called “fix”.

-- Applicative Y combinator

fix = \f -> ((\x -> (f \y -> ((x x) y)))

          (\x -> (f \y -> ((x x) y))));

Here  is a relatively simple function that takes a number and yields as many times. I have used the fixed point operator so that I can loop inside the pi block.

-- An iterator that yields 'x' times