DOC PREVIEW
UA CSC 520 - Classification

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

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

Unformatted text preview:

CSc 520Principles of Programming Languages26: Types — ClassificationChristian CollbergDepartment of Computer ScienceUniversity of [email protected] 2005 Christian CollbergApril 22, 20051 Enumerable Types• Also called discrete types or ordinal types.• Discrete types are countable, or 1-to-1 with the integers.• Examples:1. integer2. boolean3. char4. subranges5. enumeration types2 Scalar Types• Also called simple types.• The scalar types include:1. discrete types2. real3. rational4. complex13 Composite Types• Also called constructed types.• They are created by applying type constructors to other, simpler, types.• The composit types include:1. records2. variant records3. arrays4. sets5. pointers6. lists7. files4 Types — Overviewintegerbooleancharsubrangeenumerationscalar typesrealrationalcomplexrecordvariant recordarraysetpointerlistfilecomposite typesdiscrete types5 Discreet Types — Enumerations• Pascal, Ada, Modula-2, C have some variant of enumeration types.• C’s enumerations are just syntactic sugar for integer constants.• In Pascal and Ada, enumerations are real types, incompatible with other types.• In Ada and C, enumeration values can be user specified.TYPE Color = (white,blue,yellow,green,red);TYPE Fruits = (apple=4,pear=9,kumquat=99);VAR A : ARRAY Color OF Fruit;FOR c := white TO red DOIF c != yellow THEN A[c] := apple;26 Discreet Types — Subranges• Subranges can be used to force additional runtime checks.• Some languages use subrange types as array index types.TYPE S1 = [0..10];TYPE S2 = [’a’..’z’];TYPE Color = (white,blue,yellow,green,red);TYPE S3 = [blue..green];TYPE A = ARRAY S3 OF INTEGER;VAR X : S3 := white; (*⇐ error *)Structured Types7 Arrays – Storage Layout• Most languages lay out arrays in row-major order. FORTRAN uses column-major.A[1,1] A[1,2]A[2,1] A[2,2]A[3,1] A[3,2]A[4,1] A[4,2]0 A[1,1]1 A[1,2]2 A[2,1]3 A[2,2]4 A[3,1]5 A[3,2]6 A[4,1]7 A[4,2]0 A[1,1]1 A[2,1]2 A[3,1]3 A[4,1]4 A[1,2]5 A[2,2]6 A[3,2]7 A[4,2]Matrix Row Major Column Major8 Array Indexing – 1 Dimensions• How do we compute the address (L-value) of the n:th element of a 1-dimensional array?• Aelszis A’s element-size, Aaddris its base address.VAR A : ARRAY [l .. h] OF T;L − VAL(A[i]) ≡ Aaddr+ (i − l) ∗ Aelsz≡ Aaddr+ (l ∗ Aelsz) + i ∗ AelszC ≡ Aaddr+ (l ∗ Aelsz)L − VAL(A[i]) ≡ C + i ∗ Aelsz• Note that C can be computed at compile-time.39 Array Indexing – 2 DimensionsVAR A :ARRAY [l1..h1][l2..h2] OF T;w1≡ h1− l1+ 1w2≡ h2− l2+ 1L − VAL(A[i1, i2]) ≡ Aaddr+ ((i1− l1) ∗ w2+ i2+ l2) ∗ Aelsz≡ Aaddr+ (i1∗ w2+ i2) ∗ Aelsz−(l1∗ w2− l2) ∗ AelszC ≡ Aaddr− (l1∗ w2− l2) ∗ AelszL − VAL(A[i1, i2]) ≡ (i1∗ w2+ i2) ∗ Aelsz+ C• C can be computed at compile-time.10 Array Indexing – n DimensionsVAR A : ARRAY [l1..h1] ... [ln..hn] OF T;wk≡ hk− lk+ 1C ≡Aaddr− ((· · · (l1∗ w2+ l2) ∗ w3+ l3) · · ·) ∗ wn+ ln) ∗ AelszL − VAL(A[i1, i2, ..., in]) ≡((· · · (i1∗ w2+ i2) ∗ w3+ i3) · · ·) ∗ wn+ in) ∗ Aelsz+ C11 Record Types• Pascal, C, Modula-2, Ada and other languages havevariant records (C’s union type):TYPE R1 = RECORD tag : (red,blue,green);CASE tag OFred : r : REAL; |blue : i : INTEGER; |ELSE c : CHAR;END;END;Depending on the tag value R1 has a real, integer, or char field.• The size of a variant part is the max of the sizes of its constituent fields.412 Record Types. . .• Oberon has extensible record types:TYPE R3 = RECORDa : INTEGER;END;TYPE R4 = (R3) RECORDb : REAL;END;R4 has both the a and the b field.• Extensible records are similar to classes in other languages.13 Pointer Types• In order to build recursive structures, most languages allow some way of declaring recursive types.These are necessary in order to construct linked structures such as lists and trees:TYPE P = POINTER TO R;TYPE R = RECORDdata : INTEGER;next : P;END;• Note that P is declared before its use. Languages such as Pascal and C don’t allow forward declarations,but make an exception for pointers.14 Procedure Types• C, Modula-2, and other languages support procedure types. You can treat the address of a procedurelike any other object.• Languages differ in whether they allow procedures whose address is taken to be nested or not. (Why?)TYPE P = PROCEDURE(x:INTEGER; VAR Y:CHAR):REAL;VAR z : P; VAR c : CHAR; VAR r : REAL;PROCEDURE M (x:INTEGER; VAR Y:CHAR):REAL;BEGIN· · ·END;BEGINz := M; /* z holds the address of M. */r := z(44,c);END.15 Class Types• Java’s classes are just pointer to record types. Some languages (Object Pascal, Oberon, MODULA-3)define classes just like records.5• Nore about classes later.TYPE C1 = CLASSx : INTEGER;void M() { · · · };void N() { · · · };END;TYPE C2 = CLASS EXTENDS C1r : REAL; // Add another field.void M() { · · · }; // Overrides C1.Mvoid Q() { · · · }; // Add another method.END;16 Set Types• Pascal and Modula-2 support sets of ordinal types.• Sets are implemented as bitvectors.• Many implementations restrict the size of a set to 32 (the size of a machine word), or 256 (so you candeclare a set of char).type letset = set of ’A’ .. ’z’;var x, y, z, w: letset;beginx := [’A’..’Z’,’a’]; y := [’a’..’z’];z := x + y; (* set union *)z := x * y; (* set intersection *)w := x - y; (* set difference *)if ’A’ in z then ...; (* set membership *)end.17 Readings and References•Read Scott,


View Full Document

UA CSC 520 - Classification

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

Types

Types

16 pages

FORTRAN

FORTRAN

10 pages

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