CSC151.02 2010S Functional Problem Solving : Labs
Primary: [Front Door] [Schedule] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] - [Assignment]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Readings]
References: [A-Z] [By Topic] - [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [CSC151.01 2010S (Weinman)] [CSC151 2009F (Rebelsky)]
Misc: [SamR] [MediaScript] [GIMP]
Summary:
In this laboratory, we consider the various techniques for creating
local recursive procedures, particularly letrec
and named let
. We also review related issues,
such as husk-and-kernel programming.
A letrec statement has the form
(letrec ((name-of-recursive-proc body) (name-of-recursive-proc body) ... (name-of-recursive-proc body)) expression expression ... expression)
This statement builds a new environment (that maps names to values), adds all of the named procedures to the environment, evaluates the expressions and then forgets about the environment. It is useful for temporarily creating local procedures, and for limiting access to kernels.
A named let is an alternative mechanism for defining recursive kernels. It can be used only when you want to define a single recursive kernel and call it immediately, and has the form
(let kernel ((name_1 exp_1) ... (name_n exp_n)) body)
The named let tells Scheme to define a new procedure (whose name is kernel), with parameters that correspond to the names and whose body corresponds to body. That is, it creates the following procedure
(let ((kernel (lambda (name_1 ... name_2) body))) ...)
It then gives the result of of calling
kernel
on exp_1
... exp_n
.
Make a copy of local-procs-lab.scm
, which contains the code for this lab.
As the reading suggested, local kernels are particularly appropriate for checking preconditions. Local kernels are also appropriate for writing recursive helper procedures that take an extra parameter to accumulate a result.
For example, here is a helper-based definition of
rgb-brightest
.
(define rgb-brightest (lambda (colors) (rgb-brightest-helper (car colors) (cdr colors)))) (define rgb-brightest-helper (lambda (brightest-so-far remaining-colors) (cond ((null? remaining-colors) brightest-so-far) ((rgb-brighter? (car remaining-colors) brightest-so-far) (rgb-brightest-helper (car remaining-colors) (cdr remaining-colors))) (else (rgb-brightest-helper brightest-so-far (cdr remaining-colors))))))
a. Rewrite this to make the helper local and to name the helper
kernel
.
b. Test your procedure on a few simple lists of colors. For example, you might try some of the following.
>
(rgb->color-name (rgb-brightest (map color-name->rgb (list "red" "green" "blue"))))
>
(rgb->color-name (rgb-brightest (map color-name->rgb (list "black"))))
>
(rgb->color-name (rgb-brightest (map color-name->rgb (list "red" "black" "green" "yellow"))))
>
(rgb->color-name (rgb-brightest (map color-name->rgb (list "yellow" "red" "black" "green"))))
c. When you are done, you may want to compare your answer to a sample solution contained in the notes on the exercise.
The procedure given above, and your rewrite of that procedure, will fail
miserably if given an inappropriate parameter, such as an empty list, a
list that contains values that are not colors, or a non-list. Rewrite
rgb-brightest
so that it checks its preconditions (including
that the list contains only RGB colors) before calling the kernel.
Note that you can use rgb?
to check if a value
represents an RGB color.
Rewrite rgb-brightest-helper
using a named let
rather than letrec
. (The goal of this exercise
is to give you experience using named let, so you need not check
preconditions for this exercise.)
When you are done, you may want to compare your answer to a sample solution contained in the notes on the exercise.
(define tally-brights (lambda (lst) (tally-brights-helper 0 lst))) (define tally-brights-helper (lambda (tally remaining) ...))
a. Finish the definition.
b. Rewrite the definition of tally-brights
to make
the helper a local procedure. You may use
letrec
or named let.
Rewrite tally-brights
(from Exercise 4) to use
whichever of letrec and named let you did not use in that exercise.
You have now seen two examples in which you've employed two
different strategies for building local helpers, one that uses
letrec
and one that uses named let.
Reflect on which of the two strategies you prefer and why.
A list of colors is a bright-dark-alternator if its elements are alternately bright colors and dark colors, beginning with a bright color. A list of colors is a dark-bright-alternator if its elements are alternately dark and bright, beginning with a dark color. (We say that the empty list is both a bright-dark-alternator and a dark-bright-alternator.)
a. Write a predicate, colors-alternating-brightness?
,
that determines whether a non-empty list of colors is either
a bright-dark-alternator or a dark-bright-alternator. Your
definition should include a a letrec
expression
in which the identifiers bright-dark-alternator?
and dark-bright-alternator?
are bound to mutually
recursive predicates, each of which determines whether a given list
has the indicated characteristic.
(define colors-alternating-brightness? (lambda (colors) (letrec ((bright-dark-alternator? (lambda (colors) ...)) (dark-bright-alternator? (lambda (colors) ...))) ...)))
When you are done, you may want to compare your answer to a sample solution contained in the notes on the exercise.
b. Here are a few lists of colors. For which do you expect
the colors-alternating-brightness?
predicate to hold?
(define sample0 null) (define sample1 (list RGB-WHITE)) (define sample2 (list RGB-BLACK)) (define sample3 (list RGB-WHITE RGB-BLACK)) (define sample4 (list RGB-BLACK RGB-WHITE)) (define sample5 (list RGB-BLACK RGB-BLACK)) (define sample6 (list RGB-WHITE RGB-BLACK RGB-WHITE)) (define sample7 (list RGB-WHITE RGB-BLACK RGB-WHITE RGB-BLACK RGB-WHITE)) (define sample8 (list RGB-RED RGB-YELLOW RGB-BLUE RGB-WHITE RGB-BLACK))
c. Check your answers experimentally.
Here is one possible solution.
(define rgb-brightest (lambda (colors) (letrec ((kernel (lambda (brightest-so-far remaining-colors) (cond ((null? remaining-colors) brightest-so-far) ((rgb-brighter? (car remaining-colors) brightest-so-far) (kernel (car remaining-colors) (cdr remaining-colors))) (else (kernel brightest-so-far (cdr remaining-colors))))))) (kernel (car colors) (cdr colors)))))
Here is one possible solution.
(define rgb-brightest (lambda (colors) (let kernel ((brightest-so-far (car colors)) (remaining-colors (cdr colors))) (cond ((null? remaining-colors) brightest-so-far) ((rgb-brighter? (car remaining-colors) brightest-so-far) (kernel (car remaining-colors) (cdr remaining-colors))) (else (kernel brightest-so-far (cdr remaining-colors)))))))
Once bright-dark-alternator?
and
dark-bright-alternator?
are written, the definition
is fairly straightforward. A non-empty list of colors has alternating
brightness if it's not empty and it's either a bright-dark-alternator
or a dark-bright-alternator.
(and (not (null? colors)) (or (bright-dark-alternator? colors) (dark-bright-alternator? colors)))
Each definition is also fairly straightforward. A list is a bright-dark-alternator if it is empty or if the car is bright and the cdr is a dark-bright-alternator.
(bright-dark-alternator? (lambda (colors) (or (null? colors) (and (rgb-bright? (car colors)) (dark-bright-alternator? (cdr colors))))))
The definition of dark-bright-alternator?
is so similar
that we will not provide it separately.
Putting everything together, we get
(define colors-alternating-brightness? (lambda (colors) (letrec ((bright-dark-alternator? (lambda (colors) (or (null? colors) (and (rgb-bright? (car colors)) (dark-bright-alternator? (cdr colors)))))) (dark-bright-alternator? (lambda (colors) (or (null? colors) (and (rgb-dark? (car colors)) (bright-dark-alternator? (cdr colors))))))) (and (not (null? colors)) (or (bright-dark-alternator? colors) (dark-bright-alternator? colors))))))
Note that there is a hidden moral here: The procedures defined in a
letrec
can be mutually recursive.
Primary: [Front Door] [Schedule] - [Academic Honesty] [Instructions]
Current: [Outline] [EBoard] [Reading] [Lab] - [Assignment]
Groupings: [Assignments] [EBoards] [Examples] [Exams] [Handouts] [Labs] [Outlines] [Projects] [Readings]
References: [A-Z] [By Topic] - [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [CSC151.01 2010S (Weinman)] [CSC151 2009F (Rebelsky)]
Misc: [SamR] [MediaScript] [GIMP]
Copyright (c) 2007-10 Janet Davis, Matthew Kluber, Samuel A. Rebelsky, and Jerod Weinman. (Selected materials copyright by John David Stone and Henry Walker and used by permission.)
This material is based upon work partially supported by the National Science Foundation under Grant No. CCLI-0633090. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
This work is licensed under a Creative Commons
Attribution-NonCommercial 2.5 License. To view a copy of this
license, visit http://creativecommons.org/licenses/by-nc/2.5/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.