Homework 4: Object-oriented languages and Haskell
| Assigned: | 2007-02-20 |
| Due: | 2007-02-27 in class |
| Optional: | yes |
This homework assignment is optional, but recommended: It helps you learn the concepts, helps you discover if there is anything you don't understand, and is a good way to prepare for the midterm and final exams. If you turn the homework in by the due date, the TA will check your answers and give feedback.
1. Object models
What are the conceptual differences between Smalltalk's object model and Java's?
2. Polymorphism
2.1
In Java, what kind of polymorphism is used for the arguments to a method in Java?
2.2
In Java, what kind of polymorphism is used for the object on which a method is called?
2.3
Imagine a language Java* where the kind of polymorphism used for the object on which a method is called is also used for the arguments to the method. Construct an example (clean, compiling Java code) that would produce different results in Java and Java*.
3. Tree enumeration
The following defines the type BinaryTree and three example trees:
data BinaryTree
= InternalNode BinaryTree BinaryTree
| LeafNode String
deriving Show
t1 :: BinaryTree
t1 = LeafNode "Foo"
t2 :: BinaryTree
t2 = InternalNode (LeafNode "Foo") (LeafNode "Bar")
t3 :: BinaryTree
t3 = InternalNode (InternalNode (LeafNode "Foo") (LeafNode "Bar"))
(InternalNode (LeafNode "Baz") (LeafNode "Quuz"))
3.1. Visualization
Draw the three trees (t1, t2, and t3).
3.2. Code
Write a function enumerateTree :: Int -> BinaryTree -> [(Int, String)] that traverses the tree (preorder) and enumerate the leafnodes. The first argument is the number to give the leftmost leaf of the tree; the second argument is the tree to enumerate.
Your function should produce a list of (Int, String) pairs. Each pair consists of a unique number and the label of a leaf node. The returned list should be in reverse order (i.e., the rightmost leaf should be first in the list and the leftmost leaf should be last).
For instance, the three sample trees should be enumerated as follows:
enumerateTree 1 t1 = [(1,"Foo")] enumerateTree 1 t2 = [(2,"Bar"),(1,"Foo")] enumerateTree 1 t3 = [(4,"Quuz"),(3,"Baz"),(2,"Bar"),(1,"Foo")]
Hints: There are two cases: Leaf nodes (easy) and internal nodes (more difficult). To enumerate the tree rooted in an internal node, first enumerate the left subtree (by a recursive call to enumerateTreeenumerateTree when you call it to enumerate the right subtree. Concatenate the two lists with ++. You may find it useful to use local definitions (where).
This question is relevant to the project: You can use a similar technique to generate unique labels, which you will need to generate Inter code for loops and conditionals.
4. Symbol tables
4.1. Global symbol table
Design a data structure for the global symbol table of your Epsilon compiler. For each global variable, the table should contain the name and the memory location of the variable. For each procedure or function, the table should contain the name, a flag saying whether it is a procedure or a function, and the number and types of its arguments.
Write a Haskell type definition for your data structure, and give two example symbol tables as Haskell code.
Hint: The structure will probably be a list.
4.2. Local symbol table
The local symbol table contains the parameters and local variables of a function or procedure. Design a data structure for the local symbol table. Write a Haksell type definition for it. Give two example symbol tables as Haskell code.
4.3. Combining the symbol tables.
Extend your global symbol table so that the entry for a procedure or function also contains a reference to the local symbol table of that procedure or function.
4.4. Lookup functions
Write a lookup function that, given any symbol table (global or local) returns the memory location of a variable by a given name. In addition to the address, your function will need to return a flag saying whether the address is absolute (for global variables) or relative to the base address (for parameters and local variables).