Assignment 2. CS330 Programming Languages, Spring 2004 

PLEASE READ CAREFULLY
MISSING DETAILS MAY COST YOU

Details

A random 25% of students will be orally interviewed by me in person
regarding their submission. Make sure you have written everything you
submit. For any function you are trying to write, you can request
what is the desired output for a particular input by email. Solve the parts
of the assignment in the order they are given as they get progressively harder.
If you are stuck somewhere move to the next part and come back later.

Late assignment policy:  If the assignment is submitted
within three days from when it was due, you will get half the grade you
would get if you had submitted on time. You will not be able
to submit after three days. (exceptions to this rule only
if you have a VERY important reason).

IMPORTANT: The careful design and documentation (i.e comments) of
your code will be important factors in your grade. If there is a bug
it's better to report it than hide it. Be honest, precise and clear and
you shall be rewarded. NEVER (at least in this class) sacrifice
clarity for efficiency of execution.

(10% of final grade - 10 points)

Part 1. Support functions (2) 

In this section, define functions that you are going to find
helpful in the other parts of the assignment. For all functions, cover all
possible cases and raise exceptions when appropriate.

1a) Define a function nth(l,n) that returns the nth item of a list.
For example nth([1,2,3,4], 0) is 1 and nth([1,2,3,4], 3) is 4
and nth(["one", "two", "three"], 2) is "three". This function
should raise an exception named Subscript when the index is out of bounds.

1b) Define a function copy(n,ls) that returns a list of n repetitions of ls.
For example the result of copy(4,[1,2,3]) is [1,2,3,1,2,3,1,2,3,1,2,3]

1c)  Define a function scan f b l that returns the list
[b, f(b,l1),f(f(b,l1), l2), ....]. For example:

scan op+ 0 [1,2,3,4,5]                              is                 [0,1,3,6,10,15]
scan (fn(x,y) => x+2*y) 5  [1,2,3,4,5]      is                [5,7,11,17,25,35]

Scan is very similar to the foldl, foldr functions. The difference
is that it stores all the intermediate results in a list.

1d) Write functions minl and maxl which return the minimum and
maximum element of an integer list.  Write function tabulate(i,j) that returns the list of
integers from i to j. For example tabulate(2,8) is [2,3,4,5,6,7,8]

1f) Write a function member ls x that returns true if x is in the list ls.
For example member [1,2,3,4] 3 is true while
member [1,2,3,4] 5 is false.

1g) Write a function filter p l that takes as input a predicate p
and returns a list with the elements for which the predicate is true.

For example:
filter (fn x => x > 3) [1,2,3,4,5] is [4,5]

Part 2. Converting numbers to words  (2)

Write a function num2string that converts numbers less than a million
to words using the convention illustrated with the following examples:

308000 -> three hundred and eight thousand
369027 -> three hundred and sixty-nine thousand and twenty-seven
369401 -> three hundred and sixty-nine thousand four hundred and one
300000 -> three hundred thousand
Notice the use of "-" and "and".

Hints:
Use the following lists:

val units = ["one", "two", "three", "four", "five",
"six", "seven", "eight", "nine"];

val teens = ["ten", "eleven", "twelve", "thirteen",
             "fourteen", "fifteen", "sixteen", "seventeen",
             "eighteen", "nineteen"];

val tens = ["twenty", "thirty", "forty", "fifty",
            "sixty", "seventy", "eighty", "ninety"];


First try writing a function that converts
a number to a list of words for 0<n<100.
Next, write a function that uses your solution for
0<n<100 to handle 0<n<1000 and finally
extend your solutions to handle 0<n<1000000.
Use pattern matching rather than if statements
to make your code more understandable.

Use the function nth you defined in part I.
If you were not able to write nth you can
use List.nth but you will loose points.

Here is an example of how I will test your program:

val in_test1 = [0, 5, 14, 33, 91, 120, 777, 1000, 10000, 111111, 369461];
val out_test1 = map num2string in_test1;

