Last updated: Fri, 24 Apr 2015 16:27:38 -0400
The textbook introduces the notion of a design recipe as a step-by-step process for turning a problem statement and an empty code buffer into a program that solves the problem.
This page extends and further formalizes The Program Design Recipe, as it pertains to CS5010. You must apply this recipe when writing any programs for this course. Bookmark this page and refer to it often.
When other course materials, like the textbook, conflict with this guide, defer to this guide. We try to sync all the course materials but some differences may still remain.
These are the steps of The Program Design Recipe.
To write a function, apply these steps in order.
A program is a group of functions so to write a program, repeat these steps for every function you write.
Each step is explained in more detail below.
one program may process road and location information to compute driving directions;
another may process player input information to compute the current state of a game;
and yet another may process information about files on a disk to create a user interface.
This is the most critical step of the design recipe. It dictates all subsequent steps.
; A <data-definition-name> is ...
Racket is case-sensitive so data definition names are as well.
This creates a data definition named <data-definition-name>. This name may then be referenced in other (or even the same) data definitions. The defined name may also be referenced in a function’s signature (see the Signature section).
To complete the data definition, we describe the set of values represented by <data-definition-name>. Specifically, the ellipses (...) above may be replaced with:
- a single Racket value:
Data Definition Examples: Atomic Values
; A Zero is a 0. ; An A is an "a". ; A True is a true.This form of data definition rarely occurs by itself and will likely be combined with other data definitions like in the examples below.
- another data definition name:
Data Definition Examples: Aliases
; A Color is a String. ; A Coordinate is a Real.
The right-hand data definition name can refer to a previously defined data definition, or to one of the Pre-defined Data Definitions.
Thus different data definitions may have the same data representation on the right-hand side. This is fine; it just means we are representing different pieces of information as the same data.
Same data, different information
; An Author is a String. ; A Title is a String.
Another good use of aliases is to assign units to values.
Use Aliases to Describe Units
; A Pixels/sec is an Integer. ; An Inches is a PosInt.
Note: The textbook occasionally misses opportunities to use aliases, so be aware of this while reading.
Data Definition Examples: Compound Data
; A Book is a (make-book Author Title) ; A Ball is a (make-ball Coordinate Coordinate Pixels/sec). ; A World is a (make-world Ball Boolean). ; An Attribute is a (list Symbol String).In this course, Racket define-structs (and later lists and cons) are the primary way to create compound data. However, other languages may utilize other constructs (e.g., objects, tuples, records, arrays, etc.). Nevertheless, The Program Design Recipe is applicable regardless of your choice of programming language.
Compound Data: define-struct definitions
(define-struct book (author title)) (define-struct ball (x y speed)) (define-struct world (ball done?))
NOTE: The Ball data definition name and ball struct name are not the same thing (did you notice the difference in capitalization?). They are arbitrarily chosen names that are connected only by a data definition.We alternatively could have created the following valid, but confusing data definitions:
valid, but confusing examples
; A Ball is a (make-world Ball Boolean). ; A World is a (make-ball Coordinate Coordinate Pixels/sec).
Going back to the original, non-confusing definitions, Ball names the data definition (like <data-definition-name> above), while ball is used to define the various struct and struct accessor functions (e.g., make-ball, ball-x, ball-y, etc.). In other words, Ball represents all these possible make-ball values.
Stop reading and do not proceed any further until you understand the difference between data definition names and struct names. END NOTE
; A TrafficLightColor is one of: ; - "red" ; - "yellow" ; - "green"
Ideally, the easiest-to-distinguish choice should be listed first, and the more difficult-to-distinguish choices should be last. This makes it easier to write functions that process this kind of data. See Template for Itemization Data for more information.
In this course, itemization data is defined informally in comments. Similar to compound data, other languages may have other ways to define itemization data such as interfaces, unions, or variants. Again, the The Program Design Recipe is applicable regardless of the specific choice of language.
or, some combination of all the above:
For example, we can define itemization data where some of the choices are compound data. This particular pattern of itemization-of-compound data is common enough that we give it its own name: mixed data.
; A TrafficGuide is one of: ; - (make-circle Inches TrafficLightColor) ; - (make-octagon Inches) (define-struct circle radius color) (define-struct octagon side)
; A Tag is a Symbol. ; An Xexpr is one of: ; - (cons Tag (cons ListOf<Attribute> Xbody)) ; - (cons Tag Xbody) ; An Xbody is one of: ; - empty ; - (cons String Xbody) ; - (cons Xexpr XBody)
Note: We do not give special consideration to intervals or enumerations (mentioned in the book). In course course, we consider both of these as instances of itemization data. Make sure you understand why.
Occasionally, the Data Definition rules presented thus far cannot express the precise set of values that we want our program to use. In this situation, we add data invariants to further restrict the set of values represented by the data definition.
The word WHERE may be useful to introduce such invariants, and the invariant itself is expressed in English prose.
Color, restricted to those accepted by 2htdp/image
; A Color is a String ; WHERE: for each Color c, (image-color? c) = true
; A World is a (make-world ListOf<Ball> NonNegInt) ; WHERE: (length balls) == count (define-struct world (balls count))
It may be helpful to label an interpretation with INTERPRETATION or INTERP. unless it is very short.
; A TrafficGuide is one of: ; - (make-circle ...) ; - (make-octagon ...) ; INTERP: the circle is one possible traffic light, ; and the octagon is a stop sign
Author name, made more precise
; An Author is a string, representing an author's last name.
; A Coordinate is a Real. ; INTERP: ; Represents either an x or y pixel coordinate on a Universe (big-bang) ; canvas, where (0,0) is in the upper-left corner, and right and down are ; the positive directions.
If the data definition name does not directly name the units, the interpretation must include this information.
Make a judgement based on the specific program whether to use the unit name directly, or whether to use a more general data definition name.
; A Temperature is a Real, in degrees Celsius.
; A Speed is an Integer, in m/s.
Data examples are an important part of Data Design. Concrete examples can often illustrate a data definition more clearly than English prose, particularly if the data definition is complex, e.g., an itemization data consisting of various mutually recursive compound data.
For example, the Xexpr definition from the last bullet in the Data Definitions section may be difficult to understand when viewed in isolation. However, some concrete HTML examples more clearly explains each part of the data definition to anyone who has some web programming experience.
A data definition describes and names a set of values. A program then computes with those values via functions. To bridge the gap between data definitions and function implementations, we write templates.
We use the shape of the data to guide the shape of our code.
In a template, use a placeholder function name that indicates the kind of data. Note however, that this is not a good function name, so when writing actual functions, you should change it to something better for your particular program.
1.5.1 Template for Compound Data
- structs: The pieces of a struct value are extracted using the struct accessor functions, whose names have the form <struct name>-<field name>.
- fixed-size lists: A template for lists of known length uses first, second, etc. to extract the parts.
A template for compound data helps programmers take inventory, so they know what they have to work with while implementing a function.
Note, however, that it’s not necessary for a function to use all the data pieces assembled by the template.
In addition, if any of the subpieces are still compound or itemization data, include a call to that kind of data’s template function.
1.5.2 Template for Itemization Data
Creating separate global constants and predicate functions that distinguish between the choices often makes code clearer (and easier to revise later):
TrafficLightColor template, with distinguishing predicates
Note that define-struct automatically defines predicates that can identify an instance of that struct.
The order of the cond clauses should match the data defintion, and ideally the simplest-to-distinguish choice should come first.
; trafficguide-fn : TrafficGuide -> ??? (define (trafficguide-fn sh) (cond [(circle? sh) (... (circle-radius sh) ... (trafficlightcolor-fn (circle-color sh)) ...)] [(octagon? sh) (... (octagon-side sh) ...)]))
If any of the pieces are still compound or itemization data, then the template includes a call to that data’s template function. This way, we are reminded that a function should only perform one distinct task.
When the data definition has a self-reference, then there should be a self-reference in the template, i.e., a recursive call to the template function.
List of Ints Template
List of Attributes Template
Lay out the subpieces of data by calling the appropriate accessors.
For subpieces that are still compound/itemization data, call the template functions for those kinds of data.
When a compound/itemization subpiece is the same kind of data as the input, make a recursive call to the template function itself.
In summary, here are the (possible) outputs of the Data Design step.
The Data Design step defines all the data representations your program needs. The remaining steps describe how to implement a function that processes one of these kinds of data. Repeat all the remaining steps for each function required in your program.
A major goal of this course is to create readable programs. This famous quote comes from the Preface of the textbook SICP. In the words of Hal Abelson, programs must be written for people to read, and only incidentally for machines to execute
Unfortunately, code is inherently unreadable because:
it contains too many details,
and its primary purpose is to be executed by machines.
at a high level, omitting unnecessary details,
and with as little code as possible.
In summary, a Function Specification enables a reader to understand a program without looking at the implementation.
Nearly all programming languages support some form of signature specification. Some languages require annotating a function with statically checked types (e.g., Java, C++, OCaml). Other languages make use of runtime contracts.
Since different type and contract systems have varying degrees of expressiveness, to avoid this technical complexity, and to remain language agnostic, in this course we write a function’s signature as a comment. The signature begins with the function’s name, followed by a colon, followed by the kinds of input data, followed by an arrow, and finally ending with the kind of output data.
MouseEvent handler signature
; mouse-handler : World MouseEvent Coordinate Coordinate -> World (define (mouse-handler w mev x y) ...)
Note: In this course, we assume that a function will only receive input values that are allowed by its signature (and argument invariants). Thus, it’s not necessary to check for invalid inputs and throw errors.
MouseEvent handler purpose statement
; mouse-handler : World MouseEvent Coordinate Coordinate -> World ; Computes the next World state based on the current World w, ; and a MouseEvent mev at coordinate (x,y). (define (mouse-handler w mev x y) ...)
As with Data Invariants, we use argument invariants when necessary to further restrict the kinds of data that a function can consume and produce.
An argument invariant accompanies a function’s purpose statement and typically specifies a relation between a function’s arguments.
See also the note in the Signature section about error checking.
; ring-area : Inches Inches -> Inches^2 ; Computes the area of the ring formed by concentric circles with ; radiuses r1 and r2. ; WHERE: r1 < r2 (define (ring-area r1 r2) ...)
A good use of function examples is to precisely describe any edge cases.
However, there’s no reason not to include any function examples in the program’s test suite. In this class, we use the begin-for-test form and Rackunit to define tests, so examples should be written using this framework as well. Don’t forget to label every test case with a string description.
; list-sum : ListOf<Natural> ListOf<Natural> -> ListOf<Natural> ; WHERE: (length lst1) == (length lst2) ; For each pair of corresponding numbers in lst1 and lst2, add them ; and return the results in a new list. (begin-for-test (check-equal? (list-sum empty empty) empty "empty lists") (check-equal? (list-sum (list 1 2 3) (list 4 5 6)) (list 5 7 9) "non-empty list")) (define (list-sum lst1 lst2) ...)
In general, each step in The Program Design Recipe provides more detail than the steps before it.
The Data Design step defines data representations without any idea of how they will be used or processed.
In this course, there are three design strategies, described below.
Every function you write should declare its strategy in a comment, prefixed by STRATEGY:.
A function employing the function composition strategy does not inspect subcomponents of its data. Instead, it merely passes the data on to be processed by other functions, and then combines the result of these function calls.
Note: Function composition is equivalent to the textbook’s notion of arithmetic.
However, function composition is frequently an appropriate strategy for processing compound or itemization data as well, particularly when you separate the function’s behavior into multiple, distinct tasks.
The data decomposition strategy extends function composition.
Specifically, a function that decomposes compound data first extracts and processes the subpieces of its input, utilizing the template for that kind of data to do so, and then combines those subresults using function composition.
A function that decomposes itemization data first distinguishes the possible choices via cond, utilizing that data’s template to do so, and then uses function composition in the right-hand side of each cond clause.
Since a function should only perform one distinct task, data decomposing functions should only decompose one kind of data.
A data decomposition function should be labled with both the kind of data it’s decomposing, and the variable representing that data.
data decomposition strategy
; trafficguide-fn : Trafficguide -> ??? ; STRATEGY: data decomposition on tg : TrafficGuide (define (trafficguide-fn tg) ...)
Generative recursion generalizes the data decomposition strategy.
See Generative Recursion for more details about generative recursion.
In summary, here are the components of the Function Specification step:
See the Function Specification section of the style guide for additional guidelines on how write a good function specification.
An overarching theme of this course is creating readable code. Unfortunately, code by definition is for computers to run and so is inherently not very pleasant for humans to read.
To address this, we avoid looking at code as much as possible. Thus, the first several of the The Program Design Recipe attempts to explain a function’s behavior without looking at code.
To have functioning programs, however, we must eventually implement code. But we can follow some guidelines to ensure the code is well-organized and as clear as possible.
The following tutorial presents more guidelines for implementing functions: How to Implement Functions
While Function Examples should be illustrative, to confirm that a program behaves as intended, all programs should have a more comprehensive test suite.
NOTE: Racket’s Beginner Languages have their own testing forms (e.g., check-expect, etc) that are separate from Rackunit . Do not use the Beginner Language testing forms in this course. Ask if you are confused about this.
We also make use of DrRacket’s code coverage tool to check that all parts of a program are at least somewhat tested. At a minimum, all programs should have 100% code coverage.
UPDATE : For Beginning Student and other beginner languages, the code coverage tool is enabled by default. When you run your program, untested code is highlighted in black. For full Racket (later in the semester), enable code coverage through the DrRacket "Choose Language" menu at the bottom-left: Choose Language -> The Racket Language -> Show Details -> Dynamic Properties -> Syntactic test suite coverage
Employ equivalence partitioning when testing your code. In other words, for a given function, think about how to divide its possible inputs into equivalent groups, and then write at least one test per group. During code walks, it’s very likely that we will ask what partitions you came up with for a particular function.
For example, say we want to write tests for the following function that computes the distance between two points:
(define PT1 (make-posn 1 2)) (define PT2 (make-posn 4 6)) (define PT3 (make-posn 2 4)) (define PT4 (make-posn 7 16)) (begin-for-test (check-equal? (dist PT1 PT2) 5 "positive differences") (check-equal? (dist PT3 PT4) 13 "positive differences"))
(check-equal? (dist PT1 PT3) (dist PT3 PT1) "order doesn't matter")
It’s not always obvious how many different partitions need to be tested. Sometimes, new partitions are only revealed after making a mistake.
As a second example, imagine we want to implement the function inside-circle?
wrong version of inside-circle?
; inside-circle? : Posn Pixels Posn -> Boolean ; Returns true if pt lies inside the circle represented by center and radius. ; STRATEGY: data decomposition on center, pt : Posn (define (inside-circle?.bad center radius pt) (and (< (abs (- (posn-x pt) (posn-x center))) radius) (< (abs (- (posn-y pt) (posn-y center))) radius)))
(The .bad prefix is just a flag for the reader. We will continue to use inside-circle? as the function name.)
This first version is wrong, but let’s see if testing can reveal the mistake.
On first glance, one might think that we only need two test partitions: a point inside the circle and a point outside the circle.
(define ORIGIN (make-posn 0 0)) (define PT50 (make-posn 5 0)) (define PT30 (make-posn 3 0)) (begin-for-tests (check-false (inside-circle? ORIGIN 4 PT50) "outside") (check-true (inside-circle? ORIGIN 4 PT30) "inside"))
However, our incorrect implementation passes both the tests.
A better test suite might additionally include the edge case where pt is on the circle’s border (which is not considered "inside" the circle).
(define PT40 (make-posn 4 0)) (check-false (inside-circle? ORIGIN 4 PT40) "on the border")
However, the incorrect implementation passes this test as well.
The first version of inside-circle? is wrong because it only computes if pt is inside the bounding box of the circle represented by center and radius. Thus, to reveal the error, we need a test where pt is outside the circle but inside the bounding box
(define PT33 (make-posn 3 3)) (check-false (inside-circle? ORIGIN 4 PT33) "outside, but inside bounding box")
Our incorrect first version of inside-circle? does not pass this test.
Here is a correct implementation of inside-circle?, which uses our dist function.
correct version of inside-circle?
This correct version passes all of our tests.
The lesson here is that it’s not always initially obvious how many partitions are needed. A test suite should include tests for any mistakes you made while coding (make note of any such tests, since you’ll probably be asked about them during code walks). A particularly thorough test suite may want to consider mistakes that may be made as well. Of course, no test suite can completely capture all possible inputs but considering possible mistakes and testing for them is the kind of reasoning we expect from good students.
A note on code coverage: Any single test would produce 100% coverage, according to DrRacket’s code coverage tool, for these functions. However, as demonstrated, one test is clearly an insufficient test suite. This is why we say that 100% test coverage is a minimum requirement.
A program is like an essay. The first version is a draft, and drafts demand editing. – How to Design Programs, second edition
The above quote from the textbook is a nice way of saying that the first version of anything is terrible and must be improved. Thus if you submit the first version of your homework assignment, expect to receive a comparably terrible grade.
Programming must be an iterative process. The last but crucial step of the design recipe requires looking back and improving the code you wrote.
You will be asked questions about your refactoring and improvements during your code walks. It may be a good idea to keep a journal as you complete each homework assignment, to better help you remember the rationale for your decisions.
In this step, you should check that your program meets all requirements, which may have changed since the last time you checked. This is extremely common in practice and in this course as well.
Or you may realize that some requirements are actually unclear or ambiguous. This is also extremely common in practice. If you think a requirement is unclear, you should ask your client (or in this course, the course staff) questions until things are clear. This is yet another reason why it’s important to start early on each assignment.
Names are vital if one wishes to write clear code. This includes functions, variables, and data definition names.
During the review step, review your names to make sure they are as clear and accurate as possible.
The design recipe requires you to write a lot of prose, for purpose statements, interpretations, comments, etc.
Like any piece of writing, you should be constantly updating these parts of your program so that they are as clear, precise, and accurate as possible.
Review data definitions and explore possible improvements. In particular, some data definition variations may make certain functions easier to implement and make other functions more complicated. You should constantly be thinking about such tradeoffs and be prepared to discuss them during your code walks.
Read this tutorial illustrates some guidelines for choosing between the different design stratgies: How to Implement Functions.
Always be on the lookout for repeated code. This will be addressed in more detail when we study lists.
code cleanup; remove extraneous code,
collapsing cond branches, when dealing with data like MouseEvents or KeyEvents.
Less important in this course, but important in practice, this is the step where you would review and profile the performance of your program, and explore optimizations.
This course does not focus on performance. We favor clean readable code over "optimized" solutions that are often a little too clever and difficult to understand. In general, you will not be penalized for performance except in extreme cases or where explicitly mentioned.
To summarize how you should view performance and optimization, we defer to those with more experience and expertise than us (as quoted in [EffectiveJava]):
"More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason—
including blind stupidity."
William A. Wulf. Proceedings of the 25th ACM National Conference 2. 1972.
"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil."
Donald E. Knuth. Computing Surveys 6. 1974.
- "We follow two rules in the matter of optimization:
M. A. Jackson. Principles of Program Design. 1975.
Rule 1. Don’t do it.
Rule 2 (for experts only). Don’t do it yet—
that is, not until you have a perfectly clear and unoptimized solution."
"Don’t sacrifice sound architectural principles for performance. Strive to write good programs rather than fast ones."
Joshua Bloch. [EffectiveJava].
This subsection supplements Part III of the textbook and describes one example of creating abstractions for common pieces of code. In some sense, the process of abstraction works backwards through the steps of the design recipe.
We start with the following code.
; A Name is a String with no spaces, representing a capitalized first Name. (define STEVE "Steve") (define DAN "Dan") (define RAHUL "Rahul") ; A ListOfName (LoN) is one of: ; - empty ; - (cons Name LoN) ; Represents a sequence of first names. (define STEVE-DAN-RAHUL (cons STEVE (cons DAN (cons RAHUL empty)))) ; TEMPLATE ; names-fn : ListOfName -> ??? (define (names-fn names) (cond [(empty? names) ...] [else (... (first names) ... (names-fn (rest names)) ...)])) ; A ListofImage (LoI) is one of: ; - empty ; - (cons Image LoI) ; Represents a sequence of 2htdp/image images. (define RED-CIRCLE (circle 5 "solid" "red")) (define BLUE-SQUARE (square 10 "outline" "blue")) (define BLACK-CIRCLE (circle 12 "solid" "black")) (define CIRCLE-SQUARE-CIRCLE (list RED-CIRCLE BLUE-SQUARE BLACK-CIRCLE)) ; TEMPLATE ; images-fn : ListOfImage -> ??? (define (images-fn imgs) (cond [(empty? imgs) ...] [else (... (first imgs) ... (images-fn (rest imgs)) ...)])) (define THE-FIRST "TheFirst") ; names-join : ListOfName -> Name ; Appends a list of Names together and adds the suffix "TheFirst" ; Strategy: data decomposition on names : ListOfString (define (names-join names) (cond [(empty? names) THE-FIRST] [else (string-append (first names) (names-join (rest names)))])) (begin-for-test (check-equal? (names-join empty) THE-FIRST) (check-equal? (names-join STEVE-DAN-RAHUL) (string-append STEVE DAN RAHUL THE-FIRST))) ; images-join : ListOfImage -> Image ; Appends a list of images together side-by-side. ; Strategy: data decomposition on imgs : ListOfImage (define (images-join imgs) (cond [(empty? imgs) empty-image] [else (beside (first imgs) (images-join (rest imgs)))])) (begin-for-test (check-equal? (images-join empty) empty-image) (check-equal? (images-join CIRCLE-SQUARE-CIRCLE) (beside RED-CIRCLE BLUE-SQUARE BLACK-CIRCLE)))
There are many commonalities between the two functions so we identify it as a candidate for abstraction.
; join : ??? ; Strategy: data decomposition on lst : ??? (define (join combine-fn mt lst) (cond [(empty? lst) mt] [else (combine-fn (first lst) (join combine-fn mt (rest lst)))])) ; ??? (define (names-join names) (join string-append THE-FIRST names)) ; ??? (define (images-join imgs) (join beside empty-image imgs))
If we abstract the common parts of ListOfName and ListOfImage, we get:
; A ListOf<X> is one of: ; - empty ; - (cons X ListOf<X>) ; Represents a sequence of X elements. ; list-fn : ListOf<X> -> ??? (define (list-fn lst) (cond [(empty? lst) ...] [else (... (first lst) ... (list-fn (rest lst)) ...)])) ; A ListOfName is a ListOf<Name> ; A ListOfImage is a ListOf<Image>
(Note that our syntax for a parameterized data definition deviates from the textbook.)
To use this parameterized data definition, we have to give it another data definition name. Here we’ve re-defined ListOfName and ListOfImage to use ListOf<X>. In fact, it’s no longer necessary to explicitly define ListOfName and ListOfImage and instead, ListOf<Name> and ListOf<Image> may be used directly in signatures and other data definitions.
Many other programming languages utilize parameterized data definitions, such as Java’s generics and C++ templates.
Now we may add function specifications to our abstracted functions.
; join : (X Y -> Y) Y ListOf<X> -> Y ; Iteratively applies combine-fn to an element of lst and an intermediate ; accumulated value, where mt is the initial accumulator. ; STRATEGY: data decomposition on lst : ListOf<X> (define (join combine-fn mt lst) (cond [(empty? lst) mt] [else (combine-fn (first lst) (join combine-fn mt (rest lst)))])) ; names-join : ListOf<Name> -> Name ; STRATEGY: function composition (define (names-join names) (join string-append THE-FIRST names)) ; images-join : ListOf<Image> -> Image ; STRATEGY: function composition (define (images-join imgs) (join beside empty-image imgs))
In the signature of join, the undefined X and Y are implicitly declared as parameters, in the same was that the X in ListOf<X> is a parameter. The X and Y are implicitly filled in on a call to join, with the concrete data definition name of join’s arguments. For example, when join is called in names-join, both the X and Y in join’s signature are implicitly replaced with Name.
Quiz: What is another name for the join function?
In general, functions should not be defined using local.
Functions should represent one precise task that makes sense regardless of context (i.e., the function should make sense regardless of who calls it).
Using local also makes testing and debugging of functions more difficult.
Thus most functions should be defined at the top-level. In general, you should avoid writing local functions.
Related to item 1, use local to leverage scope to cut down on the number of arguments passed around. Of course, you should only do this when it does not make your code more difficult to understand, but this can technique can often cut down on extraneous code.Here is an example, from exercise 245 in the textbook:
; A Name is a String that is capitalized and consists of only letters. ; prefix-of? : Name ListOf<Name> -> Boolean ; Returns true if nam is a prefix of any element of nams. ; Strategy: function composition (define (prefix-of? nam nams) (local ((define nam-length (string-length nam)) ; prefix-of-nam? : Name -> Boolean ; Returns true if nam is a prefix of n. ; Strategy: function composition (define (prefix-of-nam? n) (and (<= nam-length (string-length n)) (string=? nam (substring n 0 nam-length))))) (ormap prefix-of-nam? nams)))
When you have functions like this that operate as a group, the templates should be grouped as well.
When writing accumulator functions.
Functions defined via local must be accompanied by all the Function Specification requirements. You may occasionally omit examples, since local functions are typically small and are difficult to test. However, add informal examples when it helps explain the behavior of your function.
Define local constants when it would eliminate duplicate expressions and clean up your code.
In other words, the primary benefit of introducing local constants is readability, not performance.
Thus if the resulting code is not more concise and readable, do not introduce local constants.
In the prefix-of? example above, the only benefit of defining nam-length is to make the code more precise.
This means that local constants need especially good variable names. If a reader has to repeatedly refer back to the local definition, then the local definition has made your code worse.
This short section explains how to use accumulators in this course. (It supplements the guide in Chapter 37.2.)
Accumulators capture additional context information, typically in recursive functions.
Here is a concrete example. It’s the same invert example from the textbook.
; invert : ListOf<X> -> ListOf<X> ; Reverses the given list. ; Strategy: function composition (define (invert lst0) (local (; ListOf<X> ListOf<X> -> ListOf<X> ; Reverses lst onto rev-so-far. ; WHERE: rev-so-far is the elements of lst0 reversed so far, ; and lst is the elements of lst0 to be reversed. ; Strategy: data decomposition on lst : ListOf<X> (define (invert/a lst rev-so-far) (cond [(empty? lst) rev-so-far] [else (invert/a (rest lst) (cons (first lst) rev-so-far))]))) (invert/a lst0 '())))
Declare an internal accumulator-style function via local.
Name an internal accumulator-style function the same name as its outer function, except add a /a suffix (pronounced "with accumulator").
The internal function consumes the same inputs as the outer function, plus an accumulator argument. Give this argument an appropriately descriptive name.
The accumulator invariant must mention all the (typically three) arguments, including the accumulator, by name, and specify how these arguments are related.
The outer function should call the internal accumulator function with an initial accumulator value.
The strategy of the outer function is function composition while the strategy for the inner function is data decomposition on lst : ListOf<X>.
A local accumulator function may omit examples, so long as the outer function’s Function Specification sufficiently conveys this information.
; genrec-fn : Problem -> Solution ; Purpose statement ... ; Strategy: Generative Recursion ; TERMINATION ARGUMENT: ; 1) declares that the function always terminates and explains why, ; i.e., in what way the smaller problems are smaller ; 2) declares that the function may not terminate and gives examplse (define (genrec-fn problem) (cond [(trivial? problem) ...] ... [else (combine (genrec-fn (create-smaller-problem problem)) ...)]))
NOTE: Though it resembles a template, this is not a template in the same sense as you are used to at this point in the course, because this code is not following the shape of any data definition. This is merely a code skeleton intended to provide some guidance in writing generative recursive functions. In other words, you do not need to include this outline your other Data Design deliverables.
The recursion stops when the function encounters a trivially-solvable problem. Otherwise, the function recursively calls itself on smaller versions of the problem, and then combines the results.
A function utilizing generative recursion must additionally present a termination argument. A termination argument is considered part of the Function Specification step.
declares that the function always terminates and explains how by demonstrating that each recursive call operates on a smaller problem than the function’s inputs.
declares that the function may not terminate and gives example inputs that result in non-terminatation.
For the first case of terminating generative recursive functions, the meaning of "smaller" in the termination argument differs depending on each specific function.
For data decomposition, the smaller refers to the number of subpieces of data. That is why data-decomposing functions do not need termination arguments, because we know they always terminate.
evaluates to a natural number,
cannot be less than zero,
and always decreases on every recursive call
For example, the halting measure in quick-sort is the length of the list because the pivot is always excluded from the recursive calls:
; ListOf<Number> -> ListOf<Number> ; Sorts the given list of numbers in ascending order. ; Strategy: generative recursion ; Halting Measure: (length alon) always decreases (define (quick-sort alon) ...)
NOTE: A termination argument does not explain when a function terminates. For example, "the function terminates when the list lst is empty" is not a valid termination argument.
A termination argument explains how and why a function terminates. A valid termination argument could be "the list lst gets smaller on every recursive call", or simply "HALTING MEASURE: (length lst)".
Ask on Piazza if you still don’t understand the difference between stating when a function terminates, versus how and why it terminates.
Use the second termination argument alternative when a generative recursive function may loop forever. In this case, the termination argument should clearly state which function inputs cause non-termination. This is vital information for someone trying to read and understand the program. See the bundle in example in Chapter 29 for a concrete example.
A backtracking function is a kind of generative recursive function.
Thus, a backtracking function has the general shape of a typical generative recursive function, with a few differences:
; backtrack-fn : Problem -> Maybe<Solution> ; Purpose statement ... ; Strategy: Generative Recursion ; TERMINATION ARGUMENT: explain either ; 1) why the function terminates, i.e., in what way the smaller problems are smaller ; 2) when the function does not terminate (define (backtrack-fn problem) (cond [(trivial-or-fail? problem) ...] ... [else (local ((define result/#f (backtrack-fn (create-smaller-problem problem)))) (if (false? result/#f) (backtrack-fn (next-smaller-problem problem)) ; backtrack result/#f))]))
The function may fail to find a result, and thus returns a Maybe<X>.
In addition to the trivial cases, the first few cond clauses may also check for fail conditions.
The result of the recursive call must be checked and if no solution was found, the algorithm must undo some progress (i.e., backtrack), and then continue down a different path.
See Interfaces, objects, and dispatching document for object-oriented design guidelines.
Prior to using objects, we didnt have to worry much about how to test our programs. The check-equal? and other testing functions handled comparisons, including deep comparisons of compound (student langage) define-struct and list values, automatically.
However, a tradeoff cost that comes with the additional encapsulation introduced by classes and interfaces is that we no longer have immediate access to the data inside every object, so comparing objects via check-equal? or equal? is insufficient.
> (define Ball.v0% (class* object% () (init-field x ; x-axis Coordinate y ; y-axis Coordinate r) ; radius, in Pixels (super-new)))
> (define ball1 (new Ball.v0% [x 1][y 2][r 10]))
> (define ball2 (new Ball.v0% [x 1][y 2][r 10]))
> (equal? ball1 ball2)
> (equal? ball1 ball1)
Hence testing object-oriented programs requires a different approach.
> (define Ball.v1<%> (interface () ; testing:get-x : -> Coordinate ; Returns the x coordinate of the ball. testing:get-x ; testing:get-y : -> Coordinate ; Returns the y coordinate of the ball. testing:get-y))
> (define Ball.v1% (class* object% (Ball.v1<%>) (init-field x ; x-axis Coordinate y ; y-axis Coordinate r) ; radius, in Pixels ; testing:get-x : -> Coordinate (define/public (testing:get-x) x) ; testing:get-y : -> Coordinate (define/public (testing:get-y) y) (super-new)))
> (define ball1 (new Ball.v1% [x 10][y 20][r 100]))
> (define ball2 (new Ball.v1% [x 10][y 20][r 100]))
> (equal? ball1 ball2)
> (= (send ball1 testing:get-x) (send ball2 testing:get-x))
> (= (send ball1 testing:get-y) (send ball2 testing:get-y))
Note the testing: prefix for methods that are added to an interface for testing purposes only. See the OOP Style guide for other object-oriented style rules.
Note: Add testing: methods only as a last resort. You should prefer to test objects through their available public interface. In this demonstration example, there are no public methods so we add two accessor methods for testing.
A second option is to write your own comparison function.
; ball=? : Ball.v1<%> Ball.v1<%> -> Boolean ; Compares two ball objects for equality.
> (define (ball=? b1 b2) (and (= (send b1 testing:get-x) (send b2 testing:get-x)) (= (send b1 testing:get-y) (send b2 testing:get-y))))
> (ball=? ball1 ball2)
Note that now you must decide which parts of a ball should be included for the purposes of computing equality. Here we’ve decided to exclude the radius field. (A better name for this comparison function would be ball-location=?.)
A third option is to add a comparison method.
> (define Ball.v2<%> (interface () ; testing:get-x : -> Coordinate ; Returns the x coordinate of the ball. testing:get-x ; testing:get-y : -> Coordinate ; Returns the y coordinate of the ball. testing:get-y ; ball=? : Ball.v2<%> -> Boolean ; Returns true if the given ball is equivalent to this one. ball=?))
> (define Ball.v2% (class* object% (Ball.v2<%>) (init-field x ; x-axis Coordinate y) ; y-axis Coordinate ; testing:get-x : -> Coordinate (define/public (testing:get-x) x) ; testing:get-y : -> Coordinate (define/public (testing:get-y) y) ; ball=? : Ball.v2<%> -> Boolean (define/public (ball=? b) (and (= x (send b testing:get-x)) (= y (send b testing:get-y)))) (super-new)))
> (define ball1 (new Ball.v2% [x 10][y 20]))
> (define ball2 (new Ball.v2% [x 10][y 20]))
> (equal? ball1 ball2)
> (send ball1 ball=? ball2)
> (send ball2 ball=? ball1)
Thanks to Ankit for pointing out this option.
Implementing the equal<%> interface is similar you how you might implement object equality in other OO languages like Java. Similar to these other languages, you must implement all three methods such that if two objects are equivalent according to equal?, then they must return the same hash codes.
Like the other testing options, you should only implement equal<%> if you cannot fully test the functionality of your program through already-accessible interface methods.
> (define Ball.v3<%> (interface () ; testing:get-x : -> Coordinate ; Returns the x coordinate of the ball. testing:get-x ; testing:get-y : -> Coordinate ; Returns the y coordinate of the ball. testing:get-y))
> (define Ball.v3% (class* object% (Ball.v3<%> equal<%>) (init-field x ; x-axis Coordinate y) ; y-axis Coordinate ; testing:get-x : -> Coordinate (define/public (testing:get-x) x) ; testing:get-y : -> Coordinate (define/public (testing:get-y) y) ; required equal<%> methods — — — — — - ; use the recur parameter on nested objects; not needed here (define/public (equal-to? b recur) (and (= x (send b testing:get-x)) (= y (send b testing:get-y)))) (define/public (equal-hash-code-of recur) (equal-hash-code (list x y))) (define/public (equal-secondary-hash-code-of recur) (equal-secondary-hash-code (list x y))) (super-new)))
> (define ball1 (new Ball.v3% [x 10][y 20]))
> (define ball2 (new Ball.v3% [x 10][y 20]))
> (equal? ball1 ball2)
Regardless of which option you choose, the overarching lesson is that with objects, we must now put more thought into our testing strategy.
; using #lang racket > (define-struct opaque-ball (x y))
> (equal? (make-opaque-ball 1 2) (make-opaque-ball 1 2))
To define structs in full Racket that behave like student language structs, add a #:transparent tag to your define-struct definition.
; using #lang racket > (define-struct ball (x y) #:transparent)
> (equal? (make-ball 1 2) (make-ball 1 2))
Note: While reading the Racket documentation, you may stumble upon the (inspect false) form that "opens" objects in the same way that #:transparent opens structs. To practice good object-oriented programming, do not use this form.
Finally here is some additional material on testing objects.
Testing mutable objects is more involved than testing immutable objects because more effort is required to get the object into the proper state. Also, if you re-use objects between different tests, you must now pay attention to the order in which your tests appear. Testing frameworks for mutable objects in other languages must explicitly account for these setup and teardown phases.
With mutable objects, you can’t simply chain together constructor and method calls. You must first create the object, giving it a name, and then sequentially send a series of method calls. However, be careful when reusing this object in subsequent tests since it’s no longer in its initial state. This complication is yet another reason why programs should strive to use as little mutation as possible.
> (define Ball<%> (interface () ; tick! : -> Void ; EFFECT: Moves this ball horizontally to the right by 3 pixels ; and changes it color every 5th tick. tick! ; get-color : -> Color ; Returns the color of this ball. get-color ; get-x : -> Coordinate ; Returns the x coordinate of this ball. get-x))
; Represents a horizontally moving ball that changes between red and green ; on every 5th tick.
> (define Ball% (class* object% (Ball<%>) (super-new) (init-field x) ; Coordinate (field [X-VEL 3] ; Pixels/tick [COLOR-CHANGE-FREQ 4] [color "green"] ; Color [color-countdown ; Natural between [0,5), Represents ticks until color change COLOR-CHANGE-FREQ]) ; toggle-color! : -> Void ; EFFECT: toggles the color of this ball between red and green. (define (switch-color!) (set! color-countdown COLOR-CHANGE-FREQ) (if (string=? color "green") (set! color "red") (set! color "green"))) ; tick! : -> Void (define/public (tick!) (set! x (+ x X-VEL)) (if (zero? color-countdown) (switch-color!) (set! color-countdown (sub1 color-countdown)))) ; get-color : -> Color (define/public (get-color) color) ; get-x : -> Coordinate (define/public (get-x) x)))
> (define b (new Ball% [x 10]))
> (check-equal? (send b get-x) 10 "initial x coordinate")
> (check-equal? (send b get-color) "green" "initial color")
> (send b tick!)
> (check-equal? (send b get-x) 13 "x coordinate after 1 tick")
> (check-equal? (send b get-color) "red" "oops")
location: (eval 40 0 40 1)
expression: (check-equal? (send b get-color) "red")
> (check-equal? (send b get-color) "green" "color doesnt change after 1 tick")
> (send b tick!)
> (send b tick!)
> (send b tick!)
> (check-equal? (send b get-x) 22 "x coord after 4 ticks")
> (check-equal? (send b get-color) "green" "right before color change")
> (send b tick!)
> (check-equal? (send b get-color) "red" "color changed on 5th tick")
> (send b tick!)
> (send b tick!)
> (send b tick!)
> (send b tick!)
> (check-equal? (send b get-color) "green" "color changed back to green --- oops it didnt")
location: (eval 53 0 53 1)
expression: (check-equal? (send b get-color) "green")
message: "color changed back to green --- oops it didnt"
> (send b tick!)
> (check-equal? (send b get-color) "green" "color changed back to green")
(begin-for-test (let ([b (new Ball% [x 10])]) (send b tick!) (check-equal? (send b get-x) 13) ...))
Here are some additional slides on testing mutable objects.