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: , , , , , , , ,

70 Comments:

Blogger FREE-HITMOVIE said...

The United Kingdom expels all Iranian diplomats from the country following an attack on its embassy in Tehran.
discount banner standswebsite how to make

10:11 PM  
Blogger Ckutude said...

No idea how to embed this, so I'll just link: Me talking risk capital and young companies, while an animator makes animation magic happen.
house designs brisbanesofie schnoor

11:04 PM  
Blogger FREE-HITMOVIE said...

The common name was recorded from the early 19th century in the Falkland Islands. English sailors apparently named the species for its conspicuous yellow crest;[5] Maccaronism was a term for a particular style in 18th-century England marked by flamboyant or excessive ornamentation. A person who adopted this fashion was labelled a maccaroni or macaroni, as in the song "'Yankee Doodle".[6]
Mississauga Real EstateSporting Events

3:56 AM  
Blogger bạn park said...

Stern also oversaw the creation of the WNBA, a professional women's basketball league. Stern has been credited for developing and broadening the NBA's audience, by setting up training camps, playing exhibition games around the world, and recruiting more international playersfurnace partsCarnival in Rio

6:33 PM  
Blogger FREE-HITMOVIE said...

that upon the death of Chief Rabbi Sholom Rivkin of St. Louis, Missouri, in October 2011, the institution of Chief Rabbi of a city in the United States came to an end?
eCoupon CodesCondos for sale in Toronto

10:50 PM  
Blogger blogcar said...

One more thing to admit: I enjoyed Jack and Jill. I love that Al Pacino clearly doesn't give a shiitake about what anyone thinks and lets it rip.
carpet dallasTorrent Search Engine

11:50 PM  
Blogger FREE-HITMOVIE said...

