DOC PREVIEW
UW CSE 341 - Lecture Notes

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CSE 341, Spring 2011, Lecture 23 SummaryStandard Disclaimer: These comments may prove useful, but certainly are not a complete summary of allthe important stuff we did in class. They may make little sense if you missed class, but hopefully will helpyou organize and process what you have learned.This lecture considers developing a static type system for an object-oriented language. We won’t considerany specific type system for any specific language. Rather, we will consider the general principles and“theory” that would go into developing such a type system. Next lecture we will “connect” this discussionto classes (as in Java) and how it compares to an ML-style type system. The main points of this lecture are:• An object’s type should indicate what methods can be called on it so that there are no message-not-understood errors.• To avoid being overly restrictive, subtyping — allowing all expressions of one type to also have anothertype — is extremely useful.• Width and permutation subtyping are sound.• Depth subtyping is unsound if fields are mutable.• Subtyping on methods (or functions) allows contravariant arguments and covariant results. (Theseterms are defined below.)Recall the purpose of a type system is to prevent certain errors for all programs, rejecting some programsbefore they run. In ML, the errors we prevented included treating a string as a function or accessing functionsmade private by a signature. For pure object-oriented languages, “all we do” is create objects and send themmessages (i.e., call methods), so what might we want to prevent?1. We want to prevent sending a message to an object that cannot understand the message (i.e., has nomethod of the right name). This is a message-not-understood error.2. If our language allows methods with multiple arguments, we want to prevent calling a method withthe wrong number of arguments.Because there isn’t much else our program does, there isn’t much else to prevent. We should also preventaccessing non-existent fields, but if we imagine field accesses as using getter/setter methods, then the firstitem above covers this case.(Though we won’t have time to discuss it, static overloading and/or multimethods raise additional errorswe may wish to prevent. With these features, languages can have multiple methods with the same namethat are actually different methods and we have to decide at each call-site which method is the “best match”for the arguments. If there are situations where there is “no best match”, that is an error. Java is anexample of a language with static overloading where the type system rejects programs that have calls withno-best-match.)Recall a type system is sound if, by definition, it never accepts a program that could have one of theerrors the type system is supposed to prevent. Our goal is to identify the key features a sound type system forobjects needs. However, preventing message-not-understood often turns out to be a bit too strong in practice,so many languages make the choice not to catch errors resulting from some “special thing” like Java’s nullor Ruby’s nil. These are not quite the same: Ruby’s nil is an object that just happens to respond to veryfew messages. null is not an object, it responds to no messages and evaluating e.m(e1,...,en) where eevaluates to null throws (as you have no doubt seen) a NullPointerException. In either case, though, thetype of nil or null should be something that accepts very few messages, but for convenience the type systemtreats as something that can have any type, meaning it can accept any message. Since this is not actuallytrue, for our type system to be sound we have to change our definition of what it intends to prevent: Wewant to prevent a message-not-understood error unless the receiver is null/nil (in which case a run-timeerror is allowed).1Before considering objects with arbitrary methods, let’s just consider objects that are like ML records.They have fields and for every field we assume there is a getter method and a setter method. We will alsoassume our language has integers, though we could get by without it. So given an expression like e.x or likee.x = 17, we need that e type-checks and has a field named x. That way the expressions above will nothave message-not-understood (or perhaps “field-not-understood”) errors.However, it is not enough to let an object’s type just list the fields of the object. Consider obj.x.y. Ifall we know about obj is that it has fields x, f, and a, then we know obj.x is okay, but we do not know ifthe resulting object has a y field. Therefore, like ML record types, we need object types to list fields andthe types of the fields. So the definition of types is recursive, as we might expect. Since we are not talkingabout any specific programming language, we need to make up some syntax for writing down types. Wewon’t use class names since that is largely a separate issues. Instead we’ll just write down types “directly”.For example, an object with two fields x and y that both hold numbers could have type:{ x : int, y : int }We can also let ourselves give names to types, which is convenient and necessary for describing lists or trees.Here are some examples:intList = { hd : int, tl : intList }string = { hd : char, tl : string }name = { first : string, last : string }In the last example, we describe objects with first and last fields, both of which hold objects thatthemselves have hd and tl fields. We can also write types just like this:{ a : {}, b : { c : int } }This type describes objects with fields a and b where the contents of the a field is an object with no fieldsand the contents of the b field is an object with a c field whose contents is a number.These types are sufficient for defining a sound type system as you might expect. For example, we couldallow a variable declaration such as:{ a : {}, b : { c : int } } o1 = [ a => [], b => [ c => 17 ]]where here we are making up syntax for creating objects. We are just writing the name of a field and thenan => and then the field’s contents, which can be another object. The syntax does not really matter. Wecould then allow setting a field with another object of the appropriate type:{ c : int } o3 = [ c => 42 ]o1.b = o3However, requiring the right-hand side of an assignment to have a type exactly equal to the type of theassigned-to location is unnecessarily restrictive. Consider:{ c : int, d : int } o4 = [ c => 42, d => 43


View Full Document

UW CSE 341 - Lecture Notes

Documents in this Course
Macros

Macros

6 pages

Macros

Macros

6 pages

Macros

Macros

3 pages

Mutation

Mutation

10 pages

Macros

Macros

17 pages

Racket

Racket

25 pages

Scheme

Scheme

9 pages

Macros

Macros

6 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?