Type Systems

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
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
Type Constructors
 
•
Pointer to T, where T is a type
•
struct { a
1
: T
1
; a
2
 : T
2
; 
…, a
k
: T
k
; }
–
Where a
i
 is a field name and T
i
 is a previously
defined type
•
array range of T
–
Where range can be single or multi dimensional
•
function of T
1
, T
2
, ..., T
k
 returns T
–
Type is a function, the types of the parameters
are T
1
 ... T
k
 and the return type is T
4
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
Type Compatibility
 
•
Which assignments are allowed by the
type system?
–
a = b;?
–
int a; float b;
–
float a; int b;
6
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
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
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
Name Equivalence
 
a: array [0..4] of int;
b: array [0..4] of int;
 
•
a = b?
–
Not allowed under name equivalence
10
Name Equivalence
 
a, b: array [0..4] of int;
 
•
a = b?
–
Not allowed because array [0..4] of int is not
named
11
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
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
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
Structural Equivalence
 
int* a;
float* b;
 
•
a = b?
–
Not structurally equivalent, because int and
float are not structurally equivalent
15
Structural Equivalence
 
3.
Determining struct structural equivalence
–
Two structures
–
st1 { x
1
: W
1
, x
2
: W
2
, 
…, x
k
: W
k
 }
–
st2 { y
1
: Q
1
, y
2
: Q
2
, ..., y
k
: Q
k
 }
–
st1 and st2 are structurally equivalent iff
•
W
1
 structurally equivalent to Q
1
•
W
2
 structurally equivalent to Q
2
•
...
•
W
k
 structurally equivalent to Q
k
16
Structural Equivalence
 
struct A { a: int, b: float }
struct B { b: int, a: float }
 
A foo;
B bar;
•
foo = bar?
17
Structural Equivalence
 
struct A { a: int, b: float }
struct B { b: float, a: int }
 
A foo;
B bar;
•
a = b?
18
Structural Equivalence
 
4.
Determining array structural equivalence
–
Two Arrays
–
T1 = array range1 of t
1
–
T2 = array range2 of t
2
–
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
•
t
1
 and t
2
 are structurally equivalent
19
Structural Equivalence
 
5.
Determining function structural
equivalence
–
Two functions
–
T1 = function of (t
1
, t
2
, t
3
, 
…, t
k
) returns t
–
T2 = function of (v
1
, v
2
, v
3
, ..., v
k
) returns v
–
T1 and T2 are structurally equivalent iff:
•
For all i from 1 to k, t
i
 is structurally equivalent to
v
i
•
t is structurally equivalent to v
20
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
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
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 T
i
 and T
j
 are not
structurally equivalent, then set the entry i, j in the table
to 
false
•
Note that T
i
 and T
j
 are the i
th
 and j
th
 types in
the program
23
 
T1 = struct { a: int; p: pointer to T2; }
T2 = struct { c: int; q: pointer to T3; }
T3 = struct { a : float; p: pointer to T1; }
24
 
