Article

The Push3 execution stack and the evolution of control

Authors:

Maarten KeijzerAuthors Info & Claims

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

Pages 1689 - 1696

https://doi.org/10.1145/1068009.1068292

Published: 25 June 2005 Publication History

Abstract

The Push programming language was developed for use in genetic and evolutionary computation systems, as the representation within which evolving programs are expressed. It has been used in the production of several significant results, including results that were awarded a gold medal in the Human Competitive Results competition at GECCO-2004. One of Push's attractive features in this context is its transparent support for the expression and evolution of modular architectures and complex control structures, achieved through explicit code self-manipulation. The latest version of Push, Push3, enhances this feature by permitting explicit manipulation of an execution stack that contains the expressions that are queued for execution in the interpreter. This paper provides a brief introduction to Push and to execution stack manipulation in Push3. It then presents a series of examples in which Push3 was used with a simple genetic programming system (PushGP) to evolve programs with non-trivial control structures.

References

[1]

R. Abbott, J. Guo, and B. Parviz. Guided genetic programming. In The 2003 International Conference on Machine Learning; Models, Technologies and Applications. CSREA Press, 2003.

[2]

P. J. Angeline and J. B. Pollack. Evolutionary module acquisition. In D. Fogel and W. Atmar, editors, Proceedings of the Second Annual Conference on Evolutionary Programming, pages 154--163, La Jolla, CA, USA, 25-26 Feb. 1993.

[3]

S. Brave. Evolving recursive programs for tree search. In P. J. Angeline and K. E. Kinnear, Jr., editors, Advances in Genetic Programming 2, chapter 10, pages 203--220. MIT Press, Cambridge, MA, USA, 1996.

Digital Library

[4]

R. Crawford-Marks and L. Spector. Size control via size fair genetic operators in the PushGP genetic programming system. In W. B. Langdon, E. Cantú-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M. A. Potter, A. C. Schultz, J. F. Miller, E. Burke, and N. Jonoska, editors, GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, pages 733--739, New York, 9-13 July 2002. Morgan Kaufmann Publishers.

Digital Library

[5]

H. Curry and R. Feys. Combinatory Logic, 1, 1958.

[6]

K. E. Kinnear, Jr. Alternatives in automatic function definition: A comparison of performance. In K. E. Kinnear, Jr., editor, Advances in Genetic Programming, chapter 6, pages 119--141. MIT Press, 1994.

Digital Library

[7]

M. J. Kochenderfer. Evolving hierarchical and recursive teleo-reactive programs through genetic programming. In C. Ryan, T. Soule, M. Keijzer, E. Tsang, R. Poli, and E. Costa, editors, Genetic Programming, Proceedings of EuroGP'2003, volume 2610 of LNCS, pages 84--94, Essex, 14-16 Apr. 2003. Springer-Verlag.

Digital Library

[8]

J. Koza. Genetic programming: A paradigm for genetically breeding populations of computer programs to solve problems. Technical Report STAN-CS-90-1314, Dept. of Computer Science, Stanford University, June 1990.

Digital Library

[9]

J. R. Koza. Hierarchical genetic algorithms operating on populations of computer programs. In N. S. Sridharan, editor, Proceedings of the Eleventh International Joint Conference on Artificial Intelligence IJCAI-89, volume 1, pages 768--774. Morgan Kaufmann, 20-25 Aug. 1989.

Digital Library

[10]

J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992.

Digital Library

[11]

J. R. Koza, David Andre, F. H. Bennett III, and M. Keane. Genetic Programming III: Darwinian Invention and Problem Solving. Morgan Kaufman, Apr. 1999.

Digital Library

[12]

K. S. Leung, K. H. Lee, and S. M. Cheang. Evolving parallel machine programs for a Multi-ALU processor. In D. B. Fogel, M. A. El-Sharkawi, X. Yao, G. Greenwood, H. Iba, P. Marrow, and M. Shackleton, editors, Proceedings of the 2002 Congress on Evolutionary Computation CEC2002, pages 1703--1708. IEEE Press, 2002.

