Kiến trúc máy tính và hợp ngữ - Chapter 6: Type systems

Programming Languages2nd editionTucker and NoonanChapter 6Type SystemsI was eventually persuaded of the need to design programming notations so as to maximize the number of errors that cannot be made, or if made, can be reliably detected at compile time. C.A.R HoareContents6.1 Type System for Clite6.2 Implicit Type Conversion6.3 Formalizing the Clite Type SystemMotivation: Detecting Type ErrorsThe detection of type errors, either at compile time or at run time, is called type checking.Type errors occur frequently in programs.Type errors can’t be prevented/detected by EBNFIf undetected, type errors can cause severe run-time errors.A type system can identify type errors before they occur.6.1 Type System for CLiteStatic bindingSingle function: mainSingle scope: no nesting, no globalsName resolution errors detected at compile timeEach declared variable must have a unique identifierIdentifier must not be a keyword (syntactically enforced)Each variable referenced must be declared.Example Clite Program (Fig 6.1)// compute the factorial of integer nvoid main ( ) { int n, i, result; n = 8; i = 1; result = 1; while (i , , }Can implement as a hash tableFunction typing creates a type mapFunction typeOf retrieves the type of a variable: typeOf(id) = type public static TypeMap typing (Declarations d) { TypeMap map = new TypeMap( ); for (Declaration di : d) { map.put (di.v, di.t); } return map;}The typing Function creates a type mapType Rule 6.2All declared variables must have unique names.public static void V (Declarations d) { for (int i=0; i<d.size() - 1; i++) for (int j=i+1; j<d.size(); j++) { Declaration di = d.get(i); Declaration dj = d.get(j); check( ! (di.v.equals(dj.v)), "duplicate declaration: " + dj.v); }}Rule 6.2 example// compute the factorial of integer nvoid main ( ) { int n, i, result; n = 8; i = 1; result = 1; while (i < n) { i = i + 1; result = result * i; }}These must all be uniqueType Rule 6.3A program is valid ifits Declarations are valid andits Block body is valid with respect to the type map for those Declarationspublic static void V (Program p) { V (p.decpart); V (p.body, typing (p.decpart));}Rule 6.3 Example// compute the factorial of integer nvoid main ( ) { int n, i, result; n = 8; i = 1; result = 1; while (i < n) { i = i + 1; result = result * i; }}These must be valid.Type Rule 6.4Validity of a Statement:A Skip is always validAn Assignment is valid if:Its target Variable is declaredIts source Expression is validIf the target Variable is float, then the type of the source Expression must be either float or intOtherwise if the target Variable is int, then the type of the source Expression must be either int or charOtherwise the target Variable must have the same type as the source Expression. A Conditional is valid if:Its test Expression is valid and has type boolIts thenbranch and elsebranch Statements are validA Loop is valid if:Its test Expression is valid and has type boolIts Statement body is validA Block is valid if all its Statements are valid.Type Rule 6.4 (continued)Rule 6.4 Example// compute the factorial of integer nvoid main ( ) { int n, i, result; n = 8; i = 1; result = 1; while (i < n) { i = i + 1; result = result * i; }}This assignment is valid if: n is declared, 8 is valid, and the type of 8 is int or char (since n is int).Rule 6.4 Example// compute the factorial of integer nvoid main ( ) { int n, i, result; n = 8; i = 1; result = 1; while (i < n) { i = i + 1; result = result * i; }}This loop is valid if i < n is valid, i < n has type bool, and the loop body is validType Rule 6.5Validity of an Expression:A Value is always valid.A Variable is valid if it appears in the type map.A Binary is valid if:Its Expressions term1 and term2 are validIf its Operator op is arithmetic, then both Expressions must be either int or floatIf op is relational, then both Expressions must have the same typeIf op is && or ||, then both Expressions must be boolA Unary is valid if:Its Expression term is valid,Type Rule 6.6The type of an Expression e is:If e is a Value, then the type of that Value.If e is a Variable, then the type of that Variable.If e is a Binary op term1 term2, then:If op is arithmetic, then the (common) type of term1 or term2If op is relational, && or ||, then boolIf e is a Unary op term, then:If op is ! then boolRule 6.5 and 6.6 Example// compute the factorial of integer nvoid main ( ) { int n, i, result; n = 8; i = 1; result = 1; while (i < n) { i = i + 1; result = result * i; }}This Expression is valid since: op is arithmetic (*) and the types of i and result are int.Its result type is int since: the type of i is int.6.2 Implicit Type ConversionClite Assignment supports implicit widening conversionsWe can transform the abstract syntax tree to insert explicit conversions as needed.The types of the target variable and source expression govern what to insert.Suppose we have an assignment f = i - int(c); (f, i, and c are float, int, and char variables).The abstract syntax tree is:Example: Assignment of int to floatSo an implicit widening is inserted to transform the tree to:Here, c2i denotes conversion from char to int, anditof denotes conversion from int to float.Note: c2i is an explicit conversion given by the operator int() in the program.Example (cont’d)