# From Requirements to Source Code: Evolution of Behavioral Programs
## 1 Introduction  
Search-based software engineering (SBSE) applies search-based techniques to software engineering tasks, of which an important one is the improvement and generation of software. This task is difficult to achieve due to several reasons, including the complexity of modern programming languages, the difficulty in evaluating the generated software, and the linearity of code--a small change might \"break\" the entire program's behavior. To overcome these difficulties we propose the use of genetic programming (GP) to evolve _behavioral programs_.  
Context-oriented behavioral programming (COBP) [1] is a software development and modeling paradigm designed to allow users to program reactive systems in a natural and intuitive manner that is aligned with how humans perceive the system requirements. A behavioral program consists of a set of context-dependent scenarios (that state what to do) and anti-scenarios (that state what not to do), which are interwoven at run-time to generate a combined reactive system. Each scenario and anti-scenario is specified as a sequential thread of execution that isolates a specific aspect of the system behavior, preferably an individual requirement; it is referred to as a _b-thread_. An application-agnostic execution mechanism repeatedly collects these scenarios, chooses actions that are consistent with all the scenarios, executes them, and continuously informs them of each selection. We elaborate on COBP in Section 3.  
A behavioral program has unique characteristics that makes it an excellent candidate for code evolution:* Repetitive structure, which allows for a simple representation of a program as an abstract syntax tree (AST).
* Small independent components that are easier to change and adjust, since in many cases breaking one b-thread has little effect on the other b-threads.
* Synthesis, formal reasoning, and verification algorithms can be used to evaluate a generated program's performance.  
In this paper we demonstrate how COBP programs can be evolved through GP, show-casing the benefits of COBP by focusing on the game of tic-tac-toe. Specifically, we evolve _from scratch_ a highly competent O player specified as a set of b-threads. Creating such a player requires the specification of different behaviors, such as place third \"O\" when possible, block \"X\" from winning, etc. We will show evolution created from scratch a complete program that consists of different modules that specify these behaviors. Most work on code evolution focuses on genetic improvements of existing code and code evolution of small modules, such as methods (elaborated in Section 2). Thus, while tic-tac-toe may be seen as a toy problem, creating a complete program from scratch is complicated. We are aware of no attempt at generating from scratch a complete program for tic-tac-toe.  
As we will show, our evolved individuals have the repetitive structure of behavioral programs. Most modules of our best individual are self-explanatory and adhere to a known strategy for the game.  
For evolving COBP programs, we design the following: a domain-independent grammar for behavioral programs, augmented with terminals for tic-tac-toe; type-based, COBP-oriented genetic operators; and a fitness function that uses a behavioral program's flow of events.  
The contributions of our work are as follows:  
1. We provide a methodology and tools for evolving complete programs from scratch.
2. We design a domain-independent grammar for behavioral programs.
3. We design domain-independent, type-based, COBP-oriented genetic operators.
4. We evolve a highly competent player for tic-tac-toe.
5. Our evolved programs are well structured, consisting of multiple modules that are explainable and similar to our handcrafted program.  
We first present a short survey on the field of SBSE and code-generation in Section 2, followed by a short primer on behavioral programming in Section 3. We then explain our method in Section 4 in detail, and present our results in Section 5. Finally, we present concluding remarks in Section 6.