Saliya's Blogs

Recursion is Natural

“Yay! I can see my bu** !! … wait, it’s not my bu**, it’s myself !”

If you can come to the last realization that you are seeing yourself then you already understand recursion is natural. If not, the following few examples may help.

Example 1: Is Even?

Zero is even. Any integer N > 0 is even if N-1 is not even.

Example 2: Factorial

Factorial of zero is 1. Factorial of any integer N > 0 is N times factorial of N-1.

Example 2: Length of a List

An empty list has a length zero. Any other list has one head element and a sub list called the tail. So length is 1 more than the length of the tail.

Example 3: Map f() to List S

If S is empty then nothing to do just return an empty list. If not map f() to the tail and get a mapped list. Then add f(head) to the front of that list.

P.S. Many thanks to Dan Friedman (https://www.cs.indiana.edu/~dfried/) for his great class of B521 (cs.indiana.edu/classes/b521) at IU, 2009.

----------

About the image; it’s an InkScape sketching of the image I found at http://contortionistsunite.ning.com/profiles/blogs/day-1-3

Taming Wild Horses: Chapel Asynchronous Tasks

Chapel supports nesting data parallel and task parallel code arbitrary as desired. This allows you, for example, to spawn asynchronous tasks inside a forall loop. The code snippet below shows code for a case like this where a forall is run on an array of 3 elements. The work to be done for second element is time consuming, hence a new task is spawned to run the timeeater(). Seems straightforward isn’t it? What if timeeater() takes more time than the forall loop? You’d expect forall to wait till all the dynamically spawned tasks to complete, but unfortunately it’s not the case. So if you want everything to be done when you exit forall loop use the construct sync to synchronize.

Try running the code with and without sync and observe the value of result, which should be 500500 if forall exit only after all the tasks have completed.

var d : domain(1) = [1..3];
var a : [d] int = d;
var result : int;
sync forall i in a{
    writeln(i);
    if (i == 2) then {
       begin result = timeeater();
    }
}
writeln("end of forall");
writeln("result ", result);

proc timeeater(){
    var tmp : int = 0;
    for i in 1 .. 1000{
        tmp = tmp + i;
        if (i%25 == 0) then {
            writeln("eating time ", i);
        }
    }
    return tmp;
}

Chapel is Sweet

It has been a little while since I started playing around Chapel (http://chapel.cray.com/) language, but could not run anything fun and large until recently. As part of the B524 – Parallelism in Programming Languages and Systems class from Prof. Lumsdaine (http://osl.iu.edu/~lums/), we had to implement Single Source Shortest Path (SSSP) of Graph500 (http://www.cc.gatech.edu/~jriedy/tmp/graph500/) specification. Only then I could realize the easiness of many of the high-level abstractions provided in Chapel compared to other parallel languages or paradigms. Honestly, I did not expect it to work in the first run across a set of machines, but surprisingly it did!

Download a Set of URLs with GNU Wget

I had a list of URLs that I wanted to download and it was a pain to do it manually. So end up writing a simple shell script and downloading all of them using GNU Wget. Here’s the shell script (modified the one at http://www.linuxquestions.org/questions/programming-9/shell-script-that-read-each-line-separatly-364259/).

#!/bin/bash
# Set the field seperator to a newline
IFS="
"
# Loop through the file
for line in `cat file.txt`;do
 wget $line
done