Digital Library

[13]

K. S. Leung, K. H. Lee, and S. M. Cheang. Parallel programs are more evolvable than sequential programs. In C. Ryan, T. Soule, M. Keijzer, E. Tsang, R. Poli, and E. Costa, editors, Genetic Programming, Proceedings of EuroGP'2003, volume 2610 of LNCS, pages 108--120, Essex, 14-16 Apr. 2003. Springer-Verlag.

Digital Library

[14]

M. Nishiguchi and Y. Fujimoto. Evolutions of recursive programs with multi-niche genetic programming (mnGP). In Proceedings of the 1998 IEEE World Congress on Computational Intelligence, pages 247--252, Anchorage, Alaska, USA, 5-9 May 1998. IEEE Press.

[15]

P. Nordin and W. Banzhaf. Evolving Turing-complete programs for a register machine with self-modifying code. In L. Eshelman, editor, Genetic Algorithms: Proceedings of the Sixth International Conference (ICGA95), pages 318--325, Pittsburgh, PA, USA, 15-19 July 1995. Morgan Kaufmann.

Digital Library

[16]

R. Olsson. Inductive functional programming using incremental program transformation. Artificial Intelligence, 74(1):55--81, Mar. 1995.

Digital Library

[17]

T. Perkis. Stack-based genetic programming. In Proceedings of the 1994 IEEE World Congress on Computational Intelligence, volume 1, pages 148--153, Orlando, Florida, USA, 27-29 June 1994. IEEE Press.

[18]

A. Racine, M. Schoenauer, and P. Dague. A dynamic lattice to evolve hierarchically shared subroutines: DL'GP. In W. Banzhaf, R. Poli, M. Schoenauer, and T. C. Fogarty, editors, Proceedings of the First European Workshop on Genetic Programming, volume 1391 of LNCS, pages 220--232, Paris, 14-15 Apr. 1998. Springer-Verlag.

Digital Library

[19]

S. C. Roberts, D. Howard, and J. R. Koza. Evolving modules in genetic programming by subtree encapsulation. In J. F. Miller, M. Tomassini, P. L. Lanzi, C. Ryan, A. G. B. Tettamanzi, and W. B. Langdon, editors, Genetic Programming, Proceedings of EuroGP'2001, volume 2038 of LNCS, pages 160--175, Lake Como, Italy, 18-20 Apr. 2001. Springer-Verlag.

Digital Library

[20]

J. Schmidhuber. Optimal ordered problem solver. Technical Report IDSIA-12-02, IDSIA, 31 July 2002.

Digital Library

[21]

M. Schönfinkel. Über die bausteine der mathematischen logik. Mathematische Annalen, 92:307--316, 1924.

[22]

L. Spector. Simultaneous evolution of programs and their control structures. In P. J. Angeline and K. E. Kinnear, Jr., editors, Advances in Genetic Programming 2, chapter 7, pages 137--154. MIT Press, Cambridge, MA, USA, 1996.

Digital Library

[23]

L. Spector. Autoconstructive evolution: Push, pushGP, and pushpop. In L. Spector, E. D. Goodman, A. Wu, W. B. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. H. Garzon, and E. Burke, editors, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 137--146, San Francisco, California, USA, 7-11 July 2001. Morgan Kaufmann.

[24]

L. Spector. Automatic Quantum Computer Programming: A Genetic Programming Approach, volume 7 of Genetic Programming. Kluwer Academic Publishers, Boston/Dordrecht/New York/London, June 2004. in press.

Digital Library

[25]

L. Spector, J. Klein, C. Perry, and M. Feinstein. Emergence of collective behavior in evolving populations of ying agents. In E. Cantú-Paz, J. A. Foster, K. Deb, D. Davis, R. Roy, U.-M. O'Reilly, H.-G. Beyer, R. Standish, G. Kendall, S. Wilson, M. Harman, J. Wegener, D. Dasgupta, M. A. Potter, A. C. Schultz, K. Dowsland, N. Jonoska, and J. Miller, editors, Genetic and Evolutionary Computation - GECCO-2003, volume 2723 of LNCS, pages 61--73, Chicago, 12-16 July 2003. Springer-Verlag.

