Kĩ thuật lập trình - Chapter 8: Semantic interpretation

Programming Languages2nd editionTucker and NoonanChapter 8Semantic InterpretationTo understand a program you must become both the machine and the program. A. PerlisContents8.1 State Transformations and Partial Functions8.2 Semantics of Clite8.3 Semantics with Dynamic Typing8.4 A Formal Treatment of SemanticsDynamically Typed LanguagesScripting: Perl, Python, PHPObject-oriented: Smalltalk, RubyFunctional: Scheme, ML, HaskelLogic: PrologOur example: dynamically typed C++Lite int main( ) { n =3; i =1; f = 1.0; while (i < n) { i = i + 1; f = f * float(i); }}Step Stmt n i f1 3 -- -- --2 4 3 -- --3 5 3 1 --4 6 3 1 1.05 7 3 1 1.06 8 3 2 1.07 6 3 2 2.08 7 3 2 2.0Step Stmt n i f9 8 3 3 2.010 6 3 3 6.011 10 3 3 6.0 Perl vs. PythonPerl: implicit conversions, distinct operators“2” < “10” : true – numeric comparison“2” lt “10” : false – string comparison2 lt “10” : false – 2 converted to “2”Python: explicit conversions required“2” < “10” : false – string comparison2 < “10” : errorMeaning Rule 8.10The meaning of a Program is the meaning of its body when given an empty initial state.Variables declared as encounteredType of a variable is type of is valueIn factorial:i, n – intf – float C++DynamicStatement = Skip | Block | Assignment | Conditional |LoopSkip, Block unchangedConditional, Loop – check that test is boolAssignment add target variable to state, if neededno assignment compatibility check needed???Meaning Rule 8.11The meaning of an expression in the current state is a value defied as follows:If the expression is a value, then the value itselfIf the expression is a Variable:If the Variable occurs in the current state, then its associated value.Otherwise the program is meaninglessMeaning Rule 8.11If the expression is a binary:Determine the value of term1, term2 in current stateApply Rule 4.12 to the operator and valuesIf the expression is a unary:Determine the value of term in current stateApply Rule 4.13 to the operator and valueSee dynamic-expr.javaMeaning Rule 8.12The meaning of a Binary Expression is a Value:If operator is arithmetic:If either operand is an int, both operands must be int; perform int addition for +, int subtraction for -, etc.If either operand is a float, both operands must be float; perform float addition for +, float subtraction for -, etc.... Value M (Expression e, State sigma) { if (e instanceof Value) return (Value)e; if (e instanceof Variable) { StaticTypeCheck.check( sigma.containsKey(e), "reference to undefined variable"); return (Value)(sigma.get(e)); } if (e instanceof Binary) { Binary b = (Binary)e; return applyBinary (b.op, M(b.term1, sigma), M(b.term2, sigma)); } if (e instanceof Unary) { Unary u = (Unary)e; return applyUnary(u.op, M(u.term, sigma)); } throw new IllegalArgumentException( "should never reach here");} Value applyBinary (Operator op, Value v1, Value v2) { StaticTypeCheck.check( v1.type( ) == v2.type( ), "mismatched types"); if (op.ArithmeticOp( )) { if (v1.type( ) == Type.INT) { if (op.val.equals(Operator.PLUS)) return new IntValue( v1.intValue( ) + v2.intValue( )); if (op.val.equals(Operator.MINUS)) return new IntValue( v1.intValue( ) - v2.intValue( )); ...