SICP: A note about Exercise 3.27

This exercise in Section 3.3.3 demonstrates a concept called “memoization,” where values that are created during the run of a function are stored, so that when requests for certain computations repeat, the previously computed values can just be retrieved, rather than redone. It’s a caching technique.

I got really frustrated trying to do this exercise, because of the way the make-table function was portrayed. The exercise text doesn’t say anything about it. The code that was given for the exercise just uses it. In the past, exercises would use code that had already been introduced and discussed in the section/chapter. There is a set of functions that implement a single-dimension table (all that would be needed for this exercise) that is discussed earlier in the section. When I brought what I thought were the appropriate functions together, what I saw was this:

(define (make-table)
   (list '*table*))

(define memo-fib
   (memoize (lambda (n)
               (cond ((= n 0) 0)
                     ((= n 1) 1)
                     (else (+ (memo-fib (- n 1))
                              (memo-fib (- n 2))))))))

(define (memoize f)
   (let ((table (make-table)))
      (lambda (x) ...

Even the two-dimensional versions of make-table that were presented initialized their local table the same way. I’m used to paying attention to details in code, and so I tried to make sense of this. Every time memo-fib got called, the table got reinitialized, wiping out everything that had been added to it! This made no sense for this exercise, since the whole idea was to store values in the table, and then retrieve them later.

By looking at what other people had done with this exercise, I realized that I needed to use “wishful thinking,” and ignore any prior implementations of make-table. Just assume that make-table initializes its table structure on the first call, and returns a reference to its table (or a reference to a dispatch function) on subsequent calls to it. Assume that it does not reinitialize its internal structure, leaving anything that was previously added intact. Once I made these assumptions, the exercise made more sense.

What I saw other people do as well was assume that the insert! and lookup functions operated in constant time, taking them out as a factor in the number of steps. I do not know what assumptions are “supposed” to be made about the insert! and lookup functions. If you are doing this exercise for a grade, take these assumptions at your own risk. To me, it made sense, but perhaps your professor has a different idea in mind for how these functions are supposed to be considered in your analysis.

Advertisements

Just thought this was cool: 9/11 and the creation of Meetup.com

The 10th anniversary of the 9/11 attacks is coming up in 2 days. I received the following e-mail today from Meetup.com, telling the tale of how Meetup was created in response to the 9/11/01 attacks in New York City. Great story!

Fellow Meetuppers,

I don’t write to our whole community often, but this week is
special because it’s the 10th anniversary of 9/11 and many
people don’t know that Meetup is a 9/11 baby.

Let me tell you the Meetup story. I was living a couple miles
from the Twin Towers, and I was the kind of person who thought
local community doesn’t matter much if we’ve got the internet
and tv. The only time I thought about my neighbors was when I
hoped they wouldn’t bother me.

When the towers fell, I found myself talking to more neighbors
in the days after 9/11 than ever before. People said hello to
neighbors (next-door and across the city) who they’d normally
ignore. People were looking after each other, helping each
other, and meeting up with each other. You know, being
neighborly.

A lot of people were thinking that maybe 9/11 could bring
people together in a lasting way. So the idea for Meetup was
born: Could we use the internet to get off the internet — and
grow local communities?

We didn’t know if it would work. Most people thought it was a
crazy idea — especially because terrorism is designed to make
people distrust one another.

A small team came together, and we launched Meetup 9 months
after 9/11.

Today, almost 10 years and 10 million Meetuppers later, it’s
working. Every day, thousands of Meetups happen. Moms Meetups,
Small Business Meetups, Fitness Meetups… a wild variety of
100,000 Meetup Groups with not much in common — except one
thing.

Every Meetup starts with people simply saying hello to
neighbors. And what often happens next is still amazing to me.
They grow businesses and bands together, they teach and
motivate each other, they babysit each other’s kids and find
other ways to work together. They have fun and find solace
together. They make friends and form powerful community. It’s
powerful stuff.

It’s a wonderful revolution in local community, and it’s thanks
to everyone who shows up.

Meetups aren’t about 9/11, but they may not be happening if it
weren’t for 9/11.

9/11 didn’t make us too scared to go outside or talk to
strangers. 9/11 didn’t rip us apart. No, we’re building new
community together!!!!

The towers fell, but we rise up. And we’re just getting started
with these Meetups.

Scott Heiferman (on behalf of 80 people at Meetup HQ)
Co-Founder & CEO, Meetup
New York City
September 2011

I had no idea! I didn’t hear of Meetup until Howard Dean ran for the Democratic presidential nomination in 2004, since his campaign was using it to organize. I thought it was a social media thing, of sorts, and I wasn’t that interested in it. Somehow (can’t remember now) I started using it in 2009, and I found a local Lisp users group through it. I’ve met some great people as a result. Thanks so much, Meetup!