Type Systems
This content provides an overview of type systems in programming languages, covering topics such as type declaration, constructors, inference, compatibility, and usage. It discusses the role of types in defining values, operations, and structures within a program, offering insights into how types are defined, declared, and utilized. The information presented sheds light on the fundamentals of type systems and their significance in programming language design.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Type Systems CSE 340 Principles of Programming Languages Spring 2016 Adam Doup Arizona State University http://adamdoupe.com
Type Systems Informally, a type in a programming language specifies a set of values and operations that can be applied on those values A type can be associated with a variables or a constant Values are not necessarily numeric values, for example we can specify function types A type system consists of Basic types Type constructors Type inference Type compatibility 2 Adam Doup , Principles of Programming Languages
Type Declaration Programming language will typically include Basic types Included in the programming language and available to any program written in that language Type constructors Way for a programmer to define new types 3 Adam Doup , Principles of Programming Languages
Type Constructors Pointer to T, where T is a type struct { a1: T1; a2 : T2; , ak: Tk; } Where aiis a field name and Tiis a previously defined type array range of T Where range can be single or multi dimensional function of T1, T2, ..., Tkreturns T Type is a function, the types of the parameters are T1... Tkand the return type is T 4 Adam Doup , Principles of Programming Languages
Using Type Constructors Declaring Types Type cm : integer; Type RGBA : array [0..4] of int; Type png : array [0..256] of RGBA; Anonymous Types array [0..4] of int x; struct { int a; char b; } y; 5 Adam Doup , Principles of Programming Languages
Type Compatibility Which assignments are allowed by the type system? a = b;? int a; float b; float a; int b; 6 Adam Doup , Principles of Programming Languages
Type Inference Types of expressions or other constructs as a function of subexpression types a + b a int; b float Returns a float in C Error in ML a * b a string; b int Error in most languages Returns a string in Python 7 Adam Doup , Principles of Programming Languages
Type Compatibility Principally about type equivalence How to determine if two types are equal? Type cm : integer; Type inch : integer; cm x; inch y; x = y? 8 Adam Doup , Principles of Programming Languages
Name Equivalence Types must have the exact same name to be equivalent Type cm : integer; Type inch : integer; cm x; inch y; x = y? // ERROR 9 Adam Doup , Principles of Programming Languages
Name Equivalence a: array [0..4] of int; b: array [0..4] of int; a = b? Not allowed under name equivalence 10 Adam Doup , Principles of Programming Languages
Name Equivalence a, b: array [0..4] of int; a = b? Not allowed because array [0..4] of int is not named 11 Adam Doup , Principles of Programming Languages
Name Equivalence Type A: array [0..4] of int; a: A; b: A; a = b? Allowed, because both a and b have the same name 12 Adam Doup , Principles of Programming Languages
Internal Name Equivalence If the program interpreter gives the same internal name to two different variables, then they share the same type a, b: array [0..4] of int; c: array [0..4] of int; a = b? Yes, because interpreter/compiler gives the same internal name to a and b a = c? No, because interpreter/compiler gives different internal name to c than to a and b 13 Adam Doup , Principles of Programming Languages
Structural Equivalence 1. Same built-in types 2. Pointers to structurally equivalent types Type cm : integer; Type inch : integer; cm x; inch y; x = y? // Allowed! 14 Adam Doup , Principles of Programming Languages
Structural Equivalence int* a; float* b; a = b? Not structurally equivalent, because int and float are not structurally equivalent 15 Adam Doup , Principles of Programming Languages
Structural Equivalence 3. Determining struct structural equivalence Two structures st1 { x1: W1, x2: W2, , xk: Wk} st2 { y1: Q1, y2: Q2, ..., yk: Qk} st1 and st2 are structurally equivalent iff W1structurally equivalent to Q1 W2structurally equivalent to Q2 ... Wkstructurally equivalent to Qk 16 Adam Doup , Principles of Programming Languages
Structural Equivalence struct A { a: int, b: float } struct B { b: int, a: float } A foo; B bar; foo = bar? 17 Adam Doup , Principles of Programming Languages
Structural Equivalence struct A { a: int, b: float } struct B { b: float, a: int } A foo; B bar; a = b? 18 Adam Doup , Principles of Programming Languages
Structural Equivalence 4. Determining array structural equivalence Two Arrays T1 = array range1 of t1 T2 = array range2 of t2 T1 and T2 are structurally equivalent iff: range1 and range2 have (1) the same number of dimensions and (2) the same number of entries in each dimension t1 and t2 are structurally equivalent 19 Adam Doup , Principles of Programming Languages
Structural Equivalence 5. Determining function structural equivalence Two functions T1 = function of (t1, t2, t3, , tk) returns t T2 = function of (v1, v2, v3, ..., vk) returns v T1 and T2 are structurally equivalent iff: For all i from 1 to k, tiis structurally equivalent to vi t is structurally equivalent to v 20 Adam Doup , Principles of Programming Languages
Determining Structural Equivalence The goal is to determine, for every pair of types in the program, if they are structurally equivalent Seems fairly simple, just keep applying the previous 5 rules until the base case 1 or 2 is reached How to handle the following case: T1 = struct { a: int; p: pointer to T2; } T2 = struct { a: int; p: pointer to T1; } Applying the rules states that T1 is structurally equivalent to T2 iff pointer to T1 is structurally equivalent to pointer to T2, which is true if T1 is structurally equivalent to T2 21 Adam Doup , Principles of Programming Languages
Structural Equivalence Algorithm The way to break the stalemate is to assume that T1 and T2 are structurally equivalent because no rule contradicts them being structurally equivalent Our goal is to create an n X n table, where n is the number of types in the program, and each entry in the table is true if the types are structurally equivalent and false otherwise 22 Adam Doup , Principles of Programming Languages
Structural Equivalence Algorithm To support cyclical definitions, we first initialize all entries in the table to true We assume that types are structurally equivalent unless we have proof otherwise Algorithm is fairly simple Set the n X n table to have each entry as true While table has not changed Check each entry i, j in the table, and if Ti and Tj are not structurally equivalent, then set the entry i, j in the table to false Note that Ti and Tj are the ith and jth types in the program 23 Adam Doup , Principles of Programming Languages
T1 = struct { a: int, p: pointer to T2 } T2 = struct { c: int, q: pointer to T3 } T3 = struct { a: float, p: pointer to T1 } T1 true true true T2 true true true T3 true true true T1 T2 T3 25 Adam Doup , Principles of Programming Languages
T1 = struct { a: int, p: pointer to T2 } T2 = struct { c: int, q: pointer to T3 } T3 = struct { a: float, p: pointer to T1 } T1 true true true T2 true true true T3 true true true T1 T2 T3 26 Adam Doup , Principles of Programming Languages
T1 = struct { a: int, p: pointer to T2 } T2 = struct { c: int, q: pointer to T3 } T3 = struct { a: float, p: pointer to T1 } T1 true true true T2 true true true T3 true true true T1 T2 T3 27 Adam Doup , Principles of Programming Languages
T1 = struct { a: int, p: pointer to T2 } T2 = struct { c: int, q: pointer to T3 } T3 = struct { a: float, p: pointer to T1 } T1 true true true T2 true true true T3 false true true T1 T2 T3 28 Adam Doup , Principles of Programming Languages
T1 = struct { a: int, p: pointer to T2 } T2 = struct { c: int, q: pointer to T3 } T3 = struct { a: float, p: pointer to T1 } T1 true true false T2 true true true T3 false true true T1 T2 T3 29 Adam Doup , Principles of Programming Languages
T1 = struct { a: int, p: pointer to T2 } T2 = struct { c: int, q: pointer to T3 } T3 = struct { a: float, p: pointer to T1 } T1 true true false T2 true true true T3 false true true T1 T2 T3 30 Adam Doup , Principles of Programming Languages
T1 = struct { a: int, p: pointer to T2 } T2 = struct { c: int, q: pointer to T3 } T3 = struct { a: float, p: pointer to T1 } T1 true true false T2 true true true T3 false false true T1 T2 T3 31 Adam Doup , Principles of Programming Languages
T1 = struct { a: int, p: pointer to T2 } T2 = struct { c: int, q: pointer to T3 } T3 = struct { a: float, p: pointer to T1 } T1 true true false T2 true true false T3 false false true T1 T2 T3 32 Adam Doup , Principles of Programming Languages
T1 = struct { a: int, p: pointer to T2 } T2 = struct { c: int, q: pointer to T3 } T3 = struct { a: float, p: pointer to T1 } T1 true true false T2 true true false T3 false false true T1 T2 T3 33 Adam Doup , Principles of Programming Languages
T1 = struct { a: int, p: pointer to T2 } T2 = struct { c: int, q: pointer to T3 } T3 = struct { a: float, p: pointer to T1 } T1 true true false T2 false true false T3 false false true T1 T2 T3 34 Adam Doup , Principles of Programming Languages
T1 = struct { a: int, p: pointer to T2 } T2 = struct { c: int, q: pointer to T3 } T3 = struct { a: float, p: pointer to T1 } T1 true false false T2 false true false T3 false false true T1 T2 T3 35 Adam Doup , Principles of Programming Languages
T1 = struct { a: int, p: pointer to T2 } T2 = struct { c: int, q: pointer to T3 } T3 = struct { a: float, p: pointer to T1 } T1 true false false T2 false true false T3 false false true T1 T2 T3 36 Adam Doup , Principles of Programming Languages
