2 Some More Design, Some More Racket
Let us work through one more exercises to see how the design recipe works.
#lang racket
(require rackunit)
# —— — — — — — — — — — — — — — — — — — — — — — — — –
PROBLEM STATEMENT
A Russian doll is either a solid wooden figure or a
Russian doll encased in a hollow wooden dress. Each
dress has a distinct color.
Design a program that consumes the representation of a
Russian doll and counts how many layer wrap the ’core’
figure.
#
;; DATA DEFINITION
(struct dress (content) #:transparent)
;; A Russiandoll (RD) is one of:
;; – "wooden figure"
;; – (dress Russiandoll)
;; RD > Number
;; how many dresses are around the "wooden figure" in rd
;; given (dress (dress (dress (dress "wooden figure"))))
;; expect 4
(define (countdresses rd)
(cond
[(string? rd) 0]
[else ; (dress? rd)
(+
(countdresses (dresscontent rd))
1)]))
(checkequal? (countdresses (dress (dress (dress (dress "wooden figure"))))) 4)
(checkequal? (countdresses "woodern figure") 0)
Figure 5 isn’t about anything realistic. It is a finger exercise in a minimalistic representation of a naturally occurring nested piece of "information." The key is, however, that by carefully following the design recipe, the definition of the function itself is a matter of a few keystrokes. The question is whether/how to come up with these keystrokes.
2.1 Definition
The step from the template to the full definition is all about combing the values that the template expressions compute. Here are some basic ideas on how to go about that.
What are the answers for the nonrecursive cond clauses?
The examples should tell you which values you need here. If not, formulate appropriate examples and tests.
What do the selector expressions in the recursive clauses compute?
The data definitions tell you what kind of data these expressions extract and the interpretations of the data definitions tell you what this data represents.
What do the natural recursions compute?
Use the purpose statement of the function to determine what the value of the recursion means not how it computes this answer. If the purpose statement doesn't tell you the answer, improve the purpose statement.
How can you combine these values into the desired answer?
If you are stuck here, arrange the examples from the third step in a table. Place the given input in the first column and the desired output in the last column. In the intermediate columns enter the values of the selector expressions and the natural recursion(s). Add examples until you see a pattern emerge that suggests a ``combinator'' function.
Figure 6: How to turn the template into a function definition
In addition, keep in mind that you should design auxiliary functions when a function gets large. Conversely, keep functions small and the "combination" functions are natural candidates for separate helper functions. HtDP/2e has some additional guidelines on this topic.
Finally, on some occasions the “combinator” cannot be just a function. Because the arguments to functions are evaluated first – Racket is a callbyvalue language – you may have to create nested conditional expressions on occasion.
Work through the example in figure 7 using the questionanswer games for creating templates and function definitions.
#lang racket
(require rackunit)
# —— — — — — — — — — — — — — — — — — — — — — — — — –
PROBLEM STATEMENT
An arithmetic expression is either a number, a string
(representing a variable), an addition of two
arithmetic expressions, or a subtraction of two
arithmetic expressions. Design a function that
replaces some given string with the number 5 in an
arithmetic expression.
#
;; DATA DEFINITION
(struct plus (left right) #:transparent)
(struct subt (left right) #:transparent)
;; An AE is one of:
;; – number
;; – string
;; – (plus AE AE)
;; – (subt AE AE)
;; String AE > AE
;; eeplace all occurrences of string s with 5 in ae
(define (replace s ae)
(cond
[(number? ae) ae]
[(string? ae) (if (string=? s ae) 5 ae)]
[(plus? ae)
(plus (replace s (plusleft ae))
(replace s (plusright ae)))]
[else
(subt (replace s (subtleft ae))
(replace s (subtright ae)))]))
(checkequal? (replace "hari" 0) 0)
(checkequal? (replace "hari" "hari") 5)
(checkequal? (replace "hari" (plus 42 "hari")) (plus 42 5))
(checkequal? (replace "hari" (subt 42 "hari")) (subt 42 5))
;; the second cond line needs another test case:
(checkequal? (replace "matthias" (plus 42 "hari")) (plus 42 "hari"))
The example illustrates a first important point about programming languages, too. Instead of working through syntaxasstrings, a programming language researcher thinks of the syntax of a language as trees and of functions/programs that process a program as treewalking functions. This form of syntax is called abstract syntax tree (AST).
2.2 Lists are special structures
(cons 12 23)
The end of the list is a special token: empty also written as '().
Naturally, cons structures come with a predicate, cons?,
as does the special token empty, namely empty?. The only
unusual aspect of lists is that the cons selector names don’t
start with cons. Instead they are called first and
rest—
Traditionally the selectors for cons structures are known as car and cdr, and yes, these selectors are available in Racket. We will deal with proper lists whenever possible and ignore these two selectors therefore.
; A LON (list of numbers) is one of: ; – empty ; – (cons Number LON) ; A LOLON (list of list of numbers) is one of: ; – empty ; – (cons LON LOLON)




You will find that this kind of code repetition between the two cond clauses is common, and the version for plain lists almost always looks simpler than the one for nonempty lists.
Exercise: Racket is untyped so cons doesn’t have to be used with the linear list format, and Racketeers use cons in all kinds of ways, because it is convenient. See below.
2.3 Sexpressions and Other Nestings
; An Sexpression is one of: ; – Atom ; – LSexpression ; ; An LSexpression is one of: ; – empty ; – (cons Sexpression LSexpression) ; ; An Atom is ...
The definition also uses two interrelated data definitions, but still programming with Sexpressions isn’t any different from programming with arithmetic expressions or Russian dolls. The key is to create two interrelated templates that refer to each other where the data definitions refer to each other.
(define (stemplate s) (cond [(atom? s) ...] [else ... (lstemplate s) ...])) (define (lstemplate s) (cond [(empty? s) ...] [else ... (stemplate (first s)) ... (lstemplate (rest s)) ...]))
2.4 Quote and Quine
Well, Sexpressions are an extremely convenient representation for (extensible) languages. It is noteworthy here to say that the XML community discovered this fact some 50 years after the Lispers. What would the world know if they listened to Lispers instead of complaining about the parentheses?
The key to Sexpressions are three special notations for lists: quote (’), quasiquote (`), and unquote (,). There is more but these three ideas are a good start.
In addition, you need to know about one more atomic datatype: symbols. A symbol is a quote (’) form followed by keys other than these: ( ) , ` ’ and a few more.
'(html () (head () (title () "a first web page")) (body ((bgcolor "white")) "My first web page. Please admire it."))
'(a b (+ 1 2) c d)
`(a b ,(+ 1 2) c d)
For an example of how quasiquote and unquote work in functions, take a look at figure 8.
#lang racket
;; String String > Sexpression
(define (awebpage t stuff)
`(html ()
(head ()
(title () "A " ,t " web page"))
(body ((bgcolor "white"))
"My " ,stuff " web page. Please admire it.")))
(awebpage "first" "first")
(awebpage "second" "beautiful")
(awebpage "last" "final")