Sixty-two known moons orbit the planet; fifty-three are officially named. This does not include the hundreds of "moonlets" within the rings. Titan, Saturn's largest and the Solar System's second largest moon (after Jupiter's Ganymede), is larger than the planet Mercury and is the only moon in the Solar System to retain a significant atmosphere.
replica bagsmetal casting

11:41 PM  
Blogger bạn park said...

Print on demand can be used to reduce risk when dealing with "surge" titles that are expected to have large sales but a short sales life (such as celebrity biographies or event tie-ins): these titles represent high profitability but also high risk owing to the danger of inadvertently printing many more copies than are necessary, and the associated costs of maintaining excess inventory or pulping.Langley computer serviceaddicting games

2:40 AM  
Blogger blogcar said...

This Sunday, we were celebrating Christmas in advance with my parents and brother.
set up a swiss trust companysinus doctor ny

8:35 AM  
Blogger bạn park said...

Under the Laws, the two basic states of play during a game are ball in play and ball out of play. From the beginning of each playing period with a kick-off until the end of the playing period, the ball is in play at all times, except when either the ball leaves the field of play, or play is stopped by the referee.vvscheap wedding cake topper

2:46 AM  
Blogger blogcar said...

This is a quality list ... community is not just about sharing, it's about interacting and communicating with other people (in my case and may who read this post that means other photographers).
extra virgin olive oildøre

11:53 AM  
Blogger FREE-HITMOVIE said...

This comment has been removed by the author.

10:25 PM  
Blogger FREE-HITMOVIE said...

The McDonnell XF-85 Goblin was an American prototype fighter aircraft conceived during World War II by McDonnell Aircraft. It was intended to be carried in and deployed from the bomb bay of the giant Convair B-36 bomber as a parasite fighter.
Removals SouthamptonLeather Wallets

10:26 PM  
Blogger blogcar said...

Instead, the MTV VMAs took home the honor of the most simultaneously-tweeted moment of the year with 8,868 tweets sent in a single minute. You may remember when Beyonce revealed she was pregnant on stage, sparking the avalanche of tweets.
Easy Openerschadeauto

8:59 AM  
Blogger FREE-HITMOVIE said...

that cliffs on the Lizard Peninsula in Cornwall are a breeding site for the rare Cornish Chough (pictured)?
china wholesaleSettle Credit Card Debts

9:41 AM  
Blogger bạn park said...

The Roman Missal contains the prayers, antiphons and rubrics of the Mass. Earlier editions also contained the Scripture readings, which were then fewer in number.transfer factor plusdecoratiefolie

4:43 AM  
Blogger bạn park said...

The first reading is followed by a Responsorial Psalm, a complete Psalm or a sizeable portion of one. A cantor, choir or lector leads, and the congregation sings or recites a refrain.Interactive DisplaysAudio Production

5:27 AM  
Blogger Administrator! said...

Luke Donald believes Rory McIlroy is more talented than Tiger Woods.

World number one Donald tees off with McIlroy in golf's Dubai World Championship first round on Thursday.

And he said: "In terms of talent I think Rory has more. I think Tiger's work ethic has always been tremendous and his mindset as well."

Donald will win the Race to Dubai - and top both the European and United States money lists - as long as he finishes ninth or better.

But his comments regarding McIlroy and Woods have caused a stir. Donald later clarified his comments on Twitter, saying: "A few people aren't understanding what I meant."
Marine SafetyJeans Shop

7:46 AM  
Blogger FREE-HITMOVIE said...

After 541 days of negotiations, a new Belgian government is sworn in, with Elio Di Rupo as prime minister.
credit cardshealthcare promotional products

2:09 AM  
Blogger blogcar said...

Yesterday night the first installation to be built by flying machines opened its doors to the public. An hour or so after the Opening, after most ...
boats for sale phuketon line clothing

8:42 AM  
Blogger ChjpHunter said...

The Cogan House Covered Bridge is a Burr arch truss covered bridge over Larrys Creek in Cogan House Township, Lycoming County, in the U.S. state of Pennsylvania. It was built in 1877 and is 94 feet 2 inches (28.7 m) long. The bridge was placed on the National Register of Historic Places in 1980, and had a major restoration in 1998. The Cogan House bridge is named for the township and village of Cogan House.






generadoresNashville lofts

8:15 AM  
Blogger FREE-HITMOVIE said...

Allegations of flaws in the Russian legislative elections trigger the country's largest protests (pictured) since the dissolution of the Soviet Union.
bling bling watchsmykker til henne online

8:27 AM  
Blogger FREE-HITMOVIE said...

The Cogan House Covered Bridge is a Burr arch truss covered bridge over Larrys Creek in Cogan House Township, Lycoming County, in the U.S. state of Pennsylvania
pubblicità onlinewebsite developers

8:33 AM  
Blogger FREE-HITMOVIE said...

that the leaves of the beard-heath Leucopogon amplexicaulis surround the stem?
Boots Salegold charms for bracelets

8:37 AM  
Blogger quan said...

real estate tucsonburst pdfhouse at Hogwarts School of Witchcraft and Wizardry has its own special animal emblem, and Ravenclaw is no exception. The Ravenclaw animal emblem is the eagle. Each house also has its own distinct color codes, and the Ravenclaw has its own distinct color code: the very sober bronze and blue.

8:42 AM  
Blogger MANHHIEU said...

This comment has been removed by the author.

11:29 PM  
Blogger thanh11111111 said...

sident is usually directly elected by the people for seven years, and can be elected for a maximum of two terms.[2] The presidency is largely a ceremonial office, but the President does exercise certain limited powers with absolute discretion. The President's official residence is Áras an Uachtaráin in Dublin. The office was established by the Constitution of Ireland in 1937, and became internationally recognised as head of state in 1949 following the coming into force of the Republic of Ire

10:15 AM  
Blogger salesroles said...

thanks for an interesting blog
salesjobs

7:04 AM  
Blogger yeu_yeu said...

Franklin argues that the end of the Cold War brought two main changes. First, the threat of war between the United States and Soviet Union was replaced by regional wars among smaller states. Second, war was transposed to what Franklin calls "another key"—the struggle for global commercial and economic dominance.[39] She asserts that this new form of war is now called globalization and its battlefields are global stock and currency markets.[40] This economic warfare defines the enemy as all those who care about the values of community. create a websiteSmall Business Web Hosting

9:48 AM  
Blogger thrillpier said...

Some others are more powerful that support more features. SMS service providers
are also known as SMS gateway providers, SMS resellers or SMS brokers.
Aduitor for file systemLigase

1:35 AM  
Blogger den_den said...

This comment has been removed by the author.

9:56 AM  
Blogger den_den said...

Soon after meeting in film class at the University of Colorado in 1992, Parker and Stone created an animated short entitled The Spirit of Christmas.[25] The film was created by animating construction paper cutouts with stop motion, and features prototypes of the main characters of South Park, including a character resembling Cartman but named "Kenny", an unnamed character resembling what is today Kenny, and two near-identical unnamed characters who resemble Stan and Kyle. Brian Graden, Fox network executive and mutual friend, commissioned Parker and Stone to create a second short film as a video Christmas card.Car Insurance Guide2003 Honda Civic AC Compressor

9:59 AM  
Blogger picasxo said...

breitling for bentley replica watchesEssay writingThoroughbred racehorse who won two British Classic Races. In a career which lasted from June 1908 to April 1910 he ran thirteen times and won seven races. After showing moderate form as a two-year-old he improved to become one of the best colts in England in the early part of 1909. He won his first five races including the 2000 Guineas and the Epsom Derby. His win at Epsom Downs Racecourse made his owner King Edward VII the first reigning British monarch to win a Derby and was greeted with unprecedented celebration. Minoru's bid to win the British Triple Crown ended when he has beaten by Bayardo in the St Leger. He was retired to stud in 1910 and was soon afterwards exported to Russia, where he disappeared during the Revolution in 1917.

1:48 PM  
Blogger CuteGirl said...

She claims she was forced into an arranged marriage at the age of 17 with a man she met 30 minutes prior to their wedding. She left the community at the age of 19, together with her newly born son.

The book has prompted angry reaction from her former community for revealing some painful secrets. She says she now worries about her personal safety.

But she still says that she is proud of her origins and that her intent was not to harm or embarrass anyone, but to open a dialogue.
bed sydneyEssay writing

7:34 PM  
Blogger picasxo said...

Kumarakom hotelsBoston Physical TherapyOn return to Port Jackson, the Mermaid was found to be no longer seaworthy, and was replaced by the brig Bathurst. In May 1821, Roe sailed in the Bathurst on the King expedition of 1821. They sailed north up the coast, anchoring at Cairncross Island in bad weather on 30 June. When the sails were hauled in, the fore top-mast stay-sail halliards were accidentally let go, and Roe, who was at the masthead holding onto them, fell 50 feet (15 m) onto the deck. He was knocked unconscious, but was not badly hurt; he recovered quickly, but in later years would attribute to this accident the loss of sight in his right eye.

11:01 AM  
Blogger KinhMinh said...

cheapest domain namesReliability engineering consulting

You love the roses - so do I. I wish
They sky would rain down roses, as they rain
From off the shaken bush. Why will it not?
Then all the valley would be pink and white
And soft to tread on. They would fall as light
As feathers, smelling sweet; and it would be
Like sleeping and like waking, all at once!

8:57 AM  
Blogger aloalo said...

Best credit card applicationsRechtsanwalt KreuztalThe Banksias, by Celia Rosser, is a three-volume series of monographs containing paintings of every Banksia species. Its publication represented the first time such a large genus had been entirely painted by a single botanical artist. It has been described as "one of the outstanding botanical works of this century.

12:24 AM  
Blogger 12345 said...

seks spelvintage wedding dressesOn 14 May, more than 20,000 people packed Anfield for a match held in memory of the 96. The Liverpool Legends, comprising ex-Liverpool footballers beat the All Stars, captained by actor Ricky Tomlinson by 3–1. The event marked the 20th anniversary of the Hillsborough disaster and raised cash for the Marina Dalglish Appeal which will be put towards a new radiotherapy centre at University Hospital in Aintree.

4:37 AM  
Blogger aloxo said...

florence knoll sofaIgre igriceBerkeley gained a reputation for student activism in the 1960s with the Free Speech Movement in 1964,[21] and opposition to the Vietnam War. In the highly publicized People's Park protest in 1969, students and the school conflicted over use of a plot of land; the National Guard was called in and violence erupted.[21][22] Modern students at Berkeley are less politically active, with a greater percentage of moderates and conservatives.[23][24] Democrats outnumber Republicans on the faculty by a ratio of 9:1.

1:02 PM  
Blogger aloxo said...

New Condos Mississaugaprofesores particulares de ingles en barcelonaAs the eldest son of the British sovereign, he was automatically Duke of Cornwall and Duke of Rothesay at birth. As a son of Prince Albert, he also held the titles of Prince of Saxe-Coburg and Gotha and Duke of Saxony. Queen Victoria created her son Prince of Wales and Earl of Chester on 8 December 1841. He was created Earl of Dublin on 17 January 1850, a Knight of the Garter on 9 November 1858, and a Knight of the Thistle on 24 May 1867.

2:27 AM  
Blogger uknowme said...

Some others are more powerful that support more features. SMS service providers
are also known as SMS gateway providers, SMS resellers or SMS brokers. 3 Mobile Voucher Codesit support los angeles

4:32 AM  
Blogger TransferontheSpot said...

Great post! thank you for the insight on this topic.


Timeshare Relief

12:34 PM  
Blogger yeu_yeu said...

The lower reaches of the ancestral river passed through a valley near where Mount Hood later arose. Carrying sediments from erosion and erupting volcanoes, it built a 2-mile (3.2 km) thick delta that underlies the foothills on the east side of the Coast Range near Vernonia in northwestern Oregon.used cisco
Jessops Discount Codes

12:34 PM  
Blogger cuongthao said...

sion to only book Richardson,Webster University but he refused to condemn referee Phil Dowd.He said: "You don't want to see peopleAtlanta Web Design

business broker

1:50 PM  
Blogger Mr Hiếu said...

best franchise opportunities

Promotional Stress ballsn and erupting volcanoes, it built a 2-mile (3.2 km) thick delta that underlies the foothills on the east side of the Coast Range near Vernonia in northwestern Oreg

9:58 PM  
Blogger cuongthao said...

Emotionally focused Therapy Bay Area

holiday cartoon illustrationsThe office was established by the Constitution of Ireland in 1937, and became internationally recognised as head of state in 1949 following the coming into force of the Republic of Ireland Act.

11:42 PM  
Blogger Eugenio Gersch said...

tesis

12:03 AM  
Blogger Shalini said...

Wow amazing i saw the article with execution models you had posted. It was such informative. Really its a wonderful article. Thank you for sharing and please keep update like this type of article because i want to learn more relevant to this topic.

Hadoop Training in Chennai

2:18 AM  
Blogger Ananth M said...


Very informative blog. Thank you so much for sharing this unique information with us.
This provides me the best way of assuring the quality content. Hadoop training in Chennai

12:31 AM  
Blogger Nainika Joseph said...

Thank you for taking the time to provide us with your valuable information. We strive to provide our candidates with excellent care and we take your comments to heart.As always, we appreciate your confidence and trust in us.

SAP training in Chennai

3:05 AM  
Blogger Jeffy said...

Here i had read the content you had posted. It is much interesting so please keep update like this.

SEO Company in Chennai

1:58 AM  
Blogger Keerthi said...

Excellent and very cool idea and the subject at the top of magnificence and I am happy to this post..Interesting post! Thanks for writing it. What's wrong with this kind of post exactly? It follows your previous guideline for post length as well as clarity..

Corporate Training in Chennai

3:55 AM  
Blogger Aashi siva said...

Really, these quotes are the holistic approach towards mindfulness. In fact, all of your posts are. Proudly saying I’m getting fruitfulness out of it what you write and share. Thank you so much to both of you.

Corporate Training in Chennai

2:49 AM  
Blogger Sathya G said...


the blog is very interesting and will be much useful for us. thank you for sharing the blog with us. please keep on updating.
ROI Services in Chennai

6:36 AM  
Blogger Aasha said...

Wow amazing i saw the article with execution models you had posted. It was such informative. Really its a wonderful article. Thank you for sharing and please keep update like this type of article because i want to learn more relevant to this topic.

Email Marketing Chennai

10:32 PM  
Blogger Sathya G said...

Superb i really enjoyed very much with this article here. Really its a amazing article i had ever read. I hope it will help a lot for all. Thank you so much for this amazing posts and please keep update like this excellent article.thank you for sharing such a great blog with us. expecting for your updation.
Hadoop Training in chennai

12:37 AM  
Blogger Abiya Carol said...

This blog is having the general information. Got a creative work and this is very different one.We have to develop our creativity mind.This blog helps for this. Thank you for this blog. This is very interesting and useful.

Hadoop Training in Chennai

5:37 AM  
Blogger Anne NormaStephanie said...

This information is impressive; I am inspired with your post writing style & how continuously you describe this topic. After reading your post, thanks for taking the time to discuss this, I feel happy about it and I love learning more about this topic
Cara Menurunkan Leukosit Tinggi

5:43 PM  
Blogger Priya said...

It's interesting that many of the bloggers to helped clarify a few things for me as well as giving.Most of ideas can be nice content.The people to give them a good shake to get your point and across the command.

ielts coaching in Chennai

8:36 PM  
Blogger Padhma said...


like to read this information. This is the most easy way of learning. This helps me to get some idea regarding this and helps me to bring a creative thought.
Back to original

10:38 PM  
Blogger Shalini said...


Very nice info..!!
seo company in india
digital marketing company in india
seo company in chennai
digital marketing company in chennai

10:22 PM  
Blogger Shalini said...

Superb. I really enjoyed very much with this article here. Really it is an amazing article I had ever read. I hope it will help a lot for all. Thank you so much for this amazing posts and please keep update like this excellent article.thank you for sharing such a great blog with us. expecting for your.

seo company in india

9:23 PM  
Blogger Abiya Carol said...

It's interesting that many of the bloggers to helped clarify a few things for me as well as giving.Most of ideas can be nice content.The people to give them a good shake to get your point and across the command.

Digital Marketing Course in Chennai

9:55 PM  
Blogger Evangeline Mitul said...

These provided information was really so nice,thanks for giving that post and the more skills to develop after refer that post. Your articles really impressed for me,because of all information so nice.

Best Dental Clinic In Chennai

11:41 PM  
Blogger Akshaysri said...

This blog is having the general information. Got a creative work and this is very different one.We have to develop our creativity mind.This blog helps for this. Thank you for this blog. This is very interesting and useful.
IELTS Coaching in Chennai

3:51 AM  
Blogger Thamizharasi J said...


Great post!I am actually getting ready to across this information,i am very happy to this commands.Also great blog here with all of the valuable information you have.Well done,its a great knowledge.

Fresher Jobs in Mumbai
Fresher Jobs in Pune
Fresher Jobs in Noida
Fresher Jobs in Hyderabad

1:20 AM  
Blogger Evangeline Mitul said...

Really i enjoyed very much. And this may helpful for lot of peoples. So you are provided such a nice and great article within this.

Laser Root Canal Treatment In Chennai

Best Dental Clinic In Velachery

2:05 AM  
Blogger tessa tessa said...

There are lots of information about latest technology and how to get trained in them, like this have spread around the web, but this is a unique one according to me. The strategy you have updated here will make me to get trained in future technologies. By the way you are running a great blog. Thanks for sharing this.

SEO Company in India

9:23 PM  
Blogger Mahalya sree said...

Wow.. Thanks much for sharing.. My friend also recommended you so that i can have a helping hand to make my blog as effective as possible.
Office Interiors in Chennai
Interior Decorators in Chennai

10:46 PM  
Blogger Isabella Olivia said...

This information is impressive; I am inspired with your post writing style & how continuously you describe this topic.


Pawn Shop

Pawn Loans

Pawn Shops

Pawn Loan

Pawn Shop near me

10:28 AM  

Post a Comment

<< Home