University of Virginia, Department of Computer Science
CS200: Computer Science, Spring 2002

Exam 2 Out: 5 April 2002
Due: Wednesday, 10 April 2002, 11:00AM

Work alone. You may not discuss these problems or anything else related to this course with anyone except for the course staff between receiving this exam and class Wednesday. You may send email to cs200-staff@cs.virginia.edu to ask for clarifications on what the questions mean.

Open book. You may use any books you want, lecture notes and slides, your notes, and problem sets. If you use anything other than the course books and notes, cite what you used. You may also use anything you find on the web, but you should cite your sources.

Open Computers. You may (and should) run DrScheme to develop your answers.

Answer well. Answer all 10 questions. Write and number your answers clearly. Only turn in the code you add or change. Staple the sheets you turn in and put your name on them. Full credit depends on the clarity and elegance of your answer, not just correctness. Your answers should be as short and simple as possible, but not simpler.

State and Mutation

1. After evaluating (define spair (cons 1 2)), we can draw spair as:

1 2

     Draw spair after then evaluating (set-car! spair spair).

2. Give a sequence of two Scheme expressions that would produce the global environment shown below after they are evaluated:




3. After evaluating the two expressions from the previous question, what one additional expression could you evaluate to make the environment look like:


Problem Classifications

For problems 4-6, classify each problem as decidable or undecidable. If the problem is undecidable, explain convincingly why there is no procedure that solves it. If the problem is decidable, further classify it as precisely as possible from in P, in NP, or not necessarily in NP. Be careful to specify how you measure the problem size. Support your answer with a convincing argument.

Two examples are shown to give you an idea of what a full credit answer requires.