Digital Library

[26]

L. Spector, J. Klein, C. Perry, and M. Feinstein. Emergence of collective behavior in evolving populations of ying agents. Genetic Programming and Evolvable Machines, 6(1):111--125, Mar. 2005.

Digital Library

[27]

L. Spector, C. Perry, J. Klein, and M. Keijzer. Push 3.0 programming language description. Technical Report HC-CSTR-2004-02, Hampshire College School of Cognitive Science, 2004. http://hampshire.edu/lspector/push3-description.html.

[28]

L. Spector and A. Robinson. Genetic programming and autoconstructive evolution with the push programming language. Genetic Programming and Evolvable Machines, 3(1):7--40, Mar. 2002.

Digital Library

[29]

K. Stoffel and L. Spector. High-performance, parallel, stack-based genetic programming. In J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo, editors, Genetic Programming 1996: Proceedings of the First Annual Conference, pages 224--229, Stanford University, CA, USA, 28-31 July 1996. MIT Press.

Digital Library

[30]

E. Tchernev. Forth crossover is not a macromutation? In J. R. Koza, W. Banzhaf, K. Chellapilla, K. Deb, M. Dorigo, D. B. Fogel, M. H. Garzon, D. E. Goldberg, H. Iba, and R. Riolo, editors, Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 381--386, University of Wisconsin, Madison, Wisconsin, USA, 22-25 July 1998. Morgan Kaufmann.

[31]

P. A. Whigham and R. I. McKay. Genetic approaches to learning recursive relations. In X. Yao, editor, Progress in Evolutionary Computation, volume 956 of Lecture Notes in Artificial Intelligence, pages 17--27. Springer-Verlag, 1995.

Digital Library

[32]

M. L. Wong. Applying adaptive grammar based genetic programming in evolving recursive programs. In S.-B. Cho, H. X. Nguyen, and Y. Shan, editors, Proceedings of The First Asian-Pacific Workshop on Genetic Programming, pages 1--8, Rydges (lakeside) Hotel, Canberra, Australia, 8 Dec. 2003.

[33]

M. L. Wong and K. S. Leung. Evolving recursive functions for the even-parity problem using genetic programming. In P. J. Angeline and K. E. Kinnear, Jr., editors, Advances in Genetic Programming 2, chapter 11, pages 221--240. MIT Press, Cambridge, MA, USA, 1996.

Digital Library

[34]

M. L. Wong and K. S. Leung. Learning recursive functions from noisy examples using generic genetic programming. In J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo, editors, Genetic Programming 1996: Proceedings of the First Annual Conference, pages 238--246, Stanford University, CA, USA, 28-31 July 1996. MIT Press.

Digital Library

[35]

G. T. Yu. An Analysis of the Impact of Functional Programming Techniques on Genetic Programming. PhD thesis, University College, London, Gower Street, London, WC1E 6BT, 1999.

[36]

T. Yu. Hierachical processing for evolving recursive and modular programs using higher order functions and lambda abstractions. Genetic Programming and Evolvable Machines, 2(4):345--380, Dec. 2001.

Digital Library

[37]

T. Yu. A higher-order function approach to evolve recursive programs. In Genetic Programming Theory and Practice 3. Kluwer, 2005. To appear.

[38]

T. Yu and C. Clack. Recursion, lambda abstractions and genetic programming. In J. R. Koza, W. Banzhaf, K. Chellapilla, K. Deb, M. Dorigo, D. B. Fogel, M. H. Garzon, D. E. Goldberg, H. Iba, and R. Riolo, editors, Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 422--431, University of Wisconsin, Madison, Wisconsin, USA, 22-25 July 1998. Morgan Kaufmann.

Cited By

