CSC 424: Programming Languages, Spring 2006

Assignments

Friday, February 3:

Chapter 2, Exercise 1 (b, d, f, h, j, l)

Monday, February 13:

Chapter 5, Exercises 2, 4, 6, 8, and 10

Wednesday, February 22:

Chapter 7, Exercises 2, 3, 6, and 8-11

Programming Project 1 (ML), due Friday, March 10:

(Based on Exercises 11 and 12 of Chapter 11) Implement a binary search tree in ML. You will need to fill in the functions create, traverse, and search in the following structure:

signature SEARCH = sig
  type 'a collection;
  val create : ('a * 'a -> order) -> 'a list -> 'a collection;
  val traverse : 'a collection -> 'a list;
  val search : ('a * 'a -> order) -> 'a collection -> 'a -> bool;
end;

structure BinarySearch : SEARCH = struct
  datatype 'a tree = Empty | Node of 'a tree * 'a * 'a tree;
  type 'a collection = 'a tree;
  
  fun create (* construct a binary search tree from the given list and compare function *)
  
  fun traverse (* return the items from the BST as a list using an inorder traversal *)
  
  fun search (* perform a binary search for the given item using the provided compare *)
  
end;
				

As discussed in class, you should be able to use this structure to create a sorting method. In the file I:\CSC424\public\search.sml you will find a number of structures and functors to help you test your code. The easiest thing will probably be to edit your BinarySearch structure into your own copy of this file, then use that file from SML/NJ. Following the example from the comment at the bottom of the file, you can do the following to test your code:

structure T = TestSearch(BinarySearch);
T.test();
structure U = TestSort(SearchSort(BinarySearch));
U.test();
				

Each of the test functions should return true (and it should run considerably faster than the corresponding test for LinearSearch). The first test checks that you can construct a collection of 20,000 "random" data items and successfully identify one element that is and one that is not in the collection. The second test checks that the sorting method created from your search structure correctly sorts that list of 20,000 items.

When testing your code, you may find that you need to see more elements in a list or a tree than SML/NJ wants to print (at some point, it stops printing "large" structures and just prints "..."). Doing the following at the SML/NJ prompt will set the limits to something more reasonable:

Control.Print.printLength := 100;
Control.Print.printDepth := 20;
				

Monday, April 3:

Read Moving Toward Object-Oriented Programming and Patterns and Elementary Patterns: Strategy, Decorator, and Composite

Wednesday, April 5:

Chapter 16, Exercise 2

Programming Project 2 (Java), due Friday, April 21:

Complete the BASIC compiler in I:/CSC424/public/JSimpLan2. The package edu.depauw.csc424.basic (and subpackages ast and parser) contains a skeleton of a compiler for a subset of BASIC, the Beginner's All-Purpose Symbolic Instruction Code. You will be extending a fairly complex framework, so most of the assignment will be discussed in class. You can look at the simplan package for an example of a compiler for a C++-like language.

Here is an informal description of the statements you should implement:

• LET <var> = <expr>
• GOTO <label>
• IF <expr> THEN <label>
• IF <expr> THEN <statement>
• FOR <var> = <expr> TO <expr>
• NEXT <var>
• INPUT <var>
• PRINT <itemList>

A program consists of a sequence of statements, one per line, each one optionally preceded by a numeric label. In the PRINT statement, an <itemList> is a comma-separated list of zero or more <expr>s and string literals (in quotes). Here is a simple example:

10 PRINT "Enter two distinct numbers, A and B"
   PRINT "A?"
   INPUT A
   PRINT "B?"
   INPUT B
   IF A = B THEN 10
   IF A > B THEN 99
   FOR I = A TO B
     PRINT I, "squared is", I * I
   NEXT I
99 PRINT "Done"
				

Monday, May 1:

Chapter 19, Exercises 1, 3, 5, 7, 9, 15-19 (recall the Chapter 7 homework)

DePauw University, Computer Science Department, Spring 2006
Maintained by Brian Howard (bhoward@depauw.edu). Last updated