---- {{#t|Design Patterns - Using FAST}} ---- {{#x|Design Patterns}} in ☺{{#c|FAST}}☺ {{#t|Agent Zhang}} {{#date|2006.4}} ---- What is {{#c|Design Pattern}}? ---- {{#ct|Proven}} design {{#x|idioms}} for software development ---- Has its root in {{#c|architecture}}... ---- {{img src="#" width="0" height="0"}} {{img src="images/asia01.jpg" width="150" height="200"}} {{img src="images/asia02.jpg" width="150" height="200"}} {{img src="images/asia03.jpg" width="150" height="200"}} {{img src="images/asia04.jpg" width="150" height="200"}} ---- The {{#ct|famous}} book... ---- {{img src="images/book.gif" width="389" height="502"}} ---- Why {{#ct|Design Pattern}}? ---- Design Patterns {{#c|✓ Robustness}} ---- Something {{#x|proven}} to work is always {{#ci|nice}}! ---- Design Patterns {{#c|✓ Efficiency}} ---- We needn't start from {{#ui|scratch}} {{#c|every time}}! ---- Design Patterns {{#c|✓ Laziness}} ---- {{img src="#" width="0" height="0"}} {{img src="images/laziness.jpg" width="450" height="309"}} ---- Never {{#c|reinvent}} the wheels! ---- But... {{#c|wait}}... ---- What is {{#c|FAST}}? ---- {{#x|F}}lowchart {{#x|A}}sbtract {{#x|S}}yntax {{#x|T}}ree {{#ci|transformer}} {{#x|♨}} ---- Recall our {{#ct|second}} homework for Programming Methodology... ---- Given an {{#c|arbitrary}} flowchart program ---- {{#c|⇒}} ---- {{img src="images/homework.png" width="556" height="249"}} ---- We were asked to convert that to a {{#ci|structural}} program ---- {{#c|⇒}} ---- {{img src="#" width="0" height="0"}} {{img src="images/homework.unopt.png" width="291" height="609"}} ---- And also a {{#ci|recursive}} {{#x|structural}} program ---- {{#c|⇒}} ---- {{img src="#" width="0" height="0"}} {{img src="images/homework.opt.png" width="296" height="615"}} ---- {{#c|☺}} ---- {{#c|Any}} problems of this category can be solved by {{#x|FAST}} ! ---- {{#x|FAST}} is powered by {{#c|mature}} design patterns ---- FAST {{#c|✓ Robustness}} ---- FAST passes {{#c|500+}} tests ---- FAST {{#c|✓ Efficiency}} ---- {{#x|FAST}}'s core was done in {{#ct|3}} days! ---- FAST {{#c|✓ Laziness}} ---- {{#x|FAST}} is a frivolous project optimized for {{#ct|fun}} ---- One {{#c|Problem}}... ---- How to {{#ci|type}} the original flowchart {{#ci|into}} the machine? ---- {{img src="#" width="0" height="0"}} {{img src="images/homework.png" width="556" height="249"}} ---- Keyboard {{#x|sucks}}... ---- Drag and drop by a {{#x|mouse}} ? ---- {{#c|As in...}} ---- {{img src="#" width="0" height="0"}} {{img src="images/word.png" width="768" height="537"}} ---- GUI {{#ci|rocks}} for interfacing {{#x|beginners}} ---- Hmm, {{#x|however}}... {{img src="images/thinker.jpg" width="186" height="220"}} ---- {{#x|☹}} Economy ? ---- {{#x|☹}} Scalability? ---- {{#x|☹}} flexibility? ---- {{#x|☹}} Testability? ---- GUI {{#ci|sucks}} for {{#x|prototyping}} FAST ---- GUI {{#ci|sucks}} for {{#x|testing}} FAST ---- GUI {{#ci|sucks}} for interfacing {{#x|apps}} ---- GUI {{#ci|sucks}} for {{#x|experienced}} users ---- Let's look {{#ci|back}}... ---- Does keyboard really {{#x|suck}} ? ---- $_ = $__.replace(/#x/, '#xs'); ---- Pattern #1 {{#c|♡ Interpreter}} ---- Given a language, define a representation for its {{#ci|grammar}} along with an {{#ci|interpreter}} that uses the representation to interpret sentences in the language. ---- Make a language of {{#ct|my own}} ! ---- That's a {{#ci|dream}} in my {{#x|childhood}}... {{img src="#" width="0" height="0"}} {{img src="images/chromatic.jpg" width="130" height="170"}} ---- Perhaps of {{#x|all}} the creations of man {{#ci|language}} is the most astonishing. -- {{#i|Giles Lytton Strachey}} ---- Why yet another {{#c|language}}? ---- FAST has a {{#ct|user language}} for entering flowcharts ---- {{img src="#" width="0" height="0"}} {{img src="images/homework01_code.png" width="146" height="296"}} {{img src="images/homework01.png" width="556" height="249"}} ---- {{img src="images/homework02_code.png" width="146" height="296"}} {{img src="images/homework02.png" width="556" height="249"}} ---- {{img src="images/homework03_code.png" width="146" height="296"}} {{img src="images/homework03.png" width="556" height="249"}} ---- {{img src="images/homework04_code.png" width="146" height="296"}} {{img src="images/homework04.png" width="556" height="249"}} ---- {{img src="images/homework05_code.png" width="146" height="296"}} {{img src="images/homework05.png" width="556" height="249"}} ---- {{img src="images/homework06_code.png" width="146" height="296"}} {{img src="images/homework06.png" width="556" height="249"}} ---- {{img src="images/homework07_code.png" width="146" height="296"}} {{img src="images/homework07.png" width="556" height="249"}} ---- {{img src="images/homework08_code.png" width="146" height="296"}} {{img src="images/homework08.png" width="556" height="249"}} ---- The {{#ci|grammar}} for this {{#x|mini-language}}... ---- {{#kw|program}} : {{#kw|statement}}(s) {{#kw|statement}} : {{#kw|node}} {{#x|'=>'}} {{#kw|node}} {{#kw|node}} : {{#x|'entry'}} | {{#x|'exit'}} | {{#x|'['}} {{#kw|string}} {{#x|']'}} | {{#x|'<'}} {{#kw|string}} {{#x|'>'}} {{#kw|string}} : {{#kw|char}}(s) ---- How to {{#ci|implement}} this {{#x|grammar}} ? ---- It's {{#ci|trivial}} if you're using {{#x|Perl}}! ---- It only costs me {{#ci|21}} {{#x|lines of code}} ! {{img src="images/monk.gif" width="148" height="182"}} ---- {{img src="images/parse.png" width="766" height="558"}} ---- {{#ci|Basic Usage}} of {{#x|FAST}} ---- {{#ci|1}} {{#x|input}} file ``{{#ci|bar}}'' ---- entry {{#c|=>}} <p> <p> {{#c|=>}} [f] [f] {{#c|=>}} [h] [h] {{#c|=>}} exit <p> {{#c|=>}} [g] [g] {{#c|=>}} <q> <q> {{#c|=>}} [h] <q> {{#c|=>}} exit ---- C:\> {{#c|fast}} {{#i|bar}} ---- {{#x|⇒}} ---- {{#ci|6}} {{#x|output}} files ! ---- bar ⇒ {{#x|bar.png}} ---- {{img src="images/homework.png" width="556" height="249"}} ---- bar ⇒ {{#x|bar.asm}} ---- {{#kw|test}} p {{#kw|jno}} L1 {{#kw|do}} f L2: {{#kw|do}} h L3: {{#kw|exit}} L1: {{#kw|do}} g {{#kw|test}} q {{#kw|jno}} L3 {{#kw|jmp}} L2 ---- bar ⇒ {{#x|bar.unopt.png}} ---- {{img src="images/homework.unopt.png" width="291" height="609"}} ---- bar ⇒ {{#x|bar.unopt.c}} ---- {{img src="images/homework.unopt.c.png" width="349" height="588"}} ---- bar ⇒ {{#x|bar.opt.png}} ---- {{img src="images/homework.opt.png" width="296" height="615"}} ---- bar ⇒ {{#x|bar.opt.c}} ---- {{#key|// bar.opt.c}} {{#kw|if}} (p) { {{#kw|do}} f {{#kw|do}} h } {{#kw|else}} { {{#kw|do}} g {{#kw|if}} (q) { {{#kw|do}} h } } ---- Looking into the {{#x|FAST}} {{#ci|Internals}}... ---- {{#x|Structural}} flowcharts are represented by {{#ci|trees}} ---- {{#ci|What}} do those {{#x|trees}} look like? ---- Pattern #2 {{#c|♡ Composite}} ---- Compose objects into {{#ci|tree}} structures to represent {{#x|part-whole}} hierarchies. Composite lets clients treat individual objects and compositions of objects {{#ci|uniformly}}. ---- Yeah, that's a story about {{#ci|trees}}... ---- {{img src="#" width="0" height="0"}} {{img src="images/realtree.jpg" width="665" height="592"}} ---- {{#ci|Every}} {{#x|structural}} flowchart can be represented by a {{#ci|tree}} ---- {{img src="images/fastast.c.png" width="248" height="423"}} {{img src="images/fastast.png" width="577" height="456"}} ---- {{#ci|Every}} node is also a {{#x|tree}}. ☼ ---- {{img src="images/fastast01.png" width="577" height="456"}} ---- {{#ci|Every}} tree is represented by its {{#x|root node}}. ☼ ---- {{img src="images/fastast02.png" width="577" height="456"}} ---- {{#x|Hence...}} {{img src="images/hence.jpg" width="188" height="220"}} ---- {{#x|Trees}} and {{#x|nodes}} share the {{#ci|same}} interface. ☼ ---- There is {{#ci|no}} {{#x|Tree}} class any more ---- As {{#x|evidenced}} in the {{#ci|UML}} thingy... ---- {{img src="images/uml.png" width="470" height="616"}} ---- Composite Pattern {{#c|✓ Building the tree is easy}} ---- FAST::Element* If = {{#kw|new}} {{#c|FAST::Struct::If}}({{#x|"<L=1>"}}, {{#x|"[a]"}}, {{#x|"[b]"}}); +{{img src="images/tree01.png" width="453" height="211"}} ---- FAST::Element* If = {{#kw|new}} {{#c|FAST::Struct::If}}({{#x|"<L=1>"}}, {{#x|"[a]"}}, {{#x|"[b]"}}); FAST::Element* While = {{#kw|new}} {{#c|FAST::Struct::While}}({{#x|"<L>0>"}}, {{#x|If}}); +{{img src="images/tree02.png" width="488" height="333"}} ---- FAST::Element* If = {{#kw|new}} {{#c|FAST::Struct::If}}({{#x|"<L=1>"}}, {{#x|"[a]"}}, {{#x|"[b]"}}); FAST::Element* While = {{#kw|new}} {{#c|FAST::Struct::While}}({{#x|"<L>0>"}}, {{#x|If}}); FAST::Element* Seq = {{#kw|new}} {{#c|FAST::Struct::Seq}}({{#x|"L:=1"}}, {{#x|While}}); +{{img src="images/fastast.png" width="577" height="456"}} ---- Composite Pattern {{#c|✓ Handling the tree is easy}} ---- {{#c|tree1->subs(node_name, tree2);}} Substitute {{#x|tree2}} for every node named {{#x|node_name}} in {{#x|tree1}}. ---- {{img src="images/fastast.png" width="577" height="456"}} Seq->{{#c|subs}}({{#x|"[a]"}}, {{#x|"[b]"}}); ---- {{img src="images/tree03.png" width="577" height="456"}} ---- {{img src="images/fastast.png" width="577" height="456"}} Seq->{{#c|subs}}({{#x|"[L:=1]"}}, {{#x|If}}); ---- {{img src="images/tree04.png" width="952" height="456"}} ---- The {{#x|subs}} method is {{#t|also}} +{{#ci|21}} lines of code ! ---- {{img src="images/subs.png" width="811" height="558"}} ---- {{#kw|bool}} {{#c|FAST::Struct::subs}} ({{#c|string}} label, {{#c|FAST::Element}}* dest) { {{#c|vector}}<{{#c|FAST::Element}}*>* relems = {{#kw|this}}->elems(); {{#kw|bool}} done = {{#kw|false}}; {{#kw|for}} ({{#kw|int}} i = 0; i < relems->size(); i++) { {{#c|FAST::Element}}* e = (*relems)[i]; {{#kw|if}} (e->is_node()) { {{#kw|if}} (e->label() == label) { (*relems)[i] = dest->clone(); done = {{#kw|true}}; } } {{#kw|else}} { {{#kw|bool}} res = e->subs(label, dest); {{#kw|if}} (!done && res) done = {{#kw|true}}; } } {{#kw|return}} done; } ---- Composite Pattern {{#c|✓ Visualizing the tree is easy}} ---- {{#ci|If}}->{{#x|as_png}}(\"if.png\"); +{{img src="images/if.png" width="181" height="491"}} ---- {{#ci|While}}->{{#x|as_png}}(\"while.png\"); +{{img src="images/while.png" width="298" height="490"}} ---- {{#ci|Seq}}->{{#x|as_png}}(\"seq.png\"); +{{img src="images/seq.png" width="296" height="489"}} ---- The operations of {{#x|trees}} and {{#x|nodes}} are {{#ci|unified}} ! ☼ ---- There are many, many {{#ci|more}} design patterns in {{#x|FAST}}... ---- You can find them {{#ci|yourself}}. {{#x|☺}} ---- Get {{#x|FAST}} and the {{#x|slides}} today! {{#c|♨}} +{{http://yxy.ujs.edu.cn/images/index.html}} ---- These slides are {{#ci|powered}} by +{{#x|Sporx}} and... ---- {{img src="images/grin.png" width="65" height="65"}} {{#ci|Takahashi}}{{#x|++}} ---- Most of the {{#x|images}} used here were {{#ci|dawn}} by +{{#i|AT&T}}'s {{#x|Graphviz}} ---- {{#c|Thank you!}} ☺