Spring 2018


Professor Don Batory batory@cs.utexas.edu
office hours TBD
office hours TBD
Room TBD
Days and Time TBD
Unique # TBD
Ground Rules UTCS Rules to Live By and Academic Honesty
Your Grades Canvas
Final TBD

Prerequisites, Overview, and Goals

This course explores leading edge paradigms for automated software design and software modularity from advances in:

A spectacular example of the integration of most of these areas was realized almost fourty years ago: relational query optimization (RQO). A relational query is specified in SQL, a parser maps it to an inefficient relational algebra expression, a query optimizer optimizes the expression automatically, and an efficient query evaluation program is generated from the optimized expression. SQL is a prototypical declarative DSL. Query evaluation programs are specified as compositions of relational algebra operations; relational algebra is a prototype for compositional programming. Query optimizers achieve automatic programming by rewriting an inefficient expression/program to a semantically equivalent but more efficient expression/program. The cost models that drive expression optimization are examples of program analysis. Mapping a relational algebra expression to an efficient program is generative programming and is an elementary example of model driven engineering.

A "holy grail" of Software Engineering is to replicate the success of RQO in other domains. Feature Oriented Software Development is a generalization, and its ideas are at the confluence mainstream research topics in software modularity, program design and program generation: OO design, product-lines, program refactoring, model driven engineering, program evolution, and program transformations.

Prior offerings of this course lead to student publications and research degrees (M.Sc. and Ph.D). Some publications -- not all -- are listed below, the most recent listed last.

 Programming Assignments

All programming assignments will use Java or Prolog. You can pick up what you need in Prolog, if you are unfamiliar with it. We will use the following software, all of which is free to UTCS students, and all of which has been installed in the UTCS public labs.  The following is for Windows Platforms.  If you use Apple or Linux machines, well, I will try to help as much as I can, but no promises!

Please note that some Java programs will be released and updated during the Semester.  These programs are NOT installed on the UTCS public labs.  You will have to install these updates yourself.  Their links will be posted on assignments.

Course Prerequisites

Basic familiarity with the following topics are assumed -- all that is needed will be covered, but some prior experience helps greatly:

Lecture Notes and Texts

Lecture notes posted online after the lecture as downloadable PPTX files.  This semester, I am using 2 special fonts in my files (linked below).  Install them if you want to see the lecture notes as they appear in class.

Links to the lectures are given below in the Course Outline. There is a required text for this course:

The University Co-op has new copies of this text weighing in at $29. This text is now available as a kindle ebook from Amazon.  Hint: I am unimpressed with today’s ebooks.  They are as expensive as hard copies and ebook software sucks.  Your call. As a free alternative -- a progenitor of this text is Pierce's 1988 CMU Tech Report "A taste of category theory for computer scientists", which  I have annotated.

Class Grades, Projects, and Homework

Final grades will be determined approximately by the following scheme:

  1. Your accumulative programming assignment grade will determine the maximum final grade for the course.  Ex: if you get a "B" average across all of your programming projects, your final grade will be no greater than a "B".
  2. Final counts 35%; midterm counts 35%; classroom participation 15%; and class presentation counts 15%. 

All programming projects are to be submitted through Canvas.  A PDF file must be included on all assignments -- it lists your name and email addresses that are hyperlinked so that I can easily send my comments of your assignment back to you.

Extenuating Circumstances

If you have difficulty meeting the requirements of this course, fail to hand in an assignment, or miss an exam because of extenuating circumstances, please advise the instructor in writing at the earliest possible date so that your situation can be discussed. If you encounter an unexpected medical or family emergency or a random act of Nature that causes you to miss the due date for homework or miss a quiz or exam, you must present suitable documentation in writing to the instructor before special consideration will be given. A file of all written correspondence will be kept by the instructor and decisions regarding them will be made at the end of the semester.


Numbers in [brackets] indicates the estimated number of lectures on a topic. The number indicated is a lower-bound, as there will be class room discussions to work on problems and review of homework assignments. Papers that are listed below are required readings and are accessible via its web link.  The order in which topics are presented might be changed as the class progresses.

The syllabus on the first day of class is here (to be posted after the first class), as I do modify this page as the course progresses, like posting new assignments, readings, and lectures.

[# of lectures + days of discussion]



Pre-Course Survey

1. Introduction to Model Driven Engineering  [5] 

  1. UML class diagrams, MDE models and metamodels, model-2-text mappings
  2. Metamodel constraints, Java Streams, model-to-model mappings
  3. Building Domain-Specific Tools with MDE, bootstrapping MDE Tools
  4. Metamodel Equivalence and Metamodel Refactorings


H1: Mapping to Tables
Tues Sept 1, 10pm

H2: MetaModels
Due Tues Sept 8, 10pm

P1: Model-2-Text 
Mon Sept  7th, 10pm

: Model-2-Model
Due Mon Sept 14th, 10pm

: FSM  Tool
Due Mon  Sept 21st, 10pm

2. Feature Models and Software Product Lines [4] 

  • Feature models, attribute grammars, propositional formulas, SAT solvers
  • Feature model analyses, reasoning about edits
  • Optimizing configurations in SPLs
  • Next generation feature models, feature replication, multi product lines (optional)


H3: Model Equivalence
Due Wed Sept 23rd, 10pm

H4: Conjunctive Normal Form (CNF)
and Feature Model Negation
Due Tues Sept 29, 10pm

Optional H4B:
Feature Model Equivalence
Due Fri Oct 9th, 10pm

P4: Feature Models
Due Mon Sept 28th, 10pm

3. Feature Oriented Software Development (a.k.a. Feature Modularity) [4] 

  • Layered designs, OO virtual machines, collaborations, extensions, mixins, mixin-layers
  • FOSD, principles of uniformity and scalability, generalized modularity, composition
  • HelloWorld.zip example in FeatureHouse



P5: Feature Modularity
Due Tues Oct 20, 10pm


4. Feature Interactions and Product Lines of Product Lines [2]
  • Feature interactions, formal models of feature modules and interactions
  • Software product lines of rank n>1, examples, and open problems


H5: Feature Interaction Algebras
Due Thur Oct 22, 5pm

P6: Product Line of Product Lines
Due Thurs Oct 29, 10pm

5. Refactorings  [3] 

  • Review of Refactorings and Design Patterns
  • Reflective Refactoring


P7: Creating a Simple Visitor
Due Mon Nov 9th, 10pm

6. Design By Transformation [3] 

  • Map reduce, Liskov and Perry substitution principles, refinement, optimization, correct-by-construction
  • Parallel architectures, product lines of streaming applications
  • Product lines of streaming applications


  • Modeling in Event-B (1st 2 chapters)


P8: Gamma
Due Tuesday Dec 1, 10pm

7. Categories [4]

score card for categories

  • Domains, instances, arrows and MDE
  • Pragmatics, inheritance, SPLs, functors, examples, commuting diagrams
  • Products, product families, products of categories, pushouts
  • Applications: portlet synthesis, geodesics, lifting, homomorphisms, test generation



Read Chapters 1-2 in Pierce

H7: Categorical Constructions Solution
Due Friday, Dec 4th 10pm


Final Review  

Post-Course Exit Survey