TOP INTRO TO MULTIMEDIA NTWRK
TOP INTRO TO MULTIMEDIA NTWRK CS 410
Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 229 page Class Notes was uploaded by Orrin Rutherford on Tuesday September 1, 2015. The Class Notes belongs to CS 410 at Portland State University taught by Staff in Fall. Since its upload, it has received 18 views. For similar materials see /class/168283/cs-410-portland-state-university in ComputerScienence at Portland State University.
Reviews for TOP INTRO TO MULTIMEDIA NTWRK
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/01/15
CS4 05 I 0 Advanced Programming Lecture 5 Collections in Smalltalk Hamming s Problem Revisited PORTLAND STATE UNIVERSIIY List Operations Last week you heard about list operations in Haskell For each there is a corresponding operation in Smalltalk most work on any collection not just lists Advanced programmers use these operations they almost never munge around with array indexes or pointers PORTLAND STATE 2 UNIVERSIIY Haskell ltgt Smalltalk crib sheet k map A4 find filter 9t all t any 2t foldl PORTLAND STAIE UNIVERSHY collect detect select allSatisfy anySatisfy inject into collect captures a pattern If you ever find yourself writing a loop or a recursive method that builds a new collection based on an old one STOP lsthisacollect PORTLAND STATE UNIVERSIIY What about do do does some action on every element of a existing collection collect builds a new collection based on applying a function to every element of an existing collection If you find yourself writing newCollection ltsomecassgt new self do each newCollection add ltan expression involving eachgt ltproceeed to use newCollectiongt Consider using collect instead PORTLAND STATE 5 UNIVERSIIY Maybe types vs Control Sometimes you don t know if an element is in a collection k find a gt Bool gt a gt Maybe a detect each aBlock ifNone anotherBlock Examples W 1 3 5 detect each each even nu error 1 3 5 detect each each even ifNone 2 mu 2 w 1 3 4 detect each each even mu 4 PORTLAND STATE 6 UNIVERSITY Anonymous functions each each even is an anonymous function What about named functions there aren t any Methods are not functions will turn a messagesend into a function 3 I H 1 is the successor function it Haskell is briefer 1 You could write a method that answers a func on PORTLAND SMTE 7 UNIVERSHY folds A foldr substitutes from the right Kfoldr0123mIgt123O or more precisely 1 2 3 0 k foldl substitutes from the left A foldO123Hquotgt 01 23 or more precisely O 1 2 3 injectintc is foldl 1 to 3 inject 0 into acc each acc each PORTLAND STATE UNIVERSITY injectintc example 1 to 6 inject Set new into acc each each even ifTrue acc add each acc PORTLAND STATE UNIVERSIIY injectintc example 1 to 6 inject Set new into acc each each even ifTrue acc add each acc nu a Set6 2 4 PORTLAND STATE UNIVERSIIY injectintc example 1 to 6 inject Set new into acc each each even ifTrue acc add each acc nu a Set6 2 4 1 to 6 select eacheach even asSet PORTLAND STATE 9 UNIVERSIIY injectintc example 1 to 6 inject Set new into acc each each even ifTrue acc add each acc nu a Set6 2 4 1 to 6 select eacheach even asSet what s the difference PORTLAND STATE 9 UNIVERSIIY common patterns captured by iterators count aPredicate answers the number of elements for which aPredicate is true do elementBlock separatedBy separatorBlock execute the elementBlock for each element and the separator block between the elements do aBIock without anltem execute aBIock for those elements that are not equal to anltem detectMax aBIock answer the element for which aBIock evaluates to the highest magnitude PORTLAND STATE l0 UNIVERSIIY and on SequenceableCollections with otherCoIlection collect twoArgBIock twoArgBlock calculates the elements of the result permutationsDoaBlock execute aBlock self size factorial times with a single copy of self reordered in all possible ways combinations kk atATimeDo aBlock take my items kk at a time and evaluate aBlock self size take kk times once for each combination aBlock takes an array of elementse ach combination only occurs once and order of the elements does not matter PORTLAND STATE H UNIVERSIIY List Comprehensions Generators A 110 A 1525 Manipulators A i2ilt 28 A i 2 i lt 28 even i A 0 I ilt 241jlt 7911 A zip 24 79 PORTLAND SMI E UNIVERSHY Programming is about finding patterns If the same pattern comes up in several places abstract it into a programming language element method class function replace all of the occurrences of the pattern with the abstraction once and only once define the pattern once PORTLAND STATE 393 UNIVERSIIY Array printing example PORTLAND STATE UNIVERSIIY Lessons from the Homework program with a partner fit into the framework don t store all the values clean up after yourself avoid complexity DTSTTCPW write a printOn method PORTLAND STATE UNIVERSIIY divide and conquer separate complex cases when you inherit override inappropriate methods write adequate tests don t forget the class side methods Hamming s problem h is an Ordered Set 1 e h 0 Xehgt2xeh3xeh5xeh generate all elements of h lt limit PORTLAND STATE UNIVERSIIY Let s solve it 1 Write a test 2 make the test run green 3 clean up the code gt remove any duplication 4repeatun done PORTLAND STATE I7 UNIVERSIIY Introduction to Objectoriented Programming in Smalltalk PORTLAND STATE UNIVERSITY Objects are responsible for their own ac ons In procedural programming I write code that reaches into the internals of some data structure and twiddles with the bits 0 0 1 1 0 0 1 1 string Process process process reads reads reads wrltes writes writes PORTLAND STATE UNIVERSITY In 00 programming I politely request some other object to perform some work on my behalf and it politely answers me String T lolol1l1lolol1l1 a COpy PORTLAND STATE UNIVERSITY In 00 programming I politely request some other object to perform some work on my behalf and it politely answers me i l l lolol1l 1l0l0l1l1t Encapsulation i boundary concat COpy PORTLAND STATE UNIVERSITY In 00 programming I politely request some other object to perform some work on my behalf and it politely answers me i l l lolol1l 1l0l0l1l1t Encapsulation i boundary concat COpy COP PORTLAND STATE UNIVERSITY In 00 programming I politely request some other object to perform some work on my behalf and it politely answers me i l l lolol1l 1l0l0l1l1t Encapsulation i boundary concat COpy PORTLAND STATE UNIVERSITY In 00 programming I politely request some other object to perform some work on my behalf and it politely answers me i l l lolol1l 1l0l0l1l1t Encapsulation i 3930 U n da F Print concat COpy aNewString V PORTLAND STATE UNIVERSITY In 00 programming I politely request some other object to perform some work on my behalf and it politely answers me i l l lolol1l 1l0l0l1l1t Encapsulation i boundary concat COpy PORTLAND STATE UNIVERSITY Computation as Simulation This collection of autonomous objects is like the world of discreet event simulation Anthropomorphize It s OK to think about this object talking to that object In fact it s recommended PORTLAND STATE UNIVERSITY Programming Philosophy ObjectOriented programming is programming by simulation The algorithm is less important than the structure of the solution When requirements change If the structure represented the structure of some reality then the new requirements will be consistent in that reality Objectoriented design is the search for this structure uncover the structure rather than construct in isolation PORTLAND STATE UNIVERSITY Shopping vs Building Constructing an Objectoriented application is a process of shopping for the components that one needs occasionally we add a new item to the shelf usually we can find a component that almost fits The openness of an 00 language allows the programmer to change the component that almostfits into one that is a good fit works only if we have a rich set of components on the shelf and if they are open to change PORTLAND STATE UNIVERSITY Is this the only view of 00 Programming No People disagree on the meaning and role of 1 Encapsulation 2 Types 3 Inheritance 4 Polymorphism 5 Sets and Classes PORTLAND STATE UNIVERSITY Smalltalk Squeak is an opensource version of Smammk Smalltalk is still the best example of a Pure OO language The Squeak workspace is a place in which you can create and interact with objects Large and active community of contributors Runs bit identical on just about any platform including many PDAs PORTLAND STATE UNIVERSITY The Squeak Environment A place to experiment with objects Forget applications files compilers data Focus on objects PORTLAND STATE UNIVERSITY rl 3 squeak W0 The H a squeak VM amp ources schanges host OS 0 STATE HY UNWE Smalltalk Syntax No syntax for classes packages etc Class creation and method categorization are done imperativey using the development tools The method syntax is simple but different gt aString quotAnswer whether the receiver sorts after or equal to aString The collation order is simple ascii with case differencesquot A self compare self with aString collated AsciiOrder gt 2 PORTLAND STATE UNIVERSITY Smalltalk The Language Literal Objects 27 The unique object 27 185 The floating point number 185 185e1 same as above 39a string39 a string request the symbol request It is unique two symbols with the same name denote the same object r the single character r 3 27 39a string39 an array literal This is a heterogeneous array containing an integer a float and a string PORTLAND STATE UNIVERSITY Sending Messages Unary Message no arguments mm receiver target of message selector selector is a keywordlike symbol examples 3 factorial 7 negated c aslnteger note no colon at the end of the symbol PORTLAND STATE l3 UNIVERSITY Binary Message one argument EBquotVargument receiver selector selector is one or two special characte 7 5 message 5 sent to object 7 i 3 message 3 sent to object i 17 3 message 3 sent to integer object 17 result is 5 173 message 3 sent to integer object 17 result is PORTLAND STATE I4 UNIVERSITY Binary Message one argument EBquotVargument receiver selector selector is one or two special charac 39 Not exactly i is not an object It39s a variable that39s bound to an object 7 5 message 5 sent to object 7 i 3 message 3 sent to object i 17 3 message 3 sent to integer object 17 result is 5 173 message 3 sent to integer object 17 result is PORTLAND STATE I4 UNIVERSITY Keyword Messages 39 one or more arguments Examples 357911at2 game movefrom pinA to pinB using pinC 5 between 0 and 9 The colon indicates to the parser that an argument follows the keyword PORTLAND STATE l5 UNIVERSITY Order of Evaluation The receiver or an argument can be another invocation message expression Evaluation order is parenthesized invocations unary invocation evaluated left to right binary invocations evaluated left to right keyword invocations No priorities for particular operators gtxlt does not bind more tightly than PORTLAND STATE l6 UNIVERSITY Cascaded Messages syntactic sugar anArray at 1 put 9 anArray at 2 put 11 anArray at 3 put 13 This can be abbreviated as anArray at 1 put 9at 2 put 11at 3 put 1339 rece er for all 3 messages receiverless messages Result is that of the last message send Transcript show 39Hello World39 cr PORTLAND STATE l7 UNIVERSITY Variables Instance Variables The names of the slots in an object which make up its representation declared in the class instanceVariabeNames 39name1 name2 Temporaries Names local to a method body or block student professorAtOGl PORTLAND STATE l8 UNIVERSITY Assignment x 3 5 makex name the object resulting from the evaluation of the expression 3 5 y Array new 1000000 make y name a new 1MB array Variables name objects They do not provide storage for objects Assigning to a variable makes it name a different object no object is created or copied by assignment PORTLAND STATE l9 UNIVERSITY Learning More Finding Classes By name or fragment of a name commandf in the Classcategory pane of a browser By selecting a morph and Choosing browse morph Class from the debug menu PORTLAND STATE 20 UNIVERSITY Finding methods By name fragment or by example with the method nder Smalltalk browseMethodsWhoseNamesContain 39soreen39 Smalltalk browseMethodsWithString 39useful39 or highlight the string and type commandE highlight a selector Choose implementors of commandm or senders of command n PORTLAND STATE UNIVERSITY 2 Finding Answers Some invaluable resources The Squeak Swiki a wiki is a website where anyone is free to contribute to editing and maintenance httpminnowccgatechedusqueak snapshot at httpswikimirrorsqueakspacecom Squeakorg Documentation tutorials swikis other sites books and papers downloads and information on PORTLAND STATE 22 UNIVERSITY The Squeak mailing list a friendly place where newbies are made welcome squeakrequestcsuiucedu Archive of FlXes ENHancements GOODIES httpswikigsugorg8080SQFIXES Searchable archive of whole list httpgroupsyahoocomgroupsqueak PORTLAND STATE UNIVERSITY 23 Creating Objects in Smalltalk Object are created by sending a message to some other exisiting object called a factory Usually the factory object is a class eg OrderedCoIection new Array with 39one39 with 39two39 with 39three39 8 Bag new The object will be deallocated automatically when it39s no longer needed garbage collected PORTLAND STATE 24 UNIVERSITY Blocks Blocks are Smalltalk objects that represent Smalltalk code 1 2 They can have arguments x1x comparewith kx1x Blocks understand messages in the value family value value value value value value value The Block is not evaluated until it receives a value message PORTLAND STATE 25 UNIVERSITY Examples of Blocks Ifthenelse is not a builtin control structure it s a message aBooIean ifTrue trueBIock ifFaIse falseBIock discountRate transactionValue gt 100 ifFaIse 005 ifTrue 010 You can build your own control structures keyEvent controlKeyPressed and keyEvent shiftKeyPressed PORTLAND STATE 26 UNIVERSITY Returning an Answer T returns an answer from a method if there is no T the method returns self T is very useful to return from a block color oolor ifNil T Color black T oolor T in a block returns from the method in which the block is defined not the method that evaluates the block PORTLAND STATE 27 UNIVERSITY Arrays Arrays in Smalltalk are Objects They are special in 2 ways 1 there is language syntax to create them 1 34 symbol av awaa LitemL 43 175 asFloat 39sym3939bol39 asSymbol a dawamicaua cowstnccteol awaa Array with 43 with 1705 with symbol the same 2 there are ByteArrays FloatArrays as well as Arrays PORTLAND STATE 28 UNIVERSITY Characters amp Strings Characters are also objects H is the literal for the character H H asciiValue is 72 H digitValue is 17 3 digitValue is 3 collect creates a new array by applying a function to all elements of the receiver 39O1234567890ABCDEF39 asArray collect each I each digitValue evaluates to O 1 234 56 78 9 0101112131415 PORTLAND STATE 29 UNIVERSITY Other enumeration methods anArray do aBIock applies aBIock to each element of anArray and answers anArray anArray withlndexCollect a2ArgumentBlock answers the new array containing the results of applying a2ArgumentBlock to each element of anArray together with its index anArray withlndexDo a2ArgumentBlock PORTLAND STATE 30 UNIVERSITY Examples one two three four withlndexCollect eaChi each 39 i asString evaluates to 0we 139 39two 239 quotclwee 339 four 439 one two three four withlndexDo eaChi Transcript nextPutAll each 39 Show i or evaluates to owe two three four Le the receiver PORTLAND STATE 3 UNIVERSITY Indexing Arrays eins zwei drei at 1 eins zwei drei first eins zwei drei third eins zwei drei at 2 put deux modifies the receiver and answers deux PORTLAND STATE UNIVERSITY 32 Assignment I Whole objects 0 Parse numerals into numbers without using explicit loops or recursion 0 Use the algorithm shown 391 1639 ex alDdE Hf F 1 4 15 digitvalue paired thmwers f 1 0 1 1 10 1 100 pairwiserduet 040100 33 Reflections on Mobile Object Systems Recent Reading 0 Explicit Code Mobility in Java RMI Alexander Ahern and Nobuko Yoshida Imperial College London Remote Invocation in r m1Remo reObjec r r39 in r a in r x rfa in r y r39ga x in r z r39ha y r39e rur39n z 0 Wha r39s wrong Ahern s solution Sender inT mOpT1RemoTeObJecT r39 inT a ThunkltinTgt r fr39eeze in r x rfa inT y rga x in r z rha y z reTurn rrunT new meThod on r a r remoTe siTe inT runThunkltinTgt x re rurn defros rx Emerald Solution in r m1Remo reObjec r r39 in r a move This To r39 in r x rfa in r y r39ga x in r z r39ha y r39e rur39n z Distributed Shared Memory The Basic Idea multiple processes share a single virtual memory space processes do loadsstores fromto memory locations pages may be resident local or nonresident remote o accesses to nonresident pages generate page faults page faults are handled by the OS and serviced by the DSM middleware o perhaps by retrieving the page from another machine protection faults can also be used by the DSM system to intercept interesting references to the shared memory 0 perhaps by invalidating pages on another machine Characteristics 0 Interprocess communication is via modi cation and subsequent reading of shared memory locations 0 Semantics de ned by memory consistency model 0 Local and remote communication look the same 0 remote communication is hidden behind MMU faults invisible to the application 0 some memory accesses take very much longer than others 0 analogy with cache misses on SMPs 0 Like programming a shared memory multiprocessor 0 UMA vs NUMA vs NORMA architectures Key Issues and Challenges I Performance 2 Performance 3 Performance Why is Performance Hard 0 minimum unit of communication is a page why 0 two processes accessing the same page cause thrashing 0 even if they are accessing different addresses false sharing 0 effect of page size Replicated Pages 0 Most DSM systems replicate pages 0 readonly processes can execute in parallel 0 only one replica can be writable 0 how do we choose it 0 how do we invalidateupdate outdated copies 0 Cost of DSM comes from protection faults and message exchanges 0 Strongly influenced by caching strategy and memory consistency model 90 How can we Implement Strong Consistency Centralized DSM Migrating DSM Readonly replication central server for writes Readonly replication migrating server for writes Did anyone ask the Programmer Programmers who use shared memory use a high level language with synchronization constructs Arbitrary memory sharing will get you a C even if your program works Novel idea ask the language implementor what abstractions help her to do her job HighDimensional 0 Data 0 Topics 0 Motivation 0 Similarity Measures 0 Index Structures 0 R trees redux 0 We want to minimize coverage and overlap m A E E rl lg ma B 9 We descend both branches to search for 0 R Trees 0 store din both A and B 0 like splitting d into two pieces I m A EI ii B 9 0 R trees 0 When a node overflows a don t split it right away a reinsert some of its nodes E El d A 9 D an E 0 R trees 0 Normal Insertion d x Bl D I a a 0 R trees 0 Reinsert 0 instead of splitting node Coverage and overlap as a function of dimension Curse of Dimensionality 0 Generally exponential growth of the hypervolume as a function of dimension 0 Other manifestations 0 number of samples required to maintain the same accuracy 0 number of nodes in a neural network required to monitor the input space 0 lots more Highdimensional data 0 Finance 0 Multimedia 0 Sound 0 Music Query by humming j a 0 Images 0 Video 0 Document Retrieval o BiologyMedicine 0 DNA sequence matching 0 Medical imagery 0 Moving Objects t0x0y0t1x1y1 o HighEnergy Physics Highdimensional Access Methods 0 Three components 0 Similarity Measure 0 Index Structures 0 Search Strategy we won 1 cover search strategy Similarity Measure 0 When are two vectors similar Q lllllllllllllllllllll DB W WlllllllllllLlulllllLLu lllllllllllllllllllll lllllllllllllllllllll 0 Similarity Measure Define a function 3 V 9 V 9 Real What properties should 3 have Reflexive SXX 0 or in nity Symmetric 50W 8W Triangle Inequality 50W 832 gt SXz 0 Timeseries Indexing 0 Timeseries Indexing 0 Timeseries Indexing o Euclidean distance 0 Dynamic Time Warping o Jagadish Faloutsos 1998 Keogh 2002 o Wavelets 0 Miller 2003 o LCSS o Vlachos Kollios Gunopolos 2002 o EDR 0 Chen Ozsu Oria 2005 O Euclidean Distance manna mmaaa 78 0 Dynamic Time Warping 0 Dynamic Time Warping 2 Diff in 33555 5 A y D iFim ij Figill mm 1 DENWI quot D uh quot 0 Dynamic Time Warping 3 0 Dynamic Time Warping 4 o Drawbacks o Sensitive to noise 0 expensive to compute 11 0 Wavelets mplitude mplitude It t W 17171quot r Time 0 Fourier Transform Lime 39 Freqtteneyr o Represents a timeseries as a sum of sine waves 0 The coefficients of the constituent waves indicate the dominant structure 0 Wavelets 2 0 Same trick different basis function 0 Sum of sine waves 0 Sum of Dirac delta functions 0 Sum of 39 gtlt I 74 73 72 rl n l 2 3 A r e r A r 2 n 2 A E 12 0 l Wavelets 3 Haar wavelet transform 8i Si1 Si 39 Si1 UrigmaiSigna 2 l 7 in s in 5 l t l 3 i I Detail Signal 1 s l 3 l a l 3 Detail Signal 2 w l 13 Smoolhed 339 439 Detail Sigm 3 9 Hierarchical decomposition allows finetuning O a l Wavelets 4 Smooth ed Image After one Horizontal filtering Detail Image 13 0 Wavelets 5 0 After two vertical and horizontal e ngs O Wavelets 6 o Wavelets can reduce dimensionality like PM Y 0 Principal Component Analysis PCA pm 0 Singular Value Decomposition SVD 0 others X o Indexing in the reduced feature space 0 False positives ok False negatives aren t 0 Use a more refined similarity measure to eliminate false positives 14 0 Other measures 0 Longest Common Subsequence n a 333 0 Index Structures 0 SSTree thite Jain 96 o RTree using Minimum Bounding Spheres gt o SRTree Katayama Satoh 97 0 Uses MBR during construction 0 but MBS during lookup o X Tree Berchtold Kreim Kriegel 96 o RTree using extended nodes to avoid splits and control maxim um overlap gt o MTree Ciaccia Patella 00 0 Build tree based on representative points 0 TVtree Lin Jagadish Faloutsos 94 SRTree and MTree appear to outperform others 15 M ss gwriitismimg sf 34 g 2 K y 1 side s 60 7 sari 3 ii Asmaimeii Yb 0 node center radius r1 2 J Samar 3 5 deius Number of active dimensions 1 j g 4quot bx m E j t 5 a I E x x g quotEm 4 f i 3 E g a D1 Samar 21 Radius 2 Di Center 74 1 Number of active dimensions 1 Telscoping Vector Tree TV 0 dimcenter gt of active dimensions 39 m x J K 3 0 5 ww39 W MMMMMMMMMMMMMMMMMMMMMMM Ms 393 7 1 Cams 26 Radius 3 S2 Tamar 14 Radius 3 Number of active dimensions 2 CS 405I0 Advanced Programming The Visitor Pattern Andrew P Black lt13 Portlanmae Recap Recall the rows and columns diagram Operations first rest isEmpty ConsList er 0 return e return I false Repres entations EmptyList error error true Each row is a separate class gt adding rows is easy Each column is a method in multiple classes gt adding columns is hard or impossible e Portlan9i tasrs Visitor Synopsis The Visitor pattern turns columns hard to add into rows easy to add ie it turns columns methods into rows classes operations are represented as classes rather than as methods can Portlanmae 3 Example Arithmetic Expressions Represent arithmetic expressions like 1o457 e Portlanmae vroot a Difference vleft an lntegerLiteral value 10 vright a Sum v left an IntegerLiteraI value 4 vright a Product vleft an IntegerLiteral value 5 vright an lntegerLiteral value 7 CIaSS hierarChy Expression BinaryExpression operations like Difference Product numericValue would Quotient normally be implemented Pf ry by recursive traversal of Factor 39 Literal the expreSSIon tree IntegerLiteral RealLiteral eg Negation Difference gtgt numericValue T left numericValue right numericValue Problem each operation prettyPrint typeCheck etc is dispersed over a dozen classes 43 Portlansmers 5 Solution turn operation into a Class 1 Create NumericEvauator Class give it methods called visitDifference visitSum that do the appropriate thing on Difference and Sum nodes eg NumericEvaluator gtgt visitDifference diffNode T diffNode left numericValue diffNode right numericValue Difference gtgt numericValue Compare T left numericValue right numericValue e Portlanmae 6 Solution continued 2 Every concrete class F00 in the Expression hierarchy gets a method accept aVisifor defined as follows Foo gtgt accept aVisitor T aVisitorvisitFoo self Note how the selector of the message tells the visitor what kind of node it is visiting Do this for Foo Difference Product Quotient Sum etc 13 Portlanmae 7 Solution continued 3 At the top of the hierarchy add a single method that provides a client interface Expression gtgt numericValue T self accept NumericEvaluator new 9Kal of the code that implements numeric evaluation is now outside of the Expression classes 9K It s in the NumericEvaluator class a Portlanme 8 Let39s look 1EI RB NumerEEvaluamr aw ESSlDapersuars 5w EmarVExpressmn a r a cummzvem a Dxfference 1 menu Expressmn v s a ampm m A xpressmnvxsuar nsquducx szcepuamm Eacmr nsu uauem mzx mpxemgcus xmegemm nsukealLueral IEEIVExampleerm Lueral nsusum j rtxamplesrxn mm 4 irurxemex n 7 m r m 7 I bravse sender 1 mp m m hm Na m WWI mum mo xen numerxcvalue vac nghx numerchalue Portland State Consequences External code in the visitor must have access to the internals of the visited objects gt all significant state must be public Is this objectoriented New operations can be added without changing the Expression classes Why is this a big deal e Portlanmae The Design Patterns Smalltalk Companion by Sherman R Alpert Kyle Brown Bobby Woolf Foreword by Kent Beck AddisonWesley 1998 lt18gtP rt1an9l ets quot Advanced Programming Andrew Black and Tim Sheard Lecture 2 Intro to Haskell Course URLs httpwebcecspdxeducs410aph Course web page Links to lecture notes and assignments httpsamlapdxeduportal Homework submissions Class mailing list Course Evaluation Daily Assignments Class participation including code walks Projects Haskell Haskell is a pure functional language Yet it supports imperative programming with the use of monads There are several implementations HUGS httphaskellorghugs GHC httpwwwhaskellorgghc Haskell has a sophisticated type system that catches many errors and supports advanced abstraction mechanisms Characteristics of Haskell Applicative style input output description of problem First class functions pass as parameters return as value of a function store in datastructures Less Importantly Automatic memory management GC no new or malloc Use of a strong type system which uses type inference ie no declarations but still strongly typed GHC or Hugs Should we use GHC or Hugs Hugs is an interpreter Great for quick editcompiletest turnaround GHC is a compiler Fast runtime binaries Extensive tool support profiling Many extensions For most uses they are compatible and many programs will run on either system So recommend you install and use both GHCI the GHC interactive system 7 V for Haskell 98 httpwwwhaskellorgghc Type for help GHC Interactive version 641 Loading package base10 linking done Preludegt length 1234 4 Preludegt In addition to the commandline compiler GHC also comes with an interactive environment GHCI it works much like Hugs after which it was modeled Try it out The Hugs Interpreter Hugs Demo Hugs 98 Based Haskell 98 standard Copyright c 1994 2003 I World Wide Web http haskell orghugs Report bugs to hugs bugs haskell org Hugs mode Restart with command line option 98 for Haskell 98 mode Hugs session for CProgram FilesHugs98librariesHugsPreludehs CProgram FilesHugs98librariesPreludehs DworksheardCoursesCSE502Fal12004lect01html Type for help Maingt 00 vs Functional Objects behave explode xxxxxxxxx 1 e Functions transform Basic Approach The basic approach to programming in Haskell is two fold Define some data structures Define functions over those data structures In contrast with Smalltalk where the model is simulation of the real world the model is transformative le we think of transforming data from one form to another IntLists Define some data IntList mm Cons Int IntList Nil Write some functions len Nil 0 len Cons x xs l len xs addAll Nil 0 addAll Cons x xs x addAll xs Data Declarations Data declarations describe treelike structures allocated in the heap Cons Nil Cons Cons HE HI I N 0 fields Note since Nil is a constant there need be only 1 such cell in the s stem 2 fields one an Int the other another list Constructing Data Treelike structures are created using constructor functions These have the same name as the tags These names always start with an uppercase letter data IntList Cons Int IntList Nil Cons 3 Cons 2 Cons 9 Nil Cons Cons Cons Nil 29 Exercise 1 Define a Haskell Data declaration to capture the following treelike structure Data Treel m pty Empty Empty Empty Exercise 2 Construct the tree using the constructors of your data declaration Fork pty Empty Empty Empty Exercise 3 1 Define a Haskell Data declaration to capture the following treelike structure 2 Construct the tree Node Node Node W T T1 E IIl H o IIl H o Func ons Functions are defined by cases over the data using patterns Patterns appear on the lefthandside of a case Patterns match treelike structures and bind variables to values len Nil 1 len Cons x xs 1 len xs Pattern Construction Patterns are composed of Constructors Variables Constants Tuples For example COl lS X XS constructors and variables COl lS 5 Nil constructors and constants y Cons X Nil tuples constructors and variables Pattern Matching Every pattern matches and binds variables A pattern can match many structures Eg Cons x xs and Nil Cons Nil N11 X binds to 5 XS binds to Nested patterns an constants Cons x Cons 5 xs matches Cons Cons Nil Cons 22 Cons 5 Nil Cons Cons Nil nan IN Cons 3 Cons 5 Cons 9 Nil But N OT Cons Nil Cons 3 Nil Cons Cons a n I l Cons 5 Cons 4 Cons 22 NH Selection or Deconstruction Pattern matching is used to select or take apart treelike heap structures We can define selection functions using patterns listHead Cons x xs x listTail Cons x xs xs first xy x second xy y A Recursion is the only primitive control structure len Nil 0 len Cons x xs 1 len xs addAll Nil 0 addAll Cons x xs x addAll xs empty Nil True empty Cons x xs False Pattern Matching vs Selection addAll Nil 0 addAll Cons x xs x addAll xs add2 x if empty x then 0 else listHead x add2 listTail x Built in Polymorphic Lists Haskell has a complete set of functions that work on polymorphic lists 146 Int TrueFalse Bool Cons 2 Nil IntList Such ists use special syntactic sugar It is as if they were defined using data a a a 1 Special Syntax but just the same 1 2 5 1 or 125 3 3 z WHMH 3 H TrueFaIse or True False H I i 1 I I m Right associativity of z means we don t need parentheses Functions on polymorhic lists sum Int gt Int sum 0 sum X XS X 4 sum XS Polymorphictype means length works on all length a gt Int mdemm length 0 length x xs 1 length xs null a gt Bool null True null x xs False Strings and characters Strings are nothing more than lists of characters type String Char Strings have special syntax abc is the same as a b39 c We can access library functions over characters by using the Char library import Char Charord Char gt Int Charohr Int gt Char tesths import Char test test2 Charord head quotabcquot Charohr test Version 20050113 Hugs mode Restart with command Type for help Maingt l tesths Maingt test 97 Maingt test2 lal Maingt Hugs 98 Based on the Haskell 98 standard Copyright c 1994 2003 world Wide web httphaskellorghugs Report bugs to hugs bugshaskellorg line option 98 for Haskell 98 mode Tuples Tuples are heterogenous collections of fixed width 4True IntBooI 345 Intntnt True zx False5 Bool String Bool Int Pattern matching As we saw in first and second we can pattern match over tuples first xy x second xy y oneOfThree xyz x twoOfThree xyz z down2 xyzw x firstOfHead xyxs x Mundane issues Lexical issues The offsides rule indenting matters Setting the search path Getting information from Hugs Using Hugs load files Change directories Get type information Syntactic Elements 1 Literals Char a lnteger 345 Float 2356 String abc Constructors Constructors start with an Uppercase letter Primitive operator constructors and Syntactic Elements 2 Operator chars operators are combinations of amp ltgtquotI Reserved operators Special sequences of opchars ltgt gt Operators are used in an infix manner 5 3 fx gt xgt 3 4 Any identifier can be made infix by using backquotes Eg 10 in w and 3 choose 5 op makes an infix operator a prefix function o 4 6 Syntactic Elements 3 Identifiers start with a lower case letter followed by digits or other letters or primes Valid Examples a a3 a b aF Invalid Examples F1 Good Reserved words case class data else if in infix infixl infixr instance let of primitive then type where Syntax 3 The offside rule Indentation matters Continuation across lines with deeper indentation continues the same declaration Less indentation means the start of the next declaration Consequence ALL DECLARATIONS IN THE SAME GROUP MUST BE EQUALLY INDENTED OK length 0 length x xs l length xs null True null x xs False NOT OK length 0 length x xs l length xs null True null x xs False Indentation matters at top level and Case f x case x of 1 gt 0 xzxs gt 1 f x Let let f xy x Ia f 23 in a Where f x g init x where g init init g init xzxs g init x xs init 5 Hugs Hugs has two modes Command mode command Evaluation mode expression Hugs 9 Based on the Haske39l39l 98 standard Copyright c 19942003 c w r39ld wide web39 httphaske39l39lorghugs Report bugs to hugsbugs haske39l39lmrg Version 20050113 ype 7 for he39lp a1 gt Hugs mode Restart with command 39I139ne option 98 for Haske39l39l 98 mode n Expression Evaluation cd ogistaffsheardcse502 52 390 l 390 390 5 2 3 13 sqrt 40 0 sum 234 length 2345 sort 3412776 1 2 3 4 6 77 0I I390Ib390KO390N390 Hugs Help Maingt LIST OF COMMANDS ltcommandgt Any command may be abbreviated to c where c is the first character in the full name load ltfilenamesgt load also ltfilenamesgt reload edit ltfilenamegt edit module ltmodulegt ltexprgt type ltexprgt set ltoptionsgt set names pat info ltnamesgt browse ltmodulesgt find ltnamegt command cd dir gc version quit Maingt load modules from specified files clear all files except prelude read additional modules repeat last load command edit file edit last module set module for evaluating expressions evaluate expression print type of expression display this list of commands set command line options help on command line options list names currently in scope describe named objects browse names exported by ltmodulesgt edit module containing definition of name shell escape change directory force garbage collection print Hugs version exit Hugs interpreter Command typing expressions Maingt Maingt t sort sort Ord a gt a gt a Maingt t mymap mymap a gt b gt a gt b Maingt t mymap x gt x1 mymap x gt x 1 Num a gt a gt a Maingt Func ons Functions are defined in Files and loaded into to Hugs Example 1 lectOl hs Functions on numbers Type of numbers Int and Float Conversion functions fromlnteger round Functions on Booleans Relational operators lt gt lt gt 2 Combinators ampamp not Examples 5 gt 7 False 1 False Function Definitions Functions defined in files by writing equations visit a samgle filehs Example plusone x x l Sample Output when loading Hugs session for EprogramsHugs98DecOllibPreludehs EworksheardCoursesCSE502weblecturenoteslect Olhs Type for help Maingt plusone plusone plusone 4 5 Functions with Multiple Arguments Example Definitions difference x y x y choose x y z if x then y else 2 Example Session Hugs session for E lectOlhs type difference difference Int gt Int gt Int type choose choose Bool gt a gt a gt a Arrow is right Associative a gt b gt c a gt b gt c Setting the search path When hugs looks for libraries and modules it looks in the directories denoted by the search path 0 set will display the path and lots of other things Set Pcxxxdyyy will add cxxx and dyyy to the existing path indicated by the leading semicolon Types of Errors Syntax errors use of symbols in unexpected places f x XO x r Reading script file quotlectOlhsquot Parsing ERROR quotlectOlhsquot line 36 Syntax error in input unexpected 39 Undefined variables lastone2 head rev r Reading script file quotlectOlhsquot Dependency analysis ERROR quotlectOlhsquot line 38 Undefined variable quotrevquot Types of Errors cont Type errors type hd hd a gt a type plusone plusone Int gt Int hd 3 ERROR Type error in application expression 1 hd 3 term 3 k k type Int does not match a plusone 12 ERROR Type error in application expression plusone 12 term 12 type Int does not match Int Assignment 2 You are to write a number of functions in Haskell explodezz String gt Char digitValue Char gt Int reversezz Int gt Int pairedWithPowersOflO Int gt IntInt pairWiseProduct IntInt gt Int sum Int gt Int toInt String gt Int Write 5 functions sum amp reverse are primitives and don t need to be written Write each one using pattern matching and recursion Create a number of tests for each function testl explode tim t i m Turnin an elegant program that communicates your solution well CS4 05 0 Advanced Programming MetaMatters in Squeak Andrew P Black PORTLAND STATE UNIVERSITY What39s Meta Metaprogramming is the act of writing a program that writes or manipulates another program or themselves Why not After all programs are just data PORTLAND STATE UNIVERSITY Simple Example In the visitor pattern last week PORTLAND STATE UNIVERSITY Solution continued 2 Every class Foo in the hierarchy gets a method accept aVisitor defined as follows l Foo gtgt accept aVisitor T aVisitor visitFoo self Note how the selector of the message tells the visitor what kind of node it is visiting PORTLAND STATE UNIVERSITY PORTLAND STATE UNIVERSITY Solution continued 2 Every class Foo in the hierarchy gets a method accept aVisitor defined as follows Foo gt39gt accept aVisitor T aVisitor visitF oo self Note how the selector of the message tells the visitor what kind of node it is visiting We wrote these methods with a metaprogram PORI IANDS I ATE Expressmn allSubclassesDo eachl each complle 39accept aVlsltor T aVisitor Visit39 each name 39 self 39 classi ed 39Visiting39 PORTLAND STATE UNIVERSITY Alternative Solution Instead of writing a separate program to write our program we could make the program write itself Put the following single method at the root of the hierarchy T aVisitor perform 39visit39 self class name 3939 asSymbol Expression accept aVisitor with self This is a reflective program one that writes itself dynamically PORTLAND STATE UNIVERSITY Another Example We know that we can write this 1 to 10 select X x even How about this 1 to 10 select even Can we make this work What about other unary messages odd isPrime PORTLAND STATE 5 UNIVERSITY Summary of Solution 1 to 10 select must answer an object that quotremembersquot the collection and the fact that we plan to do a select operation This object is called a Trampoline How can we make the trampoline understand even odd isPrime factorial Reflection PORTLAND STATE UNIVERSITY Another Example Remember ParserFun PORTLAND STATE UNIVERSITY Another Example LJ RE FarserStream 3952 ESSIUap Parsers Elli ail El I all SJ alphaNum ESSIDap Visitors J FailTest L 39oase parsers 5quot binarVArgument CustomEvents ParserEun printing binarVMessage EEompletion ParserStream accessing binarVPattern ECompletion Tests 39 ParserStreamTest composite parsers binarVSelector Exceptions Tests SmalltalKParserTest Smalltalk grammar blockGrammar EEI ExamplesMacEIS Smalltalk lexer char EEI Examples fin z Smalltalk parser digit EEI Exampleslll visitor example end PEI Kernel 3 epsilon EEI Plugin i 39 I l expressionGrammar iiinumLI1VE 1nstance c ass EH1 apb 5316320 14 composite parsers 2 implementors in change sets Parsers Parsers ilifithl ail Lbrowse genders Lim1zgtlementorsJ iLversions inheritance hierarchy tinst vars iclass vars sourcel digit all f self satisfies c cl isDigit name 39digit39 a PORTLAND STATE UNIVERSITY Another Example LI RE FareerStream CSSl ap Parsers l ail 33quot all 917 alphaNum ESSlDap vit39 39 39 v 39 Cum wg tl RE ParserStream E umpletio CSSanp Parsers Eail all ll alphaNum ECDmpletio CSSIDap Visitors EailTest base parsers All binarvi irgument Exceptions CustomEvents Parserfun printing binarvlulessage EEIExamp EEompletion ParserStream accessing binarvPattern EEIExamp ECompletion Tests ParserStreamTest composite parsers binarvSeleotor EEIExamp Exceptions Tests SmalltalkParserTest Smalltalk grammar blook rammar EEI Kernel EEIExamplesMac s Smalltalk lexer char Est plugin EEI Examples i 39in32 Smalltalk parser digit StatMd EEI Examples Hll visitor example end ET EEI Kernel F epsilon 3P1 531632 EEIPlugin expressionGrammar Earnquot LI1 instance I 1 class 1er LL W13 ap o SHE 2006 1 15 composite parsers 1 implementor in change sets Parsers Parsers lfithfail digit 39 alpha um self letter self digit name 39alphaIIum39 f selfI browseJ tsendersj Limplementorsj versions enheritancej hierarchy kinst vars Lolass vars soureel it at Another Example IZ RB ParserStream Fang ESSIUap Parsers gillsa Ell 311 alphaNum 1 ESSIDap vil a V r M CuSmmEvvaz sJLJ I HE ParserStream E umpletio CSSanp Parsers glIEail allquot all g aloha um u Etampletie CSSIDEP39Vi 39 39 quot Excepti ngl EustDme LJ 7 RBT Parsersvtream IE IQl EEIExamp EEnmpletiD CS51EIap Parsers llquotlEai1 ii all Fl char 1 EELEmmp E ampletiu CSBl ap Jisiters J EailTest A base parsers 1 digit 51 EELExamP Exceptiong EustemE39lfents ParserEun printing end EEIKer E1 EEIExampl ECempletien J ParserStream ECCESSIflg eps en J EHp1ugi EEI Exampl ECompletien Tests ParserStreamTest composite parsers expressmn rammar E1 Irm n EEI Exampl Exceptions Tests SmalltalkParserTest Smalltalk grammar fail a EEI Kerne1 EEI Examples MaCUS Smalltalk lexer identifier apb SHE EEIpmgin EE Examples Eiln Smalltalk parser integerLiteraI xamp es Visit r examp e item browse EEI Kernel Keyword 3 apb SHEf2 EEIElugin W 1 kevwerdArgument j gIt J Earnquot L 1 instance c ass Jl SGT quotquotm39m quotI g 139 M WE apb immune 1021 Smalltalk lexer 1 implementer in change sets Parsers Parsers i ithfail 39alpha um V H A l 1 self lbrowseJ genders Limplementers Lversions gnheritancej s ghierarchvj Linst vars Lclass vars sourcell identifier 2 1 self lever gtgt J 1 self alphaNum man H xs self eptienalSpaces w self unit xs capv withfirst x as Wham name 39identif ier39 39 a IL PORTLAND STATE 7 UNIVERSITY EDI Another Example RB Parser s tream CSSl ap Parsera l ail 511 a11 alphallum I ILJ RE ParserStrearn ECumpletio CSBanp Parsers g Eail allquot all Ellaloha um ECompletio CSSIDEPVi 739 7 7 quotif 7 7 7 7 7 if 7 Excepmm EustDme tJ FtB ParserStream IEJHQM EEIExamp EEnmpletiD CS51EIap Parserrs QZIEail ll all Euchar 1 7 7 d F EEI Examp E ampletiu ES5139JEP39VI RE ParserS tream EC qu EEI Examp Exceptions CustDmEV EHKer E1 3313xampl E gmpletigu CSSl ap Parsers E Fail 2 all 9 char 5 EEIPlugi 313xamp1 E ompletim ESEIDapVisitors l EailTest a base parsers 1 digit 5 muf nquot EEIExamp1 Exceptigngt CustomEvents ParserEun printing and EELKBrnel EH Exampl EEompletion ParserStream accessing epsilon l apt 531532 EEIp1ugin PEI Emmi EEompletion Tests ParserStreamTest composite parsers expression rammar tun EEI Exampl Exceptions Tests SmalltalkParserTest Smalltalk grammar fail b air 7 EELKernel EEI Examples MacUS Smalltalk lexer identifier wt apb SHEf2 331 p1ug1n EEI Examples lifinSZ Smalltalk parser integerLiteral quoturnquotv EEI Exampleslll visitor example item digit 7 V 3le browse s 391 EH39KErnEl v keyword J e apt 53391832 EEI Plugin keywordnrgument 7 alphaHm I If 1 11 1 1ngtan e l I 31333 a 3347 u r l f If browse 55 apt 531132006 1 116 Smalltalk lexer 1 implementor in change sets Visitors Parsers 1 self browse ksenders J 1imp1ementors J versions J Linheritancej khierarchy kinst vars kclass vars sourcell Self t mus 1 self string 1f II self string then I self string else II quot n rl self spaces n self unit rll name 39kejtnsrord39 d 39 a Naming Parsers The name given to the parser is often but not always the same as the selector of the method that builds it PORTLAND STATE UNIVERSITY Naming Parsers The name given to the parser is often but not always the same as the selector of the method that builds it digit I 1 self satisfies zci39 ad isDigit name 39digit39 PORTLAND STATE UNIVERSITY Naming Parsers The name given to the parser is often but not always the same as the selector of the method that builds it digit 1 3le satisfies cl d isDigit name 39diajit39 alpha um self letter self digit name 39alphaIIum39 PORTLAND STATE UNIVERSITY Naming Parsers The name given to the parser is often but not always the same as the selector of the method that builds it digit I 1 self satisfies d d isDigit name 39digit39 alphalllum self letter self digit name 39alphaIIum39 identifier self lower gtgt J self alphaIIum man gt Jrs self eptienelSpaees 2 Iself unit tics eapv fithfirst 1 as SW39DUIHH name 39identif ier39 PORTLAND STATE UNIVERSITY Naming Parsers The name given to the parser is often but not always the same as the selector of the method that builds it digit I 1 self satisfies d d isDigit name 39digit39 alpha um self letter self digit name 39alphaIIum39 self alphaIIum man Jrs self aptienalSpases 2 Iself unit rs eepv fithfirst 1 as SymbulHH name 39identif ier39 135 i quotI a 1 Itself string 39if Iself string 39then lself string 39else39I gt rl self spaces a self unit ril name 39kevwer 39 identifier self lower gtgt J PORTLAND STATE UNIVERSITY Obtain the name reflexiver PORTLAND STATE UNIVERSITY Obtain the name reflexiver Ea sfies sPredisate quotWhen evaluated 139 parse an item f mm the input and chew1 Whether it satis es aPredhsste If it dI J ES I will answer that item if it dees rst I failquot 1 self satisfies aPr edfcare name send r salestar PORTLAND STATE UNIVERSITY Obtain the name reflexiver Entries aPredreate quotWhen evaluated 139 parse an item Free the input and chews1 Whether it aarfa ea aPr edieate If it daes I will answer that item if it dees at I failquot self satisfies aPr edr39care name Madmen sender selector I H anarherI amer quotdeterminism ehaiw Anewera a gamer that 1 the GE atquot myself and anatherPareerquot self assert anarherPar aer isParserEur parserEueam I afar start WeenStream position self parse iffail yam positiun Start anatherPamer parseJ asPareerHamed mm Sender seleemr on parserStream PORTLAND STATE UNIVERSITY Obtain the name reflexive Eta sfies aPreu tsate quotWhen evaluated 139 parse an item Free the input and chews1 Whether it satis es aPredttsate If it dees I will answer that item it it sees hat I failquot self satisfies aPredt39eate name Mutter sender salestar I H ahetherParser quotdeterministic cheese Answers a parser that is the GE atquot myself and ahetherParserquot self assert anatherParser isParserEer parserEuesam 1 I star I start parserStream position self parse ifEail parsesStream pasitien start anetherParser parseJ asParserHamed WMsender selector 011 mm Hr aParser quotsequent3mg answers a earner that 1tt39heh run will run the sequential campashlar at myself art51 aParser quot f self gtgt trreletrahtl aParser name this mten sender selector PORTLAND STATE UNIVERSITY btain the name reflexive Ea s es aPreclisate Jean arrnln rauJ I rumMm P ir m F39mm 9147 iMnn pan1 J A i mrhafhawl 3 is a nenrgument 39lael quotsequencing linswers a parser that 1Ii39hen run will first run me and1 then evaluate a ne rgument las 39 1with the result at running me as its argument and then finally run the answer elntainee1 from evaluating the black 1which is assume to be a parser quot 1 I start I start parallaxStream position self parse ifNotEailDo t I a nenrg39ument laelt value v parse ifEeillZIo f I perser tream position start f asParserHamed mistth sender selectan on parsesStream MIT anatherParser parseJ asParserHamed Emmettsender selector on parserStream Hr aParser quotsequencing answers a parser that 1when run Will run the sequential compositian at myself antiI aParser quot f self gtgt irrelet39antl aParser name this mten sender selector PORTLAND STATE UNIVERSITY btain the name reflexive Estuaries aPreu teate have aura lln fad I IiMM n r m F39mm 9h iMnnr nan1 hA i mrhafharn 5 9 a hear gumeht laek quotsequencing answers a parser that 1Ii39heh run will first run me and then evaluate a hegirguateht las 39 with the result at running The as its argument aha1 then finally run the answer attained from evaluating the talemt which is assumed to be a parserquot 1 I start I start parentStream position self parse ifNotEailDo ll391 a hear39g39umeht las value VII parse ifEa Do f l perser tream position start f asParserHamed thistmtu t sender selectorl on parser tream We anatherParser parseJ asParserHamed mm sender selector on parserStream PORTLAND STATE UNIVERSITY Obtain the name reflexively Ee sfiee ePredjeete quotWhen arer A39J I names an Fraun F39mm rho IBMn gnu393 Aha4 mrhafhaw H e hehrgumeht leeh quotsequencing i SW39E FS e per eerquot that 1r39heh run will first mm are end then evaluate e he rgumeht le 39 with the result or runhr hg le as its argument em1 then fin3113quot run the ehewer ebteihed freer evaluating the Meek which is eeeumed re be 5 parserquot 1 I eraH I etc7rquot parserStreem position eelf parse ifNetEa De v lie he r39g39umeht leeh value VII parse iffeilDo f l perserSueem position Starr f asParserIIamed thiinnten sender eeleeter an parm treem 391 e1 pee 101 51 ehetherPereer perseH asPerserHamezil this nntezt sender selector en perserSueem There are only a few combinators that build parsers Each combinator can extract the name from the context PORTLAND STATE UNIVERSITY Structural Equality We say how to build a recursive equality operation in Haskell that reaches down into the structure of a data type Can we do the same in Squeak How is equality defined in Object PORTLAND STATE Io UNIVERSITY Try a new Equality Operation ms ance MinstanEEVars nmdaxedVars nrnslanCEV 395 self class instSIZe mndexedVar self basichze anDbed class inslsze nlnslanCEVars fFalse quot false snobact basmeze r nmdexedVars IiFalse false In nmsancev a 1anObeclmslVarAt f ifFalse quot false se in 1 la nmdexed I self basitAl39 r anDbect bascht r iIFalse quot false true PomANDSmE n Umvmsm How does PORTLAND STATE UNIVERSITY work out What about zipAIIWith We would like to be able to write a to 2 A to 2 zipAIIWith lo up I String with lo with up for n collections and any n argument block Can we do it PORTLAND STATE l3 UNIVERSITY Smalltalk Browsers 0 There are lots of different browsers in the Smalltalk environment 0 system browser hierarchy browser protocol browser inheritance browser inspector explorer change set browser file system browser Each one knows about the structure that it is browsing 0 e g the system browser has hardwired into its code the facts that Categories contain Classes and Classes contain Protocols and Protocols contain methods PORTLAND STATE I4 UNIVERSITY The OmniBrowser The OmniBrowser is a browser for everything and nothing in particular 0 it doesn t know about any system structure instead it is driven by metadata that describes the thing that it is browsing The metadata takes the form of a graph of objects the metagraph The domain that the browser navigates is also a graph of objects the subject graph PORTLAND STATE I5 UNIVERSITY A File System Browser We will build an instance of the OmniBrowser that examines the file system The file system is not a graph of objects That s OK we build OBNodes to represent the entities that we are browsing We define two subclasses of OBNode OBDirectoryNode and OBFileNode What do these OBNodes have to do that is defined by the metagraph PORTLAND STATE l6 UNIVERSITY File System Graph amp Metagraph object node 4 is a child of Itemp pic1jpg pi02jpg picsij PORTLAND STATE l7 UNIVERSITY File System Graph amp Metagraph objectnode 4 is a child of Itemp pic1jpg pi02jpg picsij PORTLAND STATE l7 UNIVERSITY File System Graph amp Metagraph objectnode 4 is a child of temp pic1J39pg pi02jpg picsij PORTLAND STATE l7 UNIVERSITY File System Graph amp Metagraph object node 1 4 is a child of A te mp pic1jpg DiCZjpg picsij PORTLAND STATE UNIVERSITY 4 d Metagraph as data 3 RH DBMetag ph OmniBPUwser Mur phic OEDeFinitinn all FileBr uwser UmniBr UwserNndes 1 UBMetuGruphBuilder 51 browsers I g oh stundurd helper s Uh stundur dhr nwser s OB Andr39ew39 s Experimer Z OmniBmwserNnti cuti OBMetugmph UmniBPUwserPunels OEMudulFilter OmniBrowser Tests UBMur phicPunelLuynut OmniBr39owserUti lities UE StundurdActor s UB Stundur dBr uwser s UB StundardDe nitiur OB Stundurd Nudes 39J R H rl rlT 39 391 VI39IP39 quotI39m P E El mstance J J class 1 171 no TimeStamp DBAndrew s Experiment 1 implementnr only in change set visitors IE 15 doquot 4 r 3 browse J senders JL 1mplementnrs Jtversmns J mheruance J hmrarch sr JUnst vars JL class vars Jlsourcel fileBrnwser 339 l d39r Me I TUBMetaNnde named Directory Me DBMetaNode named 39File39 fir childAt directnries put da r chiidAt files put Me A d 1 PORTLAND STATE UNIVERSITY Metagraph as data is OmniBPUwser Mur phic UmniBr owserNndes oane nmnn OBMetuGruphBuilder OmniEr39awserNoti cuti OBMetugruph UmniBPUwserPunels OBMudulFilter OmniBrowserTests UBMur phicPunelLuynut OmniBrowserUti lities UE Stundurd Actor s UB Stundur dBr uwser s UB StundurdDe nitiur L IIR TQinm39 nr dTm m3 instance I 1 class RE DBMetaggrapvh OB Stundurd Nudes J39 I FileBr uwser 21 all 5 browser s oh stundurd helper s Uh stundur dhr nwser s OB Andr39ew39 s Experimer 3 Eli l 11 no TimeStamp DBAndrew39s Experiment 1 implementnr only in change set visitors fileBmwser I def Me I TUBMetaNnde named Directory Me DBMetaNode named 39File39 dlilr childAt directnries put da r chiidAt files put Me A 1 UN L browse J senders J 1mplementnrs JL versions Jt inhernance Jt huerzatrch sr J quot 1nst vars J class vars J Isourcel directories files PORTLAND STATE UNIVERSITY Introduction to Biological Sequences Background What is DNA Deoxyribonucleic acid Blueprint that carries genetic information from one generation to the next Resides in cell nucleus DNA contains genes Each gene is responsible for the production of a particular protein A strand of DNA is a chromosome Set of chromosomes carried by an organism is a genome DNA Structure Double helix DNA consists of four nucleotides adenine cyostine guanine thymine A C G T 5 prime beginning 3 prime end Base Pairs AT CG Ordering of these pairs is a sequence An example GAATTC CTTAAG DNA Structure Base Fan39s IE AdE ir nE Thymine a Guanine Cylosimar Sugar phusphaae baukbnne U33 F39Jaimrxal Lumen f fquotrerjliurn Example Genome Sizes Species Number of base Number of genes paIrs E coli 4600000 3200 Fruit fly 180000000 13600 Chicken 1000000000 23000 Mouse 2500000000 30000 Corn 2500000000 59000 Human 3000000000 2500030000 Grasshopper 180000000000 Amoeba 670000000000 Why so many base pairs Junk DNA or noncoding DNA Portions of DNA sequence for which no func oniden ed 985 of human genome May serve functions that are not yet understood Why is DNA useful Every living thing on earth uses DNA to store and transmit information Catalogs all the different functions performed in an organism Identify similarities among organisms Identify inherited traits Solving crimes DNA replication DNA molecule splits each half gets copied Why is DNA double stranded More stable Replication consists of halfnew half old Allows for errorcorrection If a base is damaged can correct Like a RAID RNA DNA is blueprint doesn t do much on its own Transcription copy DNA into RNA Only genes get transcribed Promoter DNA sequence that enables gene to be transcribed Exon protein coding sequence of gene Intron sections of DNA that are spliced out after transcription Messenger RNA mRNA moves out of cell nucleus to provide building plans for proteins RNA alphabet Uracil U instead of thymin T Proteins Buildings and machines inside cell Composed of amino acids Analogy DNA and RNA send and store information proteins make things happen Can fold into shapes dependent on their amino acid sequences Protein Examples Collagen shaped like a rod to be used as structural suppo Myosin has a hook that can be used as a motor Found in muscles Protein alphabet 20 symbols 20 amino acids Genetic code Ribosome reads mRNA and writes protein 3 at a time Each 3 letter RNA sequence translates to one of 20 symbols Degenerate 43 64 combinations but only 20 symbols Redundancy An Example Codon translation Position is important What can we do with sequences Biological sequences show complex patterns of similarity to each other Organisms also show similarities Sequences can change over time due to different forces mutation natural selection genetic drift Similarity searches among sequences can help identify these occurrences Mutation Change in a DNA sequence Every time cell divides DNA is duplicated Replication process isn t perfect 1 error in every 300 million letters 10 mutations per genome replication Change in DNA leads to change in RNA which may change protein Mutations may also insert or remove nucleotides Natural Selection Assumptions There must be variation within a population The variation must be heritable Must be differential reproduction based on vana on Variations at DNA level explain differences within population Mutation is constantly happening Genetic Drift Not just natural selection Frequencies can change by purely random processes Suppose 10 individuals 5 C and 5 T Next generation sampling error may cause shift C 06 T 04 Over time C may increase and T may decrease Molecular Clocks In sequences of related organisms some positions change at different rates If you know rate of change can determine how long ago two sequences diverged Simple example Given a protein sequence from cats and dogs 10 differences between them Cats and dogs had common ancestor 50 million years ago Cats and humans have 12 differences in sequence Conclusion cats and humans shared ancestor 60 million years ago Homology We know which organisms exist today But don t know what existed 100 million years ago What was last common ancestor of humans chimpanzees and gorillas Phylogenetics study of relationships between organisms Two sequences are homologous if they share a common ancestor Tree of Life Recall the taxonomy hierarchy from relational lecture Five taxonomic kingdoms animals plants fungi monera protista Based on what you see Using DNA sequences new classification Prokaryotes bacteria and archaea Eukaryotes have a nucleus eg birds trees Why is similarity useful Identify which species are most closely related Before sequences morphological data Hair teeth limbs fins hearts livers eyes etc Sometimes morphological data misleading An exercise How do we measure similarity Exercise measure the similarity of a sequence in three different animals Bone Morphogenetic Protein 7 gene BMP7 Represent signals that induce bone growth Results Animals are in no particular order Rabbit Pig Sheep Any idea which is which CS 405I0 Advanced Programming The Visitor Pattern Andrew P Black lt13 Portlanmae Recap Recall the rows and columns diagram Operations first rest isEmpty ConsList er 0 return e return I false Repres entations EmptyList error error true Each row is a separate class gt adding rows is easy Each column is a method in multiple classes gt adding columns is hard or impossible e Portlan9i tasrs Visitor Synopsis The Visitor pattern turns columns hard to add into rows easy to add ie it turns columns methods into rows classes operations are represented as classes rather than as methods can Portlanmae 3 Example Arithmetic Expressions Represent arithmetic expressions like 1o457 e Portlanmae vroot a Difference vleft an lntegerLiteral value 10 vright a Sum v left an IntegerLiteraI value 4 vright a Product vleft an IntegerLiteral value 5 vright an lntegerLiteral value 7 CIaSS hierarChy Expression BinaryExpression operations like Difference Product numericValue would Quotient normally be implemented Pf ry by recursive traversal of Factor 39 Literal the expreSSIon tree IntegerLiteral RealLiteral eg Negation Difference gtgt numericValue T left numericValue right numericValue Problem each operation prettyPrint typeCheck etc is dispersed over a dozen classes 43 Portlansmers 5 Solution turn operation into a Class 1 Create NumericEvauator Class give it methods called visitDifference visitSum that do the appropriate thing on Difference and Sum nodes eg NumericEvaluator gtgt visitDifference diffNode T diffNode left numericValue diffNode right numericValue Difference gtgt numericValue Compare T left numericValue right numericValue e Portlanmae 6 Solution continued 2 Every concrete class F00 in the Expression hierarchy gets a method accept aVisifor defined as follows Foo gtgt accept aVisitor T aVisitorvisitFoo self Note how the selector of the message tells the visitor what kind of node it is visiting Do this for Foo Difference Product Quotient Sum etc 13 Portlanmae 7 Solution continued 3 At the top of the hierarchy add a single method that provides a client interface Expression gtgt numericValue T self accept NumericEvaluator new 9Kal of the code that implements numeric evaluation is now outside of the Expression classes 9K It s in the NumericEvaluator class a Portlanme 8 Let39s look 1EI RB NumerEEvaluamr aw ESSlDapersuars 5w EmarVExpressmn a r a cummzvem a Dxfference 1 menu Expressmn v s a ampm m A xpressmnvxsuar nsquducx szcepuamm Eacmr nsu uauem mzx mpxemgcus xmegemm nsukealLueral IEEIVExampleerm Lueral nsusum j rtxamplesrxn mm 4 irurxemex n 7 m r m 7 I bravse sender 1 mp m m hm Na m WWI mum mo xen numerxcvalue vac nghx numerchalue Portland State Consequences External code in the visitor must have access to the internals of the visited objects gt all significant state must be public Is this objectoriented New operations can be added without changing the Expression classes Why is this a big deal e Portlanmae The Design Patterns Smalltalk Companion by Sherman R Alpert Kyle Brown Bobby Woolf Foreword by Kent Beck AddisonWesley 1998 lt18gtP rt1an9l ets quot Bioinformatics and BLAST Overview Recap of last time Similarity discussion Algorithms NeedlemanWunsch SmithWaterman BLAST Implementation issues and current research Recap from Last Time Genome consists of entire DNA sequence of a species DNA is the blueprint Contains individual genes Genes are composed of four nucleotides ACGT RNA transcribes DNA into proteins Proteins consist of 20 amino acids Proteins perform the actual functions Recap from Last Time Identify similarities among the same gene from pig sheep and rabbit Things that were hard Manually matching letters Deciding what similar meant Things that would have made it harder What if you had the whole genome What if there were missing lettersgaps Why do similarity search Similarity indicates conserved function Human and mouse genes are more than 80 similar at sequence level But these genes are small fraction of genome Most sequences in the genome are not recognizany similar Comparing sequences helps us understand func on Locate similar gene in another species to understand your new gene Rosetta stone Issues to consider Dealing with gaps Do we want gaps in alignment What are disadvantages of Many small gaps Some big gaps Warning similarity not transitive If 1 is similar to 2 and 3 is similar to 2 is 1 similarto 3 Not necessarily AAAAAABBBBBB is similar to AAAAAA and BBBBBB But AAAAAA is not similar to BBBBBB not transitive unless alignments are overlapping
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'