CS 5010 F '09
Pair Programming
The Recipes
The Style
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


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.


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.


      > (geo-code "220 Huntington" "Boston" "MA" "02115" "USA")
       ((xmlns "urn:yahoo:maps")
        (xmlns:xsi "http://www.w3.org/2001/XMLSchema-instance")
         "urn:yahoo:maps http://api.local.yahoo.com/MapsService..."))
        ((precision "address"))
        (Latitude () "42.343340")
        (Longitude () "-71.083840")
        (Address () "220 Huntington Ave")
        (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.
      geo result

  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 2009generated with PLT Scheme