Ecology lab



SemanticsWhat is Semantics?Syntax is about form semantics is about meaning of the languages features(not just about the syntax)how the programs behave when executed on computersBoundary between syntax & semantics is not always clearSyntax vs. Semantics in Regular EnglishWrong Syntax, ‘Correct Semantics’“I is a University Student”Correct Syntax, Wrong SemanticsSentence = Subject + verb + object“A rectangle loves chicken rice”Wrong Syntax, Wrong Semantics“House worm chair long fast twenty-two”Correct Syntax, Correct SemanticsLanguage Semanticswe want to “model” the language, see what the language can doappends semantic information onto the BNF description of a language since BNF can not handle everything about a languageTools on describing the semanticsinformalManuals, Tutorials, FAQS, etc..formalThere are three approaches to defining “deeper” semantics Operational semanticshow program is compiled by compiler “C” and run on Machine “M”steps of computation taken during executionAxiomatic semanticsprove that the program conforms to formal specifications using rules and axiomsDenotational semanticsthe meaning of the program is expressed as a collection of mathematical functionsBut why do we care?What would you include to make people use your language?A.??????ReadabilityB.??????DocumentationC.??????Fills a NicheD.??????CompatibilityE.???????Efficiency(Run Speed)F.???????SimplicityG.?????Memory ManagementH.??????ExamplesI.????????FeaturesAnswers (within):Motivation of Creating deeper SemanticsCapturing what a program in some programming language means is very difficultWe can’t really do it in any practical sense For most work-a-day programming languages (e.g., C, C++, Java, Perl, C#, Python)For large programsWhy even do this stuff??How to convey to the programming language compiler/interpreter writer what it should do?Natural language may be too ambiguousHow to know that the compiler/interpreter did the right thing when it executed our code?We can’t answer this w/o a very solid idea of what the right thing isHow to be sure that the program satisfies its specification?Maybe we can do this automatically if we know what the program meansOverall MotivationsTo provide programmers with an authoritative definition of the meaning of all the language constructsTo provide compiler writers with an authoritative definition of the meaning of all constructs, thus avoiding implementation differencesTo provide a basis for standardizing the languageDescribing a Language #1 - Program Verificationanother way of describing a languagethink of it as debugging, that the program does indeed behaves the way it is required while testing hardware too!!!is the process of formally proving that the computer program does exactly what is stated in the program’s specificationcan be done for simple programming languages and small or moderately sized programsrequires a formal specification for what the program should do its inputs and the actions to take or output to generate given the inputsThat’s a hard task in itself!There are applications where it is worth ituse a simplified programming languagework out formal specs for a programcapture the semantics of the simplified PL anddo the hard work of putting it all together and proving program correctness.Like…Security and encryptionFinancial transactionsApplications on which lives depend (e.g., healthcare, aviation)Expensive, one-shot, un-repairable applications (e.g., Martian rover)Hardware design (e.g. Pentium chip)Applications that needed better verificationDouble Int kills the Ariane 5European Space Agency project in 199610 years and $7B to produceAriane 5, a giant rocket capable of hurling a pair of three-ton satellitesinto orbit with each launch and intended to give Europe supremacy in the commercial space businessthe rocket exploded in less than a minute into its maiden voyagecomputer program trying to stuff a 64-bit number into a 16-bit space.Patriot MissileClock inside hardware malfunctionIntel Pentium BugIn the mid 90’s a bug was found in the floating point hardware in Intel’slatest Pentium microprocessorUnfortunately, the bug was only found after many had been made and soldThe bug was subtle, effecting only the ninth decimal place of some computationsBut users caredIntel had to recall the chips, taking a $500M write-offThe correct value isHowever, the value returned by the flawed Pentium would be incorrect beyond four significant digits[9]:Find an example of a software issue that caused failure (and how much!)Overall goals of Program VerificationWhile automatic program verification is a long range goal …Which might be restricted to applications where the extra cost is justifiedshould try to design programming languages that help, rather than hinder, our ability to make progress in this area.continue research on the semantics of programming languages continue research the ability to prove program correctnessOperational SemanticsOperational Semantics Overviewdefinitionsdescribe the meaning of a program in language L by specifying how statements effect the state of a machine (simulated or actual) when executed.the purpose of operational semantics is to describe how a computation is performed.The change in the state of the machine (memory, registers, stack, heap, etc.) defines the meaning of the statementoperations on hypothetical machine (simulation) or “Virtual machine”Similar in spirit to the notion of a Turing Machine and also used informally to explain higher-level constructs in terms of simpler ones.Example Operation Semanticsc statementoperational semanticsfor(e1;e2;e3) e1;{<body>} loop:if e2=0 goto exit <body> e3; goto loop exit:Requirements for Operational SemanticsTo use operational semantics for a high-level language, a virtual machine in neededA hardware pure interpreter is too expensiveA software pure interpreter also has problemsThe detailed characteristics of the particular computer makes actions hard to understandSuch a semantic definition would be machine-dependentA better alternative: a complete computer simulationBuild a translator (translates source code to the machine code of an idealized computer)Build a simulator for the idealized computerEvaluation of operational semantics:Good if used informallyExtremely complex if used formally (e.g. VDL)The basic idea is to define a language’s semantics in terms of a reference language, system or machineIt’s use ranges from the theoretical (e.g., lambda calculus) to the practical (e.g., Java Virtual Machine)Expression Semantics (by operation semantics)not all expressions are done or coded the SAME waywait until you get to Scheme!!expression tree (notation)while the “parse” tree” may look the same how the programming language handles it, will be differentExpression TreeWhat is the tree in prefix, infix, and postfix notation?Which of these really doesn’t show precedence?What would happen if we had a negative number? What’s the issue?introduction “Cambridge Notation”avoids the negative (unary) issue by having the operator always precede it’s operands and enclosing the entire expression in parentheses.basically prefix with ( )swon’t find much on web about itused in Scheme/Lisp( - ( + a b) ( * c d) )associativity using common addition, multiplication and comparison is the same across the boardleft to rightotherwise break mathematical foundationsbut these may not matchunaryusually right to left (-5)Booleanexponential (C has a function, Python has a symbol)remember, it’s reversed!!Associativity of OperatorsLanguage+ - * /(simple math)Unary (-/+)**(exponential)== != < ...(comparison)C-likeLR-LAdaLnonnonnonFortranLRRLprecedence of operatorseven this isn’t the same through the languages!!Precedence of OperatorsOperatorsC-likeAdaFortranUnary -733**-55* /644+ -533== !=422< <= ...322not722AND211OR111What do they all agree on thought? (precedence # may not match, but overall structure)short circuit evaluationleft to right comparison that stops as soon as the truth of the expression can be determinedsaves timedid you know at first compilers set it up that they still had to compare both!!Program Statemapping (table) ofthe pairing of active objects (variable names) with specific memory locationpairing off active memory locations with their current values“side effect”a change to any non-local variable or I/Ochange can be value, datatype, etc…c = a + b (in Python)int = int + intfloat = int + floatetc…c can have a side affectFor each line of this program, write the values of n, i, and f respectfully. BTW, lines 6 through 9 will repeat.// compute the factorial of n1 void main ( ) {2 int n, i, f; 3 n = 3;4 i = 1;5 f = 1;6 while (i < n) {7 i = i + 1;8 f = f * i;9 }10 }#nif1undefundefundef2undefundefundef345Assignment Semanticslanguages must cover the possibility ofmultiple assignmentsassignment statements vs. assignment expressionscopy vs. reference semanticsOther semantics you already knowsequenceconditionalsLoopsInput/Outputeach may be different in code, but you already understand the usage and overall formAxiomatic SemanticsBased on formal logic (first order predicate calculus)Original purpose: formal program verificationApproach: Define axioms and inference rules in logic for each statement type in the language (to allow transformations of expressions to other expressions)The expressions are called assertions and are either Preconditions: An assertion before a statement states the relationships and constraints among variables that are true at that point in executionPostconditions: An assertion following a statementIt is a good tool for correctness proofs, and an excellent framework for reasoning about programsIt is much less useful for language users and compiler writersMeaning of Logic Symbols? implies (if … then …)? if and only if, is necessary and sufficient for, is equivalent to ∧ conjunction between propositions, means “and” ∨ disjunction between propositions, means “or” ? universal quantifier, means "for every", "for each", "for all" ? existential quantifier, means “there exists” ∴ therefore ∈ is an element of ? is not an element of notAxiomatic Semantics in Theoryuse this to prove the programing language is doing what it is supposed to doaxiom: statement accepted without proofAxiomatic Semantics using Floyd Hoare LogicAxiomatic semantics is based on Hoare Logic named after computer scientist Sir Tony HoareBased on triples that describe how execution of a statement changes the state of the computationHoare Logic SetupP is a logical statement of what’s true before executing S (Pre-Condition)Q is a logical expression describing what’s true after (Post-Condition)Since all depend on one another, we could solve for QGiven P and S determine QPGiven S and Q determine PWe will need this property to solve some conditionsWeakest Precondition (WP)A weakest precondition is the least restrictive precondition that will guarantee the post-conditionThe overall goal is to determine the preconditions {P?} that satisfies the post condition {Q} using the statement {S} in between.Symbol Definitions (Syntactic Conventions)SymbolMeaningExampleV ; V1; ... ; Vnarbitrary variablesX, R, Q etc…E;E1; ...;Enarbitrary expressions (or terms)X + 1; which denote values (usually numbers)S; S1; ...; Snarbitrary statementsX < Y ;X2 = 1 (T or F)C;C1; ...;Cnarbitrary commands of our programming languageBCondition(x < y)PPre-Condition{x< 3}QPost-Condition{ y < 12 }Complete Weakest Condition Examples (Assignment)440690043815Post-conditionPost-condition122336543027Pre-conditionPre-condition{x>0} x = x+1 {x>1}(note, since x is the ONLY variable, and is the one “assigned”, we solve for x)Usually either the Pre or POST will be missing in a problem.But we need to find the weakest of either. (Number line example, shown below)Different problems in solving for wpby axiomassignmentby inferencesequenceselection (Conditions)loopsaxioma logical statement that is assumed to be trueinferenceinferring the truth of one assertion on the basis of values of other assertionsWPs for Assignmentsone line assignment operators, form x := e in a programming language. {Qx->E} x := E {Q}Where Qx->E means the result of replacing all occurrences of x with E in QHints for Solving{P???} A = B {Q????}A is the PostCondition of the equationB is the Pre-condition of the equationSolving for the WP #1 (Assignment) {P?} x = x+1 {x>1}-- OR --{P?} x(total) = x(i)+1 {x>1}(which you know the answer already)Solve for variable in pre-condition portion of equation (x):{P?} x = x + 1; { x > 1}x + 1 > 1{ x > 0 }Solve for weakest condition:{ x > 0 } (since 1 is >, 1 is ok!!) Identify other possible preconditions:{ x > 1 }{ x > 2 }{ x > 3 } // all preconditions, but not the weakest!! (infinite # of precons!!)… Solve for weakest precondition:{P?} sum = 2 * x + 1 { sum > 1} Answer: { x > 0 }{P?} a = b / 2 – 1 { a < 10 } Answer: { b < 22 }{P?} x = 2 * y – 3 { x > 25 } Answer: { y > 14 }WP for Sequencesseveral line sequencesfor a sequence S1 ; S2; … Sn:WP for SequencesSetupExample{P1} S1 {P2}{P2} S2 {P3} {x < 2}y = 3 * x + 1;x = y + 3;{x < 10}the inference rule is:{P1} S1 {P2}, {P2} S2 {P3} {P1} S1; S2 {P3}in a nutshell, to get the ENTIRE sequence’s precondition, the precondition of the second statement {S2} is computed.this is then used as the postcondition for the first statement {S1} and the whole sequenceSolving for the WP #1 (Sequence){P? }y = 3 * x + 1;x = y + 3;{x < 10}(again, you know the answer already)Solve for {P?} for last statement {Sn}. (using assignment model of solving){P?} x = y + 3; {x < 10}y + 3 < 10;{ y < 7 }Use newly acquired and use for POST condition of previous statement {Sn-1}{P??} y = 3 * x + 1 { y < 7 }3 * x + 1 < 7x < 2Solve the wp for the following:{P?}a = 2 * b + 1;b = a – 3{b < 0}Answer: WP for ConditionsHere’s a rule for a conditional statementWP for ConditionsSetupExample{B P} S1 {Q}, {B P} S2 {Q}{P} if B then S1 else S2 {Q}// remember B is for condition{y>1}If x>0 then y=y-1 else y=y+1{y>0}And an example of its use for the statement{P} if x>0 then y=y-1 else y=y+1 {y>0}So the weakest precondition P can be deduced as follows:The postcondition of S1 and S2 is Q.The weakest precondition of S1 is x>0 y>1 and for S2 is x<=0 y>-1The rule of consequence and the fact that y>1 y>-1 supports the conclusionThat the weakest precondition for the entire conditional is y>1 .Solving for the WP #1 (Conditions){p?}If x>0 then y=y-1 else y=y+1{y>0}(again, you know the answer already)Solve for {P?} for first statement in then clause {Sn} and the Q. (using assignment model of solving){P?} y = y - 1 {y > 0}y - 1 > 0;{ y > 1 }Solve for each else in the structure using the same Q{P?} y = y + 1 {y > 0}y + 1 > 0;{ y > -1 }When all conditions are completed, pick:highest value needed if x > ?? form as your Ppick lowest value needed if x < ?? form as your Ppick the stronger (more restrictive) of the two pre-conditions.{P?} = { y > 1 }Compute the weakest precondition for the following if statement:{ P???}if (a == b) then b = 2 * a + 1;else b = 2 * a;{b > 1}Answer:weakest pre-condition for the “then” would be: a > 0weakest pre-condition for the “else” would be: a > 1/2Since both the “then” clause as well as the “else” clause must be satisfied, we need to take the stronger (more restrictive) of the two pre-conditions.Since a > 1/2 implies a > 0,but a > 0 does not imply that a > 1/2,then the weakest precondition that can guarantee the post-condition is a > 1/2.WP for (while) Loops number of iterations cannot always be determinedif it is know, you can “unroll” it like a sequencethe first goal to find the weakest condition is to find an assertion called a “loop invariant”For the loop construct {P} while B do S end {Q}the inference rule is: {I B} S {I} _ {I} while B do S {I B}where I is the loop invariant, a proposition necessarily true throughout the loop’s executionI is true before the loop executes and also after the loop executesB is false after the loop executesLoop Invariants in While LoopsA loop invariant I must meet the following conditions:P => I (the loop invariant must be true initially, in order to run the loop) {I} B {I} (evaluation of the Boolean must not change the validity of I){I and B} S {I} (I is not changed by executing the body of the loop)(I and (not B)) => Q (if I is true and B is false, Q is implied)The loop terminates (this can be difficult to prove)The loop invariant I is a weakened version of the loop postcondition, and it is also a precondition.I must be weak enough to be satisfied prior to the beginning of the loop, but when combined with the loop exit condition, it must be strong enough to force the truth of the postconditionFYI - Sectionstuff we might get to, you need to readLogic 101Propositional logic:Logical constants: true, falsePropositional symbols: P, Q, S, ... that are either true or falseLogical connectives: (and) , (or), (implies), (is equivalent), (not) which are defined by the truth tables below.Sentences are formed by combining propositional symbols, connectives and parentheses and are either true or false. e.g.: PQ (P Q)First order logic addsVariables which can range over objects in the domain of discourseQuantifiers including: (forall) and (there exists)Predicates to capture domain classes and relations (p) (q) pq (p q)x prime(x) y prime(y) y>xTruth TablesImplies & Equivalence ( => and <=> )Implies > “(p-> q)” can be used to translate to the followingIf p then q.p only if q.q if p.Whenever p, q.q provided that p.p is sufficient for q.q is necessary for p.The statement:? Your teacher tells you that "if you participate in class, then you will get extra points."?fact 1:?? "you participate in class."fact 2:?? "you get participation points."When is the teacher's statement true?1.? If you participate in class (fact 1 true) and you get extra points (fact 2 true) then the teacher's statement is true.2.? If you participate in class (fact 1 true) and you do not get extra points (fact 2 false), then the teacher did not tell the truth and the statement is false.3.? If you do not participate in class (fact 1 false), EITHER WAY we cannot judge the truth of the teacher's statement.? The teacher did not tell you what would happen if you did NOT participate in class.? Since we cannot accuse the teacher of making a false statement, we assign "true" to the statement.The Lambda CalculusThe first use of operational semantics was in the lambda calculusA formal system designed to investigate function definition, function application and recursion Introduced by Alonzo Church and Stephen Kleene in the 1930sThe lambda calculus can be called the smallest universal programming languageIt’s widely used today as a target for defining the semantics of a programming languageThe lambda calculus consists of a single transformation rule (variable substitution) and a single function definition scheme The lambda calculus is universal in the sense that any computable function can be expressed and evaluated using this formalismWe’ll revisit the lambda calculus later in the courseThe Lisp language is close to the lambda calculus modelThe lambda calculus introduces variables ranging over valuesdefines functions by (lambda) abstracting over variablesapplies functions to valuesThe Visual C++ compiler binds a lambda expression to its captured variables when the expression is declared instead of when the expression is called.basically you create a function “on the fly” without creating a separate procedure, it is local!!!Lambda Calculus Example in C++// declaring_lambda_expressions2.cpp// compile with: /EHsc#include <iostream>#include <functional>int main(){ using namespace std; int i = 3; int j = 5; // The following lambda expression captures i by value and // j by reference. function<int (void)> f = [i, &j] { return i + j; }; // Change the values of i and j. i = 22; j = 44; // Call f and print its result. cout << f() << endl;}The lambda expression that captures the local variable i by value and the local variable j by reference. Because the lambda expression captures i by value, the reassignment of i later in the program does not affect the result of the expression. However, because the lambda expression captures j by reference, the reassignment of j does affect the result of the expression.Alan Turing and his MachineThe Turing machine is an abstract machine introduced in 1936 by Alan TuringAlan Turing (1912 –54) was a British mathematician, logician, cryptographer, considered a father of modern computer scienceIt can be used to give a mathematically precise definition of algorithm or 'mechanical procedure’Concept widely used in theoretical computer science, especially in complexitytheory and the theory of computationTuring example and testing JFlap tool to create a Turing machine First Real Example of an DFSM DiagramThe machine has 4 states (0, 1, 2, and 3, written as q0, q1, q2, q3).? Its start state is q0.?The double-circled state is the accept state, which in this case also happens to be q0 input string is "01", machine accepts the stringinput string is "110".? ends in a non-accept state, machine does not acceptSources Tables: Abstract Trees: ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download