CS 5010 F '09 Pair Programming The Recipes The Style Subversion Assignments Set 1 Set 2 Set 3 Set 4 Set 5 Set 6 Set 7 Set 8 Set 9 Set 10 Set 11 Set 12

### Problem Set 8

Due date: due to the holiday, 11/12, 10am

Purpose:

The goal of this problem set is to practice all design recipes in How to Design Programs, i.e., structurally recursive and generative recursive functions, plus accumulators and the use and/or creation of abstractions. You must learn to pinpoint which design approach each function uses and whether or not using an accumulator-style is useful or not.

#### Drill:

Design the function `neighbors`, which consumes a URI, retrieves the HTML as an X-expression, and extracts all `src` links in `img` elements and all `href` links in `a` elements. Use the function `read-xexpr/web` from the teachpack "more-io.ss" to locate and retrieve X-expressions.

#### Required Problems:

Note: You must use the Intermediate Student Language with Lambda.

Note: You must annotate each function with the design strategy that you used as follows:

• domain knowledge exclusively (algebra, physics, watching traffic lights)
• function composition (very few functions qualify!)
• structural design, which argument
• structural design, supplemented with list abstractions (313)
• generative-recursion design.
For both structural and generative designs, you may add "with accumulators" though if you do, be sure to explain the connection between the local recursion argument, the accumulator, and the initial argument.

1. Design the world program `show-me`, which combines the Yahoo! geocode service with Google's mapping service to produce a zoomable map for some given address. Specifically, the `show-me` function consumes a street address and in response opens a world canvas with a zoomable map. Pressing the "left" arrow should zoom in on the specified location (if possible) and pressing the "right" arrow should zoom out (if possible).

The teachpack geocode.ss provides two functions: `geo-code`, which maps a street-level address into a "geo code", including latitude and longitude information, and `map-image`, which consumes latitude and longitude information plus a zoom factor between 0 and 21 to produce a map.

Examples:

````  > (geo-code "220 Huntington" "Boston" "MA" "02115" "USA")`
(ResultSet
((xmlns "urn:yahoo:maps")
(xmlns:xsi "http://www.w3.org/2001/XMLSchema-instance")
(xsi:schemaLocation
"urn:yahoo:maps http://api.local.yahoo.com/MapsService..."))
(Result
(Latitude () "42.343340")
(Longitude () "-71.083840")
(City () "Boston")
(State () "MA")
(Zip () "02115-4702")
(Country () "US")))
```
As you can see, the function produces an `Xexpr` (a representation of some XML answer). For processing this kind of XML, see the Yahoo! site and re-use from 4.1 or 5.1 or 6.1. (If the result contains more than one location, pick one or pick all.)
``````  > (overlay (map-image 42.343701 -71.083472 15)
(circle 10 'solid 'blue))
``````
The blue dot confirms that this function produces images with the pinhole at the center of the image and at the specified address.
```
```

2. Design the program `closed-site`. Roughly speaking, the program checks that chasing links starting at some specific Web page -- specified via a string that points to a HTML page site (i.e., a string ending in "/") on the web -- never lead to a "Web page not found" (404) error. To make the problem manageable, we restrict our attention to `href` connections specified in `a` elements and only those that specify `.html` URIs.

Since the creator of a site doesn't have control over the rest of the Web, the program does not chase links whose URL doesn't extend the given URL. Instead, the program collects all of these "external" URLs and delivers them as one part of the result. The other part of the result covers all of the missing "internal" Web pages, i.e., pages whose URI is a (string) extension of the originally given URI.

Of course, missing links aren't enough information for a Web site designer; he also needs to know where the reference to the missing link occurs. Each missing link should therefore be represented as a `posn` structure whose x-coordinate contains the URI of the reference page and the y-coordinate contains the URI of the missing page. Use `'*start` for a link missing on the original page. The final result of `closed-site` is a `posn` structure that contains the "external misses" in the x-coordinate and the "internal misses" in the y-coordinate. Yes, this is an abuse of `posn`, but this can happen when we program in dynamically typed languages.

The teachpack more-io.ss provides the function `url-exists?`, which consumes a string and checks whether the specified page exists on the Web; and the function `url-html-neighbors`, which consumes a URI string (to an HTML file) and extracts a list of all `href` URIs to html files from the corresponding Web page.

You must abstract your program over the function so that you can test the function without accessing the Web. Only one line of your program should remain untested in such cases.

To use the teachpacks, save them in the SVN directory for problem set 8, and add a require line to your program. Don't forget to commit the teachpack to the SVN repository. You should also ensure that after checking everything in, it runs on alternative computers.

 last updated on Wed Dec 2 17:58:10 EST 2009 generated with PLT Scheme