Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search-based program synthesis
Alur R., Singh R., Fisman D., Solar-Lezama A.  Communications of the ACM 61 (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?
Other reviews under "General": Date
iMapReduce: a distributed computing framework for iterative computation
Zhang Y., Gao Q., Gao L., Wang C.  Journal of Grid Computing 10(1): 47-68, 2020. Type: Article
Sep 28 2021
Soft computing: techniques in engineering science
Ram M., Singh S.,  DE GRUYTER, Berlin, Germany, 2020. 230 pp. Type: Book (978-3-110625-60-8)
Apr 22 2021
 Guide to competitive programming: learning and improving algorithms through contests
Laaksonen A.,  Springer International Publishing, New York, NY, 2017. 283 pp. Type: Book (978-3-319725-46-8)
Oct 30 2018

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2021 ThinkLoud, Inc.
Terms of Use
| Privacy Policy