Bimal,
That was something of an explanation...
As I said, I am a LISP novice, but am certainly fascinated by Guile. Don't
think I'm downgrading Python, but lisp (and its dialects) has got a certain
"thing" within themselves that mastering them gives you a feeling of Nirvana.
I thank you for enlightenening me (and for the Wiki link, heck, why didn't I
think of that in the first place?)
I still need to work on the Python snippet to assimilate the full potential
of tail-recursion. ('cos I'm writing this in a cafe, can't work on the code
now, these guys are using M$ :-( )
Q: Can u (or anyone) rewrite this similar code in C/C++? it surely helps if
there is a language that all can understand. I tried but 'long long' dosen't
seem to be the right data type.
Happy Hacking,
Mahesh Aravind
bimal viswanath <bimal_v at rediffmail.com> wrote:
Ok..this mail was interesting!
I dont know Guile or Lisp or Scheme.
But I found the code quite readable..so was able to understand.
Tail recursion optimization is implemented in guile- which we can understand
from your example.
Ok for those who dont know what tail-recursion optimization is, have a look at
this simple explanation at wiki:http://en.wikipedia.org/wiki/Tail_recursion
Ya as you said..its more like a simple goto.
As the recursive call is made as the last statement. The function need not
store the return address in stacks on each recursive call. The optimization is
done by returning the value immediately to the caller..thereby saving lots of
stack space!
So why not do this in python also? :D
I know a little bit of python.So a few searches led me to this example.
#This is tail recursion implemented in python.
#This code was taken from this
link:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474088
#Have added a few extra comments.
#!/usr/bin/env python2.4
# This program shows off a python decorator(
# which implements tail call optimization. It
# does this by throwing an exception if it is
# it's own grandparent, and catching such
# exceptions to recall the stack.
import sys
class TailRecurseException:
def __init__(self, args, kwargs):
self.args = args
self.kwargs = kwargs
def tail_call_optimized(g):
"""
This function decorates a function with tail call
optimization. It does this by throwing an exception
if it is it's own grandparent, and catching such
exceptions to fake the tail call optimization.
This function fails if the decorated
function recurses in a non-tail context.
"""
#see http://docs.python.org/lib/inspect-types.html for stack frame object
reference
def func(*args, **kwargs):
f = sys._getframe()
if f.f_back and f.f_back.f_back \
and f.f_back.f_back.f_code == f.f_code:
raise TailRecurseException(args, kwargs)
else:
while 1:
try:
return g(*args, **kwargs)
except TailRecurseException, e:
args = e.args
kwargs = e.kwargs
func.__doc__ = g.__doc__
return func
def factorial(n, acc=1):
"calculate a factorial"
if n == 0:
return acc
return factorial(n-1, n*acc)
factorial=tail_call_optimized(factorial)
print factorial(10000)
# prints a big, big number,
# but doesn't hit the recursion limit.
def fib(i, current = 0, next = 1):
if i == 0:
return current
else:
return fib(i - 1, next, current + next)
fib=tail_call_optimized(fib)
print fib(10000)
# also prints a big number,
# but doesn't hit the recursion limit.
The code above is well commented.
So if i summarise.. what it tries to do is simple:
There is this function factiorial() which we want to optimize by
tail-recursion. So we transform this function to another one
tail_call_optimized(). Now this tail_call_optimized() function takes care of
checking for tail-recursive call..and returning result immediately to the
caller. For accessing stack frames they have used the "sys" module.
So bottomline is tail-recursion can be implemented in other scripting languages
also. Its an optimization technique which the guile pple directly implemented
in the guile language.
---------------------------------
Yahoo! Mail
Bring photos to life! New PhotoMail makes sharing a breeze.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://ilug-cochin.org/pipermail/mailinglist_ilug-cochin.org/attachments/20060308/88059f1c/attachment.htm
