Homework #13

This problem requires Lecture 10, Lecture 11, and book section 2.2.

If you are using mzscheme, make sure to add the following line to your code:

(load "/users/ta/cs330ta/eopl.scm")

Part A - (20 minutes)
The implementation of bintree in Section 2.2.1 does not include empty trees. Extend the definition of bintree to support empty trees. Modify the leaf-sum function on page 46 as well to handle this new variant. Make sure to test your code by building your own test trees both with and without empty trees and testing your leaf-sum code on them.

(define-datatype bintree bintree?
	(leaf-node
		(datum number?))
	(interior-node
		(key symbol?)
		(left bintree?)
		(right bintree?)))

(define leaf-sum
	(lambda (tree)
		(cases bintree tree
			(leaf-node (datum) datum)
			(interior-node (key left right)
				(+ (leaf-sum left) (leaf-sum right))))))

Note: Remember that an empty tree has no fields: (define my-empty-tree (empty-tree))

MAKE SURE TO NAME YOUR VARIANTS: empty-tree, leaf-node, and interior-node
MAKE SURE TO NAME YOUR FUNCTION: leaf-sum

Part B - Exercise 2.6, p.50 - (10 minutes)
Draw the abstract syntax tree for the lambda caluculus expression:
((lambda (a) (a b)) c)

This exercise will help you better understand abstract syntax trees. Instead of drawing the tree, make your tree as a collection of abstract syntax records as described on page 48. For example, the tree for (lambda (x) x) would be

(define my-tree (lambda-exp 'x (var-exp 'x)))

You must use the following datatype which is defined on page 48 (i.e.: copy this into your homework file):

(define-datatype expression expression?
(var-exp (id symbol?))
(lambda-exp (id symbol?)(body expression?))
(app-exp (rator expression?)(rand expression?)))

YOU MUST STORE YOUR TREE IN A VARIABLE CALLED: my-tree

You must log in first before submitting homework assignments.

Instructions on submitting homework is here

Last updated at 2:02 pm on Monday, February 28, 2005.