- author = "Guilherme Espada and Leon Ingelse and Paulo Canelas and Pedro Barbosa and Alcides Fonseca",
- title = "Data Types as a More Ergonomic Frontend for Grammar-Guided Genetic Programming",
- booktitle = "21st ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences (GPCE 2022)",
- year = "2022",
- editor = "Bernhard Scholz and Yukiyoshi Kameyama",
- pages = "86--94",
- address = "Auckland, New Zealand",
- month = dec # " 6-7",
- publisher = "ACM",
- keywords = "genetic algorithms, genetic programming, STGP, Genetic Programming Framework, Grammar-guided Genetic Programming, Strongly-Typed Genetic Programming",
- isbn13 = "9781450399203",
-
URL = "
https://arxiv.org/abs/2210.04826",
-
DOI = "
doi:10.1145/3564719.3568697",
-
code_url = "https://github.com/alcides/GeneticEngine",
-
abstract = "Genetic Programming (GP) is an heuristic method that
can be applied to many Machine Learning, Optimization
and Engineering problems. In particular, it has been
widely used in Software Engineering for Test-case
generation, Program Synthesis and Improvement of
Software (GI). Grammar-Guided Genetic Programming
(GGGP) approaches allow the user to refine the domain
of valid program solutions. Backus Normal Form is the
most popular interface for describing Context-Free
Grammars (CFG) for GGGP. BNF and its derivatives have
the disadvantage of interleaving the grammar language
and the target language of the program.
We propose to embed the grammar as an internal Domain-Specific Language in the host language of the framework. This approach has the same expressive power as BNF and EBNF while using the host language type-system to take advantage of all the existing tooling: linters, formatters, type-checkers, autocomplete, and legacy code support. These tools have a practical utility in designing software in general, and GP systems in particular.
We also present Meta-Handlers, user-defined overrides of the tree-generation system. This technique extends our object-oriented encoding with more practicability and expressive power than existing CFG approaches, achieving the same expressive power of Attribute Grammars, but without the grammar vs target language duality.
Furthermore, we evidence that this approach is feasible, showing an example Python implementation as proof. We also compare our approach against textual BNF-representations w.r.t. expressive power and ergonomics. These advantages do not come at the cost of performance, as shown by our empirical evaluation on 5 benchmarks of our example implementation against PonyGE2. We conclude that our approach has better ergonomics with the same expressive power and performance of textual BNF-based grammar encodings.",
- notes = "University of Lisbon",
