Design 3

One important real-world type system issue we haven't dealt with in this course is overloading. Many programmers, either in fits of linguistic passion, or in moments of turbid thinking, or simply out of ignorance, confuse this feature for many others, most often polymorphism (of either kind). Overloading is really the assignment of one name to many different operators. Which operator gets used depends on the types of the arguments; some process selects the actual operator and invokes it on those values. The different operators may have nothing in common; each one may be implemented in a manner entirely distinct from the others. Think of overloading as a syntactic add-on to an otherwise traditional language of the sorts we have studied in this course. We will study overloading in a language for graphical animation, based on a typed extension to the iota calculus from the first exam. We've kept the language fairly dumb to reduce your work (see the implementation note at the bottom). The language's grammar is as follows: <L> := <num> | <id> | (<L> + <L>) | (<L> * <L>) | (fun (<id> : <T>) <L>) | (<L> (<L>)) | now | (< <L> <L> >) | (ellipse <L> <L> <L>) | (rectangle <L> <L>) | (after <L> draw <L>) with the type language T := time | dim ;; we will refer to this as a dimension | <dim, dim> ;; we will refer to this as a position | <T> -> <T> Notice that there is no numeric type! Every number is either a time or a dimension, depending on how it is used. In L, now evaluates to the current time; (< ... >) constructs a position; ellipse consumes a center (position), width (dimension) and height (dimension), draws an ellipse of the specified proportions at the given position, and returns the value of the center; rectangle consumes two positions, the top-left and bottom-right corners, draws a rectangle over the specified range, and returns the top-left corner; and, after schedules future animations. The first sub-expression must evaluate to a positive time value. after waits for that duration to elapse, then evaluates the second sub-expression, which must evaluate to a position (typically through the composition of several drawing commands). The result value of the after expression is this position. This language has two overloaded operations: + and *, each of which consumes two arguments. Either both arguments are times, or they're both dimensions, or they're both positions. In the first two cases, the operations perform their ordinary numeric roles; in the third case, the operation performs the operation pointwise on the cartesian pair, creating a new position. In each case, the operation returns a value of the same type as its arguments. This poses a problem to a static type checker. There is no uniform type that the type checker can assign to these primitives. Its best bet is to rewrite the program into one that makes the type evident at each primitive application; for instance, each + becomes either +-time or +-dim or +-posn. Given the types of the arguments, it can (a) check them for consistency, (b) determine which operation the programmer intends, and (c) continue with type checking. Your task is to design a type checker that translates the names of all overloaded primitives into their disambiguated implementation names. (Think of the type checker as conveying this information, by rewriting, to the interpreter/compiler, so the latter won't have to figure this out again.) This kind of rewriter is called a type elaborator. Rather than implement it, you must present it as a set of judgements. (Yes, those again.) Though judgements were initially presented as a peculiar way of writing if-then rules, you have since seen judgements take on more functionality. In the polymorphism section, the judgements computed sets of constraints (and, in fact, did no type checking!). In the section on Java types, the judgements elaborated the program to annotate field and some method lookups with their compile-time types. This latter kind of elaboration is very similar to what you will want to do, except yours is much simpler. One tricky problem: what if the entire expression is, say, 3? From the context, it's impossible to determine the type of this expression. That's okay: this should not result in a type error. How about if the expression is (3 + 4)? What should the + be rewritten to? You may pick either +-time or +-dim — just not +-posn. In short, you must always be type consistent, but if the type is not fully constrained, you may pick any (specific) type you choose. Even if you use type variables internally, there shouldn't be any in the output. Tips: You may find it easier to first write down a type system that ignores the overloading and elaboration, rather than tackle it all at once. Beware that <num> is a bit tricky. Get the rest right first, then worry about this one. (By then, it may have become clear how to do it.) And do ask for help if you get stuck on this assignment! Please do individual work on this assignment, so you fully understand the related language design issues. You must turn in three things: an explanation of the form of your judgements (a judgement ``consumes'' the following number of the these kinds of things, and ``returns'' the following number of those kinds of things ...) — i.e., if you were implementing it, what would the type of the elaborator be?; the target language used by the elaborator; and, the elaborator, expressed as judgement rules. Turn in your text on paper. Unless your handwriting is extremely legible, please print your submission. Your responses are due by 11:59pm on 2000-12-06. Miscellany Terminology: People sometimes refer to overloading as ad hoc polymorphism. The operative term here is the ``ad hoc'' part — there is no rhyme or reason to these operations sharing the same name, other than clashing convention, perceived convenience or programmer caprice. Most programming languages people would not call this a form of polymorphism at all to avoid muddying the waters. Literacy Note: Overloading is a type issue, and many languages resolve it in a static type system. ML, for instance, overloads +, and resolves statically between integer and floating-point addition. Some languages, especially those without a static type system, handle overloading dynamically: they examine the type tags on the arguments and accordingly pick an operation. Scheme does this to choose between, say, addition on small integers, bignums, floating points, complex numbers, and so on, each of which is really a different operation (adding small integers is largely a matter of using the processor's addition; adding bignums requires heap operations; floating points need floating point operations; complex numbers are really pairs, which must be added (by overloading) point-wise; and so on). Opinion: Overloading is not inherently evil. As the paragraph above illustrates, most languages internally have some limited form of overloading. Giving unrestricted use of this to programmers, however, doesn't seem too smart. The good examples I've seen seem to all involve math (e.g., overloading + to operate on your new matrix package). Programmers seem to have trouble resisting the overloading impulse. They often create excessively cute notations that make software impenetrable to a reader, who might need to debug or extend it. (``Hey, look, Bjarne forgot to define + for the CellPhone class I just created! Let's correct this weakness by extending the language to define the addition of two cellular phones to mean the digit-wise addition of their numbers, ignoring carry's, with the following special algorithm to handle sums that result in non-existent area codes ...'') As a designer and implementor, remember that not every feature available to you must necessarily be passed on to the user. Two other good examples: pointers and manual memory management (which is how a garbage collector is itself implemented). Do what you must behind the scenes. And leave it there. Implementation Note: Don't worry, you don't need to implement anything. You could imagine the drawing language described here being beneath the surface of a tool like Macromedia Flash, especially if after were to spawn a thread that performed the drawing. See the course newsgroup for a posting that describes such a library, and tells you how you can run it.