Chathura Herath 's Blog

My Photo
Name:
Location: Bloomington, Indiana, United States

Friday, February 18, 2011

Non-tail call to tail call coversion - Scheme Fibonacci example with recursion tree

After thought from a discussion i had with Felix Terkhorn, made write this blog to show the awesome display of tail-call optimization of scheme using scheme trace. I implemented this optimization when i did my scheme compiler for Prof Dybvig's class.

Here on display is also the conversion of non-tail call to a tail call. Most common example for this is Factorial which can be seen here, but i took Fibonacci as an example because it requires little more thinking. Take a look at the following Fibonacci implementation. We know if lambda is placed in tail context the lambda body will also be in tail context. Also if cond/if is placed in tail context the then and else branches will also be in tail context. But the recursion to fib is placed as args to +. Although + is in the tail context the args to + are not. This is displayed when we calculate (fib 13) and we can see the stack growing and shrinking in the recursion tree.

Now take a look at the re-written tailfib function and its trace. you would notice the tail call optimization as the stack does not grow in the recursion tree. In other words its an iteration. Here the idea is to use an accumulator similar to that of the Factorial example, but in Fibonacci you need two such accumulators because it is a second order recurrence with reference to two previous states. Which updating the accumulators in the reverse order as if you started with the initial condition you would decrement the counter. This placement of accumulators allow us to position tailfib function in tail context of the cond special form, thus making it a tail recursion.



>(define fib (lambda (n)
(cond
( (= n 0) 0)
( (= n 1) 1)
( else (+ (fib (- n 1)) (fib (- n 2)))))))
>(fib 7)
13
> (trace fib)
(fib)
> (fib 7)
|(fib 7)
| (fib 5)
| |(fib 3)
| | (fib 1)
| | 1
| | (fib 2)
| | |(fib 0)
| | |0
| | |(fib 1)
| | |1
| | 1
| |2
| |(fib 4)
| | (fib 2)
| | |(fib 0)
| | |0
| | |(fib 1)
| | |1
| | 1
| | (fib 3)
| | |(fib 1)
| | |1
| | |(fib 2)
| | | (fib 0)
| | | 0
| | | (fib 1)
| | | 1
| | |1
| | 2
| |3
| 5
| (fib 6)
| |(fib 4)
| | (fib 2)
| | |(fib 0)
| | |0
| | |(fib 1)
| | |1
| | 1
| | (fib 3)
| | |(fib 1)
| | |1
| | |(fib 2)
| | | (fib 0)
| | | 0
| | | (fib 1)
| | | 1
| | |1
| | 2
| |3
| |(fib 5)
| | (fib 3)
| | |(fib 1)
| | |1
| | |(fib 2)
| | | (fib 0)
| | | 0
| | | (fib 1)
| | | 1
| | |1
| | 2
| | (fib 4)
| | |(fib 2)
| | | (fib 0)
| | | 0
| | | (fib 1)
| | | 1
| | |1
| | |(fib 3)
| | | (fib 1)
| | | 1
| | | (fib 2)
| | | |(fib 0)
| | | |0
| | | |(fib 1)
| | | |1
| | | 1
| | |2
| | 3
| |5
| 8
|13
13




>(define tailfib (lambda (n F-1 F-2)
(cond
( (= n 0) 0)
( (= n 1) F-1)
( else (tailfib (- n 1) (+ F-1 F-2) F-1)))))

>(define fib(lambda (n)
(tailfib n 1 0)))
>(trace tailfib)

>(fib 7)
|(tailfib 7 1 0)
|(tailfib 6 1 1)
|(tailfib 5 2 1)
|(tailfib 4 3 2)
|(tailfib 3 5 3)
|(tailfib 2 8 5)
|(tailfib 1 13 8)
|13
13

Labels: , , , , , , , ,

Saturday, January 29, 2011

Trace lambda in Scheme to display recursion tree

When doing recursions in Scheme programming sometime its useful to see the growth of the recursion tree for debugging or even to get an intuition about approaches to improve the algorithm like dynamic programming. Following is a pure recursive insertion sort, obviously not the efficient implementation, yet it illustrate the use of trace procedure.

(define insert (lambda (val sorted)
(if (null? sorted)
(list val)
(if (< val (car sorted))
(cons val sorted)
(cons (car sorted) (insert val (cdr sorted)))))))

(define sort (lambda (vals)
(if (null? vals)
vals
(insert (car vals) (sort (cdr vals))))))

(trace insert)
(trace sort)





