I have been getting my brain fried the past few days trying to relate call-by-need and delimited continuations. Staring vacantly into space I noticed my little flying certificate from Cornwall. Happy memories, hence the post –

Granite cliffs around Land’s End, Cornwall taken from a Cessna 172 that I was flying.

(Yes it’s safe to let go of the controls of a small plane like that for a short while)

On foot this time.

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.

Functional Programmer’s Lament:

Forgive me Lord, for I have side-effected.

Logic Programmer’s Lament:

Forgive me Lord, for I have temporized.

System’s Programmer’s Lament:

Forgive me Lord, for it crashed.

Hannibal Lecter: First principles, Clarice. Read Marcus Aurelius. Of each particular thing ask: what is it in itself? What is its nature? What does he do, this man you seek?

One of my professor's, Dan Friedman, once said in class, "Some people are of the opinion that computer scientists should choose to work on problems that are *useful*, and that working on your pet problem that has no apparent use is not right. I myself am not of that opinion." After about a year, I must say I agree. In this spirit, some people are of the opinion that people who write blogs should choose to write what others would like to read. I myself am not of that opinion. (My apologies to Dan for not quoting him verbatim, but its been a year)

Recently I have been watching Sean Connery’s old James Bond movies. (When I went to Scotland it was interesting to notice that they wasted no time in pointing out that Sean Connery was once a milkman in Edinburgh.) That minor detail aside, I was wondering what I would like to do when I get out of college.

And then it struck me – I would love to be a high profile programming language designer. People all over the world who need someone to design their languages for them, will know the right man for the job. “Hello, may I speak with Mr. 00\lambda please?”. “Mr. 00\lambda we have an emergency situation here that needs your immediate attention. We need a domain specific language with the following bisimulation properties…” “No, no, Mr. 00\lambda, the weak barbed congruence for the underlying process calculus must be provable, otherwise all hope is lost…” “Our competitors have the advantage of equational reasoning for their monadic computations.”

That would be a good life indeed. “Sorry I am busy today evening, you see I am in Tokyo right now”. “No not tomorrow, tomorrow I am at INRIA in Paris…” “Its the work of a systems programmer! I should have known it…”

And when I am leaving for a mission, Q would hand me that parser generator that is disguised so conveniently as a watch, or that POPLMark verifier that fits in the sole of my shoe. “And what’s that Q?”, “That, my dear lambda, is something special – top secret I must add – that our secret new decidability checker… of course, you know the risks of using it”.

Anyone out there with a great language design job on your hands, come talk to me.

This semester, due to an issue with my funding situation at college, I found work with a systems group. So officially I am off working on PL theory for a while. The thing is, after about a year of doing PL, I am convinced that as programmers or language designers one should focus on building good abstractions that compose well. All other concerns are secondary to this goal.

The project I am involved with one that is concerned with creating a mechanism for programming the increasing for viable multicore machines that are available in the market. The objective being with coming up with a programming paradigm that makes it “easy” to program machines that have a large number of computing units (cores, processors etc).

The best description of the motivation for this is described in Herb Sutter's famous article -

The Free Lunch is Over: A Fundamental Turn Towards Concurrency in Software

http://www.gotw.ca/publications/concurrency-ddj.htm

Since many of my blog entries have ceased being blog entries and have become more beacons of the fact that I am trudging through life, here is another life update.

I am back in Bloomington, Indiana after a great summer. After many years have I had a summer that left me with so many memories. I spent the summer in Cambridge, UK and like I was telling one of my friends here at IU (Indiana University) that Cambridge is like a distillation of the essence of several Bloomingtons put together, and then matured over several hundred years – a little like comparing a fine Scottish whisky to beer – maybe a 16year old Glenmorangie in burgundy wood to a Guinness.

I made it a point to travel as much as I could this summer – as much as time and finances would allow. And it was great. I look at some slight embarrassment at the rant about Cornwall below. But yes I had a great time at Cornwall. Cornwall aside, took several trips to London, went to Norfolk – Hunstanton, Cromer, Great Yarmouth. London’s a pretty amazing city and I haven’t been to most of the major touristy spots. Spent some time gallivanting around Cambridge – went to Peterborough and Ely – saw the famous cathedrals. Went to Granchester – the little village near Cambridge.

However most of the really great travel came towards the end of summer. I had a chance to finally go to Scotland. The trip to Scotland was primarily motivated by a long standing wish to go see Skye – the island of Skye – like in the famous Robert Stevenson poem “over the sea to Skye”. Scotland was amazing in many ways – firstly it was beautiful. But that aspect of it didn’t impress me much initially – in my mind I kept comparing it to the highranges in Kerala and not seeing much more there. But after a while you realize how much grander Scotland is – the deep lochs and the high lands and the people. I got a chance to spend two night at the bank of the Lochness in a little town called Fort Augustus. At Fort Augustus I picked up a liking for good single malt whisky. I never had a liking for hard liquor before – but this is great. Favourites? Hmm… I like a Glenmorangie (esp in Burgundy wood), The Macallan, Dalwhinnie; I like this really interesting whisky liquor called the Glayva…. Scotland was interesting in other ways too – here was a land that was under conflict with the English for many hundred years and they too, much like India tries to hold on fiercely to their traditions. Scotland of today is not much like that, but an Scotsman you meet will be only happy to make clear to you how they are not Englishmen. It was alsoa funny parallel that very often tartan patterns on kilts were like the checked patterns on mundu back in Kerala.

After Scotland the next major travel was to Paris and then to Rome. Paris was good, Rome was great. I think aside from a love for whisky another take away from summer is the need to be Italian and to speak Italian – I am so amazed by that language – I have taken an instinctive liking to it. It also partly has to do with a good Italian friend I made this summer (who also happens to be a logician in his free time). More on all that later. Honestly these days there is too much to write about, and so many things to say about every little thing – I need to sort out my time for blogging a little more carefully.

Hairy Coo!