Example 1. The Yabba Problem
Input: Code for a Scheme expression, P
Output: true if evaluating P prints out "Yabba!".
Answer. The Yabba problem is undecidable. If we had a procedure prints-yabba to solve it, we could solve the halting problem like this: 
(define (halts? P)
  (prints-yabba (list 'begin (remove-all-prints P) (print "Yabba!"))))
Corrected 9 April: was (not (prints-yabba (list 'begin (remove-all-prints P) (print "Yabba!")))) which solves the does-not-halt? problem (which is also undecidable) instead of the halt? problem.
where remove-all-prints is a procedure that removes all printing from a procedure, but doesn't change it otherwise. Since we know halts? is undecidable, prints-yabba must also be undecidable.
Example 2. The Minimum Difference Problem
Input: A number x and a list of one or more numbers lst.
Output: A number y such that y is in the list lst and the value of (abs (- x y)) is as small as the value of (abs (- x z)) for any z that is in the list lst

For example, (minimum-difference 3 (list 1 2 4 5)) evaluates to either 2 or 4 and (minimum-difference 3 (list 1 2 3 4 5)) evaluates to 3.

Answer. The Minimum Difference Problem is decidable. The size of the problem is the number of elements in the list of numbers. It is in P since we can solve it by trying each element of the list and comparing the different to the best one we have found so far. This is O(n) which is in P.
4. The Grammar Checking Problem
Input: A BNF grammar G and a string S
Output: true if S is a string in the language described by G, false if S is not a string in the language.

5. The Expression Equivalence Problem

Input: Two typed mini-Scheme (the language from classes 28 and 29) expressions, S and T
Output: true if S and T evaluate to the same value, false otherwise.

6. The Type Equivalence Problem

Input: Two typed mini-Scheme (the language from classes 28 and 29) expressions, S and T
Output: true if S and T have the same type, false otherwise.

Evaluators

For questions 7-10, you will modify the Typed Mini-Scheme evaluator from classes 28 and 29.

Typed Mini-Scheme does not support the begin special form. In questions 7 and 8, you will extend it to handle (begin expression1 expression2). The begin special form takes two expressions. It evaluates expression1 first, and then evaluates expression2. The value of the begin is the value of expression2. The type of the begin is the type of the expression2.

For the code you turn in for questions 7-10, make sure to clearly identify the code for each question. Don't include code from clueval.ss that you did not change at all, but remember to include all of your changes. If you are not able to get all the code working, you can still get substantial credit for these questions by explaining what you are trying to do, turning in the code you have written so far, and explaining what you think is going wrong.

Downloads:

7. Extend meval to evaluate begin special forms. After your changes, you should get the following interactions:

> (meval '(begin (+ 2 3) (+ 4 5)) the-global-environment)

9

> (meval '(begin (define x number 3) x) the-global-environment)

3

> (meval '(begin 3 (begin 4 5)) the-global-environment)

5

8. Extend typeof to check the type of begin special forms. After your changes, you should get the following interactions:

> (typeof '(begin 3 (begin 4 5)) the-global-environment)

(primitive-type number)

> (typeof '(begin (+ 3 +) 5) the-global-environment)

Type mismatch. Application (+ 3 +) parameter types are (Number x Number) -> (Number) x Number, should be Number x Number.

(primitive-type number)

Note: it is okay if (typeof '(begin (define x number 3) x) the-global-environment) does not work. Since typeof does not modify the environment, the x will not be defined in the second expression.

Up and Down

The evaluator in clueval.ss is based on the typed Mini-Scheme evaluator, expect it has been extended to allow new type definitions using (definetype Name Type). For example, (meval '(definetype color number) the-global-environment) defines a type named color that is represented by the primitive type Number.

Type definitions are handled in meval by: 

   ((type-definition? expr) (define-type! 
                              (type-definition-name expr)
                              (type-definition-type expr)
                              env)
We added these procedures to support type definitions: 
(define (type-definition? expr)
  (tagged-list? expr 'definetype))

(define (type-definition-name expr)
  (cadr expr))

(define (type-definition-type expr)
  (parse-type (caddr expr)))
The procedure define-type! is similar to define-variable!, except instead of associating a name with a type and a value, it associates a name with a type. We store type definitions in the same frame as variables, but distinguish them with a special type. Here is the code: 
(define (make-typedef-type) 
  (list 'typedef-type))

(define (typedef-type? type) 
  (tagged-list? type 'typedef-type))

(define (define-type! name type env)
  ;;; We put type definitions in the frame like variable definitions, but use
  ;;; the typedef type to distinguish them. 
  (set-car! env (cons (list name (make-typedef-type) type) (car env)))
  'ok)
The procedure teval takes an expression and checks the type of that expression in the global environment. If it type checks okay, it then evaluates that expression in the global environment: 
(define (teval expr)
  (let ((exptype (typeof expr the-global-environment)))
    (if (error-type? exptype)
	(error-type)
	(meval expr the-global-environment))))
The type definitions: 
(teval '(definetype seconds number))
(teval '(definetype meters number))
(teval '(definetype meters-per-second number))
(teval '(definetype mps meters-per-second))
define the seconds, meters and meters-per-second types that are each represented by a number, and the mps type that is represented by the abstract type meters-per-second.

After these evaluations, the global environment is:

> the-global-environment

(((mps (typedef-type) (abstract-type meters-per-second))
  (meters-per-second (typedef-type) (primitive-type number))
  (meters (typedef-type) (primitive-type number))
  (seconds (typedef-type) (primitive-type number))
  (+
   (procedure-type
      (product-type (primitive-type number) (primitive-type number))
      (primitive-type number))
   (primitive-procedure #))
  (*
   (procedure-type
      (product-type (primitive-type number) (primitive-type number))
      (primitive-type number))
   (primitive-procedure #))))

Suppose we wanted to define a procedure: 

(define howfar (-> (x meters-per-second seconds) meters) 
   (lambda ((v meters-per-second) (t seconds)) (* v t)))
Giving the parameters the types meters-per-second and seconds means we will get a type error if a programmer mistakenly passes in a different type of value to howfar. (The programmers for the NASA Mars Orbiter, for example, would have found this checking useful. See Units Blunder Sent Craft Into Martian Atmosphere for details.)

As defined above, howfar has a type error:

> (teval '(define howfar (-> (x meters-per-second seconds) meters)
            (lambda ((v meters-per-second) (t seconds)) (* v t))))

Type mismatch.
  Application (* v t) parameter types are seconds x meters-per-second,
  should be Number x Number.

ok

The problem is we want to use the * procedure that expects two Number parameters to multiply a meters-per-second and a meters.

One of the solutions to this problem was developed by Barbara Liskov and her research group for the CLU programming language. CLU was one of a few programming languages developed in the mid-1970s to explore abstract data types. An abstract data type is a type whose representation is hidden. For example, we define a seconds type that is represented using a Number, but the representation type is hidden (meaning, we cannot use a value of type seconds like a value of type Number).

To do useful things with abstract data types, of course, we need a way to sometimes treat them as their representation types. In CLU, this was done by using down to convert an abstract type into its representation type. We also need a way to create values of an abstract type. In CLU, this was done using up to convert a representation type into an abstract type.

Using up and down, we could rewrite howfar as: 

(define howfar (-> (x meters-per-second seconds) meters) 
   (lambda ((v meters-per-second) (t seconds)) 
      (up meters (* (down meters-per-second v) (down seconds t)))))
9. Extend typed Mini-Scheme to support the special form (up Type Expr). An up expression converts the value Expr evaluates into a value of abstract type Type. The value of (up Type Expr) is the value of Expr. The type of (up Type Expr) is the abstract type named by Type. It is a type error if the representation type of Type does not match the type of Expr.

Remember you will need to change both typeof and meval.

After your extensions, you should get these interactions:

> (teval '(definetype seconds number))

ok

> (teval '(definetype meters number))

ok

> (teval '(definetype meters-per-second number))

ok

> (teval '(definetype mps meters-per-second))

ok

> (teval '(up seconds 3))

3

> (teval '(up seconds (+ 3 3)))

6

> (check-type '(up seconds 3))

"seconds"

> (check-type '(up seconds +))

Up type error. The type of the expression (Number x Number) -> (Number)
does not match the representation type Number.

"Error"

> (check-type '(up seconds (+ 3 3)))

"seconds"

> (check-type '(up meters-per-second (+ 3 3)))

"meters-per-second"

> (check-type '(up mps (up meters-per-second (+ 3 3))))

"mps"

10. Extend typed Mini-Scheme to support the special form (down Type Expr). A down expression converts the value Expr evaluates to into a value of the representation type of the abstract type Type. The value of (down Type Expr) is the value of Expr. The type of (down Type Expr) is the representation type of the abstract type named by Type. It is a type error if the type of Expr does not match the abstract type named by Type.

Remember you will need to change both typeof (to do typechecking and evalaute the type of an up or down) and meval.

After your extensions, you should get these interactions:

> (teval '(down seconds (up seconds 3)))

3

> (check-type '(down meters-per-second (+ 3 3)))

Down type error. The type of the expression Number does not match the
abstract type meters-per-second.

"Error"

> (check-type '(down meters (up meters 3)))

"Number"

> (teval '(down seconds (up meters 3)))

Down type error. The type of the expression meters does not match the
abstract type seconds.

"Error"

> (teval '(down meters-per-second (down mps (up mps (up meters-per-second 3)))))

3

> (teval '(define howfar (-> (x meters-per-second seconds) meters) (lambda ((v meters-per-second) (t seconds)) (up meters (* (down meters-per-second v) (down seconds t))))))

ok

> (teval '(howfar 3 4))

Type mismatch.
  Application (howfar 3 4) parameter types are Number x Number, should
  be seconds x meters-per-second.

(error-type)

> (teval '(howfar (up meters-per-second 3) (up seconds 60)))

180

> (teval '(howfar (up meters 3) (up seconds 60)))

Type mismatch.
  Application (howfar (up meters 3) (up seconds 60)) parameter types are
  seconds x meters, should be seconds x meters-per-second.

(error-type)

Remember to clearly identify the code for each question and only include code from clueval.ss that you changed. If you are not able to get all the code working, you can still get substantial credit for these questions by explaining what you are trying to do, turning in the code you have written so far, and explaining what you think is going wrong.

CS 655 University of Virginia
Department of Computer Science
CS 200: Computer Science
 David Evans
evans@virginia.edu
Using these Materials