(sort '(7 6 5 9 3 4 2 8))

|(sort (7 6 5 9 3 4 2 8))
| (sort (6 5 9 3 4 2 8))
| |(sort (5 9 3 4 2 8))
| | (sort (9 3 4 2 8))
| | |(sort (3 4 2 8))
| | | (sort (4 2 8))
| | | |(sort (2 8))
| | | | (sort (8))
| | | | |(sort ())
| | | | |()
| | | | (insert 8 ())
| | | | (8)
| | | |(insert 2 (8))
| | | |(2 8)
| | | (insert 4 (2 8))
| | | |(insert 4 (8))
| | | |(4 8)
| | | (2 4 8)
| | |(insert 3 (2 4 8))
| | | (insert 3 (4 8))
| | | (3 4 8)
| | |(2 3 4 8)
| | (insert 9 (2 3 4 8))
| | |(insert 9 (3 4 8))
| | | (insert 9 (4 8))
| | | |(insert 9 (8))
| | | | (insert 9 ())
| | | | (9)
| | | |(8 9)
| | | (4 8 9)
| | |(3 4 8 9)
| | (2 3 4 8 9)
| |(insert 5 (2 3 4 8 9))
| | (insert 5 (3 4 8 9))
| | |(insert 5 (4 8 9))
| | | (insert 5 (8 9))
| | | (5 8 9)
| | |(4 5 8 9)
| | (3 4 5 8 9)
| |(2 3 4 5 8 9)
| (insert 6 (2 3 4 5 8 9))
| |(insert 6 (3 4 5 8 9))
| | (insert 6 (4 5 8 9))
| | |(insert 6 (5 8 9))
| | | (insert 6 (8 9))
| | | (6 8 9)
| | |(5 6 8 9)
| | (4 5 6 8 9)
| |(3 4 5 6 8 9)
| (2 3 4 5 6 8 9)
|(insert 7 (2 3 4 5 6 8 9))
| (insert 7 (3 4 5 6 8 9))
| |(insert 7 (4 5 6 8 9))
| | (insert 7 (5 6 8 9))
| | |(insert 7 (6 8 9))
| | | (insert 7 (8 9))
| | | (7 8 9)
| | |(6 7 8 9)
| | (5 6 7 8 9)
| |(4 5 6 7 8 9)
| (3 4 5 6 7 8 9)
|(2 3 4 5 6 7 8 9)
(2 3 4 5 6 7 8 9)

Labels: , , , ,

Thursday, December 02, 2010

Latex Equation Editor

Here is a great site that allows you to edit and render mathematical equation.

Monday, September 06, 2010

How to setup Eclipse project and development envionment for changing Hadoop framework

Here are the three easy steps that i followed when i want to hack the hadoop code to for my research and i have seen this question asked and answered few times and i personally think the approach i took is worth blogging.

First of all you need to decide on the version that you are selecting to hack on. I usually use the .20.2 tag and i download and install the binary version of that and follow the instructions posted that. Now the idea is you would check out the same tag from svn and and setup an eclipse project and you would build that project and replace the jar in binary installation with the newly build jar.

Step 1: Install: Download and install a stable version of Hadoop that you are chosen to develop on.

Step2 : Setup Hadoop Eclipse Project - To setup the Hadoop eclipse project you would have to have Eclipse with the svn plug-in and add a svn repository using https://svn.apache.org/repos/asf/hadoop/common/ URL. Once the repository is added go into the tags in the repository tree and find the tag version you installed in step 1 and check out that using the eclipse. Now you will have a eclipse project with lot of errors. First step in getting the project to compile is to run the ant jar target in the build script. This will find all the dependency jars and they will be stored in the lib and other folders. You can try to add the jars one by one but i would rather suggest using a explorer like Konqueror and searching for all the jar files in the project root folder and copying all of them into a folder named libn. You might have to manually download the ant.jar and add that to the libn as well. Then you can add all these jar files to the eclipse classpath. Once this is done you will be almost all set except for selecting the src folders that you want to be compiled. Most of the exciting stuff in hadoop happen in src/mapreduce, src/core, src/hdfs source trees. So for a starter i would only add these as the source directories. By now the Eclipse project should compile successfully without errors.

Step 3: Deployment - Once the eclipse project is setup and you done with your hacking and changed say the Hadoop core, you could run the jar target of the build.xml and build the project. This would generate a jar file inside the build directory named hadoop-0.xx.x-dev-core.jar. Now you should go to the installation directory of Hadoop in step1 and delete the core jar there and replace it with the new jar you just build. Once you have done that you can restart Hadoop and you will have your own version of Hadoop installation.

Happy Hadoop hacking !!!

Labels: , , , , ,

Tuesday, June 22, 2010

Nice overview of Hadoop Pig


Came across this nice presentation of Hadoop Pig!. It can be found here.

Tuesday, June 15, 2010

Great Hadoop installation guide

Following is the link to the most straight forward installation guide i ve seen so far

Link!!

Tuesday, May 04, 2010

Amazon Elastic Map Reduce: API call to find and terminate job flows without Amazon Console

Recently one of the interns in the lab asked me how can he kill the running job flows in Amazon Elastic Map Reduce so he will not run up a big bill. This is straight forward to do in Amazon Management Console, but in this case the student didn't have the username/password to the amazon account because he was using a community account (although he had access to the accesskeys). Another application would be to write a cron job that checks the left over Job Flows and their EC2 instances every night so being able to do this programmatically helps.

Terminating a Job flow is straight forward using the client API that Amazon has provided and a sample can be found here. Now the issue is how to find the running Job Flows using API calls. The DescribeJobFlow API may give the impression that one need to give the Job Flow id to begin with to query the Job Flow Status, but my testing shows that if we don't specify any Job Flow ids in the request as shown in the sample here, it would return the Job Flows with the most recent activities. If there are Job Flows that are running those would have most recent activities. So once you have these two its easy to write a piece of code that would glue these two together to kill all the existing Job Flows.

Thats it!!!

Labels: , , , , , ,