1CS 580: Software SpecificationsOCL 4:Advanced OCL ExpressionsCopyright 2001-2002, Matt Dwyer, John Hatcliff, and Rod Howell. The syllabus and all lectures for this course are copyrighted materials and may not be used in other course settings outside of Kansas State University in their current form or modified form without the express written permission of one of the copyright holders. During this course, students are prohibited from selling notes to or being paid for taking notes by any person or commercial firm without the express written permission of one of the copyright holders. Used and modified with permission by Robert Stehwien2OutlineOutlineOutlineOutlineCoding transitive closure with recursionUseful expressionsUndefined valuesMeta-modeling…with the Academia model as the running example.3Transitive Closure in OCLTransitive Closure in OCLTransitive Closure in OCLTransitive Closure in OCLOCL does not have a primitive operation for transitive closureOCL does allow recursionWe must implement transitive closure directly in terms of recursion24Transitive Closure in OCLTransitive Closure in OCLTransitive Closure in OCLTransitive Closure in OCLConsider the following definitions (transitive-closure-1.use)class Aendassociation R betweenA role predA role succend We can attempt to code the transitive closure of R as followsclass Aoperations closure() : Set(A) = succ.closure()->asSet()->including(self)end5Transitive Closure in OCLTransitive Closure in OCLTransitive Closure in OCLTransitive Closure in OCLConsider the following instantiation (transitive-closure-instantiation-1.cmd)An example evaluation!create a1:A!create a2:A!create a3:A!insert (a1,a2) into R!insert (a2,a3) into Ruse> ? a1.closure()-> Set{@a1,@a2,@a3} : Set(A)6Transitive Closure in OCLTransitive Closure in OCLTransitive Closure in OCLTransitive Closure in OCLWhat is happening on a1.closure? Tracing the evaluation through the recursion…Level 1 call: self = a1, a1.succ = a2Level 2 call: self = a2, a2.succ = a3Level 3 call: self = a3, a3.succ = {} Level 3 return: Set{@a3} Level 2 return: Set{@a2,@a3} Level 1 return: Set{@a1,@a2,@a3}class Aoperations closure() : Set(A) = succ.closure()->asSet()->including(self)end37Demo Demo Demo Demo …………Load the model in transitive-closure-1.useinto USERun the script transitive-closure-instantiation-1.cmdNow give the following command at the USE command lineuse> ? a1.closure() what happens?Now give the following commands at the USE command lineuse> !insert (a3,a1) into Ruse> ? a1.closure()what happens? why? can you fix the problem?8Transitive Closure in OCLTransitive Closure in OCLTransitive Closure in OCLTransitive Closure in OCLConsider the following instantiation (transitive-closure-instantiation-2.cmd)An example evaluation!create a1:A!create a2:A!create a3:A!insert (a1,a2) into R!insert (a2,a3) into R!insert (a3,a1) into Ruse> ? a1.closure()…java.lang.RuntimeException: StackOverflow…9AssessmentAssessmentAssessmentAssessmentThe problem is that we have an infinite path through Rand the closureoperation doesn’t know how to stop.Intuitively, we should stop when we have collected all the elements that we encounter when walking across R starting from the initial value (e.g., a1).In other words, we should stop when we don’t find anything “new” when walking across R.410IfIfIfIf----thenthenthenthen----elseelseelseelseif bool-exprthen expr1else expr2endifReturns expr1if bool-expris trueReturns expr2 if bool-exprif falseUndefined if bool-expris undefined…we can use the if-then-else construct to help us code an appropriate transitive closure operation11Transitive Closure in OCLTransitive Closure in OCLTransitive Closure in OCLTransitive Closure in OCLThe correct coding of (reflexive) transitive closureclosure(s : Set(A)) : Set(A) =closure(s : Set(A)) : Set(A) =closure(s : Set(A)) : Set(A) =closure(s : Set(A)) : Set(A) =if sif sif sif s---->>>>includesAll(s.succincludesAll(s.succincludesAll(s.succincludesAll(s.succ---->>>>asSetasSetasSetasSet) then s) then s) then s) then selse closure(selse closure(selse closure(selse closure(s---->>>>union(s.succunion(s.succunion(s.succunion(s.succ---->>>>asSetasSetasSetasSet))))))))endifendifendifendifNote: the closure is reflexive because argument s must be included in the resultreachableFromSelfreachableFromSelfreachableFromSelfreachableFromSelf() : Set(A) = closure(Set{self})() : Set(A) = closure(Set{self})() : Set(A) = closure(Set{self})() : Set(A) = closure(Set{self})An initial call to compute reflexive transitive closure of {self}Note: stop when we don’t find anything new via R (succ) to add to s.12Transitive Closure in OCLTransitive Closure in OCLTransitive Closure in OCLTransitive Closure in OCLWhat is happening on a1.reachableFromSelf() ? Tracing the evaluation through the recursion…Level 1 call: s = {@a1}, s.succ = {@a2}Level 2 call: s = {@a1,@a2}, s.succ = {@a2,@a3}Level 3 call: s = {@a1,@a2,@a3}, s.succ = {@a1,@a2,@a3} Level 3 return: Set{@a1,@a2,@a3}Level 2 return: Set{@a1,@a2,@a3} Level 1 return: Set{@a1,@a2,@a3}class Aclass Aclass Aclass Aoperations operations operations operations closure(s : Set(A)) : Set(A) =closure(s : Set(A)) : Set(A) =closure(s : Set(A)) : Set(A) =closure(s : Set(A)) : Set(A) =if sif sif sif s---->>>>includesAll(s.succincludesAll(s.succincludesAll(s.succincludesAll(s.succ---->>>>asSetasSetasSetasSet) then s) then s) then s) then selse closure(selse closure(selse closure(selse closure(s---->>>>union(s.succunion(s.succunion(s.succunion(s.succ---->>>>asSetasSetasSetasSet))))))))endifendifendifendifreachableFromSelfreachableFromSelfreachableFromSelfreachableFromSelf() : Set(A) = closure(Set{self})() : Set(A) = closure(Set{self})() : Set(A) = closure(Set{self})() : Set(A) = closure(Set{self})endendendend513For You To DoFor You To DoFor You To DoFor You To Do…………Load the model in transitive-closure-2.useinto USERun the script transitive-closure-instantiation-2.cmdNote that this script adds (a3,a1) to R to create a cycle in RNow give the following command at the USE command lineuse> ? a1.reachableFromSelf() what happens? why?14Enumeration Types Enumeration Types Enumeration Types Enumeration Types (per OCL spec)(per OCL spec)(per OCL spec)(per OCL spec)General Formenum {value1, value2, …, valuen}Example: Academia Gradesenum {A, B, C, D, F, X, W}Enumeration Values#A, #B, #C, #D, #F, #X, #W15Enumeration Types
View Full Document