T1 = struct { a: int, p: pointer to T2 }
T2 = struct { c: int, q: pointer to T3  }
T3 = struct { a: float, p: pointer to T1 }
25
T1 = struct { a: int, p: pointer to T2 }
T2 = struct { c: int, q: pointer to T3  }
T3 = struct { a: float, p: pointer to T1 }
26
T1 = struct { a: int, p: pointer to T2 }
T2 = struct { c: int, q: pointer to T3  }
T3 = struct { a: float, p: pointer to T1 }
27
T1 = struct { a: int, p: pointer to T2 }
T2 = struct { c: int, q: pointer to T3  }
T3 = struct { a: float, p: pointer to T1 }
28
T1 = struct { a: int, p: pointer to T2 }
T2 = struct { c: int, q: pointer to T3  }
T3 = struct { a: float, p: pointer to T1 }
29
T1 = struct { a: int, p: pointer to T2 }
T2 = struct { c: int, q: pointer to T3  }
T3 = struct { a: float, p: pointer to T1 }
30
T1 = struct { a: int, p: pointer to T2 }
T2 = struct { c: int, q: pointer to T3  }
T3 = struct { a: float, p: pointer to T1 }
31
T1 = struct { a: int, p: pointer to T2 }
T2 = struct { c: int, q: pointer to T3  }
T3 = struct { a: float, p: pointer to T1 }
32
T1 = struct { a: int, p: pointer to T2 }
T2 = struct { c: int, q: pointer to T3  }
T3 = struct { a: float, p: pointer to T1 }
33
T1 = struct { a: int, p: pointer to T2 }
T2 = struct { c: int, q: pointer to T3  }
T3 = struct { a: float, p: pointer to T1 }
34
T1 = struct { a: int, p: pointer to T2 }
T2 = struct { c: int, q: pointer to T3  }
T3 = struct { a: float, p: pointer to T1 }
35
T1 = struct { a: int, p: pointer to T2 }
T2 = struct { c: int, q: pointer to T3  }
T3 = struct { a: float, p: pointer to T1 }
36

								

								

								

										

												
Slide Note

												

										

								


								
						

							
						


							

								

									
										
Embed
									
									
										
Share
									

									
									
									

								

								
							


							

							 
 							 
 							 
						  


							
							

								
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.


								
    
																		
  •   Programming Languages
    • 
																	
  •    Type Systems
    • 
																	
  •    Declarations
    • 
																	
  •    Constructors
    • 
																	
  •    Compatibility
    • 
																

								

								

									

										mano485
										

											 mano485 Follow
											

										

									

									
Uploaded on Feb 16, 2025 | 0 Views

								

								


								

									
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.

								

									 
									
Download 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.


								

									
 E N D 

								


							
Presentation Transcript

							

							
  1. Type Systems CSE 340     Principles of Programming Languages Spring 2016 Adam Doup   Arizona State University http://adamdoupe.com
    2. 
            
            
            
  2. 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
    3. 
            
            
            
  3. 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
    4. 
            
            
            
  4. 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
    5. 
            
            
            
  5. 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
    6. 
            
            
            
  6. 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
    7. 
            
            
            
  7. 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
    8. 
            
            
            
  8. 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
    9. 
            
            
            
  9. 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
    10. 
            
            
            
  10. 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
    11. 
            
            
            
  11. 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
    12. 
            
            
            
  12. 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
    13. 
            
            
            
  13. 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
    14. 
            
            
            
  14. 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
    15. 
            
            
            
  15. 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
    16. 
            
            
            
  16. 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
    17. 
            
            
            
  17. 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
    18. 
            
            
            
  18. 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
    19. 
            
            
            
  19. 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
    20. 
            
            
            
  20. 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
    21. 
            
            
            
  21. 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
    22. 
            
            
            
  22. 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
    23. 
            
            
            
  23. 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
    24. 
            
            
            
  24. 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
    25. 
            
            
            
  25. 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
    26. 
            
            
            
  26. 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
    27. 
            
            
            
  27. 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
    28. 
            
            
            
  28. 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
    29. 
            
            
            
  29. 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
    30. 
            
            
            
  30. 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
    31. 
            
            
            
  31. 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
    32. 
            
            
            
  32. 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
    33. 
            
            
            
  33. 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
    34. 
            
            
            
  34. 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
    35. 
            
            
            
  35. 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
    36. 
            
            
            
						

						

					

					
					
					

						
Related

						

						


							
							
							
							

						

							

									

      

        
          

            

              E-bikes Market to be Worth $88.3 Billion by 2030—Exclusive Report by Meticulous Research®”
            

            

              
E-bikes Market to be Worth $88.3 Billion by 2030—Exclusive Report by Meticulous Research®”

              
Dips

            

          

        
      


     

      

        
          

            

              Water Quality Testing Market: Test Type and Industry Sector
            

            

              
Water Quality Testing Market: Test Type and Industry Sector

              
Savi

            

          

        
      


     

      

        
          

            

              Overview of Distributed Systems: Characteristics, Classification, Computation, Communication, and Fault Models
            

            

              
