►Programming Language Design (Fall 2011)
▼3 Assignments
►3.20 Type Inference
On this page:
3.20.1 Constraint Generation and Satisfaction
3.20.2 Type Inference
3.20.3 Application
  ← prev  up  next → 

3.20 Type Inference

Complete this assignment with Team Three.

You must submit this in an archive named "wtypei.zip". This archive must contain a folder named "wtypei". This folder must contain all the files specified below. You must attach "wtypei.zip" to an email whose subject is "BYU - Fall 2011 - CS 330 - wtypei" and whose message body contains the name of everyone on your team (each on a separate line.) You must send this email to jay@cs.byu.edu before 5pm (Provo time) on 12/1. Ensure that what you are satisfied with what you submit, because only your chronologically first submission will be graded. Ensure that you follow these instructions exactly, since submissions that do not meet these requirements (i.e. do not have the correct format) will receive no credit, despite the time and energy you put into the assignment. Please see Turn In Policy for more information.

You must submit this in a file named "wtypei.pdf".

3.20.1 Constraint Generation and Satisfaction

Consider the program:

(+ 1 (first (cons true empty)))

This program has a type error.

Generate constraints for this program. Isolate the smallest set of these constraints that, solved together, identify the type error.

Feel free to label the sub-expressions above with superscripts for use when writing and solving constraints.

3.20.2 Type Inference

Consider the following typed expression:
{fun {f : B1}  : B2
  {fun {x : B3}  : B4
    {fun {y : B5}  : B6
      {cons x {f {f y}}}}}}
We have left the types unspecified (Bn) to be filled in by the type inference process. Derive type constraints from the above program. Then solve these constraints. From these solutions, fill in the values of the boxes. Be sure to show all the steps specified by the algorithms (i.e., writing the answer based on intuition or knowledge is insufficient). You should use type variables where necessary. To save writing, you can annotate each expression with an appropriate type variable, and present the rest of the algorithm in terms of these type variables alone (to avoid having to copy the corresponding expressions). If you do this, be sure to annotate every sub-expression with a type variable. Be sure the annotations are clearly readable!

3.20.3 Application

In 850 words or less, describe if and how your knowledge of type inference will help you in your future programming practice. Good answers might discuss how this concept can be applied in interesting programming environments or how knowledge of its subtleties clarifies or improves existing practices, techniques, tools, etc.

  ← prev  up  next →