Centralized vs. DecentralizedDefining a pictureDefining a Language for PicturesInterpreter PatternObject-Oriented InterpretersSlide 6Example: ValueModelsValueModelsExample: Regular Expression CheckerRegular Expression ClassesRegular Expression ObjectsMatchingSlide 13(continued)Slide 15Slide 16Slide 17Protocol for Building TreeInterface methodInterface methodsSlide 21Replacing Cases with SubclassesSlide 23How To Centralize AlgorithmsWhen to Centralize AlgorithmVisitor patternSlide 27Slide 28REVisitor and MatchVisitorSlide 30Slide 31Slide 32FixVisitorVisitor as a refactoringSlide 35CommentsVisitor PatternParseTreeEnumeratorVisualWorks GUI SpecsSlide 40SummaryCentralized vs. DecentralizedInterpreter PatternVisitor PatternDefining a pictureTextFig.TextFig.DrawingDrawingCompFig.CompFig.CompFig.CompFig.RectangleFig.RectangleFig.TextFig.TextFig.RectangleFig.RectangleFig.Defining a Language for PicturesFigure - displayOn: is abstract methodCompositeFigureDrawingRectangleFigureTextFigureInterpreter PatternTree of objects is a kind of programInterpret program by sending message to root, which is recursively sent to entire tree.Not about parsing!!!Object-Oriented InterpretersTo write a little object-oriented interpreter for a language L:1) make a subclass of LParseNode for each rule in the grammar of L2) for each subclass, define an interpreter method that takes the current context as an argument.Object-Oriented Interpreters3) define protocol for making a tree of LParseNodes.4) define a program for L by building an abstract syntax tree.Example: ValueModelsValueModelValueModelvaluevalueValueHolderValueHoldervaluevaluevaluevalueBlockValueBlockValueblockblockargumentsargumentsvaluevalueValueModels| x y |x := 3 asValue.y := 7 asValue.x + yValueModel>> + aValue^ BlockValue block: [:a :b | a value * b value] arguments: (Array with: self with: aValue asValue)ValueHolderBlockValueValueHolderExample: Regular Expression CheckerGrammar: exp ::= string | exp ‘+’ exp | exp ‘&’ exp | exp ‘repeat’ Step 1: define RegExpNode, MatchRENode, AlternationRENode, SequenceRENode, RepeatRENodeStep 2: define a match: method for each class that takes an input state as an argumentRegular Expression ClassesRegExpNodeRegExpNodeSequenceRENodeSequenceRENodeMatchMatchMatchMatchMatchRENodeMatchRENodecontentscontentsMatchMatchRepeatRENodeRepeatRENodeMatchMatchAlternationRENodeAlternationRENodeMatchMatchRegular Expression Objects'this is a ' ('very ' *) ('big ’ + 'small ') ('dog' + 'cat' + 'mouse')'this is a ' ('very ' *) ('big ’ + 'small ') ('dog' + 'cat' + 'mouse')SequenceRENodeSequenceRENodeMatchRENodeMatchRENode'this is a ''this is a 'RepeatRENodeRepeatRENodeMatchRENodeMatchRENode'big ''big 'AlternationRENodeAlternationRENodeAlternationRENodeAlternationRENodeMatchRENodeMatchRENode'small ''small 'MatchRENodeMatchRENode'very ''very 'MatchRENodeMatchRENode'dog''dog'MatchRENodeMatchRENode'mouse'mouseMatchRENodeMatchRENode'cat''cat'this is a very very very big mousethis is a very very very big mouseMatchingSequenceRENode>>match: inputState^components inject: inputState into: [:nextState :exp | exp match: nextState]MatchingRepeatRENode>>match: inputState| aState finalState |aState := inputState.finalState := inputState copy....(continued)[aState notEmpty] whileTrue: [aState := component match: aState. finalState addAll: aState].^finalStateMatchingAlternationRENode>>match: inputState| finalState |finalState := REState new.components do: [ :exp | finalState addAll: (exp match: inputState)]^finalStateMatchingMatchRENode>>match: inputState| finalState tStream |finalState := REState new....REState is a collection of streams.(continued)inputStatedo: [:stream | tStream := stream copy.(tStream nextAvailable: components size) = components ifTrue: [finalState add: tStream]].^finalStateProtocol for Building TreeDefine ”+" and "repeat" and ”&" as methods on RegExpNodes and any literals that are to be treated as patterns, such as strings.Then (('dog ' + 'cat ') repeat & 'weather') matches: 'dog dog cat weather' is true.Interface methodRegExpNode>>matches: anArg| inputState |inputState := (streamOrCollection isKindOf: Collection)ifTrue: [REState with: (ReadStream on: streamOrCollection)]ifFalse: [REState with: streamOrCollection].(self match: inputState) do: [:stream | stream atEnd ifTrue: [^true]].^falseInterface methodsDefine +, &, repeat, and asRENode in RegExpNode and String+ anArg^AlternationRENode new components: (Array with: self with: anArg asRENode)Other examples of Interpreter pattern:• producing Postscript for a document• figuring out the value of an insurance policy• spreadsheet• compiling a programC program would use case statementReplacing Cases with SubclassesAdvantages• instead of modifying case statements, add a new subclass• easier to parameterize• can use inheritance to make new optionsReplacing Cases with SubclassesDisadvantages• program is spread out,+ harder to understand+ harder to replace algorithm• state of object can change, but class can notHow To Centralize AlgorithmsDefine isAlternative, isRepeat, isSequence, isMatch, childrenDo:fix: anRENodeanRENode isMatch ifTrue: [anRENode contents: (anRENode contents capitalize)]ifFalse: [anRENode childrenDo: [:child | self fix: child]]When to Centralize AlgorithmUse centralized algorithm when you need to • change entire algorithm at once• look at entire algorithm at once• change algorithm, but not add new classes of componentsVisitor patternVisitor lets you centralize algorithm, lets you create a family of algorithms by inheritance, and makes it easy to create new algorithms.Major problem is that adding a new kind of parse node requires adding a new method to each visitor.Visitor pattern• two kinds of classes: nodes and node visitor• nodes have accept: method with visitor as an argument• accept: method sends visit messageSequenceRENode>>accept: aVisitoraVisitor visitSequence: selfVisitor pattern• each node class sends a different visit message to visitorvisitSequence:, visitAlternation:, visitRepetition:, visitMatch:• visitor defines a visit method for each class of parse tree node• uses double dispatchingREVisitor and MatchVisitorAn REVisitor implements visitSequence:, visitAlternation:, visitRepetition:, visitMatch:MatchVisitor is an REVisitor with one instance variable, state, and methods to access it.MatchVisitor>>visitSequence: sequence^state := sequence components inject: state into: