Software Tools for Automated Program Design, Synthesis, and Auto-Tuning

Software Tools for Automated Program Design, Synthesis, and Auto-Tuning

DOI: 10.4018/978-1-5225-9384-3.ch005


The authors consider the software tools based on algebra-algorithmic models and formal methods of constructing algorithms and programs. The algebra-algorithmic integrated toolkit for design and synthesis of programs IDS, the rewriting rules system TermWare, and the auto-tuning framework TuningGenie are presented. IDS uses algebraic specifications based on Glushkov's algebra of algorithms, which are represented in three forms: algebraic (regular scheme), natural linguistic, and graphical (flowgraphs). IDS is based on the method of dialogue design of syntactically correct algorithm schemes, which eliminates syntax errors during construction of algorithm specifications. To automate transformations of algorithms and programs being designed, the rewriting rules system TermWare is used. TuningGenie framework is applied to automate the adjustment of programs to a target computing environment.
Chapter Preview


The algebra-algorithmic approach (Andon, Doroshenko, Tseytlin, & Yatsenko, 2007; Doroshenko, Tseytlin, Yatsenko, & Zachariya, 2006) is supported by a number of tools developed within the framework of Kyiv algebraic-cybernetic school. The first such tool was the system called MULTIPROCESSIST (Yushchenko, Tseytlin, Hrytsay, & Terzyan, 1989), developed in the 1980s in the programming automation department of V. M. Glushkov Institute of Cybernetics. The system provided the multilevel design of algorithms and data structures represented in the form of schemes in Glushkov’s system of algorithmic algebra (SAA) and synthesis of corresponding programs. The algebraic approach was also used at development of the system for transformation of algorithm schemes (Petrushenko, 1991). The method of controlling spaces based on algebraic approach was used in the parallel programming technology PARUS (Anisimov & Kulyabko, 1984).

In this chapter, the developed tools for programming automation are considered, which continue the aforementioned research, namely, the Integrated toolkit for Design and Synthesis of programs (IDS) (Andon et al., 2007; Doroshenko, Ivanenko, Ovdii, & Yatsenko, 2016; Doroshenko, Zhereb, & Yatsenko, 2013; Yatsenko, 2012), the term rewriting system TermWare (Doroshenko & Shevchenko, 2006; “TermWare”, n.d.) (see also Chapter 3) and the auto-tuning framework TuningGenie (Ivanenko, Doroshenko, Zhereb, 2014).

The approach being considered is related to works on automated synthesis of program code from specifications (Flener, 2002; Gulwani, 2010). The important aspects of program synthesis include:

  • format of inputs (specifications) — how specifications or other inputs for synthesis are provided;

  • methods for supporting particular subject domains — how the proposed approach is specialized for a given domain, so that domain knowledge can be used to produce more efficient programs and/or to improve developer’s productivity;

  • techniques for implementing transformation from specifications to output program code.

These aspects roughly correspond to three dimensions of program synthesis discussed in (Gulwani, 2010):

  • user intent describes specifications;

  • search space restricts all possible programs to a manageable subset;

  • search technique describes how transformations are implemented.

For input specification, a popular option is using domain-specific languages that allow capturing requirements of a subject domain. In (Bagheri & Sullivan, 2012), authors describe Pol, a system that transforms specifications in Alloy language (Jackson, 2002) into a platform-specific code that targets different object-oriented frameworks. A similar approach is used in (Mannadiar & Vangheluwe, 2010): domain-specific models are transformed automatically into mobile applications for Android platform. Domain-specific languages can reduce the size of specifications significantly, because many details are already accounted for in domain-specific language constructs. However, creating a new DSL can require significant effort, and learning it might be hard for a domain expert.

It is possible to make DSL easier to learn by using graphical modeling language. For instance, in (Batory, 2007) a graphical tool is described that operates on state charts and eventually generates web components. Paper (Mannadiar & Vangheluwe, 2010) also develops graphical language including state charts and models of user interface screens. Such an approach works well for small specifications, but becomes inconvenient as the size of models grows and their graphical representations do not fit into a single page.

Key Terms in this Chapter

Rule Patterns: The facilities of the rewriting rules framework TermWare.NET, which are applied for a transition between a low-level (more detailed) model of a program and its high-level version.

SAA/1: The algorithmic language based on Glushkov’s system of algorithmic algebras and focused on natural linguistic representation of schemes. It is applied for multilevel structured designing and documenting of sequential and parallel algorithms and programs.

TermWare.NET: The toolkit based on rewriting rules system TermWare and intended for transformation of programs on Microsoft.NET platform.

TermWare: An open-source implementation of rewriting rules engine written in Java. It provides a language for describing rewriting rules that operate on data structures called terms and also a rule engine that interprets rules to transform terms.

SAA Scheme: A representation of an algorithm in algorithmic language SAA/1.

TuningGenie: The framework automating the adjustment of programs to a target computing environment.

Regular Scheme (RS): A representation of an algorithm in the system of algorithmic algebras (SAA).

Integrated Toolkit for Design and Synthesis of Programs (IDS): The software system intended for automated constructing of sequential and parallel algorithm schemes represented in the modified system of algorithmic algebras (SAA-M) and synthesis of programs in C, C++, Java languages.

Glushkov’s System of Algorithmic Algebras (SAA, Glushkov’s Algebra): The two-sorted algebra focused on analytical form of representation of algorithms and formalized transformation of these representations.

Complete Chapter List

Search this Book: