Assignment 2: Algorithmic Image Paradigms

Due: 9 a.m. Wednesday, 9 February 2011

Summary: In this assignment, you will explore the two models of images we've learned so far (GIMP tools and drawings as values) as you consider how to create some simple images, reflect on what makes them functional or imperative, and generalize the algorithm with a procedure.

Purposes: To give you some experience writing and generalizing algorithms in Scheme. To encourage you to think about the strengths and weaknesses of the different representations.

Expected Time: Two to three hours. You should stop when you reach three hours! If you cannot complete the assignment in that time, note that on your solution and you'll get at least a check.

Collaboration: We would prefer that you work in groups of size three. However, you may in a group of size two, or a group of size four. You may not work alone. You may discuss this assignment with anyone you wish. If you discuss this assignment with people other than group members, make sure to include a citation (e.g., “I consulted this person, who helped me do this”).

Submitting: Send your answer to <grader-151-01@cs.grinnell.edu>. The title of your email should have the form CSC-151-01 Assignment 2 and should contain your answers to all parts of the assignment. Please send your answers in the body of the message, rather than as an attachment.

So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.

Preliminaries

We've now seen a variety of ways to describe images, both informal and formal. We've even seen two Scheme-based models: GIMP tools, and drawings as images.

Given an image to construct, how do you choose which one to use? in many cases, one model will lend itself to the problem more naturally than another. For example, if you needed a lot of diagonal lines in your image, you would be unlikely to use the drawings as values model, since it does not directly support lines.

But one might also look at the algorithms (programs) that get constructed under a particular model. Computer scientists compare algorithms in many different ways, and we could use some of the common comparisons to compare the resulting algorithms. For example, we might strive to find the algorithm that is fastest or that is most concise. Because speed of algorithms can be difficult to measure, for this assignment, we will focus on concision.

How will we measure concision? One could count characters, but that would encourage programmers to use unreadable, one-letter, names. A better way is to count the number of units of expression (other than parenthesis). For example, +, body, really-thin-left-arm, and 3.14159 are each considered a single unit in analyzing conciseness. We'll use that metric in looking at solutions in this assignment.

Note that concision should not require you to sacrifice readability. Because we are not counting characters, you should use clear names, such as stick-body, rather than shorthand, such as s. Note also that this metric does not penalize you for using whitespace: spaces, tabs, newlines, and blank lines. Please use as much whitespace as is necessary to make the code readable.

Assignment

Problem 1: Drawing Simple Images

Consider the following two images. For each image described below, write a program (that is, a sequence of expressions) to generate the image, using either the Scheme-based GIMP tools or drawings as values. Your goals are to correctly generate the image and to make your program for generating the image as concise as possible. (Reminder: In considering conciseness, we care more about units of expression, rather than number of characters.)

a. A stick figure. That is, a circle with a long vertical line trailing down from it (representing the body), and four appropriately drawn angled lines sticking out from the body.
b. A checkerboard. That is, an 8x8 grid of squares in alternating black and red colors.

Because choosing the right representation is likely to contribute to the conciseness of the code, make sure that you understand the representations well. You may find it particularly helpful to read the “For those with extra time” section of the lab on drawings as values.

Note that you may only use one of the models for each image, and you must use different models for the different images. In each case, please draw in a 200x200 pixel image.

Problem 2: Reflecting on Simple Images

a. For each image in Problem 1, explain why you chose the GIMP tools model or the drawings-as-values model.

b. How do the GIMP tools reflect the imperative paradigm? Review your program that uses the GIMP tools, and describe the features that make it an imperative program.

c. How do drawings as values reflect the functional paradigm? Review your program that uses drawings as values, and describe the features that make it a functional program.

Problem 3: Drawing Simple Images, Generally

You have already written several programs to create interesting pictures using the GIMP tools. For example, you wrote programs to make a smiley face and a house for the lab on scripting the GIMP tools. You also wrote a program to create a picture in Problem 1.

Take the program you wrote using GIMP tools from Problem 1 and copy and paste it into the body of a new procedure, like so:

(define your-proc-name!
  (lambda (image width height)
     ; Your code for making a picture with GIMP tools goes here
     ))

Delete the line of code that defines a new image. You should not define a new image inside the procedure, because the image is one of the parameters. You may need to change the procedure definition so that the parameter name for the image matches the name of the image in your code.

Try calling your procedure. If you originally made a 200x200 image, you would call your new procedure as follows:

> (define canvas (image-new 200 200))
> (image-show canvas)
1
> (your-proc-name! canvas 200 200)

You should see your picture appear in the image.

But what if you wanted to make a picture that was some other size, and not 200x200? That is where the width and height parameters come in.

Modify your code, still using the GIMP tools procedures, so that the numbers in your code are related to the width and height parameters. For example, if your original program selected a 100x50 ellipse in a 200x200 image, you would modify the call to image-select-ellipse! to instead select an ellipse with the dimensions (* 0.5 width) by (* 0.25 height).

You may alter your original instructions to make them simpler, for example, changing the size and location of elements or removing elements altogether.

Your procedure may take other parameters if you wish, but this is not required. If you add extra parameters, please provide informal documentation explaining how we should use your procedure.

For example, suppose we defined a procedure called sams-smiley! that generalizes the original smiley face from the lab on scripting the GIMP tools. The generalized version takes a width and height as input and draws a simple smiley of that width and height.

Here are some examples of using sams-smiley! to make a smiley face in a 200 x 200 image.

(define canvas (image-new 200 200))
(image-show canvas)
(sams-smiley! canvas 200 200)

(define another-canvas (image-new 200 200))
(image-show another-canvas)
(sams-smiley! another-canvas 100 150)

Note that although the second smiley is much thinner and slightly shorter, the brushes used to draw it are the same. Changing brushes based on image size is beyond the expectations of this assignment.

Important Evaluation Criteria

The first criterion we will use in evaluating your assignments is correctness. In particular, we will check to ensure that each program generates the appropriate image.

The second criterion we will use in evaluating your assignments is conciseness. That is, we will look to see whether your program is short or long for the problem. We will not differentiate short and long variable names, so please use comprehensible names.

We will also consider your choice of models, your creativity in making the images, and your insight into the imperative and functional paradigms.

Extra credit opportunity

We will award extra credit for the most concise code to draw a checkerboard.