Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Search-based program synthesis
Alur R., Singh R., Fisman D., Solar-Lezama A. Communications of the ACM61 (12):84-93,2018.Type:Article
Date Reviewed: Mar 19 2019

Program synthesis aims at the automatic generation of “an executable implementation ... from a high-level logical specification of the desired input-to-output behavior.” The review article concentrates on syntax-guided synthesis. This approach to automatic program generation gives a specification of a function for the creation of a grammar that specifies additional semantic constraints--in effect the language in which the program is to be written--and a program implementing the specification.

The article uses a running example in which the grammar allows simple linear expressions and conditionals. One way to proceed is to search through increasingly complex expressions from the grammar for an implementation. The article describes how this can be done in a somewhat efficient manner. Other approaches are outlined; one particularly intriguing approach uses decision tree learning to determine the program. This is particularly transparent in the case where conditionals are required.

The article describes the research activity in the area as it is fostered through SV-COMP, “a competition of automated tools for software verification held annually in conjunction with [the European Joint Conferences on Theory and Practice of Software, ETAPS].”

As a survey, the article covers a considerable amount of ground, always in a lucid expository manner with adequate examples that illustrate the ideas. For readers interested in an introduction to the contemporary work on program synthesis or the automatic synthesis of programs, this article is highly recommended.

Reviewer:  J. P. E. Hodgson Review #: CR146476 (1906-0234)
Bookmark and Share
  Reviewer Selected
Featured Reviewer
 
 
General (D.1.0 )
 
 
Search Process (H.3.3 ... )
 
 
Software Development (K.6.3 ... )
 
Would you recommend this review?
yes
no
Other reviews under "General": Date
Problems in programming
Vitek A., Tvrdy I., Reinhardt R., Mohar B. (ed), Martinec M., Dolenc T., Batagelj V. (ed), John Wiley & Sons, Inc., New York, NY, 1991. Type: Book (9780471930174)
Aug 1 1992
KNOs: KNowledge acquisition, dissemination, and manipulation Objects
Tsichritzis D., Fiume E., Gibbs S., Nierstrasz O. ACM Transactions on Information Systems 5(1): 96-112, 1987. Type: Article
Nov 1 1987
Programmer perceptions of productivity and programming tools
Hanson S. (ed), Rosinski R. Communications of the ACM 28(2): 180-189, 1985. Type: Article
Jul 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy