Functional Problem Solving (CSC 151 2014F) : Readings
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
Summary:
Up to this point, all of the programs we have written are, in some
sense, predictable. That is, the output depends only on the input.
However, we want some programs, such as games and simulations,
to be less predictable. We may also want to have make drawings
using unpredictable procedures, so that we can derive inspiration
from unexpected results. In this reading, we consider Scheme's
tools for supporting such unpredictability, particularly the
random
procedure.
Many computing applications involve the simulation of games or events, with the hope of gaining insights and identifying underlying principles. In some cases, simulations can apply definite, well-known formulae. For example, in studying the effect of a pollution source in a lake or stream, one can keep track of pollutant concentrations in various places. Then, since the flow of water and the interactions of pollutants is reasonably well understood, one can follow the flow of the pollutants over a period of time, according to known equations.
In other cases, specific outcomes involve some chance. For example, when an automobile begins a trip and encounters a traffic light, it may be a matter of chance whether the light is green, yellow, or red. Similar uncertainties arise when considering genetic mutations or when tabulating outcomes involving flipping a coin, tossing a die, or dealing cards. In these cases, one may know about the probability of an event occurring (a head occurs about half the time), but the outcome of any one event depends on chance.
In studying events that involve some chance, one approach is to model the event or game, using a random-number generator as the basis for decisions. If such a model is simulated many times on a computer, the results may give some statistical information about what outcomes are likely and how often each type of outcome might be expected to occur. This approach to problem solving is called the Monte Carlo Method.
Randomness is also useful in image generation. A number of artists, from the founders of the Dada movement to Jackson Pollock and beyond, have reveled in the images that can be created by random or unpredictable processes. The Dadaists employed random selection to write poetry and subconscious drawing to create images. Pollock threw paint with an expectation that interesting patterns would result. (And yes, those are incredible simplifications of the philosophies and techniques of these artists.) By combining a random-number generator with some drawing techniques, we can produce some potentially interesting images.
random
Procedure
A random number generator for a typical computer language is a procedure
that produces an unpredictable value each time it is called. Such
procedures simulate a random selection process. Scheme provides the
procedure random
for this purpose. This procedure
returns integer values that depend on its parameter. In particular,
random
returns an unpredictable integer value
between 0 and one less than its parameter, inclusive. By
“unpredictable” we mean that we are unlikely to be
able to predict the number that random
will
return.
>
(random 10)
1
>
(random 10)
9
>
(random 10)
7
>
(random 10)
0
>
(random 10)
5
>
(random 10)
1
>
(random 10)
0
We can use random
to write a program to simulate
the rolling of a die. The simulation generates integers from 1 to
6, to correspond to the faces on the die cube. The details of this
simulation are shown in the following procedure:
;;; Procedure: ;;; roll-a-die ;;; Parameters: ;;; None ;;; Purpose: ;;; To simulate the rolling of one six-sided die. ;;; Produces: ;;; An integer between 1 and 6, inclusive. ;;; Preconditions: ;;; [None] ;;; Postconditions: ;;; Returns an integer between 1 and 6, inclusive. ;;; It should be difficult (or impossible) to predict which ;;; number is produced. (define roll-a-die (lambda () (+ (random 6) ; a value in the range [0 .. 5] 1))) ; now in the range [1 .. 6]
We can use that procedure to simulate the roll of multiple dice.
;;; Procedure: ;;; roll-dice ;;; Parameters: ;;; n, an integer ;;; Purpose: ;;; Roll n six-sided dice and make a list of their values. ;;; Produces: ;;; rolls, a list of integers ;;; Preconditions: ;;; [No additional] ;;; Postconditions: ;;; (length rolls) = n ;;; Each element of rolls is a value between 1 and 6. ;;; The values in rolls are reasonably evenly distributed. ;;; The values in rolls are difficult to predict. (define roll-dice (lambda (n) (if (zero? n) null (cons (roll-a-die) (roll-dice (- n 1))))))
We can use a number of simple techniques to generate such randomized art. What can we randomize? One thing to start with is colors. Given a list of colors, it is easy to select one of those colors.
;;; Procedure: ;;; random-rainbow-color ;;; Parameters: ;;; [None] ;;; Purpose: ;;; Picks a "random" (unpredictable) color from the basic colors ;;; of the rainbow. ;;; Produces: ;;; color, a string ;;; Preconditions: ;;; [None] ;;; Postconditions: ;;; color is a color. ;;; It is difficult for someone to predict what color random-color ;;; will return. (define random-rainbow-color (let ([rainbow (map color->irgb (list "red" "orange" "yellow" "green" "blue" "indigo" "violet"))]) (lambda () (list-ref rainbow (random (length rainbow))))))
It's also possible to be a bit more open in our random selection. For example, we can choose a random color simply by choosing random red, green, and blue components.
;;; Procedure: ;;; random-color ;;; Parameters: ;;; [none] ;;; Purpose: ;;; Selects and returns a random color. ;;; Produces: ;;; color, a color. ;;; Postconditions: ;;; color is difficult to predict. (define random-color (lambda () (irgb (random 256) (random 256) (random 256))))
Similarly, we can choose a random brush. The easiest way to choose a random brush is to select a random element of the brushes list.
;;; Procedure ;;; select-random-brush! ;;; Parameters: ;;; (none) ;;; Purpose: ;;; Select one of the brushes. ;;; Produces: ;;; (nothing) ;;; Postconditions: ;;; It is difficult to predict the brush. (define select-random-brush! (lambda () (context-set-brush! (list-ref (context-list-brushes) (random (length (context-list-brushes)))))))
However, that procedure can choose from perhaps too many brushes. We might create a similar procedure that selects from a particular list of brushes.
;;; Procedure: ;;; randomly-select-brush! ;;; Parameters: ;;; brushes, a list of strings ;;; Purpose: ;;; Select one of brushes. ;;; Produces: ;;; (nothing) ;;; Preconditions: ;;; All the strings in brushes name valid brushes. ;;; Postconditions: ;;; The current brush is an element of brushes. ;;; It is equally likely that each element of brushes is now the ;;; active brush ;;; It is difficult to predict which brush will be selected. (define randomly-select-brush! (lambda (brushes) (context-set-brush! (list-ref brushes (random (length brushes))))))
If we wanted to select one of the circle brushes, we might use
>
(randomly-select-brush! (list "2. Hardness 025" "2. Hardness 050" "2. Harndess 075" "2. Hardness 100"))
or
>
(randomly-select-brush! (context-list-brushes "2. Hardness"))
In fact, we can rewrite select-random-brush!
using this procedure.
(define select-random-brush! (lambda () (randomly-select-brush! (context-list-brushes))))
It is, of course, also possible that we'll want to randomly select from other lists (not just lists of brushes). For example, we might want randomly select a shade of blue by selecting an element of the list of all colors with “blue” in their names. Hence, we'll define a generalized procedure for randomly selecting elements of lists. (This procedure is now part of the standard Mediascheme/gigls library.)
;;; Procedure: ;;; list-random-element ;;; Parameters: ;;; values, a list ;;; Purpose: ;;; Randomly select an element of values. ;;; Produces: ;;; value, a value ;;; Preconditions: ;;; values is nonempty. ;;; Postconditions: ;;; value is an element of values. ;;; value is equally likely to be any element of values. ;;; It is difficult to predict which value it is. ;;; Problems: ;;; If values has only one element, it's not so difficult to predict ;;; which value is returned. (define list-random-element (lambda (values) (list-ref values (random (length values)))))
We can now select a random shade of blue with the following procedure.
;;; Procedure: ;;; random-blue ;;; Parameters: ;;; [None] ;;; Purpose: ;;; Selects a color with blue in its name. ;;; Produces: ;;; some-blue, an integer-encoded RGB color ;;; Preconditions: ;;; [None] ;;; Postconditions: ;;; some-blue is a color whose name includes "blue". ;;; It is difficult to predict which blue it is. (define random-blue (let ([colors-blues (map color-name->irgb (list "aliceblue" "blue" "blueviolet" "cadetblue" "cornflowerblue" "darkblue" "darkslateblue" "deepskyblue" "dodgerblue" "lightblue" "lightskyblue" "lightsteelblue" "mediumblue" "mediumslateblue" "midnightblue" "powderblue" "royalblue" "skyblue" "slateblue" "steelblue"))]) (lambda () (list-random-element colors-blues))))
We can also rewrite randomly-select-brush!
to use
list-random-element
. (The process of identifying common
procedures and then rewriting code to use these common procedures is
called refactoring, and it's a good practice.)
(define randomly-select-brush! (lambda (brushes) (context-set-brush! (list-random-element brushes))))
Let's step back and remember what we're doing. We're trying to build a procedure (or set of procedures) that make unpredictable images. What have we figured out so far? We have a way to randomly select colors and to randomly select brushes. What next? Now we need ways to randomly draw things. For lines, circles, and rectangles, we can simply randomly select all of the parameters (perhaps within certain limits, such as the width and height of the image). For example, here is a procedure to draw a line between two randomly selected points.
;;; Procedure: ;;; draw-random-line! ;;; Parameters: ;;; image, an image ;;; Purpose: ;;; Draw a random line in the image, assuming that its width ;;; and height are as specified. ;;; Produces: ;;; (nothing) ;;; Postconditions: ;;; A new line has been added to image, using the current color ;;; and brush. (define draw-random-line! (lambda (image) (image-draw-line! image (random (image-width image)) (random (image-height image)) (random (image-width image)) (random (image-height image)))))
There are many interesting variants, such as ones that use a fixed starting point, a fixed line length, and so on and so forth.
Now that we know how to select colors unpredictably, how to select brushes unpredictably, and how to draw lines unpredictably. We can write a procedure that puts all of these techniques together.
;;; Procedure: ;;; splat! ;;; Parameters: ;;; image, an image ;;; Purpose: ;;; Draw a line between random points, using a random color and ;;; a random brush. ;;; Produces: ;;; (nothing) ;;; Postconditions: ;;; The foreground color may have changed. ;;; The brush may have changed. ;;; The image now contains another line. ;;; It should be difficult to predict what that line will look like. (define splat! (lambda (image) (context-set-fgcolor! (random-color)) (select-random-brush!) (draw-random-line! image) (context-update-displays!) image))
random
a. When you give the procedure random
the
parameter n
, it will produce one of how many
unique values? What is the smallest value? What is the largest?
b. Evaluate the expression (random 10)
several times.
What values do you get?
c. What values do you expect to get if you call
random
with 1 as a parameter?
d. Check your hypothesis experimentally.
e. What do you expect to happen if you call random
with 0 or -1 as a parameter?
f. Check your hypothesis experimentally.
g. What do you expect to happen if you call
random
with non-integer parameters.
h. Check your hypothesis experimentally.
i. Try calling random
with no parameters. What
happens?
a. Make a copy of random-drawing-lab.rkt
.
b. Using roll-dice
, roll ten dice.
c. Using roll-dice
, roll ten dice. (Yes, this instruction
is the same as the previous instruction. You should do it twice.)
d. Did you get the same list of values each time? Why or why not?
e. What other procedures have you encountered that may return different values each time you call them with the same parameters?