I wrote a simple stack based language, and am looking to exhaustively generate all programs for it, to find the shortest program that generates a particular output.
Given a program fragment, I can determine if it is terminated, and, if not, how many operands it requires. Currently, my search strategy is:
If program is terminated --> test it else --> add all programs with one additional operand to the queue
However, the queue ends up using too much space. Instead, I'd rather keep the queue small, and find a way to produce all valid programs efficiently (more efficiently than just trying all program text). What is a good strategy to generate all valid programs for a simple stack language?
UPDATE The language is guaranteed to halt (and is of course not Turing complete).
UPDATE: The approach I am working on is as follows:
- Observe that, for certain program fragments, nothing that can be appended to them will make them valid
- Define an ordering over each token that may appear in a program.
- Define a "mayBeAppendedToToMakeAValidProgram" over a incomplete program.
- For n = 0 to infinity:
- Start with a program of n tokens; set each token to the first
- Increment token-0 until mayBeAppendedToToMakeAValidProgram(token-0)
- Increment token-1 until mayBeAppendedToToMakeAValidProgram(token-0 + token-1)
- Etc. until the last token
- Increment the last token until the program is valid; test that program
- On to the next one