CS 515 Fall 2005 Type Homework

#1.a. Our simple language type inference rules handout does not
specify type rules for the common arithmetic expressions.  In class we
talked about type rules that would allow integer arguments to be
coerced into float arguments where necessary (e.g., in arithmetic
expressions.  Write the rules for correct typing of mixed type
arithmetic expressions for the operators +, -, * and /.

b. Using the rules you constructed in #a, show that if we take a list
of pairs whose elements are either floats or integers, then we can form
a new list of floats by summing each pair to yield the corresponding
element in the new list.  For example, [(1.0,2.5), (3,5), (4.5,5.0)]
would yield the list [3.5,8.0,9.5]. 

Call this operation sumList(L) where L is a list of these pairs. Write
the sequence of typing rules needed to show sumList is well-typed,
given the assumptions on the types of elements in L.

c. Assume we want to add a ROUND operation to our language such that
ROUND takes a float operand to its rounded integer value. Give a typing
rule for ROUND.

d. Our project language allows overloading of the + operator. When it
has string operands it means "concatenation" and when it has numerical
operands it means "add".  Does this introduce a complication in our
typing rules? Why or why not?

#2. ASU #6.21, 6.26

Prolem 6.26 is another type reconstruction problem, like the
polymorphic list length fucntion we did in class.  You can 
think of the function "map" as defined in Scheme (see below) or use
the book's version as coded in SML.  map takes 2 arguments, a function f and 
a list x, and it returns the list consisting of f applied to each element of x.

(define (map f x) (cond ((null x) nil)
			(#t cons (f (car x)) (map f (cdr x)))))