Abstract
We demonstrate a functional style recursion implementation to evolve recursive programs. This approach re-expresses a recursive program using a non-recursive application of a higher-order function. It divides a program recursion pattern into two parts: the recursion code and the application of the code. With the higher-order functions handling recursion code application, GP effort becomes focused on the generation of recursion code. We employed this method to evolve two recursive programs: a strstr C library function, and programs that produce the Fibonacci sequence. In both cases, the program space defined by higher-order functions are much easier for GP to search and to find a solution. We have learned about higher-order function selection and fitness assignment through this study. The next step will be to test the approach on applications with open-ended solutions, such as evolutionary design.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Field, Anthony J. and Harrison, Peter G. (1988). Functional Programming. Addison-Wesley Publishing Company.
Jones, Simon Peyton (2002). Haskell 98 language and libraries, the revised report. Technical report, Haskell Org.
Koza, John R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA.
Koza, John R., Andre, David, Bennett III, Forrest H, and Keane, Martin (1999). Genetic Programming 3: Darwinian Invention and Problem Solving. Morgan Kaufman.
Olsson, Roland (1995). Inductive functional programming using incremental program transformation. Artificial Intelligence, 74(1):55–81.
Yu, Gwoing Tina (1999). An Analysis of the Impact of Functional Programming Techniques on Genetic Programming. PhD thesis, University College, London, Gower Street, London, WC1E 6BT.
Yu, Tina, Chen, Shu-Heng, and Kuo, Tzu-Wen (2004). Discovering financial technical trading rules using genetic programming with lambda abstraction. In U-M O’Reilly, T. Yu, R. Riolo and Worzel, B., editors, Genetic Programming Theory and Practice II, pages 11–30.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer Science+Business Media, Inc.
About this chapter
Cite this chapter
Yu, T. (2006). A Higher-Order Function Approach to Evolve Recursive Programs. In: Yu, T., Riolo, R., Worzel, B. (eds) Genetic Programming Theory and Practice III. Genetic Programming, vol 9. Springer, Boston, MA. https://doi.org/10.1007/0-387-28111-8_7
Download citation
DOI: https://doi.org/10.1007/0-387-28111-8_7
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-28110-0
Online ISBN: 978-0-387-28111-7
eBook Packages: Computer ScienceComputer Science (R0)