Due date: 10/14
The goal of this problem set is to practice the structural design recipe,
plus function composition.
Solve all problems in chapter 16.
Note: You may use DrScheme's HtDP Intermediate Student
Language or Beginning Student Language with List Abbreviations.
- Recall the definition of X-expressions from class:
X-expressions are used to represent XML information within the BSL and ISL
#| X-expressions, a subset of S-expressions:
Xexpr is one of:
-- (cons Symbol (cons LOA Xbody))
-- (cons Symbol Xbody)
Xbody is one of:
-- (cons String Xbody)
-- (cons Xexpr Xbody)
LOA is one of:
-- (cons (list Symbol String) LOA)
Note: (list Symbol String) is called an Attribute.
Furthermore, (list 'a "some text") is called an a-Attribute
and "some text" is its value.
The teachpack more-io.ss provides the function
read-xexpr for reading an entire XML files as an
X-expression. To use the teachpack, save it in the SVN
directory for problem set 4, and add
to your program. Don't forget to commit the teachpack to the SVN
Here is a sample XML piece:
Represent it as an X-expression to practice your data representation
<syllabus week="2" src="sample2.xml" />
<syllabus week="1" src="sample1.xml">
Your task is to design four functions:
You should notice that two of the functions are one-line definitions, if
you use function composition to define them.
find-srcs, which consumes the name of an XML file (a file
whose extension is .xml and whose content is an XML expression; see
sample.xml) and produces the list of all the values of src attributes in
xexpr-find, which consumes an X-expression and produces the
list of all the values of src attributes.
file-depth, which determines the depth, also called
complexity, of the XML in the file of the given name.
If you have at most one start tag per line and if you indent one more
space every time you use an open tag without closing preceding tags, the
depth of a piece of XML is the maximal number of spaces between a tag and
the left border.
xexpr-depth, which consumes an X-expression and determines
For your entertainment, this assignment comes with the XML file
sample.xml, which stores information about the
third week of your course. You may use it to
run your program (not test). For testing, you
create a simpler file than this.
Design a Universe program that graphically illustrates a push-down
automata ("stack machine") for accepting strings containing
in a balanced shape. Balanced means of course that every
"(" is matched by
")", and every
"[" is matched by
"]", ignoring all characters (keystrokes) that come in
is balanced but
[define (f (x 10) y) a]
is not due to the closing bracket.
[define (f (x 10) y] a]
Display the initial state as a 100 by 100 white rectangle. Once your
program has seen left parentheses and (this means "one
or the other") brackets, it should display a 100 x
100 yellow rectangle. It sticks with yellow until all opening parentheses
and brackets are matched. After the first opening parentheses or bracket
is matched, the program display a green square and goes into a final
state. As soon as it discovers an unbalanced closing parenthesis or
bracket, the program displays a red rectangle of 100 by 100 pixels and
also goes into a final state.
In contrast to a finite-state machine, a stack machine's finite number of
"base states" come with a stack. In other words, the
machine really has an infinite number of states---base states combined
with an infinite variety of stacks---and each transition may change the
base state and/or the stack. Also recall that such a stack is a sequence
of letters in the input alphabet (parentheses and brackets in this
case). As you should know from your undergraduate days, you can push an
element onto the front of a stack, look at the front of a stack, and pop a
stack. Use lists to represent the stacks that come with each
state. Optionally, display the stack as a piece of text
with the colored rectangles that represent the basic state.
Tetris was a popular computer game. Your company's manager is thinking of a
revival edition and suggests to start with a simple ``block world''
In the ``block world'' scenario, a block drops down from the top
of the computer canvas---at a steady rate---until it lands on the ground
or on blocks that have landed before. A player can steer the dropping
block with the ``left'' and ``right'' arrow keys. Once blocks land on the
floor of the canvas or on top of some already resting block, they come to
rest. In a short time, the blocks stack up and, if a stack of blocks
reaches the ceiling of the canvas, the game is over. The objective of this
game is to land as many blocks as possible.
The three screen shots illustrate the idea. In the left one, you can see how
one block (on the left) has no support; it is falling. In the
right one, the block has landed on the ground. Finally, an additional block has
landed on top of the stack in the center of the canvas. This stack now
reaches the top of the canvas, which means that the game is over.
Hints: A state should always combine the stacks of blocks on the ground
and the currently dropping block. (If this is the case, one of the above
screen shots doesn't render a state. Which one?) For the stacks, the
minimum you need to know is how tall they are. Finally, you may consider
adapting the physics approach of thinking of all moving objects as a "dot"
and nothing else. Of course, you should render these "dots" in a suitable
way so that the game is playable.