Problem Set 4

Due date: 10/14

Purpose:

The goal of this problem set is to practice the structural design recipe, plus function composition.

Drill:

Solve all problems in chapter 16.

Required Problems:

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, a subset of S-expressions: 

   Xexpr is one of: 
   -- (cons Symbol (cons LOA Xbody))
   -- (cons Symbol Xbody)

   Xbody is one of: 
   -- empty
   -- (cons String Xbody)
   -- (cons Xexpr Xbody)

   LOA is one of: 
   -- empty 
   -- (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. 
|#
```
X-expressions are used to represent XML information within the BSL and ISL languages.
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 (require "more-io.ss") to your program. Don't forget to commit the teachpack to the SVN repository.

Here is a sample XML piece:
```
	<week>
	 <assignment> 
	  hello
	  <syllabus week="2" src="sample2.xml" />
	  <syllabus week="1" src="sample1.xml">
	   world
	  </syllabus>
	 </assignment>
	 done
	</week>
```
Represent it as an X-expression to practice your data representation skills.

Your task is to design four functions:
1. 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 the file.
2. xexpr-find, which consumes an X-expression and produces the list of all the values of src attributes.
3. 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.
4. xexpr-depth, which consumes an X-expression and determines its depth.
You should notice that two of the functions are one-line definitions, if you use function composition to define them.
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 must create a simpler file than this.
Design a Universe program that graphically illustrates a push-down automata ("stack machine") for accepting strings containing "(", "[", ")", and "]" 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 between. Thus,
```
[define (f (x 10) y) a]
```
is balanced but
```
[define (f (x 10) y] a]
```
is not due to the closing bracket.

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'' program.
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.