Kestrel Interactive Development System (KIDS)
KIDS is a REFINE prototype application for algorithm design and program analysis and optimization. It provides intuitive, high-level operations for transformational development of programs from specifications. KIDS was developed by Kestrel Institute with support from RADC, AFOSR, ONR, NSF, and ARPA. KIDS provides operations such as the following for deriving a program from a specification:
- simplify an expression with respect to a set of invariants
- designing tree search algorithms
- incremental maintenance of expensive expressions
- divide-and-conquer algorithms
A typical scenario for using KIDS contains the following steps:
- start with a high-level logical specification
- select, using the mouse, a high-level, transformational operation from a menu
- mark the region of the specification to which the operation is to be applied
The operation is then executed and the resulting program displayed.
Example application areas in which KIDS has derived efficient implementations include: scheduling [slide 1, slide 2], sorting and searching, combinatorial design, graph theory, matching, and linear programming.