Programentanglement,featureinteractionandtheFeature

1、1Program entanglement, feature interaction and the Feature Language Extensions (FLX)Francis LeungComputer ScienceIllinois Institute of Technology2Ideal Software DevelopmentModular ProgramminglEach functionality of an application can be developed as a reusable program module independent of other modu

2、leslEach new release is an integration of new modules and existing moduleslReality: the programs of different functionalities entangles in the same module; new releases are developed by changing existing code.Automated VerificationlThere is a tool that can automatically verify whether an application

3、 satisfies assertions about itlTodays software relies on case by case testing.3Why cant we use automated verifier like the hardware designers?HardwarelFinite state machinelBoolean logicSoftwarelState variables may not be bounded (e.g. integer)lMust reason on predicate logic whose variables have comp

4、lex data structures (e.g. Is the linked list empty?)4FLX approach to the verification problemAn executable FLX program is compiled into a finite state machine even if state variables are unbounded.A new first order satisfiability algorithm that does not require iterations of solving a SAT problem.W.

5、H. Leung, “On the Verifiability of Programs Written in the Feature Language Extensions,” HASE07.5OutlineIntroductionThe feature interaction problemThe foundation constructs of the Feature Language Extensions (FLX)Exception handling and extensibility in FLXConclusion6Some terminologyA feature is some

6、 functionality of an application. It is also called a concern, an aspect etc. in the literature.lCongestion control and reliable data transport are two features of TCPlPlain old telephone call, call forwarding are two features of a telephony applicationThe programs of two features are entangled if t

7、hey appear in the same method or function.When a feature is implemented by changing the code of another feature, it implies that their programs are entangled.7What It Takes to Add Features to SW TodayThe programmer develops Call Waiting by changing the code of POTSCall Forwarding is developed by cha

8、nging the code of Call Waiting and POTSRetry is developed by changing the code of Call Forwarding, Call Waiting and POTS, and so onThe programmer is not just implementing one feature. He must thoroughly understand change the code and test many featuresFeatures are not reusable without each otherlThe

9、y are “entangled”POTS as An Example8How does entangled code look like?9OutlineIntroductionlThe software verification challengelThe program entanglement problemThe feature interaction problemThe foundation constructs of the Feature Language Extensions (FLX)Exception handling and extensibility in FLXC

10、onclusion10Why Are We Still Writing Entangled Code?The programmer is not experiencedThe programmer is not well trainedThe programmer is not given enough time and resources.Because they use top-downIt is due to object oriented programmingIt is due to water fall“Whoever blames will later be blamed. Th

11、e times they are a changing” I. Bob DylanIt is because they do not follow a plan (agile programming)No, because they use bottom-upThe programmers cannot help it!11Entanglement Conditions*C1: If features interact;C2: Executed by the same sequential process; andC3: Implemented by a programming languag

12、e that require specification of execution flowsThe programs of these features will inevitably entangle.If features do not interact, their programs do not have to be entangled.*W. H. Leung, “Program entanglement, feature interaction and the Feature Language Extensions,” Computer Networks, Feb., 20071

13、2TerminologyTwo features interact if their behavior changes when integrated togetherA feature is implemented by computer programsThe behavior of a feature is its execution flow and output for a given inputAn interaction condition is a condition under which the behavior of the interacting features ch

14、anges.lvalue of variables, a particular point in the execution pathAn interaction condition is resolved by specification of the changed behavior13Examples of feature interactionAdding call forwarding or do not disturb changes the behave of POTS when the phone is calledAdding congestion control chang

15、es the behavior of reliable data transport when a duplicated acknowledgement is receivedAdding exception handling changes the behavior of the application program when the system throws an exceptionA new release typically will consist of new features that change the behavior of old features14Another

16、Example of Entangled CodeWhen a function throws a new exception, programs that call the function may have to be changedPrograms that transitively (indirectly) call the function may also have to be changedExisting programming languages offer very little help to programmersMany popular programs hang o

17、ften because exceptions are not handledFunction throws a new exception15What is the solution?Is it sufficient to put all the blue, green, orange and purple code into separate files (or modules)?To implement purple, you still have to go through and often times change blue, green and orange.Purple can

18、not be understood by itself.Purple cannot be reused without blue, green, and orange.16Requirements for solving the program entanglement problemProgrammers add features by changing the code of other featuresThey must manually read large amount of code to determine where to make the changesThe program

19、s of interacting features are entangled in the same reusable program unitFeatures cannot be reused without each otherThe programs of interacting features can be developed independent of one anotherThere is a tool to automatically detect feature interaction conditionsFeatures can be integrated withou

20、t changing the code of other featuresFeatures can be reused independent of one another17OutlineIntroductionlThe software verification challengelThe program entanglement problemThe feature interaction problemlThe entanglement conditionslRequirements for the solutionThe foundation constructs of the Fe

21、ature Language Extensions (FLX)Exception handling and extensibility in FLXConclusion18FLX is meant for feature rich componentsPhoneDigit AnalysisFeature PackageCall ProcessingFeature PackagePhone AgentRouter19FLX relaxes C3 and supports non-procedural programmingA program unit consists of a conditio

22、n and a program bodyWhen a condition becomes true, the corresponding program body is executedProgrammer does not sequence the execution order of the program unitsProgram Unit 1Program Unit 2Program Unit NCondition 1Condition 2Condition NProgram Body 1Program Body 2Program Body N.20An Example Program

23、 UnitIdleRingingTerm-requestReceiveCall condition: state.equals (State.IDLE);event: TerminationRequest e; Ringing r = new Ringing (e.FromPhoneID);rt.sendEvent ( r); state = State.RINGING; 21Features and feature packages written in FLX are reusableFeatures are written based on a model instead of the

24、code of other featuresFeatures and feature packages are integrated in a feature packageOne can integrate different combinations of features and feature packages into different feature packagescallwaiting3-wayhomeinter-comselectivcallforwardcallpick-upBasicTelephonyPOTSresidentialpackagebusinesspacka

25、geDomainAnchor feature22An Example Domain Statementdomain BasicTelephony variables: DTenum State (DIALING, OUTPULSING, BUSY, AUDIBLE, TALKING, RINGING, DISCONNECT, IDLE;State state = State.IDLE; events: TerminationRequest; Busy; Ringing;Answer;Disconnect; Onhook;Offhook;Digits;TimeOut;resources:Phon

26、e fone;Router rt;23An Anchor Featureanchor feature Pots domain BasicTelephony;MakeCall condition: state.equals(State.IDLE);event: Offhook; fone.applyDialTone();state = State.DIALING; ReceiveCall RingPhone OutpulseDigits 24An Example FeatureFeature DoNotDisturb domain BasicTelephony;anchorPots;SayBus

27、y condition: all;event: TerminationRequest e; Busy b = new Busy(e.FromPhoneID);rt.sendEvent ( b); 25An Example Feature Packagefeature package QuietPhone domain: BasicTelephony;features:DoNotDisturb, Pots, CatchAll;PriorityPrecedence DoNotDisturb, Pots, CatchAll;The priority precedence list specifies

28、 that when an interaction condition becomes true, the program unit belonging to the feature with the highest precedence gets executed.26Feature InteractionTwo program units interact if the conjunction of their condition parts is satisfiable.Two features interact if a program unit in one feature inte

29、racts with a program unit in the other feature.Do not disturbSayBusy condition: state.equals(State.IDLE);event: Term-request e; Busy b = new Busy(e.fromPID):rt.sendEvent (b); (2) Call Forwarding ForwardCall condition: state.equals (State.IDLE);event: Term-request e; If (forwardNumber != “” & for

30、wardNumber != e.fromPID) rt.send (forwardNumber, e); stop; 27Feature interaction resolution using program unitsfeature package SelectiveForwarding PriorityPrecedence: DND, CF, POTS;.selectToForward condition: state.equals(State.IDLE);event: Term-request e; if (phoneIDlist.contains(e.FromPhoneID) DND

31、; else CF; stop;28Straight PrecedenceWhen an interaction condition becomes true, program units of the features will be executed according to their precedence.feature Billing domain: BasicTelephony; anchor: POTS;StartMeter condition: state.equals(State.AUDIBLE); event: Answer e; CallRecord=new CallRe

32、cord (e.fromPID); meter.start (1 second); feature package NoFreeCalls domain:BasicTelephony; features: Billing,Pots; straightPrecedence (Billing, Pots);29Multiple precedence listsMultiple precedence lists may lead to order or type contradictions. Contradiction may be resolved by program units.featur

33、e package BilledQuietPhone domain: BasicTelephony;feature: DND, Billing, POTS, CatchAll;straightPrecedence (Billing, POTS);priorityPrecedence (Billing, CatchAll);priorityPrecedence (DND, POTS, CatchAll);30It is sufficient to only implement priority and straight precedence lists*All contradiction fre

34、e precedence list sets can be represented by a matrix like this.* L. Yang, A. Chaven, K. Ramachandra, W. H. Leung, Resolving feature interaction using precedence lists in the Feature Language Extensions,” ICFI07.31OutlineIntroductionlThe software verification challengelThe program entanglement probl

35、emThe feature interaction problemlThe entanglement conditionslRequirements for the solutionThe foundation constructs of the Feature Language Extensions (FLX)lModel: domain statement, anchor featurelFeatures and feature packageslPrecedence listsException handling and extensibility in FLXConclusion32R

36、eusable FLE exception features example 1exception feature CatchAll domain: BasicTelephony;anchor: Pots;catch condition: all;event: any; System.out.println (“CatchAll: unexpected condition and event”);this.dump (domain, event);33Reusable FLE exception featureexample 2exception feature DamageControl d

37、omain: RobustTelephony;anchor: Pots;illegalOnhook condition: state.NotEquals(State.IDLE);event: Onhook; System.out.println (“Illegal Onhook”);fone.disable ();stop ();brokenRingCkt condition: all;event: RingCktBrokenException e; System.out.println (“Major Alarm: Ring CKT broken:”, e.id); stop ();34Ex

38、tending a domain statementdomain RobustTelephony extends BasicTelephony exceptions:RingCKTBrokenException;ConfCKTBrokenException;/ and others35Putting them togetherfeature package RobustSCFdomain: RobustTelephony;features: SelectiveCallForwarding, DamageControl, CatchAll;PriorityPrecedence: DamageCo

39、ntrol, SelectiveForwarding, CatchAll;36Some properties of exception handling and extensibility in FLXException handlinglNormal processing features and exception handling features can be developed independentlylException features confines the scope of exceptionslExceptions handling does not have a di

40、fferent control flow modellSupports the complete set of termination modelsExtensibilitylA model can evolve without changing existing codelOriginal features can be integrated with features developed with the evolved model37OutlineIntroductionlThe software verification challengelThe program entanglement problemThe feature interaction problemlThe entanglement conditionslRequirements for the solutionThe foundation constructs of the Feature Language Extensions (FLX)lDom