| Abstract : | Τα πρότυπα σχεδίασης εμφανίστηκαν αρχικά στον χώρο της αρχιτεκτονικής στα μέσα του '70 από τον διάσημο αρχιτέκτονα Christopher Alexander. Ο Alexander όρισε τα πρότυπα με τον εξής τρόπο:" Κάθε πρότυπο περιγράφει ένα πρόβλημα που εμφανίζεται συνέχεια μέσα σε ένα περιβάλλον και στη συνέχεια περιγράφει τον πυρήνα της λύσης κατά τέτοιο τρόπο ώστε η λύση να μπορεί να εφαρμοστεί εκατομμύρια φορές χωρίς ποτέ δύο λύσεις να μοιάζουν μεταξύ τους."Ουσιαστικά, τα πρότυπα πρόκειται για κοινές λύσεις που δόθηκαν σε κοινά προβλήματα σχεδίασης. Για κάθε ένα από αυτά ο Alexander έδωσε το όνομα του προτύπου, το πρόβλημα που επιλύει, τον τρόπο επίλυσης του προβλήματος καθώς και τους περιορισμούς που πρέπει να ληφθούν υπόψη κατά την εφαρμογή του. Και γενικά, ο Alexander περίγραψε πως να σχεδιάζεις και να χτίζεις χρησιμοποιώντας μια γλώσσα από πρότυπα.Η μεταφορά τους στον χώρο της τεχνολογίας λογισμικού πραγματοποιήθηκε από τους Erich Gamma, Richard Helm, Ralph Johnson και John Vlissides που είναι γνωστοί και ως Gang Of Four (GoF). Οι τελευταίοι έγραψαν στις αρχές του '90 το βιβλίο "Design Patterns: Elements of Reusable Object-Oriented Software" που θεωρείται σήμερα η βίβλος των προτύπων σχεδίασης στο λογισμικό. Μέσα στο βιβλίο αυτό περιγράφεται ένας κατάλογος από 23 πρότυπα σχεδίασης. Όπως προκύπτει και από τον τίτλο του βιβλίου, απώτερος σκοπός των προτύπων σχεδίασης είναι η επαναχρησιμοποίηση του λογισμικού. Τα πρότυπα σχεδίασης κατηγοριοποιούνται σε τρεις κατηγορίες: την σχετική με την δημιουργία (creational), την σχετική με τη δομή (structural) και την σχετική με την συμπεριφορά (behavioral). Η τεκμηρίωση ενός προτύπου σχεδίασης ακολουθεί μία συγκεκριμένη δομή και αποτελείται από τα ακόλουθα 13 στοιχεία: όνομα και κατηγοριοποίηση, σκοπός, συνώνυμα, κίνητρο, εφαρμοσιμότητα, δομή, συμμετέχοντες, συνέπειες, υλοποίηση, δοκιμαστικός κώδικας, γνωστές χρήσεις, και σχετιζόμενα πρότυπα.Η ανίχνευση των προτύπων σχεδίασης είναι πολύ σημαντική διαδικασία γιατί βασιζόμενη σε αυτήν μπορούν να βελτιωθούν αρκετές διαδικασίες της τεχνολογίας λογισμικού, όπως π.χ. το redocumenting, το restructuring, το reengineering, το forward engineering κ.α. Η αναζήτηση των προτύπων, γενικά, καταλήγει σε τρία πιθανά αποτελέσματα: σε True positive (TP), σε περίπτωση που ένα πρότυπο έχει αναγνωριστεί και υπάρχει πραγματικά μέσα στο σύστημα που μελετάμε, σε False positive (FP), σε περίπτωση που ένα πρότυπο έχει αναγνωριστεί αλλά δεν υπάρχει πραγματικά μέσα στο σύστημα και σε False negative (FN), σε περίπτωση που ένα πρότυπο υπάρχει μέσα στο σύστημα αλλά δεν έχει αναγνωριστεί από τον αλγόριθμο. Η πρώτη περίπτωση είναι η επιθυμητή ενώ οι υπόλοιπες πρέπει να αποφευχθούν. Με βάση τις παραπάνω τιμές αξιολογούμε την απόδοση των διάφορων αλγορίθμων που έχουν αναπτυχθεί για να υλοποιήσουν την διαδικασία της ανίχνευσης. Ειδικότερα, βάση αυτών των τιμών έχουν ορισθεί δύο μετρικές, η precision και η recall. Η πρώτη μετρική μετρά πόσο καλά ο αλγόριθμος ανίχνευσης βρίσκει αυτό που θέλει ο σχεδιαστής και η δεύτερη πόσο καλά ο αλγόριθμος ανίχνευσης απομακρύνει τα instances που δεν θέλει ο σχεδιαστής. Οι δύο παραπάνω μετρικές είναι οι κύριες παράμετροι που ορίζουν την συμπεριφορά ενός αλγορίθμου ανίχνευσης. Στην βιβλιογραφία έχουν προταθεί ποικίλες μεθοδολογίες σχετικές με την ανίχνευση των προτύπων σχεδίασης μέσα στο λογισμικό. Η εργασία αυτή επικεντρώθηκε σε 4 μεθοδολογίες σχετικές με την ανίχνευση που περιγράφονται συνοπτικά παρακάτω.Η μεθοδολογία 1 χρησιμοποιεί κατευθυνόμενους γράφους ή αλλιώς τετραγωνικούς πίνακες για την αναπαράσταση των πληροφοριών του συστήματος που μας ενδιαφέρει να αναλύσουμε. Γενικά, η μεθοδολογία δεν περιορίζει τους σχεδιαστές όσον αφορά το τι μπορεί να περιγράψουν με τους πίνακες. Ο πυρήνας της μεθοδολογίας αυτής είναι ο αλγόριθμος similarity scoring που αρχικά είχε προταθεί σαν μια λύση στο πρόβλημα της αναζήτησης των εγγράφων στον παγκόσμιο ιστό. Η μεθοδολογία αυτή βασίζεται πάνω στo [1].Η μεθοδολογία 2 βασίζεται πάνω σε βάρη και πίνακες προκειμένου να πραγματοποιηθεί η ανίχνευση των προτύπων σχεδίασης μέσα στον πηγαίο κώδικα. Πιο συγκεκριμένα, η δομή του συστήματος αναπαρίσταται σαν ένας πίνακας όπου οι γραμμές και οι στήλες του είναι όλες οι τάξεις του συστήματος. Η τιμή κάθε κελιού αναπαριστά τις σχέσεις μεταξύ αυτών των τάξεων. Με τον ίδιο τρόπο αναπαρίσταται και η δομή για κάθε πρότυπο. Η ανίχνευση των προτύπων σχεδίασης από τον πηγαίο κώδικα προκύπτει ύστερα από ταίριασμα μεταξύ αυτών των δύο πινάκων. Αν ο πίνακας του προτύπου ταιριάζει με τον πίνακα του συστήματος, τότε έχει βρεθεί ένα υποψήφιο instance του προτύπου. Εκτός, όμως, από τους πίνακες χρησιμοποιούνται και βάρη για να αναπαρασταθούν τα attributes και τα operations κάθε τάξης καθώς και οι σχέσεις της με τις υπόλοιπες τάξεις. Η μεθοδολογία αυτή ασχολείται όχι μόνο με την στατική δομή των προτύπων σχεδίασης αλλά και με την δυναμική και την νοητική και περιλαμβάνει έτσι τρεις φάσεις ανάλυσης που είναι η structural, η behavioral και η semantic. Η μεθοδολογία αυτή βασίζεται πάνω στο [2].Η καινοτομία της μεθοδολογίας 3 είναι μια καινούργια γλώσσα περιγραφής των προτύπων που ανέπτυξαν οι συγγραφείς της. Η γλώσσα αυτή ονομάζεται DPML (Design Pattern Markup Language) και είναι βασισμένη πάνω στην XML. Με την γλώσσα αυτή παρέχεται η δυνατότητα στους σχεδιαστές να ορίσουν και δικά τους πρότυπα πέρα από τα πρότυπα των GoF και να τα τροποποιούν εύκολα κάθε φορά ανάλογα με τις ανάγκες τους. Όσον αφορά την ανάλυση του συστήματος χρησιμοποιήθηκε το framework Columbus που εδώ δημιουργεί μια ενδιάμεση αναπαράσταση του συστήματος (Abstract Semantic Graph). Στην πορεία για την ανίχνευση των προτύπων σχεδίασης χρησιμοποιείται ο αλγόριθμος pattern miner ο οποίος συνδυάζει τάξεις του συστήματος με αυτές των προτύπων σχεδίασης και ελέγχει αν αυτές σχετίζονται με κάποιο τρόπο μεταξύ τους. Η μεθοδολογία αυτή βασίζεται στα [3] και [4]. Η μεθοδολογία 4 είναι βασισμένη πάνω σε έναν νέο αλγόριθμο ανίχνευσης που λειτουργεί επαυξητικά αντί να προσπαθεί να αναλύσει ένα μεγάλο ενδεχομένως σύστημα λογισμικού σε ένα μόνο πέρασμα και χωρίς καμιά ανθρώπινη παρέμβαση. Αυτός ο καινούριος αλγόριθμος εκμεταλλεύεται τη γνώση για το domain και το context που δίνεται τόσο από τον σχεδιαστή όσο και από μια πρόσθετη ειδική δομή που είναι το annotated abstract syntax graph (ASG) του προγράμματος. Στόχος, λοιπόν, εδώ είναι η διαδικασία της ανίχνευσης να είναι ημιαυτόματη και να επιτρέπει στον σχεδιαστή να ορίζει τα δικά του πρότυπα . Ειδικότερα, σε αυτή την μεθοδολογία τα πρότυπα ορίζονται σαν graph-rewrite-rules δηλαδή πρόκειται για κανόνες που επανεγγράφουν έναν γράφο. Η μεθοδολογία αυτή αποτελείται από δύο φάσεις ανάλυσης, την στατική και την δυναμική. Ο αλγόριθμος που χρησιμοποιείται στην στατική ανάλυση συνδυάζει μια bottom-up στρατηγική με μια top-down. Επιπλέον, οι συγγραφείς εισήγαγαν την έννοια των fuzzy sets για να βελτιώσουν την προσέγγισή τους και να μειωθεί ο μεγάλος αριθμός των FP που επέστρεφε ο αλγόριθμος ανάλυσης. Τα fuzzy sets στην ουσία εκφράζουν τον βαθμό της ακρίβειας των κανόνων. Η δυναμική ανάλυση χρησιμοποιείται στην πορεία για να επιβεβαιώσει ή να απορρίψει τα αποτελέσματα της στατικής ανάλυσης. Ο ορισμός των κανόνων και στην δυναμική ανάλυση πραγματοποιείται από graph-rewrite-rules. Η μεθοδολογία αυτή βασίζεται πάνω στα [5], [6], [7].Η εργασία αυτή επικεντρώθηκε πέρα από την ποιοτική σύγκριση των μεθοδολογιών και στην ποσοτική σύγκρισή τους. Τα εργαλεία των μεθοδολογιών 1, 2 και 4 ανιχνεύουν πρότυπα σε προγράμματα Java ενώ το εργαλείο της μεθοδολογίας 3 σε προγράμματα C++. Για το λόγο αυτό, η μεθοδολογία 3 δεν έχει συμπεριληφθεί στην ποσοτική σύγκριση των μεθοδολογιών. Στα πλαίσια της ποσοτικής σύγκρισης πραγματοποιήθηκε η ανίχνευση των προτύπων πάνω στο ίδιο σύνολο δεδομένων, δηλαδή πάνω στο ίδιο πρόγραμμα. Το πρόγραμμα που χρησιμοποιήθηκε, λοιπόν, είναι το JHotDraw που πρόκειται για ένα σχεδιαστικό εργαλείο. Η έκδοση που εξετάστηκε είναι η 5.2. Αρχικά έγινε η διεξοδική μελέτη της τεκμηρίωσης του συστήματος καθώς και άλλων πηγών από το web προκειμένου να βρεθούν τα πραγματικά instances που έχουν υλοποιηθεί μέσα στο JHotDraw. Στην συνέχεια, κάθε instance που επέστρεψαν τα εργαλεία αξιολογήθηκε είτε ως TP είτε ως FP ύστερα από την σύγκρισή τους με τα πραγματικά instances του προγράμματος. Στην πορεία, για κάθε πρότυπο που ανιχνεύουν τα εργαλεία υπολογίστηκε η τιμή των μετρικών precision και recall για να μπορέσει να γίνει αργότερα η αξιολόγηση των εργαλείων. Η σύγκριση των μετρικών precision και recall έγινε ανάμεσα σε αυτά τα εργαλεία που εκ κατασκευής ασχολούνται με το ίδιο πρότυπο. Τέλος, έγινε μια γενικότερη αποτίμηση των αποτελεσμάτων και παρουσιάστηκε η πληροφορία όσον αφορά ποια εργαλεία ενδείκνυνται περισσότερο για την ανίχνευση κάθε προτύπου.Η ανίχνευση των προτύπων, γενικά, δεν πρόκειται για μια εύκολη διαδικασία. Κάποια προβλήματα που συναντάμε εδώ είναι οι παραλλαγές υλοποίησης (implementation variants problem), οι μικρές παραλλαγές των πρωταρχικών προτύπων, τα προβλήματα κλιμάκωσης που εμφανίζονται όταν μεγαλώνει ο χώρος αναζήτησης, πρότυπα με ίδια δομή ή/και συμπεριφορά που δεν είναι εύκολο να τα ξεχωρίσει ένας αλγόριθμος κ.α. Επιπρόσθετα, ούτε η σύγκριση των μεθοδολογιών μεταξύ τους είναι απαλλαγμένη από δυσκολίες. Ορισμένα συστήματα υπό εξέταση δεν έχουν λεπτομερή τεκμηρίωση για την σχεδίαση του κώδικά τους. Επομένως, δεν είναι σαφές ούτε ποια πρότυπα έχουν χρησιμοποιηθεί ούτε που ακριβώς έχουν εφαρμοστεί μέσα σε κάθε σύστημα. Όμως, χωρίς την γνώση αυτής της πληροφορίας είναι γενικά δύσκολο να μετρήσουμε τις τιμές precision και recall κάθε μεθοδολογίας και κατ’ επέκταση να τις συγκρίνουμε μεταξύ τους. Επιπλέον, η πληροφορία από τα αποτελέσματα των πειραμάτων που συνήθως διεξάγονται δεν έχει καταγραφεί σε μορφή benchmark με αποτέλεσμα η σύγκριση των μεθοδολογιών να μην είναι εύκολη διαδικασία. Για το λόγo αυτό, πρέπει να δοθεί έμφαση στην σημασία του benchmarking των instances σε διάφορα συστήματα που συνήθως εξετάζονται. Συμπερασματικά, η ανίχνευση των προτύπων στον πηγαίο κώδικα είναι ένα σημαντικό πρόβλημα που, μέχρι τώρα, είναι άλυτο; εάν όμως λυθεί αποτελεσματικά, θα βοηθήσει πολύ τους σχεδιαστές να αναπτύσσουν συστήματα που θα τηρούν πιστά τις καλές αρχές σχεδίασης. Γενικά, η αποτελεσματική ανίχνευση των υλοποιημένων προτύπων θα βοηθούσε στη κατανόηση του συστήματος, στον έλεγχο της σχεδίασης καθώς και στην συντήρηση του λογισμικού. Επιπλέον, θα παρείχε το έδαφος για περαιτέρω βελτιώσεις του υπάρχοντος συστήματος.
The concept of design pattern originally came from Christopher Alexander, a professor of Architecture at the University of California, and was enthusiastically adopted by the object technology community. The reason for this willing adoption was that the OO community needed a higher abstraction concept to facilitate design reuse beyond classes and objects. The main book in pattern community is the “Design Patterns: Elements of Reusable Object-Oriented Software”. The authors of that book are Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides and are also known as GoF (Gang of Four).Design patterns became an important part of software practice, fundamentally impacting the design of commercial systems, class libraries, etc. They capture the distilled wisdom of design communities by describing a set of recurring problems, proven solutions to those problems, and the conditions under which the solutions can be applied. They are usually presented as part of a catalog that includes a set of patterns relevant to a particular problem domain or application area. When a designer is faced with a design difficulty, the relevant catalogs provide guidance on how to address the difficulty. This idea continues to gain influence; patterns are being discovered and applied in many emerging areas. Besides offering proven solutions using patterns purportedly provides additional advantages: design patterns define terminology that improves communication among designers or from designers to maintainers. They also make it easier to think clearly about a design and encourage the use of best practices. Moreover, using patterns improves programmer productivity and program quality.The recognition of design patterns is a crucial question in software engineering, since they represent a high level of abstraction in OO design. One possible usage might be in measuring the quality of a software system. This can help the project managers to decide whether a code is good enough to be used in the project. Good enough means that the code should be readily understandable, and it should be easy to modify parts of the code without needing to modify the whole code. So if the design patterns are well documented, it should be much easier to understand the source, and to make appropriate modifications on a well-defined part of it. Another possible usage is in helping documenting a source without proper comments on patterns for gaining advantages described above. Well-commented program code is much easier to maintain than the one without comments or with poor comments. We can find pattern instances and this way help inserting comments where it is necessary. Yet another possible usage is in forward engineering, when the system designers inspect the source to see if the coders implemented the pattern correctly.The search for patterns leads to three possible results: true positive in case a pattern has been recognized and the pattern is really implemented within the software system, false positive in case a pattern has been recognized and the pattern is not really implemented within the system and false negative in case an implemented pattern has not been recognized. The first case is desired and the other two have to be avoided.Based on the achieved results it is possible to derive metrics for the evaluation of searching tools, as described by the recall and the precision of the corresponding algorithms. Both metrics are used widely for evaluating search results, e.g. in Information Retrieval. Recall is the number of all implemented patterns in a software system divided by the number of recognized patterns. A recall of 100% means that all implemented patterns were recognized. Precision is the ratio of recognized and really implemented patterns divided by the number of recognized patterns. A precision of 50% means that half of the recognized patterns are not really implemented in the software system. Both values have to be taken into consideration for a tool evaluation. There have been proposed a number of methodologies about design pattern detection in the literature. This paper focuses on 4 methodologies that are briefly presented below.In methodology 1 both the system under study and the design pattern to be detected are described in terms of graphs. In particular, the approach employs a set of matrices representing all important aspects of their static structure. Each class relationship, such as generalization, creation, and delegation, is represented by a matrix. For the detection of patterns, it employs a graph similarity algorithm, which takes as input both the system and the pattern graph and calculates similarity scores between their vertices. The major advantage of this approach is the ability to detect not only patterns in their basic form (the one usually found in the literature) but also modified versions of them (given that the modification is limited to one pattern characteristic). This is a significant prerequisite since any design pattern may be implemented with myriad variations. Moreover, the system is partitioned to clusters of hierarchies (pairs of communicating hierarchies), so that the similarity algorithm is applied to smaller subsystems rather than to the entire system in order to reduce the size of the exploration space.Methodology 2 presents a novel approach based on matrix and weight to discover design patterns from source code. In particular, the system structure is represented by a matrix with the columns and rows being all classes in the system. The value of each cell represents the relationships among the classes. The structure of each design pattern is also represented by another matrix. The discovery of design patterns from source code becomes matching between the two matrices. If the pattern matrix matches the system matrix, a candidate instance of the pattern is found. Besides matrix, we use weight to represent the attributes/operations of each class and its relationships with other classes. The discovery process includes several analysis phases, the structural, the behavioral and the semantic. This approach is based on the XMI standard so that it is compatible with other techniques following such standard.Methodology 3 introduces a method for mining design pattern instances using the Columbus reverse engineering system. Columbus represents a C++ source code in the form of an Abstract Semantic Graph (ASG), and this approach to locating patterns was to try to find the patterns structures in the graph using a custom-made pattern matching method. In this system the structure of a design pattern is stored using a special format based on XML. This format, the Design Pattern Markup Language (DPML), is appropriate for storing the structure of a design pattern by capturing the prescribed design elements found in the conceptual description. This includes classes, their required attributes and operations, and the relations between the participants. Finding a design pattern via this approach means, then, applying the graph matching algorithm with the DPML description to the ASG. Clearly, since other information besides the mere structure of a graph fragment is not used, many false pattern instances could be found using this approach. In addition, authors made an enhancement to this pattern matching-based approach. This enhancement uses machine learning methods to further refine the pattern mining by marking the pattern instance candidates returned by the matching algorithm either as true or false instances, and this way produced better results.Methodology 4 is based on a new recognition algorithm which works incrementally rather than trying to analyze a possibly large software system in one pass without any human intervention. The new algorithm exploits domain and context knowledge given by a reverse engineer and by a special underlying data structure, namely a special form of an annotated abstract syntax graph. The authors developed a graphical rule definition language based on graph-rewrite-rules with a left and a right side. Each pattern that should be searched for is defined by the left side of such a graph-rewrite-rule. The right side of the rule consists of the pattern together with the annotation node that has to be added to the ASG. By successfully applying these rules to the ASG, pattern instances are recovered. The information of a found pattern instance is stored by the annotation node linked to the ASG elements that are participating in the pattern’s instance. In addition, this analysis algorithm combines a bottom-up strategy and a top-down strategy. The overall analysis finishes when all possible annotations are created. Also, it is used the theory of fuzzy sets to express the impreciseness of the rules. Besides static analysis, the authors suggest using runtime data to check the behavioral aspect of patterns dynamically. The runtime information is gathered during program execution using a debugging tool. This paper also focused on the comparison of the methodologies described above. We didn’t compare the tool of methodology 3 because it detects design patterns in C++ source code in contrast with the others that detect patterns in java programs.The three methodologies evaluated on JHotDraw 5.2, which is an open source GUI framework for technical and structured graphics. This project has been selected because the authors explicitly indicate the implemented design patterns in the documentation and in this way it was possible to evaluate the results of these methodologies. The experiment started with writing down the actual design pattern instances (system classes associated with pattern roles) on that project. Then, we tested each methodology and interpreted the results by counting the number of correctly detected patterns (TP), False Positives (FP), and False Negatives (FN). We evaluated the effectiveness of each pattern detection methodology by calculating the recall and precision metrics. The comparison of the above metrics became between the tools that detect the same design patterns. Finally, we show which tool is the best for the detection of each design pattern.In general, the detection of design patterns is not an easy process. Some problems that we meet here are the implementations variants problem, the scalability problem which appears in large exploration space, design patterns with the same structure and/or behavior, etc. Moreover, the comparison of different methodologies is not easy too. Some systems typically do not have detail design documentation. Hence, it is unclear which design patterns have been used and where they are applied in the systems. Without such information, it is hard to measure the precision and recall of design pattern discovery approaches. So, it is important to emphasize the importance of benchmarking design pattern instances existing in different open-source systems. All in all, the identification of implemented design patterns could be useful for the comprehension of an existing design providing the ground for further improvements. Furthermore, it would help designers to maintain the software systems by following best practices.
|
|---|
Copyright © 2013 Library AUEB. All rights reserved.