On the difficulty of benchmarking inductive program synthesis methods

Edward Pantridge, Tomas Helmuth, Nicholas Freitag McPhee, Lee Spector

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    8 Scopus citations

    Abstract

    A variety of inductive program synthesis (IPS) techniques have recently been developed, emerging from di.erent areas of computer science. However, these techniques have not been adequately compared on general program synthesis problems. In this paper we compare several methods on problems requiring solution programs to handle various data types, control structures, and numbers of outputs. .e problem set also spans levels of abstraction; some would ordinarily be approached using machine code or assembly language, while others would ordinarily be approached using highlevel languages. .e presented comparisons are focused on the possibility of success; that is, on whether the system can produce a program that passes all tests, for all training and unseen testing inputs. .e compared systems are Flash Fill, MagicHaskeller, TerpreT, and two forms of genetic programming. .e two genetic programming methods chosen were PushGP and Grammar Guided Genetic Programming. .e results suggest that PushGP and, to an extent, TerpreT and Grammar Guided Genetic Programming are more capable of finding solutions than the others, albeit at a higher computational cost. A more salient observation is the dificulty of comparing these methods due to drastically di.erent intended applications, despite the common goal of program synthesis.

    Original languageEnglish (US)
    Title of host publicationGECCO 2017 - Proceedings of the Genetic and Evolutionary Computation Conference Companion
    PublisherAssociation for Computing Machinery, Inc
    Pages1589-1596
    Number of pages8
    ISBN (Electronic)9781450349390
    DOIs
    StatePublished - Jul 15 2017
    Event2017 Genetic and Evolutionary Computation Conference Companion, GECCO 2017 - Berlin, Germany
    Duration: Jul 15 2017Jul 19 2017

    Publication series

    NameGECCO 2017 - Proceedings of the Genetic and Evolutionary Computation Conference Companion

    Conference

    Conference2017 Genetic and Evolutionary Computation Conference Companion, GECCO 2017
    CountryGermany
    CityBerlin
    Period7/15/177/19/17

    Bibliographical note

    Funding Information:
    National Science Foundation under Grants No. 1617087, 1129139 and 1331283.

    Keywords

    • Benchmarking
    • Genetic programming
    • Inductive Program Synthesis
    • Machine Learning

    Fingerprint Dive into the research topics of 'On the difficulty of benchmarking inductive program synthesis methods'. Together they form a unique fingerprint.

    Cite this