Frazier JHelmuth TLi XHandl J(2024)Explaining Automatically Designed Software Defined Perimeters with a Two Phase Evolutionary Computation SystemProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664155(1527-1535)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3664155
De La Torre CCortacero KCussat-Blanc SWilson DLi XHandl J(2024)Multimodal Adaptive Graph EvolutionProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3654347(499-502)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3654347
Boldi RBao ABriesch MHelmuth TSobania DSpector LLalejini ALi XHandl J(2024)A Comprehensive Analysis of Down-sampling for Genetic Programming-based Program SynthesisProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3654134(487-490)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3654134
Show More Cited By

Index Terms

The Push3 execution stack and the evolution of control
1. Software and its engineering
  1. Software notations and tools
    1. Context specific languages
      1. Specialized application languages

Recommendations

Graph structured program evolution
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

In recent years a lot of Automatic Programming techniques have developed. A typical example of Automatic Programming is Genetic Programming (GP), and various extensions and representations for GP have been proposed so far. However, it seems that more ...
Automatic python programming using stack-based genetic programming
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation

Traditional genetic programming uses tree-like data structure to represent a program. It should be converted into a Lisp code, or needs a custom-made virtual machine or interpreter to execute the program generated. Recently, there is a study on genetic ...
Expressive genetic programming: tutorial: 2012 genetic and evolutionary computation conference (GECCO-2012)
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation

The language in which evolving programs are expressed can have significant impacts on the problem-solving capabilities of a genetic programming system. These impacts stem both from the absolute computational power of the languages that are used, as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

June 2005

2272 pages

ISBN:1595930108

DOI:10.1145/1068009

Editor:
Hans-Georg Beyer
Vorarlberg University of Applied Sciences, Austria
,
General Chair:
Una-May O'Reilly
CSAIL, MIT

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO05

Sponsor:

GECCO05: Genetic and Evolutionary Computation Conference

June 25 - 29, 2005

Washington DC, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

120
Total Citations
View Citations
400
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Frazier JHelmuth TLi XHandl J(2024)Explaining Automatically Designed Software Defined Perimeters with a Two Phase Evolutionary Computation SystemProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664155(1527-1535)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3664155
De La Torre CCortacero KCussat-Blanc SWilson DLi XHandl J(2024)Multimodal Adaptive Graph EvolutionProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3654347(499-502)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3654347
Boldi RBao ABriesch MHelmuth TSobania DSpector LLalejini ALi XHandl J(2024)A Comprehensive Analysis of Down-sampling for Genetic Programming-based Program SynthesisProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3654134(487-490)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3654134
Freitag McPhee NLussier R(2024)The Impact of Step Limits on Generalization and Stability in Software SynthesisGenetic Programming Theory and Practice XX10.1007/978-981-99-8413-8_5(87-104)Online publication date: 18-Feb-2024
https://doi.org/10.1007/978-981-99-8413-8_5
De La Torre CLavinas YCortacero KLuga HWilson DCussat-Blanc S(2024)Multimodal Adaptive Graph Evolution for Program SynthesisParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_19(306-321)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70055-2_19
Helmuth TPantridge EFrazier JSpector L(2024)Generational Computation Reduction in Informal Counterexample-Driven Genetic ProgrammingGenetic Programming10.1007/978-3-031-56957-9_2(21-37)Online publication date: 3-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-56957-9_2
Helmuth TFrazier JShi YAbdelrehim ASilva SPaquete L(2023)Human-Driven Genetic Programming for Program Synthesis: A PrototypeProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596373(1981-1989)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596373
Pantridge EHelmuth TSilva SPaquete L(2023)Solving Novel Program Synthesis Problems with Genetic Programming using Parametric PolymorphismProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590502(1175-1183)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590502
Zhang HChen QXue BBanzhaf WZhang MSilva SPaquete L(2023)A Double Lexicase Selection Operator for Bloat Control in Evolutionary Feature Construction for RegressionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590365(1194-1202)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590365
Sobania DSchweim DRothlauf F(2023)A Comprehensive Survey on Program Synthesis With Evolutionary AlgorithmsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.316232427:1(82-97)Online publication date: Feb-2023
https://doi.org/10.1109/TEVC.2022.3162324
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents