From clear specifications to efficient implementations

Title: From clear specifications to efficient implementations
Speaker: Prof. Annie Liu
Time: 4:00pm, Tuesday，Aug.26
Venue: Lecture Room,State Key Lab of Computer Science, Level 3 Building #5, Institute of Software, CAS

Abstract: Two major concerns of study rest at the center of computer science: what to compute, and how to compute efficiently. Problem solving involves going from clear specifications for the “what” to efficient implementations for the “how”. This is challenging because clear specifications usually correspond to straightforward implementations, not at all efficient, while efficient implementations are usually difficult to understand, not at all clear.

This talk gives an overview of a general and systematic method for transforming clear specifications into efficient implementations. The method has three steps: (1) iterate—determine a minimum step to be taken repeatedly, (2) incrementalize—maintain appropriate values incrementally over the repeated steps, and (3) implement—design data structures for the values maintained. We will illustrate the method through examples, taken from problems in hardware design and image processing expressed using loops and arrays, in query processing and access control expressed using set operations, in sequence processing and math puzzles expressed using recursive functions, in program analysis and trust management expressed using logic rules, and in building software components expressed using objects. Finally, we summarize our ongoing projects on a number of fronts.