Using Schemas to Reduce Inference in Automated Software Engineering
Department of Information Science
Uppsala University
Sweden
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
Place: 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).
|
