DOC PREVIEW
U of I CS 421 - Lecture

This preview shows page 1-2-3-4-5-32-33-34-35-64-65-66-67-68 out of 68 pages.

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

Unformatted text preview:

Programming Languages and Compilers (CS 421)Why Data Types?TerminologyTypes as SpecificationsSound Type SystemStrongly Typed LanguageSlide 7Static vs Dynamic TypesType CheckingSlide 10Dynamic Type CheckingSlide 12Static Type CheckingSlide 14Slide 15Type DeclarationsType InferenceFormat of Type JudgmentsExample Valid Type JudgmentsFormat of Typing RulesSlide 21Axioms - ConstantsAxioms - VariablesSimple Rules - ArithmeticSimple Rules - BooleansSimple ExampleSlide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Type Variables in RulesFunction ApplicationApplication ExamplesFun RuleFun ExamplesLet and Let RecMia CopaExampleSlide 56Proof of 1Slide 58Proof of 3Proof of 4Proof of 2Proof of 5Slide 63Slide 64Proof of 6Proof of 7Curry - Howard IsomorphismSlide 68Programming Languages and Compilers (CS 421)Elsa L Gunter2112 SC, UIUChttp://www.cs.uiuc.edu/class/sp07/cs421/Based in part on slides by Mattox Beckman, as updated by Vikram Adve and Gul AghaElsa L. Gunter Why Data Types?•Data types play a key role in:–Data abstraction in the design of programs–Type checking in the analysis of programs–Compile-time code generation in the translation and execution of programsElsa L. Gunter Terminology•Type: A type t defines a set of possible data values–E.g. short in C is {x| 215 - 1  x  -215}–A value in this set is said to have type t•Type system: rules of a language assigning types to expressionsElsa L. Gunter Types as Specifications•Types describe properties•Different type systems describe different properties, eg–Data is read-write versus read-only–Operation has authority to access data–Data came from “right” source–Operation might or could not raise an exception•Common type systems focus on types describing same data layout and access methodsElsa L. Gunter Sound Type System•If an expression is assigned type t, and it evaluates to a value v, then v is in the set of values defined by t•SML, OCAML, Scheme and Ada have sound type systems•Most implementations of C and C++ do notElsa L. Gunter Strongly Typed Language•When no application of an operator to arguments can lead to a run-time type error, language is strongly typed–Eg: 1 + 2.3;;•Depends on definition of “type error”Elsa L. Gunter Strongly Typed Language•C++ claimed to be “strongly typed”, but –Union types allow creating a value at one type and using it at another–Type coercions may cause unexpected (undesirable) effects–No array bounds check (in fact, no runtime checks at all)•SML, OCAML “strongly typed” but still must do dynamic array bounds checks, runtime type case analysis, and other checksElsa L. Gunter Static vs Dynamic Types•Static type: type assigned to an expression at compile time•Dynamic type: type assigned to a storage location at run time•Statically typed language: static type assigned to every expression at compile time•Dynamically typed language: type of an expression determined at run timeElsa L. Gunter Type Checking•When is op(arg1,…,argn) allowed?•Type checking assures that operations are applied to the right number of arguments of the right types–Right type may mean same type as was specified, or may mean that there is a predefined implicit coercion that will be applied•Used to resolve overloaded operationsElsa L. Gunter Type Checking•Type checking may be done statically at compile time or dynamically at run time•Dynamically typed (aka untyped) languages (eg LISP, Prolog) do only dynamic type checking•Statically typed languages can do most type checking staticallyElsa L. Gunter Dynamic Type Checking•Performed at run-time before each operation is applied•Types of variables and operations left unspecified until run-time– Same variable may be used at different typesElsa L. Gunter Dynamic Type Checking•Data object must contain type information•Errors aren’t detected until violating application is executed (maybe years after the code was written)Elsa L. Gunter Static Type Checking•Performed after parsing, before code generation•Type of every variable and signature of every operator must be known at compile timeElsa L. Gunter Static Type Checking•Can eliminate need to store type information in data object if no dynamic type checking is needed•Catches many programming errors at earliest point•Can’t check types that depend on dynamically computed values–Eg: array boundsElsa L. Gunter Static Type Checking•Typically places restrictions on languages–Garbage collection–References instead of pointers–All variables initialized when created–Variable only used at one type•Union types allow for work-arounds, but effectively introduce dynamic type checksElsa L. Gunter Type Declarations•Type declarations: explicit assignment of types to variables (signatures to functions) in the code of a program–Must be checked in a strongly typed language–Often not necessary for strong typing or even static typing (depends on the type system)Elsa L. Gunter Type Inference•Type inference: A program analysis to assign a type to an expression from the program context of the expression–Fully static type inference first introduced by Robin Miller in ML–Haskle, OCAML, SML all use type inference•Records are a problem for type inferenceElsa L. Gunter Format of Type Judgments•A type judgment has the form  |- exp : •  is a typing environment–Supplies the types of variables and functions–  is a list of the form [ x :  , . . .]•exp is a program expression•  is a type to be assigned to exp•|- pronounced “turnstyle”, or “entails” (or “satisfies”)Elsa L. Gunter Example Valid Type Judgments•[ ] |- true or false : bool•[ x : int] |- x + 3 : int•[ p : int -> string ] |- p(5) : stringElsa L. Gunter Format of Typing RulesAssumptions 1 |- exp1 : 1 . . . n |- expn : n  |- exp : Conclusion•Idea: Type of expression determined by type of components•Rule without assumptions is called an axiom•  may be omitted when not neededElsa L. Gunter Format of Typing RulesAssumptions 1 |- exp1 : 1 . . . n |- expn : n  |- exp : Conclusion• , exp,  are parameterized environments, expressions and types - i.e. may contain meta-variablesElsa L. Gunter Axioms - Constants|- n : int (assuming n is an integer


View Full Document

U of I CS 421 - Lecture

Documents in this Course
Lecture 2

Lecture 2

12 pages

Exams

Exams

20 pages

Lecture

Lecture

32 pages

Lecture

Lecture

21 pages

Lecture

Lecture

15 pages

Lecture

Lecture

4 pages

Lecture

Lecture

68 pages

Lecture

Lecture

84 pages

s

s

32 pages

Parsing

Parsing

52 pages

Lecture 2

Lecture 2

45 pages

Midterm

Midterm

13 pages

LECTURE

LECTURE

10 pages

Lecture

Lecture

5 pages

Lecture

Lecture

39 pages

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