Overview of Distributed Systems: Characteristics, Classification, Computation, Communication, and Fault Models

              
paulina

            

          

        
      


     

      

        
          

            

              Lower Your Patients' Risk of Type 2 Diabetes with CDC's National DPP Lifestyle Change Program
            

            

              
Lower Your Patients' Risk of Type 2 Diabetes with CDC's National DPP Lifestyle Change Program

              
timur

            

          

        
      


     

      

        
          

            

              Operating Systems
            

            

              
Operating Systems

              
lucy

            

          

        
      


     

      

        
          

            

              Information Systems in Organizational Management
            

            

              
Information Systems in Organizational Management

              
bode

            

          

        
      


     

      

        
          

            

              Radar Market Worth $38.4 Billion by 2029
            

            

              
Radar Market Worth $38.4 Billion by 2029

              
roshanikale

            

          

        
      


     

      

        
          

            

              E-bikes Market is projected to reach $88.3 billion by 2030
            

            

              
E-bikes Market is projected to reach $88.3 billion by 2030

              
Harshita

            

          

        
      


     

      

        
          

            

              Different Types of Recommender Systems
            

            

              
Different Types of Recommender Systems

              
adam43

            

          

        
      


     

      

        
          

            

              Type I and Type II Errors in Hypothesis Testing
            

            

              
Type I and Type II Errors in Hypothesis Testing

              
sonnet

            

          

        
      


     

      

        
          

            

              Diabetes: Types, Causes, and Prevention
            

            

              
Diabetes: Types, Causes, and Prevention

              
eilish

            

          

        
      


     

      

        
          

            

              Introduction to Embedded Systems Design
            

            

              
Introduction to Embedded Systems Design

              
scarlettrose

            

          

        
      


     

      

        
          

            

              Marine Collagen Market Expected to Surpass $2.32 Billion by 2031
            

            

              
Marine Collagen Market Expected to Surpass $2.32 Billion by 2031

              
Komal1

            

          

        
      


     

      

        
          

            

              Biometric Systems Market on Track to Reach $51.6 Billion by 2029
            

            

              
Biometric Systems Market on Track to Reach $51.6 Billion by 2029

              
Komal1

            

          

        
      


     

      

        
          

            

              Information Systems in Organizations: Overview and Implementation
            

            

              
Information Systems in Organizations: Overview and Implementation

              
aub_and

            

          

        
      


     

      

        
          

            

              Types of Conditional Clauses and Examples
            

            

              
Types of Conditional Clauses and Examples

              
maconbe

            

          

        
      


     

      

        
          

            

              Bandwidth and Packet Type Detection Schemes for 40-50GHz Millimeter Wave Communication Systems
            

            

              
Bandwidth and Packet Type Detection Schemes for 40-50GHz Millimeter Wave Communication Systems

              
kean660

            

          

        
      


     

      

        
          

            

              Cascade Control Systems in Industrial Processes
            

            

              
Cascade Control Systems in Industrial Processes

              
ripperger_z

            

          

        
      


     

      

        
          

            

              Type Generality and Equality Types in Programming
            

            

              
Type Generality and Equality Types in Programming

              
eberwein_y

            

          

        
      


     

      

        
          

            

              Typed Assembly Language and Type Inference in Program Compilation
            

            

              
Typed Assembly Language and Type Inference in Program Compilation

              
kuperman_m

            

          

        
      


     

      

        
          

            

              Haskell Types, Classes, Functions, and Polymorphism
            

            

              
Haskell Types, Classes, Functions, and Polymorphism

              
halm_a

            

          

        
      


     

      

        
          

            

              Types and Classes in Haskell Programming
            

            

              
Types and Classes in Haskell Programming

              
petrovich_k

            

          

        
      


     							

						

					

					

				


				

			

		
		

			

				
				

					
More Related Content

					

						

														

					

				

				
			

		












 





  
  
  



giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#