Advanced Development Techniques

Tecniche Evolute di Progettazione e Sviluppo del Software


Abstract

This curriculum of the PhD school in Computer Science of the University of Milan focuses on the most recent and advanced development techniques and on their limitations. In particular the activated courses cover the whole software lifecycle (designing, programming, testing, debugging and development tools) providing a complete overview of the current trends in software development research area.

To complement the curriculum the interested student can attend:

Board.

Curricula Coordinators: Walter Cazzola and Sebastiano Vigna.

Scientific and Teaching Board.

Paolo Boldi, Walter Cazzola, Mattia Monga Giovanni Pighizzini, Massimo Santini, Sebastiano Vigna

Activated Courses and Scheduling

In this curriculum of the PhD school in Computer Science we have activated five courses that cover the whole software development process with particular attention to programming techniques. Courses are listed sorted by time; details can be found following the links.

Schedule Course's Title Lecturer(s)
June 2009 Search Engines Design and Development Sebastiano Vigna
Sep. 2009 Advanced Programming Techniques Walter Cazzola
Oct. 2009 Implementation Techniques of AOP and Reflection Shigeru Chiba
Jan. 2011 Systematic Debugging Techniques Massimo Santini
Feb. 2011 Functional Programming in a Nutshell with Haskell and F# Microsoft
Jul. 2012 An Introduction to Reflection and Context-Oriented Programming Mens, K., S. Gonzalez
Sep. 2012 Computational Types, Collection Types and Monads Eugenio Moggi
Mar. 2013 Development by Contract Mattia Monga
May 2013 Systematic Debugging Techniques Massimo Santini
Apr 2014 Modular Language Implementation Cazzola, W., E. Vacchi
Sep. 2014 Search Engines Design and Development Sebastiano Vigna
Nov. 2014 From Lightweight Validation to Formal Certification Alberto Momigliano
Apr. 2015 Special Topics in Domain Specific Languages Marjan Mernik
Jun. 2015 Parallel Haskell on Multi­Cores and Clusters Hans Wolfang Loidl
Nov. 2015 Approximation Algorithms Sebastiano Vigna
Sep. 2016 Structural Analysis of Petri Nets Lorenzo Capra
Jan. 2020 Regression Test Selection and Prioritization Sudipto Ghosh
Search Engines Design and Development

Schedule First Edition (2009)

Day Time Room
03 June 2009 10:00-12:00 Auletta 5
03 June 2009 14:30-16:30 Auletta 5
04 June 2009 10:00-12:00 Auletta 6
05 June 2009 10:00-12:00 Auletta 5
08 June 2009 14:30-16:30 Auletta 5
09 June 2009 10:00-12:00 Auletta 5

Schedule Second Edition (2014)

Day Time Room
15 September 2014 09:30-11:30 1st Floor Meeting Room
16 September 2014 09:30-11:30 1st Floor Meeting Room
18 September 2014 09:30-11:30 1st Floor Meeting Room
19 September 2014 09:30-11:30 1st Floor Meeting Room
22 September 2014 09:30-11:30 1st Floor Meeting Room
23 September 2014 09:30-11:30 1st Floor Meeting Room

Lecturer

Sebastiano Vigna (Ph.D.) is currently an associate professor at the Computer Science Department of the University of Milano, and a member of the Laboratory for Web Algorithmics. His research interests include web-graph compression and analysis, indexing of large document collections, high-performance parallel web crawling and automatic generation of software from conceptual models. He has written more than 70 technical papers about these research topics.

Topics

References

  1. Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008
  2. Ricardo A. Baeza-Yates and Berthier Ribero-Neto. Modern Information Retrival. Addison-Wesley. 1999.
  3. Soumen Chakrabarti. Mining the Web: Discovering Knowledge from Hypertext Data. Morgan-Kauffman. 2002.
Advanced Programming Techniques

Schedule

This lecture has been split in two parts: the first part introduces some basic concepts on reflection and aspect-oriented programming and is propaedeutic to Chiba's lectures in the last week of September; second part will present some advance in aspect-oriented programming research, open issues and applications.

Fist Part

Day Time Room Slides
23 September 2009 10:30-12:30 Auletta 5 theory
23 September 2009 14:00-16:00 Auletta 5  
24 September 2009 10:30-12:30 Auletta 5 java
24 September 2009 14:00-16:00 Auletta 5  
25 September 2009 10:30-12:30 Auletta 5 AOP
25 September 2009 14:00-16:00 Auletta 5  

Second Part

Day Time Room Slides
20 January 2010 09:00-13:00 Aula τ  
20 January 2010 14:00-18:00 Aula τ  
22 January 2010 09:00-13:00 Aula 5  

Note that on Wednesday we will have a hands-on-session on aspect-oriented programming whereas on Friday the students will propose their seminars.

Lecturer

Walter Cazzola (Ph.D.) is currently an associate professor at the Department of Computer Science of the Università degli Studi di Milano, Italy and the chair of the ADAPT research group. His research interests include reflection, aspect-oriented programming, programming methodologies and languages. He is the designer of the mChaRM framework, of the @Java, [a]C#, Blueprint programming languages and he is currently involved in the designing of the neverlang general purpose compiler generator. He has written more than 70 technical papers about reflection and aspect-oriented programming.

This lecture will present one of the most recent approached to the software development, that is, the aspect-oriented programming and software development.

Topics

