-
Notifications
You must be signed in to change notification settings - Fork 94
Portal: Stack
A total of 11 stacks is used in Clojush to run the Push programs. And stack is one of the core idea of Push/Clojush. This portal brings information about stack-based languages and stacks in Clojush. The first section is an introduction to the general introduction to the ideas while the second part links to some detailed resources.
Stack is a data structure. The feature of a stack could be described with the word LIFO (Last In First Out). Generally, 2 operations are widely used on stacks. push would add an item on the top of a stack while pop would get the top item out from a stack. So the item which is pushed into the stack last would be on the top and it would be the first item when we are popping the stack.
A typical stack-based programming language is postscript. A very basic postscript code is:
1 2 +1 and 2 would be pushed into the stack. When the instruction + is being executed, 2 items would be popped and the result would be pushed back to the stack. Thus in this example, 1 and 2 would be popped and the result is calculated to be 3, which would be pushed to the stack.
The stack system in Clojush is more complex than the one in postscript. A Push program contains only instructions. When Clojush is executing an instruction, it would find the inputs from the related stack and after calculating the result would be pushed into the target stack.
For example integer_lt compares 2 integers and decide whether the first one is lesser than the second one or not. This instruction takes 2 integers as inputs and outputs a boolean value. Thus when it is executed, Clojush would gets the inputs from the :integer stack and pushes the result into the :boolean stack.
If there isn’t enough items in the inputing stack, it would be regarded as a noop, which stands for "no options". And nothing would be done.
In Clojush, 11 stacks are defined. They are: :exec, :integer, :float, :code, :boolean, :string, :zip, :tag, :auxiliary, :return and :environment.
The stacks are defined in global.clj.
;; push-types is the list of stacks used by the Push interpreter
(def push-types '(:exec :integer :float :code :boolean :string :zip
:tag :auxiliary :return :environment)) ;; Stack typesBesides this definition, various functions which operates the stacks are defined in Clojush. Detailed information is in Operations on Stacks.
:integer and :float share most of their instructions. So the detail is in Integer and Float Instructions.
:integer and :float share most of their instructions. So the detail is in Integer and Float Instructions.
The :exec stack was introduced in Push3. The general idea of :exec is that it’s a place to store instructions which are needed to be executed subsequently. While :exec stack is not empty, items would be popped and executed. A detailed introduction to :exec is in GECCO-2005 paper.
Tags are positive numbers. The idea of tagging is designed for modularity in Genetic Programming. A block of code is tagged with a number. When you are trying to get something with a tag value, the closest match would be returned.
What is a closest match? You can image it as a clock. The closest match is always the nearest tag in the clockwise direction. Normally it would be larger than the value, but it would turn over when it reaches the biggest value.
Further information on this topic could be found at Tag-based Modularity in Tree-based Genetic Programming and Tag-Based Modules in Genetic Programming.
Instructions for :exec are included in Code Instructions.
When a program is running, inputs are always needed. Normally, we push the inputs into the appropriate stack before a test starts to run. However, sometimes we want the inputs to be inputed again during a running.
:auxiliary stack is designed to do this. When we are pushing the inputs into the related stack, we would also push them into :auxiliary at the same time. In combination, an instruction called 'in is often designed. This instruction would push the contents in :auxiliary into a specific stack. Thus, when 'in is executed, the values would be inputed again during a run.