with result:
val out_test1 =
  ["zero","five","fourteen","thirty-three","ninety-one",
   "one hundred and twenty","seven hundred and seventy-seven","one thousand",
   "ten thousand","one hundred and eleven thousand one hundred and eleven",
   "three hundred and sixty-nine thousand four hundred and sixty-one"]
  : string list


Part 3 Polynomial multiplication (2) 

We rerpesent the polynomial a0 + a1 * x + ..... + an x^n with integer
coefficients a0, a1, ...., an by the list [a0,...,an]. For instance the polynomial
x^3 + 2 is represented by the list [2,0,0,1].

2a) Declare an SML function for multiplying a polynomial by a constant
2b) Declare an SML function for multiplying a polynomial Q(x) by x
2c) Declare infix SML functions for addition and multiplication of
polynomials in the chosen representation. The following recursion formula
is useful when defining multiplication:

0 * Q(x) = 0
(a0 + a1 * x + ... + an * xn) * Q(x) = a0 * Q(x) + x (a1 + a2 * x + .... + an * x^(n-1) * Q(x))

2d) Declare an SML function to give a textual representation for a polynomial.



Part 4 Turtle graphics (4)

Some of you maybe be familiar with the language Logo that is based on manipulating
a so-called turtle for creating graphics. In this part of the assignment we will try to model
the interaction with a turtle. This is the hardest part of the assignment and will show how
one can model state using a functional language. DO NOT use
recursion to define the functions in this part. You must only use the functions
defined in Part 1 and the higher-order functions foldl, map. If you use recursion
you will loose one point.

Consider a device (called a 'turtle') which can move around a potentially infinite rectangular
grid. At any one moment, the turtle is at some grid point and is oriented in one of four directions:
East, South, West, North coded as 0, 1, 2, 3. The turtle is equipped with a pen which can either
be in the 'up' or 'down'  position. When the pen is down, each grid point that the turtle passes
over is marked; when the pen is up the turtle is up and it moves without leaving a trail.

The commands which can be issued to the turtle are of three kinds:

1) To turn, either one position to the left or to the right.
2) To move one step along the grid in the direction currently indicated
3) To put the pen up or down

A turtle state consists of a current direction (int), a pen position (bool) and a point on the grid (int * int).
A turtle command is a function from states to states. Each command will be modeled as a function
that takes as input the current turtle state and returns the changed turtle state.

For example, wherever the turtle happens to be initially, the following sequence of commands
causes it to trace the perimeter of a square of side k and return to its starting point:

fun square k = let val side = copy(k-1,[move])@[right]
               in [down] @ copy(4,side) @ [up] end;

The function turtle takes a sequence of commands and returns a sequence of states. Assume the
turtle always starts off at the origin facing East with its pen in the up position.

The remaining task is to define a function for drawing a turtle trail. A trail is a list of coordinate
points visited by the turtle while the pen is down. Write a function trail that takes a list of states
and returns a list of points marked by the turtle (when the pen is down). Write a function picture
that converts the trail into a two-dimensional boolean array (a bitmap). The size of the bitmap
is determined by looking at the minimum and maximum values of the x-coordinates and y-coordinates
of the trail left by the turtle. Write a function symbolize that converts a bitmap of type bool list list
to type char list list for a specific mapping of boolean values to characters. Write a function
layout that converts the two dimensional array (represented by a list of lists) of characters
to a string with newlines separating each row. Now you are ready to program the turtle.

Use the built in function print to print the string result to the screen.

For example if I define:
fun printTurtle p = (print o layout o symbolize o bitmap o trail o turtle) p;
where p is a list of commands.
I can do (with symbolize with true -> o, false -> *):

printTurtle(square(4));
oooo
o**o
o**o
oooo
val it = () : unit

or with a different symbolize (true -> o, false-> space)

printTurtle([down,move, move,move,move,right,move,move,right,move])
ooooo
        o
      oo

and
printTurtle([down,move,move,move,move,left,move,move,left, move]);
      oo
        o
ooooo
val it = () : unit

Extra credit 

1) Make a cool picture using the turtle graphics program you developed. The best
pictures will get  (1 extra point)

2) Generate postscript output for the turtle pictures. You will have to find
yourselves how to do this but basically it's simple text output with the right
postscript commands. (2 extra points)