Aspect Oriented Programming and Software Development

Asymmetric Approaches: AspectJ and Prose

Symmetric Approaches: HyperJ

Aspect-Oriented at Work

Open Issues and Future Perspectives

References

  1. Robert E. Filman, Tzilla Elrad, Siobhán Clarke and Mehmet Aksit, editors. Aspect-Oriented Software Development. Addison-Wesley. 2004.
  2. Joseph D. Gradecki and Nicholas Lesiecki. Mastering AspectJ: Aspect-Oriented Programming in Java. John Wiley and Sons. 2003.
  3. Ivar Jacobson and Pan-Wei Ng. Aspect-Oriented Software Development with Use Cases. Addison-Wesly. 2004.
Implementation Techniques of AOP and Reflection

Schedule

Day Time Room Slides
28 September 2009 9:00-13:00 Auletta 4 modularization
29 September 2009 9:00-13:00 Auletta 4 AOP-impl
30 September 2009 9:00-13:00 Aula Tau refl-impl

Lecturer

Shigeru Chiba (Ph.D.) is currently a full professor at the Department of Mathematical and Computing Sciences of the Tokyo Institute of Technology, Japan. His main research interests concern programming language design, open compilers, meta-object protocols, reflection, and aspect-oriented programming. Chiba is the designer of OpenC++, OpenJava, and Javassist. Javassist is his most successful software, which is now a core component of Redhat/JBoss products. He has written and has served as a reviewer of a number of technical papers about computational reflection and aspect-oriented programming.

Hands-on-session. The last day of the lecture will be partially devoted to a hands-on-session to develop an aspect-oriented framework. To deal with the hands-on-session each student should have their own laptop (the labs are busy with the grad/undergrad lectures) with JDK 1.5/1.6, Javassist and JastAddJ installed and running. Please let me know if you have problems in preparing your system.

This lecture presents implementation techniques for Aspect-Oriented Programming (AOP) and/or reflective languages. The reflection mechanism is one of the source of AOP. This lecture introduces the implementation of reflective languages as the basis of the implementation of early AOP languages.

Topics

References

  1. Shigeru Chiba. Load-Time Structural Reflection in Java. In Proceedings of ECOOP 2000. LNCS 1850, pages 313-336, Cannes, France, June 2000. Springer
  2. Shigeru Chiba and Kiyoshi Nakagawa. Josh: An Open AspectJ-like Language. In Proceedings of AOSD'04, pages 102-112, Lancaster, UK, March 2004.
  3. Ira R. Forman and Nate B. Forman. Java Reflection in Action. Manning Publications. October 2004.
  4. Yoshiki Sato, Shigeru Chiba and Michiaki Tatsubori. A Selective, Just-in-Time Aspect Weaver. In Proceedings of GPCE'03, LNCS 2830, pages 189-208, Erfürt, Germany, September 2003.
Systematic Debugging Techniques

The lecturers can be found here

Schedule First Edition (2011).

Day Time Room
01 February 2011 10:00-14:00 sala riunioni 1º piano
02 February 2011 10:00-14:00 sala riunioni 1º piano
03 February 2011 10:00-14:00 sala riunioni 1º piano
04 February 2011 10:00-14:00 sala riunioni 1º piano

Schedule Second Edition (2013).

Day Time Room
20 May 2013 10:00-14:00 auletta 4
21 May 2013 10:00-14:00 sala riunioni 1º piano
22 May 2013 10:00-14:00 auletta 4
23 May 2013 10:00-14:00 sala riunioni 1º piano

Lecturer

Massimo Santini (Ph.D.) is currently an assistant professor at the Department of Computer Science of the University of Milano, and a member of the Laboratory for Web Algorithmics. His research interests include design and analysis of algorithms with particular regard to distributed high performance web algorithmics. He has written and has served as reviewer of several technical papers about these research topics.

All the material of the lectures can be found in: Santini's SDT Web Page. The lecturer asks those that will attend to fill this questionnaire.

Topics

References

  1. Andreas Zeller. Why Programs Fail: A Guide to Systematic Debugging. Morgan Kaufman. 2009
  2. Grötker T., U. Holtmann, H. Keding and Markus Włoka. The Developer’s Guide to Debugging. Springer-Verlag. 2008
  3. David Astels. Test-Driven Development: A Practical Guide. Prantice Hall PTR, July 2003.
  4. Brian W. Kerningham and Rob Pike. The Practice of Programming. Addison Wesley. 1999.
  5. Steve McConnell. Code Complete: A Practical Handbook of Software Construction. Microsoft. 2004.
Functional Programming in a Nutshell with Haskell and F#

Schedule

Day Time Room Slides
07 February 2011 9:00-13:00 sala lauree intro
07 February 2011 14:30-16:30 sala lauree haskell 1 2
08 February 2011 9:00-13:00 sala lauree F#
08 February 2011 14:30-16:30 aula τ  

A hands-on-session is foreseen for the 8 of February for those that want to use their laptops (mandatory for those not enrolled at the University of Milano) you need to install F# (it works on linux as well but it is better to have visual studio 2010) and XNA 4.0.

Code for the hands-on session ZIP

Note that, the exam consists on a 2-page paper on the benefits/drawbacks of using functional languages in your research area. The paper is due by the 15th of March and should be sent to giotam[_AT_]microsoft.com.

Lecturers

