ASTEC - Advanced Software Technology

Using Schemas to Reduce Inference in Automated Software Engineering

Pierre Flener

Department of Information Science
Uppsala University

Schemas have been introduced in automated software engineering so as to drastically reduce search spaces. However, a lot of difficult inference remains to be done, such as in the KIDS program synthesis system.

I show how to reduce the amount of inference in synthesis through the introduction of SPECIFICATION SCHEMAs (or specification templates, rather) and the guidance by program schemas. A PROGRAM SCHEMA for a programming methodology M (such as divide and conquer, generate and test, etc) is a couple , where template T is an open program showing the (problem-independent) dataflow and control flow of programs constructed following M, and axioms A constrain the (problem-dependent) programs for the open relations in T, such that the overall (closed) program will really be a program constructed following M.

To illustrate this, and by focusing on the family of assignment problems (such as graph colouring, n-Queens, etc), I show how to adapt the KIDS approach for the synthesis of constraint (logic) programs (CLP) that just pose the constraints, rather than (applicative) Refine programs with explicit constraint propagation and pruning code. KIDS-synthesised (non-optimised) Refine programs are one order of magnitude slower than our synthesised CLP(FD) programs. CLP(Sets) programs are equivalent in expressiveness to our input specifications, but are also one order of magnitude slower than our synthesised CLP(FD) programs. The latter would, after optimising transformations, be competitive with carefully hand-crafted programs.

Finally, I generalise this approach to program optimisation, by introducing the notion of TRANSFORMATION SCHEMA, as a couple of program schemas plus applicability and equivalence conditions.

ASTEC seminar


Room: 1406
Time: 13.15 - 14 (+ coffe and discussion)

Room 1406 is in Building 1, Floor 4, room 06
(in the southern part of the building).
Help on how get here and MIC campus drawing.

There will be an extended period for discissions after the seminar
nourished by buns and coffe.

Speakers are encouraged to
- give an short (5 min) introduction to the subject at the begining of the talk.
- keep the time (listeners are excused if they have to leave at 14.00).

Updated Thursday, 27-Apr-2006 17:27:02 MEST by
Roland Grönroos