DOC PREVIEW
UA CSC 520 - Types

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

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 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 16 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 16 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 16 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 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CSc 520 — Principles of Programming Languages15 : Types — EquivalenceChristian CollbergDepartment of Computer ScienceUniversity of [email protected] 2008 Christian CollbergFebruary 18, 20081 Type Checking• In statically typed languages, when an object is defined, we must also give its type:TYPE equivalence = type;TYPE subrange = [from..to];TYPE enumeration = (id,id,...);TYPE array = ARRAY range OF type;TYPE record = RECORDfield : type;END;TYPE func = PROCEDURE (INTEGER):REAL;TYPE set = SET OF type;TYPE ptr = POINTER TO type;VAR name : type;PROCEDURE name (formal-list) [: type];2 Type Checking. . .• In statically typed languages, whenever a typed object us used, we must check that it occurs in theright type context:var x : integer;var y : record a:float; b:integer; end;beginx := y.a; (* ⇐ error *)x := x + y.b;x := x + 5.0; (* ⇐ error? *)end13 Type Checking. . .• type compatibility — can an object of a certain type T be used in a certain context expecting a typeU ?– If T = U then, yes, of course.– But, if T is almost the same as U , then what?• type equivalence — what does it mean for two types T and U to be equivalent?4 Type Checking. . .• type conversion — how can we convert (cast) a value of one type into another?• type coersion — which automatic conversions between types should the language allow?• nonconverting type casts — what are the consequences of allowing values to change type withoutconversion?• type inference — given individual types of parts of an expression, what is the type of the wholeexpression?Type Equivalence5 Structural Type Equivalence• structural equivalence — two types as the same if they consist of the same components.• Example:TYPE T1 = RECORDa:INTEGER;b:ARRAY [0..10] OF CHAR;END;TYPE T2 = RECORDa:INTEGER;b:ARRAY [0..10] OF CHAR;END;Types T1 and T2 are equivalent.• Algol-68, Modula-3, C, ML use structural type equivalence.26 Name Type Equivalence• name equivalence — each type declaration introduces a new type, distinct from all others.• Example:TYPE T1 = ARRAY [0..10] OF CHAR;TYPE T2 = ARRAY [0..10] OF CHAR;Types T1 and T2 are not equivalent.• Java and Ada use name equivalence.7 Declaration Type Equivalence• declaration equivalence — two types are equivalent if they lead back to the same type.• Example:TYPE T1 = ARRAY [0..10] OF CHAR;TYPE T2 = T1;TYPE T3 = T2;TYPE T4 = ARRAY [0..10] OF CHAR;Types T1, T2, T3 are equivalent.• Pascal, Modula-2 use declaration equivalence.• Type equivalence was left out of Pascal definition: some implementations used name equivalence somestructural equivalence some declaration equivalence.8 Type Equivalence. . .TYPE T1 = RECORD a:CHAR; b:REAL END;TYPE T2 = RECORD a:CHAR; b:REAL END;VAR x1 : T1;VAR x2 : T2;VAR x3,x4: RECORD a:CHAR; b:REAL END;BEGINx1 := x2; (* OK, or not? *)x3 := x4; (* OK, or not? *)END• name-equivalence: both assignments are illegal.• declaration-equivalence: only 2nd assignment is legal.• structural type equivalence: both assignments are legal.39 Structural Type EquivalenceTYPE Shape = OBJECTMETHOD draw (); · · ·METHOD move (X,Y:REAL); · · ·END;TYPE Cowboy = OBJECTMETHOD draw (); · · ·METHOD move (X,Y:REAL); · · ·END;VAR s:S; c:C;BEGIN s := c; (* OK? *) END• In Modula-3 (which uses structural equivalence) s and c are compatible! In Object-Pascal (which usesname equivalence) they are not.10 Structural Type Equivalence• Are these types structurally equivalent:TYPE T1 = RECORDa : INTEGER;b : INTEGER;END;TYPE T2 = RECORDb : INTEGER;a : INTEGER;END;• ML and Algol-68: NO, most other languages, YES.11 Structural Type Equivalence• Are these types structurally equivalent:TYPE T1 = ARRAY [1..10] OF CHAR;TYPE T2 = ARRAY [1..2*5] OF CHAR;TYPE T3 = ARRAY [0..9] OF CHAR;• Algol-68: T1,T2,T3are equivalent.• Modula-2: T1,T2 are equivalent, T3 not.12 Name Equivalence• Is this assignment legal?TYPE celsius = REAL;TYPE farenheit = REAL;VAR c : celsius;VAR f : farenheit;c := f;4• In Modula-2, YES. This is a problem.• In Ada, we can construct new types, which are not equivalent:type celsius is new integer;type farenheit is new integer;13 Case Study: C• C uses a combination of declaration and structural equivalence.• Unions and structs use declaration equivalence.• Pointers and arrays use structural equivalence.5Case Study: Modula-314 Modula-3TYPET1 = {A, B, C};T2 = {A, B, C};U1 = [T1.A..T1.C];U2 = [T1.A..T2.C];V = {A,B};• T1 and T2 are the same type. Modula-3 uses structural type equivalence. Two types are the s ame ifthey look the same once they have been expanded.• T1 and U1 are different types, one is an enumeration, the other a subrange.15 Modula-3TYPET = REF INTEGER;S = BRANDED "myType" REF INTEGER; (* Explicit *)V = BRANDED REF INTEGER; (* Compiler-generated *)• Branded types are different from all other types. It is a way of circumventing structural type equiva-lence.16 Readings and References• Read Scott, pp. 321–335.6How Modula-3 Got Structural Type Equivalence17 How the language got its spotsFrom Chapter 8, Systems Programming with Modula-3, Edited by Greg Nelson, Prentice-Hall, ISBN 0-13-590464-1.AnonymousI greatly welcomed the chance of meeting and hearing the wisdom of many of the original languagedesigners. I was astonished and dismayed at the heat and even rancour of their discussions.Apparently the original design of ALGOL 60 had not proceeded in that spit-it of dispassionatesearchfor truth which the quality of the language had led me to suppose. -C.A.R. HoareLike many programming languages, Mo dula-3 was designed by a committee. The meetings were heldat the DEC Systems Research Center in Palo Alto, whose director, Bob Taylor, likes to record importantevents on videotape-including our meetings.18 IntroductionAt first we found the whirring of the cameras distracting, but eventually we became used to it. We evenstarted to imagine that the tapes might be useful in university courses, to teach students how real scientistsapproach problems of programming language design.Unfortunately, when we reviewed the tapes at the end of the project it was obvious that to show them tostudents was out of the question. Such scenes would probably drive students out of computing, if not all theway out of the sciences. In fact, to show the tapes to anybody at all would be highly embarrassing. But oursense of duty to history prevailed, and we resolved to provide the world with copies of the


View Full Document

UA CSC 520 - Types

Documents in this Course
Handout

Handout

13 pages

Semantics

Semantics

15 pages

Haskell

Haskell

15 pages

Recursion

Recursion

18 pages

Semantics

Semantics

12 pages

Scheme

Scheme

32 pages

Syllabus

Syllabus

40 pages

Haskell

Haskell

17 pages

Scheme

Scheme

27 pages

Scheme

Scheme

9 pages

TypeS

TypeS

13 pages

Scheme

Scheme

27 pages

Syllabus

Syllabus

10 pages

FORTRAN

FORTRAN

10 pages

Load more
Download Types
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 Types 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 Types 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?