Giordano Tamburrelli is Academic Developer Evangelist at Microsoft Italia. He is currently responsible for all the academic initiatives for faculties and students in Italy. Giordano is currently a PhD candidate at the Politecnico di Milano in the DeepSe Group. During his research activity he was visiting Ph.D. student at Swinburne University in Melbourne, Australia. His research interests include : Service Oriented Architectures, Context-Aware Systems, and Non-Functional Requirements. Finally, he obtained in 2007 a Master in Computer Science Engineering from University of Illinois at Chicago, US.
Matteo Pradella is a researcher at the IEIIT (Istituto di Elettronica e di Ingegneria dell'Informazione e delle Telecomunicazioni) of the Italian National Research Council (CNR) since December 2001. He received his Ph.D. in January 2001 from Politecnico di Milano. In 2000, 2001, and 2002 he was first visiting Ph.D. student, then visiting reasearcher at the Software Engineering group (code 5546) of the Naval Research Laboratory, Washington, DC. His research interests are mainly in formal languages and automata theory, picture languages, and formal methods for safety-critical and real time systems.
Matteo Rossi received a PhD in Compouter Engineering from Politecnico di Milano in 2003. Since 2005 he is an assistant professor at the Dipartimento di Elettronica e Informazione of Politecnico di Milano. His research interests are centered on Software Engineering, with a focus on languages (in particular formal ones), methods and tools for the specification and analysis of time- and safety-critical systems. He is the co-chair of the Student Contest on Software Engineering (SCORE), which will be held as part of the 33rd International Conference on Software Engineering (ICSE 2011).
Giuseppe Maggiore obtained a Master's Degree in Computer Science from Università Ca' Foscari di Venezia a few years ago. He is now completing a Ph.D. in Computer Science on functional languages, videogames and software engineering. Giuseppe teaches computer graphics and game development at Università di Verona. In the meantime he is also working as a Metro Trainer for the upcoming Windows Phone 7 and he is consulting for various firms on XNA.

Abstract

The functional programming paradigm has received increasing attention in the last few years, as the level of abstraction it provides is well-suited to programming complex applications such as concurrent ones. In this lecture we will present the basic concepts underlying the functional programming paradigm, using the Haskell language as reference. We will also present some more advanced concepts, like type classes and monadic computations.

In the second part of the lecture we will study the functional language F#. F# is unique in that it is the first functional language with a clear commercial (rather than academic) target, and as such is supported by very advanced tools and IDEs. We will start with the basic operators (bind and lambda) and data structures (tuples and lists); then we will move to the imperative constructs (refs and mutable binding); we will study functional datatypes in more detail (tuples, records, discriminated unions); we will see ActivePatterns, a powerful form of computed patterns and we will build a simple and small monadic-style parser; we will study the OO capabilities of the language and its interop capabilities with the rest of .Net; we will then move to computation expressions (monads) and finally we will see code quotations.

An Introduction to Reflection and Context-Oriented Programming

Schedule

Day Time Room
03 July 2012 9:00-13:00 Sala Lauree
04 July 2012 9:00-13:00 Sala Lauree
05 July 2012 9:00-13:00 Sala Lauree
09 July 2012 9:00-13:00 Sala Lauree

Some hands-on-sessions are foreseen during the lectures, due to the variability of the teaching mechanism we chosed to have the lectures in a normal classroom without PCs and you will do the exercises on your own laptop. To do so, you have to install the Pharo system. In case of problems with the installation contact the lecturers that will be happy to help you.

Lecturers

Kim Mens is full Professor in Computer Science at the Université Catholique de Louvain (UCL), Belgium where he leads the REsearch Laboratory on software Evolution And Software Development technology (RELEASeD). He holds the degrees of Licentiate in Mathematics, Licentiate in Computer Science, and PhD in Computer Science from the Vrije Universiteit Brussel (VUB), Belgium. His main research interests include software development, software maintenance and software evolution with a particular emphasis on the programming aspect and tool support. He is one of the originators of the reuse contracts technique for automatically detecting conflicts in evolving software, of the IntensiVE toolsuite for documenting, checking and correcting structural regularities in the source code of software systems. Other research topics that fit this common theme and in which he is interested are software architecture, software variability, reverse engineering, software transformation, software restructuring and renovation, and co-evolution between source code and earlier life-cycle software artifacts. In addition to that he is interested in language engineering and a variety of programming language paradigms such as object-oriented and aspect-oriented programming, reflection and metaprogramming, logic metaprogramming and, more recently, context-oriented programming.
Sebastián González is a postdoc research fellow at the Computing Science Engineering pole of the ICTEAM institute at Université Catholique de Louvain, Belgium. His research currently focuses on programming language engineering for adaptive systems and dynamic software composition. He is the main driving force behind the context-oriented software development research team that is part of the RELEASeD lab led by Prof. Kim Mens. Sebastián's principal areas of interest include programming paradigms, programming language design, formalization and implementation, meta-programming and computational reflection, adaptive computing, live software evolution, context-oriented programming, and software composition and variability.

Abstract

The aim of this course is to take a closer look at the paradigm of computational reflection and the novel programming paradigm of context-oriented programming. The object-oriented programming language Smalltalk will be used as a vehicle to introduce the course matter. After having introduced the basics of reflection and the essence of the Smalltalk programming language, the reflective features and meta-object protocol of the Smalltalk language will be studied. The Smalltalk language was chosen because of its conceptual pureness and because it is a fully reflective language which has been a source of inspiration for many other languages (like Java, Ruby or Objective-C). All sessions will be a mixture of traditional course lectures and practical hands-on sessions on the computer. At the end of this course the students will have acquired both a conceptual knowledge of and hands-on experience with the concepts of computational reflection and context-oriented programming, while at the same time having being exposed to the Smalltalk programming language.

Course Organization

The course is organized in 4 slots of 3/4 hours.

Slot 1 : (4 hours) Introduction to reflection and Smalltalk

Slot 2 : (4 hours) Reflection in Smalltalk

Slot 3 : (4 hours) Context-oriented programming

Slot 4 : (~3 hours) Context-oriented programming (2)

For the hands-on sessions you need to install on your laptop the Pharo system.

All the slides and exercise are availabel at RELEASeD's web page.

Assignment

The following tasks are required from those willing to receive PhD course credits:

  1. Finish the remaining context-oriented programming practical guides listed above. Upon completion you will have a minimal but functional COP framework, which should pass all furnished unit tests (besides other tests you might have added on your own).
  2. Extend the COP framework by picking one of the proposed extensions. Your extension should include sufficient testing code to show that it complies with your design.
  3. Write a succinct report describing your framework extension (i.e. all you want to communicate that cannot be easily observed from your commented code).

Your Smalltalk code should be furnished as one or more Monticello packages, just like the exercise and answer code from the practical sections. For information on Monticello, please consult Pharo by Example.

All files should be packaged as a compressed archive and sent by e-mail to Kim Mens and Sebastián González before 3 September 2012.

If you need help or have questions concerning the assignment, please do not hesitate to ask.

Computational Types, Collection Types and Monads

Schedule

Day Time Room
06 Sept. 2012 10:30-13:30 1st floor meeting room
06 Sept. 2012 14:30-17:30 1st floor meeting room
11 Sept. 2012 10:30-13:30 1st floor meeting room
11 Sept. 2012 14:30-17:30 1st floor meeting room

Lecturer

Eugenio Moggi (Ph. D) is currently a full professor in computer science at Università degli Studi di Genova. Previously he was lecturer in computer science at the University of Edinburgh and assistant professor at Univesità degli Studi di Pisa. His research interests are semantics of programming languages and program logics. He first described the general use of monads to structure programs. Details are available from http://www.disi.unige.it/person/MoggiE/ .

Abstract

In the context of programming languages type systems provide a general and convenient tool for classifying different kind of entities, and in doing so they are relevant for error detection and optimization. We introduce computational types and collection types, appropriate syntax associated to these types (borrowing mainly from Haskell), their mathematical semantics in terms of monads (and algebraic theories), and give an overview of their uses (mainly in the context of Haskell).

The whole course material can be downloaded from here (slides).

Development by Contract

Lecturer

Mattia Monga (Ph.D.) is currently an associate professor at Università degli Studi di Milano (Department of Computer Science) where he teaches "operating systems" courses. He has also worked as a research assistant at the University of Italian Switzerland and as a lecturer at Politecnico di Milano. His main research interests concern software engineering and security. Further information about his research work can be found at http://homes.dico.unimi.it/~monga/

Design by contract (DBC) is an approach to the design and development of software based on explicit "contracts" between the provider and the user of a programming feature. Its roots are in the Hoare's work on the axiomatic basis of programming and was popularized by the Eiffel language. Today several tools can be used to apply DBC in mainstream systems: this course will present basic DBC techniques and explore how to use them to define and check contracts in Java programs.

Topics

What is a contract

Contracts and Abstract Data Types

Design by Contract in Java

References

  1. Barbara Liskov and John Guttag. Program Development in Java: Abstraction, Specifications and Object-Oriented Design. Addison-Wesley. 2000.
  2. Bertrand Meyer. Object-Oriented Software Construction. Prentice Hall, second edition, 1997.
Modular Language Implementation

Schedule

This lecture has been split in two parts: the first part introduces some basic concepts about translators and translating process (in particular about attributed grammars and syntax directed translation); the second part will present Neverlang a modular translator framework and its use to write a fully-fledged Javascript interpreter.

Day Time Room Slides
14 March 2014 09:30-13:30 1st Floor Meeting Room sdt neverlang
15 March 2014 09:30-13:30 1st Floor Meeting Room getting started
16 March 2014 09:30-13:30 1st Floor Meeting Room neverlang.js

Lecturers

Walter Cazzola (Ph.D.) is currently an associate professor at the Department of Computer Science of the Università degli Studi di Milano, Italy and the chair of the ADAPT research group. His research interests include reflection, aspect-oriented programming, programming methodologies and languages. He is the designer of the mChaRM framework, of the @Java, [a]C#, Blueprint programming languages and he is currently involved in the designing of the neverlang general purpose compiler generator. He has written more than 70 technical papers about reflection and aspect-oriented programming.
Edoardo Vacchi is currently a PhD student at the ADAPT-lab. His interests include language development, parsing, compilation and separation of concerns. His master thesis consisted in the development of a dynamically extensible LALR parser generator, called DEXTER, that is now a core part of Neverlang. Currently, he is in charge of the reengineering of the Neverlang language and implementation.

Abstract

In this short course we will show the basics of programming language implementation: how a parser and an interpreter or a compiler are generally implemented, explaining widely-known, practical techniques. In particular, the course will focus on the use of so-called modular language implementation frameworks. These frameworks stress the importance of extensibility and code reuse in the implementation of programming languages. The students will be asked to develop of an extension to a relatively simple programming language using a modular language implementation framework that will be presented during the course.

References

  1. Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison Wesley, Reading, Massachusetts, 1986.
  2. Donald E. Knuth. Semantics of Context-Free Languages. Mathematical Systems Theory, 2(2):127–145, 1968.
  3. Walter Cazzola, Domain-Specific Languages in Few Steps: The Neverlang Approach, in Proceedings of the 11th International Conference on Software Composition (SC'12), Prague, Czech Republic, May-June 2012, Lecture Notes in Computer Science 7306, pp.162–177, Springer.
  4. Walter Cazzola and Edoardo Vacchi, Neverlang 2: Componentised Language Development for the JVM, in Proceedings of the 12th International Conference on Software Composition (SC'13), Budapest, Hungary, June 2013, Lecture Notes in Computer Science 8088, pp. 17–32, Springer.
From Lightweight Validation to Formal Certification

Schedule

Day Time Room
10 November 2014 09:30-12:30 1st Floor Meeting Room
11 November 2014 09:30-12:30 1st Floor Meeting Room
12 November 2014 09:30-12:30 1st Floor Meeting Room
13 November 2014 09:30-12:30 1st Floor Meeting Room
14 November 2014 09:30-12:30 1st Floor Meeting Room

Lecturer

Alberto Momigliano (Ph.D.) is currently an assistant professor at the Computer Science Department of the University of Milano. Alberto Momigliano, after graduating from the University of Milan, went on to receive a Ms in Computation from Oxford University (Tony Hoare adviser) and a Msc and PhD in Pure and Applied Logic from Carnegie Mellon University (Frank Pfenning adviser). He has worked as a research scientist at the University of Leicester and at LFCS Edinburgh. He’s the author of around 40 papers in the area of computational logic and formal methods.

Contents

The purpose of this lectures is to introduce students to the booming field of mechanized semantics and its applications to the formal validation and verification of programming tools such as compilers. Topics will be chosen among the following:

  1. Validation. Before even attempting a formal verification, it is valuable to have some evidence that our soft/hardware artifact makes sense w.r.t. to our specification, if we have one or our intuition. This is where validation tools enter the picture:
    • The X-Check Family. Quickcheck [3] brought property-based random testing to the masses (well, the functional programming masses). Since then Quickcheck-like tools exist for almost any programming language, from C to Java and Scala.We will also discuss alternatives such as SmallCheck [8] and them move to tools that extend this idea to the validation of the design of domain specific languages such as PLT-Redex [4] and αCheck [2].
    • Snapshots Generation. Another approach is model validation, that is evaluating a model “correctness” with respect to their requirements. We have studied the case where models are UML class diagrams with OCL constraints, while the objects populating a system state are a “snapshot” of a corresponding counterpart in the modeled world. Snapshot generation [7] here is achieved using Answer Set Programming, whereby answer sets – roughly, stable models in the logic programming sense – encode non-isomorphic snapshots: this allows us e.g. to make sure that unexpected instances are not generated or to generate all snapshots corresponding to specific expected states. If time permits we will briefly talk about Alloy (http://alloy.mit.edu/alloy).
  2. Verification. We then move to the more labour-intensive job of full verification of either a single program or of a meta-program such as a compiler. To do this we will need a proof assistant, where to perform those proofs, which tend to be mostly interactive. The most wide-spread system are Coq http://coq.inria.fr and Isabelle/HOL http://isabelle.in.tum.de/. As a test case, we will limit ourselves to IMP, the simplest imperative language comprising assignments, conditionals and loops and we will look at:
    • Compiler Verification. To give an idea of recent work in the area (viz. the CompCert project [5], http://compcert.inria.fr/ or the Verified Software Toolchain http://vst.cs.princeton.edu/ [1]), we will define a non-optimizing compiler from IMP to a virtual machine and prove the correctness of this compiler via a semantic preservation argument [6]. If time permits, we may study a representative optimization, dead code elimination, using liveness analysis, and show that it is semantic preserving.

Exam

A small programming/proving project such as some QuickChecking in your favourite PL or adding some features to IMP and then prove something about.

Course Material

All the course material will be available on Ariel

References

  1. Appel, A. and contributors. Program Logics for Certified Compilers. Cambridge University Press, 2014.
  2. Cheney, J. and A. Momigliano. Mechanized metatheory model-checking. In M. Leuschel and A. Podelski, editors, PPDP, pages 75–86. ACM, 2007.
  3. Claessen, K. and J. Hughes. QuickCheck: a lightweight tool for random testing of Haskell programs. In Proceedings of the 2000 ACM SIGPLAN International Conference on Functional Programming (ICFP 2000), pages 268–279. ACM, 2000.
  4. Felleisen, M., R. B. Findler, and M. Flatt. Semantics Engineering with PLT Redex. The MIT Press, 2009.
  5. Leroy, X. Formal verification of a realistic compiler. Commun. ACM, 52(7):107–115, 2009.
  6. Leroy, X. Mechanized semantics - with applications to program proof and compiler verification. In J. Esparza, B. Spanfelner, and O. Grumberg, editors, Logics and Languages for Reliability and Security, volume 25 of NATO Science for Peace and Security Series - D: Information and Communication Security, pages 195–224. IOS Press, 2010.
  7. Ornaghi, M., C. Fiorentini, A. Momigliano, and F. Pagano. Applying asp to uml model validation. In E. Erdem, F. Lin, and T. Schaub, editors, LPNMR, volume 5753 of Lecture Notes in Computer Science, pages 457–463. Springer, 2009.
  8. Runciman, C., M. Naylor, and F. Lindblad. Smallcheck and lazy smallcheck: automatic exhaustive testing for small values. In A. Gill, editor, Haskell, pages 37–48. ACM, 2008.
Special Topics in Domain Specific Languages

Schedule

Day Time Room Slides
28 April 2015 09:00-13:00 1st Floor Meeting Room lecture1
29 April 2015 09:00-13:00 1st Floor Meeting Room lecture2
30 April 2015 09:00-13:00 1st Floor Meeting Room lecture3

Lecturer

Marjan Mernik received the M.Sc. and Ph.D. degrees in computer science from the University of Maribor in 1994 and 1998, respectively. Since 1998, he has been a professor at the Faculty of Electrical Engineering and Computer Science, University of Maribor, Slovenia, teaching various courses on Programming, Programming Languages, Compilers, and Evolutionary Algorithms. He spent a Sabbatical in 2004 at the University of Alabama at Birmingham (UAB), and since then he has been a visiting professor at UAB, where he has been teaching an undergraduate class on Programming Languages and a graduate class on Domain-Specific Languages. He is also a visiting Professor at the University of Novi Sad, Faculty of Technical Sciences, Serbia. His research interests include domain-specific (modeling) languages, grammar-based systems, grammatical inference, and evolutionary computations. In these research areas he has published more than 50 scientific papers in journals with an SCI index, and more than 150 conference/workshop papers. Marjan Mernik has been also active in organizing international conferences and workshops, journal special issues, serving in journal Editorial Boards, and being a member of Program Committees. Marjan Mernik is a member of the IEEE, ACM, EAPLS, and the Editor-In-Chief of Computer Languages, Systems and Structures journal.

Course Description

Programming languages are a programmer's most basic tools. A language is suitable for a programming problem if it makes the programmer productive, and if it allows the programmer to write highly scalable, generic, readable and maintainable code. There are various ways to classify or to group programming languages. We want to emphasize the division of programming languages into general-purpose and domain-specific languages. With general-purpose languages, one can address large classes of problems e.g., scientific computing, business processing, symbolic processing while a domain-specific language (DSL) facilitates the solution of problems in a particular domain. To this end, a DSL provides built-in abstractions and notations specific to the domain of concern. DSLs are usually small, more declarative than imperative, and more attractive than GPLs for a variety of applications because of easier programming, systematic reuse and easier verification. DSLs have been used in various domains and these applications have clearly illustrated the advantages of DSLs over GPLs in areas such as productivity, reliability, maintainability and flexibility. However, the cost for DSL design, development and maintenance has to be taken into account. Without an appropriate methodology and tools this costs can be higher than savings obtained by the later use of DSL. This course introduces students to appropriate methodologies and tools needed to support the development of DSLs.

The general topics of the course will be:

Exam

Students will be examinated on some homework Prof. Mernik will assign them at the end of the lectures.

References

  1. Bentley, J.. Little languages. Communication of the ACM, Vol. 29, No. 8, pp. 711 – 721, 1986.
  2. Hudak, P.. Modular Domain Specific Languages and Tools. Proceedings of Fifth International Conference on Software Reuse, 1998.
  3. Cardelli, L., R. Davies. Service Combinators for Web Computing. IEEE Transactions on Software Engineering, Vol. 25, No. 3, pp. 309-316, 1999.
  4. van Deursen, A., P. Klint, J. Visser. Domain-specific languages: An Annotated Bibliography. ACM Sigplan Notices, Vol. 35, No. 6, 26– 36, 2000.
  5. Spinellis, D., Notable design patterns for domain-specific languages. The Journal of Systems and Software, 56:2001, pp. 91-99.
  6. Wile, D., Lessons learned from real DSL experiments. Science of Computer Programming, Vol 51, Issue 3, pages 265-290, 2004.
  7. Mernik, M., J. Heering, T. Sloane. When and how to develop domain-specific languages. ACM Computing Surveys, Vol. 37, Issue 4, pages 316 – 344, 2005.
  8. Mernik, M., V. Žumer. Incremental Programming Language Development, Computer Languages, Systems and Structures, Vol. 31, Issue 1, pages 1 -16, 2005.
  9. Kosar, K., P. Martinez Lopez, P. Barrientos, M. Mernik. A preliminary study on various implementation approaches of domain-specific language. Information and Software Technology, Vol. 50, No. 5, pp. 390-405, 2008.
  10. van Schagen, J.. Measuring the quality of domain-specific language implementation approaches: Java versus ANTLR. Master Thesis Software Engineering. University of Amsterdam, 2009.
  11. Erdweg, E., P.G. Giarrusso, T. Rendel. Language Composition Untangled. Proceedings of Workshop on Language Descriptions, Tools and Applications (LDTA’12), 2012.
  12. Fister Jr, I., T. Kosar, I. Fister, M. Mernik. EasyTime++: A Case Study of Incremental Domain-Specific Language Development. Information Technology and Control, 2013, 42(1):77–85.
  13. Mernik, M., An Object-Oriented Approach to Language Compositions for Software Language Engineering. Journal of Systems and Software, 86(9): 2451-2464 (2013).
  14. Mernik, M. (Ed.). Formal and Practical Aspects of Domain-Specific Languages: Recent Developments. IGI Global, 2013.
  15. Vacchi E. and W. Cazzola, A Framework for Feature-Oriented Language Development, Computer Languages, Systems & Structures, 2015.
Parallel Haskell on Multi­Cores and Clusters

Schedule

Day Time Room
30 June 2015 14:00-17:00 meeting room 1st floor
01 July 2015 14:00-17:00 meeting room 1st floor
02 July 2015 14:00-17:00 meeting room 1st floor
03 July 2015 14:00-17:00 degree room

No prior knowledge of Haskell assumed

Students are strongly invited to bring their own laptop

Lecturer

Hans Wolfgang Loidl received his PhD degree from the University of Glasgow in 1998 for his research on the parallel implementation of functional languages. From 1999 to 2002 he worked as a postdoctoral research fellow of the Austrian Academy of Sciences at Heriot­Watt University, Edinburgh, on architecture-independent parallelism. From 2002 to 2009 he worked as a postdoctoral researcher in the Theoretical Computer Science group at Ludwig­Maximilians University Munich on the EU­funded EmBounded projects MRG and EmBounded. Since 2009 he is a lecturer at the School of Mathematical and Computer Sciences of Heriot­Watt University, Edinburgruh. He's the author of more than 60 papers in the area of programming languages, parallel computation, foundations of programming, and symbolic computation.

Course Description

While most programming languages struggle to incorporate parallelism into their natural computation models, purely functional languages provide parallel execution for free: due to the absence of side effects, any two non­overlapping sub­expressions can be evaluated in parallel. This offers the programmer an opportunity to exploit the power of modern multi­core architectures with only a fraction of the effort that is needed in traditional, stateful programming languages. In particular, the purely functional language Haskell provides several mechanisms to introduce parallelism, ranging from non­intrusive annotation­style language extensions (such as GpH or Eden), best suited for multi­cores and small­scale clusters, to more explicit ways of encoding coordination (such Cloud Haskell or HdpH), best suited for large­scale distribution. In this lecture series, I will give an introduction to parallel programming in several of these languages extensions, discuss correctness and performance aspects of the resulting parallel programs, and give practical examples for developing parallel code in these extensions. In the first section of the series, after a general introduction to sequential Haskell, I will give an overview of parallel programming in the Glasgow parallel Haskell (GpH) [1,2]. This model adds one primitive to Haskell, which enables the programmer to annotate an expression, marking it for (potential) parallel execution. This approach retains the purely functional nature of the language, is minimally intrusive by only requiring local changes to the program, and delegates most of the cumbersome coordination aspects of the parallel program to an adaptive runtime­system. I will discuss evaluation strategies as an abstraction over this basic programming model that provides a clean separation between computation and coordination. Finally, I will discuss lazy, data­oriented strategies that make use of laziness in order to further improve the parallel performance in operating on large data structures [3].

The second section will cover the Eden [4] extension of Haskell, which adds the concept of a process, akin to a parallel function, to Haskell. While maintaining a high level of abstraction it provides more opportunities for control to programmer more concious about the parallel nature of the application. In particular it can be used to efficiently implement and use skeletons, implementations of parallel patterns, in order to isolate parallelism in the application and avoid exposing low­level details to the application programmer.

The final part of the course will cover more explicit forms of parallelism, using Cloud Haskell [5] and HdpH [6] as programming models aimed for large­scale distribution. These models use a monadic top­level structure of the parallel code, with explicit constructs for communication, and can thereby be more prescriptive about the exact coordination and placement of the parallel tasks.

In this way, an expert programmer can profit from advantages of functional languages in terms of abstraction and modularity to engineer complex orchestrations of large­scale parallel code.

For each of the parallel programming models practical exercises will be given, demonstrating their use on a range of architectures, discussing common techniques for performance tuning, and demonstrating the use of available tools to in the parallel program development and tuning process.

Exam

lab exam at the end of the course

Course Material

TBD

References

  1. P.W. Trinder, K. Hammond, H.­W. Loidl, S.L. Peyton Jones "Algorithm + Strategy = Parallelism", in Journal of Functional Programming 8(1), Jan 1998. DOI: http://10.1017/S0956796897002967
  2. Simon Marlow and Patrick Maier and Hans­Wolfgang Loidl and Mustafa K. Aswad and Phil Trinder."Seq no more: Better Strategies for Parallel Haskell", in Haskell'10: Haskell symposium DOI: http://10.1145/1863523.1863535
  3. Prabhat Totoo, Hans­Wolfgang Loidl. "Lazy Data­Oriented Evaluation Strategies" In FHPC 2014: Workshop on Functional High­Performance Computing, Gothenburg, Sweden, September, 2014. DOI:http://10.1145/2636228.2636234
  4. Rita Loogen and Yolanda Ortega­Mallén and Ricardo Peña­Marí . "Parallel Functional Programming in Eden," Journal of Functional Programming, No. 15(2005),3, pages 431­475
  5. Jeff Epstein, Andrew Black, and Simon Peyton Jones. "Towards Haskell in the Cloud", in Haskell'11: Haskell Symposium, Tokyo, Sept 2011.
  6. Patrick Maier and Robert Stewart and Phil W. Trinder. "The HdpH DSLs for Scalable Reliable Computation", in Haskell'14, ACM Press. DOI http://10.1145/2633357.2633363
Approximation Algorithms

Schedule

Day Time Room
16 November 2015 09:30-11:30 Auletta 5
18 November 2015 09:30-11:30 Auletta 5
20 November 2015 09:30-11:30 Auletta 5
23 November 2015 09:30-11:30 Auletta 5
25 November 2015 09:30-11:30 Auletta 5
27 November 2015 09:30-11:30 Auletta 5

Lecturer

Sebastiano Vigna (Ph.D.) is currently an associate professor at the Computer Science Department of the University of Milano, and a member of the Laboratory for Web Algorithmics. His research interests include web-graph compression and analysis, indexing of large document collections, high-performance parallel web crawling and automatic generation of software from conceptual models. He has written more than 70 technical papers about these research topics.

Abstract

Approximation algorithms are optimization algorithms that return an answer which is not exact, with a guarantee of the distance from the optimal solution. The course is based loosely on Chapter 11 of Kleinberg and Tardos book "Algorithm Analysis"; we will start with greedy algorithms, then explore the pricing method and finally show an example of fully polynomial approximation scheme. In one case, we will be able to show using standard reduction techniques that our approximation ratio is optimal.

Structural Analysis of Petri Nets

TBD

Regression Test Selection and Prioritization

Schedule

Day Time Room Slides
08 January 2020 09:00-13:00 5016 Introduction
10 January 2020 09:00-13:00 5016 Early Approaches
13 January 2020 09:00-13:00 5017 Recent Approaches
15 January 2020 09:00-13:00 5016 Model-Based Approaches (pdf) (pptx)

Note that, the lectures will effectively start at 9:30.

Note the room change for the 13th of January

Lecturer

Sudipto Ghosh (Ph.D.) is a Professor of Computer Science at Colorado State University. He received the Ph.D. degree in Computer Science from Purdue University in 2000. His research interests are in the areas of modeling and testing software in the object-oriented, aspect-oriented, and component-based paradigms. Specific topics include data warehouse testing, fault localization, model-based software development, mutation testing and higher order mutation, and regression test selection. Dr. Ghosh is on the editorial boards of IEEE Transactions on Reliability, Software Quality Journal, and Information and Software Technology. He was a general co-chair of the ACM/IEEE 12th International Conference on Model Driven Engineering Languages and Systems held in Denver in 2009, and the 16th Modularity Conference in Fort Collins in 2015. He was a program co-chair of the Third International Conference on Software Testing, Verification and Validation held in Paris in 2010, the Fourth International Conference on Dependable Systems and their Applications in Beijing in 2017, and the 29th IEEE International Symposium on Software Reliability Engineering in Memphis in 2018. He is a member of the ACM and a Senior Member of the IEEE.

Course Description

In this course, students will be able to learn and apply state-of-the-art techniques for performing regression test selection and prioritization. Regression testing is a critical but expensive activity that is undertaken during software maintenance and evolution to ensure that code modifications do not introduce new faults into previously tested code. To reduce the cost of regression testing, testers may select a subset of the original test set for retesting; in this approach, only the modification-traversing tests are selected. Alternatively, test cases may be prioritized based on scheduling those test cases that maximize some objective such as the rate of fault detection.

This course will teach the fundamental program analysis concepts and objectives underlying test case selection and prioritization. Post-graduate students will be prepared for practical work in the software industry by exposing them to the latest approaches and tools. Students who are interested in cutting-edge research in software testing will also benefit from the course.

The sessions will be organized to give students adequate background in the necessary basic techniques involving control-flow graphs, program dependence graphs, syntax trees, and program slicing. Key objectives and metrics will be introduced for assessing test case selection and prioritization such as test case reduction, safety and precision, fault detection effectiveness, and APFD (Average Percentage Faults Detected).

Every session will involve interactive lectures with in-class assignments. Some sessions will involve the use of personal laptops to install and run regression test selection tools on sample programs. Some sessions will require reading papers published in major software engineering conferences or journals.

Exam

There is no examination. In the early part of the course, students will work on a few written assignments to demonstrate their understanding of program dependence graphs. Later they will evaluate a few regression test selection tools on open source programs and write up a brief report documenting their results.

References

  1. Milos Gligoric, Lamyaa Eloussi, and Darko Marinov. Practical Regression Test Selection with Dy- namic File Dependencies, International Symposium on Software Testing and Analysis (ISSTA 2015), pages 211-222, Baltimore, USA, July 2015.
  2. Simone Romano, Giuseppe Scanniello, Giuliano Antoniol, Alessandro Marchetto. SPIRITuS: a Sim- Ple Information Retrieval regressIon Test Selection approach. Information & Software Technology 99: 62-80, 2018.
  3. Gregg Rothermel, Roland H. Untch, Chengyun Chu, Mary Jean Harrold. Prioritizing Test Cases For Regression Testing. IEEE Transactions on Software Engineering 27(10): 929-948, 2001.
  4. Lingming Zhang. Hybrid regression test selection. Proceedings of the 40th International Conference on Software Engineering, ICSE 2018, pages 199-209, Gothenburg, Sweden, May 27 - June 03, 2018.

Walter Cazzola

Didactics

Publications

Funded Projects

Research Projects

Related Events